Методы кластеризации

K-means

Идея проста - фиксируем количество кластеров \(k\). По итогу, каждый \(x_i\) должен быть в том кластере, к центру масс которого он ближе всего. Алгоритм:

Алгоритм k-means

• Инициализируем центроиды (центры масс) кластеров \(\mu_1, \dots, \mu_k \in \mathbb{R}^n\).

• Повторять до сходимости:

  • Для каждой точки \(x^{(i)}\) находим ближайший к ней центр масс

\[c^{(i)} = \arg \underset{j}{\min}{\Vert x^{(i)} - \mu_j \Vert^2}\]

• Для каждого \(j\) переопределяем центры масс исходя из ближайших точек на прошлом шаге

\[\mu_j = \frac{\sum_{i=1}^{N} 1\{c^{(i)} = j\} \cdot x^{(i)}}{\sum_{i=1}^{N} 1\{c^{(i)} = j\}}\]

В алгоритме \(k\) - это параметр, обозначающий количество кластеров, фиксируется изначально. Центроиды \(\mu_j\) представляют собой наши текущие предположения о положении центров кластеров. Инициализация центроидов может происходить различными способами, например, мы можем случайным образом выбрать \(k\) точек из обучающего множества.

Шаги алгоритма:

Алгоритм очень прост и, как правило, работает хорошо на данных, где «истинные» кластеры далеки друг от друга. Тем не менее, он будет плохо работать, если «истинные» кластеры находятся близко к друг другу, или далеки по своей форме от шара.

Show code cell source Hide code cell source

from bokeh.io import output_notebook, show
from bokeh.plotting import figure
from bokeh.models import ColumnDataSource, Button, CustomJS
from bokeh.layouts import column, row
import numpy as np

from bokeh.resources import INLINE
output_notebook(INLINE, hide_banner = True)

# Создаем начальные данные
np.random.seed(0)
cluster1 = np.random.normal([2.5, 2.5], 0.5, (50, 2))
cluster2 = np.random.normal([4.5, 4.5], 0.5, (50, 2))
data = np.vstack([cluster1, cluster2])

# Инициализируем центроиды с фиксированными начальными значениями
centroids = np.array([[2. + 2*_, 3. + 2*_] for _ in range(2)])

# Создаем источники данных для точек, центроидов и линий
source_points = ColumnDataSource(data=dict(x=data[:, 0], y=data[:, 1], color=["blue"] * 50 + ["green"] * 50))
source_centroids = ColumnDataSource(data=dict(x=centroids[:, 0], y=centroids[:, 1]))
source_lines = ColumnDataSource(data=dict(x_start=[], y_start=[], x_end=[], y_end=[], color=[]))

# Создаем фигуру
p = figure(width=400, height=400, title="K-means Clustering", x_range=(1, 6), y_range=(1, 6),
           tools="", toolbar_location=None)  # Отключаем toolbar и инструменты
p.scatter('x', 'y', color='color', source=source_points, size=6, alpha=0.6)
p.scatter('x', 'y', color="red", source=source_centroids, size=8, alpha=0.8)
p.segment('x_start', 'y_start', 'x_end', 'y_end', color='color', source=source_lines, line_dash="dotted", alpha=0.5)

# JavaScript для запуска анимации
callback = CustomJS(args=dict(source_points=source_points, source_centroids=source_centroids, source_lines=source_lines), code="""
    const data_points = source_points.data;
    const data_centroids = source_centroids.data;
    const lines = source_lines.data;
    const x_points = data_points['x'];
    const y_points = data_points['y'];
    let centroids_x = data_centroids['x'];
    let centroids_y = data_centroids['y'];

    function update() {
        // Расстояния и метки для точек относительно центроидов
        const labels = Array.from({length: x_points.length}, () => 0);
        for (let i = 0; i < x_points.length; i++) {
            const dists = [
                Math.hypot(x_points[i] - centroids_x[0], y_points[i] - centroids_y[0]),
                Math.hypot(x_points[i] - centroids_x[1], y_points[i] - centroids_y[1])
            ];
            labels[i] = dists[0] < dists[1] ? 0 : 1;
        }

        // Вычисляем новые центроиды
        const new_centroids_x = [0, 0];
        const new_centroids_y = [0, 0];
        const counts = [0, 0];

        for (let i = 0; i < labels.length; i++) {
            const label = labels[i];
            new_centroids_x[label] += x_points[i];
            new_centroids_y[label] += y_points[i];
            counts[label]++;
        }

        // Избегаем деления на ноль и вылетов на бесконечность
        for (let j = 0; j < 2; j++) {
            if (counts[j] > 0) {
                new_centroids_x[j] /= counts[j];
                new_centroids_y[j] /= counts[j];
            } else {
                new_centroids_x[j] = centroids_x[j];
                new_centroids_y[j] = centroids_y[j];
            }
        }

        // Периодическое обновление источников данных для линий
        lines['x_start'] = [];
        lines['y_start'] = [];
        lines['x_end'] = [];
        lines['y_end'] = [];
        lines['color'] = [];
        for (let i = 0; i < labels.length; i++) {
            const color = labels[i] === 0 ? "blue" : "green";
            lines['x_start'].push(x_points[i]);
            lines['y_start'].push(y_points[i]);
            lines['x_end'].push(new_centroids_x[labels[i]]);
            lines['y_end'].push(new_centroids_y[labels[i]]);
            lines['color'].push(color);
        }
        source_lines.change.emit();

        // Плавное перемещение центроидов к новым позициям
        const smooth_factor = 0.02;  // Уменьшено для более плавного перемещения
        centroids_x[0] += smooth_factor * (new_centroids_x[0] - centroids_x[0]);
        centroids_x[1] += smooth_factor * (new_centroids_x[1] - centroids_x[1]);
        centroids_y[0] += smooth_factor * (new_centroids_y[0] - centroids_y[0]);
        centroids_y[1] += smooth_factor * (new_centroids_y[1] - centroids_y[1]);

        // Обновление цвета точек в зависимости от их кластера
        const colors = Array.from(labels, label => label === 0 ? "blue" : "green");
        data_points['color'] = colors;

        source_points.change.emit();
        source_centroids.change.emit();
    }

    function animate() {
        if (window.intervalID) {
            clearInterval(window.intervalID);  // Сброс текущей анимации, если она есть
        }
        window.intervalID = setInterval(update, 30);  // Более частое обновление для плавности
    }

    animate();  // Старт анимации при загрузке
""")

# Кнопка для запуска анимации
button_start = Button(label="Start K-means Animation", button_type="success")
button_start.js_on_click(callback)

# Кнопка для рестарта
button_restart = Button(label="Restart Animation", button_type="warning")
button_restart.js_on_click(CustomJS(args=dict(source_points=source_points, source_centroids=source_centroids, source_lines=source_lines), code="""
    // Генерация новых случайных позиций центроидов
    source_centroids.data['x'] = [1 + Math.random() * 5, 1 + Math.random() * 5];
    source_centroids.data['y'] = [1 + Math.random() * 5, 1 + Math.random() * 5];
    source_centroids.change.emit();

    // Очистка данных линий
    source_lines.data['x_start'] = [];
    source_lines.data['y_start'] = [];
    source_lines.data['x_end'] = [];
    source_lines.data['y_end'] = [];
    source_lines.data['color'] = [];
    source_lines.change.emit();

    // Немедленное перекрашивание точек
    const data_points = source_points.data;
    const x_points = data_points['x'];
    const y_points = data_points['y'];
    const centroids_x = source_centroids.data['x'];
    const centroids_y = source_centroids.data['y'];

    const labels = Array.from({length: x_points.length}, () => 0);
    for (let i = 0; i < x_points.length; i++) {
        const dists = [
            Math.hypot(x_points[i] - centroids_x[0], y_points[i] - centroids_y[0]),
            Math.hypot(x_points[i] - centroids_x[1], y_points[i] - centroids_y[1])
        ];
        labels[i] = dists[0] < dists[1] ? 0 : 1;
    }

    const colors = Array.from(labels, label => label === 0 ? "blue" : "green");
    data_points['color'] = colors;
    source_points.change.emit();

    if (window.intervalID) {
        clearInterval(window.intervalID);  // Сброс текущей анимации
    }
"""))

# Располагаем кнопки в одном ряду и над графиком
layout = column(row(button_start, button_restart), p)
show(layout)

Сходимость k-means

Введём так называемую distortion function:

\[J(c, \mu) = \sum_{i=1}^{N} \Vert x^{(i)} - \mu_{c^{(i)}} \Vert^2\]

\(J\) равна сумме квадратов расстояний между каждым \(x^{(i)}\) и центром масс кластера \(\mu_{c^{(i)}}\), к которому он был отнесен. Внутренний цикл k-means многократно минимизирует \(J\) по отношению к \(c\) при фиксированном \(\mu\), затем минимизирует \(J\) по отношению к \(\mu\) при фиксированном \(c\). Таким образом, \(J\) монотонно убывает и может служить параметром сходимости.

На самом деле возможно, что k-means колеблется между несколькими различными кластеризациями, которые дают одинаковые значения \(\mu\) и/или \(c\). \(J\) - невыпуклая функция, поэтому координатный спуск по \(J\) не гарантирует сходимость к глобальному минимуму. В качестве обходного пути можно использовать многократный запуск k-means, выбирая в итоге кластеризацию, дающую наименьшее distortion.

Примечание о выборе количества кластеров

В k-means мы заранее обязаны выбрать количество кластеров \(k\) или n_clusters. В то же время, как правило, мы не знаем сколько их вообще должно быть. Возможные пути работы с этой проблемой:

• Запустить k-mean несколько раз, каждый раз с разным числом кластеров, и в итоге выбрать кластер с наименьшим distortion (с этим поаккуратнее, можете ещё «занулить» \(J\))

• Использовать другие алгоритмы кластеризации, в которых n_clusters не фиксировано.

Примечание об обработке данных

Нормировка данных перед применением алгоритма - штука спорная. Она может привести к сильному изменению положений всех объектов, что загубит кластеризацию. После же выполнения алгоритма (пост-процессинг), можно, например, удалить кластеры с маленьким числом объектов, сказав, что это выбросы.

import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

# Генерация случайных данных с помощью функции make_blobs
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# Визуализация сгенерированных данных
plt.scatter(X[:, 0], X[:, 1], s=50, edgecolor='k')
plt.show()

# Инициализация и обучение модели k-means
kmeans = KMeans(n_clusters=5, n_init = 'auto') # Позапускайте несколько раз с разными n_clusters
kmeans.fit(X)
y_kmeans = kmeans.predict(X)

# Вывод
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis', edgecolor='k')

centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.75, label='Centroids', edgecolor='k')
plt.legend()
plt.title('K-Means Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Иерархическая кластеризация

В отличие от K-means, где требуется предварительно выбрать количество кластеров и начальную конфигурацию, в алгоритмах иерархической кластеризации этого не требуется. Вместо этого необходимо задать меру несходства (linkage) между группами объектов (подкластерами).

Эта мера основана на попарном несходстве между двумя группами (подкластерами или самими кластерами). Эти алгоритмы создают иерархию кластеров, в которой кластеры определенного уровня создаются путем слияния кластеров следующего, более низкого уровня. Корнем этой структуры является кластер, содержащий все данные, а листьями - кластеры, состоящие из одного объекта.

Существуют две основные парадигмы:

• Агломеративная: она начинается с объектов как отдельных кластеров. Затем сливается пара кластеров на определенном уровне, имеющих наименьшее межгрупповое несходство (linkage), с целью получения одного, более крупного кластера на верхнем уровне. В агломеративных методах несходство между объединяемыми кластерами является монотонно возрастающим.

• Дивизивная: заключается в разбиении существующего кластера с целью получения двух новых групп, имеющих большее межгрупповое несходство (linkage).

Каждый уровень иерархии представляет собой группировку данных в неравнозначные множества. Необходимо выбрать уровень, который представляет собой удовлетворительную кластеризацию.

Сложно, да? На практике, оно выглядит попроще.

Дендрограмма

Графически представить последовательность группировок подкластеров (иерархию) можно с помощью дендрограммы - дерева, где по оси абсцисс откладывается логическое расстояние (согласно заданной метрике) между кластерами, а высота каждого узла пропорциональна величине межгруппового несходства между двумя его дочерними элементами. Другими словами, чем выше связь между двумя кластерами, тем сильнее различаются их признаки. Чем ниже в дереве сливаются группы наблюдений, тем более схожи их наблюдения. С другой стороны, наблюдения, объединившиеся позже, вблизи корня дерева, могут быть совершенно разными.

Если разрезать дендрограмму по горизонтали на определенной высоте, то данные разделятся на кластеры, представленные вертикальными линиями, пересекающими разрез. Таким образом, на одной дендрограмме можно получить любое количество кластеров в зависимости от высоты горизонтального разреза.

Show code cell source Hide code cell source

from bokeh.io import output_notebook, show
from bokeh.resources import INLINE
output_notebook(INLINE, hide_banner = True)

import numpy as np
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
from bokeh.io import output_notebook, show
from bokeh.models import ColumnDataSource, Slider, CustomJS, Span, LabelSet
from bokeh.layouts import row, column
from bokeh.plotting import figure
from bokeh.transform import factor_cmap
from bokeh.palettes import Category10

# Примерные координаты точек
points = np.array([
    [-1.1, -1.2], [-0.5, -0.4], [-0.8, 0.1],
    [-1.3, -1.5], [-0.2, 0.8], [0.2, -0.8],
    [1.1, 0.6], [0.9, 0.5], [0.1, -0.1]
])

# Выполнение агломеративной кластеризации
Z = linkage(points, 'ward')

# Предварительно рассчитываем кластеры для различных порогов
threshold_values = np.arange(0, 3.1, 0.1)
clusters_dict = {}
for threshold in threshold_values:
    clusters = fcluster(Z, t=threshold, criterion='distance')
    clusters_dict[str(round(threshold, 1))] = clusters.tolist()

# Форматируем данные для построения дендрограммы, убирая лишние линии
dendro_data = dendrogram(Z, no_plot=True)
icoord = np.array(dendro_data['icoord'])
dcoord = np.array(dendro_data['dcoord'])

# Заданный порядок подписей для дендрограммы
leaves = [0, 3, 6, 7, 4, 1, 2, 8, 5]

# Группируем данные для дендрограммы, выделяя ветви под порогом
dendro_segments = []
for xs, ys in zip(icoord, dcoord):
    for i in range(3):  # отрезки в дендрограмме
        dendro_segments.append({
            'x': [xs[i], xs[i+1]],
            'y': [ys[i], ys[i+1]]
        })

# Используем позиции из leaves для правильного отображения подписей
# Добавляем смещение только для существующих индексов
leaf_positions = {}
for idx, leaf in enumerate(leaves):
    x_position = icoord[idx // 2, 1]
    
    # Добавляем смещения для нужных позиций
    if leaf == 3:
        x_position += 10  # Сдвиг вправо для 3
    elif leaf == 7:
        x_position += 10  # Сдвиг вправо для 7
    elif leaf == 4:
        x_position -= 10  # Сдвиг влево для 4
    elif leaf == 2:
        x_position -= 10  # Сдвиг влево для 2
    elif leaf == 5:
        x_position += 25  # Сдвиг влево для 5
    
    leaf_positions[leaf] = (x_position, -0.3)

label_positions = [(x, y + 0.05, str(leaf)) for leaf, (x, y) in leaf_positions.items()]

# Устанавливаем начальные цвета на основе значения threshold=1.5
initial_threshold = '1.5'
initial_clusters = clusters_dict[initial_threshold]
colors = ['#1f77b4', '#ff7f0e', '#2ca02c', '#d62728', '#9467bd', '#8c564b', '#e377c2', '#7f7f7f', '#bcbd22', '#17becf']
initial_colors = [colors[initial_clusters[int(label)] - 1] for _, _, label in label_positions]

# Источник данных для дендрограммы и кластеров
source_dendro = ColumnDataSource(data=dict(
    xs=[seg['x'] for seg in dendro_segments],
    ys=[seg['y'] for seg in dendro_segments]
))
source_points = ColumnDataSource(data=dict(
    x=points[:, 0], y=points[:, 1], cluster=[str(c) for c in initial_clusters],
    label=[str(i) for i in range(len(points))]  # Добавляем метки точек
))

# Источник данных для подписей на дендрограмме
label_source = ColumnDataSource(data=dict(
    x=[pos[0] for pos in label_positions],
    y=[pos[1] for pos in label_positions],
    label=[pos[2] for pos in label_positions],
    color=initial_colors  # Начальные цвета, соответствующие кластерам при threshold=1.5
))

# Фигура для дендрограммы с отключенной панелью инструментов и запретом на перемещение
p_dendro = figure(width=350, height=300, title="Dendrogram", y_axis_label='Distance', y_range=(-0.3, 3.5),
                  toolbar_location=None, tools="", active_scroll=None)
p_dendro.xaxis.visible = False  # Скрываем ось X
p_dendro.toolbar.active_drag = None  # Запрет перетаскивания

# Добавляем линии дендрограммы
p_dendro.multi_line(xs='xs', ys='ys', line_width=2, source=source_dendro, color="black")

# Добавляем подписи номеров точек под линиями дендрограммы
labels_dendro = LabelSet(x='x', y='y', text='label', text_color='color', source=label_source, level='glyph', text_align='center')
p_dendro.add_layout(labels_dendro)

# Добавляем горизонтальную линию, которая изменяется слайдером
threshold_line = Span(location=1.5, dimension='width', line_color='red', line_width=2)
p_dendro.add_layout(threshold_line)

# Фигура для точек с отключенной панелью инструментов и запретом на перемещение
p_points = figure(width=350, height=300, title="Clusters", x_axis_label="X1", y_axis_label="X2",
                  toolbar_location=None, tools="", active_scroll=None)
p_points.toolbar.active_drag = None  # Запрет перетаскивания
p_points.scatter('x', 'y', size=8, source=source_points, 
                 color=factor_cmap('cluster', palette=Category10[10], factors=[str(i) for i in range(1, 11)]))

# Подписи для точек с номерами (со смещением, чтобы избежать наложения)
labels_points = LabelSet(x='x', y='y', text='label', level='glyph', source=source_points,
                         x_offset=5, y_offset=-5)  # Смещение для меток
p_points.add_layout(labels_points)

# Слайдер для отсечения дендрограммы
slider = Slider(start=0, end=3, value=1.5, step=0.1, title="Threshold for Clustering")

# JavaScript для обновления кластеров и цвета подписей на основе значения слайдера
slider.js_on_change('value', CustomJS(args=dict(source_points=source_points, source_dendro=source_dendro, 
                                                label_source=label_source, clusters_dict=clusters_dict, slider=slider, 
                                                threshold_line=threshold_line), code="""
    const threshold = slider.value.toFixed(1);
    threshold_line.location = parseFloat(threshold);  // Обновляем горизонтальную линию
    const clusters = clusters_dict[threshold];
    const colors = ['#1f77b4', '#ff7f0e', '#2ca02c', '#d62728', '#9467bd', '#8c564b', '#e377c2', '#7f7f7f', '#bcbd22', '#17becf'];
    
    // Обновляем кластеры точек
    source_points.data['cluster'] = clusters.map(String);
    source_points.change.emit();
    
    // Обновляем цвета подписей на дендрограмме
    const new_colors = [];
    for (let i = 0; i < label_source.data['label'].length; i++) {
        const pointIndex = parseInt(label_source.data['label'][i]);  // Индекс точки
        const clusterIndex = clusters[pointIndex] - 1;  // Соответствующий кластер
        new_colors.push(colors[clusterIndex]);  // Устанавливаем цвет в зависимости от кластера
    }
    label_source.data['color'] = new_colors;
    label_source.change.emit();
"""))

# Размещение графиков и слайдера
layout = column(row(p_dendro, p_points), slider)
show(layout)