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

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

(Различия между версиями)

Версия 11:50, 19 июля 2026

Статья написана с использованием LLM ChatGPT и проверена участником ....

Содержание

1 Постановка задачи
2 Построение графа сходства
- 2.1 Полносвязный граф
- 2.2 Граф ближайших соседей
- 2.3 ε-граф
3 Матрица смежности и матрица степеней
4 Лапласианы графа
- 4.1 Ненормализованный лапласиан
- 4.2 Нормализованный лапласиан
5 Собственные значения и собственные векторы
6 Спектральное вложение
7 Связь с RatioCut и Normalized Cut
- 7.1 Разрез графа
- 7.2 RatioCut
- 7.3 Normalized Cut
8 Алгоритм спектральной кластеризации
- 8.1 Базовый алгоритм
- 8.2 Псевдокод
9 Выбор параметров
- 9.1 Число кластеров
- 9.2 Выбор числа соседей
- 9.3 Выбор параметра ядра
10 Ненормализованная и нормализованная спектральная кластеризация
- 10.1 Ненормализованный вариант
- 10.2 Нормализованный вариант
11 Масштабируемая спектральная кластеризация
- 11.1 Метод Nyström
- 11.2 Разреженная спектральная кластеризация
- 11.3 Landmark-based методы
12 Расширения метода
- 12.1 Многопредставленческая спектральная кластеризация
- 12.2 Робастная спектральная кластеризация
- 12.3 Глубокая спектральная кластеризация
13 Применения
- 13.1 Сегментация изображений
- 13.2 Анализ социальных сетей
- 13.3 Текстовые данные
- 13.4 Биоинформатика
- 13.5 Рекомендательные системы
14 Сравнение с другими методами
- 14.1 k-means
- 14.2 Иерархическая кластеризация
- 14.3 DBSCAN
- 14.4 Gaussian Mixture Models
- 14.5 Mean Shift
- 14.6 Affinity Propagation
15 Отличия от близких методов
- 15.1 Спектральное разбиение графов
- 15.2 Laplacian Eigenmaps
- 15.3 Diffusion Maps
- 15.4 Графовые нейронные сети
16 Преимущества и ограничения
17 Типичные ошибки
18 Когда метод предпочтителен
19 См. также
20 Литература

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

Основная идея метода состоит в построении графа сходства, вычислении нескольких собственных векторов соответствующего лапласиана и последующей кластеризации полученного низкоразмерного представления, обычно алгоритмом k-means. Метод тесно связан с задачами разбиения графов, критериями Normalized Cut и RatioCut, а также с такими направлениями, как Laplacian Eigenmaps и Diffusion Maps.^[1]

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

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

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

Цель кластеризации — разбить множество объектов на $K$ групп:

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

В спектральной кластеризации сначала строится граф

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

где:

$V$ — множество вершин, соответствующих объектам;
$E$ — множество рёбер;
$W=(w_{ij})$ — матрица весов, задающая сходство объектов.

Вес $w_{ij}$ показывает, насколько объекты $x_i$ и $x_j$ близки. Большие значения соответствуют сильным связям, малые — слабым.

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

Построение графа сходства

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

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

В простейшем случае каждое ребро присутствует между всеми парами объектов:

$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 \Leftrightarrow x_j\in {\rm kNN}(x_i).$

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

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

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

ε-граф

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

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

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

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

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

$W=(w_{ij})$

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

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

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

Степень вершины определяется как

$d_i=\sum_j w_{ij}.$

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

$D= \left(\begin{array}{cccc} d_1&0&\dots&0\\ 0&d_2&\dots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&d_n \end{array}\right).$

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

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

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

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

$L=D-W.$

Он обладает важным свойством:

$x^TLx=\frac12\sum_{i,j}w_{ij}(x_i-x_j)^2.$

Следовательно, если две вершины сильно связаны, то значение соответствующих координат вектора должно быть близким.

Лапласиан является симметричной положительно полуопределённой матрицей. Его минимальное собственное значение равно нулю:

$\lambda_1=0.$

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

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

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

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

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

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

Он связан со случайным блужданием по графу.

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

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

Пусть

$Lu=\lambda u$

— задача на собственные значения лапласиана.

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

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

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

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

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

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

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

Разность между соседними собственными значениями:

$\lambda_{K+1}-\lambda_K$

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

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

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

$u_1,\ldots,u_K.$

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

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

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

$y_i=U_{i,:}.$

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

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

$\{y_1,\ldots,y_n\}\rightarrow C_1,\ldots,C_K.$

Чаще всего используется k-means.

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

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

^[1]

Связь с RatioCut и Normalized Cut

Разрез графа

Для двух множеств вершин $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,\bar A_i)} {|A_i|}.$

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

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

Normalized Cut

Normalized Cut использует объём множества:

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

Критерий:

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

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

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

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

Базовый алгоритм

Вход:

множество объектов $X=\{x_1,\ldots,x_n\}$ ;
число кластеров $K$ ;
функция сходства;
параметры построения графа.

Выход:

кластерные метки объектов.

Алгоритм:

Построить матрицу сходства $W$ .
Вычислить матрицу степеней $D$ .
Построить выбранный лапласиан:
1. $L=D-W$ для ненормализованной версии;
2. $L_{sym}=I-D^{-1/2}WD^{-1/2}$ для нормализованной версии.
Найти $K$ собственных векторов, соответствующих наименьшим собственным значениям.
Сформировать спектральное вложение объектов.
Выполнить кластеризацию строк полученной матрицы, обычно методом k-means.
Присвоить исходным объектам найденные метки.

Псевдокод

Вход: данные X, число кластеров K.

Выход: метки кластеров.

1. Построить граф сходства W.
2. Вычислить степени вершин D.
3. Построить лапласиан L.
4. Найти K минимальных собственных векторов:
      L u_i = λ_i u_i
5. Сформировать матрицу U.
6. Нормировать строки U (для нормализованного варианта).
7. Выполнить k-means по строкам U.
8. Вернуть полученные группы.

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

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

В классическом алгоритме число кластеров $K$ задаётся заранее. Однако часто его необходимо оценивать.

Один из распространённых подходов основан на спектральном зазоре:

$gap(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).$

Такой подход называется самонастраиваемой спектральной кластеризацией.^[1]

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

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

Используется лапласиан

$L=D-W.$

Он соответствует релаксации критерия RatioCut.

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

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

Недостатки:

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

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

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

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

или

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

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

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

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

Именно нормализованные варианты чаще используются в современных приложениях.

Масштабируемая спектральная кластеризация

Классическая спектральная кластеризация имеет высокую вычислительную стоимость.

Для полной матрицы сходства:

$W\in\mathbf{R}^{n\times n},$

требуется

$O(n^2)$

памяти.

Полное собственное разложение имеет сложность порядка:

$O(n^3).$

Поэтому для больших наборов данных применяются приближённые методы.

Метод Nyström

Метод Nyströ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)},...,X^{(m)},$

для каждого строится отдельный граф.

Затем графы объединяются:

$W=\sum_i\alpha_iW_i.$

Такой подход применяется, например, при объединении:

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

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

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

Классический метод чувствителен к ошибочным рёбрам.

Робастные варианты учитывают:

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

Обычно вводится дополнительная модель ошибок:

$W=W_0+E,$

где $W_0$ — истинная структура, а $E$ — шум.

Цель состоит в восстановлении устойчивого графа перед кластеризацией.

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

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

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

$f_\theta(x):\mathbf{R}^d\rightarrow\mathbf{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).$

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

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

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

Спектральные методы позволяют находить:

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

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

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

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

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

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

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

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

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

Применения:

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

Особенно полезна способность работать с графами взаимодействий.

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

k-means

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

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

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

DBSCAN

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

Gaussian Mixture Models

Gaussian Mixture Models задают вероятностную смесь распределений и позволяют получать мягкие принадлежности. Спектральная кластеризация не требует предположения о гауссовой форме компонент, но не даёт вероятностной интерпретации меток.

Mean Shift

Mean Shift ищет моды оценки плотности и не требует заранее задавать число кластеров. Его результат чувствителен к ширине окна, а вычислительная стоимость высока на больших выборках.

Affinity Propagation

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

Отличия от близких методов

Спектральное разбиение графов

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

Laplacian Eigenmaps

Laplacian Eigenmaps использует собственные векторы лапласиана для нелинейного снижения размерности. Целью является сохранение локальной геометрии, а не обязательное получение кластерных меток.^[1]

Diffusion Maps

Diffusion Maps строит координаты по собственным векторам марковского оператора и учитывает многошаговую диффузию. Метод предназначен прежде всего для анализа геометрии и диффузионных расстояний.^[1]

Графовые нейронные сети

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

Преимущества и ограничения

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

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

Основные ограничения:

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

Типичные ошибки

использование нестандартизованных признаков при евклидовой метрике;
слишком малое или слишком большое число соседей;
игнорирование изолированных вершин;
выбор собственных векторов не с того края спектра;
пропуск построчной нормировки в алгоритме Нга — Джордана — Вайса;
единственный запуск k-means;
подбор параметров по тестовым меткам;
интерпретация любого спектрального зазора как доказательства кластерной структуры.

Когда метод предпочтителен

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

См. также

Литература

Chung F. R. K. Spectral Graph Theory. — American Mathematical Society, 1997.
von Luxburg U. A Tutorial on Spectral Clustering // Statistics and Computing. — 2007. — Т. 17. — № 4. — С. 395—416.
Shi J., Malik J. Normalized Cuts and Image Segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2000. — Т. 22. — № 8. — С. 888—905.
Ng A. Y., Jordan M. I., Weiss Y. On Spectral Clustering: Analysis and an Algorithm // Advances in Neural Information Processing Systems 14. — 2002. — С. 849—856.
Zelnik-Manor L., Perona P. Self-Tuning Spectral Clustering // Advances in Neural Information Processing Systems 17. — 2004.
Fowlkes C., Belongie S., Chung F., Malik J. Spectral Grouping Using the Nyström Method // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2004. — Т. 26. — № 2. — С. 214—225.
Belkin M., Niyogi P. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation // Neural Computation. — 2003. — Т. 15. — № 6. — С. 1373—1396.
Coifman R. R., Lafon S. Diffusion Maps // Applied and Computational Harmonic Analysis. — 2006. — Т. 21. — № 1. — С. 5—30.
Shaham U., Stanton K., Li H., Nadler B., Basri R., Kluger Y. SpectralNet: Spectral Clustering Using Deep Neural Networks // International Conference on Learning Representations. — 2018.

Источник — «http://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»

@@ Строка 1: / Строка 1: @@
-'''Спектральная кластеризация''' — семейство методов [[Кластеризация|кластеризации]], основанных на представлении данных в виде графа сходства и анализе спектральных свойств соответствующего [[Лапласиан графа|лапласиана]]. В отличие от методов, работающих непосредственно с координатами объектов, спектральная кластеризация использует структуру связей между объектами и позволяет обнаруживать кластеры сложной формы.
+{{well|Статья написана с использованием LLM ChatGPT и проверена участником [[Участник:...|...]].}}
-Основная идея метода заключается в построении графа, вершины которого соответствуют объектам, а веса рёбер отражают их сходство. Затем вычисляются несколько собственных векторов лапласиана графа. Полученное низкоразмерное представление объектов кластеризуется стандартными методами, чаще всего [[k-means]].
+{{TOCright}}
-Спектральная кластеризация занимает промежуточное положение между методами машинного обучения и теорией графов. Она связана с задачами разбиения графов, случайными блужданиями, снижением размерности и методами анализа сетей.<ref name="Luxburg2007">U. von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4):395–416, 2007.</ref>
+'''Спектральная кластеризация''' — семейство методов [[Кластеризация|кластеризации]], основанных на представлении данных в виде взвешенного графа и анализе спектра его [[Лапласиан графа|лапласиана]]. В отличие от методов, работающих непосредственно в исходном пространстве признаков, спектральная кластеризация использует структуру связей между объектами и позволяет находить кластеры сложной формы, которые могут быть неразделимы линейными границами.
+Основная идея метода состоит в построении графа сходства, вычислении нескольких собственных векторов соответствующего лапласиана и последующей кластеризации полученного низкоразмерного представления, обычно алгоритмом [[k-means]]. Метод тесно связан с задачами разбиения графов, критериями [[Normalized Cut]] и [[RatioCut]], а также с такими направлениями, как [[Laplacian Eigenmaps]] и [[Diffusion Maps]].<ref name="Luxburg2007">U. von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4):395–416, 2007.</ref>
 == Постановка задачи ==
-Пусть дана выборка объектов:
+Пусть дана выборка объектов
-:: <tex>X=\{x_1,x_2,\ldots,x_n\}, \qquad x_i\in\mathbb R^d.</tex>
+:: <tex>X=\{x_1,\ldots,x_n\}, \qquad x_i\in\mathbf{R}^d.</tex>
-Требуется разбить множество объектов на <tex>K</tex> кластеров:
+Цель [[кластеризация|кластеризации]] — разбить множество объектов на <tex>K</tex> групп:
 :: <tex>X=C_1\cup C_2\cup\dots\cup C_K.</tex>
-В классических алгоритмах кластеризации близость объектов определяется расстоянием в исходном пространстве признаков. Спектральная кластеризация использует другой подход: сначала строится граф сходства.
+В спектральной кластеризации сначала строится граф
-Граф задаётся тройкой:
 :: <tex>G=(V,E,W),</tex>
@@ Строка 23: / Строка 23: @@
 где:
-* <tex>V</tex> — множество вершин;
+* <tex>V</tex> — множество вершин, соответствующих объектам;
 * <tex>E</tex> — множество рёбер;
-* <tex>W=(w_{ij})</tex> — матрица весов рёбер.
+* <tex>W=(w_{ij})</tex> — матрица весов, задающая сходство объектов.
-Каждому объекту <tex>x_i</tex> соответствует вершина <tex>v_i</tex>. Вес
+Вес <tex>w_{ij}</tex> показывает, насколько объекты <tex>x_i</tex> и <tex>x_j</tex> близки. Большие значения соответствуют сильным связям, малые — слабым.
-:: <tex>w_{ij}</tex>
+После построения графа задача кластеризации преобразуется в задачу поиска слабо связанных областей графа.
-характеризует степень сходства объектов <tex>x_i</tex> и <tex>x_j</tex>.
+== Построение графа сходства ==
-Если два объекта похожи, то
+Качество спектральной кластеризации во многом определяется выбором графа. Один и тот же набор объектов при разных способах построения графа может давать различные результаты.
-:: <tex>w_{ij}</tex>
-имеет большое значение. Если объекты различаются, вес близок к нулю.
-После построения графа задача кластеризации преобразуется в задачу поиска слабо связанных групп вершин.
-== Граф сходства ==
-Построение графа является одним из наиболее важных этапов спектральной кластеризации. Ошибки на этом этапе могут привести к неправильному разбиению даже при идеальном вычислении собственных векторов.
-Основные способы построения графа:
-* полносвязный граф;
-* граф ближайших соседей;
-* ε-граф.
 === Полносвязный граф ===
-В полносвязном графе каждая пара объектов соединена ребром:
+В простейшем случае каждое ребро присутствует между всеми парами объектов:
 :: <tex>w_{ij}>0,\qquad i\neq j.</tex>
-Чаще всего используется гауссово ядро:
+Часто используется гауссово ядро:
-:: <tex>
+:: <tex>w_{ij}=\exp\left(-\frac{\|x_i-x_j\|^2}{2\sigma^2}\right).</tex>
-w_{ij}=
-\exp
-\left(
--\frac{\|x_i-x_j\|^2}{2\sigma^2}
-\right).
-</tex>
-Параметр <tex>\sigma</tex> определяет масштаб локальности. Малое значение приводит к тому, что близкими считаются только очень похожие объекты, большое — делает все объекты похожими.
+Параметр <tex>\sigma</tex> определяет масштаб локальной близости.
-Преимущества полносвязного графа:
+Преимущество полносвязного графа — использование всей информации о сходстве. Недостаток — квадратичная сложность хранения:
-* используется информация обо всех парах объектов;
+:: <tex>O(n^2).</tex>
-* хорошо подходит для небольших выборок.
-Недостаток:
+Поэтому для больших данных чаще используются разреженные графы.
-:: <tex>O(n^2)</tex>
-по памяти и времени для построения матрицы сходства.
 === Граф ближайших соседей ===
-В графе ближайших соседей объект соединяется только с наиболее близкими объектами.
+В <tex>k</tex>-NN графе вершина соединяется только с ближайшими соседями:
-Для <tex>k</tex>-NN графа:
+:: <tex>(i,j)\in E \Leftrightarrow x_j\in {\rm kNN}(x_i).</tex>
-:: <tex>
+После построения граф обычно симметризуется:
-(i,j)\in E
-\Longleftrightarrow
-x_j\in kNN(x_i).
-</tex>
-После построения граф обычно симметризуется.
+* объединённый граф — ребро существует, если хотя бы одна вершина выбирает другую;
+* взаимный граф — ребро существует, если обе вершины выбирают друг друга.
-Используются два варианта:
+Граф ближайших соседей уменьшает вычислительную стоимость и лучше сохраняет локальную структуру данных.
-* объединённый граф — ребро существует, если одна из вершин выбирает другую;
-* взаимный граф — ребро существует только при взаимном выборе.
-Граф ближайших соседей уменьшает количество рёбер и лучше сохраняет локальную структуру данных.
 === ε-граф ===
-В ε-графе связь определяется расстоянием:
+В ε-графе связь создаётся, если расстояние меньше заданного порога:
-:: <tex>
-(i,j)\in E
-\Longleftrightarrow
-\|x_i-x_j\|\leq\varepsilon.
-</tex>
-Преимущество такого подхода — простая геометрическая интерпретация.
+:: <tex>(i,j)\in E \Leftrightarrow \|x_i-x_j\|\leq\varepsilon.</tex>
-Недостаток — необходимость выбора параметра <tex>\varepsilon</tex>. Если он слишком мал, граф может стать несвязным. Если слишком велик, различные кластеры могут соединиться.
+Недостаток метода — необходимость правильно выбрать параметр <tex>\varepsilon</tex>. Малое значение может привести к разрыву графа, а большое — к объединению разных кластеров.
-== Матрица смежности ==
+== Матрица смежности и матрица степеней ==
 Матрица весов
-:: <tex>
+:: <tex>W=(w_{ij})</tex>
-W=(w_{ij})
-</tex>
 называется матрицей смежности или матрицей сходства.
@@ Строка 127: / Строка 84: @@
 Для невзвешенного графа:
-:: <tex>
+:: <tex>w_{ij}= \left\{\begin{array}{ll} 1,&(i,j)\in E,\\ 0,&(i,j)\notin E. \end{array}\right.</tex>
-w_{ij}=
-\begin{cases}
-,&(i,j)\in E,\\
-,&(i,j)\notin E.
-\end{cases}
-</tex>
-Для взвешенного графа элементы матрицы принимают значения, характеризующие силу связи.
+Степень вершины определяется как
-Обычно предполагается, что граф неориентированный:
+:: <tex>d_i=\sum_j w_{ij}.</tex>
-:: <tex>w_{ij}=w_{ji}.</tex>
+Матрица степеней:
-Это условие позволяет использовать свойства симметричных матриц и стандартную теорию собственных значений.
+:: <tex>D= \left(\begin{array}{cccc} d_1&0&\dots&0\\ 0&d_2&\dots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&d_n \end{array}\right).</tex>
-== Матрица степеней ==
+Степень показывает общую силу связи вершины с остальным графом.
-Степенью вершины называется сумма весов всех исходящих рёбер:
-:: <tex>
-d_i=\sum_{j=1}^{n}w_{ij}.
-</tex>
-На основе степеней строится диагональная матрица:
-:: <tex>
-D=
-\begin{pmatrix}
-d_1&0&\dots&0\\
-&d_2&\dots&0\\
-\vdots&\vdots&\ddots&\vdots\\
-&0&\dots&d_n
-\end{pmatrix}.
-</tex>
-Матрица степеней играет важную роль в нормализованных вариантах спектральной кластеризации.
-Если вершина имеет большую степень, это означает, что она сильно связана с большим числом других объектов.
 == Лапласианы графа ==
-Лапласиан графа является центральным объектом спектральной кластеризации.
 === Ненормализованный лапласиан ===
-Классический лапласиан определяется как:
+Классический лапласиан определяется как
-:: <tex>
+:: <tex>L=D-W.</tex>
-L=D-W.
-</tex>
-Для любого вектора <tex>f</tex> выполняется:
+Он обладает важным свойством:
-:: <tex>
+:: <tex>x^TLx=\frac12\sum_{i,j}w_{ij}(x_i-x_j)^2.</tex>
-f^TLf=
-\frac12
-\sum_{i,j}
-w_{ij}(f_i-f_j)^2.
-</tex>
-Это выражение показывает, что лапласиан минимизирует различия между сильно связанными вершинами.
+Следовательно, если две вершины сильно связаны, то значение соответствующих координат вектора должно быть близким.
-Если два объекта имеют большой вес связи, то соответствующие значения вектора <tex>f</tex> должны быть близкими.
+Лапласиан является симметричной положительно полуопределённой матрицей. Его минимальное собственное значение равно нулю:
-Основные свойства:
+:: <tex>\lambda_1=0.</tex>
-* <tex>L</tex> симметрична;
+Количество собственных значений, равных нулю, совпадает с количеством компонент связности графа.<ref name="Chung1997">F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.</ref>
-* собственные значения неотрицательны;
-* минимальное собственное значение равно нулю.
-Количество нулевых собственных значений равно числу компонент связности графа.<ref name="Chung1997">F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.</ref>
+=== Нормализованный лапласиан ===
-=== Симметричный нормализованный лапласиан ===
+Для уменьшения влияния различий в степенях вершин используют нормализованный лапласиан:
-Для уменьшения влияния различий в степенях используется:
+:: <tex>L_{sym}=D^{-1/2}LD^{-1/2} =I-D^{-1/2}WD^{-1/2}.</tex>
-:: <tex>
-L_{sym}
-=
-D^{-1/2}LD^{-1/2}.
-</tex>
-Эквивалентная форма:
-:: <tex>
-L_{sym}
-=
-I-D^{-1/2}WD^{-1/2}.
-</tex>
-Нормализация делает вклад вершин более сопоставимым и особенно полезна для графов с различными плотностями.
-=== Лапласиан случайного блуждания ===
 Другой вариант:
-:: <tex>
+:: <tex>L_{rw}=D^{-1}L.</tex>
-L_{rw}=D^{-1}L.
-</tex>
-Он связан с вероятностями переходов случайного блуждания:
+Он связан со случайным блужданием по графу.
-:: <tex>
+Нормализация особенно важна, когда кластеры имеют разные размеры или различную плотность связей.
-P=D^{-1}W.
-</tex>
-Тогда:
+== Собственные значения и собственные векторы ==
-:: <tex>
+Пусть
-L_{rw}=I-P.
-</tex>
-Этот оператор показывает, насколько быстро случайное блуждание распространяется по графу.
+:: <tex>Lu=\lambda u</tex>
-== Собственные значения и собственные векторы ==
+— задача на собственные значения лапласиана.
-Спектральная кластеризация использует решение задачи:
+Собственные значения упорядочиваются:
-:: <tex>
+:: <tex>0=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n.</tex>
-Lu=\lambda u.
-</tex>
-где:
+Собственные векторы соответствуют направлениям, в которых структура графа изменяется медленно.
-* <tex>\lambda</tex> — собственное значение;
+Если граф состоит из нескольких почти независимых частей, то первые собственные векторы приближают индикаторы этих групп.
-* <tex>u</tex> — собственный вектор.
-Собственные значения упорядочиваются:
+В идеальном случае, когда граф имеет ровно <tex>K</tex> компонент связности:
-:: <tex>
+:: <tex>\lambda_1=\lambda_2=\dots=\lambda_K=0.</tex>
-=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n.
-</tex>
-Малые собственные значения соответствуют направлениям, в которых структура графа изменяется медленно.
+Поэтому первые <tex>K</tex> собственных векторов содержат информацию о кластерной структуре.
-Если граф имеет несколько почти независимых компонент, первые собственные векторы приближают индикаторы этих компонент.
+Разность между соседними собственными значениями:
-В идеальном случае граф из <tex>K</tex> компонент имеет:
+:: <tex>\lambda_{K+1}-\lambda_K</tex>
-:: <tex>
+называется спектральным зазором и часто используется для выбора числа кластеров.
-\lambda_1=\lambda_2=\dots=\lambda_K=0.
-</tex>
-Поэтому первые <tex>K</tex> собственных векторов содержат информацию о структуре кластеров.
 == Спектральное вложение ==
-Пусть найдены собственные векторы:
+Пусть найдены собственные векторы
-:: <tex>
+:: <tex>u_1,\ldots,u_K.</tex>
-u_1,u_2,\ldots,u_K.
-</tex>
 Из них формируется матрица:
-:: <tex>
+:: <tex>U=[u_1,\ldots,u_K].</tex>
-U=[u_1,u_2,\ldots,u_K].
-</tex>
-Каждый объект заменяется строкой:
+Каждый объект заменяется строкой этой матрицы:
-:: <tex>
+:: <tex>y_i=U_{i,:}.</tex>
-y_i=U_{i,:}.
-</tex>
-Таким образом исходные данные переводятся в новое пространство размерности <tex>K</tex>.
+Таким образом исходное пространство высокой размерности заменяется новым пространством размерности <tex>K</tex>.
-После этого выполняется обычная кластеризация:
+После этого применяется обычная кластеризация:
-:: <tex>
+:: <tex>\{y_1,\ldots,y_n\}\rightarrow C_1,\ldots,C_K.</tex>
-y_1,y_2,\ldots,y_n
-\rightarrow
-C_1,C_2,\ldots,C_K.
-</tex>
-Чаще всего применяется алгоритм [[k-means]].
+Чаще всего используется [[k-means]].
-Для нормализованной версии Нга — Джордана — Вайса выполняется дополнительная нормировка строк:
+Для нормализованной версии Нга — Джордана — Вайса строки дополнительно нормируются:
-:: <tex>
+:: <tex>y_i= \frac{U_{i,:}}{\|U_{i,:}\|_2}.</tex>
-y_i=
-\frac{U_{i,:}}
-{\|U_{i,:}\|_2}.
-</tex>
 <ref name="Ng2002">A. Ng, M. Jordan, Y. Weiss. On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 2002.</ref>
-== Связь с задачами разбиения графов ==
+== Связь с RatioCut и Normalized Cut ==
-Спектральная кластеризация тесно связана с задачами минимального разреза графа. Идея состоит в поиске такого разбиения:
-:: <tex>
-V=A_1\cup A_2\cup\dots\cup A_K,
-</tex>
-при котором связи между различными группами минимальны, а внутри групп — максимальны.
 === Разрез графа ===
-Для двух непересекающихся множеств вершин <tex>A</tex> и <tex>B</tex> определяется:
+Для двух множеств вершин <tex>A</tex> и <tex>B</tex> определяется вес разреза:
-:: <tex>
+:: <tex>cut(A,B)= \sum_{i\in A}\sum_{j\in B}w_{ij}.</tex>
-cut(A,B)=
-\sum_{i\in A}
-\sum_{j\in B}
-w_{ij}.
-</tex>
-Минимизация только этого критерия приводит к вырожденному решению: можно отделить одну вершину или небольшую группу вершин.
+Минимизация только этого выражения приводит к выделению маленьких групп или одиночных вершин.
-Поэтому используются нормированные критерии, учитывающие размер кластеров.
 === RatioCut ===
-Критерий RatioCut определяется как:
+Критерий RatioCut учитывает размер кластеров:
-:: <tex>
+:: <tex>RatioCut(A_1,\ldots,A_K)= \sum_{i=1}^{K} \frac{cut(A_i,\bar A_i)} {|A_i|}.</tex>
-RatioCut(A_1,\ldots,A_K)=
-\sum_{i=1}^{K}
-\frac{cut(A_i,\overline{A_i})}
-{|A_i|}.
-</tex>
-Он нормирует значение разреза количеством вершин в кластере.
+Он стремится минимизировать связи между кластерами и одновременно избегать слишком маленьких групп.
-Спектральная релаксация этой задачи приводит к поиску собственных векторов ненормализованного лапласиана:
+Спектральная релаксация RatioCut приводит к поиску собственных векторов ненормализованного лапласиана.
-:: <tex>
-L=D-W.
-</tex>
 === Normalized Cut ===
-Вместо количества вершин используется объём:
+Normalized Cut использует объём множества:
-:: <tex>
+:: <tex>vol(A)=\sum_{i\in A}d_i.</tex>
-vol(A)=\sum_{i\in A}d_i.
-</tex>
-Критерий Normalized Cut:
+Критерий:
-:: <tex>
+:: <tex>Ncut(A_1,\ldots,A_K)= \sum_{i=1}^{K} \frac{cut(A_i,\bar A_i)} {vol(A_i)}.</tex>
-Ncut(A_1,\ldots,A_K)=
-\sum_{i=1}^{K}
-\frac{cut(A_i,\overline{A_i})}
-{vol(A_i)}.
-</tex>
-Этот критерий учитывает количество связей вершины с остальным графом.
+Его спектральная релаксация приводит к собственным векторам нормализованного лапласиана.
-Его спектральная релаксация приводит к нормализованному лапласиану:
-:: <tex>
-L_{sym}=D^{-1/2}LD^{-1/2}.
-</tex>
-Normalized Cut был предложен для задачи сегментации изображений и стал одной из наиболее известных интерпретаций спектральной кластеризации.<ref name="ShiMalik2000">J. Shi, J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.</ref>
+Normalized Cut широко применяется в задачах сегментации изображений.<ref name="ShiMalik2000">J. Shi, J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.</ref>
 == Алгоритм спектральной кластеризации ==
-=== Ненормализованный вариант ===
+=== Базовый алгоритм ===
 Вход:
-* объекты <tex>X</tex>;
+* множество объектов <tex>X=\{x_1,\ldots,x_n\}</tex>;
 * число кластеров <tex>K</tex>;
-* функция сходства.
+* функция сходства;
+* параметры построения графа.
-Шаги алгоритма:
+Выход:
+* кластерные метки объектов.
+Алгоритм:
 # Построить матрицу сходства <tex>W</tex>.
 # Вычислить матрицу степеней <tex>D</tex>.
-# Построить лапласиан:
+# Построить выбранный лапласиан:
+## <tex>L=D-W</tex> для ненормализованной версии;
+## <tex>L_{sym}=I-D^{-1/2}WD^{-1/2}</tex> для нормализованной версии.
+# Найти <tex>K</tex> собственных векторов, соответствующих наименьшим собственным значениям.
+# Сформировать спектральное вложение объектов.
+# Выполнить кластеризацию строк полученной матрицы, обычно методом [[k-means]].
+# Присвоить исходным объектам найденные метки.
-:: <tex>
+=== Псевдокод ===
-L=D-W.
-</tex>
-# Найти <tex>K</tex> собственных векторов, соответствующих минимальным собственным значениям.
+'''Вход:''' данные X, число кластеров K.
-# Сформировать матрицу вложения:
-:: <tex>
+'''Выход:''' метки кластеров.
-U=[u_1,\ldots,u_K].
-</tex>
-# Выполнить [[k-means]] над строками матрицы <tex>U</tex>.
+. Построить граф сходства W.
-# Назначить исходным объектам найденные метки.
+. Вычислить степени вершин D.
+. Построить лапласиан L.
+. Найти K минимальных собственных векторов:
+       L u_i = λ_i u_i
+. Сформировать матрицу U.
+. Нормировать строки U (для нормализованного варианта).
+. Выполнить k-means по строкам U.
+. Вернуть полученные группы.
+== Выбор параметров ==
-=== Нормализованный вариант ===
+=== Число кластеров ===
-Для нормализованной версии:
+В классическом алгоритме число кластеров <tex>K</tex> задаётся заранее. Однако часто его необходимо оценивать.
-# Строится граф сходства.
+Один из распространённых подходов основан на спектральном зазоре:
-# Вычисляется:
-:: <tex>
+:: <tex>gap(k)=\lambda_{k+1}-\lambda_k.</tex>
-L_{sym}=I-D^{-1/2}WD^{-1/2}.
-</tex>
-# Находятся первые <tex>K</tex> собственных векторов.
+Если между двумя соседними собственными значениями существует большой разрыв, это может указывать на естественное число кластеров.
-# Формируется матрица:
-:: <tex>
+Однако спектральный зазор является только эвристикой. Большой разрыв может возникать из-за особенностей построенного графа, выбросов или неравномерной плотности данных.
-U=[u_1,\ldots,u_K].
-</tex>
-# Каждая строка нормируется:
+=== Выбор числа соседей ===
-:: <tex>
+В графах ближайших соседей параметр <tex>k</tex> определяет локальный масштаб.
-y_i=
-\frac{U_i}{\|U_i\|}.
-</tex>
-# Выполняется [[k-means]].
+Слишком маленькое значение:
+* приводит к разрывам графа;
+* создаёт искусственные компоненты связности;
+* делает результат нестабильным.
-=== Псевдокод ===
+Слишком большое значение:
- Вход: X, K
+* добавляет связи между различными группами;
+* сглаживает границы кластеров;
+* приближает граф к полносвязному.
-. Построить граф сходства W.
+На практике рекомендуется проверять устойчивость кластеров при нескольких значениях <tex>k</tex>.
-. Вычислить D.
-. Построить лапласиан L.
-. Найти K минимальных собственных векторов.
-. Получить спектральное представление объектов.
-. При необходимости нормировать строки.
-. Выполнить k-means.
-. Вернуть метки кластеров.
+=== Выбор параметра ядра ===
-== Выбор параметров ==
+Для гауссового сходства
-=== Число кластеров ===
+:: <tex>w_{ij}= \exp \left( -\frac{\|x_i-x_j\|^2}{2\sigma^2} \right)</tex>
-Число кластеров <tex>K</tex> является одним из главных параметров алгоритма.
+параметр <tex>\sigma</tex> определяет масштаб.
-Часто используется анализ спектрального зазора:
+Если <tex>\sigma</tex> слишком мал:
-:: <tex>
+* большинство весов становится близко к нулю;
-\Delta_k=\lambda_{k+1}-\lambda_k.
+* граф может распасться.
-</tex>
-Большой разрыв может указывать на естественное число кластеров.
+Если <tex>\sigma</tex> слишком велик:
-Однако этот критерий является эвристикой. Спектральный зазор зависит от построенного графа и не всегда соответствует реальной структуре данных.
+* все объекты становятся похожими;
+* теряется локальная структура.
-=== Число соседей ===
+Для неоднородных данных применяют локальные масштабы:
-Для графа ближайших соседей параметр <tex>k</tex> определяет размер локального окружения.
+:: <tex>w_{ij}= \exp \left( -\frac{\|x_i-x_j\|^2}{\sigma_i\sigma_j} \right).</tex>
-Малое значение:
+Такой подход называется самонастраиваемой спектральной кластеризацией.<ref name="Zelnik2004">L. Zelnik-Manor, P. Perona. Self-Tuning Spectral Clustering. Advances in Neural Information Processing Systems, 2004.</ref>
-* сохраняет локальную структуру;
+== Ненормализованная и нормализованная спектральная кластеризация ==
-* может привести к несвязности графа.
-Большое значение:
+=== Ненормализованный вариант ===
-* увеличивает связность;
+Используется лапласиан
-* может создавать ложные связи между кластерами.
-На практике рекомендуется проверять устойчивость результата при разных значениях <tex>k</tex>.
+:: <tex>L=D-W.</tex>
-=== Масштаб ядра ===
+Он соответствует релаксации критерия RatioCut.
-В гауссовом ядре:
+Преимущества:
-:: <tex>
+* простая математическая форма;
-w_{ij}=
+* естественная связь с теорией графов;
-\exp
+* хорошая работа при близких степенях вершин.
-\left(
--\frac{\|x_i-x_j\|^2}{2\sigma^2}
-\right)
-</tex>
-параметр <tex>\sigma</tex> задаёт масштаб близости.
+Недостатки:
-При малом <tex>\sigma</tex> граф становится слишком разреженным.
+* чувствительность к различию плотностей;
+* зависимость от размеров кластеров;
+* хуже работает при сильно неоднородных данных.
-При большом <tex>\sigma</tex> различия между объектами уменьшаются.
+=== Нормализованный вариант ===
-Для неоднородных данных используют локальные масштабы:
+Используются:
-:: <tex>
+:: <tex>L_{sym}=D^{-1/2}LD^{-1/2}</tex>
-w_{ij}
-=
-\exp
-\left(
--\frac{\|x_i-x_j\|^2}
-{\sigma_i\sigma_j}
-\right).
-</tex>
-=== Число собственных векторов ===
+или
-В стандартном алгоритме число собственных векторов совпадает с числом кластеров:
+:: <tex>L_{rw}=D^{-1}L.</tex>
-:: <tex>
+Нормализация учитывает степень каждой вершины и уменьшает влияние крупных плотных областей.
-r=K.
-</tex>
-Использование большего количества компонент возможно, но требует дополнительного выбора и уже не является прямой релаксацией исходной задачи разбиения графа.
+Преимущества:
+* устойчивость к различным размерам кластеров;
+* связь со случайными блужданиями;
+* широкое применение на реальных данных.
-== Масштабируемые методы ==
+Именно нормализованные варианты чаще используются в современных приложениях.
-Классическая спектральная кластеризация плохо масштабируется на больших данных из-за необходимости хранить матрицу сходства.
+== Масштабируемая спектральная кластеризация ==
-Для решения этой проблемы используются приближённые методы.
+Классическая спектральная кластеризация имеет высокую вычислительную стоимость.
-=== Метод Nyström ===
+Для полной матрицы сходства:
-Метод Nyström заменяет полную матрицу сходства низкоранговым приближением.
+:: <tex>W\in\mathbf{R}^{n\times n},</tex>
-Пусть выбрано <tex>m</tex> опорных объектов:
+требуется
-:: <tex>
+:: <tex>O(n^2)</tex>
-m\ll n.
-</tex>
-Матрица сходства приближается:
+памяти.
-:: <tex>
+Полное собственное разложение имеет сложность порядка:
-W\approx UV^T.
-</tex>
-Это позволяет вычислять спектральное представление без полного разложения матрицы размера <tex>n\times n</tex>.
+:: <tex>O(n^3).</tex>
-Преимущества:
+Поэтому для больших наборов данных применяются приближённые методы.
-* снижение требований к памяти;
+=== Метод Nyström ===
-* ускорение вычислений;
-* возможность работы с большими наборами данных.
-Недостаток:
+Метод Nyström приближает большую матрицу сходства через небольшое количество опорных точек.
-* качество зависит от выбора опорных точек.<ref name="Fowlkes2004">C. Fowlkes, S. Belongie, F. Chung, J. Malik. Spectral Grouping Using the Nyström Method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214–225, 2004.</ref>
+Пусть выбрано <tex>m\ll n</tex> объектов. Тогда матрица сходства приближается низкоранговой:
+:: <tex>W\approx UV^T.</tex>
+Вместо разложения матрицы размера <tex>n\times n</tex> решается задача меньшего размера.
+Преимущества:
+* снижение памяти;
+* ускорение вычислений;
+* возможность работы с большими выборками.
+Недостаток — качество зависит от выбора опорных точек.<ref name="Fowlkes2004">C. Fowlkes, S. Belongie, F. Chung, J. Malik. Spectral Grouping Using the Nyström Method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214–225, 2004.</ref>
 === Разреженная спектральная кластеризация ===
-Вместо полного графа используется граф ближайших соседей.
+Вместо полного графа используется разреженный граф ближайших соседей.
-Количество рёбер становится:
+Количество рёбер:
-:: <tex>
+:: <tex>|E|\ll n^2.</tex>
-|E|\ll n^2.
-</tex>
-Это позволяет применять итерационные методы поиска собственных векторов.
+Это позволяет применять итерационные методы поиска собственных векторов, например методы Ланцоша.
 Преимущества:
@@ Строка 585: / Строка 414: @@
 * возможность работы с большими графами;
 * сохранение локальной структуры.
-Ограничение — результат зависит от качества построенного разреженного графа.
 === Landmark-based методы ===
-Вместо всех объектов выбирается небольшое число представителей:
+Выбирается небольшое множество представителей данных:
-:: <tex>
+:: <tex>L=\{l_1,\ldots,l_m\}.</tex>
-L=\{l_1,\ldots,l_m\}.
-</tex>
-Строится только сходство объектов с этими представителями.
+Затем строится граф только между объектами и представителями.
-Такие методы позволяют применять спектральную кластеризацию к очень большим наборам данных, но требуют правильного выбора landmarks.
+Метод позволяет применять спектральную кластеризацию к миллионам объектов, но качество зависит от того, насколько хорошо выбраны landmarks.
-== Расширения спектральной кластеризации ==
+== Расширения метода ==
 === Многопредставленческая спектральная кластеризация ===
-Во многих задачах объекты могут быть описаны несколькими наборами признаков:
+Если объекты имеют несколько представлений:
-:: <tex>
+:: <tex>X^{(1)},X^{(2)},...,X^{(m)},</tex>
-X^{(1)},X^{(2)},\ldots,X^{(m)}.
-</tex>
-Например, объект может иметь одновременно:
+для каждого строится отдельный граф.
-* текстовое представление;
+Затем графы объединяются:
-* визуальные признаки;
-* биологические характеристики;
-* сетевую информацию.
-Для каждого представления строится собственный граф сходства:
+:: <tex>W=\sum_i\alpha_iW_i.</tex>
-:: <tex>
+Такой подход применяется, например, при объединении:
-W^{(1)},W^{(2)},\ldots,W^{(m)}.
-</tex>
-Простейший вариант объединения:
+* текстовых признаков;
+* изображений;
-:: <tex>
+* биологических измерений.
-W=\sum_{i=1}^{m}\alpha_iW^{(i)},
-</tex>
-где:
-:: <tex>
-\alpha_i\geq0,\qquad \sum_i\alpha_i=1.
-</tex>
-Более сложные методы совместно оптимизируют несколько представлений и учитывают их согласованность.
-Преимущество многопредставленческих методов заключается в использовании дополнительной информации.
-Ограничение состоит в том, что различные представления могут содержать противоречивую структуру, поэтому простое объединение графов не всегда улучшает качество.
+Основная проблема — определить оптимальные веса различных представлений.
 === Робастная спектральная кластеризация ===
-Классическая спектральная кластеризация чувствительна к ошибкам в матрице сходства.
+Классический метод чувствителен к ошибочным рёбрам.
-Пусть наблюдаемая матрица:
+Робастные варианты учитывают:
-:: <tex>
+* шум в матрице сходства;
-W=W_0+E,
+* выбросы;
-</tex>
+* неправильные связи графа.
-где:
+Обычно вводится дополнительная модель ошибок:
-* <tex>W_0</tex> — истинная структура графа;
-* <tex>E</tex> — шум или ошибки.
-Робастные методы пытаются восстановить устойчивое представление графа перед выполнением кластеризации.
-Используются:
-* удаление выбросов;
+:: <tex>W=W_0+E,</tex>
-* регуляризация степеней;
-* устойчивые функции сходства;
-* модели разреженных ошибок;
-* совместное обучение графа и кластеров.
-Такие методы особенно важны для реальных сетей, где часть рёбер может быть случайной или ошибочной.
+где <tex>W_0</tex> — истинная структура, а <tex>E</tex> — шум.
+Цель состоит в восстановлении устойчивого графа перед кластеризацией.
 === Глубокая спектральная кластеризация ===
@@ Строка 677: / Строка 471: @@
 Вместо явного вычисления собственных векторов обучается отображение:
-:: <tex>
+:: <tex>f_\theta(x):\mathbf{R}^d\rightarrow\mathbf{R}^K.</tex>
-f_\theta(x):\mathbb R^d\rightarrow\mathbb R^K.
-</tex>
-Цель обучения — получить представление, близкое к спектральному вложению.
+Сеть обучается так, чтобы её выходы приближали спектральное вложение.
 Преимущества:
-* возможность обработки больших наборов данных;
+* масштабируемость;
-* работа с новыми объектами;
+* возможность работы с новыми объектами;
 * использование сложных признаковых представлений.
 Недостатки:
-* необходимость обучения;
+* сложность обучения;
-* зависимость от архитектуры сети;
+* зависимость от архитектуры;
 * отсутствие точного совпадения с классическим спектральным решением.
-Примером является SpectralNet, где нейронная сеть обучается приближать спектральное вложение.<ref name="SpectralNet2018">U. Shaham, K. Stanton, H. Li, B. Nadler, R. Basri, Y. Kluger. SpectralNet: Spectral Clustering Using Deep Neural Networks. International Conference on Learning Representations, 2018.</ref>
+Пример такого подхода — SpectralNet.<ref name="SpectralNet2018">U. Shaham et al. SpectralNet: Spectral Clustering Using Deep Neural Networks. International Conference on Learning Representations, 2018.</ref>
 == Применения ==
@@ Строка 702: / Строка 493: @@
 === Сегментация изображений ===
-Одно из наиболее известных применений спектральной кластеризации — сегментация изображений.
+Одно из первых практических применений спектральной кластеризации — разделение изображения на области.
-Вершинами графа являются пиксели или суперпиксели, а веса отражают:
+Вершинами графа являются пиксели или суперпиксели.
+Вес учитывает:
 * сходство цвета;
-* близость положения;
+* близость координат;
-* сходство текстуры.
+* текстурные признаки.
 Например:
-:: <tex>
+:: <tex>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).</tex>
-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),
-</tex>
-где:
+Метод Normalized Cut стал одним из классических подходов к компьютерной сегментации.<ref name="ShiMalik2000"/>
-* <tex>I_i</tex> — цветовые характеристики;
+=== Анализ социальных сетей ===
-* <tex>p_i</tex> — координаты пикселя.
-Normalized Cut стал одним из классических методов сегментации изображений.<ref name="ShiMalik2000"/>
+В социальных графах вершины представляют пользователей, а рёбра — связи между ними.
+Спектральные методы позволяют находить:
-=== Анализ социальных и информационных сетей ===
+* сообщества;
+* группы пользователей;
-В сетях:
+* скрытую структуру сети.
-* вершины соответствуют пользователям или объектам;
-* рёбра отражают взаимодействия.
-Спектральная кластеризация применяется для поиска:
-* сообществ;
-* групп пользователей;
-* скрытой структуры сети.
-Метод особенно эффективен, если связи внутри групп сильнее связей между ними.
+Они особенно эффективны, когда связи внутри сообществ значительно сильнее связей между ними.
 === Текстовые данные ===
@@ Строка 752: / Строка 528: @@
 * веса — сходство текстовых представлений.
-В качестве признаков используются:
+Используются:
 * TF-IDF;
 * эмбеддинги слов;
-* представления трансформеров.
+* трансформерные представления.
-Спектральная кластеризация позволяет выделять тематические группы документов без заранее заданной модели распределения текстов.
+Спектральная кластеризация позволяет находить тематические группы документов.
 === Биоинформатика ===
-В биоинформатике метод применяется для:
+Применения:
-* анализа экспрессии генов;
-* поиска групп клеток;
-* анализа биологических сетей;
-* исследования взаимодействий белков.
-Особенно полезна возможность учитывать графовую структуру взаимодействий между объектами.
+* кластеризация профилей экспрессии генов;
+* анализ белковых сетей;
+* поиск групп клеток.
+Особенно полезна способность работать с графами взаимодействий.
 === Рекомендательные системы ===
-Пользователей и объекты можно представить как двудольный граф:
+Пользователи и объекты можно представить двудольным графом.
-* одна группа вершин — пользователи;
-* другая — товары или услуги;
-* рёбра — взаимодействия.
 Спектральные методы применяются для:
-* сегментации пользователей;
+* группировки пользователей;
-* поиска похожих объектов;
+* поиска похожих товаров;
-* анализа структуры предпочтений.
+* анализа структуры взаимодействий.
-=== Графовые данные ===
-Если данные уже представлены графом, спектральная кластеризация является естественным методом анализа.
-Примеры:
-* графы цитирования;
-* транспортные сети;
-* молекулярные графы;
-* графы знаний;
-* сети взаимодействий.
 == Сравнение с другими методами ==
@@ Строка 805: / Строка 560: @@
 === k-means ===
-[[k-means]] минимизирует расстояние объектов до центров кластеров:
+[[k-means]] быстр и хорошо масштабируется, но предпочитает компактные кластеры, близкие к сферическим. Спектральная кластеризация предпочтительнее для колец, дуг, многообразий и данных с естественной графовой структурой.
-:: <tex>
-J=
-\sum_{i=1}^{K}
-\sum_{x\in C_i}
-\|x-\mu_i\|^2.
-</tex>
-Преимущества:
-* высокая скорость;
-* простота;
-* хорошая масштабируемость.
-Недостатки:
-* требуется число кластеров;
-* плохо работает для кластеров сложной формы;
-* зависит от инициализации.
-Спектральная кластеризация предпочтительнее, если структура данных определяется связями, а не расстояниями до центроидов.
 === Иерархическая кластеризация ===
-Иерархические методы строят дерево кластеров.
+[[Иерархическая кластеризация]] строит дендрограмму и позволяет исследовать несколько уровней разбиения. Спектральный метод обычно выдаёт одно плоское разбиение, используя глобальную структуру графа.
-Преимущества:
+=== DBSCAN ===
-* позволяют исследовать несколько уровней структуры;
+[[DBSCAN]] ищет области высокой плотности и выделяет шум. Спектральный метод вместо плотностной достижимости ищет слабо связанные части графа. Оба подхода чувствительны к выбору локального масштаба.
-* не требуют заранее задавать число кластеров.
-Недостатки:
+=== Gaussian Mixture Models ===
-* высокая вычислительная сложность;
+Gaussian Mixture Models задают вероятностную смесь распределений и позволяют получать мягкие принадлежности. Спектральная кластеризация не требует предположения о гауссовой форме компонент, но не даёт вероятностной интерпретации меток.
-* решения ранних этапов трудно исправить.
-Спектральная кластеризация использует глобальную информацию о графе.
+=== Mean Shift ===
+Mean Shift ищет моды оценки плотности и не требует заранее задавать число кластеров. Его результат чувствителен к ширине окна, а вычислительная стоимость высока на больших выборках.
-=== DBSCAN ===
+=== Affinity Propagation ===
-[[DBSCAN]] основан на плотности данных.
+Affinity Propagation выбирает реальные объекты в качестве представителей кластеров и передаёт сообщения между парами объектов. В плотной реализации он, как и классическая спектральная кластеризация, требует квадратичной памяти.
-Преимущества:
+== Отличия от близких методов ==
-* обнаружение кластеров произвольной формы;
+=== Спектральное разбиение графов ===
-* выделение шума.
-Недостатки:
+Спектральное разбиение графов делит уже заданный граф, часто по знаку вектора Фидлера. Спектральная кластеризация дополнительно включает построение графа из объектов, выбор функции сходства, многомерное вложение и округление методом [[k-means]].
-* чувствительность к параметрам плотности;
+=== Laplacian Eigenmaps ===
-* проблемы при различной плотности кластеров.
-Спектральный метод использует структуру графа, а не только локальную плотность.
+Laplacian Eigenmaps использует собственные векторы лапласиана для нелинейного [[Снижение размерности|снижения размерности]]. Целью является сохранение локальной геометрии, а не обязательное получение кластерных меток.<ref name="Belkin2003">M. Belkin, P. Niyogi. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6):1373–1396, 2003.</ref>
+=== Diffusion Maps ===
-=== Gaussian Mixture Models ===
+Diffusion Maps строит координаты по собственным векторам марковского оператора и учитывает многошаговую диффузию. Метод предназначен прежде всего для анализа геометрии и диффузионных расстояний.<ref name="Coifman2006">R. R. Coifman, S. Lafon. Diffusion Maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.</ref>
-Gaussian Mixture Models предполагают:
+=== Графовые нейронные сети ===
-:: <tex>
+[[Графовые нейронные сети]] обучают параметрические преобразования признаков с использованием рёбер графа. Использование лапласиана в выводе графовой свёртки не делает модель алгоритмом спектральной кластеризации.
-p(x)=
-\sum_{k=1}^{K}
-\pi_kN(x|\mu_k,\Sigma_k).
-</tex>
-Преимущества:
+== Преимущества и ограничения ==
-* вероятностная интерпретация;
+Преимущества метода:
-* оценка степени принадлежности.
-Недостатки:
+* обнаружение невыпуклых и линейно неразделимых групп;
+* использование произвольных предметных мер сходства;
+* естественная работа с графовыми данными;
+* формальная связь с RatioCut и Normalized Cut.
-* необходимость предполагать форму распределений;
+Основные ограничения:
-* локальные оптимумы EM-алгоритма.
-Спектральная кластеризация не требует конкретной вероятностной модели.
+* квадратичная память для плотной матрицы сходства;
+* высокая стоимость вычисления собственных векторов;
+* необходимость выбирать граф, масштаб и число кластеров;
+* чувствительность к выбросам и ошибочным рёбрам;
+* отсутствие естественного точного продолжения на новые объекты.
+== Типичные ошибки ==
-=== Mean Shift ===
+* использование нестандартизованных признаков при евклидовой метрике;
+* слишком малое или слишком большое число соседей;
+* игнорирование изолированных вершин;
+* выбор собственных векторов не с того края спектра;
+* пропуск построчной нормировки в алгоритме Нга — Джордана — Вайса;
+* единственный запуск [[k-means]];
+* подбор параметров по тестовым меткам;
+* интерпретация любого спектрального зазора как доказательства кластерной структуры.
-Mean Shift ищет максимумы оценки плотности.
+== Когда метод предпочтителен ==
-Преимущества:
+Спектральная кластеризация особенно полезна, когда объекты естественно образуют граф, кластеры имеют сложную форму, важна связность по цепочкам локальных соседей и существует содержательная функция сходства. Метод обычно не является первым выбором для миллионов объектов без специальных приближений, при частом добавлении новых данных или когда кластеры хорошо описываются центроидами.
-* число кластеров определяется автоматически;
+== См. также ==
-* подходит для сложных форм.
-Недостатки:
+* [[Кластеризация]]
+* [[Обучение без учителя]]
+* [[Лапласиан графа]]
+* [[Матрица смежности]]
+* [[Собственные значения]]
+* [[Собственные векторы]]
+* [[k-means]]
+* [[Иерархическая кластеризация]]
+* [[DBSCAN]]
+* [[Снижение размерности]]
+* [[Графовые нейронные сети]]
-* высокая вычислительная стоимость;
+== Литература ==
-* зависимость от ширины окна.
+<references/>
-=== Affinity Propagation ===
+* {{книга |автор=Chung F. R. K. |заглавие=Spectral Graph Theory |издательство=American Mathematical Society |год=1997 |язык=en}}
+* {{статья |автор=von Luxburg U. |заглавие=A Tutorial on Spectral Clustering |издание=Statistics and Computing |год=2007 |том=17 |номер=4 |страницы=395—416 |doi=10.1007/s11222-007-9033-z |язык=en}}
-Affinity Propagation выбирает представителей кластеров через передачу сообщений между объектами.
+* {{статья |автор=Shi J., Malik J. |заглавие=Normalized Cuts and Image Segmentation |издание=IEEE Transactions on Pattern Analysis and Machine Intelligence |год=2000 |том=22 |номер=8 |страницы=888—905 |doi=10.1109/34.868688 |язык=en}}
+* {{статья |автор=Ng A. Y., Jordan M. I., Weiss Y. |заглавие=On Spectral Clustering: Analysis and an Algorithm |издание=Advances in Neural Information Processing Systems 14 |год=2002 |страницы=849—856 |язык=en}}
-Преимущества:
+* {{статья |автор=Zelnik-Manor L., Perona P. |заглавие=Self-Tuning Spectral Clustering |издание=Advances in Neural Information Processing Systems 17 |год=2004 |язык=en}}
+* {{статья |автор=Fowlkes C., Belongie S., Chung F., Malik J. |заглавие=Spectral Grouping Using the Nyström Method |издание=IEEE Transactions on Pattern Analysis and Machine Intelligence |год=2004 |том=26 |номер=2 |страницы=214—225 |doi=10.1109/TPAMI.2004.1262185 |язык=en}}
-* не требует заранее задавать число кластеров;
+* {{статья |автор=Belkin M., Niyogi P. |заглавие=Laplacian Eigenmaps for Dimensionality Reduction and Data Representation |издание=Neural Computation |год=2003 |том=15 |номер=6 |страницы=1373—1396 |doi=10.1162/089976603321780317 |язык=en}}
-* центры являются реальными объектами.
+* {{статья |автор=Coifman R. R., Lafon S. |заглавие=Diffusion Maps |издание=Applied and Computational Harmonic Analysis |год=2006 |том=21 |номер=1 |страницы=5—30 |doi=10.1016/j.acha.2006.04.006 |язык=en}}
+* {{статья |автор=Shaham U., Stanton K., Li H., Nadler B., Basri R., Kluger Y. |заглавие=SpectralNet: Spectral Clustering Using Deep Neural Networks |издание=International Conference on Learning Representations |год=2018 |язык=en}}
-Недостатки:
-* квадратичная память;
+[[Категория:Кластеризация]]
-* ограниченная масштабируемость.
+[[Категория:Обучение без учителя]]
+[[Категория:Теория графов]]
+[[Категория:Машинное обучение]]
+[[Категория:Энциклопедия анализа данных]]
+[[Категория:Спектральные методы]]

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

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

Версия 11:50, 19 июля 2026

Содержание

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

Построение графа сходства

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

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

ε-граф

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

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

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

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

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

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

Связь с RatioCut и Normalized Cut

Разрез графа

RatioCut

Normalized Cut

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

Базовый алгоритм

Псевдокод

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

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

Выбор числа соседей

Выбор параметра ядра

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

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

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

Масштабируемая спектральная кластеризация

Метод Nyström

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

Landmark-based методы

Расширения метода

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

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

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

Применения

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

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

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

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

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

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

k-means

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

DBSCAN

Gaussian Mixture Models

Mean Shift

Affinity Propagation

Отличия от близких методов

Спектральное разбиение графов

Laplacian Eigenmaps

Diffusion Maps

Графовые нейронные сети

Преимущества и ограничения

Типичные ошибки

Когда метод предпочтителен

См. также

Литература

Просмотры

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

Навигация

Поиск

Инструменты