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

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

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

${\displaystyle L^{\text{norm}}:=I-D^{-1/2}AD^{-1/2},}$

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

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

Математически эквивалентный алгоритм[2] использует собственный вектор, соответствующий наибольшему собственному значению нормализованной матрицы Кирхгофа случайного блуждания ${\displaystyle P=D^{-1}A}$. Алгоритм Мейла – Ши был проверен в контексте диффузионных карт, которые, как обнаружилось, имеют связь с вычислительной квантовой механикой[3].

Другая возможность — использование матрицы Кирхгофа, задаваемой выражением

${\displaystyle L:=D-A}$

а не симметрично нормализованной матрицы Кирхгофа.

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

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

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

Спектральная кластеризация тесно связана с нелинейным понижением размерности и могут быть использованы техники понижения размерности, такие как локально линейное вложение, для уменьшения погрешности от шума или выброса в наблюдениях[5].

Бесплатное программное обеспечение для имплементации спектральной кластеризации доступно в больших проектах с открытым исходным кодом, таких как Scikit-learn[6], MLlib для кластеризации на основе псевдособственных значений с использованием метода степенной итерации[7], языка R[8].

Задача о k-средних с нелинейным ядром является расширением задачи о k-средних, в которой входные точки отображаются нелинейно в пространство признаков высокой размерности с помощью ядерной функции ${\displaystyle k(x_{i},x_{j})=\varphi ^{T}(x_{i})\varphi (x_{j})}$. Взвешенная задача о k-средних с нелинейным ядром расширяет задачу далее, задавая вес ${\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}).}$

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

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

при условиях

${\displaystyle F=G_{n\times k}G_{k\times n}^{T}}$

${\displaystyle G^{T}G=E}$

При этом ${\displaystyle \operatorname {rank} (G)=k}$. Кроме того, задано ограничение на коэффициенты ${\displaystyle F}$

${\displaystyle F\cdot \mathbf {1} =\mathbf {1} }$,

где ${\displaystyle \mathbf {1} }$ представляет собой вектор из единиц.

${\displaystyle F^{T}\mathbf {1} =\mathbf {1} }$

Задачу можно преобразовать в

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

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

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

• Метод распространения близости
• Ядерный метод главных компонент
• Кластерный анализ
• Спектральная теория графов