Тема 6. Обучение без учителя

В предыдущих темах мы строили модели, для которых обучающая выборка приходила «с ответом»: классификатор знал метку каждого объекта, регрессор — числовое значение целевой переменной. На этом фундаменте удобно изучать методологию — функцию потерь, разделение данных, метрики, — но реальная практика чаще выглядит иначе. У аналитика на руках оказывается таблица, в которой целевой столбец отсутствует: журналы датчиков с производственной линии, логи поведения пользователей, фотографии без подписей, тексты обращений в техподдержку без рубрикатора. Размечать всё это вручную дорого, иногда невозможно, а действовать как-то надо.

Обучение без учителя — это семейство методов, которые ищут в данных структуру без подсказок извне. Модели не получают «правильного ответа» и оптимизируют не точность предсказаний, а внутренние свойства решения: компактность кластеров, долю сохранённой дисперсии, согласованность локальных соседств. В этой теме мы рассмотрим две большие линии: кластеризацию и снижение размерности. К концу темы у нас будет инструментарий для того, чтобы по неразмеченной таблице ответить на два вопроса: «есть ли в данных естественные группы?» и «можно ли сжать пространство признаков, не теряя сути?».

Задачи обучения без учителя

Постановка проблемы

Формально задача обучения без учителя выглядит проще, чем обучение с учителем: задано множество объектов $\{x_i\}_{i=1}^{n} \subset \mathcal{X}$, и требуется построить модель, описывающую структуру этого множества. Целевой переменной нет — нет ни функции $y = f(x)$, ни обучающей пары «вход — ответ», к которой можно подгонять параметры. Простота постановки обманчива: именно из-за отсутствия эталона у задачи нет однозначного критерия успеха. Кластер из двадцати клиентов можно одновременно интерпретировать как «активные пользователи мобильного приложения» и как «студенты технического вуза», и оба варианта будут согласованы с одними и теми же данными.

У задачи обучения без учителя есть два магистральных направления. Кластеризация (англ. clustering) разбивает объекты на группы так, чтобы внутри группы объекты были похожи, а между группами — различны. Снижение размерности (англ. dimensionality reduction) ищет компактное представление выборки: $x \in \mathbb{R}^d \mapsto z \in \mathbb{R}^{d'}$ при $d' \ll d$, сохраняющее ключевые свойства данных. Эти две задачи часто решают совместно: понижение размерности готовит данные к кластеризации (избавляя её от проклятия размерности) или, наоборот, кластеризация даёт оси, по которым потом строится визуализация.

Прикладных сюжетов, в которых работает этот аппарат, много. Маркетинговая сегментация ищет однородные группы клиентов, чтобы построить для них целевые предложения; биоинформатика группирует образцы по экспрессии генов; служба безопасности банка использует обнаружение аномалий, чтобы выделять подозрительные транзакции — точки, не вписывающиеся ни в один из обнаруженных кластеров. Визуализация многомерных данных в двумерной плоскости — отдельный жанр: исследователь хочет «увидеть» структуру датасета, прежде чем выбрать модель.

Особое слово об оценке. В обучении с учителем мы оцениваем модель тестовой ошибкой; в обучении без учителя тестовой ошибки в строгом смысле нет — нет «правильного» разбиения. На практике используют внутренние метрики (англ. internal metrics), такие как силуэтный коэффициент или индекс Калинского — Харабаса, опирающиеся на расстояния между объектами без обращения к меткам, и внешние метрики (англ. external metrics), требующие пусть и небольшой эталонной разметки — индекс Ранда, нормализованная взаимная информация. Подробнее о метриках мы поговорим в теме 7; здесь достаточно понимать, что результат кластеризации почти всегда оценивается косвенно и допускает несколько правомерных интерпретаций.

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

K-Means

Алгоритм $k$-средних — самый известный метод кластеризации, и причины его популярности прозаичны: он простой, быстрый и в большинстве учебников приводится как первый пример. Идея сформулирована ещё в работе ¹: задано число кластеров $k$, и требуется разбить выборку на $k$ непересекающихся групп $C_1, \ldots, C_k$ так, чтобы минимизировать сумму квадратов расстояний от каждого объекта до центра его кластера: $J(C, \mu) = \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2,$ где $\mu_j$ — центроид (англ. centroid) кластера $C_j$, среднее всех его точек. Минимизация $J$ — задача NP-трудная, но у неё есть простая эвристика, известная как алгоритм Ллойда: выбрать начальные центроиды случайно, потом итеративно повторять два шага. На шаге назначения каждый объект приписывается ближайшему центроиду; на шаге пересчёта каждый центроид заменяется средним точек своего кластера. Итерации продолжаются, пока назначения не перестанут меняться (или меняться меньше заданного порога). Сходимость к локальному минимуму гарантирована, причём обычно за десятки итераций.

Главный практический вопрос — выбор числа кластеров $k$. У задачи нет «правильного» ответа: можно разбить выборку на 2 группы, на 5, на 50. Помогают полуэмпирические индикаторы. Метод локтя (англ. elbow method) строит зависимость $J(k)$ от $k$ и ищет на ней излом: при увеличении $k$ внутрикластерная сумма квадратов монотонно падает, но в какой-то момент скорость падения резко уменьшается. Точка излома — кандидат на оптимальное число кластеров. Силуэтный коэффициент (англ. silhouette score) для каждого объекта $x_i$ сравнивает среднее расстояние до точек своего кластера $a(i)$ со средним расстоянием до точек ближайшего чужого кластера $b(i)$:

$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \in [-1, 1].$

Среднее $s(i)$ по выборке даёт интегральный показатель: значения, близкие к 1, говорят о хорошо разделённых кластерах, значения, близкие к нулю — о размытых границах. На практике обе методики дают подсказку, а не приговор: финальное число кластеров обычно фиксируется с учётом содержательных соображений — например, бюджета на персонализацию или числа сегментов, которые продукт-менеджер готов поддерживать.

У $k$-средних есть три принципиальных ограничения. Первое — чувствительность к инициализации: разные начальные центроиды приводят к разным локальным минимумам $J$, и плохая инициализация может «зажать» один кластер в углу выборки, оставив остальные плохо разделёнными. Второе — сферическая форма кластеров: метод неявно предполагает, что точки кластера расположены симметрично вокруг своего центра, и плохо работает на вытянутых или вложенных структурах. Третье — необходимость задавать $k$ заранее, что мы только что обсудили.

С инициализацией борются эвристикой k-means++ ²: первый центроид выбирается случайно, каждый следующий — с вероятностью, пропорциональной квадрату расстояния до ближайшего уже выбранного центроида. Идея в том, чтобы стартовые центроиды были «разнесены» по выборке. Авторы показали, что такая инициализация в среднем даёт решение, отличающееся от глобального оптимума не более чем в $O(\log k)$ раз — слабее, чем хотелось бы в теории, но на порядок надёжнее случайного старта на практике. По умолчанию в scikit-learn используется именно k-means++; «чистого» случайного запуска без особых причин стоит избегать.

DBSCAN

Когда кластеры имеют сложную форму — вытянутые, изогнутые, концентрические — $k$-средние работают плохо: они разрезают такие структуры по прямой. Алгоритм DBSCAN (англ. Density-Based Spatial Clustering of Applications with Noise) подходит к задаче с другой стороны ³: кластер — это плотная область пространства, отделённая от других плотных областей разреженной зоной. Никакой сферичности не предполагается, число кластеров не задаётся — оно определяется самой структурой данных.

Алгоритм опирается на два параметра. Радиус $\varepsilon$ задаёт окрестность точки; число $\text{minPts}$ — минимальное число соседей, при котором точка считается «плотной». На основе этих параметров вводятся три типа точек. Ядровая точка (англ. core point) — точка, в $\varepsilon$-окрестности которой не менее $\text{minPts}$ объектов выборки, включая саму точку. Граничная точка (англ. border point) — точка, попадающая в окрестность какой-то ядровой, но сама ядровой не являющаяся. Остальные точки — шум (англ. noise) — не принадлежат ни одному кластеру.

Кластер строится как максимальный связный по плотности набор точек: две ядровые точки попадают в один кластер, если до одной можно добраться от другой цепочкой $\varepsilon$-шагов через ядровые точки; граничные точки присоединяются к ближайшему кластеру. Алгоритм линеен по числу объектов при использовании пространственного индекса (например, KD-дерева) для поиска соседей.

Преимущества DBSCAN перед $k$-средними хорошо видны на синтетических примерах. На двух концентрических кольцах $k$-средние с $k = 2$ разрежут плоскость пополам; DBSCAN правильно отделит внешнее кольцо от внутреннего. Шум — точки, далёкие от любого кластера, — алгоритм явно помечает как $\text{noise}$, что напрямую полезно для обнаружения аномалий: подозрительные транзакции, выбросы в сенсорных данных, опечатки в адресной базе оказываются именно в этой категории. Число кластеров определяется автоматически и может равняться нулю, если данные слишком разрежены.

Слабые места тоже есть. Главное — чувствительность к выбору $\varepsilon$ и $\text{minPts}$: слишком маленький $\varepsilon$ оставит всё в шуме, слишком большой склеит кластеры в один. Стандартная эвристика — построить $k$-distance plot: упорядочить все точки выборки по расстоянию до своего $k$-го ближайшего соседа (где $k = \text{minPts}$) и взять $\varepsilon$ в точке излома кривой. Второе ограничение принципиальнее: DBSCAN исходит из единой плотности всех кластеров, а если в выборке плотные и разреженные группы соседствуют, общий $\varepsilon$ либо «съест» разреженные, либо склеит плотные. Эту проблему адресуют расширения вроде OPTICS ⁴, строящие иерархическую плотностную структуру вместо одного разбиения.

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

Третий подход — иерархический — даёт не одно разбиение, а целое семейство, упорядоченное по числу кластеров: от каждого объекта в своём кластере до всех объектов в одном. Различают агломеративную (англ. agglomerative) кластеризацию, идущую снизу вверх (объекты последовательно сливаются в группы), и дивизивную (англ. divisive) — сверху вниз, рекурсивно разбивающую один общий кластер. На практике агломеративная встречается чаще — у неё проще реализация и понятнее интерпретация.

Алгоритм агломеративной кластеризации лаконичен. На старте каждая точка — отдельный кластер. На каждом шаге сливаются два ближайших кластера, после чего расстояния пересчитываются. Процесс продолжается, пока не останется один кластер. Главный выбор — как именно определять расстояние между двумя кластерами $A$ и $B$, состоящими более чем из одной точки. Стандартных метрик четыре. Single linkage берёт минимум попарных расстояний: $d(A, B) = \min_{a \in A, b \in B} \|a - b\|$ — даёт длинные «цепочки», склонные к эффекту хвоста. Complete linkage — максимум: даёт компактные шарообразные кластеры, плохо адаптируется к вытянутым формам. Average linkage — среднее: компромисс между крайностями. Ward минимизирует прирост внутрикластерной суммы квадратов при слиянии — даёт сбалансированные кластеры одинакового размера, по духу близок к $k$-средним.

Иерархия слияний представляется в виде дендрограммы (англ. dendrogram) — древовидной диаграммы, в которой по горизонтальной оси расположены объекты, а вертикальная ось показывает расстояние, на котором происходило слияние. Высокие «развилки» соответствуют слияниям между сильно различающимися группами; горизонтальный срез дендрограммы на заданной высоте даёт конкретное разбиение. Дендрограмма — удобный диагностический инструмент: глядя на неё, аналитик видит, в каком диапазоне число кластеров устойчиво (большой вертикальный «зазор» между слияниями), а где разбиение случайно (несколько слияний подряд на одной высоте).

В отличие от $k$-средних, иерархическая кластеризация не требует фиксировать число кластеров заранее; в отличие от DBSCAN, она не требует выбора плотностных параметров. Расплата — вычислительная сложность $O(n^2 \log n)$ в обычной реализации и $O(n^2)$ по памяти на матрицу расстояний, что ограничивает применение десятками тысяч объектов. Для больших датасетов используют разреженные приближения или предварительную кластеризацию $k$-средними с последующей агломерацией центроидов.

Снижение размерности

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

Кластеризация искала структуру в виде «групп объектов»; метод главных компонент (англ. Principal Component Analysis, PCA) ищет структуру в виде «направлений вариации». Идея сформулирована Пирсоном ещё в 1901 году ⁵: найти такое подпространство меньшей размерности, проекция на которое сохраняет максимально возможную долю дисперсии исходных данных. Геометрически это означает поворот системы координат: новые оси (главные компоненты) выбираются так, чтобы первая ось «смотрела» в направлении наибольшего разброса точек, вторая — в направление наибольшего разброса среди ортогональных первой, и так далее.

Положим, что данные центрированы — из каждого признака вычтено его среднее. Тогда матрица ковариаций $\Sigma = \frac{1}{n} X^\top X$ симметрична и положительно полуопределена, и её можно разложить по собственным векторам: $\Sigma = U \Lambda U^\top$, где $\Lambda$ — диагональная матрица собственных значений $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_d \geq 0$, а столбцы $U$ — соответствующие собственные векторы $u_1, \ldots, u_d$. Эти векторы и есть главные компоненты, упорядоченные по убыванию объяснённой дисперсии: $\lambda_i$ — дисперсия данных вдоль направления $u_i$. Проекция объекта на первые $k$ компонент даёт сжатое представление $z_i = U_k^\top x_i \in \mathbb{R}^k$. Изложение с алгебраическими деталями есть в монографии ⁶; теоретический фундамент собран в ⁷.

Главный вопрос применения PCA — сколько компонент оставить. Доля объяснённой дисперсии (англ. explained variance ratio) первых $k$ компонент равна $\sum_{i=1}^{k} \lambda_i / \sum_{i=1}^{d} \lambda_i$. На практике выбирают $k$ так, чтобы покрыть 90–95% общей дисперсии — этот критерий гибче, чем абсолютная отсечка по $\lambda_i$, и не зависит от шкалы признаков. Альтернатива — график «осыпи» (англ. scree plot): отсортированные $\lambda_i$ откладываются по оси ординат, и берётся точка перегиба, как в методе локтя у кластеризации.

Применений у PCA три основных. Первое — визуализация: проекция многомерной выборки на первые две-три компоненты даёт картину, на которой глаз ловит структуру быстрее, чем формальные метрики. Второе — борьба с проклятием размерности: модели на 200 признаках часто работают хуже моделей на 20 главных компонентах, потому что в большом пространстве расстояния теряют смысл, а число параметров растёт. Третье — предобработка: PCA устраняет мультиколлинеарность и шум, что особенно полезно перед линейными моделями.

Ограничения PCA вытекают из его линейности. Если структура данных нелинейна — скажем, точки лежат на свёрнутой двумерной поверхности в трёхмерном пространстве, — никакая проекция на прямые оси не «развернёт» её обратно. Кроме того, направления максимальной дисперсии не обязаны совпадать с «полезными» для дальнейшей задачи: если классы различаются по слабому, но содержательному признаку, его дисперсия может оказаться меньше, чем у шумного, и PCA его отбросит. Для подобных случаев существуют нелинейные обобщения (kernel PCA, автоэнкодеры) и методы, заточенные под визуализацию, к одному из которых мы перейдём.

t-SNE

Если PCA — линейный метод глобальной структуры, то t-SNE (англ. t-distributed Stochastic Neighbor Embedding) — нелинейный метод локальной структуры ⁸. Алгоритм был предложен ван дер Маатеном и Хинтоном специально для двумерной визуализации многомерных датасетов и быстро стал стандартом в задачах исследовательского анализа: scatter-плот, полученный с помощью t-SNE на 50 000 рукописных цифр MNIST, отчётливо показывает десять кластеров, в то время как PCA на тех же данных даёт перекрывающиеся облака.

Принцип t-SNE — сохранять локальные соседства. Для каждой пары объектов $(x_i, x_j)$ в исходном пространстве вычисляется условная вероятность $p_{j|i}$ того, что $x_j$ — сосед $x_i$, по гауссовскому ядру с шириной, индивидуально подобранной для каждого $i$. В целевом низкоразмерном пространстве для пары $(z_i, z_j)$ вводится аналогичная вероятность $q_{ij}$, но уже по распределению Стьюдента с одним степенью свободы — «толстохвостому», чтобы дальние пары не слишком «прижимались» друг к другу. Положения $z_i$ подбираются градиентным спуском по дивергенции Кульбака — Лейблера между распределениями $p$ и $q$.

Главный гиперпараметр t-SNE — perplexity (англ. perplexity) — управляет шириной гауссовых ядер и интерпретируется как «эффективное число соседей», учитываемых при оценке локальной плотности. Типичные значения — от 5 до 50; на маленьких датасетах лучше работают значения поменьше, на больших — побольше. Чувствительность результата к perplexity иногда неожиданно высока: разные значения могут дать визуально разные «облака», и важно проверять устойчивость, прогоняя алгоритм с несколькими значениями параметра.

У t-SNE два принципиальных ограничения, о которых надо знать с самого начала. Первое — невоспроизводимость: алгоритм стохастический, разные запуски с разной инициализацией дают разные карты. Это значит, что t-SNE — инструмент визуализации, а не координатной системы: на нём нельзя строить классификатор, ожидая что обученная модель применима к новым данным. Второе — непригодность для новых объектов: t-SNE не строит функцию $\phi: \mathcal{X} \to \mathbb{R}^2$, которую можно было бы применить к точке вне обучающей выборки; алгоритм минимизирует расстановку конкретных точек, и для новой точки придётся пересчитывать всё с нуля. Если нужна именно «карта» с возможностью добавления данных, используют UMAP ⁹ — родственный по идее метод, который явно строит обобщающее отображение.

Ещё одна особенность, регулярно сбивающая интерпретацию: глобальные расстояния на t-SNE-карте не сохраняются. Если два кластера на картинке кажутся далёкими — это не значит, что в исходном пространстве они тоже далеки; алгоритм оптимизирует только локальные структуры. По этой же причине плотность точек в кластере на t-SNE-карте не отражает плотности в исходных данных. Карту следует читать как «есть ли локальные группы и какие точки в них объединены», а не как «насколько одни группы похожи на другие».

Литература

1. MacQueen J. Some Methods for Classification and Analysis of Multivariate Observations. — Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1967, С. 281–297.
2. Arthur D., Vassilvitskii S. k-means++: The Advantages of Careful Seeding. — Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, С. 1027–1035, DOI: 10.5555/1283383.1283494.
3. Ester M., Kriegel H., Sander J., Xu X. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. — Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD), 1996, С. 226–231.
4. Ankerst M., Breunig M. M., Kriegel H., Sander J. OPTICS: Ordering Points to Identify the Clustering Structure. — Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, 1999, С. 49–60, DOI: 10.1145/304182.304187.
5. Pearson K. On Lines and Planes of Closest Fit to Systems of Points in Space. — Philosophical Magazine, 1901, С. 559–572, DOI: 10.1080/14786440109462720.
6. Jolliffe I. T. Principal Component Analysis. — Springer, 2002, DOI: 10.1007/b98835.
7. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — Springer, 2009, DOI: 10.1007/978-0-387-84858-7.
8. van der Maaten L., Hinton G. Visualizing Data using t-SNE. — Journal of Machine Learning Research, 2008, С. 2579–2605.
9. McInnes L., Healy J., Melville J. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. — arXiv preprint arXiv:1802.03426, 2018, https://arxiv.org/abs/1802.03426.