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

こんにちは、データサイエンスチーム 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 LaplacianLの固有値はすべて非負の実数である。また、固有値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\}で与えられることと対応しています。
このようにして、グラフの連結成分を、行列の固有値問題を解くことによって得ることができます。

以上の議論をまとめると、以下の手順によって、グラフの連結成分分解ができることがわかります。

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

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

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

  1. データからグラフを構築する。
  2. グラフから隣接行列表現W、degree matrixDを計算し、unnormalized graph LaplacianLを計算する。
  3. unnormalized graph LaplacianLの固有値が小さい順に固有ベクトルをKu_1, \ldots, u_Kを計算する。
  4. 固有ベクトルを並べて行列U=(u_1 u_2 \cdots u_K)を作る。
  5. 行列Uの行ベクトルをK-meansなどを用いてK個にクラスタリングする。
  6. 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_2v_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_2v_3v_4にクラスタリングされるということで、4つの頂点の中でv_1, v_2の組み合わせが一番近くにあることに対応しています。
four points plot
(よく見ると2点(1, 1, 1)(1, 0.99, 0.59)が重なっています。)

関連する話題

スペクトラルクラスタリングではまずデータをグラフに変換します。グラフへの変換の仕方はいろいろあり、

  • ε近傍法
  • k近傍法
  • 全結合法

などがあるようです。ユークリッド空間上の距離関数をdとすると、データx_1, x_2の間の辺の重みは\exp(-d(x_1, x_2)^2/2\sigma^2)などで与えることができます。さらに、行列を疎にするためのε近傍法やk近傍法などを用いるとよい、ということのようです。

また、graph Laplacian Lにはいろいろな亜種があり、
L_{sym} = D^{-1/2}LD^{1/2}

L_{rw} = D^{-1}L
などが使われるようです。どちらも L と似た性質を持ちます。

まとめ

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

参考文献

AWS利用料$100ドル無料

あなたにおすすめの記事