SpectralClustering - PukiWiki
2008/10/11

Spectral Clustering of Graphs

固有値問題の解を利用してグラフを分割する問題を考える.

例1

graph1.png
グラフG=(V,E)のVの部分集合A,Bに対して
とする. 但し,
上図のグラフに対して, いくつか cut(A,V-A) を計算すると

AV-Acut(A,V-A)Ncut(A,V-A)
{1}{2,3,4,5,6}21.16667
{1,2}{3,4,5,6}20.7
{1,2,3}{4,5,6}10.285714
{1,2,3,4}{5,6}20.7
{1,2,3,4,5}{6}21.6667

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

例2

graph2.png
上図のグラフに対して, いくつか cut(A,V-A) を計算すると

AV-Acut(A,V-A)NCut(A,V-A)
{1}{2,3,4,5,6,7}21.11111
{1,2}{3,4,5,6,7}20.625
{1,2,3}{4,5,6,7}20.416667
{1,2,3,4}{5,6,7}30.606061
{1,2,3,4,5}{6,7}30.8
{1,2,3,4,5,6}{7}21.11111

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

但し, deg(A)はAに含まれる頂点の次数の和を表す.
※ この標準化されたNcut(Normalized cut)の値が小さくなるクラスターAを探せば良さそう.

例1 (別の視点から)

graph1.png
上図のグラフの隣接行列Mと次数を対角成分に持つ行列Dを考える.
,
ベクトル に対して次の評価関数J(q)を考える.

Vの部分集合Aに対して, ベクトルq=q(A)を とする. 但し, , とする.
上図のグラフに対して, いくつかの頂点集合Aに対して, ベクトルq(A)と値J(q(A))を計算してみると

Aq(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)であることは, すぐに確認出来ると思います. さらには, 実は...
J(q(A))の値がNcut(A,V-A)の値に等しい! (←これは 証明出来る.)

まとめ (その1)

Ncut(A,V-A)が小さくなるAを求める問題は, J(q)が小さくなるベクトルqを求める問題に還元できる.
さらに, より,
, とすると
が小さくなるベクトルzを求める問題に還元できる.
F(z)はレイリー商(Rayleigh quotient)と呼ばれ, F(z)の最小値は行列Xの最小の固有値 であり, を満たす固有ベクトル により実現されることが知られている.
F(z)が小さくなるzは固有ベクトルを求めればよい.
, であるが, これはクラスタリング(qの近似)には役立たない.
2番目に小さな固有値 に対する固有ベクトル を求め, とすると, これが近似的にJ(q)の最小値を与える. すなわち, で定まるqがJ(q)を小さくすると信じる!
言い換えると, 求めた の成分の正負によりクラスターAを とする.

例1 (別の方法で計算)

graph1.png
,
Xの固有値と固有ベクトルを求めてみる.

z10.0{1., 1., 1.22474, 1.22474, 1., 1.}
z20.204666{-1., -1., -0.723417, 0.723417, 1., 1.}
z31.6667{1., 1., -1.63299, -1.63299, 1., 1.}
z41.5{-1., 1., 0., 0., 0., 0.}
z51.5{0., 0., 0., 0., -1., 1.}
z61.62867{-1., -1., 2.76466, -2.76466, 1., 1.}

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

例3

graph3.png
例1のグラフと同型だが頂点番号が違うので隣接行列Mや次数行列Dは異なる.
,

の固有値と固有ベクトルを求める.

z20.204666{-1., 0.723417, -0.723417, -1., 1., 1.}

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

例2 (別の方法で計算)

graph2.png

例2のグラフについて, の固有値と固有ベクトルを求める.

z10.0{1., 1., 1.41421, 1.22474, 1.41421, 1.22474, 1.}
z20.272982{-1.38585, -1.38585, -0.889861, 0.463162, 0.797192, 1.09043, 1.}
z30.923454{0.420329, 0.420329, -0.503432, -1.08207, -0.0935431, 0.26851, 1.}
z41.21036{-1.02785, -1.02785, 2.06515, -2.01748, 3.49906, -3.54555, 1.}
z51.5{-1., 1., 0., 0., 0., 0., 0.}
z61.5{-1., 0., 1.41421, 0., -1.41421, 0., 1.}
z71.5932{0.251126, 0.251126, -0.776492, 1.19437, -0.246958, -1.23917, 1.}

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

まとめ (その2)

  • 2つのクラスターへの分割について
    固有ベクトルz2の成分の正負による分割をグラフの頂点の分割に対応させた. 一般化すると正負に限らず実数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 (複数クラスターへの分割)

graph2.png

x1x2x3x4x5x6x7
z20.272982{-1.38585,-1.38585,-0.889861,0.463162,0.797192,1.09043,1.}
z30.923454{0.420329,0.420329,-0.503432,-1.08207,-0.0935431,0.26851,1.}

z2とz3の成分を並べた列ベクトルを分割する.
例えば成分の正負だけに着目して, {1,2},{3},{4,5},{6,7}の4つのクラスターへの分割候補が考えられる.

(つづく)

Counter: 9569, today: 1, yesterday: 0

添付ファイル: filegraph3.png 949件 [詳細] filegraph2.png 971件 [詳細] filegraph1.png 930件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSSPDF
Last-modified: 2008-10-11 (土) 21:16:35 (3266d)