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

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

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

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

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

Основная идея метода заключается в построении графа, вершины которого соответствуют объектам, а веса рёбер отражают их сходство. Затем вычисляются несколько собственных векторов лапласиана графа. Полученное низкоразмерное представление объектов кластеризуется стандартными методами, чаще всего 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://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 и проверена участником [[Участник:...|...]].}}
+'''Спектральная кластеризация''' — семейство методов [[Кластеризация|кластеризации]], основанных на представлении данных в виде графа сходства и анализе спектральных свойств соответствующего [[Лапласиан графа|лапласиана]]. В отличие от методов, работающих непосредственно с координатами объектов, спектральная кластеризация использует структуру связей между объектами и позволяет обнаруживать кластеры сложной формы.
-{{TOCright}}
+Основная идея метода заключается в построении графа, вершины которого соответствуют объектам, а веса рёбер отражают их сходство. Затем вычисляются несколько собственных векторов лапласиана графа. Полученное низкоразмерное представление объектов кластеризуется стандартными методами, чаще всего [[k-means]].
-'''Спектральная кластеризация''' — семейство методов [[Кластеризация|кластеризации]], основанных на представлении данных в виде взвешенного графа и анализе спектра его [[Лапласиан графа|лапласиана]]. В отличие от методов, работающих непосредственно в исходном пространстве признаков, спектральная кластеризация использует структуру связей между объектами и позволяет находить кластеры сложной формы, которые могут быть неразделимы линейными границами.
+Спектральная кластеризация занимает промежуточное положение между методами машинного обучения и теорией графов. Она связана с задачами разбиения графов, случайными блужданиями, снижением размерности и методами анализа сетей.<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,\ldots,x_n\}, \qquad x_i\in\mathbb R^d.</tex>
+:: <tex>X=\{x_1,x_2,\ldots,x_n\}, \qquad x_i\in\mathbb 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>w_{ij}</tex> показывает, насколько объекты <tex>x_i</tex> и <tex>x_j</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>w_{ij}>0,\qquad i\neq j.</tex>
-Часто используется гауссово ядро:
+Чаще всего используется гауссово ядро:
-:: <tex>w_{ij}=\exp\left(-\frac{\|x_i-x_j\|^2}{2\sigma^2}\right).</tex>
+:: <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>(i,j)\in E \Longleftrightarrow x_j\in kNN(x_i).</tex>
+Для <tex>k</tex>-NN графа:
-После построения граф обычно симметризуется:
+:: <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
+\Longleftrightarrow
+\|x_i-x_j\|\leq\varepsilon.
+</tex>
+Преимущество такого подхода — простая геометрическая интерпретация.
-Недостаток метода — необходимость правильно выбрать параметр <tex>\varepsilon</tex>. Малое значение может привести к разрыву графа, а большое — к объединению разных кластеров.
+Недостаток — необходимость выбора параметра <tex>\varepsilon</tex>. Если он слишком мал, граф может стать несвязным. Если слишком велик, различные кластеры могут соединиться.
-== Матрица смежности и матрица степеней ==
+== Матрица смежности ==
 Матрица весов
-:: <tex>W=(w_{ij})</tex>
+:: <tex>
+W=(w_{ij})
+</tex>
 называется матрицей смежности или матрицей сходства.
@@ Строка 84: / Строка 127: @@
 Для невзвешенного графа:
-:: <tex>w_{ij}=
+:: <tex>
+w_{ij}=
 \begin{cases}
 ,&(i,j)\in E,\\
 ,&(i,j)\notin E.
-\end{cases}</tex>
+\end{cases}
+</tex>
-Степень вершины определяется как
+Для взвешенного графа элементы матрицы принимают значения, характеризующие силу связи.
-:: <tex>d_i=\sum_j w_{ij}.</tex>
+Обычно предполагается, что граф неориентированный:
-Матрица степеней:
+:: <tex>w_{ij}=w_{ji}.</tex>
-:: <tex>D=
+Это условие позволяет использовать свойства симметричных матриц и стандартную теорию собственных значений.
+== Матрица степеней ==
+Степенью вершины называется сумма весов всех исходящих рёбер:
+:: <tex>
+d_i=\sum_{j=1}^{n}w_{ij}.
+</tex>
+На основе степеней строится диагональная матрица:
+:: <tex>
+D=
 \begin{pmatrix}
 d_1&0&\dots&0\\
@@ Строка 105: / Строка 163: @@
 </tex>
-Степень показывает общую силу связи вершины с остальным графом.
+Матрица степеней играет важную роль в нормализованных вариантах спектральной кластеризации.
+Если вершина имеет большую степень, это означает, что она сильно связана с большим числом других объектов.
 == Лапласианы графа ==
+Лапласиан графа является центральным объектом спектральной кластеризации.
 === Ненормализованный лапласиан ===
-Классический лапласиан определяется как
+Классический лапласиан определяется как:
-:: <tex>L=D-W.</tex>
+:: <tex>
+L=D-W.
+</tex>
-Он обладает важным свойством:
+Для любого вектора <tex>f</tex> выполняется:
-:: <tex>x^TLx=\frac12\sum_{i,j}w_{ij}(x_i-x_j)^2.</tex>
+:: <tex>
+f^TLf=
+\frac12
+\sum_{i,j}
+w_{ij}(f_i-f_j)^2.
+</tex>
-Следовательно, если две вершины сильно связаны, то значение соответствующих координат вектора должно быть близким.
+Это выражение показывает, что лапласиан минимизирует различия между сильно связанными вершинами.
-Лапласиан является симметричной положительно полуопределённой матрицей. Его минимальное собственное значение равно нулю:
+Если два объекта имеют большой вес связи, то соответствующие значения вектора <tex>f</tex> должны быть близкими.
-:: <tex>\lambda_1=0.</tex>
+Основные свойства:
-Количество собственных значений, равных нулю, совпадает с количеством компонент связности графа.<ref name="Chung1997">F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.</ref>
+* <tex>L</tex> симметрична;
+* собственные значения неотрицательны;
+* минимальное собственное значение равно нулю.
-=== Нормализованный лапласиан ===
+Количество нулевых собственных значений равно числу компонент связности графа.<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>L_{rw}=D^{-1}L.</tex>
+:: <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>0=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n.</tex>
+:: <tex>
+Lu=\lambda u.
+</tex>
-Собственные векторы соответствуют направлениям, в которых структура графа изменяется медленно.
+где:
-Если граф состоит из нескольких почти независимых частей, то первые собственные векторы приближают индикаторы этих групп.
+* <tex>\lambda</tex> — собственное значение;
+* <tex>u</tex> — собственный вектор.
-В идеальном случае, когда граф имеет ровно <tex>K</tex> компонент связности:
+Собственные значения упорядочиваются:
-:: <tex>\lambda_1=\lambda_2=\dots=\lambda_K=0.</tex>
+:: <tex>
+=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n.
+</tex>
-Поэтому первые <tex>K</tex> собственных векторов содержат информацию о кластерной структуре.
+Малые собственные значения соответствуют направлениям, в которых структура графа изменяется медленно.
-Разность между соседними собственными значениями:
+Если граф имеет несколько почти независимых компонент, первые собственные векторы приближают индикаторы этих компонент.
-:: <tex>\lambda_{K+1}-\lambda_K</tex>
+В идеальном случае граф из <tex>K</tex> компонент имеет:
-называется спектральным зазором и часто используется для выбора числа кластеров.
+:: <tex>
+\lambda_1=\lambda_2=\dots=\lambda_K=0.
+</tex>
+Поэтому первые <tex>K</tex> собственных векторов содержат информацию о структуре кластеров.
 == Спектральное вложение ==
-Пусть найдены собственные векторы
+Пусть найдены собственные векторы:
-:: <tex>u_1,\ldots,u_K.</tex>
+:: <tex>
+u_1,u_2,\ldots,u_K.
+</tex>
 Из них формируется матрица:
-:: <tex>U=[u_1,\ldots,u_K].</tex>
+:: <tex>
+U=[u_1,u_2,\ldots,u_K].
+</tex>
-Каждый объект заменяется строкой этой матрицы:
+Каждый объект заменяется строкой:
-:: <tex>y_i=U_{i,:}.</tex>
+:: <tex>
+y_i=U_{i,:}.
+</tex>
-Таким образом исходное пространство высокой размерности заменяется новым пространством размерности <tex>K</tex>.
+Таким образом исходные данные переводятся в новое пространство размерности <tex>K</tex>.
-После этого применяется обычная кластеризация:
+После этого выполняется обычная кластеризация:
-:: <tex>\{y_1,\ldots,y_n\}\rightarrow C_1,\ldots,C_K.</tex>
+:: <tex>
+y_1,y_2,\ldots,y_n
+\rightarrow
+C_1,C_2,\ldots,C_K.
+</tex>
-Чаще всего используется [[k-means]].
+Чаще всего применяется алгоритм [[k-means]].
-Для нормализованной версии Нга — Джордана — Вайса строки дополнительно нормируются:
+Для нормализованной версии Нга — Джордана — Вайса выполняется дополнительная нормировка строк:
-:: <tex>y_i=
+:: <tex>
-\frac{U_{i,:}}{\|U_{i,:}\|_2}.
+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>cut(A,B)=
+:: <tex>
-\sum_{i\in A}\sum_{j\in B}w_{ij}.
+cut(A,B)=
+\sum_{i\in A}
+\sum_{j\in B}
+w_{ij}.
 </tex>
-Минимизация только этого выражения приводит к выделению маленьких групп или одиночных вершин.
+Минимизация только этого критерия приводит к вырожденному решению: можно отделить одну вершину или небольшую группу вершин.
+Поэтому используются нормированные критерии, учитывающие размер кластеров.
 === RatioCut ===
-Критерий RatioCut учитывает размер кластеров:
+Критерий RatioCut определяется как:
 :: <tex>
 RatioCut(A_1,\ldots,A_K)=
 \sum_{i=1}^{K}
-\frac{cut(A_i,\bar A_i)}
+\frac{cut(A_i,\overline{A_i})}
 {|A_i|}.
 </tex>
-Он стремится минимизировать связи между кластерами и одновременно избегать слишком маленьких групп.
+Он нормирует значение разреза количеством вершин в кластере.
-Спектральная релаксация RatioCut приводит к поиску собственных векторов ненормализованного лапласиана.
+Спектральная релаксация этой задачи приводит к поиску собственных векторов ненормализованного лапласиана:
+:: <tex>
+L=D-W.
+</tex>
 === Normalized Cut ===
-Normalized Cut использует объём множества:
+Вместо количества вершин используется объём:
 :: <tex>
@@ Строка 235: / Строка 367: @@
 </tex>
-Критерий:
+Критерий Normalized Cut:
 :: <tex>
 Ncut(A_1,\ldots,A_K)=
 \sum_{i=1}^{K}
-\frac{cut(A_i,\bar A_i)}
+\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=\{x_1,\ldots,x_n\}</tex>;
+* объекты <tex>X</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>
-'''Вход:''' данные X, число кластеров K.
+# Найти <tex>K</tex> собственных векторов, соответствующих минимальным собственным значениям.
+# Сформировать матрицу вложения:
-'''Выход:''' метки кластеров.
+:: <tex>
+U=[u_1,\ldots,u_K].
+</tex>
-. Построить граф сходства W.
+# Выполнить [[k-means]] над строками матрицы <tex>U</tex>.
-. Вычислить степени вершин D.
+# Назначить исходным объектам найденные метки.
-. Построить лапласиан L.
-. Найти K минимальных собственных векторов:
-       L u_i = λ_i u_i
-. Сформировать матрицу U.
-. Нормировать строки U (для нормализованного варианта).
-. Выполнить k-means по строкам U.
-. Вернуть полученные группы.
-== Выбор параметров ==
-=== Число кластеров ===
+=== Нормализованный вариант ===
-В классическом алгоритме число кластеров <tex>K</tex> задаётся заранее. Однако часто его необходимо оценивать.
+Для нормализованной версии:
-Один из распространённых подходов основан на спектральном зазоре:
+# Строится граф сходства.
+# Вычисляется:
 :: <tex>
-gap(k)=\lambda_{k+1}-\lambda_k.
+L_{sym}=I-D^{-1/2}WD^{-1/2}.
 </tex>
-Если между двумя соседними собственными значениями существует большой разрыв, это может указывать на естественное число кластеров.
+# Находятся первые <tex>K</tex> собственных векторов.
+# Формируется матрица:
-Однако спектральный зазор является только эвристикой. Большой разрыв может возникать из-за особенностей построенного графа, выбросов или неравномерной плотности данных.
+:: <tex>
+U=[u_1,\ldots,u_K].
+</tex>
-=== Выбор числа соседей ===
+# Каждая строка нормируется:
-В графах ближайших соседей параметр <tex>k</tex> определяет локальный масштаб.
+:: <tex>
+y_i=
+\frac{U_i}{\|U_i\|}.
+</tex>
-Слишком маленькое значение:
+# Выполняется [[k-means]].
-* приводит к разрывам графа;
-* создаёт искусственные компоненты связности;
-* делает результат нестабильным.
-Слишком большое значение:
+=== Псевдокод ===
-* добавляет связи между различными группами;
+ Вход: X, K
-* сглаживает границы кластеров;
-* приближает граф к полносвязному.
-На практике рекомендуется проверять устойчивость кластеров при нескольких значениях <tex>k</tex>.
+. Построить граф сходства W.
+. Вычислить D.
+. Построить лапласиан L.
+. Найти K минимальных собственных векторов.
+. Получить спектральное представление объектов.
+. При необходимости нормировать строки.
+. Выполнить k-means.
+. Вернуть метки кластеров.
+== Выбор параметров ==
+=== Число кластеров ===
-=== Выбор параметра ядра ===
+Число кластеров <tex>K</tex> является одним из главных параметров алгоритма.
-Для гауссового сходства
+Часто используется анализ спектрального зазора:
 :: <tex>
-w_{ij}=
+\Delta_k=\lambda_{k+1}-\lambda_k.
-\exp
-\left(
--\frac{\|x_i-x_j\|^2}{2\sigma^2}
-\right)
 </tex>
-параметр <tex>\sigma</tex> определяет масштаб.
+Большой разрыв может указывать на естественное число кластеров.
-Если <tex>\sigma</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.
+w_{ij}=
+\exp
+\left(
+-\frac{\|x_i-x_j\|^2}{2\sigma^2}
+\right)
 </tex>
-Он соответствует релаксации критерия RatioCut.
+параметр <tex>\sigma</tex> задаёт масштаб близости.
-Преимущества:
+При малом <tex>\sigma</tex> граф становится слишком разреженным.
-* простая математическая форма;
+При большом <tex>\sigma</tex> различия между объектами уменьшаются.
-* естественная связь с теорией графов;
-* хорошая работа при близких степенях вершин.
-Недостатки:
+Для неоднородных данных используют локальные масштабы:
-* чувствительность к различию плотностей;
-* зависимость от размеров кластеров;
-* хуже работает при сильно неоднородных данных.
-=== Нормализованный вариант ===
-Используются:
 :: <tex>
-L_{sym}=D^{-1/2}LD^{-1/2}
+w_{ij}
+=
+\exp
+\left(
+-\frac{\|x_i-x_j\|^2}
+{\sigma_i\sigma_j}
+\right).
 </tex>
-или
+=== Число собственных векторов ===
+В стандартном алгоритме число собственных векторов совпадает с числом кластеров:
 :: <tex>
-L_{rw}=D^{-1}L.
+r=K.
 </tex>
-Нормализация учитывает степень каждой вершины и уменьшает влияние крупных плотных областей.
+Использование большего количества компонент возможно, но требует дополнительного выбора и уже не является прямой релаксацией исходной задачи разбиения графа.
-Преимущества:
-* устойчивость к различным размерам кластеров;
+== Масштабируемые методы ==
-* связь со случайными блужданиями;
-* широкое применение на реальных данных.
-Именно нормализованные варианты чаще используются в современных приложениях.
+Классическая спектральная кластеризация плохо масштабируется на больших данных из-за необходимости хранить матрицу сходства.
-== Масштабируемая спектральная кластеризация ==
+Для решения этой проблемы используются приближённые методы.
-Классическая спектральная кластеризация имеет высокую вычислительную стоимость.
+=== Метод Nyström ===
-Для полной матрицы сходства:
+Метод Nyström заменяет полную матрицу сходства низкоранговым приближением.
-:: <tex>
+Пусть выбрано <tex>m</tex> опорных объектов:
-W\in\mathbb R^{n\times n},
-</tex>
-требуется
 :: <tex>
-O(n^2)
+m\ll n.
 </tex>
-памяти.
+Матрица сходства приближается:
-Полное собственное разложение имеет сложность порядка:
-:: <tex>
-O(n^3).
-</tex>
-Поэтому для больших наборов данных применяются приближённые методы.
-=== Метод Nyström ===
-Метод Nyström приближает большую матрицу сходства через небольшое количество опорных точек.
-Пусть выбрано <tex>m\ll n</tex> объектов. Тогда матрица сходства приближается низкоранговой:
 :: <tex>
@@ Строка 445: / Строка 555: @@
 </tex>
-Вместо разложения матрицы размера <tex>n\times n</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>
-Недостаток — качество зависит от выбора опорных точек.<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>
@@ Строка 465: / Строка 578: @@
 </tex>
-Это позволяет применять итерационные методы поиска собственных векторов, например методы Ланцоша.
+Это позволяет применять итерационные методы поиска собственных векторов.
 Преимущества:
@@ Строка 472: / Строка 585: @@
 * возможность работы с большими графами;
 * сохранение локальной структуры.
+Ограничение — результат зависит от качества построенного разреженного графа.
 === Landmark-based методы ===
-Выбирается небольшое множество представителей данных:
+Вместо всех объектов выбирается небольшое число представителей:
 :: <tex>
@@ Строка 481: / Строка 597: @@
 </tex>
-Затем строится граф только между объектами и представителями.
+Строится только сходство объектов с этими представителями.
-Метод позволяет применять спектральную кластеризацию к миллионам объектов, но качество зависит от того, насколько хорошо выбраны landmarks.
+Такие методы позволяют применять спектральную кластеризацию к очень большим наборам данных, но требуют правильного выбора landmarks.
-== Расширения метода ==
+== Расширения спектральной кластеризации ==
 === Многопредставленческая спектральная кластеризация ===
-Если объекты имеют несколько представлений:
+Во многих задачах объекты могут быть описаны несколькими наборами признаков:
 :: <tex>
-X^{(1)},X^{(2)},...,X^{(m)},
+X^{(1)},X^{(2)},\ldots,X^{(m)}.
 </tex>
-для каждого строится отдельный граф.
+Например, объект может иметь одновременно:
-Затем графы объединяются:
+* текстовое представление;
+* визуальные признаки;
+* биологические характеристики;
+* сетевую информацию.
+Для каждого представления строится собственный граф сходства:
 :: <tex>
-W=\sum_i\alpha_iW_i.
+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>
@@ Строка 527: / Строка 653: @@
 </tex>
-где <tex>W_0</tex> — истинная структура, а <tex>E</tex> — шум.
+где:
+* <tex>W_0</tex> — истинная структура графа;
+* <tex>E</tex> — шум или ошибки.
+Робастные методы пытаются восстановить устойчивое представление графа перед выполнением кластеризации.
+Используются:
+* удаление выбросов;
+* регуляризация степеней;
+* устойчивые функции сходства;
+* модели разреженных ошибок;
+* совместное обучение графа и кластеров.
+Такие методы особенно важны для реальных сетей, где часть рёбер может быть случайной или ошибочной.
-Цель состоит в восстановлении устойчивого графа перед кластеризацией.
 === Глубокая спектральная кластеризация ===
@@ Строка 541: / Строка 681: @@
 </tex>
-Сеть обучается так, чтобы её выходы приближали спектральное вложение.
+Цель обучения — получить представление, близкое к спектральному вложению.
 Преимущества:
-* масштабируемость;
+* возможность обработки больших наборов данных;
-* возможность работы с новыми объектами;
+* работа с новыми объектами;
 * использование сложных признаковых представлений.
 Недостатки:
-* сложность обучения;
+* необходимость обучения;
-* зависимость от архитектуры;
+* зависимость от архитектуры сети;
 * отсутствие точного совпадения с классическим спектральным решением.
-Пример такого подхода — SpectralNet.<ref name="SpectralNet2018">U. Shaham et al. SpectralNet: Spectral Clustering Using Deep Neural Networks. International Conference on Learning Representations, 2018.</ref>
+Примером является 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>
 == Применения ==
@@ Строка 561: / Строка 702: @@
 === Сегментация изображений ===
-Одно из первых практических применений спектральной кластеризации — разделение изображения на области.
+Одно из наиболее известных применений спектральной кластеризации — сегментация изображений.
-Вершинами графа являются пиксели или суперпиксели.
+Вершинами графа являются пиксели или суперпиксели, а веса отражают:
-Вес учитывает:
 * сходство цвета;
-* близость координат;
+* близость положения;
-* текстурные признаки.
+* сходство текстуры.
 Например:
 :: <tex>
-w_{ij}
+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).
+\right),
 </tex>
-Метод Normalized Cut стал одним из классических подходов к компьютерной сегментации.<ref name="ShiMalik2000"/>
+где:
-=== Анализ социальных сетей ===
+* <tex>I_i</tex> — цветовые характеристики;
+* <tex>p_i</tex> — координаты пикселя.
-В социальных графах вершины представляют пользователей, а рёбра — связи между ними.
+Normalized Cut стал одним из классических методов сегментации изображений.<ref name="ShiMalik2000"/>
-Спектральные методы позволяют находить:
-* сообщества;
+=== Анализ социальных и информационных сетей ===
-* группы пользователей;
-* скрытую структуру сети.
+В сетях:
+* вершины соответствуют пользователям или объектам;
+* рёбра отражают взаимодействия.
+Спектральная кластеризация применяется для поиска:
+* сообществ;
+* групп пользователей;
+* скрытой структуры сети.
+Метод особенно эффективен, если связи внутри групп сильнее связей между ними.
-Они особенно эффективны, когда связи внутри сообществ значительно сильнее связей между ними.
 === Текстовые данные ===
@@ Строка 604: / Строка 752: @@
 * веса — сходство текстовых представлений.
-Используются:
+В качестве признаков используются:
 * TF-IDF;
 * эмбеддинги слов;
-* трансформерные представления.
+* представления трансформеров.
+Спектральная кластеризация позволяет выделять тематические группы документов без заранее заданной модели распределения текстов.
-Спектральная кластеризация позволяет находить тематические группы документов.
 === Биоинформатика ===
-Применения:
+В биоинформатике метод применяется для:
-* кластеризация профилей экспрессии генов;
+* анализа экспрессии генов;
-* анализ белковых сетей;
+* поиска групп клеток;
-* поиск групп клеток.
+* анализа биологических сетей;
+* исследования взаимодействий белков.
+Особенно полезна возможность учитывать графовую структуру взаимодействий между объектами.
-Особенно полезна способность работать с графами взаимодействий.
 === Рекомендательные системы ===
-Пользователи и объекты можно представить двудольным графом.
+Пользователей и объекты можно представить как двудольный граф:
+* одна группа вершин — пользователи;
+* другая — товары или услуги;
+* рёбра — взаимодействия.
 Спектральные методы применяются для:
-* группировки пользователей;
+* сегментации пользователей;
-* поиска похожих товаров;
+* поиска похожих объектов;
-* анализа структуры взаимодействий.
+* анализа структуры предпочтений.
+=== Графовые данные ===
+Если данные уже представлены графом, спектральная кластеризация является естественным методом анализа.
+Примеры:
+* графы цитирования;
+* транспортные сети;
+* молекулярные графы;
+* графы знаний;
+* сети взаимодействий.
 == Сравнение с другими методами ==
-{| class="wikitable"
+=== k-means ===
-! Метод
-! Основная идея
+[[k-means]] минимизирует расстояние объектов до центров кластеров:
-! Преимущества
-! Ограничения
+:: <tex>
-|-
+J=
-| [[k-means]]
+\sum_{i=1}^{K}
-| Минимизация расстояний до центроидов
+\sum_{x\in C_i}
-| Быстрый, масштабируемый
+\|x-\mu_i\|^2.
-| Только выпуклые кластеры, нужно задать K
+</tex>
-|-
-| Иерархическая кластеризация
+Преимущества:
-| Построение дерева кластеров
-| Не требует K заранее
+* высокая скорость;
-| Высокая сложность на больших данных
+* простота;
-|-
+* хорошая масштабируемость.
-| DBSCAN
-| Поиск областей высокой плотности
+Недостатки:
-| Находит шум, кластеры произвольной формы
-| Чувствителен к параметрам плотности
+* требуется число кластеров;
-|-
+* плохо работает для кластеров сложной формы;
-| Gaussian Mixture Models
+* зависит от инициализации.
-| Вероятностная модель смеси распределений
-| Даёт вероятности принадлежности
+Спектральная кластеризация предпочтительнее, если структура данных определяется связями, а не расстояниями до центроидов.
-| Требует предположения о форме кластеров
-|-
-| Mean Shift
+=== Иерархическая кластеризация ===
-| Поиск мод плотности
-| Не требует задания числа кластеров
+Иерархические методы строят дерево кластеров.
-| Дорогой вычислительно
-|-
+Преимущества:
-| Affinity Propagation
-| Передача сообщений между объектами
+* позволяют исследовать несколько уровней структуры;
-| Выбирает реальные представители кластеров
+* не требуют заранее задавать число кластеров.
-| Квадратичная память
-|}
+Недостатки:
+* высокая вычислительная сложность;
+* решения ранних этапов трудно исправить.
+Спектральная кластеризация использует глобальную информацию о графе.
+=== DBSCAN ===
+[[DBSCAN]] основан на плотности данных.
+Преимущества:
+* обнаружение кластеров произвольной формы;
+* выделение шума.
+Недостатки:
+* чувствительность к параметрам плотности;
+* проблемы при различной плотности кластеров.
+Спектральный метод использует структуру графа, а не только локальную плотность.
+=== Gaussian Mixture Models ===
+Gaussian Mixture Models предполагают:
+:: <tex>
+p(x)=
+\sum_{k=1}^{K}
+\pi_kN(x|\mu_k,\Sigma_k).
+</tex>
+Преимущества:
+* вероятностная интерпретация;
+* оценка степени принадлежности.
+Недостатки:
+* необходимость предполагать форму распределений;
+* локальные оптимумы EM-алгоритма.
+Спектральная кластеризация не требует конкретной вероятностной модели.
+=== Mean Shift ===
+Mean Shift ищет максимумы оценки плотности.
+Преимущества:
+* число кластеров определяется автоматически;
+* подходит для сложных форм.
+Недостатки:
+* высокая вычислительная стоимость;
+* зависимость от ширины окна.
+=== Affinity Propagation ===
+Affinity Propagation выбирает представителей кластеров через передачу сообщений между объектами.
+Преимущества:
+* не требует заранее задавать число кластеров;
+* центры являются реальными объектами.
+Недостатки:
+* квадратичная память;
+* ограниченная масштабируемость.

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

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

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

Содержание

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

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

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

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

ε-граф

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

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

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

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

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

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

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

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

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

Разрез графа

RatioCut

Normalized Cut

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

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

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

Псевдокод

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

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

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

Масштаб ядра

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

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

Метод Nyström

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

Landmark-based методы

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

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

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

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

Применения

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

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

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

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

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

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

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

k-means

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

DBSCAN

Gaussian Mixture Models

Mean Shift

Affinity Propagation

Просмотры

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

Навигация

Поиск

Инструменты