Skip to content
Назад к результатам поиска

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

Автор метода
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
Год
2002
Тип
Graph-based clustering (spectral method)

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Спектральная кластеризация — это основанный на графах алгоритм обучения без учителя, формализованный Ng, Jordan и Weiss в 2002 году, который отображает точки данных в низкоразмерное собственное пространство, полученное из лапласиана графа сходства, перед применением k-средних.

Эта спектральная эмбеддинг позволяет восстанавливать кластеры произвольной формы — кольца, полумесяцы, переплетенные спирали — которые методы, основанные на евклидовом расстоянии, последовательно не могут разделить.

Интуиция метода

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

История

Теоретические основы спектральной кластеризации восходят к работе Fiedler 1973 года по связности графов и собственному значению алгебраической связности. Shi и Malik (2000) привнесли этот подход в компьютерное зрение через свой критерий нормализованных разрезов для сегментации изображений. Ng, Jordan и Weiss (2002) представили чистый, универсальный алгоритм на NIPS — тот, на который сейчас чаще всего ссылаются — вместе с анализом теории возмущений, объясняющим, когда и почему метод работает. Тьюториал Von Luxburg 2007 года в Statistics and Computing объединил конкурирующие формулировки, прояснил роль нормализации лапласиана и стал стандартным справочником для практиков. Спектральная кластеризация теперь занимает центральное место в учебной программе по машинному обучению и остается активной темой исследований, с текущими работами по масштабируемым аппроксимациям, робастным ядрам и расширениям для графов и многообразий.

Когда применять

Спектральная кластеризация хорошо подходит, когда кластеры в данных являются невыпуклыми, нелинейно разделимыми или соединены тонкими мостиками, которые методы евклидова разбиения не могут обнаружить — типичные примеры включают кольцевые кластеры, переплетенные спирали и сегменты изображений. Она уместна, когда попарное сходство между точками может быть осмысленно вычислено (либо из ядра на сырых признаках, либо из предварительно предоставленной матрицы аффинности), и когда количество кластеров k известно или может быть оценено с помощью эвристики эйгензазора. Метод не требует предположений о распределении форм кластеров. Практические ограничения включают квадратичную память по количеству точек (для полной матрицы аффинности) и кубическое время для эйгенразложения, что делает стандартную формулировку дорогостоящей для более чем примерно 10 000 точек. Приближенные методы (Nystrom, разреженные графы, рандомизированное SVD) расширяют ее возможности для больших наборов данных.

Ограничения и замечания

  • Построение полной n×n матрицы аффинности требует O(n^2) памяти и O(n^3) времени для эйгенразложения, что делает наивный алгоритм невыполнимым для больших наборов данных.
  • Результаты чувствительны к выбору ширины полосы пропускания ядра sigma и стратегии построения графа; плохой выбор может привести к слиянию или фрагментации кластеров.
  • Инициализация k-средних в спектральном эмбеддинге вносит случайность; разные запуски могут давать разные разбиения.
  • Плохо масштабируется для очень высокоразмерных пространств признаков без тщательного выбора ядра.
  • Предоставляет только метки кластеров; не предлагает генеративную модель и естественное расширение для новых точек вне выборки.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Обнаруживает кластеры произвольной формы, включая невыпуклые и нелинейно разделимые конфигурации, которые побеждают k-средние и модели гауссовских смесей.
  • Может работать с любой матрицей попарного сходства, а не только с евклидовыми расстояниями, что делает ее применимой к графам, строкам и другим структурированным данным.
  • Эвристика эйгензазора предоставляет принципиальное руководство, основанное на данных, для выбора количества кластеров k.
  • Основана на богатой спектральной теории графов, позволяющей формально анализировать сходимость и качество кластеризации.
  • Концептуально проста и легко реализуется с использованием стандартных библиотек линейной алгебры.

Применение

  • Сегментация изображений: разбиение пикселей или суперпикселей на перцептивно связные области с использованием сходства признаков на уровне пикселей.
  • Обнаружение сообществ в социальных и биологических сетях, где связность пар, а не векторы признаков, определяет структуру.
  • Биоинформатика: группировка генов или белков по сходству профилей экспрессии, где кластеры экспрессии редко бывают выпуклыми в пространстве генов.
  • Обработка естественного языка: кластеризация документов или предложений с использованием ядер семантического сходства.
  • Компьютерное зрение: сегментация движения и разбиение облаков точек, где границы кластеров нерегулярны.
  • Исследовательский анализ данных: выявление неочевидной структуры кластеров перед применением подтверждающих методов.

Как это работает

Как это работает

1

Строится матрица попарного сходства (аффинности) W, полученная из данных. Наиболее распространенным выбором является гауссовское ядро (RBF), которое присваивает большой вес близким парам и вес, близкий к нулю, для удаленных пар. Параметр ширины полосы пропускания sigma контролирует, насколько быстро сходство убывает с расстоянием; его правильный выбор критически важен. Альтернативно, граф k-ближайших соседей может быть использован для более разреженных представлений на больших наборах данных.

Формула
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

Матрица степеней D — это диагональная матрица, i-й элемент которой равен сумме i-й строки W. Из W и D формируется нормализованный (симметричный) лапласиан графа L_sym. Эта матрица отражает полную структуру связности графа сходства; ее спектр собственных значений показывает, сколько естественных кластеров содержит набор данных и насколько чисто они разделены.

Формула
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

Вычисляются k собственных векторов, соответствующих k наименьшим собственным значениям L_sym. Эти собственные векторы формируют столбцы матрицы эмбеддинга U, которая имеет одну строку на точку данных. В этом k-мерном спектральном пространстве точки, принадлежащие одному кластеру, сближаются, даже если они были переплетены в исходном пространстве признаков.

Формула
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

Каждая строка U делится на ее евклидову норму для проецирования эмбеддированных точек на единичную гиперсферу. Эта нормализация, введенная Ng, Jordan и Weiss, устраняет ложные различия в масштабе между собственными векторами и гарантирует, что последующий шаг k-средних фокусируется на угловой структуре эмбеддинга, а не на величине.

Формула
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

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

Частые ошибки

  • Выбор sigma без принципиальной кросс-валидации или самонастройки; ширина полосы пропускания, которая слишком мала, создает несвязный граф, в то время как слишком большая ширина полосы пропускания объединяет различные кластеры.
  • Пренебрежение нормализацией строк матрицы аффинности перед k-средними (шаг нормализации строк Ng et al. имеет решающее значение для стабильности).
  • Игнорирование эйгензазора: использование фиксированного k без проверки спектра собственных значений часто приводит к недо- или пере-сегментации.
  • Применение полного алгоритма к наборам данных с десятками тысяч точек без перехода к приближенному или разреженному варианту.
  • Путаница между ненормализованным (L = D - W) и нормализованным (L_sym, L_rw) лапласианами, которые могут существенно изменить присвоение кластеров.

Часто задаваемые вопросы

Как выбрать количество кластеров k?

Эвристика эйгензазора является стандартным руководством: вычислите собственные значения нормализованного лапласиана в порядке возрастания и найдите наибольший разрыв между последовательными собственными значениями. Индекс, при котором происходит этот разрыв, предполагает естественное количество кластеров. Когда эйгензазор неоднозначен, подходы, основанные на стабильности — запуск алгоритма для нескольких значений k и сравнение присвоений кластеров при возмущениях — могут помочь.

Как следует установить ширину полосы пропускания гауссовского ядра sigma?

Распространенная эвристика — медиана попарных расстояний в наборе данных или схема самонастройки ближайшего соседа (Zelnik-Manor & Perona, 2004), которая присваивает локальную ширину полосы пропускания каждой точке. На практике sigma следует проверять, анализируя связность результирующего графа аффинности: каждая точка должна иметь по крайней мере несколько соседей с большим весом, и граф не должен фрагментироваться на изолированные компоненты.

Почему необходим шаг нормализации строк?

Собственные векторы лапласиана могут существенно различаться по масштабу. Без нормализации каждой строки матрицы эмбеддинга до единичной длины, шаг k-средних может быть доминирован собственными векторами с большими величинами и игнорировать информативные, но меньшие по величине компоненты. Нормализация строк, введенная Ng, Jordan и Weiss, отображает все точки на единичную сферу, так что k-средние реагируют на угловую геометрию эмбеддинга.

Может ли спектральная кластеризация обрабатывать очень большие наборы данных?

Не в своей наивной форме, которая требует O(n^2) памяти и O(n^3) времени эйгенразложения. Для больших n стандартные решения включают: построение разреженного графа k-ближайших соседей вместо полной матрицы аффинности; использование аппроксимации Nystrom для оценки собственных векторов по подвыборке; или применение рандомизированного SVD. Эти приближенные методы восстанавливают большую часть точности при доле затрат.

Похожие методы

Источники

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    Открыть ссылку на публикацию
    Скопировано.
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    Открыть ссылку DOI
    Скопировано.
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    Открыть ссылку DOI
    Скопировано.