Кластеризация на собеседовании Data Scientist

Зачем разбирать на собесе

Кластеризация — типичная задача segmentation, anomaly detection, exploratory analysis. На собесе DS обязательно: «как работает k-means», «зачем DBSCAN», «как выбрать K». Senior — нюансы инициализации, density-based vs centroid-based.

Главная боль без понимания — DS использует k-means на geo-данных, получает странные кластеры из-за разной плотности. С DBSCAN получилось бы лучше.

k-means: алгоритм и нюансы

Алгоритм Lloyd.

1. Случайно выбрать K центроидов.
2. Присвоить каждый объект ближайшему центроиду.
3. Пересчитать центроиды как среднее своего кластера.
4. Повторять, пока не сойдётся (центроиды не меняются).

Целевая функция (within-cluster sum of squares, inertia):

WCSS = Σₖ Σᵢ∈Cₖ ||xᵢ - μₖ||²

Минимизируется итеративно. Не глобальный оптимум — зависит от инициализации.

k-means++. Умная инициализация — выбирает центроиды далеко друг от друга. Снижает риск плохого локального минимума. Default в sklearn.

Свойства:

• Сложность O(N·K·d·iters). На больших — Mini-Batch k-means.
• Кластеры — выпуклые (Voronoi-разбиение).
• Плохо работает на не-сферических кластерах, разных плотностях, разных размерах.
• Чувствителен к scale — нормализовать фичи!
• Чувствителен к outliers (среднее их учитывает).

from sklearn.cluster import KMeans
km = KMeans(n_clusters=5, init='k-means++', n_init=10, random_state=42)
labels = km.fit_predict(X)

Выбор K: elbow, silhouette

Elbow method. Строим WCSS vs K. Ищем «локоть» — точку, после которой улучшение слабое.

wcss = []
for k in range(1, 15):
    km = KMeans(n_clusters=k).fit(X)
    wcss.append(km.inertia_)

Субъективно: «локоть» не всегда чёткий.

Silhouette score. Для каждого объекта:

s(i) = (b(i) - a(i)) / max(a(i), b(i))

a — среднее расстояние до своих, b — до ближайшего чужого кластера. s ∈ [-1, 1]. Усредняем.

from sklearn.metrics import silhouette_score
score = silhouette_score(X, labels)

Высокое значение = объекты ближе к своим, чем к чужим. Хорошая метрика.

Davies-Bouldin index. Lower = better. Учитывает разброс внутри кластера vs расстояния между.

Бизнес-логика. Иногда K фиксирован продуктом («3 сегмента: эконом, стандарт, премиум»). Метрики только подтверждают разумность.

DBSCAN: density-based

Идея. Кластер = плотная область. Точки делятся на core, border, noise.

Параметры:

• eps — радиус окрестности.
• min_samples — минимум точек в окрестности, чтобы точка считалась core.

Алгоритм:

1. Для каждой точки посчитать число соседей в радиусе eps.
2. Если >= min_samples → core. Если меньше, но есть core-сосед → border. Иначе noise.
3. Connected components from core points → кластеры.

Свойства:

• Не требует K.
• Произвольная форма кластеров (не только сфера).
• Выявляет шум (anomaly detection).
• Чувствителен к eps и min_samples.
• Плохо работает с разной плотностью кластеров.
• O(N²) наивно, O(N·log N) через индекс (KD-tree).

from sklearn.cluster import DBSCAN
db = DBSCAN(eps=0.5, min_samples=5).fit(X)
labels = db.labels_  # -1 = noise

HDBSCAN — иерархический DBSCAN, адаптируется к разной плотности. Часто лучше базового.

Hierarchical clustering

Agglomerative (bottom-up):

1. Каждый объект — свой кластер.
2. На каждом шаге объединить два ближайших кластера.
3. Повторять до одного кластера.

Linkage — как считать расстояние между кластерами:

• single — мин. расстояние между точками. Создаёт «цепочки».
• complete — макс. расстояние. Компактные кластеры.
• average — среднее.
• ward — минимизирует увеличение WCSS. Дефолт, обычно лучший.

Дендрограмма — визуализация иерархии. Срез по высоте даёт K кластеров.

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
Z = linkage(X, method='ward')
labels = fcluster(Z, t=5, criterion='maxclust')  # 5 кластеров

Свойства:

• Не требует K заранее (выбирается на дендрограмме).
• Интерпретируемо.
• O(N²) или O(N²·log N) — медленно на N > 10k.
• Чувствителен к шуму и outliers (зависит от linkage).

Divisive (top-down) — обратный подход, реже используется.

Gaussian Mixture Models

Идея. Данные — смесь K гауссиан с разными μ, Σ, π. EM-алгоритм находит параметры.

E-step: оценить P(zᵢ = k | xᵢ) для каждого объекта (soft assignment).

M-step: обновить параметры компонент по weighted statistics.

Свойства:

• Soft clustering — каждый объект имеет вероятности принадлежности.
• Может моделировать elliptical кластеры (через Σ).
• BIC / AIC помогают выбрать K.
• Может уйти в singularity (одна гауссиана сжимается до точки).

from sklearn.mixture import GaussianMixture
gmm = GaussianMixture(n_components=5, covariance_type='full', random_state=42)
labels = gmm.fit_predict(X)

covariance_type:

• full — полная Σ для каждого компонента (гибко, много параметров).
• tied — одна Σ для всех (как k-means по сути).
• diag — диагональная (быстрее, проще).
• spherical — изотропная (≈ k-means).

Когда что выбирать

k-means:

• Большие данные.
• Кластеры примерно сферические и одного размера.
• Знаешь K заранее.
• Нужна скорость.

DBSCAN:

• Произвольная форма кластеров.
• Хочешь найти шум / аномалии.
• Не знаешь K.
• Плотности кластеров примерно одинаковые.

HDBSCAN:

• DBSCAN, но плотности разные.
• Часто лучший дефолт для exploratory.

Hierarchical:

• Маленькие данные (< 10k).
• Нужна дендрограмма / иерархия.
• Биология, документы, маркетинговая сегментация.

GMM:

• Эллиптические кластеры.
• Soft assignment важен.
• Statistical model полезен.

Частые ошибки

Не нормализовать. Колонка с большим scale доминирует distance metric. Всегда StandardScaler перед k-means / hierarchical.

Использовать k-means на категориальных. Среднее категории не определено. Используй k-modes (категории) или k-prototypes (mixed).

Один запуск k-means. Зависит от random init. n_init=10 (sklearn) или больше — даёт стабильный результат.

Считать silhouette на huge data. O(N²) — для миллионов объектов невозможно. Семпл или другие метрики.

DBSCAN с дефолтом eps=0.5. Это магическое число. Использовать k-distance plot для выбора.

Игнорировать noise в DBSCAN. -1 — это не «нулевой кластер», это «шум». Может быть полезно само по себе (anomaly).

Hierarchical на 100k объектов. Память и время убивают. Семплируй или используй BIRCH / mini-batch методы.

Сравнивать кластеры разных алгоритмов по labels. Метки — произвольны. Сравнивай через ARI (Adjusted Rand Index) или NMI.

Связанные темы

• PCA — снижение размерности для DS
• Class imbalance на собесе DS
• Hyperparameter tuning на собесе DS
• Bias-variance trade-off на собесе DS
• Подготовка к собесу Data Scientist

FAQ

k-means для категорий?

Не работает (среднее категории не определено). Использовать k-modes или one-hot + k-means (с осторожностью).

Можно ли validate clustering без labels?

Да, через intrinsic metrics: silhouette, Davies-Bouldin, Calinski-Harabasz. Если labels есть — extrinsic: ARI, NMI, V-measure.

Как ускорить k-means на 10М объектов?

Mini-Batch k-means из sklearn — обрабатывает мини-батчи. Faiss-clustering — суперскорость на GPU. Spark MLlib — distributed k-means.

Что такое cluster stability?

Свойство — насколько кластеризация устойчива к bootstrap-выборкам. Запускаешь алгоритм на N подвыборках, смотришь, как часто пары объектов попадают в один кластер.

Hierarchical clustering работает на не-Euclidean метриках?

Да. Linkage methods умеют любую метрику (Manhattan, cosine), Ward требует Euclidean.

Это официальная информация?

Нет. Статья основана на классических работах (Lloyd 1982, Ester 1996 «DBSCAN», Murtagh 2011 «Hierarchical clustering»), документации scikit-learn.

Тренируйте Data Science — откройте тренажёр с 1500+ вопросами для собесов.