スペクトルクラスタリングを使用したデータの分割

このトピックでは、スペクトルクラスタリングについて紹介し、クラスター数の推定とスペクトルクラスタリングを行う例を提供します。

スペクトルクラスタリングの紹介

スペクトルクラスタリングは、データ点または観測値を k 個のクラスターに分割するグラフベースのアルゴリズムです。Statistics and Machine Learning Toolbox™ の関数 spectralcluster は、入力データ行列、またはデータから派生された類似度グラフの類似度行列に対してクラスタリングを実行します。spectralcluster はクラスターインデックス、ラプラシアン行列の k 個の固有ベクトルを含む行列、および固有ベクトルに対応する固有値のベクトルを返します。

spectralcluster では、クラスター数 k を指定しなければなりません。ただし、k の推定が正しいことを次のいずれかの方法で確認することができます。

ラプラシアン行列の固有値ゼロの数を数える。固有値ゼロの多重度はデータに含まれるクラスター数を示します。
MATLAB^® 関数の conncomp を使用して、類似度行列内の連結要素の数を調べる。

アルゴリズムの説明

"スペクトルクラスタリング" は、データ内にある k 個の任意の形状のクラスターを見つけるためのグラフベースのアルゴリズムです。この手法では、データを低次元で表します。低次元では、データ内のクラスターがより広く分離されるため、k-means または k-medoids クラスタリングといったアルゴリズムを使用できます。この低次元は、ラプラシアン行列の k 個の最小固有値に対応する固有ベクトルに基づいています。ラプラシアン行列は、データ点間の局所的な近傍関係をモデル化する類似度グラフを無向グラフとして表す 1 つの方法です。スペクトルクラスタリングアルゴリズムは、類似度グラフを k 個のパーティションに分割するために、データから類似度グラフの類似度行列を派生させ、ラプラシアン行列を見つけ、そのラプラシアン行列を使用して k 個の固有ベクトルを求めます。クラスター数がわかっている場合はスペクトルクラスタリングを使用できますが、このアルゴリズムにはデータ内のクラスター数を推定する方法も用意されています。

既定では、spectralcluster のアルゴリズムは、Shi-Malik[1] によって説明されている方式を使用して、正規化されたランダムウォークラプラシアン行列を計算します。spectralcluster は正規化されていないラプラシアン行列と、Ng-Jordan-Weiss 方式[2]を使用する正規化された対称ラプラシアン行列もサポートします。関数 spectralcluster はクラスタリングを次のように実装します。

名前と値のペアの引数 'SimilarityGraph' で指定されているように、X 内の各データ点に対して、半径探索法または最近傍法のいずれかを使用して局所的な近傍を定義します (類似度グラフを参照)。次に、近傍内のすべての点 i および j のペアワイズ距離 $D i s t_{i, j}$ を求めます。
カーネル変換 $S_{i, j} = \exp (- {(\frac{D i s t_{i, j}}{σ})}^{2})$ を使用して、距離を類似度測定に変換します。名前と値のペアの引数 'KernelScale' を使用して指定されるように、行列 S は類似度行列であり、σ はカーネルのスケール係数です。
名前と値のペアの引数 'LaplacianNormalization' の値に応じて、正規化されていないラプラシアン行列 L、正規化されたランダムウォークラプラシアン行列 L_rw、または正規化された対称ラプラシアン行列 L_s を計算します。
列 $v_{1}, \dots, v_{k}$ が含まれる行列 $V \in ℝ^{n \times k}$ を作成します。この行列の列は、ラプラシアン行列の k 個の最小固有値に対応する k 個の固有ベクトルです。L_s を使用している場合は、V の各行が単位長さをもつように正規化します。
V の各行を点として処理することで、名前と値のペアの引数 'ClusterMethod' で指定されているように、k-means クラスタリング (既定) または k-medoids クラスタリングを使用して n 個の点をクラスタリングします。
X 内の元の点を V 内の対応する行として同じクラスターに割り当てます。

クラスター数の推定とスペクトルクラスタリングの実行

ライブスクリプトを開く

この例では、スペクトルクラスタリングを実行する 2 つのアプローチを示しています。

1 つ目のアプローチは、ラプラシアン行列の固有値を使用してクラスター数を推定し、データセットに対してスペクトルクラスタリングを実行します。
2 つ目のアプローチは、類似度グラフを使用してクラスター数を推定し、類似度行列に対してスペクトルクラスタリングを実行します。

標本データの生成

十分に分離した 3 つのクラスターをもち、各クラスターに 20 個の点が含まれる標本データセットを無作為に生成します。

rng('default'); % For reproducibility
n = 20;
X = [randn(n,2)*0.5+3;
    randn(n,2)*0.5;
    randn(n,2)*0.5-3];

データに対するスペクトルクラスタリングの実行

ラプラシアン行列の固有値を使用してデータ内のクラスター数を推定し、データセットに対してスペクトルクラスタリングを実行します。

関数spectralclusterを使用して、ラプラシアン行列の (大きさが) 最小の固有値を 5 個計算します。既定では、この関数は正規化されたランダムウォークラプラシアン行列を使用します。

[~,V_temp,D_temp] = spectralcluster(X,5)

V_temp = 60×5

    0.2236   -0.0000    0.0000    0.1534   -0.0000
    0.2236   -0.0000    0.0000   -0.3093    0.0000
    0.2236   -0.0000    0.0000    0.2225   -0.0000
    0.2236   -0.0000    0.0000    0.1776   -0.0000
    0.2236   -0.0000    0.0000    0.1331   -0.0000
    0.2236   -0.0000    0.0000    0.2176   -0.0000
    0.2236   -0.0000    0.0000    0.1967    0.0000
    0.2236   -0.0000    0.0000   -0.0088    0.0000
    0.2236   -0.0000    0.0000   -0.2844    0.0000
    0.2236   -0.0000    0.0000   -0.3275    0.0000
      ⋮

D_temp = 5×1

   -0.0000
   -0.0000
   -0.0000
    0.0876
    0.1653

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

関数spectralclusterを使用して、観測値に対してスペクトルクラスタリングを実行します。k=3 個のクラスターを指定します。

k = 3;
[idx1,V,D] = spectralcluster(X,k)

idx1 = 60×1

     1
     1
     1
     1
     1
     1
     1
     1
     1
     1
      ⋮

V = 60×3

    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
    0.2236   -0.0000   -0.0000
      ⋮

D = 3×1
10^-16 ×

   -0.0740
   -0.1589
   -0.3613

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

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

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

Figure contains an axes object. The axes object contains 3 objects of type line. One or more of the lines displays its values using only markers These objects represent 1, 2, 3.

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

関数 spectralcluster を再度使用する代わりに、V_temp を関数 kmeans に渡してデータ点をクラスタリングできます。

idx2 = kmeans(V_temp(:,1:3),3);
gscatter(X(:,1),X(:,2),idx2);

Figure contains an axes object. The axes object contains 3 objects of type line. One or more of the lines displays its values using only markers These objects represent 1, 2, 3.

データ点が同じ方法でクラスタリングされている場合でも、idx1 および idx2 のクラスター割り当ての順序は異なります。

類似度行列に対するスペクトルクラスタリングの実行

類似度グラフを使用してクラスター数を推定し、類似度行列に対してスペクトルクラスタリングを実行します。

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

dist_temp = pdist(X);
dist = squareform(dist_temp);

ペアワイズ距離から類似度行列を作成し、類似度行列が対称であることを確認します。

S = exp(-dist.^2);
issymmetric(S)

ans = logical
   1

ペアワイズ距離が探索半径よりも小さい点のみを類似度グラフが接続するように、類似度の値を 0.5 に制限します。

S_eps = S;
S_eps(S_eps<0.5) = 0;

S からgraphオブジェクトを作成します。

G_eps = graph(S_eps);

類似度グラフを可視化します。

plot(G_eps)

Figure contains an axes object. The axes object contains an object of type graphplot.

関数 unique と関数conncompを使用して、G_eps グラフ内の連結要素の数を特定します。

unique(conncomp(G_eps))

ans = 1×3

     1     2     3

類似度グラフには 3 セットの連結要素が示されています。類似度グラフに含まれる連結要素数によって、データ内のクラスター数を適切に推定できます。そのため、k=3 は X に含まれるクラスター数に適切な選択です。

データセット X から派生された類似度行列に対してスペクトルクラスタリングを実行します。

k = 3;
idx3 = spectralcluster(S_eps,k,'Distance','precomputed');
gscatter(X(:,1),X(:,2),idx3);

Figure contains an axes object. The axes object contains 3 objects of type line. One or more of the lines displays its values using only markers These objects represent 1, 2, 3.

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

参照

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

[2] 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.

参考