Спектральная кластеризация
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);
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' аргумент пары имя-значение (см. График подобия). Затем найдите попарные расстояния j для всех точек i и j по соседству.
Преобразуйте расстояния в измерения подобия с помощью преобразования ядра jλ) 2). Матрица S является матрицей подобия, а λ является масштабным коэффициентом для ядра, как указано с помощью'KernelScale' аргумент пары имя-значение.
Вычислите ненормализованную лапласианскую матрицу
L, нормализованную лапласианскую матрицу случайного обхода Lrw или нормализованную симметричную лапласианскую матрицу Ls, в зависимости от значения 'LaplacianNormalization' аргумент пары имя-значение.
Создайте матрицы, содержащий столбцы vk, где столбцы являются k собственными векторами, которые соответствуют k наименьшим собственным значениям матрицы Лапласа. При использовании LS нормализуйте каждую строку V, чтобы она имела единичную длину.
Рассматривая каждую строку V как точку, скопируйте n точек, используя кластеризацию k-means (по умолчанию) или кластеризацию k-medoids, как определено 'ClusterMethod' аргумент пары имя-значение.
Назначение исходных точек в X к тем же кластерам, что и их соответствующие строки в V.
[2] Ши, Дж., и Дж. Малик. «Нормализованные вырезы и сегментация изображения». Транзакции IEEE по анализу шаблонов и машинному интеллекту. Том 22, 2000, стр. 888-905.
[3] Нг, А. Я., М. Джордан и Я. Вайс. «О спектральной кластеризации: анализ и алгоритм». В трудах о достижениях в системах обработки нейронной информации 14. MIT Press, 2001, стр. 849-856.