Перейти к содержанию

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

Обзор

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

K-Means (K-средних)

Принцип работы

  1. Инициализировать K центроидов случайным образом
  2. Назначить каждый объект ближайшему центроиду
  3. Пересчитать центроиды как среднее точек в кластере
  4. Повторять шаги 2-3 до сходимости

Формула

Минимизируется сумма квадратов расстояний: 

J = Σᵢ Σⱼ ||xⱼ⁽ⁱ⁾ - μᵢ||²

Гиперпараметры

  • n_clusters: количество кластеров (K)
  • init: метод инициализации ('k-means++', 'random')
  • max_iter: максимальное количество итераций
  • n_init: количество запусков алгоритма

Выбор количества кластеров

  • Метод локтя: поиск "излома" на графике inertia
  • Silhouette score: оценка качества разделения
  • Gap statistic: сравнение с равномерным распределением

Преимущества и недостатки

Преимущества Недостатки
Простота и скорость Нужно задавать K
Масштабируемость Чувствителен к выбросам
Сходимость гарантирована Предполагает сферические кластеры
Чувствителен к инициализации

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

Принцип работы

Строит древовидную структуру кластеров (дендрограмму).

Типы

  • Агломеративная (bottom-up): каждый объект — отдельный кластер, затем объединяем
  • Дивизивная (top-down): все объекты в одном кластере, затем разделяем

Методы связи (Linkage)

  • Single: минимальное расстояние между кластерами
  • Complete: максимальное расстояние
  • Average: среднее расстояние
  • Ward: минимизация дисперсии внутри кластеров

Преимущества и недостатки

Преимущества Недостатки
Не нужно задавать K O(n³) сложность
Дендрограмма для визуализации Не масштабируется
Любая форма кластеров Чувствительна к шуму

DBSCAN (Density-Based Spatial Clustering)

Принцип работы

Группирует точки, находящиеся в областях высокой плотности.

Термины

  • Core point: точка с min_samples соседей в eps-окрестности
  • Border point: имеет меньше соседей, но достижима из core point
  • Noise point: выбросы, не принадлежащие ни одному кластеру

Гиперпараметры

  • eps: радиус окрестности
  • min_samples: минимальное количество точек для core point

Преимущества и недостатки

Преимущества Недостатки
Не нужно задавать K Чувствителен к параметрам
Находит кластеры любой формы Плохо работает с разной плотностью
Устойчив к выбросам Не подходит для данных высокой размерности
Определяет шум

Сравнение методов

Метод Форма кластеров Нужно ли K Выбросы Масштабируемость
K-Means Сферические Да Нет Высокая
Hierarchical Любая Нет Нет Низкая
DBSCAN Любая Нет Да Средняя

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

Внешние метрики (если известны истинные метки)

  • Adjusted Rand Index (ARI)
  • Normalized Mutual Information (NMI)
  • Fowlkes-Mallows Index

Внутренние метрики (без истинных меток)

  • Silhouette Coefficient: от -1 до 1, чем больше, тем лучше
  • Calinski-Harabasz Index: отношение межкластерной дисперсии к внутрикластерной
  • Davies-Bouldin Index: чем меньше, тем лучше

Пример кода

from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN
from sklearn.metrics import silhouette_score, calinski_harabasz_score
import matplotlib.pyplot as plt
import scipy.cluster.hierarchy as sch

# K-Means
kmeans = KMeans(n_clusters=3, init='k-means++', random_state=42)
kmeans_labels = kmeans.fit_predict(X)
kmeans_centers = kmeans.cluster_centers_

# Оценка качества
sil_score = silhouette_score(X, kmeans_labels)
ch_score = calinski_harabasz_score(X, kmeans_labels)

# Выбор оптимального K (метод локтя)
inertias = []
for k in range(1, 11):
    km = KMeans(n_clusters=k, random_state=42)
    km.fit(X)
    inertias.append(km.inertia_)

plt.plot(range(1, 11), inertias, 'bo-')
plt.xlabel('Количество кластеров')
plt.ylabel('Inertia')
plt.title('Метод локтя')
plt.show()

# Иерархическая кластеризация
hc = AgglomerativeClustering(n_clusters=3, linkage='ward')
hc_labels = hc.fit_predict(X)

# Дендрограмма
dendrogram = sch.dendrogram(sch.linkage(X, method='ward'))
plt.title('Дендрограмма')
plt.xlabel('Образцы')
plt.ylabel('Расстояние')
plt.show()

# DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
dbscan_labels = dbscan.fit_predict(X)
# -1 обозначает выбросы

Практические советы

  1. Стандартизируйте данные перед кластеризацией
  2. Начните с K-Means как базового метода
  3. Используйте силуэтный коэффициент для выбора K
  4. DBSCAN хорош для данных с выбросами и сложной формой
  5. Визуализируйте результаты с помощью PCA или t-SNE
  6. Проверьте устойчивость кластеризации на подвыборках

Применение

  • Сегментация клиентов
  • Группировка документов
  • Обнаружение аномалий
  • Сжатие изображений
  • Биоинформатика

См. также