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

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

Перейти к: навигация, поиск
Статья написана с использованием LLM ChatGPT и проверена участником ....


Содержание

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

Основная идея метода состоит в построении графа сходства, вычислении нескольких собственных векторов соответствующего лапласиана и последующей кластеризации полученного низкоразмерного представления, обычно алгоритмом 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;
  • функция сходства;
  • параметры построения графа.

Выход:

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

Алгоритм:

  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\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;
  • подбор параметров по тестовым меткам;
  • интерпретация любого спектрального зазора как доказательства кластерной структуры.

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

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

См. также

Литература


Источник — «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»
Личные инструменты