SpectralClustering の変更点 - PukiWiki

RIGHT:2008/10/11
** Spectral Clustering of Graphs [#i940d70f]
固有値問題の解を利用してグラフを分割する問題を考える.
*** 例1 [#n601dc12]
&ref(graph1.png); ~
グラフG=(V,E)のVの部分集合A,Bに対して ~
&mimetex("cut(A,B)=\sum_{x\in A, y\in B} E[x,y]"); とする.
但し, &mimetex("E[x,y]=\begin{cases} 1 & ((x,y)\in E) \\ 0 & ((x,y)\not\in E) \end{cases}"); ~
上図のグラフに対して, いくつか cut(A,V-A) を計算すると ~
|A|V-A|cut(A,V-A)|Ncut(A,V-A)|
|{1}|{2,3,4,5,6}|2|1.16667|
|{1,2}|{3,4,5,6}|2|0.7|
|&color(red){{1,2,3}};|{4,5,6}|&color(red){1};|0.285714|
|{1,2,3,4}|{5,6}|2|0.7|
|{1,2,3,4,5}|{6}|2|1.6667|

※ Aがクラスターであるとは, &color(red){cut(A,V-A)が小さくなるようなAを求めれば良いような気がする.}; ~

*** 例2 [#m3e18cef]
&ref(graph2.png); ~
上図のグラフに対して, いくつか cut(A,V-A) を計算すると ~
|A|V-A|cut(A,V-A)|NCut(A,V-A)|
|{1}|{2,3,4,5,6,7}|&color(orange){2};|1.11111|
|{1,2}|{3,4,5,6,7}|&color(orange){2};|0.625|
|&color(red){{1,2,3}};|{4,5,6,7}|&color(orange){2};|&color(red){0.416667};|
|{1,2,3,4}|{5,6,7}|3|0.606061|
|{1,2,3,4,5}|{6,7}|3|0.8|
|{1,2,3,4,5,6}|{7}|&color(orange){2};|1.11111|

&color(orange){cut(A,V-A)だけではクラスターAを決めれない!}; そこで, Ncut(A,B)を次のように定義する. ~

&mimetex("Ncut(A,B)=\frac{cut(A,B)}{deg(A)} + \frac{cut(A,B)}{deg(B)}"); 但し, deg(A)はAに含まれる頂点の次数の和を表す. ~
※ この標準化された&color(red){Ncut(Normalized cut)の値が小さくなるクラスターAを探せば良さそう.};

*** 例1 (別の視点から) [#y5863040]
&ref(graph1.png); ~
上図のグラフの隣接行列Mと次数を対角成分に持つ行列Dを考える. ~
&mimetex("M=\left( \begin{array}0&1&1&0&0&0\\1&0&1&0&0&0\\1&1&0&1&0&0\\0&0&1&  0&1&1\\0&0&0&1&0&1\\0&0&0&1&1&0\end{array}\right)");
,
&mimetex("D=\left( \begin{array}2&0&0&0&0&0\\0&2&0&0&0&0\\0&0&3&0&0&0\\0&0&0&   3&0&0\\0&0&0&0&2&0\\0&0&0&0&0&2\end{array}\right)"); ~
ベクトル&mimetex("q=(q_1,q_2,\cdots,q_n)");に対して次の評価関数J(q)を考える. ~
&mimetex("J(q)=\frac{q^t(D-M)q}{q^tDq}"); ~
Vの部分集合Aに対して, ベクトルq=q(A)を
&mimetex("q(A)_i=\begin{cases} a & (i \in A) \\ -b & (i \in V-A)\end{cases}");
とする.
但し, &mimetex("a=\sqrt{\frac{deg(V-A)}{deg(A)deg(V)}}");,
&mimetex("b=\sqrt{\frac{deg(A)}{deg(V-A)deg(V)}}"); とする. ~
上手のグラフに対して, いくつかの頂点集合Aに対して, ベクトルq(A)と値J(q(A))を計算してみると
上図のグラフに対して, いくつかの頂点集合Aに対して, ベクトルq(A)と値J(q(A))を計算してみると

|A|q(A)|J(q(A))|
|{1}|{0.654654, -0.109109, -0.109109, -0.109109, -0.109109, -0.109109}|1.16667|
|{1,2}|{0.422577, 0.422577, -0.169031, -0.169031, -0.169031, -0.169031}|0.7|
|{1,2,3}|{0.267261, 0.267261, 0.267261, -0.267261, -0.267261, -0.267261}|0.285714|
|{1,2,3,4}|{0.169031, 0.169031, 0.169031, 0.169031, -0.422577, -0.422577}|0.7|
|{1,2,3,4,5}|{0.109109, 0.109109, 0.109109, 0.109109, 0.109109, -0.654654}|1.6667|

q(A)の値は暗算ではなくMathematicaで計算してますが, Aに含まれる成分要素が正の値(a), それ以外が負の値(-b)であることは, すぐに確認出来ると思います. さらには, 実は... ~
※ &color(red){J(q(A))の値がNcut(A,V-A)の値に等しい!}; (←これは
証明出来る.)

*** まとめ (その1) [#c5e97737]
Ncut(A,V-A)が小さくなるAを求める問題は, J(q)が小さくなるベクトルqを求める問題に還元できる. ~
さらに, &mimetex("J(q)=\frac{q^t(D-M)q}{q^tDq}=\frac{(D^{1/2}q)^t (I-D^{-1/2}MD^{-1/2})(D^{1/2}q)}{(D^{1/2}q)^t(D^{1/2}q)}"); より, ~
&mimetex("z=D^{1/2}q"); , &mimetex("X=I-D^{-1/2}MD^{-1/2}"); とすると ~
&mimetex("F(z)=\frac{z^t X z}{z^t z}"); が小さくなるベクトルzを求める問題に還元できる. ~
F(z)はレイリー商(Rayleigh quotient)と呼ばれ, F(z)の最小値は行列Xの最小の固有値&mimetex(\lambda_1); であり, &mimetex(Xz_1=\lambda_1 z_1); を満たす固有ベクトル&mimetex(z_1);により実現されることが知られている. ~
※ &color(red){F(z)が小さくなるzは固有ベクトルを求めればよい.}; ~
&mimetex(\lambda_1=0); ,
&mimetex("z_1=D^{1/2}(1,1,1,\cdots,1)"); であるが, これはクラスタリング(qの近似)には役立たない. ~
2番目に小さな固有値&mimetex(\lambda_2);に対する固有ベクトル&mimetex(z_2);を求め,
&mimetex(\hat{q}=D^{-1/2}z_2); とすると, これが近似的にJ(q)の最小値を与える.
すなわち, &mimetex("q_i=\begin{cases}a&(\hat{q}_i>0)\\-b&(\hat{q}_i<0)\end{cases}"); で定まるqがJ(q)を小さくすると&color(red){信じる!}; ~
言い換えると, 求めた&mimetex(z_2);の成分の正負によりクラスターAを &mimetex("A=\{i\in V|(z_2)_i > 0\}"); とする.

*** 例1 (別の方法で計算) [#e313e44e]
&ref(graph1.png); ~
&mimetex("D^{1/2}=\left( \begin{array}\sqrt{2}&0&0&0&0&0\\0&\sqrt{2}&0&0&0&0\\0&0&\sqrt{3}&0&0&0\\0&0&0&\sqrt{3}&0&0\\0&0&0&0&\sqrt{2}&0\\0&0&0&0&0&\sqrt{2}\end{array}\right)"); , 
&mimetex("X=I-D^{-1/2}MD^{-1/2}=\left( \begin{array}1&-\frac{1}{2}&-\frac{1}{\sqrt{6}}&0&0&0\\-\frac{1}{2}&1&-\frac{1}{\sqrt{6}}&0&0&0\\-\frac{1}{\sqrt{6}}&-\frac{1}{\sqrt{6}}&1&-\frac{1}{3}&0&0\\0&0&-\frac{1}{3}&1&-\frac{1}{\sqrt{6}}&-\frac{1}{\sqrt{6}}\\0&0&0&-\frac{1}{\sqrt{6}}&1&-\frac{1}{2}\\0&0&0&-\frac{1}{\sqrt{6}}&-\frac{1}{2}&1\end{array}\right)"); ~
Xの固有値と固有ベクトルを求めてみる. ~
|z1|0.0|{1., 1., 1.22474, 1.22474, 1., 1.}|
|z2|0.204666|{&color(orange){-1.};, &color(orange){-1.};, &color(orange){-0.723417};, &color(red){0.723417};, &color(red){1.};, &color(red){1.};}|
|z3|1.6667|{1., 1., -1.63299, -1.63299, 1., 1.}|
|z4|1.5|{-1., 1., 0., 0., 0., 0.}|
|z5|1.5|{0., 0., 0., 0., -1., 1.}|
|z6|1.62867|{-1., -1., 2.76466, -2.76466, 1., 1.}|

z2の成分の正負を見て, &color(orange){{1,2,3}};と&color(red){{4,5,6}};のクラスターに分けることが出来る.

*** 例3 [#wf63ffc8]
&ref(graph3.png); ~
例1のグラフと同型だが頂点番号が違うので隣接行列Mや次数行列Dは異なる. ~
&mimetex("M=\left(\begin{array}0&0&1&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\1&0&1&   0&0&0\\0&1&0&0&0&1\\0&1&0&0&1&0\end{array}\right)"); ,
&mimetex("D=\left( \begin{array}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&3&0&0&0\\0&0&0&   2&0&0\\0&0&0&0&2&0\\0&0&0&0&0&2\end{array}\right)"); ~


&mimetex("X=I-D^{-1/2}MD^{-1/2}"); の固有値と固有ベクトルを求める.

|z2|0.204666|{&color(orange){-1.};, &color(red){0.723417};, &color(orange){-0.723417};, &color(orange){-1.};, &color(red){1.};, &color(red){1.};}|

z2の成分の正負を見て, &color(orange){{1,3,4}};と&color(red){{2,5,6}};のクラスターに分けることが出来る.

*** 例2 (別の方法で計算) [#h4d71791]
&ref(graph2.png); ~

例2のグラフについて, &mimetex("X=I-D^{-1/2}MD^{-1/2}"); の固有値と固有ベクトルを求める. ~

|z1|0.0|{1., 1., 1.41421, 1.22474, 1.41421, 1.22474, 1.}|
|z2|0.272982|{&color(orange){-1.38585};, &color(orange){-1.38585};, &color(orange){-0.889861};, &color(red){0.463162};, &color(red){0.797192};, &color(red){1.09043};, &color(red){1.};}|
|z3|0.923454|{0.420329, 0.420329, -0.503432, -1.08207, -0.0935431, 0.26851, 1.}|
|z4|1.21036|{-1.02785, -1.02785, 2.06515, -2.01748, 3.49906, -3.54555, 1.}|
|z5|1.5|{-1., 1., 0., 0., 0., 0., 0.}|
|z6|1.5|{-1., 0., 1.41421, 0., -1.41421, 0., 1.}|
|z7|1.5932|{0.251126, 0.251126, -0.776492, 1.19437, -0.246958, -1.23917, 1.}|

z2の成分の正負を見て, &color(orange){{1,2,3}};と&color(red){{4,5,6,7}};のクラスターに分けることが出来る.

** まとめ (その2) [#lf61c5f7]
- 2つのクラスターへの分割について ~
固有ベクトルz2の成分の正負による分割をグラフの頂点の分割に対応させた.
一般化すると正負に限らず実数kに対して, 
&mimetex("A(k)=\{i\in V|(z_2)_i > k\}"); によりクラスターを定めることが可能である.
Ncut(A(k),V-A(k))が最小となるkがk=0とは限らないかもしれない.
-- z2の成分を小さい順に並べ替えれば, 全てのA(k)は簡単に求まる.
-- 全てのA(k)に対してNcut(A(k),V-A(k))を計算し, 最小となるA(k)を探す.
- 3つ以上のクラスターへの分割について ~
2つの部分グラフへの分割ではなく複数の部分グラフへの分割も考えられる.
その際, 固有ベクトルz2だけでなく, z3,z4,..も使って, それぞれの第i成分だけから
列ベクトルxiを作り, xiたちの分割を考え, そのiたちに対応してグラフのクラスター分割を
考えることが可能になる.
-- Ncutの拡張のような複数クラスター分割の評価式(Modularity function)が必要.
-- k個のクラスターへの分割にk-1個の固有ベクトルを使う.
-- xiたちの分割にはk-meansアルゴリズムを用いる.

** 例2 (複数クラスターへの分割) [#qebcdef7]
&ref(graph2.png); ~
|||x1|x2|x3|x4|x5|x6|x7|
|z2|0.272982|{&color(orange){-1.38585};,|&color(orange){-1.38585};,|&color(orange){-0.889861};,|&color(red){0.463162};,|&color(red){0.797192};,|&color(red){1.09043};,|&color(red){1.};}|
|z3|0.923454|{&color(red){0.420329};,|&color(red){0.420329};,|&color(orange){-0.503432};,|&color(orange){-1.08207};,|&color(orange){-0.0935431};,|&color(red){0.26851};,|&color(red){1.};}|

z2とz3の成分を並べた列ベクトルを分割する. ~
例えば成分の正負だけに着目して, {1,2},{3},{4,5},{6,7}の4つのクラスターへの分割候補が考えられる.
** (つづく)[#d1f9fd96]
- [[(ymken)/Spectral Clustering]] (内部資料) ~

#counter

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSSPDF