Кластеризация

Постановка задачи

Дана выборка \(\mathbb{X} = (x_i)_{i=1}^\ell\) без меток. Хотим построить модель \(a: \mathbb{X} \to \{1, \dots, K\}\) такую, что похожие объекты попадают в один кластер: \(x_i \sim x_j \implies a(x_i) = a(x_j)\).

Типы кластеризации:

  • Hard clustering — каждый объект принадлежит ровно одному кластеру.
  • Soft clustering — каждому объекту присваивается вероятность принадлежности к каждому кластеру.

Зачем нужна кластеризация:

  • Разведочный анализ данных.
  • Генерация признаков.
  • Квантизация — уменьшение размера пространства признака.
  • Продуктовые задачи (кластеризация новостей, сегментация пользователей).

Метрики качества кластеризации

Лучший способ оценить кластеризацию — посмотреть глазами. Формальные метрики дополняют, но не заменяют визуальный анализ.

Внутрикластерное расстояние

\[\sum_{k=1}^K \sum_{i=1}^\ell [a(x_i) = k]\, \rho(x_i, c_k) \to \min\]

где \(c_k\) — центр \(k\)-го кластера. Чем меньше — тем компактнее кластеры.

Межкластерное расстояние

\[\sum_{i \neq j} [a(x_i) \neq a(x_j)]\, \rho(x_i, x_j) \to \max\]

Чем больше — тем лучше кластеры разделены.

Индекс Данна

Объединяет обе метрики:

\[\frac{\min_{1 \leq k < k' \leq K} \alpha(k, k')}{\max_{1 \leq k \leq K} \alpha(k)} \to \max\]

где \(\alpha(k, k')\) — расстояние между кластерами, \(\alpha(k)\) — внутрикластерное расстояние.

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

Метод локтя (Elbow Method)

Строим график внутрикластерного расстояния от числа кластеров \(K\). Оптимальное \(K\) — в точке «локтя», где прирост качества резко замедляется.

K-Means

\(K\) — гиперпараметр. Минимизируем:

\[\sum_{k=1}^K \sum_{i=1}^\ell [a(x_i) = k]\, \rho(x_i, c_k) \to \min\]

Мы не знаем ни центры, ни предсказания — поэтому оптимизируем поочерёдно:

  • Шаг 0: инициализируем центры (например, K-Means++).
  • Шаг а: фиксируем \(c_k\), назначаем объекты: \(a(x_i) = \mathop{\text{argmin}}_{k} \rho(x_i, c_k)\).
  • Шаг б: фиксируем \(a(x_i)\), пересчитываем центры: при евклидовом расстоянии \(c_k = \frac{1}{\sum [a(x_i)=k]} \sum [a(x_i)=k]\, x_i\).
  • Повторяем до сходимости (сходимость гарантируется).
Плюсы Минусы
Быстрый Зависит от инициализации
Легко параллелится Признаки разного масштаба могут всё сломать
Кластеры только эллиптической формы

Иерархический подход

Шаг 1: каждый объект — отдельный кластер: \(C_{(1)} = \{\{x_1\}, \dots, \{x_\ell\}\}\).

Шаг j: склеиваем два ближайших кластера:

\[(m, n) = \mathop{\text{argmin}}_{1 \leq m < n \leq \ell - j + 1} d(X_m, X_n)\]

Метрику \(d\) между кластерами выбираем сами (single linkage, complete linkage, average linkage и др.). Результат — дендрограмма, из которой можно получить разбиение на любое число кластеров.

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

DBSCAN

Алгоритм, основанный на плотности. Плотность точки \(x\) — число точек в её \(\varepsilon\)-окрестности.

Типы точек:

  • Внутренние (Core points) — в окрестности \(\varepsilon\) не менее \(\text{minPts}\) точек.
  • Граничные (Border points) — в окрестности меньше \(\text{minPts}\), но достижимы из внутренней точки.
  • Шумовые (Noise points) — не достижимы ни из одной внутренней точки.
DBSCAN не требует задавать число кластеров заранее и находит кластеры произвольной формы. Шумовые точки автоматически отфильтровываются.

EM-кластеризация

Мягкая кластеризация на основе смеси распределений:

\[p(x) = \sum_{k=1}^n p_k(x)\, \pi_k\]

где \(p_k(x)\) — функция распределения \(k\)-й компоненты, \(\pi_k\) — вес компоненты.

Алгоритм чередует два шага:

  • E-шаг: вычисляем вероятности принадлежности каждого объекта к каждому кластеру.
  • M-шаг: пересчитываем параметры распределений (среднее, дисперсию) и веса компонент.

В отличие от K-Means, EM выдаёт вероятности принадлежности, а не жёсткие метки.

← Назад к списку тем