Данные о разделе Используя спектральную кластеризацию

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

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

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

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

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

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

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

По умолчанию, алгоритм для spectralcluster вычисляет нормированную Матрицу Лапласа случайного обхода с помощью метода, описанного Ши-Маликом [1]. spectralcluster также поддерживает ненормированную Матрицу Лапласа и нормированную симметричную Матрицу Лапласа, которая использует метод Ына-Джордана-Вайса [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 - означает кластеризировать (значение по умолчанию) или k-medoids кластеризацию, как задано 'ClusterMethod' аргумент пары "имя-значение".
Присвойте исходные точки в X к тем же кластерам как их соответствующие строки в V.

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

Скрипт Open 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 функция. По умолчанию функция использует нормированную Матрицу Лапласа случайного обхода.

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

V_temp = 60×5

    0.0000    0.2236   -0.0000   -0.1534   -0.0000
    0.0000    0.2236   -0.0000    0.3093    0.0000
    0.0000    0.2236   -0.0000   -0.2225    0.0000
    0.0000    0.2236   -0.0000   -0.1776   -0.0000
    0.0000    0.2236   -0.0000   -0.1331    0.0000
    0.0000    0.2236   -0.0000   -0.2176   -0.0000
    0.0000    0.2236   -0.0000   -0.1967    0.0000
    0.0000    0.2236   -0.0000    0.0088    0.0000
    0.0000    0.2236   -0.0000    0.2844    0.0000
    0.0000    0.2236   -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.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   -0.2236    0.0000
      ⋮

D = 3×1
10^-16 ×

   -0.1031
   -0.1601
   -0.3754

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

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

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

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

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

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

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

Figure contains an axes object. The axes object 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 object. The axes object 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 object. The axes object contains 3 objects of type line. These objects represent 1, 2, 3.

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

Ссылки

[1] Ши, J. и Дж. Малик. “Нормированные сокращения и сегментация изображений”. Транзакции IEEE согласно Анализу Шаблона и Искусственному интеллекту. Издание 22, 2000, стр 888–905.

[2] Ын, A.Y., М. Джордан и И. Вайс. “На спектральной кластеризации: Анализ и алгоритм”. В Продолжениях Усовершенствований в Нейронных Системах обработки информации 14. Нажатие MIT, 2001, стр 849–856.

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