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

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

Версия от 11:34, 19 июля 2026; Valeriia Berdnikova (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM ChatGPT и проверена участником ....


Содержание

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

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

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

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

X=\{x_1,\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}) — матрица весов, задающая сходство объектов.

Вес 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 \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}

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

d_i=\sum_j 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.

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

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;
  • функция сходства;
  • параметры построения графа.

Выход:

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

Алгоритм:

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

Псевдокод

Вход: данные 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\mathbb 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):\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).

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

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

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

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

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

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

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

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

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

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

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

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

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

Применения:

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

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

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

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

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

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

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

Метод Основная идея Преимущества Ограничения
k-means Минимизация расстояний до центроидов Быстрый, масштабируемый Только выпуклые кластеры, нужно задать K
Иерархическая кластеризация Построение дерева кластеров Не требует K заранее Высокая сложность на больших данных
DBSCAN Поиск областей высокой плотности Находит шум, кластеры произвольной формы Чувствителен к параметрам плотности
Gaussian Mixture Models Вероятностная модель смеси распределений Даёт вероятности принадлежности Требует предположения о форме кластеров
Mean Shift Поиск мод плотности Не требует задания числа кластеров Дорогой вычислительно
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»
Личные инструменты