Main Content

このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

spectralcluster

スペクトル クラスタリング

説明

idx = spectralcluster(X,k) は、スペクトル クラスタリング アルゴリズム (アルゴリズムを参照) を使用して、n 行 p 列のデータ行列 X 内の観測値を k 個のクラスターに分割します。spectralcluster は、各観測値のクラスター インデックスが格納されている n 行 1 列のベクトル idx を返します。

idx = spectralcluster(S,k,'Distance','precomputed') は、類似度グラフ類似度行列 (または隣接行列) である S に対するクラスター インデックスのベクトルを返します。S には adjacency の出力を指定できます。

1 番目の入力として類似度行列を使用するには、'Distance','precomputed' を指定しなければなりません。

idx = spectralcluster(___,Name,Value) では、前の構文の入力引数に加えて、1 つ以上の名前と値のペアの引数を使用してオプションを指定します。たとえば、'SimilarityGraph','epsilon' を指定すると、半径探索法を使用して類似度グラフを作成できます。

[idx,V] = spectralcluster(___) は、ラプラシアン行列k 個の最小固有値に対応する固有ベクトル V も返します。

[idx,V,D] = spectralcluster(___) は、ラプラシアン行列の k 個の最小固有値を含むベクトル D も返します。

すべて折りたたむ

既定のユークリッド距離計量でスペクトル クラスタリングを使用して、2 次元の円状データセットをクラスター化します。

ノイズがある 2 つの円が含まれている人工的なデータを生成します。

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

スペクトル クラスタリングを使用して、データ内のクラスターを 2 つ求めます。

idx = spectralcluster(X,2);

クラスタリングの結果を可視化します。

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

Figure contains an axes object. The axes object contains 2 objects of type line. These objects represent 1, 2.

関数 spectralcluster はデータセット内の 2 つのクラスターを正しく識別します。

フィッシャーのアヤメのデータセットから類似度行列を計算し、類似度行列に対してスペクトル クラスタリングを実行します。

フィッシャーのアヤメのデータセットを読み込みます。クラスタリングに考慮される特徴量として花弁の長さと幅を使用します。

load fisheriris
X = meas(:,3:4);
gscatter(X(:,1),X(:,2),species);

Figure contains an axes object. The axes object contains 3 objects of type line. These objects represent setosa, versicolor, virginica.

既定のユークリッド距離計量で関数pdistsquareformを使用して、X に含まれている観測値の各ペア間の距離を求めます。

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);

Figure contains an axes object. The axes object contains 3 objects of type line. These objects represent 1, 2, 3.

クラスタリングの結果を表にします。

tabulate(idx)
  Value    Count   Percent
      1       48     32.00%
      2       50     33.33%
      3       52     34.67%

Percent 列は、3 つのクラスターに割り当てられたデータ点の割合を示しています。

spectralcluster に入力されるデータを使用してスペクトル クラスタリングを繰り返します。'NumNeighbors'size(X,1) に指定します。これは、各点を残りのすべての点に接続して類似度行列 S を作成することに対応します。

idx2 = spectralcluster(X,k,'NumNeighbors',size(X,1),'LaplacianNormalization','symmetric');
gscatter(X(:,1),X(:,2),idx2);

Figure contains an axes object. The axes object contains 3 objects of type line. These objects represent 1, 2, 3.

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);

Figure contains an axes object. The axes object contains 3 objects of type line. These objects represent 1, 2, 3.

ラプラシアン行列の固有値と固有ベクトルを求め、それらの値を使用してクラスタリングの結果を確認します。

十分に分離した 3 つのクラスターをもち、各クラスターに 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]; 

ラプラシアン行列の固有値を使用してデータ内のクラスター数を推定します。ラプラシアン行列の (大きさが) 最小の固有値を 5 個計算します。

[~,~,D_temp] = spectralcluster(X,5)
D_temp = 5×1

   -0.0000
   -0.0000
   -0.0000
    0.0277
    0.0296

最初の 3 つの固有値のみがほぼゼロです。固有値ゼロの数は類似度グラフ内の連結要素の数を適切に示します。つまり、データに含まれるクラスターの数を適切に推定しています。そのため、k=3X に含まれるクラスター数を適切に推定しています。

k=3 のクラスターを求め、ラプラシアン行列の 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.3498
   -0.3857
   -0.3962

D の要素はラプラシアン行列の 3 個の最小固有値に対応します。V の列には D の固有値に対応する固有ベクトルが含まれています。十分に分離されたクラスターの場合、固有ベクトルはインジケーターのベクトルです。特定のクラスターに属さない点の固有ベクトルの値はゼロ (またはゼロに近い値) になり、特定のクラスターに属する点については非ゼロの値になります。

クラスタリングの結果を可視化します。

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

Figure contains an axes object. The axes object contains 3 objects of type line. These objects represent 1, 2, 3.

入力引数

すべて折りたたむ

入力データ。n 行 p 列の数値行列を指定します。X の行は観測値 (点) に、列は変数に対応します。

NaNX の欠損データとして扱われ、最低 1 つの NaN を含む X の任意の行を無視します。関数 spectralcluster は、出力引数 idx および V の対応する行に NaN の値を返します。

データ型: single | double

類似度行列。n 行 n 列の対称行列として指定します。n は観測値の個数です。類似度行列 (または隣接行列) は、データ点間の局所的な近傍関係をモデル化することで入力データを表します。類似度行列内の値は、類似度グラフ内で接続しているノード (データ点) 間のエッジ (または接続) を表します。詳細は、類似度行列を参照してください。

SNaN 値を含んではなりません。

spectralcluster の 1 番目の入力として類似度行列を使用するには、'Distance','precomputed' を指定しなければなりません。

データ型: single | double

データ内のクラスターの数。正の整数として指定します。

クラスターの数を推定する方法の詳細については、ヒントを参照してください。

データ型: single | double

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名、Value は対応する値です。名前と値の引数は他の引数の後ろにする必要がありますが、ペアの順序は関係ありません。

R2021a より前では、名前と値をそれぞれコンマを使って区切り、Name を引用符で囲みます。

例: spectralcluster(X,3,'SimilarityGraph','epsilon','Radius',5) は、3 つのクラスターを指定し、探索半径 5 で半径探索法を使用して類似度グラフを作成します。

距離計量。'Distance' と次の表で説明されている文字ベクトル、string スカラーまたは関数ハンドルから構成されるコンマ区切りのペアとして指定します。

説明
'precomputed'

事前計算済みの距離。spectralcluster に対する 1 番目の入力が類似度行列 S である場合、このオプションを指定しなければなりません。

'euclidean'

ユークリッド距離 (既定)

'seuclidean'

標準化されたユークリッド距離。観測値間の各座標差は、X から計算された標準偏差の対応する要素で除算することによりスケーリングされます。名前と値のペアの引数 Scale を使用して、異なるスケーリング係数を指定します。

'mahalanobis'

X の標本共分散を使用したマハラノビス距離、C = cov(X,'omitrows')。名前と値のペアの引数 Cov を使用して、異なる共分散行列を指定します。

'cityblock'

市街地距離

'minkowski'

ミンコフスキー距離。既定の指数は 2 です。名前と値のペアの引数 P を使用して、別の指数を指定します。P は正のスカラー値です。

'chebychev'

チェビシェフ距離 (最大座標差)

'cosine'

1 から、ベクトルとして扱われる観測間の夾角の余弦を減算

'correlation'

1 から、観測値間の標本相関を減算 (値の系列として処理)

'hamming'

ハミング距離 (異なる座標の比率)

'jaccard'

1 からジャカード係数 (異なる非ゼロ座標の比率) を減算

'spearman'

1 から観測値間の標本スピアマン順位相関係数を減算 (値の系列として処理)

@distfun

カスタム距離関数のハンドル。距離関数の形式は次のようになります。

function D2 = distfun(ZI,ZJ)
% calculation of distance
...
ここで、

  • ZI は、単一の観測値が含まれている 1n 列のベクトルです。

  • ZJ は、複数の観測値が含まれている m2n 列の行列です。distfun は、任意の個数の観測値が含まれている行列 ZJ を受け入れなければなりません。

  • D2m21 列の距離のベクトルであり、D2(k) は観測値 ZIZJ(k,:) の間の距離です。

データがスパースでない場合、通常は関数ハンドルではなく組み込みの距離を使用する方が高速に距離を計算できます。

詳細は、距離計量を参照してください。

'seuclidean''minkowski' または 'mahalanobis' 距離計量を使用する場合、追加の名前と値のペアの引数 'Scale''P' または 'Cov' をそれぞれ指定して、距離計量を制御することができます。

例: spectralcluster(X,5,'Distance','minkowski','P',3) は、5 個のクラスターを指定し、クラスタリング アルゴリズムを実行するために指数 3 のミンコフスキー距離計量を使用するよう指定します。

ミンコフスキー距離計量の指数。'P' と正のスカラー値をコンマで区切って指定します。

この引数は、'Distance''minkowski' である場合のみ有効です。

例: 'P',3

データ型: single | double

マハラノビス距離計量の共分散行列。'Cov' と正定値行列から構成されるコンマ区切りのペアとして指定します。

この引数は、'Distance''mahalanobis' である場合のみ有効です。

例: 'Cov',eye(4)

データ型: single | double

標準化されたユークリッド距離計量のスケール係数。'Scale' と非負値の数値ベクトルから構成されるコンマ区切りのペアとして指定します。

X の各次元 (列) には対応する Scale の値があるので、Scale の長さは p (X の列数) です。spectralcluster は、X の各次元について、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 の最近傍であるか、j が i の最近傍であるかのいずれかの場合に、i と j の 2 つの点を接続します。

このオプションでは、類似度行列がより密に表現されます。

'mutual'

i が j の最近傍であり、かつ j が i の最近傍である場合に、i と j の 2 つの点を接続します。

このオプションでは、類似度行列がより希薄に表現されます。

この引数は、'SimilarityGraph''knn' である場合のみ有効です。

例: 'KNNGraphType','mutual'

類似度グラフの作成に使用される最近傍の探索半径。'Radius' と非負のスカラーで構成されるコンマ区切りのペアとして指定します。

'SimilarityGraph''epsilon' の場合、この引数を指定しなければなりません。詳細は、類似度グラフを参照してください。

例: 'Radius',5

データ型: single | double

カーネルのスケール係数。'KernelScale''auto' または正のスカラーで構成されるコンマ区切りのペアとして指定します。距離を類似度測定に変換するために、スケール係数が使用されます。詳細は、類似度グラフを参照してください。

  • 'auto' オプションは、'euclidean' および 'seuclidean' の距離計量でのみサポートされます。

  • 'auto' を指定した場合、ヒューリスティック手法を使用して適切なスケール係数が選択されます。このヒューリスティック手法では副標本抽出を使用するので、呼び出すたびに推定値が変化する可能性があります。結果を再現するには、spectralcluster を呼び出す前に rng を使用して乱数シードを設定します。

この引数は、'Distance''precomputed' でない場合のみ有効です。

例: 'KernelScale','auto'

データ型: double | single | char | string

ラプラシアン行列 L を正規化する方式。'LaplacianNormalization' と次のいずれかの値から構成されるコンマ区切りのペアとして指定します。

説明
'none'

正規化なしでラプラシアン行列 L を使用します。

'randomwalk'

(既定) 正規化されたランダムウォーク ラプラシアン行列 Lrw (Shi-Malik [2]) を使用します。

Lrw=Dg1L.

行列 Dg次数行列です。

'symmetric'

正規化された対称ラプラシアン行列 Ls (Ng-Jordan-Weiss [3]) を使用します。

Ls=Dg1/2LDg1/2.

行列 Dg は次数行列です。

詳細は、ラプラシアン行列を参照してください。

例: 'LaplacianNormalization','randomwalk'

ラプラシアン行列の固有ベクトルをクラスタリングするためのクラスタリング手法。'ClusterMethod''kmeans' または 'kmedoids' のいずれかで構成されるコンマ区切りのペアとして指定します。

  • 'kmeans' — 関数 kmeans を使用して k-means クラスタリングを実行します。

  • 'kmedoids' — 関数 kmedoids を使用して k-medoid クラスタリングを実行します。

kmeanskmedoids のアルゴリズムにはランダム性があります。そのため、spectralcluster の結果を再現するには、rng を使用して乱数発生器のシードを設定しなければなりません。

例: 'ClusterMethod','kmedoids'

出力引数

すべて折りたたむ

クラスター インデックス。数値列ベクトルとして返されます。idx の行数は n であり、idx の各行は X 内の対応する行 (または観測値) のクラスター割り当てを示します。

データ型: double

固有ベクトル。n 行 k 列の数値行列として返されます。V の列は、ラプラシアン行列k 個の最小固有値に対応する固有ベクトルです。これらの固有ベクトルは、クラスターがより広く分離された新しい空間における、入力データ X の低次元表現です。

十分に分離されたクラスターの場合、固有ベクトルはインジケーターのベクトルです。つまり、特定のクラスターに属さない点の固有ベクトルの値はゼロ (またはゼロに近い値) になり、特定のクラスターに属する点については非ゼロの値になります。

データ型: single | double

固有値。ラプラシアン行列の k 個の最小固有値を含む k 行 1 列の数値ベクトルとして返されます。D の固有値ゼロの数は類似度グラフ内の連結要素の数を示します。つまり、データに含まれるクラスターの数を適切に推定しています。

データ型: single | double

詳細

すべて折りたたむ

類似度グラフ

類似度グラフは、X のデータ点間の局所的な近傍関係を無向グラフとしてモデル化します。グラフ内のノードはデータ点を表し、無向のエッジはデータ点間の接続を表します。

任意の 2 つのノード i および j 間のペアワイズ距離 Disti,j が正である (またはあるしきい値よりも大きい) 場合、類似度グラフはエッジ[1]を使用して 2 つのノードを接続します。2 つのノード間のエッジは、ペアワイズ類似度 Si,j によって重み付けされます。ここで、指定されたカーネル スケール σ の値に対して Si,j=exp((Disti,jσ)2) です。

spectralcluster は、以下の 2 つの類似度グラフ作成方式をサポートしています。

  • "最近傍" 法 ('SimilarityGraph''knn' の場合 (既定)): spectralclusterX の最近傍である点を接続します。名前と値のペアの引数 'NumNeighbors' および 'KNNGraphType' を使用して、最近傍グラフを作成するオプションを指定できます。

    • 'NumNeighbors' を使用して、最近傍の個数を指定します。

    • 'KNNGraphType' を使用して、点の接続を 'complete' にするか 'mutual' にするか指定します。

  • "半径探索" 法 ('SimilarityGraph''epsilon' の場合): spectralcluster はペアワイズ距離が探索半径未満である点を接続します。名前と値のペアの引数 'Radius' を使用して、類似度グラフの作成に使用される最近傍の探索半径を指定しなければなりません。

類似度行列

類似度行列は、類似度グラフの行列表現です。n 行 n 列の行列 S=(Si,j)i,j=1,,n には、類似度グラフで接続しているノード間のペアワイズ類似度の値が含まれます。グラフの類似度行列は、隣接行列とも呼ばれます。

類似度グラフのエッジが無向であるため、類似度行列は対称です。Si,j = 0 の値は、類似度グラフのノード i と j が接続していないことを意味します。

次数行列

次数行列 Dg は、類似度行列 S の行を合計することで得られる n 行 n 列の対角行列です。つまり、Dg の i 番目の対角要素は Dg(i,i)=j=1nSi,j. です。

ラプラシアン行列

ラプラシアン行列は、類似度グラフを表す 1 つの方法です。関数 spectralcluster は、正規化されていないラプラシアン行列、Shi-Malik 方式[2]を使用する正規化されたラプラシアン行列、Ng-Jordan-Weiss 方式[3]を使用する正規化されたラプラシアン行列をサポートしています。

  • "正規化されていないラプラシアン行列" L は、次数行列類似度行列の差です。

    L=DgS.

  • "正規化されたランダムウォーク ラプラシアン行列 (Shi-Malik)" は次のように定義されます。

    Lrw=Dg1L.

    Lrw を導き出すには、一般化固有値問題 Lv=λDgv を解きます。ここで、v は長さ n の列ベクトルで、λ はスカラーです。この方程式を満たす λ の値は、行列 Lrw=Dg1L. の一般化された固有値です。

    MATLAB® 関数 eigs を使用して一般化固有値問題を解くことができます。

  • "正規化された対称ラプラシアン行列 (Ng-Jordan-Weiss)" は次のように定義されます。

    Ls=Dg1/2LDg1/2.

名前と値のペアの引数 'LaplacianNormalization' を使用して、ラプラシアン行列を正規化する方式を指定します。

ヒント

  • データ内のクラスターが凸領域に自然に対応しないとき、スペクトル クラスタリングの使用を検討してください。

  • スペクトル クラスタリング アルゴリズムにより、クラスター数 k を次のように推定できます。

    • 0 に等しいラプラシアン行列の固有値の数。

    • 類似度グラフ表現内の連結要素の数。graph を使用して、類似度行列から類似度グラフを作成し、conncomp を使用してグラフ内の連結要素の数を求めます。

    たとえば、クラスター数の推定とスペクトル クラスタリングの実行を参照してください。

アルゴリズム

スペクトル クラスタリングは、データ点 (または X 内の観測値) をクラスタリングするグラフベースのアルゴリズムです。アルゴリズムには、グラフの作成、そのラプラシアン行列の特定、この行列を使用した k 通りにグラフを分割する k 個の固有ベクトルの特定が含まれます。既定では、spectralcluster のアルゴリズムは、Shi-Malik[2]によって説明されている方式を使用して、正規化されたランダムウォーク ラプラシアン行列を計算します。spectralcluster は正規化されていないラプラシアン行列と、Ng-Jordan-Weiss 方式[3]を使用する正規化された対称ラプラシアン行列もサポートします。spectralcluster はクラスタリングを次のように実装します。

  1. 名前と値のペアの引数 'SimilarityGraph' で指定されているように、X 内の各データ点に対して、半径探索法または最近傍法のいずれかを使用して局所的な近傍を定義します (類似度グラフを参照)。次に、近傍内のすべての点 i および j のペアワイズ距離 Disti,j を求めます。

  2. カーネル変換 Si,j=exp((Disti,jσ)2) を使用して、距離を類似度測定に変換します。名前と値のペアの引数 'KernelScale' を使用して指定されるように、行列 S は類似度行列であり、σ はカーネルのスケール係数です。

  3. 名前と値のペアの引数 'LaplacianNormalization' の値に応じて、正規化されていないラプラシアン行列 L、正規化されたランダムウォーク ラプラシアン行列 Lrw、または正規化された対称ラプラシアン行列 Ls を計算します。

  4. v1,,vk が含まれる行列 Vn×k を作成します。この行列の列は、ラプラシアン行列の k 個の最小固有値に対応する k 個の固有ベクトルです。Ls を使用している場合は、V の各行が単位長さをもつように正規化します。

  5. V の各行を点として処理することで、名前と値のペアの引数 'ClusterMethod' で指定されているように、k-means クラスタリング (既定) または k-medoids クラスタリングを使用して n 個の点をクラスタリングします。

  6. X 内の元の点を V 内の対応する行として同じクラスターに割り当てます。

参照

[1] Von Luxburg, U. “A Tutorial on Spectral Clustering.” Statistics and Computing Journal. Vol.17, Number 4, 2007, pp. 395–416.

[2] Shi, J., and J. Malik. “Normalized cuts and image segmentation.” IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 22, 2000, pp. 888–905.

[3] Ng, A.Y., M. Jordan, and Y. Weiss. “On spectral clustering: Analysis and an algorithm.” In Proceedings of the Advances in Neural Information Processing Systems 14. MIT Press, 2001, pp. 849–856.

バージョン履歴

R2019b で導入