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

tmtk

Data Science

2017.11.2

Topics

スペクトラルクラスタリングとは
行列の固有値問題によるグラフの連結成分分解
スペクトラルクラスタリングのアルゴリズムと計算例
関連する話題
まとめ
参考文献

こんにちは、データサイエンスチーム tmtkです。
この記事では、スペクトラルクラスタリング（Spectral Clustering）について説明します。スペクトラルクラスタリングについて、具体的には、

スペクトラルクラスタリングとは
行列の固有値分解によるグラフの連結成分分解の説明
スペクトラルクラスタリングのアルゴリズムと計算例
関連する話題

を説明します。

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

スペクトラルクラスタリングとは、クラスタリングアルゴリズムの一つです。クラスタリングは機械学習の方法のうち、教師なし学習に分類されます。データが与えられたとき、正解データなしでデータを複数の集団に分ける方法です。
スペクトラルクラスタリングの特徴は、データからグラフを生成し、グラフの連結成分分解を応用してクラスタリングするところです。クラスタリングアルゴリズムとして古典的なものに、KMeansやGaussian mixture modelがあります。KMeansやGaussian mixture modelはクラスタの中心点からの距離に基づいてクラスタリングを行いますが、スペクトラルクラスタリングでは連結性に注目してクラスタリングを行うため、KMeansやGaussian mixtureではうまくクラスタリングできなかったようなデータをうまくクラスタリングできることがあります。
comparison to other algorithms
（KMeans, Spectral Clustering, Gaussian Mixtureの比較。画像はscikit-learnのページのプログラムを改変して作成しました。）

行列の固有値問題によるグラフの連結成分分解

スペクトラルクラスタリングのアルゴリズムを説明する前に、その基礎として、行列の固有値問題によってグラフの連結成分分解を行う方法を説明します。
いま、正の重みつき無向グラフ $G=(V = \{ v_1, \ldots, v_n\}, E)$ があるとします。その隣接行列を $W=(w_{ij})$ とします。ここで、 $w_{ij}$ は $w_{ij}=w_{ji}, w_{ii} =0, w_{ij}\geq 0$ であり、 $w_{ij}$ の値が大きいほど頂点 $i, j$ が近いようにします。
たとえば、頂点1と頂点2が重み100の辺でつながっていて、頂点3と頂点4が重み20の辺でつながっているグラフ $G_1$ の場合、
graph
隣接行列 $W$ は
$W=\left(\begin{array}{cccc}0 & 100 & 0 & 0\\100 & 0 & 0 & 0 \\0 & 0 & 0 & 20\\ 0 & 0 & 20 & 0\end{array}\right)$
になります。
隣接行列 $W=(w_{ij})$ に対して、そのdegree matrixを
$D=\left(\begin{array}{ccc}\sum_{j=1}^n w_{1j} & 0 & 0 \\0 & \ddots & 0 \\0 & 0 & \sum_{j=1}^n w_{nj}\end{array}\right)$
で定義します。グラフ $G$ のunnormalized graph Laplacianを
$L=D-W$
で定義します。
グラフ $G_1$ の場合、degree matrix $D$ とunnormalized graph Laplacian $L$ は
$D = \left(\begin{array}{cccc}100 & 0 & 0 & 0\\0 & 100 & 0 & 0 \\0 & 0 & 20 & 0\\ 0 & 0 & 0 & 20\end{array}\right) ,\, L=\left(\begin{array}{cccc}100 & -100 & 0 & 0\\-100 & 100 & 0 & 0 \\0 & 0 & 20 & -20\\ 0 & 0 & -20 & 20\end{array}\right)$
になります。
このとき、次の定理が成り立ちます。

定理

グラフ $G=(V = \{ v_1, \ldots, v_n\}, E)$ が $K$ 個の連結成分をもち、 $V=\{v_1,\ldots,v_{c_1}\}\cup\{v_{c_1+1},\ldots,v_{c_2}\}\cup\cdots\cup\{v_{c_{K-1}+1},\ldots,v_n\}$ と連結成分分解されるとする。このとき、 $G$ のunnormalized graph Laplacian $L$ の固有値はすべて非負の実数である。また、固有値 $0$ に対応する固有空間は、 $(1,\ldots,\stackrel{c_1}{\stackrel{\vee}{1}},0,\ldots,0)^\mathrm{T},(0,\ldots,\stackrel{c_1}{\stackrel{\vee}{0}},\stackrel{c_1+1}{\stackrel{\vee}{1}},\ldots,\stackrel{c_2}{\stackrel{\vee}{1}},0,\ldots,0)^\mathrm{T},\ldots,(0,\ldots,0,,\stackrel{c_{K-1}+1}{\stackrel{\vee}{1}},\ldots,1)^\mathrm{T}$ を基底にもつ。

証明

線形代数からわかります。詳細は参考文献を参照していただくとして、ここでは証明の概略を説明します。
まず、具体的に計算すると、対称行列 $L$ は半正定値行列であることがわかります。また、グラフ $G$ が連結である場合、 $L$ の固有値0に属する固有ベクトルは $(1, \ldots, 1)^\mathrm{T}$ （とそのスカラー倍）のみであることがわかります。グラフが非連結である場合は、グラフの連結成分分解に対応して $L$ が線形写像として直和分解されるので、結論を得ます。
この定理を前の例で計算してみましょう。
$x=\left(\begin{array}{c}x_1 \\x_2 \\x_3 \\x_4\end{array}\right)$
が $L$ の固有値 $0$ に属する固有ベクトルだとすると、
$Lx=0x$
すなわち、
$\left(\begin{array}{cc}100x_1 & -100x_2 \\-100x_1 &+100x_2 \\20x_3& -20x_4 \\-20x_3& +20x_4 \end{array}\right)=0$
が成り立ちます。このことから、固有値0に属する固有空間は $(1,1,0,0)^\mathrm{T},(0,0,1,1)^\mathrm{T}$ を基底にもつことがわかります。（ただし、基底の与え方は一意ではなく、たとえば $(1,1,1,1)^\mathrm{T}, (1,1,0,0)^\mathrm{T}$ も別の基底になっていることに注意します。）
ここから、グラフの連結成分分解を得るには次のようにします。まず、この基底を並べて行列
$U=\left(\begin{array}{cc}1& 0\\1&0\\0&1\\0&1\end{array}\right)$
をつくります。この行列を構成する行ベクトルをそれぞれ見ると、1行目と2行目がどちらも $(1, 0)$ で同じで、3行目と4行目がどちらも $(0, 1)$ で同じです。これはグラフの連結成分分解が $\{v_1, v_2\}, \{v_3, v_4\}$ で与えられることと対応しています。
このようにして、グラフの連結成分を、行列の固有値問題を解くことによって得ることができます。
以上の議論をまとめると、以下の手順によって、グラフの連結成分分解ができることがわかります。

グラフから隣接行列表現 $W$ 、degree matrix $D$ を計算し、unnormalized graph Laplacian $L$ を計算する。
unnormalized graph Laplacian $L$ の固有値0に属する固有空間の基底 $u_1, \ldots, u_K$ を計算する。
基底ベクトルを並べて行列 $U=(u_1 u_2 \cdots u_K)$ を作る。
行列 $U$ のi行目とj行目の行ベクトルが等しければ、頂点 $v_i$ と $v_j$ は同じ連結成分に属し、さもなくば違う連結成分に属している。

AWSのビッグデータ活用・機械学習導入支援サービス

スペクトラルクラスタリングのアルゴリズムと計算例

スペクトラルクラスタリングのアルゴリズムは、上に説明したグラフの連結成分分解を応用したものです。具体的には、以下のようなアルゴリズムで行います。
いま、クラスタ数 $K$ が与えられているとします。

データからグラフを構築する。
グラフから隣接行列表現 $W$ 、degree matrix $D$ を計算し、unnormalized graph Laplacian $L$ を計算する。
unnormalized graph Laplacian $L$ の固有値が小さい順に固有ベクトルを $K$ 個 $u_1, \ldots, u_K$ を計算する。
固有ベクトルを並べて行列 $U=(u_1 u_2 \cdots u_K)$ を作る。
行列 $U$ の行ベクトルをK-meansなどを用いて $K$ 個にクラスタリングする。
K-meansの結果、i行目が入ったクラスタを頂点 $v_i$ の入るクラスタとする。

連結成分分解との相違点は、データからグラフを構築するステップが必要であるところと、連結成分分解のようにi行目とj行目が厳密に等しかったり異なったりしないために、K-meansなどを使う必要があるところです。
具体的に計算をしてみましょう。前のグラフとは少し変えて、次の連結なグラフを考えます。このグラフを $K=2$ 個のクラスタに分類してみます。
graph2
このグラフのunnormalized graph Laplacianは
$L=D-W =\left(\begin{array}{cccc}100&&&\\&101&&\\&&21&\\&&&20\end{array}\right)-\left(\begin{array}{cccc}0&100&&\\100&0&1&\\&1&0&20\\&&20&0\end{array}\right)=\left(\begin{array}{cccc}100&-100&&\\-100&101&-1&\\&-1&21&-20\\&&-20&20\end{array}\right)$
と計算でき、コンピュータを用いて計算すると、その固有値は
$-1.15040601\times 10^{-14}, 0.984903474, 40.5110121, 200.504084$
で、対応する固有ベクトルは、有効数字2桁で四捨五入すると、
$u_1 = \left(\begin{array}{c}1 \\1 \\1 \\1\end{array}\right), \, u_2 = \left(\begin{array}{c}1 \\ 0.99\\ -0.97\\ -1.0\end{array}\right), u_3 = \left(\begin{array}{c}1 \\ 0.59\\ -64\\ 62\end{array}\right), \, u_4 = \left(\begin{array}{c}1\\ -1.0\\ 0.0057\\ -0.00063\end{array}\right)$
です。固有値の小さいほうから固有ベクトルを $K=2$ つとり、並べると、
$U = \left( \begin{array}{cc}1&1\\ 1&0.99\\1&-0.97\\1&-1.0\end{array}\right)$
この4つの行ベクトルをK-meansでクラスタリングしたら、1行目と2行目の $(1,1), (1, 0.99)$ のクラスタと3行目と4行目の $(1, -0.97), (1, -1.0)$ のクラスタに分かれることが予想できます。これは $v_1, v_2$ と $v_3, v_4$ にクラスタリングされることに対応しています。
同様に、 $K=3$ で計算すると、固有値の小さいほうから固有ベクトルを $K=3$ 個とって、
$U = \left( \begin{array}{ccc}1&1&1\\ 1&0.99&0.59\\1&-0.97&-64\\1&-1.0&62\end{array}\right)$
の4つ行ベクトルを3クラスタにK-Meansでクラスタリングすることになります。この場合は $(1,1,1), (1,0.99,0.59)$ のクラスタと $(1,-0.97, -64)$ のクラスタと $(1, -1.0, 62)$ のクラスタに分かれます。これは $v_1, v_2$ と $v_3$ と $v_4$ にクラスタリングされるということで、4つの頂点の中で $v_1, v_2$ の組み合わせが一番近くにあることに対応しています。
four points plot
（よく見ると2点 $(1, 1, 1)$ と $(1, 0.99, 0.59)$ が重なっています。）

まとめ

グラフの連結成分分解を、行列の固有値問題に還元することができます。
固有値問題による連結成分分解を応用したクラスタリングが、スペクトラルクラスタリングです。

参考文献

A Tutorial on Spectral Clusteringがこの分野のテキストの決定版のようです。本記事もこの資料を大いに参考にしています。
Comparing different clustering algorithms on toy datasets – scikit-learn documentationクラスタリングアルゴリズムを比較する画像が面白いです。

テックブログ新着情報のほか、AWSやGoogle Cloudに関するお役立ち情報を配信中！

Follow @twitter