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

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

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

Текущая версия

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником Valeriia Berdnikova 14:00, 19 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Спектральная кластеризация.

Содержание

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 Примечания
21 Литература

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

Основная идея метода состоит в построении графа сходства, вычислении нескольких собственных векторов соответствующего лапласиана и последующей кластеризации полученного низкоразмерного представления, обычно алгоритмом 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. — С. 1601—1608.
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 и проверена участником [[Участник:...|...]].}}
+{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Valeriia Berdnikova |Valeriia Berdnikova]] 14:00, 19 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Спектральная кластеризация]].}}
 {{TOCright}}
 '''Спектральная кластеризация''' — семейство методов [[Кластеризация|кластеризации]], основанных на представлении данных в виде взвешенного графа и анализе спектра его [[Лапласиан графа|лапласиана]]. В отличие от методов, работающих непосредственно в исходном пространстве признаков, спектральная кластеризация использует структуру связей между объектами и позволяет находить кластеры сложной формы, которые могут быть неразделимы линейными границами.
-Основная идея метода состоит в построении графа сходства, вычислении нескольких собственных векторов соответствующего лапласиана и последующей кластеризации полученного низкоразмерного представления, обычно алгоритмом [[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>
+Основная идея метода состоит в построении графа сходства, вычислении нескольких собственных векторов соответствующего лапласиана и последующей кластеризации полученного низкоразмерного представления, обычно алгоритмом [[k-means]]. Метод тесно связан с задачами разбиения графов, критериями [[Normalized Cut]] и [[RatioCut]], а также с такими направлениями, как [[Laplacian Eigenmaps]] и [[Diffusion Maps]].<ref name="Luxburg2007">{{статья |автор=von Luxburg U. |заглавие=A Tutorial on Spectral Clustering |ссылка=https://doi.org/10.1007/s11222-007-9033-z |издание=Statistics and Computing |год=2007 |том=17 |номер=4 |страницы=395—416 |doi=10.1007/s11222-007-9033-z |язык=en}}</ref>
 == Постановка задачи ==
@@ Строка 11: / Строка 11: @@
 Пусть дана выборка объектов
-:: <tex>X=\{x_1,\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> групп:
@@ Строка 57: / Строка 57: @@
 В <tex>k</tex>-NN графе вершина соединяется только с ближайшими соседями:
-:: <tex>(i,j)\in E \Longleftrightarrow x_j\in kNN(x_i).</tex>
+:: <tex>(i,j)\in E \Leftrightarrow x_j\in {\rm kNN}(x_i).</tex>
 После построения граф обычно симметризуется:
@@ Строка 70: / Строка 70: @@
 В ε-графе связь создаётся, если расстояние меньше заданного порога:
-:: <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>. Малое значение может привести к разрыву графа, а большое — к объединению разных кластеров.
@@ Строка 84: / Строка 84: @@
 Для невзвешенного графа:
-:: <tex>w_{ij}=
+:: <tex>w_{ij}= \left\{\begin{array}{ll} 1,&(i,j)\in E,\\ 0,&(i,j)\notin E. \end{array}\right.</tex>
-\begin{cases}
-,&(i,j)\in E,\\
-,&(i,j)\notin E.
-\end{cases}</tex>
 Степень вершины определяется как
@@ Строка 96: / Строка 92: @@
 Матрица степеней:
-:: <tex>D=
+:: <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>
-\begin{pmatrix}
-d_1&0&\dots&0\\
-&d_2&\dots&0\\
-\vdots&\vdots&\ddots&\vdots\\
-&0&\dots&d_n
-\end{pmatrix}.
-</tex>
 Степень показывает общую силу связи вершины с остальным графом.
@@ Строка 125: / Строка 114: @@
 :: <tex>\lambda_1=0.</tex>
-Количество собственных значений, равных нулю, совпадает с количеством компонент связности графа.<ref name="Chung1997">F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.</ref>
+Количество собственных значений, равных нулю, совпадает с количеством компонент связности графа.<ref name="Chung1997">{{книга |автор=Chung F. R. K. |заглавие=Spectral Graph Theory |ссылка=https://www.ams.org/books/cbms/092/ |место=Providence, Rhode Island |издательство=American Mathematical Society |год=1997 |isbn=978-0-8218-0315-8 |язык=en}}</ref>
 === Нормализованный лапласиан ===
@@ Строка 131: / Строка 120: @@
 Для уменьшения влияния различий в степенях вершин используют нормализованный лапласиан:
-:: <tex>L_{sym}=D^{-1/2}LD^{-1/2}
+:: <tex>L_{sym}=D^{-1/2}LD^{-1/2} =I-D^{-1/2}WD^{-1/2}.</tex>
-=I-D^{-1/2}WD^{-1/2}.</tex>
 Другой вариант:
@@ Строка 194: / Строка 182: @@
 Для нормализованной версии Нга — Джордана — Вайса строки дополнительно нормируются:
-:: <tex>y_i=
+:: <tex>y_i= \frac{U_{i,:}}{\|U_{i,:}\|_2}.</tex>
-\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>
+<ref name="Ng2002">{{статья |автор=Ng A. Y., Jordan M. I., Weiss Y. |заглавие=On Spectral Clustering: Analysis and an Algorithm |ссылка=https://proceedings.neurips.cc/paper/2001/hash/801272ee79cfde7fa5960571fee36b9b-Abstract.html |издание=Advances in Neural Information Processing Systems 14 |год=2002 |страницы=849—856 |язык=en}}</ref>
 == Связь с RatioCut и Normalized Cut ==
@@ Строка 206: / Строка 192: @@
 Для двух множеств вершин <tex>A</tex> и <tex>B</tex> определяется вес разреза:
-:: <tex>cut(A,B)=
+:: <tex>cut(A,B)= \sum_{i\in A}\sum_{j\in B}w_{ij}.</tex>
-\sum_{i\in A}\sum_{j\in B}w_{ij}.
-</tex>
 Минимизация только этого выражения приводит к выделению маленьких групп или одиночных вершин.
@@ Строка 216: / Строка 200: @@
 Критерий 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,\bar A_i)}
-{|A_i|}.
-</tex>
 Он стремится минимизировать связи между кластерами и одновременно избегать слишком маленьких групп.
@@ Строка 231: / Строка 210: @@
 Normalized Cut использует объём множества:
-:: <tex>
+:: <tex>vol(A)=\sum_{i\in A}d_i.</tex>
-vol(A)=\sum_{i\in A}d_i.
-</tex>
 Критерий:
-:: <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,\bar A_i)}
-{vol(A_i)}.
-</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">{{статья |автор=Shi J., Malik J. |заглавие=Normalized Cuts and Image Segmentation |ссылка=https://doi.org/10.1109/34.868688 |издание=IEEE Transactions on Pattern Analysis and Machine Intelligence |год=2000 |том=22 |номер=8 |страницы=888—905 |doi=10.1109/34.868688 |язык=en}}</ref>
 == Алгоритм спектральной кластеризации ==
@@ Строка 299: / Строка 271: @@
 Один из распространённых подходов основан на спектральном зазоре:
-:: <tex>
+:: <tex>gap(k)=\lambda_{k+1}-\lambda_k.</tex>
-gap(k)=\lambda_{k+1}-\lambda_k.
-</tex>
 Если между двумя соседними собственными значениями существует большой разрыв, это может указывать на естественное число кластеров.
@@ Строка 329: / Строка 299: @@
 Для гауссового сходства
-:: <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> определяет масштаб.
@@ Строка 351: / Строка 315: @@
 Для неоднородных данных применяют локальные масштабы:
-:: <tex>
+:: <tex>w_{ij}= \exp \left( -\frac{\|x_i-x_j\|^2}{\sigma_i\sigma_j} \right).</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>
+Такой подход называется самонастраиваемой спектральной кластеризацией.<ref name="Zelnik2004">{{статья |автор=Zelnik-Manor L., Perona P. |заглавие=Self-Tuning Spectral Clustering |ссылка=https://proceedings.neurips.cc/paper/2004/hash/40173ea48d9567f1f393b20c855bb40b-Abstract.html |издание=Advances in Neural Information Processing Systems 17 |год=2004 |страницы=1601—1608 |язык=en}}</ref>
 == Ненормализованная и нормализованная спектральная кластеризация ==
@@ Строка 367: / Строка 325: @@
 Используется лапласиан
-:: <tex>
+:: <tex>L=D-W.</tex>
-L=D-W.
-</tex>
 Он соответствует релаксации критерия RatioCut.
@@ Строка 389: / Строка 345: @@
 Используются:
-:: <tex>
+:: <tex>L_{sym}=D^{-1/2}LD^{-1/2}</tex>
-L_{sym}=D^{-1/2}LD^{-1/2}
-</tex>
 или
-:: <tex>
+:: <tex>L_{rw}=D^{-1}L.</tex>
-L_{rw}=D^{-1}L.
-</tex>
 Нормализация учитывает степень каждой вершины и уменьшает влияние крупных плотных областей.
@@ Строка 415: / Строка 367: @@
 Для полной матрицы сходства:
-:: <tex>
+:: <tex>W\in\mathbf{R}^{n\times n},</tex>
-W\in\mathbb R^{n\times n},
-</tex>
 требуется
-:: <tex>
+:: <tex>O(n^2)</tex>
-O(n^2)
-</tex>
 памяти.
@@ Строка 429: / Строка 377: @@
 Полное собственное разложение имеет сложность порядка:
-:: <tex>
+:: <tex>O(n^3).</tex>
-O(n^3).
-</tex>
 Поэтому для больших наборов данных применяются приближённые методы.
@@ Строка 441: / Строка 387: @@
 Пусть выбрано <tex>m\ll n</tex> объектов. Тогда матрица сходства приближается низкоранговой:
-:: <tex>
+:: <tex>W\approx UV^T.</tex>
-W\approx UV^T.
-</tex>
 Вместо разложения матрицы размера <tex>n\times n</tex> решается задача меньшего размера.
@@ Строка 453: / Строка 397: @@
 * возможность работы с большими выборками.
-Недостаток — качество зависит от выбора опорных точек.<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">{{статья |автор=Fowlkes C., Belongie S., Chung F., Malik J. |заглавие=Spectral Grouping Using the Nyström Method |ссылка=https://doi.org/10.1109/TPAMI.2004.1262185 |издание=IEEE Transactions on Pattern Analysis and Machine Intelligence |год=2004 |том=26 |номер=2 |страницы=214—225 |doi=10.1109/TPAMI.2004.1262185 |язык=en}}</ref>
 === Разреженная спектральная кластеризация ===
@@ Строка 461: / Строка 405: @@
 Количество рёбер:
-:: <tex>
+:: <tex>|E|\ll n^2.</tex>
-|E|\ll n^2.
-</tex>
 Это позволяет применять итерационные методы поиска собственных векторов, например методы Ланцоша.
@@ Строка 477: / Строка 419: @@
 Выбирается небольшое множество представителей данных:
-:: <tex>
+:: <tex>L=\{l_1,\ldots,l_m\}.</tex>
-L=\{l_1,\ldots,l_m\}.
-</tex>
 Затем строится граф только между объектами и представителями.
@@ Строка 491: / Строка 431: @@
 Если объекты имеют несколько представлений:
-:: <tex>
+:: <tex>X^{(1)},X^{(2)},...,X^{(m)},</tex>
-X^{(1)},X^{(2)},...,X^{(m)},
-</tex>
 для каждого строится отдельный граф.
@@ Строка 499: / Строка 437: @@
 Затем графы объединяются:
-:: <tex>
+:: <tex>W=\sum_i\alpha_iW_i.</tex>
-W=\sum_i\alpha_iW_i.
-</tex>
 Такой подход применяется, например, при объединении:
@@ Строка 523: / Строка 459: @@
 Обычно вводится дополнительная модель ошибок:
-:: <tex>
+:: <tex>W=W_0+E,</tex>
-W=W_0+E,
-</tex>
 где <tex>W_0</tex> — истинная структура, а <tex>E</tex> — шум.
@@ Строка 537: / Строка 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>
 Сеть обучается так, чтобы её выходы приближали спектральное вложение.
@@ Строка 555: / Строка 487: @@
 * отсутствие точного совпадения с классическим спектральным решением.
-Пример такого подхода — 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">{{статья |автор=Shaham U., Stanton K., Li H., Nadler B., Basri R., Kluger Y. |заглавие=SpectralNet: Spectral Clustering Using Deep Neural Networks |ссылка=https://openreview.net/forum?id=HJ_aoCyRZ |издание=International Conference on Learning Representations |год=2018 |язык=en}}</ref>
 == Применения ==
@@ Строка 573: / Строка 505: @@
 Например:
-:: <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"/>
@@ Строка 634: / Строка 558: @@
 == Сравнение с другими методами ==
-{| class="wikitable"
+=== k-means ===
-! Метод
-! Основная идея
+[[k-means]] быстр и хорошо масштабируется, но предпочитает компактные кластеры, близкие к сферическим. Спектральная кластеризация предпочтительнее для колец, дуг, многообразий и данных с естественной графовой структурой.
-! Преимущества
-! Ограничения
+=== Иерархическая кластеризация ===
-|-
-| [[k-means]]
+[[Иерархическая кластеризация]] строит дендрограмму и позволяет исследовать несколько уровней разбиения. Спектральный метод обычно выдаёт одно плоское разбиение, используя глобальную структуру графа.
-| Минимизация расстояний до центроидов
-| Быстрый, масштабируемый
+=== DBSCAN ===
-| Только выпуклые кластеры, нужно задать K
-|-
+[[DBSCAN]] ищет области высокой плотности и выделяет шум. Спектральный метод вместо плотностной достижимости ищет слабо связанные части графа. Оба подхода чувствительны к выбору локального масштаба.
-| Иерархическая кластеризация
-| Построение дерева кластеров
+=== Gaussian Mixture Models ===
-| Не требует K заранее
-| Высокая сложность на больших данных
+Gaussian Mixture Models задают вероятностную смесь распределений и позволяют получать мягкие принадлежности. Спектральная кластеризация не требует предположения о гауссовой форме компонент, но не даёт вероятностной интерпретации меток.
-|-
-| DBSCAN
+=== Mean Shift ===
-| Поиск областей высокой плотности
-| Находит шум, кластеры произвольной формы
+Mean Shift ищет моды оценки плотности и не требует заранее задавать число кластеров. Его результат чувствителен к ширине окна, а вычислительная стоимость высока на больших выборках.
-| Чувствителен к параметрам плотности
-|-
+=== Affinity Propagation ===
-| Gaussian Mixture Models
-| Вероятностная модель смеси распределений
+Affinity Propagation выбирает реальные объекты в качестве представителей кластеров и передаёт сообщения между парами объектов. В плотной реализации он, как и классическая спектральная кластеризация, требует квадратичной памяти.
-| Даёт вероятности принадлежности
-| Требует предположения о форме кластеров
+== Отличия от близких методов ==
-|-
-| Mean Shift
+=== Спектральное разбиение графов ===
-| Поиск мод плотности
-| Не требует задания числа кластеров
+Спектральное разбиение графов делит уже заданный граф, часто по знаку вектора Фидлера. Спектральная кластеризация дополнительно включает построение графа из объектов, выбор функции сходства, многомерное вложение и округление методом [[k-means]].
-| Дорогой вычислительно
-|-
+=== Laplacian Eigenmaps ===
-| Affinity Propagation
-| Передача сообщений между объектами
+Laplacian Eigenmaps использует собственные векторы лапласиана для нелинейного [[Снижение размерности|снижения размерности]]. Целью является сохранение локальной геометрии, а не обязательное получение кластерных меток.<ref name="Belkin2003">{{статья |автор=Belkin M., Niyogi P. |заглавие=Laplacian Eigenmaps for Dimensionality Reduction and Data Representation |ссылка=https://doi.org/10.1162/089976603321780317 |издание=Neural Computation |год=2003 |том=15 |номер=6 |страницы=1373—1396 |doi=10.1162/089976603321780317 |язык=en}}</ref>
-| Выбирает реальные представители кластеров
-| Квадратичная память
+=== Diffusion Maps ===
-|}
+Diffusion Maps строит координаты по собственным векторам марковского оператора и учитывает многошаговую диффузию. Метод предназначен прежде всего для анализа геометрии и диффузионных расстояний.<ref name="Coifman2006">{{статья |автор=Coifman R. R., Lafon S. |заглавие=Diffusion Maps |ссылка=https://doi.org/10.1016/j.acha.2006.04.006 |издание=Applied and Computational Harmonic Analysis |год=2006 |том=21 |номер=1 |страницы=5—30 |doi=10.1016/j.acha.2006.04.006 |язык=en}}</ref>
+=== Графовые нейронные сети ===
+[[Графовые нейронные сети]] обучают параметрические преобразования признаков с использованием рёбер графа. Использование лапласиана в выводе графовой свёртки не делает модель алгоритмом спектральной кластеризации.
+== Преимущества и ограничения ==
+Преимущества метода:
+* обнаружение невыпуклых и линейно неразделимых групп;
+* использование произвольных предметных мер сходства;
+* естественная работа с графовыми данными;
+* формальная связь с RatioCut и Normalized Cut.
+Основные ограничения:
+* квадратичная память для плотной матрицы сходства;
+* высокая стоимость вычисления собственных векторов;
+* необходимость выбирать граф, масштаб и число кластеров;
+* чувствительность к выбросам и ошибочным рёбрам;
+* отсутствие естественного точного продолжения на новые объекты.
+== Типичные ошибки ==
+* использование нестандартизованных признаков при евклидовой метрике;
+* слишком малое или слишком большое число соседей;
+* игнорирование изолированных вершин;
+* выбор собственных векторов не с того края спектра;
+* пропуск построчной нормировки в алгоритме Нга — Джордана — Вайса;
+* единственный запуск [[k-means]];
+* подбор параметров по тестовым меткам;
+* интерпретация любого спектрального зазора как доказательства кластерной структуры.
+== Когда метод предпочтителен ==
+Спектральная кластеризация особенно полезна, когда объекты естественно образуют граф, кластеры имеют сложную форму, важна связность по цепочкам локальных соседей и существует содержательная функция сходства. Метод обычно не является первым выбором для миллионов объектов без специальных приближений, при частом добавлении новых данных или когда кластеры хорошо описываются центроидами.
+== См. также ==
+* [[Кластеризация]]
+* [[Обучение без учителя]]
+* [[Лапласиан графа]]
+* [[Матрица смежности]]
+* [[Собственные значения]]
+* [[Собственные векторы]]
+* [[k-means]]
+* [[Иерархическая кластеризация]]
+* [[DBSCAN]]
+* [[Снижение размерности]]
+* [[Графовые нейронные сети]]
+== Примечания ==
+<references/>
+== Литература ==
+* Chung F. R. K. [https://www.ams.org/books/cbms/092/ Spectral Graph Theory]. — American Mathematical Society, 1997.
+* von Luxburg U. [https://doi.org/10.1007/s11222-007-9033-z A Tutorial on Spectral Clustering] // Statistics and Computing. — 2007. — Т. 17. — № 4. — С. 395—416.
+* Shi J., Malik J. [https://doi.org/10.1109/34.868688 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. [https://proceedings.neurips.cc/paper/2001/hash/801272ee79cfde7fa5960571fee36b9b-Abstract.html On Spectral Clustering: Analysis and an Algorithm] // Advances in Neural Information Processing Systems 14. — 2002. — С. 849—856.
+* Zelnik-Manor L., Perona P. [https://proceedings.neurips.cc/paper/2004/hash/40173ea48d9567f1f393b20c855bb40b-Abstract.html Self-Tuning Spectral Clustering] // Advances in Neural Information Processing Systems 17. — 2004. — С. 1601—1608.
+* Fowlkes C., Belongie S., Chung F., Malik J. [https://doi.org/10.1109/TPAMI.2004.1262185 Spectral Grouping Using the Nyström Method] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2004. — Т. 26. — № 2. — С. 214—225.
+* Belkin M., Niyogi P. [https://doi.org/10.1162/089976603321780317 Laplacian Eigenmaps for Dimensionality Reduction and Data Representation] // Neural Computation. — 2003. — Т. 15. — № 6. — С. 1373—1396.
+* Coifman R. R., Lafon S. [https://doi.org/10.1016/j.acha.2006.04.006 Diffusion Maps] // Applied and Computational Harmonic Analysis. — 2006. — Т. 21. — № 1. — С. 5—30.
+* Shaham U., Stanton K., Li H., Nadler B., Basri R., Kluger Y. [https://openreview.net/forum?id=HJ_aoCyRZ SpectralNet: Spectral Clustering Using Deep Neural Networks] // International Conference on Learning Representations. — 2018.
+[[Категория:Кластеризация]]
+[[Категория:Обучение без учителя]]
+[[Категория:Теория графов]]
+[[Категория:Машинное обучение]]
+[[Категория:Энциклопедия анализа данных]]
+[[Категория:Спектральные методы]]

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

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

Текущая версия

Содержание

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

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

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

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

ε-граф

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

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

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

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

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

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

Связь с RatioCut и Normalized Cut

Разрез графа

RatioCut

Normalized Cut

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

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

Псевдокод

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

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

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

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

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

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

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

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

Метод Nyström

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

Landmark-based методы

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

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

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

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

Применения

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

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

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

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

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

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

k-means

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

DBSCAN

Gaussian Mixture Models

Mean Shift

Affinity Propagation

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

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

Laplacian Eigenmaps

Diffusion Maps

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

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

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

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

См. также

Примечания

Литература

Просмотры

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

Навигация

Поиск

Инструменты