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

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

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

はじめに

本記事のモチベーション

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

本記事で扱う範囲

データのグラフ表現〜スペクトラルクラスタリングのアルゴリズムを扱います．

本記事で扱わない範囲

Normalized cutsとの関連: 文献[1][2]が詳しいです．
カーネル法との関連: 文献[1][3]が詳しいです．

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

グラフの特性を表現するような行列として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: 重み（たとえばガウシアン重み）を全サンプル同士について与えます．

Graph Laplacian matrixとその諸性質（[1] Sec. 3）

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

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

Graph Laplacian matrixは別名Kirchhoff matrixと呼ばれており[7]，グラフを回路に見立てて，各頂点の電流入出量を表した行列と捉えることもできると思います．

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を並べたベクトル）．

特に性質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のみ紹介します．

Un-normalized spectral clustering

Input: データ $(x_1,\dots,x_n)$ ，クラスタ数 $k$
Output: 各サンプルについてのクラスタID．

Similarity graph~ graph Laplacian matrix $L$ をつくる．
$L$ の固有ベクトルを，固有値が小さいものから順に $k$ 個（ $u_1,\dots, u_k$ ）求める．
固有ベクトル $u_p$ を $p$ 列目に持つような行列 $U\in \mathbb{R}^{n\times k}$ を作る．
$L$ が理想的に $k$ 個の部分グラフに分割されている場合… $u_p$ は $p$ 番目の連結部分グラフのindicatorであるはずなので， $U$ について $i$ 番目の行はサンプル $x_i$ の所属するクラスタを示しているはず．おしまい．
そうでない場合… $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] 機械学習概論次元削減（２） - 東工大杉山先生 (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となる．

付録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]にあります．

はじめに

本記事のモチベーション

本記事で扱う範囲

本記事で扱わない範囲

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

Similarity graph（[1] Sec. 2）

Graph Laplacian matrixとその諸性質（[1] Sec. 3）

性質1: 次元ベクトルについて，

性質2: は半正値対称行列（なので，固有値はすべて）

性質3: の最小固有値は0であり，対応する固有ベクトルは全要素1のn次元ベクトル．

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

Un-normalized spectral clustering

まとめ

参考文献

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

性質1: 次元ベクトルについて，

性質2: は半正値対称行列（なので，固有値はすべて）

性質3: の最小固有値は0であり，対応する固有ベクトルは全要素1のn次元ベクトル．

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

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

性質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}$ ．

性質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}$ ．