Данные разбиения с использованием спектральной кластеризации

Эта тема предоставляет введение в спектральную кластеризацию и пример, который оценивает количество кластеров и выполняет спектральную кластеризацию.

Введение в спектральную кластеризацию

Спектральная кластеризация является основанным на графе алгоритмом для разбиения точек данных, или наблюдений, на k кластеров. Функция Statistics and Machine Learning Toolbox™ spectralcluster выполняет кластеризацию на входные данные матрице или на матрице подобия графика полученной из данных. spectralcluster возвращает индексы кластера, матрицу k содержащую собственные векторы Матрицы Лапласа, и вектор собственных значений, соответствующих собственным векторам.

spectralcluster требует, чтобы вы задали количество k кластеров. Однако можно проверить, что ваша оценка для k верна, используя один из следующих методов:

Отсчитайте количество нулевых собственных значений Матрицы Лапласа. Кратность нулевых собственных значений является показателем количества кластеров в ваших данных.
Найдите количество связанных компонентов в матрице подобия с помощью MATLAB^® функция conncomp.

Описание алгоритма

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

По умолчанию алгоритм для spectralcluster вычисляет нормированную матрицу Лапласа случайной ходьбы с помощью метода, описанного Ши-Маликом [1]. spectralcluster также поддерживает неормализованную матрицу Лапласа и нормализованную симметричную матрицу Лапласа, которая использует метод Ng-Jordan-Weiss [2]. spectralcluster функция реализует кластеризацию следующим образом:

Для каждой точки данных в X, задайте локальное соседство с помощью метода поиска радиуса или метода ближайшего соседа, как задано 'SimilarityGraph' Аргумент пары "имя-значение" (см. График подобия). Затем найдите парные расстояния $D i s t_{i, j}$ для всех точек i и j в районе.
Преобразуйте расстояния в измерения подобия с помощью преобразования ядра $S_{i, j} = \exp (- {(\frac{D i s t_{i, j}}{σ})}^{2})$ . Матричная S является матрицей подобия, и σ является масштабным коэффициентом для ядра, как задано с помощью 'KernelScale' аргумент пары "имя-значение".
Вычислите неормализованную матричную L Лаплака, нормализованную Матрицу Лапласа Lrw с случайной ходьбой или нормализованную _{симметричную} матричную Ls с Лаплаковой в зависимости от значения 'LaplacianNormalization' аргумент пары "имя-значение".
Создайте матрицу $V \in ℝ^{n \times k}$ содержащие столбцы $v_{1}, \dots, v_{k}$ , где столбцы являются k собственными векторами, которые соответствуют k наименьшим собственным значениям Матрицы Лапласа. При использовании _Ls нормализуйте каждую строку V, чтобы она имела единичную длину.
Рассматривая каждую строку V как точку, группируйте точки n с помощью кластеризации k -means (по умолчанию) или k-medoids, как задано 'ClusterMethod' аргумент пары "имя-значение".
Присвойте исходные точки в X в те же кластеры, что и соответствующие им строки в V.

Оценка количества кластеров и выполнение спектральной кластеризации

Открыть Live Script

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

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

Сгенерируйте выборочные данные

Случайным образом сгенерируйте набор выборочных данных с тремя хорошо разделенными кластерами, каждый из которых содержит 20 точек.

rng('default'); % For reproducibility
n = 20;
X = [randn(n,2)*0.5+3;
    randn(n,2)*0.5;
    randn(n,2)*0.5-3];

Выполните спектральную кластеризацию данных

Оцените количество кластеров в данных с помощью собственных значений Матрицы Лапласа и выполните спектральную кластеризацию на наборе данных.

Вычислите пять наименьших собственных значений (в величине) Матрицы Лапласа с помощью spectralcluster функция. По умолчанию функция использует нормированную матрицу Лапласа random-walk.

[~,V_temp,D_temp] = spectralcluster(X,5)

V_temp = 60×5

    0.2236    0.0000    0.0000    0.1534   -0.0000
    0.2236    0.0000    0.0000   -0.3093    0.0000
    0.2236    0.0000    0.0000    0.2225   -0.0000
    0.2236    0.0000    0.0000    0.1776   -0.0000
    0.2236    0.0000    0.0000    0.1331   -0.0000
    0.2236    0.0000    0.0000    0.2176   -0.0000
    0.2236    0.0000    0.0000    0.1967    0.0000
    0.2236    0.0000    0.0000   -0.0088   -0.0000
    0.2236    0.0000    0.0000   -0.2844    0.0000
    0.2236    0.0000    0.0000   -0.3275    0.0000
      ⋮

D_temp = 5×1

   -0.0000
   -0.0000
   -0.0000
    0.0876
    0.1653

Только первые три собственных значений примерно равны нулю. Количество нулевых собственных значений является хорошим показателем количества связанных компонентов в графике подобия и, следовательно, является хорошей оценкой количества кластеров в ваших данных. Итак, k=3 является хорошей оценкой количества кластеров в X.

Выполните спектральную кластеризацию по наблюдениям при помощи spectralcluster функция. Задайте k=3 кластеры.

k = 3;
[idx1,V,D] = spectralcluster(X,k)

idx1 = 60×1

     1
     1
     1
     1
     1
     1
     1
     1
     1
     1
      ⋮

V = 60×3

    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
    0.2236    0.0000   -0.0000
      ⋮

D = 3×1
10^-16 ×

   -0.0740
   -0.1589
   -0.3613

Элементы D соответствуют трем наименьшим собственным значениям Матрицы Лапласа. Столбцы V содержат собственные векторы, соответствующие собственным значениям в D. Для хорошо разделенных кластеров собственные векторы являются векторами-индикаторами. Собственные векторы имеют значения нуля (или близкие к нулю) для точек, которые не принадлежат конкретному кластеру, и ненулевые значения для точек, которые принадлежат конкретному кластеру.

Визуализируйте результат кластеризации.

gscatter(X(:,1),X(:,2),idx1);

Figure contains an axes. The axes contains 3 objects of type line. These objects represent 1, 2, 3.

The spectralcluster функция правильно определяет три кластера в наборе данных.

Вместо использования spectralcluster снова функция, вы можете пройти V_temp на kmeans функция для кластеризации точек данных.

idx2 = kmeans(V_temp(:,1:3),3);
gscatter(X(:,1),X(:,2),idx2);

Figure contains an axes. The axes contains 3 objects of type line. These objects represent 1, 2, 3.

Порядок назначения кластеров в idx1 и idx2 отличается, даже если точки данных кластеризованы одинаково.

Выполните спектральную кластеризацию на матрице подобия

Оцените количество кластеров, используя графиков подобия, и выполните спектральную кластеризацию на матрице подобия.

Найти расстояние между каждой парой наблюдений в X при помощи pdist и squareform функционирует с метрикой Евклидова расстояния по умолчанию.

dist_temp = pdist(X);
dist = squareform(dist_temp);

Создайте матрицу подобия из парного расстояния и подтвердите, что матрица подобия симметрична.

S = exp(-dist.^2);
issymmetric(S)

ans = logical
   1

Ограничьте значения подобия 0.5 так что график подобия соединяет только точки, чьи парные расстояния меньше радиуса поиска.

S_eps = S;
S_eps(S_eps<0.5) = 0;

Создайте graph объект из S.

G_eps = graph(S_eps);

Визуализируйте график подобия.

plot(G_eps)

Figure contains an axes. The axes contains an object of type graphplot.

Определите количество связанных компонентов в графике G_eps при помощи unique и conncomp функций.

unique(conncomp(G_eps))

ans = 1×3

     1     2     3

На графике подобия показаны три набора связанных компонентов. Количество связанных компонентов в графике подобия является хорошей оценкой количества кластеров в ваших данных. Поэтому k=3 является хорошим выбором для количества кластеров в X.

Выполните спектральную кластеризацию на матрице подобия, выведенной из набора данных X.

k = 3;
idx3 = spectralcluster(S_eps,k,'Distance','precomputed');
gscatter(X(:,1),X(:,2),idx3);

Figure contains an axes. The axes contains 3 objects of type line. These objects represent 1, 2, 3.

The spectralcluster функция правильно определяет три кластера в наборе данных.

Ссылки

[1] Ши, Дж., и Дж. Малик. «Нормированные вырезы и сегментация изображений». Транзакции IEEE по шаблонному анализу и машинному анализу. Том 22, 2000, стр. 888-905.

[2] Ng, A.Y., M. Jordan, and Y. Weiss. «О спектральной кластеризации: Анализ и алгоритм». В трудах по усовершенствованиям в системах обработки нейронной информации 14. MIT Press, 2001, стр. 849-856.

См. также

Документация