Понижение размерности. Кластеризация

В данной главе рассматриваются методы работы с данными, направленные на уменьшение количества признаков при сохранении структуры данных (понижение размерности), а также методы автоматического grouping объектов без учителя (кластеризация). Мы изучим метод главных компонент (PCA), t-SNE, алгоритмы k-средних, иерархическую кластеризацию и DBSCAN.

1. Понижение размерности

Основная идея

Главная задача понижения размерности — сохранить расстояния между точками при переходе к пространству меньшей размерности. Точки, которые были близкими (или далёкими) в пространстве высокой размерности, должны оставаться близкими (или далёкими) в пространстве меньшей размерности.

Метод главных компонент (PCA)

Простое отрезание оси пространства почти всегда не оптимально: в худшем случае проекция превратится в точку.

Основная концепция:

  1. Предполагается, что данные описываются неким эллипсом.
  2. Меняется базис пространства.
  3. Отрезается «новая ось» с минимальной дисперсией.
  4. Чтобы посчитать «потерянную информацию», делят дисперсию отрезанной оси на сумму дисперсий по всем осям.

Вычисления: Ковариация признаков вычисляется по формуле: $$cov(X_i, X_j) = M[(X_i - M[X_i])(X_j - M[X_j])] = M[X_i X_j] - M[X_i]M[X_j]$$

Выборку можно переместить так, чтобы математическое ожидание $M[X_i] = 0$. В матричном виде ковариация: $$cov(X) = X^T X$$

Свойства:

  • Ковариация симметрична.
  • Ковариация признака с самим собой равна его дисперсии.
  • Направление оси с максимальной дисперсией совпадает с направлением собственного вектора с максимальным собственным значением.
  • Собственное значение в этом случае равно дисперсии.

Ограничения PCA:

  • Необходимо стандартизировать выборку.
  • Не работает со сложными структурами, не похожими на эллипс.

t-SNE (t-Distributed Stochastic Neighbor Embedding)

Физический смысл:

  1. Данные из пространства размерности $N$ помещаются в пространство меньшей размерности $M$ (отображение).
  2. Объекты «прибиваются гвоздями» к своим местам.
  3. Объекты в пространстве $M$ соединяются пружинками. Сила пружины зависит от того, насколько расстояние в пространстве $M$ отличается от расстояния в пространстве $N$.
  4. Система «отпускается» (гвозди убираются).

Динамика:

  • Если точки в пространстве $M$ дальше, чем в пространстве $N$, то они притягиваются.
  • Если точки в пространстве $M$ ближе, чем в пространстве $N$, то они отталкиваются.

Математическое описание: Пусть $|x_i - x_j|$ — расстояние в исходном пространстве, $|y_i - y_j|$ — расстояние в пространстве отображения.

Условное сходство (Гауссово распределение): $$p_{j|i} = \frac{e^{-|x_i - x_j|^2 / 2\sigma_i^2}}{\sum_{k \neq i} e^{-|x_i - x_k|^2 / 2\sigma_i^2}}$$ где $\sigma_i^2$ — дисперсия распределения Гаусса вокруг точки $x_i$. Разные распределения берутся для точек в плотных и разреженных участках.

Симметричное сходство: $$p_{ji} = \frac{p_{j|i} + p_{i|j}}{2N}$$

В пространстве меньшей размерности используется не Гауссово, а распределение Стьюдента с одной степенью свободы (t-distribution): $$q_{ij} = \frac{t(|y_i - y_j|)}{\sum_{k \neq i} t(|y_i - y_k|)}, \text{ где } t(x) = \frac{1}{1 + x^2}$$

Оптимизация: Необходимо приблизить матрицу сходства отображения к матрице исходного пространства. Минимизируется расстояние Кульбака-Лейблера: $$KL(P||Q) = \sum_{i,j} p_{ij} \log \frac{p_{ij}}{q_{ij}} \to \min$$

Минимизация производится методом градиентного спуска. Градиент является совокупностью всех сил, действующих на объект: $$\frac{\partial KL(P||Q)}{\partial y_i} = 4 \sum_j (p_{ij} - q_{ij}) t(|x_i - x_j|) u_{ij}$$ где $u_{ij}$ — единичный вектор.

Почему t-distribution? При понижении размерности максимальные расстояния «меняются». Если использовать распределение Гаусса, то точки отображаются очень скученно (crowding problem).

Особенности t-SNE:

  • Работает со сложными структурами.
  • При появлении новых данных нет возможности просто спроецировать их. Нужно либо полностью переобучаться, либо использовать «хитрости» (например, k-nn).
  • Долго считать. Можно брать не все точки, а только ближайших соседей.
    • Если брать мало соседей, t-SNE больше учитывает локальные паттерны.
    • Если брать много соседей, t-SNE больше учитывает глобальные паттерны.

Autoencoders

...

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

k-средних (k-means)

Алгоритм заключается в следующем:

  1. Задать количество кластеров.
  2. Бросить случайным образом точки (центроиды) в пространстве.
  3. Для каждой точки посчитать, к какому центроиду она ближе.
  4. Передвинуть каждый центроид в «центры масс» подвыборки, принадлежащих этому центроиду.
  5. Повторять пункты 3-4 фиксированное число раз, или пока перемещение центроидов не будет достаточно маленьким (алгоритм сойдётся).

Особенности и ограничения:

  • Нужно задавать количество кластеров. Для подбора можно смотреть на сумму расстояний от точек до центров кластеров. Если сумма перестаёт резко падать, можно останавливаться.
  • Чувствителен к начальным случайным значениям.
  • Есть ограничения на форму кластеров.
  • Требует много вычислений.

Агломеративная (иерархическая) кластеризация

Алгоритм «снизу-вверх»:

  1. Сначала каждая точка — центр своего кластера.
  2. Считаем попарные расстояния между центрами кластеров.
  3. Склеиваем пару ближайших кластеров в новый кластер и пересчитываем его центр.
  4. Повторяем пункты 2-3, пока не склеим все в один кластер.

DBSCAN

Алгоритм, основанный на плотности:

  1. Берём случайную точку.
  2. Если у неё меньше $N$ соседей, то помечаем её как потенциальный выброс (noise point), и берём другую точку.
  3. Если соседей больше $N$:
    • Заводим новый кластер и помещаем точку (core point) в него.
    • Если сосед — потенциальный выброс или у него мало соседей, то это край кластера (border point). Заносим его в кластер и идём к другому соседу.
    • Если у соседа достаточно его собственных соседей, то добавляем его в кластер (core point), а его соседей заносим в очередь обхода.
  4. Повторяем пункты 1-3.
  5. Выбросы выделяем в отдельный кластер.

3. Заключение

В данной главе были рассмотрены ключевые методы уменьшения размерности данных и методы кластеризации без учителя.

В следующих лекциях планируется рассмотрение нейронных сетей.