Спектральная кластеризация
idx = spectralcluster(S,k,'Distance','precomputed')S, матрица подобия (или матрица смежности) график подобия. S может быть выходом adjacency.
Чтобы использовать матрицу подобия в качестве первого входа, вы должны задать 'Distance','precomputed'.
idx = spectralcluster(___,Name,Value)'SimilarityGraph','epsilon' чтобы создать график подобия с помощью метода радиусного поиска.
[ также возвращает собственные векторы idx,V] = spectralcluster(___)V соответствующий k наименьшие собственные значения Матрицы Лапласа.
Скопируйте 2-D набор круговых данных с помощью спектральной кластеризации с метрикой Евклидова расстояния по умолчанию.
Сгенерируйте синтетические данные, которые содержат два шумных круга.
rng('default') % For reproducibility % Parameters for data generation N = 300; % Size of each cluster r1 = 2; % Radius of first circle r2 = 4; % Radius of second circle theta = linspace(0,2*pi,N)'; X1 = r1*[cos(theta),sin(theta)]+ rand(N,1); X2 = r2*[cos(theta),sin(theta)]+ rand(N,1); X = [X1;X2]; % Noisy 2-D circular data set
Найдите два кластера в данных с помощью спектральной кластеризации.
idx = spectralcluster(X,2);
Визуализируйте результат кластеризации.
gscatter(X(:,1),X(:,2),idx);
The spectralcluster функция правильно определяет два кластера в наборе данных.
Вычислите матрицу подобия из набора данных радужки Фишера и выполните спектральную кластеризацию на матрице подобия.
Загрузите набор данных радужки Фишера. Используйте длины и ширины лепестков в качестве функций для кластеризации.
load fisheriris
X = meas(:,3:4);
gscatter(X(:,1),X(:,2),species);
Найти расстояние между каждой парой наблюдений в X при помощи pdist и squareform функционирует с метрикой Евклидова расстояния по умолчанию.
dist_temp = pdist(X); dist = squareform(dist_temp);
Создайте матрицу подобия и подтвердите, что она симметричная.
S = exp(-dist.^2); issymmetric(S)
ans = logical
1
Выполните спектральную кластеризацию. Задайте 'Distance','precomputed' для выполнения кластеризации с помощью матрицы подобия. Задайте k=3 кластеры и установите 'LaplacianNormalization' аргумент пары "имя-значение" для использования нормализованной симметричной матрицы Лапласа.
k = 3; % Number of clusters rng('default') % For reproducibility idx = spectralcluster(S,k,'Distance','precomputed','LaplacianNormalization','symmetric');
idx содержит индексы кластеров для каждого наблюдения в X.
Визуализируйте результат кластеризации.
gscatter(X(:,1),X(:,2),idx);
Сведите результаты кластеризации в таблицу.
tabulate(idx)
Value Count Percent
1 48 32.00%
2 50 33.33%
3 52 34.67%
The Percent в столбце показан процент точек данных, присвоенных трем кластерам.
Повторите спектральную кластеризацию, используя данные как вход в spectralcluster. Задайте 'NumNeighbors' как size(X,1), что соответствует созданию матрицы подобия S путем соединения каждой точки со всеми оставшимися точками.
idx2 = spectralcluster(X,k,'NumNeighbors',size(X,1),'LaplacianNormalization','symmetric'); gscatter(X(:,1),X(:,2),idx2);
tabulate(idx2)
Value Count Percent
1 50 33.33%
2 52 34.67%
3 48 32.00%
Результаты кластеризации для обоих подходов одинаковы. Порядок назначений кластеров отличается, даже если точки данных кластеризованы одинаковым образом.
Найдите кластеры в наборе данных на основе заданного радиуса поиска для создания графика подобия.
Создайте данные с 3 кластеры, каждый из которых содержит 500 точек.
rng('default') % For reproducibility N = 500; X = [mvnrnd([0 0],eye(2),N); ... mvnrnd(5*[1 -1],eye(2),N); ... mvnrnd(5*[1 1],eye(2),N)];
Задайте радиус поиска 2 для создания графика подобия и поиска 3 кластеров в данных.
idx = spectralcluster(X,3,'SimilarityGraph','epsilon','Radius',2);
Визуализируйте результат кластеризации.
gscatter(X(:,1),X(:,2),idx);
Найдите собственные значения и собственные векторы Матрицы Лапласа и используйте значения для подтверждения результатов кластеризации.
Случайным образом сгенерируйте выборочные данные с тремя хорошо разделенными кластерами, каждый из которых содержит 100 точек.
rng('default'); % For reproducibility n = 100; X = [randn(n,2)*0.5+3; randn(n,2)*0.5 randn(n,2)*0.5-3];
Оцените количество кластеров в данных с помощью собственных значений Матрицы Лапласа. Вычислите пять наименьших собственных значений (в величине) Матрицы Лапласа.
[~,~,D_temp] = spectralcluster(X,5)
D_temp = 5×1
-0.0000
-0.0000
-0.0000
0.0277
0.0296
Только первые три собственных значений примерно равны нулю. Количество нулевых собственных значений является хорошим показателем количества связанных компонентов в графике подобия и, следовательно, является хорошей оценкой количества кластеров в ваших данных. Итак, k=3 является хорошей оценкой количества кластеров в X.
Поиск k=3 Кластеры и возврат трёх наименьших собственных значений и соответствующие собственные векторы Матрицы Лапласа.
[idx,V,D] = spectralcluster(X,3)
idx = 300×1
3
3
3
3
3
3
3
3
3
3
⋮
V = 300×3
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
-0.0000 0.1000 0.0000
⋮
D = 3×1
10-16 ×
-0.3634
-0.3857
-0.3894
Элементы D соответствуют трем наименьшим собственным значениям Матрицы Лапласа. Столбцы V содержат собственные векторы, соответствующие собственным значениям в D. Для хорошо разделенных кластеров собственные векторы являются векторами-индикаторами. Собственные векторы имеют значения нуля (или близкие к нулю) для точек, которые не принадлежат конкретному кластеру, и ненулевые значения для точек, которые принадлежат конкретному кластеру.
Визуализируйте результат кластеризации.
gscatter(X(:,1),X(:,2),idx);
Рассмотрите использование спектральной кластеризации, когда кластеры в ваших данных естественно не соответствуют выпуклым областям.
Из алгоритма спектральной кластеризации можно оценить количество кластеров k как:
Для получения примера см. «Оценка количества кластеров и выполнение спектральной кластеризации».
Спектральная кластеризация является основанным на графе алгоритмом для кластеризации точек данных (или наблюдений в X). Алгоритм включает построение графика, нахождение его Матрицы Лапласа и использование этой матрицы для поиска k собственных векторов, чтобы разделить графиков k способами. По умолчанию алгоритм для spectralcluster вычисляет нормированную матрицу Лапласа случайной ходьбы с помощью метода, описанного Ши-Маликом [2]. spectralcluster также поддерживает неормализованную матрицу Лапласа и нормализованную симметричную матрицу Лапласа, которая использует метод Ng-Jordan-Weiss [3]. spectralcluster реализует кластеризацию следующим образом:
Для каждой точки данных в X, задайте локальное соседство с помощью метода поиска радиуса или метода ближайшего соседа, как задано 'SimilarityGraph' Аргумент пары "имя-значение" (см. График подобия). Затем найдите парные расстояния для всех точек i и j в районе.
Преобразуйте расстояния в измерения подобия с помощью преобразования ядра . Матричная S является матрицей подобия, и σ является масштабным коэффициентом для ядра, как задано с помощью 'KernelScale' аргумент пары "имя-значение".
Вычислите неормализованную матричную
L Лаплака, нормализованную Матрицу Лапласа Lrw с случайной ходьбой или нормализованную симметричную матричную Ls с Лаплаковой в зависимости от значения 'LaplacianNormalization' аргумент пары "имя-значение".
Создайте матрицу содержащие столбцы , где столбцы являются k собственными векторами, которые соответствуют k наименьшим собственным значениям Матрицы Лапласа. При использовании Ls нормализуйте каждую строку V, чтобы она имела единичную длину.
Рассматривая каждую строку V как точку, группируйте точки n с помощью кластеризации k -means (по умолчанию) или k-medoids, как задано 'ClusterMethod' аргумент пары "имя-значение".
Присвойте исходные точки в X в те же кластеры, что и соответствующие им строки в V.
[2] Ши, Дж., и Дж. Малик. «Нормированные вырезы и сегментация изображений». Транзакции IEEE по шаблонному анализу и машинному анализу. Том 22, 2000, стр. 888-905.
[3] Ng, A.Y., M. Jordan, and Y. Weiss. «О спектральной кластеризации: Анализ и алгоритм». В трудах по усовершенствованиям в системах обработки нейронной информации 14. MIT Press, 2001, стр. 849-856.