Краткий сравнительный анализ — описание, когда предпочтителен, недостатки, подбор метрик и методы выбора параметров.
k‑means
- Суть: минимизация внутрикластерной суммы квадратов: ${\min }_{C_1,\dots ,C_k}{\sum }_{i=1}^k{\sum }_{x\in C_i}\Vert x-{\mu }_i{\Vert }^2$.
- Предположения: кластеры примерно сферические, одинакового масштаба, Евклидово пространство.
- Когда предпочтителен: большие наборы данных, когда ожидается $k$ и кластеры шарообразны; быстрый baseline.
- Параметры/чувствительность: требует заданного $k$; чувствителен к масштабированию признаков (нужна стандартизация) и инициализации (использовать k‑means++).
- Сложность: приблизительно $\mathcal{O}(nktd)$ (n — число точек, t — число итераций, d — размерность).
- Минусы: плохо работает при несимметричных, вытянутых или разной плотности кластерах; восприимчив к выбросам.
DBSCAN
- Суть: плотностной алгоритм, кластеры — связные области с плотностью >= порог; параметры: $\epsilon$ (eps) и minPts.
- Когда предпочтителен: данные с кластерами произвольной формы и шумом/выбросами; пространственные/геометрические данные.
- Параметры/чувствительность: подбор $\epsilon$ и minPts критичен (k‑distance plot). Работает с любыми метриками расстояния.
- Сложность: в общем случае $\mathcal{O}(n^2)$, с индексами близости (k‑d tree, R‑tree) часто $\mathcal{O}(n\log n)$.
- Минусы: плохо при кластерах разной плотности (одни параметры не подходят); чувствителен к выбору eps; может пометить много шума.
Иерархическая кластеризация (agglomerative/divisive)
- Суть: строится дендрограмма — последовательное объединение/разбиение; связывания: single, complete, average, Ward и др. (Ward минимизирует внутрикл. дисперсию и требует Евклида).
- Когда предпочтителен: исследовательский анализ, необходимо иерархическое представление, малые/средние выборки, когда неизвестно число кластеров.
- Параметры/чувствительность: выбор метода linkage сильно влияет на результат; можно выбирать порог разреза дендрограммы.
- Сложность: типично $\mathcal{O}(n^2)$ по памяти и времени (в зависимости от реализации).
- Минусы: плохо масштабируется на большие $n$; чувствительна к шуму и выбросам (особенно single linkage — эффект «цепочки»).
Метрики качества кластеризации
- Внешние (требуют эталонных меток):
- Adjusted Rand Index (ARI): диапазон примерно $[-1,1]$, скорректирован на случайное совпадение. Чем ближе к 1 — лучше.
- Normalized Mutual Information (NMI): диапазон $[0,1]$, оценивает взаимную информацию.
- Fowlkes–Mallows, Purity — вспомогательные.
- Внутренние (не требуют меток):
- Silhouette score: $\in [-1,1]$, лучше ближе к 1; учитывает плотность и разделимость.
- Davies–Bouldin index: лучше — меньше.
- Calinski–Harabasz index: лучше — больше.
- Cophenetic correlation coefficient (для иерархической) — мера согласованности дендрограммы с расстояниями.
- Для плотностных алгоритмов:
- Модифицированный Silhouette (игнорируя выбросы) или оценка доли помеченных как шум точек.
- Оценка стабильности кластеров при варьировании $\epsilon$/minPts (robustness).
- Практика: при наличии истиновых меток использовать ARI/NMI; без меток — смотреть несколько внутренних индексов одновременно (Silhouette + CH/Davies‑Bouldin) и визуализацию.
Как выбирать метод по задаче (коротко)
- Большие данные, ожидаемые шарообразные кластеры, известно $k$ → k‑means (k‑means++ + стандартизация).
- Кластеры произвольной формы, шум, пространственные данные → DBSCAN (подбирать eps через k‑distance plot).
- Нужна иерархия, исследование структуры, небольшие/средние выборки, неизвестно $k$ → иерархическая кластеризация (анализ дендрограммы, выбор linkage).
- Смесь требований: для неевклидовых расстояний или произвольных метрик использовать k‑medoids (PAM) вместо k‑means; для разных плотностей — HDBSCAN (расширение DBSCAN).
Короткие рекомендации по подбору числа кластеров/параметров
- k‑means: elbow method (внутрикластерная сумма квадратов), Silhouette, Gap statistic; инициализация k‑means++.
- DBSCAN: k‑distance plot (minPts ≈ dimensionality+1 или 4), проверка чувствительности.
- Иерархическая: смотреть дендрограмму и Cophenetic correlation; выбирать разрез по стабильности/сильным скачкам расстояния.
Это сжатый набор критериев и практических указаний для выбора метода и метрик.