About Spectral Clustering

About Spectral Clustering Univ. of Tsukuba MMA Lab Shunya
Ueta

目次 1.  Spectral Graph 1.  About 2.  Graph
Laplacian Matrix 3.  応用例 2.  Spectral Clustering 3.  実装 2

About Spectral Graph 歴史: 1950年代~ 目的:
グラフの特徴とグラフの固有値・固有ベクトルを結びつける応用例: Spectral Clustering 画像領域分割 3

Graph Laplacian matrix 4 定義: 4 2 3
5 1 [ 0 1 0 1 0 ] [ 1 0 1 1 0 ] [ 0 1 0 0 1 ] [ 1 1 0 0 1 ] [ 0 0 1 1 0 ] [ 2 0 0 0 0 ] [ 0 3 0 0 0 ] [ 0 0 2 0 0 ] [ 0 0 0 3 0 ] [ 0 0 0 0 2 ] AG DG G n頂点無向グラフ G = (V, E) : AG : DG : Gの近接行列 Gの次数行列 LG = DG AG ラプラシアン行列 [ 2 -‐1 0 -‐1 0 ] [ -‐1 3 -‐1 -‐1 0 ] [ 0 -‐1 2 0 -‐1 ] [ -‐1 -‐1 0 3 -‐1 ] [ 0 0 -‐1 -‐1 2 ] LG = =

Spectral Graphの応用例画像領域分割 : 画素毎の類似画像 5

Spectral Graphの応用例画像領域分割 6

Spectral Grapth の応用例 Spectral Clustering 7

Spectral Clustering 8 P次元 n 個 .
. . 目的 p次元のデータn個を kクラスタに分類したいグラフ表現データをグラフで表す Laplacian matrix グラフの行列表現 n n 対称行列固有値集合(スペクトラム)を求める固有ベクトルを小さいものから k番目までを選定 k n

Graph Laplacian matrix 9 定義: 4 2 3
5 1 [ 0 1 0 1 0 ] [ 1 0 1 1 0 ] [ 0 1 0 0 1 ] [ 1 1 0 0 1 ] [ 0 0 1 1 0 ] [ 2 0 0 0 0 ] [ 0 3 0 0 0 ] [ 0 0 2 0 0 ] [ 0 0 0 3 0 ] [ 0 0 0 0 2 ] AG DG G n頂点無向グラフ G = (V, E) : AG : DG : Gの近接行列 Gの次数行列 LG = DG AG ラプラシアン行列 [ 2 -‐1 0 -‐1 0 ] [ -‐1 3 -‐1 -‐1 0 ] [ 0 -‐1 2 0 -‐1 ] [ -‐1 -‐1 0 3 -‐1 ] [ 0 0 -‐1 -‐1 2 ] LG = =

ProperLes of Laplacian matrix 10 1.  Lは部分対角優位行列なので全ての固有値は 0 以上
2.  L の最小固有値は 0 であり、対応する固有ベクトルは全要素1の n 次元ベクトル 3.  固有値0の個数はグラフの連結部の数連結部A 連結部B Laplacian matrix グラフの行列表現対称行列 A B 1 1 1 0 0 0 I 0 = x x 固有値対角行列

ProperLes of Laplacian matrix 11 1.  Lは部分対角優位行列なので全ての固有値は 0 以上
2.  L の最小固有値は 0 であり、対応する固有ベクトルは全要素1の n 次元ベクトル 3.  固有値0の個数はグラフの連結部の数連結部A 連結部B Laplacian matrix グラフの行列表現対称行列 A B 0 0 0 1 1 1 I 0 = x x 固有値対角行列

Spectral Clustering 12 理想的なグラフ状態各行に対して各列の要素がクラスタを示している
k n 1 1 0 0 0 0 0 1 0 0 i番目の行はあるデータX_i が所属するクラスタを示している 0 0 0 １ 1

About Spectral Clustering

About Spectral Clustering

Shunya Ueta

More Decks by Shunya Ueta

Other Decks in Research

Featured

Transcript