Hatena::ブログ(Diary)

おいしいお米の話

2012-12-14

スペクトラルクラスタリングの話

Machine Learning Advent Calendar 2012に参加させていただきました,@yonetaniryo と申します.現在,博士後期課程2年で,コンピュータビジョンパターン認識に興味があります.最近,クラスタリング手法の一つであるスペクトラルクラスタリングについて勉強する機会があったので,今回はそれを紹介しようと思います.

  • 2013 1.24 いただいたコメントをもとに,図を一部更新しました.

はじめに

本記事のモチベーション

本記事では,「スペクトラルクラスタリングについて何も知らない」人を「スペクトラルクラスタリングとは何かを大雑把には知っている」状態に持っていくことを目標にしています.具体的には,文献[1]の最初の方を紹介します.

本記事で扱う範囲
本記事で扱わない範囲
  • Normalized cutsとの関連: 文献[1][2]が詳しいです.
  • カーネル法との関連: 文献[1][3]が詳しいです.

スペクトラルクラスタリングのざっくりした説明

f:id:mr_r_i_c_e:20130124211910p:image:w600
グラフの特性を表現するような行列としてgraph Laplacian matrixがあり,graph Laplacian matrixの固有値集合はグラフのスペクトルスペクトラム)と呼ばれます[4].スペクトラルクラスタリング(spectral clustering)は,データをサンプル間の類似度に基づいてグラフ表現し,そのスペクトル固有値)の計算を通してクラスタリングを解く手法です.[3][5][6]などで指摘されている通り,データをその局所性(元の特徴空間におけるペアワイズな類似性)を保存しつつ低次元空間に飛ばし(Locality preserving projection; LPP),その低次元空間の中で通常のクラスタリング(たとえばk-means)を行うことと同じです(良いグラフ表現をしていればk-meansなどせずにクラスタ分割ができます.詳しくは後述).

Similarity graph([1] Sec. 2)

スペクトラルクラスタリングにあたって,サンプル x_i (i=1,¥dots, n) のペアワイズな類似性をグラフ表現する必要があります.このグラフをsimilarity graphと呼びます.

  • G=(V,E): similarity graph.
  • v_i ¥in V: サンプル  x_i に対応.
  •  e_{ij}¥in E: サンプル間の類似度に対応.類似度に応じて重みw_{ij}が与えられる(似てる/近いほど大きい).w_{ij}¥geq 0であり,w_{ij}= 0のときはエッジ無し.ちなみにw_{ii}=0です.

重みの与え方はいくつかの種類があり,

  •  ¥epsilon-neighbor: 距離 ¥epsilon以下のサンプルのみ重みを与えます(他はゼロ).
  • k-nearest neighbor: 各サンプルについて最も類似しているk個のデータ点にのみ重みを与えます.
  • Fully-connected: 重み(たとえばガウシアン重み)を全サンプル同士について与えます.

f:id:mr_r_i_c_e:20121210132239p:image:w600

Graph Laplacian matrixとその諸性質([1] Sec. 3)

スペクトラルクラスタリングでは,similarity graphの性質をよく表現するような行列,graph Laplacian matrixを導入します.具体的には,

  1. データ点 x_i, x_jの重み(近さ)w_{ij}(i,j)要素に持つ n¥times nの行列(nはサンプル数)を weighted adjacency matrix Wとして定義します.
  2. サンプル x_iに与えられる重みの総和  d_i =¥sum_j w_{ij}(i,i)要素に持つような n¥times nの行列をdegree matrix  Dとして定義します.
  3. これらの行列W,Dを用いて,graph Laplacian matrix L=D-Wが得られます.

Graph Laplacian matrixは別名Kirchhoff matrixと呼ばれており[7],グラフを回路に見立てて,各頂点の電流入出量を表した行列と捉えることもできると思います.
f:id:mr_r_i_c_e:20121210132240p:image:w600
Graph Laplaciansには幾つかの重要な性質があります.以下ではそれを簡単に説明します(証明は付録).

性質1: n次元ベクトルf=(f_1,¥dots,f_n)について,f^T L f =¥frac{1}{2} ¥sum_{i,j} w_{ij} (f_i-f_j)^2

性質2: Lは半正値対称行列(なので,固有値はすべて¥lambda¥geq 0

性質3:  Lの最小固有値は0であり,対応する固有ベクトルは全要素1のn次元ベクトル¥mathbb{1}

性質4: 固有値0の重複度(multiplicity) K L中の連結部分グラフの数に対応する(すなわち,similarity graph  G ¥{A_1,¥dots, A_K¥}に分解できる).また,固有値0に関する固有空間は ¥left¥[¥begin{matrix}¥mathbb{1}_{A_1}¥¥0¥end{matrix}¥right¥],¥dots,¥left¥[¥begin{matrix}0¥¥¥mathbb{1}_{A_K}¥end{matrix}¥right¥]によって張られる( ¥mathbb{1}_{A_k}は連結部分グラフ A_kの頂点数だけ1を並べたベクトル).

f:id:mr_r_i_c_e:20121210132241p:image:w600

特に性質4が重要で,固有値0に対応する固有ベクトルが連結部分グラフの頂点集合を示しているということで,固有値問題を解くことでグラフの分割ができる=データのクラスタリングができる,というのが直感的に分かるかと思います.以上で準備は完了です.

ちなみに,冒頭に定義したgraph Laplacian matrix L=D-Wは,正確にはun-normalized graph Laplacian matrixと呼ばれ,normalized graph Laplacian matrixというものもあります.2種類あります.

  •  L_{sym}:=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2}
  •  L_{rw}:=D^{-1}LD=I-D^{-1}W

Normalized graph Laplacian matrixも,これまで紹介した諸性質に非常に似た性質を持っています.本記事では省略しますので,詳しくは[1]を参照してください.

スペクトラルクラスタリングのアルゴリズム([1] Sec. 4)

ここでは,unnormalized graph Laplacian matrix  L=D-Wを用いたun-normalized spectral clusteringのみ紹介します.
f:id:mr_r_i_c_e:20130124211910p:image:w600

Un-normalized spectral clustering

Input: データ (x_1,¥dots,x_n)クラスタ k
Output: 各サンプルについてのクラスタID.

  1. Similarity graph~ graph Laplacian matrix  Lをつくる.
  2.  L固有ベクトルを,固有値が小さいものから順に k個( u_1,¥dots, u_k)求める.
  3. 固有ベクトル u_p p列目に持つような行列  U¥in ¥mathbb{R}^{n¥times k}を作る.
  4. Lが理想的に k個の部分グラフに分割されている場合… u_p p番目の連結部分グラフのindicatorであるはずなので, Uについて  i番目の行はサンプル x_iの所属するクラスタを示しているはず.おしまい.
  5. そうでない場合… i番目の行をサンプル x_iの新たな特徴ベクトルとして,通常のクラスタリング(たとえばk-means)を行う.

4. は先の性質4に由来する部分であり,スペクトラルクラスタリングのキモの部分になります.また,5. を考えると,スペクトラルクラスタリングが実質のところ局所性を保存した次元削減→通常のクラスタリング,となっていることが分かります.

Lが理想的に k個の部分グラフに分割されている場合,と書きましたが,実際はそんな綺麗な分割になっていることはなく(similarity graphの計算の仕方に大きく依存します),出てくる固有ベクトルがindicator vectorsになることはまれです(多分まれだと思います).そこで,問題をちょっと読み替えて,部分グラフ間のエッジ重みが小さく(クラスタ間の距離が大きく)なるようなグラフの分割を探そうということを考えます.すなわちgraph cutsの問題であり,ここでようやくnormalized cutsが出てきます(つづきは付録).

まとめ

データのグラフ表現〜スペクトラルクラスタリングのアルゴリズムを紹介しました.基本的には,[1]の前半を踏襲した内容になっています.スペクトラルクラスタリングは非常に奥の深いテーマで,まだ理解できていないところは多いです… 誤り,補足等ありましたら随時修正していきますので,ぜひぜひよろしくお願いします.

参考文献

[1] A Tutorial on Spectral Clustering - Ulrike von Luxburg (url)
[2] Normalized Cuts and Image Segmentation - Jianbo Shi and Jitendra Malik (url)
[3] 機械学習概論 次元削減(2) - 東工大 杉山先生 (url)
[4] Spectral graph theory - Wikipedia (url)
[5] スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 観月橋日記 (続生駒日記) (url)
[6] スペクトラルクラスタリングの基本的な解説、および高速化手法のざっくりとした説明 - The beautiful mind (url)
[7] Laplacian matrix - Wikipedia (url)
[8] Spectral partitioning works: planar graphs and finite element meshes - Daniel A. Spielman and Shang-Hua Teng (url)
[9] Algebraic connectivity of graphs - Miroslav Fiedler (url)

付録1: graph Laplaciansの諸性質とその証明

性質1: n次元ベクトルf=(f_1,¥dots,f_n)について,f^T L f =¥frac{1}{2} ¥sum_{i,j} w_{ij} (f_i-f_j)^2

証明
 f^T L f = f^T D f - f^T W f = ¥sum_i d_i f_i^2-¥sum_{i,j}w_{i,j}f_i f_j
 =¥frac{1}{2}¥left¥(¥sum_i d_i f_i^2 +¥sum_j d_j f_j^2 -2¥sum_{i,j}w_{i,j}f_i f_j¥right¥)(ここが一番トリッキーですね!)
 =¥frac{1}{2}¥left¥(¥sum_{i,j}w_{i,j} f_i^2 +¥sum_{i,j}w_{i,j} f_j^2 -2¥sum_{i,j}w_{i,j}f_i f_j¥right¥)
 =¥frac{1}{2} ¥sum_{i,j} w_{ij} (f_i-f_j)^2

性質2: Lは半正値対称行列(なので,固有値はすべて¥lambda¥geq 0

証明
性質1 のところで, w_{ij}¥geq 0なので,任意のベクトル fについてf^T L f¥geq 0

性質3:  Lの最小固有値は0であり,対応する固有ベクトルは全要素1のn次元ベクトル¥mathbb{1}

証明:  L i番目の行を L_iとおくと,
 L_i=¥left¥(-w_{i1},¥dots,¥sum_j w_{ij},¥dots, -w_{in}¥right¥)よりL_i ¥mathbb{1} = 0
したがって, L¥mathbb{1}=¥mathbb{0}=0¥times ¥mathbb{1}

性質4: 固有値0の重複度(multiplicity) K L中の連結部分グラフの数に対応する(すなわち,similarity graph  G ¥{A_1,¥dots, A_K¥}に分解できる).また,固有値0に関する固有空間は ¥left¥[¥begin{matrix}¥mathbb{1}_{A_1}¥¥0¥end{matrix}¥right¥],¥dots,¥left¥[¥begin{matrix}0¥¥¥mathbb{1}_{A_K}¥end{matrix}¥right¥]によって張られる( ¥mathbb{1}_{A_k}は連結部分グラフ A_kの頂点数だけ1を並べたベクトル).

証明:

  • K=1のとき

固有値0に対応する固有ベクトルは性質3より ¥mathbb{1}_G

  • K¥geq2のとき

K個の連結部分グラフからなるgraph Laplacian matrix Lを考える.
たとえば K=2のとき L=¥left¥[¥begin{matrix}L_1 & 0 ¥¥ 0 & L_2¥end{matrix}¥right¥].これまでの議論より L_kの最小固有値 ¥lambda_kは0,対応する固有ベクトル ¥mathbb{1}_{A_k}.このようなblock diagonal matrixについて,
 L=¥left¥[¥begin{matrix}L_1 & 0 ¥¥ 0 & L_2¥end{matrix}¥right¥]¥left¥[¥begin{matrix}¥mathbb{1}_{A_1}¥¥0¥end{matrix}¥right¥]=¥left¥[¥begin{matrix}L_1¥mathbb{1}_{A_1}¥¥0¥end{matrix}¥right¥]=¥left¥[¥begin{matrix}¥lambda_1¥mathbb{1}_{A_1}¥¥0¥end{matrix}¥right¥]=¥lambda_1¥left¥[¥begin{matrix}¥mathbb{1}_{A_1}¥¥0¥end{matrix}¥right¥]
したがって,連結部分グラフ A_k のgraph Laplacian matrix  L_k固有値 L固有値であり,その固有ベクトル A_kのindicator vectorとなる.
f:id:mr_r_i_c_e:20121210132241p:image:w600

付録2: Normalized cuts とスペクトラルクラスタリング

Normalized cutsは,最小カットに基づくグラフの分割を求める方法の一つで,分割された2つの部分グラフA, Bに関して,A, B間のエッジコストが小さく(最小カット)なり,かつA, Bそれぞれについて「頂点集合から全頂点へのエッジコストの総和」がバランスよくなるような目的関数を入れることが特徴になっています.また,この目的関数の最小化はレイリー商の最小化に帰着でき([2]に詳しく式変形が書かれています),結果としてグラフ分割を固有値問題で解くことになります.Normalized cutsによるグラフ分割は,先のnormalized graph Laplacian matrixを用いたスペクトラルクラスタリングに対応しており,

  • クラスタ内サンプル間の距離が小さくなるような分割
  • クラスタ間距離が大きくなるような分割

の両方を考慮することができます(un-normalized spectral clusteringは前者のみ考慮します.この辺の詳細は[1] Sec. 8.5を参照してください).

付録3: 固有ベクトルの選び方についての補足

Lが理想的に k個の部分グラフに分割されていない場合においても,最小固有値は0かつ対応する固有ベクトル ¥mathbb{1}となります.したがって,実際のスペクトラルクラスタリングでは2番目に小さい固有値から順に k-1個の固有ベクトルを用いる場合が多いようです.この2番目に小さい固有値に対応する固有ベクトルをFiedler vectorといい,Fiedler vectorのみを用いたグラフ分割はFiedler cut([8] Sec 2.3に概要があります)と呼ばれます.Fiedlerの論文は[9]にあります.f:id:mr_r_i_c_e:20130124211910p:image

imaumaimauma 2012/12/16 17:56 クラスタリング手法については素人なのですが、非常に面白かったです。ところで、記事内の図表はなんのソフトを使って作成されていますか?見やすく、センスが良く感じました

mr_r_i_c_emr_r_i_c_e 2012/12/16 20:15 imauma さん,コメントありがとうございます.図表はすべてPowerPointで作成しております.

studentstudent 2013/01/25 00:32 クラスタリングに関して勉強しています.
非常に簡潔に書いていただいており,参考になります.
しかし,図に関して混乱してしまいました.
局所性を保存したデータの次元削減の矢印についてですが,
元空間のデータと,グラフのスペクトルからグラフラプラシアンの固有ベクトルを求めている.ということでしょうか
自分の理解としましてはグラフラプラシアン行列の情報だけで固有ベクトルを算出するということなのですが.
御解答頂ければ幸いです.

mr_r_i_c_emr_r_i_c_e 2013/01/25 06:09 student さん
仰る通り,グラフラプラシアンのみから固有ベクトルを計算します.
本図は,得られた固有ベクトルからなる行列が,結果として元データの局所性保存射影を求めていることと等価,ということを意図しておりました.しかし,同じ矢印を使ってしまっては,確かに混乱を招きますね.すみません.近いうちに修正させていただきます.ありがとうございます.

いなかびといなかびと 2014/04/15 01:13 学部卒の者ですが、スペクトラルクラスタリングを学ぶにあたって
この記事は相当参考になりました。

英語資料だけではあやふやな理解であり、周りの学部生も深く説明できていない状況でしたが、
この記事でようやく、理解が芯まで届いたと思います。

分かりやすい説明ありがとうございました。

sonicboysonicboy 2014/07/06 20:04 大変勉強になりました。ありがとうございました。

sonicboysonicboy 2014/07/06 20:04 大変勉強になりました。ありがとうございました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

Connection: close