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

Материал из MachineLearning.

Версия от 11:40, 19 июля 2026; Valeriia Berdnikova (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Основная идея метода заключается в построении графа, вершины которого соответствуют объектам, а веса рёбер отражают их сходство. Затем вычисляются несколько собственных векторов лапласиана графа. Полученное низкоразмерное представление объектов кластеризуется стандартными методами, чаще всего k-means.

Спектральная кластеризация занимает промежуточное положение между методами машинного обучения и теорией графов. Она связана с задачами разбиения графов, случайными блужданиями, снижением размерности и методами анализа сетей.^[1]

Содержание

1 Постановка задачи
2 Граф сходства
3 Матрица смежности
4 Матрица степеней
5 Лапласианы графа
6 Собственные значения и собственные векторы
7 Спектральное вложение
8 Связь с задачами разбиения графов
9 Алгоритм спектральной кластеризации
10 Выбор параметров
11 Масштабируемые методы
12 Расширения спектральной кластеризации
13 Применения
14 Сравнение с другими методами

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

Пусть дана выборка объектов:

$X=\{x_1,x_2,\ldots,x_n\}, \qquad x_i\in\mathbb R^d.$

Требуется разбить множество объектов на $K$ кластеров:

$X=C_1\cup C_2\cup\dots\cup C_K.$

В классических алгоритмах кластеризации близость объектов определяется расстоянием в исходном пространстве признаков. Спектральная кластеризация использует другой подход: сначала строится граф сходства.

Граф задаётся тройкой:

$G=(V,E,W),$

где:

$V$ — множество вершин;
$E$ — множество рёбер;
$W=(w_{ij})$ — матрица весов рёбер.

Каждому объекту $x_i$ соответствует вершина $v_i$ . Вес

$w_{ij}$

характеризует степень сходства объектов $x_i$ и $x_j$ .

Если два объекта похожи, то

$w_{ij}$

имеет большое значение. Если объекты различаются, вес близок к нулю.

После построения графа задача кластеризации преобразуется в задачу поиска слабо связанных групп вершин.

Граф сходства

Построение графа является одним из наиболее важных этапов спектральной кластеризации. Ошибки на этом этапе могут привести к неправильному разбиению даже при идеальном вычислении собственных векторов.

Основные способы построения графа:

полносвязный граф;
граф ближайших соседей;
ε-граф.

Полносвязный граф

В полносвязном графе каждая пара объектов соединена ребром:

$w_{ij}>0,\qquad i\neq j.$

Чаще всего используется гауссово ядро:

$w_{ij}= \exp \left( -\frac{\|x_i-x_j\|^2}{2\sigma^2} \right).$

Параметр $\sigma$ определяет масштаб локальности. Малое значение приводит к тому, что близкими считаются только очень похожие объекты, большое — делает все объекты похожими.

Преимущества полносвязного графа:

используется информация обо всех парах объектов;
хорошо подходит для небольших выборок.

Недостаток:

$O(n^2)$

по памяти и времени для построения матрицы сходства.

Граф ближайших соседей

В графе ближайших соседей объект соединяется только с наиболее близкими объектами.

Для $k$ -NN графа:

$(i,j)\in E \Longleftrightarrow x_j\in kNN(x_i).$

После построения граф обычно симметризуется.

Используются два варианта:

объединённый граф — ребро существует, если одна из вершин выбирает другую;
взаимный граф — ребро существует только при взаимном выборе.

Граф ближайших соседей уменьшает количество рёбер и лучше сохраняет локальную структуру данных.

ε-граф

В ε-графе связь определяется расстоянием:

$(i,j)\in E \Longleftrightarrow \|x_i-x_j\|\leq\varepsilon.$

Преимущество такого подхода — простая геометрическая интерпретация.

Недостаток — необходимость выбора параметра $\varepsilon$ . Если он слишком мал, граф может стать несвязным. Если слишком велик, различные кластеры могут соединиться.

Матрица смежности

Матрица весов

$W=(w_{ij})$

называется матрицей смежности или матрицей сходства.

Для невзвешенного графа:

$w_{ij}= \begin{cases} 1,&(i,j)\in E,\\ 0,&(i,j)\notin E. \end{cases}$

Для взвешенного графа элементы матрицы принимают значения, характеризующие силу связи.

Обычно предполагается, что граф неориентированный:

$w_{ij}=w_{ji}.$

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

Матрица степеней

Степенью вершины называется сумма весов всех исходящих рёбер:

$d_i=\sum_{j=1}^{n}w_{ij}.$

На основе степеней строится диагональная матрица:

$D= \begin{pmatrix} d_1&0&\dots&0\\ 0&d_2&\dots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&d_n \end{pmatrix}.$

Матрица степеней играет важную роль в нормализованных вариантах спектральной кластеризации.

Если вершина имеет большую степень, это означает, что она сильно связана с большим числом других объектов.

Лапласианы графа

Лапласиан графа является центральным объектом спектральной кластеризации.

Ненормализованный лапласиан

Классический лапласиан определяется как:

$L=D-W.$

Для любого вектора $f$ выполняется:

$f^TLf= \frac12 \sum_{i,j} w_{ij}(f_i-f_j)^2.$

Это выражение показывает, что лапласиан минимизирует различия между сильно связанными вершинами.

Если два объекта имеют большой вес связи, то соответствующие значения вектора $f$ должны быть близкими.

Основные свойства:

$L$ симметрична;
собственные значения неотрицательны;
минимальное собственное значение равно нулю.

Количество нулевых собственных значений равно числу компонент связности графа.^[1]

Симметричный нормализованный лапласиан

Для уменьшения влияния различий в степенях используется:

$L_{sym} = D^{-1/2}LD^{-1/2}.$

Эквивалентная форма:

$L_{sym} = I-D^{-1/2}WD^{-1/2}.$

Нормализация делает вклад вершин более сопоставимым и особенно полезна для графов с различными плотностями.

Лапласиан случайного блуждания

Другой вариант:

$L_{rw}=D^{-1}L.$

Он связан с вероятностями переходов случайного блуждания:

$P=D^{-1}W.$

Тогда:

$L_{rw}=I-P.$

Этот оператор показывает, насколько быстро случайное блуждание распространяется по графу.

Собственные значения и собственные векторы

Спектральная кластеризация использует решение задачи:

$Lu=\lambda u.$

где:

$\lambda$ — собственное значение;
$u$ — собственный вектор.

Собственные значения упорядочиваются:

$0=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n.$

Малые собственные значения соответствуют направлениям, в которых структура графа изменяется медленно.

Если граф имеет несколько почти независимых компонент, первые собственные векторы приближают индикаторы этих компонент.

В идеальном случае граф из $K$ компонент имеет:

$\lambda_1=\lambda_2=\dots=\lambda_K=0.$

Поэтому первые $K$ собственных векторов содержат информацию о структуре кластеров.

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

Пусть найдены собственные векторы:

$u_1,u_2,\ldots,u_K.$

Из них формируется матрица:

$U=[u_1,u_2,\ldots,u_K].$

Каждый объект заменяется строкой:

$y_i=U_{i,:}.$

Таким образом исходные данные переводятся в новое пространство размерности $K$ .

После этого выполняется обычная кластеризация:

$y_1,y_2,\ldots,y_n \rightarrow C_1,C_2,\ldots,C_K.$

Чаще всего применяется алгоритм k-means.

Для нормализованной версии Нга — Джордана — Вайса выполняется дополнительная нормировка строк:

$y_i= \frac{U_{i,:}} {\|U_{i,:}\|_2}.$

^[1]

Связь с задачами разбиения графов

Спектральная кластеризация тесно связана с задачами минимального разреза графа. Идея состоит в поиске такого разбиения:

$V=A_1\cup A_2\cup\dots\cup A_K,$

при котором связи между различными группами минимальны, а внутри групп — максимальны.

Разрез графа

Для двух непересекающихся множеств вершин $A$ и $B$ определяется:

$cut(A,B)= \sum_{i\in A} \sum_{j\in B} w_{ij}.$

Минимизация только этого критерия приводит к вырожденному решению: можно отделить одну вершину или небольшую группу вершин.

Поэтому используются нормированные критерии, учитывающие размер кластеров.

RatioCut

Критерий RatioCut определяется как:

$RatioCut(A_1,\ldots,A_K)= \sum_{i=1}^{K} \frac{cut(A_i,\overline{A_i})} {|A_i|}.$

Он нормирует значение разреза количеством вершин в кластере.

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

$L=D-W.$

Normalized Cut

Вместо количества вершин используется объём:

$vol(A)=\sum_{i\in A}d_i.$

Критерий Normalized Cut:

$Ncut(A_1,\ldots,A_K)= \sum_{i=1}^{K} \frac{cut(A_i,\overline{A_i})} {vol(A_i)}.$

Этот критерий учитывает количество связей вершины с остальным графом.

Его спектральная релаксация приводит к нормализованному лапласиану:

$L_{sym}=D^{-1/2}LD^{-1/2}.$

Normalized Cut был предложен для задачи сегментации изображений и стал одной из наиболее известных интерпретаций спектральной кластеризации.^[1]

Алгоритм спектральной кластеризации

Ненормализованный вариант

Вход:

объекты $X$ ;
число кластеров $K$ ;
функция сходства.

Шаги алгоритма:

Построить матрицу сходства $W$ .
Вычислить матрицу степеней $D$ .
Построить лапласиан:

$L=D-W.$

Найти $K$ собственных векторов, соответствующих минимальным собственным значениям.
Сформировать матрицу вложения:

$U=[u_1,\ldots,u_K].$

Выполнить k-means над строками матрицы $U$ .
Назначить исходным объектам найденные метки.

Нормализованный вариант

Для нормализованной версии:

Строится граф сходства.
Вычисляется:

$L_{sym}=I-D^{-1/2}WD^{-1/2}.$

Находятся первые $K$ собственных векторов.
Формируется матрица:

$U=[u_1,\ldots,u_K].$

Каждая строка нормируется:

$y_i= \frac{U_i}{\|U_i\|}.$

Выполняется k-means.

Псевдокод

Вход: X, K

1. Построить граф сходства W.
2. Вычислить D.
3. Построить лапласиан L.
4. Найти K минимальных собственных векторов.
5. Получить спектральное представление объектов.
6. При необходимости нормировать строки.
7. Выполнить k-means.
8. Вернуть метки кластеров.

Выбор параметров

Число кластеров

Число кластеров $K$ является одним из главных параметров алгоритма.

Часто используется анализ спектрального зазора:

$\Delta_k=\lambda_{k+1}-\lambda_k.$

Большой разрыв может указывать на естественное число кластеров.

Однако этот критерий является эвристикой. Спектральный зазор зависит от построенного графа и не всегда соответствует реальной структуре данных.

Число соседей

Для графа ближайших соседей параметр $k$ определяет размер локального окружения.

Малое значение:

сохраняет локальную структуру;
может привести к несвязности графа.

Большое значение:

увеличивает связность;
может создавать ложные связи между кластерами.

На практике рекомендуется проверять устойчивость результата при разных значениях $k$ .

Масштаб ядра

В гауссовом ядре:

$w_{ij}= \exp \left( -\frac{\|x_i-x_j\|^2}{2\sigma^2} \right)$

параметр $\sigma$ задаёт масштаб близости.

При малом $\sigma$ граф становится слишком разреженным.

При большом $\sigma$ различия между объектами уменьшаются.

Для неоднородных данных используют локальные масштабы:

$w_{ij} = \exp \left( -\frac{\|x_i-x_j\|^2} {\sigma_i\sigma_j} \right).$

Число собственных векторов

В стандартном алгоритме число собственных векторов совпадает с числом кластеров:

$r=K.$

Использование большего количества компонент возможно, но требует дополнительного выбора и уже не является прямой релаксацией исходной задачи разбиения графа.

Масштабируемые методы

Классическая спектральная кластеризация плохо масштабируется на больших данных из-за необходимости хранить матрицу сходства.

Для решения этой проблемы используются приближённые методы.

Метод Nyström

Метод Nyström заменяет полную матрицу сходства низкоранговым приближением.

Пусть выбрано $m$ опорных объектов:

$m\ll n.$

Матрица сходства приближается:

$W\approx UV^T.$

Это позволяет вычислять спектральное представление без полного разложения матрицы размера $n\times n$ .

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

снижение требований к памяти;
ускорение вычислений;
возможность работы с большими наборами данных.

Недостаток:

качество зависит от выбора опорных точек.^[1]

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

Вместо полного графа используется граф ближайших соседей.

Количество рёбер становится:

$|E|\ll n^2.$

Это позволяет применять итерационные методы поиска собственных векторов.

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

меньшая память;
возможность работы с большими графами;
сохранение локальной структуры.

Ограничение — результат зависит от качества построенного разреженного графа.

Landmark-based методы

Вместо всех объектов выбирается небольшое число представителей:

$L=\{l_1,\ldots,l_m\}.$

Строится только сходство объектов с этими представителями.

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

Расширения спектральной кластеризации

Многопредставленческая спектральная кластеризация

Во многих задачах объекты могут быть описаны несколькими наборами признаков:

$X^{(1)},X^{(2)},\ldots,X^{(m)}.$

Например, объект может иметь одновременно:

текстовое представление;
визуальные признаки;
биологические характеристики;
сетевую информацию.

Для каждого представления строится собственный граф сходства:

$W^{(1)},W^{(2)},\ldots,W^{(m)}.$

Простейший вариант объединения:

$W=\sum_{i=1}^{m}\alpha_iW^{(i)},$

где:

$\alpha_i\geq0,\qquad \sum_i\alpha_i=1.$

Более сложные методы совместно оптимизируют несколько представлений и учитывают их согласованность.

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

Ограничение состоит в том, что различные представления могут содержать противоречивую структуру, поэтому простое объединение графов не всегда улучшает качество.

Робастная спектральная кластеризация

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

Пусть наблюдаемая матрица:

$W=W_0+E,$

где:

$W_0$ — истинная структура графа;
$E$ — шум или ошибки.

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

Используются:

удаление выбросов;
регуляризация степеней;
устойчивые функции сходства;
модели разреженных ошибок;
совместное обучение графа и кластеров.

Такие методы особенно важны для реальных сетей, где часть рёбер может быть случайной или ошибочной.

Глубокая спектральная кластеризация

Современные методы объединяют спектральные идеи с нейронными сетями.

Вместо явного вычисления собственных векторов обучается отображение:

$f_\theta(x):\mathbb R^d\rightarrow\mathbb R^K.$

Цель обучения — получить представление, близкое к спектральному вложению.

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

возможность обработки больших наборов данных;
работа с новыми объектами;
использование сложных признаковых представлений.

Недостатки:

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

Примером является SpectralNet, где нейронная сеть обучается приближать спектральное вложение.^[1]

Применения

Сегментация изображений

Одно из наиболее известных применений спектральной кластеризации — сегментация изображений.

Вершинами графа являются пиксели или суперпиксели, а веса отражают:

сходство цвета;
близость положения;
сходство текстуры.

Например:

$w_{ij}= \exp \left( -\frac{\|I_i-I_j\|^2}{2\sigma_I^2} -\frac{\|p_i-p_j\|^2}{2\sigma_p^2} \right),$

где:

$I_i$ — цветовые характеристики;
$p_i$ — координаты пикселя.

Normalized Cut стал одним из классических методов сегментации изображений.^[1]

Анализ социальных и информационных сетей

В сетях:

вершины соответствуют пользователям или объектам;
рёбра отражают взаимодействия.

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

сообществ;
групп пользователей;
скрытой структуры сети.

Метод особенно эффективен, если связи внутри групп сильнее связей между ними.

Текстовые данные

Для документов строится граф сходства:

вершины — документы;
веса — сходство текстовых представлений.

В качестве признаков используются:

TF-IDF;
эмбеддинги слов;
представления трансформеров.

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

Биоинформатика

В биоинформатике метод применяется для:

анализа экспрессии генов;
поиска групп клеток;
анализа биологических сетей;
исследования взаимодействий белков.

Особенно полезна возможность учитывать графовую структуру взаимодействий между объектами.

Графовые данные

Если данные уже представлены графом, спектральная кластеризация является естественным методом анализа.

Примеры:

графы цитирования;
транспортные сети;
молекулярные графы;
графы знаний;
сети взаимодействий.

Сравнение с другими методами

k-means

k-means минимизирует расстояние объектов до центров кластеров:

$J= \sum_{i=1}^{K} \sum_{x\in C_i} \|x-\mu_i\|^2.$

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

высокая скорость;
простота;
хорошая масштабируемость.

Недостатки:

требуется число кластеров;
плохо работает для кластеров сложной формы;
зависит от инициализации.

Спектральная кластеризация предпочтительнее, если структура данных определяется связями, а не расстояниями до центроидов.

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

Иерархические методы строят дерево кластеров.

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

позволяют исследовать несколько уровней структуры;
не требуют заранее задавать число кластеров.

Недостатки:

высокая вычислительная сложность;
решения ранних этапов трудно исправить.

Спектральная кластеризация использует глобальную информацию о графе.

DBSCAN

DBSCAN основан на плотности данных.

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

обнаружение кластеров произвольной формы;
выделение шума.

Недостатки:

чувствительность к параметрам плотности;
проблемы при различной плотности кластеров.

Спектральный метод использует структуру графа, а не только локальную плотность.

Gaussian Mixture Models

Gaussian Mixture Models предполагают:

$p(x)= \sum_{k=1}^{K} \pi_kN(x|\mu_k,\Sigma_k).$

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

вероятностная интерпретация;
оценка степени принадлежности.

Недостатки:

необходимость предполагать форму распределений;
локальные оптимумы EM-алгоритма.

Спектральная кластеризация не требует конкретной вероятностной модели.

Mean Shift

Mean Shift ищет максимумы оценки плотности.

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

число кластеров определяется автоматически;
подходит для сложных форм.

Недостатки:

высокая вычислительная стоимость;
зависимость от ширины окна.

Affinity Propagation

Affinity Propagation выбирает представителей кластеров через передачу сообщений между объектами.

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

не требует заранее задавать число кластеров;
центры являются реальными объектами.

Недостатки:

квадратичная память;
ограниченная масштабируемость.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B5%D0%BA%D1%82%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F»

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

Материал из MachineLearning.

Содержание

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

Граф сходства

Полносвязный граф

Граф ближайших соседей

ε-граф

Матрица смежности

Матрица степеней

Лапласианы графа

Ненормализованный лапласиан

Симметричный нормализованный лапласиан

Лапласиан случайного блуждания

Собственные значения и собственные векторы

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

Связь с задачами разбиения графов

Разрез графа

RatioCut

Normalized Cut

Алгоритм спектральной кластеризации

Ненормализованный вариант

Нормализованный вариант

Псевдокод

Выбор параметров

Число кластеров

Число соседей

Масштаб ядра

Число собственных векторов

Масштабируемые методы

Метод Nyström

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

Landmark-based методы

Расширения спектральной кластеризации

Многопредставленческая спектральная кластеризация

Робастная спектральная кластеризация

Глубокая спектральная кластеризация

Применения

Сегментация изображений

Анализ социальных и информационных сетей

Текстовые данные

Биоинформатика

Рекомендательные системы

Графовые данные

Сравнение с другими методами

k-means

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

DBSCAN

Gaussian Mixture Models

Mean Shift

Affinity Propagation

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты