spectralcluster

Спектральная кластеризация

Описание

пример

idx = spectralcluster(X,k) наблюдения разделов в n-by-p матрица данных X в k кластеры с помощью спектрального алгоритма кластеризации (см. Алгоритмы). spectralcluster возвращает n-by-1 векторный idx содержа кластерные индексы каждого наблюдения.

пример

idx = spectralcluster(S,k,'Distance','precomputed') возвращает вектор кластерных индексов для S, матрица подобия (или матрица смежности) графика подобия. S может быть выход adjacency.

Чтобы использовать матрицу подобия в качестве первого входа, необходимо задать 'Distance','precomputed'.

пример

idx = spectralcluster(___,Name,Value) задает дополнительные опции с помощью одного или нескольких аргументов пары "имя-значение" в дополнение к входным параметрам в предыдущих синтаксисах. Например, можно задать 'SimilarityGraph','epsilon' создать график подобия с помощью метода поиска радиуса.

[idx,V] = spectralcluster(___) также возвращает собственные вектора V соответствие k самые маленькие собственные значения Матрицы Лапласа.

пример

[idx,V,D] = spectralcluster(___) также возвращает векторный D содержа 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.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
      ⋮

D = 3×1
10-16 ×

   -0.3308
   -0.3747
   -0.4167

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

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

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

Входные параметры

свернуть все

Входные данные в виде n-by-p числовая матрица. Строки X соответствуйте наблюдениям (или точки), и столбцы соответствуют переменным.

Программное обеспечение обрабатывает NaNs в X как недостающие данные и игнорирует любую строку X содержа по крайней мере один NaN. spectralcluster функция возвращает NaN значения для соответствующей строки в выходных аргументах idx и V.

Типы данных: single | double

Матрица подобия в виде n-by-n симметрическая матрица, где n является количеством наблюдений. Матрица подобия (или матрица смежности) представляют входные данные путем моделирования локальных отношений окружения среди точек данных. Значения в матрице подобия представляют ребра (или связи) между узлами (точки данных), которые соединяются в графике подобия. Для получения дополнительной информации смотрите Матрицу Подобия.

S не должен содержать NaN значения.

Использовать матрицу подобия в качестве первого входа spectralcluster, необходимо задать 'Distance','precomputed'.

Типы данных: single | double

Количество кластеров в данных в виде положительного целого числа.

Для получения дополнительной информации о том, как оценить количество кластеров, смотрите Советы.

Типы данных: single | double

Аргументы в виде пар имя-значение

Задайте дополнительные разделенные запятой пары Name,Value аргументы. Name имя аргумента и Value соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: spectralcluster(X,3,'SimilarityGraph','epsilon','Radius',5) задает 3 кластеры и использование метод поиска радиуса с поисковым радиусом 5 создать график подобия.

Метрика расстояния в виде разделенной запятой пары, состоящей из 'Distance' и вектор символов, строковый скаляр или указатель на функцию, как описано в этой таблице.

ЗначениеОписание
'precomputed'

Предварительно вычисленное расстояние. Необходимо задать эту опцию если первый вход к spectralcluster матрица подобия S.

'euclidean'

Евклидово расстояние (значение по умолчанию)

'seuclidean'

Стандартизированное Евклидово расстояние. Каждое координатное различие между наблюдениями масштабируется путем деления на соответствующий элемент стандартного отклонения, вычисленного из X. Используйте Scale аргумент пары "имя-значение", чтобы задать различный масштабный коэффициент.

'mahalanobis'

Расстояние Mahalanobis с помощью выборочной ковариации X, C = nancovX. Используйте Cov аргумент пары "имя-значение", чтобы задать различную ковариационную матрицу.

'cityblock'

Расстояние городского квартала

'minkowski'

Расстояние Минковскего. Экспонента по умолчанию равняется 2. Используйте P аргумент пары "имя-значение", чтобы задать различную экспоненту, где P значение положительной скалярной величины.

'chebychev'

Расстояние Чебычева (максимум координируют различие),

'cosine'

Один минус косинус включенного угла между наблюдениями (обработанный как векторы)

'correlation'

Один минус корреляция выборки между наблюдениями (обработанный как последовательности значений)

'hamming'

Расстояние Хемминга, которое является процентом координат, которые отличаются

'jaccard'

Один минус коэффициент Jaccard, который является процентом ненулевых координат, которые отличаются

'spearman'

Один минус порядковая корреляция демонстрационного Копьеносца между наблюдениями (обработанный как последовательности значений)

@distfun

Пользовательский указатель на функцию расстояния. Функция расстояния имеет форму

function D2 = distfun(ZI,ZJ)
% calculation of distance
...
где

  • ZI 1- n вектор, содержащий одно наблюдение.

  • ZJ m2- n матрица, содержащая несколько наблюдений. distfun должен принять матричный ZJ с произвольным числом наблюдений.

  • D2 m2- 1 вектор расстояний и D2(k) расстояние между наблюдениями ZI и ZJ(k,:).

Если ваши данные не разреженны, можно обычно вычислять расстояние более быстро при помощи встроенного расстояния вместо указателя на функцию.

Для получения дополнительной информации смотрите Метрики Расстояния.

Когда вы используете 'seuclidean', 'minkowski', или 'mahalanobis' метрика расстояния, можно задать дополнительный аргумент пары "имя-значение" 'Scale'P, или 'Cov', соответственно, чтобы управлять метрикой расстояния.

Пример: spectralcluster(X,5,'Distance','minkowski','P',3) задает 5 кластеры и использование метрики расстояния Минковскего с экспонентой 3 выполнять кластеризирующийся алгоритм.

Экспонента для метрики расстояния Минковскего в виде разделенной запятой пары, состоящей из 'P' и положительная скалярная величина.

Этот аргумент допустим только если 'Distance' 'minkowski'.

Пример: 'P',3

Типы данных: single | double

Ковариационная матрица для метрики расстояния Mahalanobis в виде разделенной запятой пары, состоящей из 'Cov' и положительная определенная матрица.

Этот аргумент допустим только если 'Distance' 'mahalanobis'.

Пример: 'Cov',eye(4)

Типы данных: single | double

Масштабные коэффициенты для стандартизированной Евклидовой метрики расстояния в виде разделенной запятой пары, состоящей из 'Scale' и числовой вектор неотрицательных значений.

Scale имеет длину p (количество столбцов в X), потому что каждая размерность (столбец) X имеет соответствующее значение в Scale. Для каждой размерности X, spectralcluster использует соответствующее значение в Scale стандартизировать различие между наблюдениями.

Этот аргумент допустим только если 'Distance' 'seuclidean'.

Типы данных: single | double

Тип графика подобия, чтобы создать из входных данных XВ виде разделенной запятой пары, состоящей из 'SimilarityGraph' и одно из этих значений.

ЗначениеОписаниеСпецифичные для графика Аргументы в виде пар имя-значение
'knn'Построение (По умолчанию) график с помощью самых близких соседей.

'NumNeighbors' — Количество самых близких соседей раньше создавало график подобия

'KNNGraphType' — Тип самого близкого соседнего графика

'epsilon'

Создайте график с помощью поиска радиуса. Необходимо задать значение для Radius если вы используете эту опцию.

'Radius' — Поисковый радиус для самых близких соседей раньше создавал график подобия

Для получения дополнительной информации см. График Подобия.

Этот аргумент допустим только если 'Distance' не 'precomputed'.

Пример: 'SimilarityGraph','epsilon'

Количество самых близких соседей раньше создавало график подобия в виде разделенной запятой пары, состоящей из 'NumNeighbors' и положительное целое число.

Этот аргумент допустим только если 'SimilarityGraph' 'knn'. Для получения дополнительной информации см. График Подобия.

Пример: 'NumNeighbors',10

Типы данных: single | double

Тип самого близкого соседнего графика в виде разделенной запятой пары, состоящей из 'KNNGraphType' и одно из этих значений.

ЗначениеОписание
'complete'

Подключения (По умолчанию) две точки i и j, когда или i является самым близким соседом j или j, являются самым близким соседом i.

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

'mutual'

Подключения две точки i и j, когда i является самым близким соседом j и j, являются самым близким соседом i.

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

Этот аргумент допустим только если 'SimilarityGraph' 'knn'.

Пример: 'KNNGraphType','mutual'

Поисковый радиус для самых близких соседей раньше создавал график подобия в виде разделенной запятой пары, состоящей из 'Radius' и неотрицательный скаляр.

Необходимо задать этот аргумент если 'SimilarityGraph' 'epsilon'. Для получения дополнительной информации см. График Подобия.

Пример: 'Radius',5

Типы данных: single | double

Масштабный коэффициент для ядра в виде разделенной запятой пары, состоящей из 'KernelScale' и 'auto' или положительная скалярная величина. Программное обеспечение использует масштабный коэффициент, чтобы преобразовать расстояния до мер по подобию. Для получения дополнительной информации см. График Подобия.

  • 'auto' опция поддерживается только для 'euclidean' и 'seuclidean' метрики расстояния.

  • Если вы задаете 'auto', затем программное обеспечение выбирает соответствующий масштабный коэффициент с помощью эвристической процедуры. Эта эвристическая процедура использует подвыборку, таким образом, оценки могут варьироваться от одного вызова до другого. Чтобы воспроизвести результаты, установите seed случайных чисел с помощью rng прежде, чем вызвать spectralcluster.

Этот аргумент допустим только если 'Distance' не 'precomputed'.

Пример: 'KernelScale','auto'

Типы данных: double | single | char | string

Метод, чтобы нормировать Матрицу Лапласа L в виде разделенной запятой пары, состоящей из 'LaplacianNormalization' и одно из этих значений.

ЗначениеОписание
'none'

Используйте Матрицу Лапласа L без нормализации.

'randomwalk'

Использование (По умолчанию) нормированная Матрица Лапласа случайного обхода Lrw (Ши-Малик [2]).

Lrw=Dg1L.

Матричный Dg является матрицей степени.

'symmetric'

Используйте нормированную симметричную Матрицу Лапласа Ls (Ын-Джордан-Вайс [3]).

Ls=Dg1/2LDg1/2.

Матричный Dg является матрицей степени.

Для получения дополнительной информации смотрите Матрицу Лапласа.

Пример: 'LaplacianNormalization','randomwalk'

Кластеризация метода, чтобы кластеризировать собственные вектора Матрицы Лапласа в виде разделенной запятой пары, состоящей из 'ClusterMethod' и любой 'kmeans' или 'kmedoids'.

  • 'kmeans' — Выполните k - означает кластеризироваться при помощи kmeans функция.

  • 'kmedoids' — Выполните k-medoids кластеризирующийся при помощи kmedoids функция.

kmeans и kmedoids вовлеките случайность в их алгоритмы. Поэтому воспроизвести результаты spectralcluster, необходимо установить seed генератора случайных чисел при помощи rng.

Пример: 'ClusterMethod','kmedoids'

Выходные аргументы

свернуть все

Кластерные индексы, возвращенные как числовой вектор-столбец. idx имеет строки n и каждую строку idx указывает на кластерное присвоение соответствующей строки (или наблюдение) в X.

Типы данных: double

Собственные вектора, возвращенные как n-by-k числовая матрица. Столбцы V собственные вектора, соответствующие k самые маленькие собственные значения Матрицы Лапласа. Эти собственные вектора являются низко-размерным представлением входных данных X на новом пробеле, где кластеры более широко разделяются.

Для хорошо разделенных кластеров собственные вектора являются векторами индикатора. Таким образом, собственные вектора имеют значения нуля (или близко к нулю) для точек, которые не принадлежат данному кластеру и ненулевым значениям для точек, которые принадлежат конкретному кластеру.

Типы данных: single | double

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

Типы данных: single | double

Больше о

свернуть все

График подобия

График подобия моделирует локальные отношения окружения между точками данных в X как неориентированный граф. Узлы в графике представляют точки данных, и ребра, которые бесцельны, представляют связи между точками данных.

Если попарное расстояние Disti,j между какими-либо двумя узлами i и j положительны (или больше, чем определенный порог), то график подобия соединяет эти два узла с помощью ребра [1]. Ребро между этими двумя узлами взвешивается попарным подобием Si,j, где Si,j=exp((Disti,jσ)2), поскольку заданное ядро масштабирует значение σ.

spectralcluster поддержки эти два метода построения графика подобия:

  • Самый близкий соседний метод (если 'SimilarityGraph' 'knn'(значение по умолчанию)): spectralcluster подключения указывают в X это - самые близкие соседи. Можно использовать 'NumNeighbors' и 'KNNGraphType' аргументы пары "имя-значение", чтобы задать опции для построения самого близкого соседнего графика.

    • Используйте 'NumNeighbors' задавать количество самых близких соседей.

    • Используйте 'KNNGraphType' задавать, сделать ли 'complete' или 'mutual' связь точек.

  • Метод поиска радиуса (если 'SimilarityGraph' 'epsilon'): spectralcluster подключения указывают, чьи попарные расстояния меньше, чем поисковый радиус. Необходимо указать, что поисковый радиус для самых близких соседей раньше создавал график подобия при помощи 'Radius' аргумент пары "имя-значение".

Матрица подобия

Матрица подобия является матричным представлением графика подобия. n-by-n матрица S=(Si,j)i,j=1,,n содержит попарные значения подобия между связанными узлами в графике подобия. Матрица подобия графика также называется матрицей смежности.

Матрица подобия симметрична, потому что ребра графика подобия бесцельны. Значение Si,j = 0 средние значения, что узлы i и j графика подобия не соединяются.

Матрица степени

Матрицей степени Dg является n-by-n диагональная матрица, полученная путем подведения итогов строк матрицы подобия S. Таким образом, i th диагональный элемент Dg Dg(i,i)=j=1nSi,j.

Матрица Лапласа

Матрица Лапласа является одним способом представлять график подобия. spectralcluster функционируйте поддерживает ненормированную Матрицу Лапласа, нормированная Матрица Лапласа с помощью метода Ши-Малика [2] и нормированная Матрица Лапласа с помощью метода Ына-Джордана-Вайса [3].

  • Ненормированная Матрица Лапласа L является различием между матрицей степени и матрицей подобия.

    L=DgS.

  • Нормированная Матрица Лапласа случайного обхода (Ши-Малик) задана как:

    Lrw=Dg1L.

    Чтобы вывести Lrw, решите обобщенную задачу о собственных значениях Lv=λDgv, где v является вектор-столбцом длины n, и λ является скаляром. Значения λ, которые удовлетворяют уравнению, являются обобщенными собственными значениями матрицы Lrw=Dg1L.

    Можно использовать функцию MATLAB® eigs решить обобщенную задачу о собственных значениях.

  • Нормированная симметричная Матрица Лапласа (Ын-Джордан-Вайс) задана как:

    Ls=Dg1/2LDg1/2.

Используйте 'LaplacianNormalization' аргумент пары "имя-значение", чтобы задать метод, чтобы нормировать Матрицу Лапласа.

Советы

  • Рассмотрите использование спектральной кластеризации, когда кластеры в ваших данных не будут естественно соответствовать выпуклым областям.

  • Из спектрального алгоритма кластеризации можно оценить количество кластеров k как:

    • Количество собственных значений Матрицы Лапласа, которые равны 0.

    • Количество связанных компонентов в вашем представлении графика подобия. Используйте graph создать график подобия из матрицы подобия и использовать conncomp найти количество связанных компонентов в графике.

    Для примера смотрите Оценочное Количество Кластеров и Выполните Спектральную Кластеризацию.

Алгоритмы

Спектральная кластеризация является основанным на графике алгоритмом для кластеризации точек данных (или наблюдения в X). Алгоритм включает построение графика, нахождение его Матрицы Лапласа и использование этой матрицы, чтобы найти, что собственные вектора k разделяют график k пути. По умолчанию, алгоритм для spectralcluster вычисляет нормированную Матрицу Лапласа случайного обхода с помощью метода, описанного Ши-Маликом [2]. spectralcluster также поддерживает ненормированную Матрицу Лапласа и нормированную симметричную Матрицу Лапласа, которая использует метод Ына-Джордана-Вайса [3]. spectralcluster реализации, кластеризирующиеся можно следующим образом:

  1. Для каждой точки данных в X, задайте локальное окружение с помощью или метода поиска радиуса или самого близкого соседнего метода, как задано 'SimilarityGraph' аргумент пары "имя-значение" (см. График Подобия). Затем найдите попарные расстояния Disti,j для всех точек i и j в окружении.

  2. Преобразуйте расстояния до мер по подобию с помощью преобразования ядра Si,j=exp((Disti,jσ)2). Матричный S является матрицей подобия, и σ является масштабным коэффициентом для ядра, как задано использование 'KernelScale' аргумент пары "имя-значение".

  3. Вычислите ненормированную Матрицу Лапласа L, нормированная Матрица Лапласа случайного обхода Lrw или нормированная симметричная Матрица Лапласа Ls, в зависимости от значения 'LaplacianNormalization' аргумент пары "имя-значение".

  4. Создайте матрицу Vn×k содержа столбцы v1,,vk, где столбцы являются собственными векторами k, которые соответствуют k самые маленькие собственные значения Матрицы Лапласа. При использовании Ls нормируйте каждую строку V, чтобы иметь единичную длину.

  5. При обработке каждой строки V как точка кластеризируйтесь, точки n с помощью k - означает кластеризировать (значение по умолчанию) или k-medoids кластеризацию, как задано 'ClusterMethod' аргумент пары "имя-значение".

  6. Присвойте исходные точки в X к тем же кластерам как их соответствующие строки в V.

Ссылки

[1] Фон Люксбург, U. “Пример на Спектральной Кластеризации”. Статистика и Вычисляющий Журнал. Vol.17, Номер 4, 2007, стр 395–416.

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

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

Введенный в R2019b

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