Спектральная кластеризация

Спектральная кластеризация — это семейство методов машинного обучения и анализа данных, предназначенных для разделения множества объектов на группы (кластеры) на основе связности графа, построенного по этим объектам. В отличие от классических методов, таких как k-средних, которые работают непосредственно с признаками объектов в исходном пространстве, спектральная кластеризация использует спектр (собственные значения и собственные векторы) матрицы, представляющей граф. Это позволяет выявлять кластеры произвольной формы, включая вложенные, вытянутые и непересекающиеся структуры, которые нелинейно разделимы в исходном пространстве признаков.

История

Методы, лежащие в основе спектральной кластеризации, имеют корни в теории графов и спектральном анализе. В 1973 году Мирослав Фидлер (Miroslav Fiedler) ввёл понятие алгебраической связности графа и показал, что второй наименьший собственный вектор матрицы Лапласа (вектор Фидлера) может использоваться для разбиения графа на две части. В 1990-х годах работы Джеймса Ши (Jianbo Shi) и Джитендры Малика (Jitendra Malik) по сегментации изображений (нормализованные разрезы, Normalized Cuts) популяризировали применение спектральных методов в компьютерном зрении. В 2000-х годах Ульрике фон Люксбург (Ulrike von Luxburg) и другие исследователи формализовали алгоритм, связав его с теорией графов, ядерными методами и задачами минимизации разреза графа.

Основные понятия

Граф и матрица смежности

Исходные данные представляются в виде взвешенного неориентированного графа \( G = (V, E) \), где вершины \( V \) — это объекты (например, точки данных), а рёбра \( E \) — связи между ними. Вес ребра \( w_{ij} \) отражает степень сходства между объектами \( i \) и \( j \). Обычно вес вычисляется с помощью функции ядра, например, гауссовского радиально-базисного ядра: \[ w_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \] где \( \sigma \) — параметр масштаба. Матрица смежности \( W \) размера \( n \times n \) (где \( n \) — число объектов) содержит веса \( w_{ij} \).

Матрица Лапласа

Центральным инструментом является матрица Лапласа графа. Существует несколько вариантов:

• Ненормализованная матрица Лапласа: \( L = D - W \), где \( D \) — диагональная матрица степеней вершин, \( D_{ii} = \sum_j w_{ij} \).
• Нормализованная симметричная матрица Лапласа: \( L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} \).
• Нормализованная случайная матрица Лапласа: \( L_{rw} = D^{-1} L = I - D^{-1} W \).

Свойства матрицы Лапласа: она симметрична (для \( L \) и \( L_{sym} \)), положительно полуопределена, имеет \( n \) неотрицательных собственных значений \( 0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n \). Количество нулевых собственных значений равно числу связных компонент графа.

Спектральное разложение

Спектральная кластеризация использует собственные векторы, соответствующие \( k \) наименьшим собственным значениям матрицы Лапласа (исключая нулевое, если граф связен). Эти векторы содержат информацию о структуре кластеров: точки, принадлежащие одному кластеру, имеют близкие значения в этих векторах.

Алгоритм

Наиболее распространённый алгоритм спектральной кластеризации (нормализованные разрезы) состоит из следующих шагов:

1. Построение графа сходства: По набору данных \( \{x_1, x_2, \dots, x_n\} \) строится взвешенный граф. Используются три основных подхода:

• ε-окрестность: вершины соединяются, если расстояние между ними меньше ε.
• k ближайших соседей (k-NN): каждая вершина соединяется с k ближайшими соседями.
• Полносвязный граф: все вершины соединяются, веса задаются ядром (например, гауссовским).

1. Вычисление матрицы Лапласа: Выбирается один из вариантов (обычно \( L_{sym} \) или \( L_{rw} \)).
2. Спектральное разложение: Находятся \( k \) собственных векторов, соответствующих \( k \) наименьшим собственным значениям выбранной матрицы Лапласа (для \( L_{sym} \) — это \( u_1, \dots, u_k \)). Эти векторы образуют матрицу \( U \in \mathbb{R}^{n \times k} \).
3. Нормализация строк: Строки матрицы \( U \) нормализуются до единичной длины (для \( L_{sym} \)), чтобы устранить влияние степени вершин.
4. Кластеризация в пространстве меньшей размерности: Каждая строка матрицы \( U \) рассматривается как точка в \( \mathbb{R}^k \). К этим точкам применяется стандартный алгоритм кластеризации, например, k-средних. Полученные метки присваиваются исходным вершинам.

Применение

Спектральная кластеризация широко применяется в задачах, где данные имеют сложную нелинейную структуру:

• Сегментация изображений: Разделение изображения на семантически связанные области (объекты, фон) на основе сходства пикселей по цвету, текстуре и положению.
• Анализ социальных сетей: Выявление сообществ (community detection) в графах социальных связей.
• Биоинформатика: Кластеризация генов или белков по функциональной близости, анализ экспрессии генов.
• Обработка текстов: Группировка документов по тематике на основе косинусного сходства.
• Анализ данных с шумом: Спектральная кластеризация устойчивее к выбросам, чем k-средних, при правильном выборе параметров.

Преимущества и недостатки

Преимущества

• Гибкость формы кластеров: Способна выделять кластеры произвольной формы (кольца, спирали, вложенные структуры), что невозможно для методов на основе центроидов.
• Теоретическая обоснованность: Связана с задачей минимизации разреза графа (Normalized Cut, Ratio Cut), что даёт чёткую оптимизационную интерпретацию.
• Работа с графами: Может применяться к данным, изначально представленным в виде графа (например, социальные сети).

Недостатки

• Вычислительная сложность: Требует вычисления собственных векторов матрицы размера \( n \times n \), что для больших наборов данных (\( n > 10^5 \)) становится дорогим (O(n³) для полной диагонализации). Используются приближённые методы, такие как итерации Ланцоша или Nyström-аппроксимация.
• Чувствительность к параметрам: Результат сильно зависит от выбора функции сходства (например, σ в гауссовском ядре) и метода построения графа (ε, k). Неверный выбор может привести к плохому качеству кластеризации.
• Необходимость задания числа кластеров k: Как и многие методы, требует априорного указания количества кластеров, что не всегда известно.
• Масштабируемость: На больших разреженных графах спектральная кластеризация может работать медленнее, чем иерархические методы или алгоритмы на основе случайных блужданий.

Связь с другими методами

Спектральная кластеризация тесно связана с:

• Методом главных компонент (PCA): PCA использует собственные векторы ковариационной матрицы, а спектральная кластеризация — матрицы Лапласа. Оба метода выполняют проекцию в пространство меньшей размерности, но с разной целью.
• Ядерными методами: Спектральная кластеризация может быть интерпретирована как кластеризация в пространстве воспроизводящего ядра (RKHS), где ядро задаётся функцией сходства.
• Диффузионными картами (Diffusion Maps): Эти методы также используют спектр матрицы Лапласа, но для вложения данных в низкоразмерное пространство, а не для кластеризации.
• Алгоритмом k-средних: На завершающем этапе спектральной кластеризации часто применяется k-средних.

Примеры

Пример 1: Концентрические окружности

Набор данных состоит из двух концентрических окружностей. Алгоритм k-средних не может их разделить, так как центроиды не отражают структуру. Спектральная кластеризация строит граф, где точки на одной окружности имеют высокие веса связей, а между окружностями — низкие. После спектрального разложения точки каждой окружности проецируются в два различных кластера в пространстве собственных векторов.

Пример 2: Сегментация изображения

Изображение 100×100 пикселей преобразуется в граф с 10 000 вершин. Веса рёбер вычисляются на основе сходства цвета и близости пикселей. Спектральная кластеризация выделяет области, соответствующие объектам, например, человеку на фоне неба.

Интересные факты

• Второй собственный вектор матрицы Лапласа (вектор Фидлера) используется не только для кластеризации, но и для визуализации графов, упорядочивания вершин и анализа связности.
• Спектральная кластеризация является частным случаем более общего подхода — спектрального анализа графов, который применяется в задачах уменьшения размерности (например, Laplacian Eigenmaps).
• В 2018 году исследователи из Массачусетского технологического института (MIT) предложили метод спектральной кластеризации с использованием случайных блужданий (Random Walk Spectral Clustering), который улучшил масштабируемость для больших графов.

Источники

• Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395–416.
• Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
• Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(98), 298–305.
• Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 849–856.