Спектральная кластеризация
idx = spectralcluster(S,k,'Distance','precomputed')S, матрица подобия (или матрица смежности) графика подобия. S может быть выход adjacency.
Чтобы использовать матрицу подобия в качестве первого входа, необходимо задать 'Distance','precomputed'.
idx = spectralcluster(___,Name,Value)'SimilarityGraph','epsilon' создать график подобия с помощью метода поиска радиуса.
[ также возвращает собственные вектора idx,V] = spectralcluster(___)V соответствие k самые маленькие собственные значения Матрицы Лапласа.
Кластеризируйте 2D круговой набор данных с помощью спектральной кластеризации с Евклидовой метрикой расстояния по умолчанию.
Сгенерируйте синтетические данные, которые содержат два шумных круга.
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);
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%
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 также поддерживает ненормированную Матрицу Лапласа и нормированную симметричную Матрицу Лапласа, которая использует метод Ына-Джордана-Вайса [3]. spectralcluster реализации, кластеризирующиеся можно следующим образом:
Для каждой точки данных в X, задайте локальное окружение с помощью или метода поиска радиуса или самого близкого соседнего метода, как задано 'SimilarityGraph' аргумент пары "имя-значение" (см. График Подобия). Затем найдите попарные расстояния для всех точек i и j в окружении.
Преобразуйте расстояния до мер по подобию с помощью преобразования ядра . Матричный S является матрицей подобия, и σ является масштабным коэффициентом для ядра, как задано использование 'KernelScale' аргумент пары "имя-значение".
Вычислите ненормированную Матрицу Лапласа
L, нормированная Матрица Лапласа случайного обхода Lrw или нормированная симметричная Матрица Лапласа Ls, в зависимости от значения 'LaplacianNormalization' аргумент пары "имя-значение".
Создайте матрицу содержа столбцы , где столбцы являются собственными векторами k, которые соответствуют k самые маленькие собственные значения Матрицы Лапласа. При использовании Ls нормируйте каждую строку V, чтобы иметь единичную длину.
При обработке каждой строки V как точка кластеризируйтесь, точки n с помощью k - означает кластеризировать (значение по умолчанию) или k-medoids кластеризацию, как задано 'ClusterMethod' аргумент пары "имя-значение".
Присвойте исходные точки в X к тем же кластерам как их соответствующие строки в V.
[2] Ши, J. и Дж. Малик. “Нормированные сокращения и сегментация изображений”. Транзакции IEEE согласно Анализу Шаблона и Искусственному интеллекту. Издание 22, 2000, стр 888–905.
[3] Ын, A.Y., М. Джордан и И. Вайс. “На спектральной кластеризации: Анализ и алгоритм”. В Продолжениях Усовершенствований в Нейронных Системах обработки информации 14. Нажатие MIT, 2001, стр 849–856.