Разбиение данных с использованием спектральной кластеризации

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

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

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

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

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

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

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

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

Для каждой точки данных в X, определите локальную окрестность с помощью метода поиска по радиусу или метода ближайшего соседа, как указано в 'SimilarityGraph' аргумент пары имя-значение (см. График подобия). Затем найдите попарные расстояния $_{Disti,}$ j для всех точек i и j по соседству.
Преобразуйте расстояния в измерения подобия с помощью преобразования ядра $_{Si,} j = {exp \frac{(-_{(}}{}}^{Disti},$ jλ) 2). Матрица S является матрицей подобия, а λ является масштабным коэффициентом для ядра, как указано с помощью'KernelScale' аргумент пары имя-значение.
Вычислите ненормализованную лапласианскую матрицу L, нормализованную лапласианскую матрицу случайного обхода Lrw или нормализованную _{симметричную} лапласианскую матрицу Ls, в зависимости от значения 'LaplacianNormalization' аргумент пары имя-значение.
Создайте $^{V∈ℝn×k}$ матрицы, содержащий столбцы $_{v1}, . . ._{,}$ vk, где столбцы являются k собственными векторами, которые соответствуют k наименьшим собственным значениям матрицы Лапласа. При _{использовании} LS нормализуйте каждую строку V, чтобы она имела единичную длину.
Рассматривая каждую строку V как точку, скопируйте n точек, используя кластеризацию k-means (по умолчанию) или кластеризацию k-medoids, как определено 'ClusterMethod' аргумент пары имя-значение.
Назначение исходных точек в X к тем же кластерам, что и их соответствующие строки в V.

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

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

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

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

Создать образец данных

Случайная генерация набора данных выборки с тремя хорошо разделенными кластерами, каждый из которых содержит 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.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.

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.

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

Ссылки

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

[2] Нг, А.Я., М. Джордан и Й. Вайс. «О спектральной кластеризации: анализ и алгоритм». В трудах о достижениях в системах обработки нейронной информации 14. MIT Press, 2001, стр. 849-856.

См. также

Связанные темы

Выбор метода кластерного анализа

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