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

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

Применительно к сегментации изображений спектральная кластеризация известна как категоризация объектов на основе сегментации .

Определения

Учитывая пронумерованный набор точек данных, матрица подобия может быть определена как симметричная матрица , где представляет меру сходства между точками данных с индексами и . Общий подход к спектральной кластеризации заключается в использовании стандартной кластеризации метода (существует много таких методов, K -средних обсуждаются ниже ) на соответствующих собственных векторах одного лапласиана матрицы из . Есть много разных способов определения лапласиана, которые имеют разные математические интерпретации, поэтому кластеризация также будет иметь разные интерпретации. Релевантными собственными векторами являются те, которые соответствуют нескольким наименьшим собственным значениям лапласиана, за исключением наименьшего собственного значения, которое будет иметь значение 0. Для вычислительной эффективности эти собственные векторы часто вычисляются как собственные векторы, соответствующие нескольким наибольшим собственным значениям a. функция лапласиана. ${\ displaystyle A}$${\ displaystyle A_ {ij} \ geq 0}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle A}$

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

${\ displaystyle L: = DA}$,

где - диагональная матрица ${\ displaystyle D}$

${\ displaystyle D_ {ii} = \ sum _ {j} A_ {ij}.}$

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

Популярным родственным методом спектральной кластеризации является алгоритм нормализованных отсечений или алгоритм Ши – Малика, представленный Джианбо Ши и Джитендрой Малик, обычно используемый для сегментации изображений . Это разделяет точки на две группы на основе собственного вектора , соответствующего второму-наименьшее собственное значение из симметричной нормализуется лапласиан определяется как ${\ displaystyle (B_ {1}, B_ {2})}$ ${\ displaystyle v}$

${\ displaystyle L ^ {\ text {norm}}: = ID ^ {- 1/2} AD ^ {- 1/2}.}$

Математически алгоритм эквивалентно принимает собственный вектор , соответствующий величине собственного значения от случайного блуждания нормализуется смежности матрицы . ${\ Displaystyle P = D ^ {- 1} A}$

Зная собственные векторы, разбиение может быть выполнено различными способами, например, путем вычисления медианы компонентов второго наименьшего собственного вектора и размещения всех точек, компонент которых больше, чем in , а остальные - внутрь . Алгоритм можно использовать для иерархической кластеризации , многократно разделяя подмножества таким образом. ${\ displaystyle m}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle m}$${\ displaystyle B_ {1}}$${\ displaystyle B_ {2}}$

Алгоритмы

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

1. Вычислите лапласиан (или нормализованный лапласиан)${\ displaystyle L}$
2. Вычислите первые собственные векторы (собственные векторы, соответствующие наименьшим собственным значениям )${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle L}$
3. Рассмотрим матрицу, образованную первыми собственными векторами; -й строка определяет особенность узла графа${\ displaystyle k}$${\ displaystyle l}$${\ displaystyle l}$
4. Кластеризация узлов графа на основе этих функций (например, с использованием кластеризации k-средних )

Если матрица подобия еще не была построена явно, эффективность спектральной кластеризации может быть улучшена, если решение соответствующей проблемы собственных значений выполняется безматричным способом (без явного манипулирования или даже вычисления матрицы подобия), как в Алгоритм Ланцоша . ${\ displaystyle A}$

Для графов большого размера второе собственное значение (нормализованной) матрицы Лапласа графа часто плохо обусловлено , что приводит к медленной сходимости итерационных решателей собственных значений. Предварительная подготовка - это ключевая технология, ускоряющая сходимость, например, в безматричном методе LOBPCG . Спектральная кластеризация успешно применялась к большим графам, сначала определяя структуру их сообществ , а затем группируя сообщества.

Спектральная кластеризация тесно связана с нелинейным уменьшением размерности , и методы уменьшения размерности, такие как локально-линейное встраивание, могут использоваться для уменьшения ошибок из-за шума или выбросов.

Программное обеспечение

Свободное программное обеспечение реализация спектральной кластеризации доступно в крупных проектах с открытым исходным кодом , как Scikit-Learn использования LOBPCG с многосеточным предобусловливанием или ARPACK , MLlib для псевдо-собственных векторов кластеризации с использованием мощности итераций методы и R .

Связь с другими методами кластеризации

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

Отношения с k- средними

Проблема ядра k- средних является расширением проблемы k- средних, где точки входных данных нелинейно отображаются в пространство признаков более высокой размерности через функцию ядра . Проблема взвешенного ядра k- средних еще больше расширяет эту проблему, определяя вес для каждого кластера как величину, обратную количеству элементов в кластере, ${\ Displaystyle к (x_ {i}, x_ {j}) = \ varphi ^ {T} (x_ {i}) \ varphi (x_ {j})}$${\ displaystyle w_ {r}}$

${\ displaystyle \ max _ {\ {C_ {s} \}} \ sum _ {r = 1} ^ {k} w_ {r} \ sum _ {x_ {i}, x_ {j} \ in C_ {r }} k (x_ {i}, x_ {j}).}$

Предположим , это матрица нормализующих коэффициентов для каждой точки для каждого кластера, если и ноль в противном случае. Предположим, есть матрица ядра для всех точек. Взвешенная ядерная k- средняя задача с n точками и k кластерами задается как, ${\ displaystyle F}$${\ displaystyle F_ {ij} = w_ {r}}$${\ displaystyle i, j \ in C_ {r}}$${\ displaystyle K}$

${\ displaystyle \ max _ {F} \ operatorname {trace} (KF)}$

такой, что

${\ Displaystyle F = G_ {п \ раз к} G_ {к \ раз п} ^ {T}}$

${\ Displaystyle G ^ {T} G = I}$

такой что . Кроме того, существуют ограничения идентичности, заданные выражением ${\ displaystyle \ operatorname {rank} (G) = k}$${\ displaystyle F}$

${\ Displaystyle F \ cdot \ mathbb {I} = \ mathbb {I}}$

${\ Displaystyle F ^ {T} \ mathbb {I} = \ mathbb {I}}$

где представляет собой вектор единиц. Эту задачу можно переформулировать как ${\ displaystyle \ mathbb {I}}$

${\ displaystyle \ max _ {G} \ operatorname {trace} (G ^ {T} G).}$

Эта проблема эквивалентна проблеме спектральной кластеризации, когда ограничения идентичности ослаблены. В частности, проблема k- средних взвешенных ядер может быть переформулирована как проблема спектральной кластеризации (разбиения графа) и наоборот. Результатом работы алгоритмов являются собственные векторы, которые не удовлетворяют требованиям идентичности для индикаторных переменных, определенных в . Следовательно, для обеспечения эквивалентности задач требуется постобработка собственных векторов. Преобразование проблемы спектральной кластеризации в задачу взвешенного ядра с k- средними значительно снижает вычислительную нагрузку. ${\ displaystyle F}$${\ displaystyle F}$

Связь с DBSCAN

Спектральная кластеризация также связана с кластеризацией DBSCAN , которая находит связанные по плотности компоненты. Связанные компоненты соответствуют оптимальным спектральным кластерам (без сечения краев); а DBSCAN использует асимметричный соседний граф с удаленными ребрами, когда исходные точки не являются плотными. Таким образом, DBSCAN - это частный случай спектральной кластеризации, но тот, который позволяет использовать более эффективные алгоритмы (в худшем случае , во многих практических случаях гораздо быстрее с индексами). ${\ Displaystyle О (п ^ {2})}$

Меры для сравнения кластеризации

Рави Каннан, Сантош Вемпала и Адриан Ветта предложили двухкритериальную меру для определения качества данной кластеризации. Они сказали, что кластеризация является (α, ε) -кластеризацией, если проводимость каждого кластера (в кластеризации) была не менее α, а вес межкластерных краев составлял не более ε доли от общего веса всех кластеров. ребра в графе. Они также рассматривают два алгоритма аппроксимации в той же статье.

Примерные решения

Спектральная кластеризация требует больших вычислительных ресурсов, если только граф не является разреженным и матрица подобия не может быть эффективно построена. Если матрица подобия представляет собой матрицу ядра RBF, спектральная кластеризация обходится дорого. Существуют приблизительные алгоритмы для повышения эффективности спектральной кластеризации: степенной метод, метод Нистрома и т. Д. Однако недавние исследования выявили проблемы со спектральной кластеризацией с методом Нистрома; в частности, матрица подобия с приближением Нистрома не является элементарно положительной, что может быть проблематичным.

История и родственная литература

Спектральная кластеризация имеет долгую историю. Спектральную кластеризацию как метод машинного обучения популяризировали Ши и Малик, Нг, Джордан и Вайс.

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

Смотрите также

• Распространение сродства
• Анализ основных компонентов ядра
• Кластерный анализ
• Теория спектральных графов

использованная литература