スペクトラルクラスタリングの導出

 これからいよいよ3.1で概略を示したNcut最小値問題の解法過程の詳細を追っていきた いと思います．最初の目標は，今!

のように定義されたJnについて，Ncutとの等式!

を示す事です．後ほど証明しますが，Jnは3.1で出てきたように!

という式に変形することができ，そしてその最小値はレイリー商の性質を使えば求めるこ とができますので，Ncut = Jnという関係式がもし正しければ，それはNcutの最小値問題の 解決を意味しているわけです．Jnの各要素について詳しく見てみますと，まずWは!

と表されるN×N次元の類似度行列でした．ここでdijはノードiとノードjの類似度を表しま す．また!

のように定義されるN次元のワンズベクトルeを使って以下のような対角行列Dを定義しま す．!

なお，diagはN次元ベクトルをそれぞれの要素を行列の対角の要素とするN×N次元ベクト ルに変換する関数です．Dはまた!

Jn = q

^t

(D W )q q

^t

q

N cut = Jn

Jn = z

^t

Xz z

^t

z

W =

d

₁₁

d

₁₂

· · · d

_1n

d

₂₁

d

₂₂

· · · d

_2n

· · · · · · · · · · · ·

d

_n1

d

_n2

· · · d

_nn

e =

1 1

· · · 1

D = diag(W e)

と定義したdiを使うと!

と表す事ができます．さらに，ベクトルqはaか-bの離散的な値をとるN次元ベクトルであ るとします．ここでaとbは以下のように定義しておきます．!

ただし，!

です．またi ∈ Aならばa，i ∈ Bならば-bの値を取るものとします．さて，これでJnをしっか り定義できたのですが，そもそもNcutは!

と定義される関数でした．これをJnに変換する為にはここで新たに以下の三つの関係式を 証明する必要があります．!

d

_i

=

j

d

_ij

D =

d

₁

O

d

₂

· · ·

O dn

a = d

_B

d

_A

d b = d

_A

d

_B

d

d

_X

=

i X

d

_i

d = d

_A

+ d

_B

N cut = W (A, B)

d

_A

+ W (A, B) d

_B

q

^t

W q = a

²

W (A) + b

²

W (B) 2abW (A, B) aW (A) bW (B ) + (a b)W (A, B) = 0 W (A, B) = q

^t

(D W )q

(a + b)

²

まず!

について．Wqのi行目は!

ですが，qはaか-bの離散的な値を取ることを思い出すとこれは!

と変形する事ができます．ただしdA(i)はノードiとクラスタAの全要素との類似度の総和を 表す値とします．そうすると!

示されました．次に!

について．これは!

!

q

^t

W q = a

²

W (A) + b

²

W (B) 2abW (A, B)

N

j=1

d

_ij

q

_i

N

j=1

d

_ij

q

_i

= a

N

j A

d

_ij

b

N

j B

d

_ij

= ad

⁽ⁱ⁾_A

bd

⁽ⁱ⁾_B

q

^t

W q =

N

i=1

(ad

⁽ⁱ⁾_A

bd

⁽ⁱ⁾_B

)q

_i

= a

N

i=1

(ad

⁽ⁱ⁾_A

bd

⁽ⁱ⁾_B

) b

N

i=1

(ad

⁽ⁱ⁾_A

bd

⁽ⁱ⁾_B

)

= a

²

d

_A

abW (A, B) baW (A, B) + b

²

d

_B

= a

²

d

_A

+ b

²

d

_B

2abW (A, B)

aW (A) bW (B ) + (a b)W (A, B) = 0

と変形できますが，ここで!

を代入すると，!

示されました．最後に!

について．まず以下のようにxiを定義します．!

すると!

aW (A) bW (B) + (a b)W (A, B)

= a(W (A) + W (A, B)) b(W (B ) + W (A, B))

= a

i A

d

_i

b

i B

d

_i

= ad

_A

bd

_B

a = d

_B

d

_A

d b = d

_A

d

_B

d

ad

_A

bd

_B

= d

_A

d

_B

d

_A

d d

_B

d

_A

d

_B

d

= d

²_A

d

_B

d

_A

d

d

²_B

d

_A

d

_B

d

= 0

W (A, B) = q

^t

(D W )q (a + b)

²

x

_i

= q

_i

a b 2

2 a + b

x

_i

= 1 if q

_i

= a

1 if q

_i

= b

となり，同時に!

という関係式も満たします．従ってW(A,B)は!

とxiを使って書き直す事ができます．ここで(xi - xj)²は，!

ですので，!

となりますが，ここでDqのi 行目はdiqi，Wqの_j 行目がΣjdijqjであった事を思い出すと，!

(x

_i

x

_j

)

²

= 0 if x

_i

= x

_j

4 if x

_i

= x

_j

W (A, B) = 1 2

ij

(x

_i

x

_j

)

²

4 d

_ij

(x

_i

x

_j

)

²

= q

_i

a b 2

2

a + b q

_j

a b 2

2 a + b

2

= 4 (q

_i

q

_j

)

²

(a + b)

²

W (A, B) = 1 2

ij

(q

_i

q

_j

)

²

(a + b)

²

d

_ij

= 1 2

ij

q

²_i

2q

_i

q

_j

+ q

_j²

(a + b)

²

d

_ij

= 1

2(a + b)

²

i

q

_i²

j

d

_ij

2

i

q

_i

j

q

_j

d

_ij

+

j

q

²_j

i

d

_ij

= 1

(a + b)

²

i

q

_i²

d

_i

i

q

_i

j

q

_j

d

_ij

W (A, B) = 1

(a + b)

²

(q

^t

Dq q

^t

W q)

= q

^t

(D W )q

(a + b)

²

示されました．さて，これで準備ができましたので，NcutをJnへ変換します．まず，!

より!

です．また!

より，!

ここに，!

を代入すると，!

となります．さらにここで!

を代入すると!

となります．従って，!

!

aW (A) bW (B ) + (a b)W (A, B) = 0

a(W (A) + W (A, B)) = b(W (B ) + W (A, B)) ad

_A

= bd

_B

W (A, B) = q

^t

(D W )q (a + b)

²

(a + b)

²

W (A, B) = q

^t

Dq q

^t

W q

q

^t

W q = a

²

W (A) + b

²

W (B) 2abW (A, B)

(a + b)

²

W (A, B ) = q

^t

Dq a

²

W (A) b

²

W (B) + 2abW (A, B )

(a

²

+ 2ab + b

²

)2W (A, B ) + a

²

W (A) + b

²

W (B) 2abW (A, B ) = q

^t

Dq a

²

(W (A) + W (A, B)) + b

²

(W (B) + W (A, B)) = q

^t

Dq

a

²

d

_A

+ b

²

d

_B

= q

^t

Dq

ad

_A

= bd

_B

a(a + b)d

_A

= q

^t

Dq

ということで，確かにNcut=Jnになりました．残る作業はJnをレイリー商に変換すること だけです．Dが対称行列だということをフルに活用して!

ここで!

N cut = W (A, B)

d

_A

+ W (A, B) d

_B

= W (A, B) 1

d

_A

+ 1 d

_B

= W (A, B) 1

d

_A

+ 1

a b

d

_A

= W (A, B) a + b ad

_A

= q

^t

(D W )q a(a + b)d

_A

= q

^t

(D W )q q

^t

Dq

= J

_n

J

_n

= q

^t

(D W )q q

^t

Dq

= q

^t

D(E D

¹

W )q q

^t

D

¹²

D

¹²

q

= q

^t

D

¹²

(E D

¹²

W D

¹²

)D

¹²

q q

^t

D

¹²

D

¹²

q

= D

¹²

q

^t

(E D

¹²

W D

¹²

) D

¹²

q D

¹²

q

^t

D

¹²

q

z = D

¹²

q

X = E D

¹²

W D

¹²

のようにベクトルzと行列Xを定義してしまえば!

すなわちレイリー商に変形できました．ということで，Xの最小固有値とそれに対応する 固有ベクトルを求めればめでたくクラスタリングの答えが得られるはずなのですが，よく よく考えてみると最小の固有値λ1はどんな集合を対象にしても，その値は0です．なぜそ うなるのかというとNcutを本当に最小化したい場合は以下の図のようにクラスターBを空 にしてしまえばよいからです．!

!

この場合はW(A,B) = 0なのでλ1=0です．しかしこれは我々にとって意味のある結果ではあ りません．従って二番目に小さな固有値こそが求めるべき値ということになります．この 二番目に小さな固有値には名前がついていて，その名をFielder値と言い，対応する固有ベ

クトルはFielderベクトルと言います．!

!

  以上でNcutを用いたスペクトラルクラスタリングの導出が完了しました．長くなりまし たが，今3.1の概要を読み返していただけると，全体的な流れが改めて良く理解できるの ではないかと思います．初歩的な線形代数しか用いていないのですが，クラスタリングの 問題が類似度行列(を少し変形した行列)の固有値問題に帰着できるという以上の結論は驚 くべきものですね．!

!

 また，Mcutも類似した手順でレイリー商の最小値問題まで帰着できます．もしかしたら Ncutの導出の説明に少し冗長な部分があったことに気づかれた方がいらっしゃるかもしれ ませんが，それはMcutの導出過程で出てくる式と共通の式を使用するようにしたためで す．余裕のある方は是非Mcutの導出にもチャレンジしてみてください．


Jn = z

^t

Xz z

^t

z

Fig.21-”最適な”分割の例．分割をしない場合，評価値は”最適”になってしまう．

!

4.1 統計解析のあらまし 

 統計は言うなれば「不確実性を考慮した論理的推論」です．様々な手法，考え方，理論 が統計学に含まれますが，二つに大別すると以下のようになるでしょう．!

!

a. 標本情報に基づいた全体の推論!

 全体(母集団)から一部(サンプル，標本)を抜き出し，そこから全体を推論すること．こ れはさらに以下の二つに分かれます．なお系統解析は一般的にはこの範疇に入ります．!

!

 ・検定 (統計的仮説検定)!

 ある二つの標本について，それが同一の母集団から得られたのか否かを判断するこ と．多種多様な検定手法が提案されていますが，根本はこれにつきます．!

  ...t検定，U検定，χ二乗検定，ANOVAなど!

!

 ・推定 (統計的推定)!

  標本の情報(統計量)から母集団の平均などを決められた幅でもって推定すること．!   ...点推定，信頼区間，最尤法，ベイズ統計!

!

b. 情報の要約，構造解析!

 母集団の一部，あるいは全体から，その特徴量を算出する解析手法です．代表的なもの を以下に列挙します．!

!

 ・回帰分析，主成分分析 (次元縮約)!

 回帰分析は二つの変数間の関連性を数値化する手法の一つ (ピアソン相関係数，スピ アマン相関係数など)．主成分分析は多数の変数を少数の変数へ縮約する手法の一つ．!  !

 ・グラフ平滑化!

  グラフの変動からはずれ値を除いて滑らかなグラフを描く方法(LOESSなど)．!

!

 ・クラス分類 (判別分析，SVMなど)!

  二つの群を区切る超平面の決定手法．機械学習と関連が深い．!

!

 ・クラスタリング(階層クラスタリング，K-means，スペクトラルクラスタリングなど)!

  一つの群から二つの群への分割手法．集合からの特徴抽出法．


Basic theories of Bioinformatics 

L ECTURE  4 

Lecturer: Matsui M

ドキュメント内 春プロ勉強会14.pages (ページ 51-60)