スペクトラル?クラスタリング
- 1. 1/25 スペクトラル?クラスタリング 宮澤 彬 総合研究大学院大学 博士前期 1 年 miyazawa-a@nii.ac.jp September 15, 2015
- 4. 3/25 動機 グラフの連結構造を活用すればクラスタリングの精度が向上する．以下 の図は，k 平均法ではうまくいかないが，スペクトラル?クラスタリン グでは期待通りのクラスタが得られる例である．この図は Murphy (2012) から引用した． ?6 ?4 ?2 0 2 4 6 ?5 ?4 ?3 ?2 ?1 0 1 2 3 4 5 k?means clustering x y ?6 ?4 ?2 0 2 4 6 ?5 ?4 ?3 ?2 ?1 0 1 2 3 4 5 spectral clustering x y 切断の問題は，グラフ理論の分野で既に多くの研究結果があり，それら を使うことができるという利点もある．
- 5. 4/25 グラフとは グラフは，頂点と呼ばれる対象からなる有限非空集合 V と，辺と呼ば れる対象からなる集合 E の組 (V, E) である．辺とは，V の異なる 2 つ の元の非順序対である．辺 {vi, vj} を eij のように書く． 例えば以下のグラフを図示すると下の図のようになる． G = (V, E) , V = {v1, v2, v3, v4, v5} , E = {e13, e14, e24, e25, e35} v1 v2 v3 v4 v5
- 6. 5/25 行列によるグラフの表現 A = (aij) = 1E (eij) とすれば，グラフの辺の構造を行列で表現するこ とができる．この A を隣接行列 (adjacency matrix) と呼ぶ． v1 v2 v3 v4 A = ? ? ? ? 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 ? ? ? ?
- 7. 6/25 行列によるグラフの表現 データ x1, . . . , xn に頂点 v1, . . . , vn を対応させる．2 つのデータ xi, xj の類似度 sij によっての辺 eij に重み wij ≥ 0 を付与する．このとき n 次実対称行列 W = (wij) を重み付き隣接行列 (weighted adjacency matrix) と呼ぶ． v1 v2 v3 v4 0.5 1.2 0.7 W = ? ? ? ? 0 0.5 0 0 0.5 0 1.2 0.7 0 1.2 0 0 0 0.7 0 0 ? ? ? ?
- 8. 7/25 行列によるグラフの表現 グラフの分割を考えるにあたり，重み付き隣接行列の他に，次数行列と いう行列も必要になるのでここで紹介しておく． 任意の頂点 vi ∈ {v1, . . . , vn} について，その次数 (degree) を di = n j=1 wij と定める．次数を対角成分に持つ n 次正方行列 D = (diδij) を次数行列 (degree matrix) と呼ぶ．ただし δij はクロネッカーのデルタである．
- 9. 8/25 重み付き隣接行列と次数行列 v1 v2 v3 v4 v5 0.8 0.1 0.1 0.1 0.4 0.2 0.2 0.9 0.7 0.8 D = ? ? ? ? ? ? 1.1 0 0 0 0 0 1.6 0 0 0 0 0 2.1 0 0 0 0 0 2 0 0 0 0 0 1.8 ? ? ? ? ? ? , W = ? ? ? ? ? ? 0 0.8 0.1 0.1 0.1 0.8 0 0.4 0.2 0.2 0.1 0.4 0 0.9 0.7 0.1 0.2 0.9 0 0.8 0.1 0.2 0.7 0.8 0 ? ? ? ? ? ?
- 10. 9/25 Cut とは どこで切断するかを決めるため，以下で定められる量を考えよう． cut A, A = (i,j) ; vi∈A, vj ∈A wij (1) ここで A = V A である．(1) はクラスター A と A を結ぶ重みの総和で あり，これが小さくなるように切断するのが望ましいと考えられる．
- 11. 10/25 Cut の例 A1 := {v1, v2} とする． v1 v2 v3 v4 v5 0.8 0.1 0.1 0.1 0.4 0.2 0.2 0.9 0.7 0.8 cut A1, A1 = w13 + w14 + w15 + w23 + w24 + w25 = 0.1 + 0.1 + 0.1 + 0.4 + 0.2 + 0.2 = 1.1
- 12. 11/25 Cut の例 A2 := {v1, v2, v3} とする． v1 v2 v3 v4 v5 0.8 0.1 0.1 0.1 0.4 0.2 0.2 0.9 0.7 0.8 cut A2, A2 = w14 + w15 + w24 + w25 + w34 + w35 = 0.1 + 0.1 + 0.2 + 0.2 + 0.9 + 0.7 = 2.2 > cut A1, A1
- 13. 12/25 Cut の例 この基準には，1 つの頂点と残りの頂点全部，という分割になりやすい 傾向がある．以下は A3 := {v1} とした例である． v1 v2 v3 v4 v5 0.8 0.1 0.1 0.1 0.4 0.2 0.2 0.9 0.7 0.8 cut A3, A3 = w12 + w13 + w14 + w15 = 0.8 + 0.1 + 0.1 + 0.1 = 1.1 = cut A1, A1
- 14. 13/25 NCut この問題を解決するため新しく normalized cut という基準を導入す る．これは次の値 NCut A, A := cut A, A vol A + cut A, A vol A が小さいほうが好ましいとする方法である．ただし vol A = {i ; vi∈A} di = {i ; vi∈A} {j ; vj ∈V } wij である．上で見た例について，これを計算すると NCut A1, A1 = 1.1 1.1 + 1.6 + 1.1 2.1 + 2 + 1.8 = 946 1593 < 1, NCut A3, A3 = 1.1 1.1 + 1.1 1.6 + 2.1 + 2 + 1.8 = 1 + 11 75 > 1 となり，より均衡がとれている A1 が好ましいとされる．
- 15. 14/25 NCut 一般に A1, . . . , Ak について NCut (A1, . . . , Ak) = k i=1 cut Ai, Ai vol Ai と定める． 今までの話から，グラフの切断の問題は次の最適化問題に帰着させら れる． minimize A1,...,Ak NCut (A1, . . . , Ak) (2) しかし，これは NP 困難であることが知られている．
- 16. 15/25 グラフ?ラプラシアン そこでグラフ?ラプラシアンというものを導入し，(2) を少し書き換え ることを試みる．グラフ?ラプラシアンは L := D ? W で与えられる． 定義からすぐに以下の性質が分かる． L は n 次実対称行列である． L の固有値 0 と，それに対応する固有ベクトル 1 = (1 · · · 1) ∈ Rn をもつ．
- 17. 16/25 グラフ?ラプラシアンの性質 補題 任意のベクトル f ∈ Rn について以下が成り立つ． f Lf = 1 2 n i,j=1 wij (fi ? fj) 2 . 証明 f Lf = f Df ? f Wf = n i=1 dif2 i ? n i,j=1 fifjwij = ? ? n i=1 dif2 i ? n i,j=1 fifjwij + 2 j=1 djf2 j ? ? = 1 2 n i,j=1 wij (fi ? fj) 2
- 18. 17/25 グラフ?ラプラシアンの性質 任意の Aκ ? V に対して，hκ := (h1,κ · · · hn,κ) ∈ Rn を以下で定める． hi,κ := 1Aκ (vi) √ vol Aκ すると以下が成り立つ． hκLhκ = 1 2 n i,j=1 wij (hi,κ ? hj,κ) 2 = 1 2 (i,j) ; vi∈Aκ, vj ∈Aκ wij 1 √ vol Aκ 2 + 1 2 (i,j) ; vi∈Aκ, vj ∈Aκ wij 1 vol Aκ 2 = cut Aκ, Aκ vol Aκ .
- 19. 18/25 問題の再定式化 さらに以下が成り立つ． hιDhκ = n i=1 dihi,ιhi,κ = n i=1 di 1Aι (vi) 1Aκ (vi) √ vol Aι √ vol Aκ = 1 √ vol Aι √ vol Aκ {i ; vi∈Aι∩Aκ} di = δικ. よって (2) は以下のように書き換えられる． minimize A1,...,Ak?V tr (H LH) subject to H DH = I (3)
- 20. 19/25 問題の再定式化 しかし (3) は依然として NP 困難であるから，H が Rn×k を動くものと する．すなわち minimize H∈Rn×k tr (H LH) subject to H DH = I (4) を解くことにする． 解きやすくするため，以下では T := D1/2 H と置いた minimize T ∈Rn×k tr T D?1/2 LD?1/2 T subject to T T = I (5) を考える．
- 21. 20/25 2 次形式に関する不等式 定理 行列 A ∈ Cn×n をエルミート行列とし，その固有値を λ1, . . . , λn， 対応する固有ベクトルを u1, . . . , un, ui, uj = δij とする 1 ．このとき 固有値について λ1 ≤ λ2 ≤ · · · ≤ λn が成り立っているならば，任意の q ∈ {1, . . . , n} と任意の正規直交系 {x1, . . . , xq ; xi ∈ Cn , xi, xj = δij} に対して q i=1 λi ≤ q i=1 xiAxi (6) が成り立つ．さらに xi = ui (i = 1, . . . , q) ならば，(6) において等号が 成立する． 証明 例えば Simovici and Djeraba (2008) を参照せよ． 1 エルミート行列の固有ベクトルはそれぞれ互いに直交する． λi ui, uj = λiui, uj = Aui, uj = ui, A? uj = ui, λjuj = λj ui, uj エルミート行列の固有値は実数なので λi = λj ならば，λi = λj となり， ui, uj = 0．
- 22. 21/25 最適化問題の解 前のページの定理により (5) の解が求めることができる．つまり，行列 D?1/2 LD?1/2 の固有値を小さいほうから λ1, . . . , λn と並べ，それぞれ に対応する正規化された固有ベクトルを u1, . . . , un とするとき， T = (u1 · · · uk) とすれば tr T D?1/2 LD1/2 T が最小になるのである． ここで zi := D?1/2 ui と置くと D?1/2 LD?1/2 ui = λiui D?1 LD?1/2 u = λiD?1/2 ui D?1 Lzi = λizi Lzi = λiDzi となり，H = D?1/2 u1 · · · D?1/2 uk = (z1 · · · zk) は一般化された固 有値問題 Lz = λDz の解を並べたものであることが分かる．
- 23. 22/25 類似度行列 アルゴリズムを紹介する前に，類似度行列を構成する主要な 3 つの手法 を示す． 1. ε-neighbor 半径 ε 以内にある点のみに重みを与える． 2. k-nearest neighbor 類似度が高い k 個の点のみに重みを与える．類似度行列が対称にな るように注意する．例えば vi と vj がお互いに k-nearest neighbor に含まれる場合にのみ重さを与えるようにすればよい． 3. 完全連結 任意の 2 点間の類似度を計算する方法である．例えば sij = exp ? xi ? xj 2 2σ2 として計算しておく．
- 24. 23/25 アルゴリズム Normalized spectral clustering according to Shi and Malik (2000) 1: Construct a similarity graph. 2: Compute the graph Laplacian L. 3: Compute the ?rst k generalized eigenvectors u1, . . . , uk of the generalized eigenproblem Lu = λDu. 4: Let H := (hiκ) = (u1 · · · uk) ∈ Rn×k . 5: Let yi := (hi,1 · · · hi,k) ∈ Rk (i = 1, . . . , n). 6: Cluster the points y1, . . . , yn with the k-means algorithm into clusters C1, . . . , Ck. 時間計算量について考察する．類似度行列の作成は，完全連結で計算し た場合 O dn2 となる．固有ベクトルの計算は，手法によって違いはあ るものの大体 O n3 程度である．k 平均法によるクラスタリングは繰 り返しの回数を I として O (Ikdn) である． データが増えると固有ベクトルの計算が大きな負担になってしまう．
- 25. 24/25 追記 スペクトラル?クラスタリングにはいくつかの似た変種がある．例えば normalized cut のかわりに，次の RatioCut を使う方法がある． RatioCut (A1, . . . , An) := k i=1 cut Ai, Ai |Ai| ただし |Ai| は Ai に含まれる頂点の数である． このスライドは主に von Luxburg (2007) を参考に作った．類似の他 の手法や技術的な詳細については，この資料を参考にするとよい．
- 26. 25/25 参考文献 Murphy, K. P. (2012). Machine learning: a probabilistic perspective. Simovici, D. A. and Djeraba, C. (2008). Mathematical tools for data mining. Advanced Information and Knowledge Processing, page 129–172. von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4):395–416.