はじめに

A Tutorial on Spectral Clusteringを読んだのでメモその２．準備ができたのでいよいよspectral clusteringについて

Spectral Clustering Algorithms

ここでは $n$ 個のデータ点 $x_1,\dots,x_n$ が与えられ，類似度関数 $s_{ij}=s(x_i,x_j)$ が対象(入力を入れ替えても出力が変わらない)かつ非負の値を返す関数として定義する．また類似度行列を $S=(s_{ij})_{i,j=1\dots n}$ として定義する．

Spectral clusteringはunnormalized Laplacianを使うかnormalized Laplacianを使うかで，unnormalized spectral clusteringとnormalized spectral clusteringに分けられる．

Unnormalized spectral clustering

入力として，類似度行列 $S\in\mathbb{R}^{n\times n}$ ，クラスタ数 $k$ が与えられる．

その１の記事で紹介した方法のどれか( $k$ -nearest neighborなど)を用いてグラフを構成し，重み付き隣接行列 $W$ を得る．
そこからunnormalized Laplacian $L$ を計算し，Laplacianの固有ベクトルを順に $k$ 個取り出した集合 $u_1,\dots,u_k$ を得る
$U\in\mathbb{R}^{n\times k}$ を $k$ 個の固有ベクトルを列にもつ行列とし， $y_i\in\mathbb{R}^k$ を $U$ の $i$ 番目の行とする．
k-meansのアルゴリズムを用いて点 $(y_i)_{i=1,\dots,n}$ を $k$ 個のクラスタ $C_1,\dots,C_k$ にクラスタリングしていく．

Normalized spectral clustering according to Phi and Malik (2000)

入力として，類似度行列 $S\in\mathbb{R}^{n\times n}$ ，クラスタ数 $k$ が与えられる．

その１の記事で紹介した方法のどれかを用いてグラフを構成し，重み付き隣接行列 $W$ を得る．
そこからunnormalized Laplacian $L$ を計算し，Laplacianの一般化固有値問題 $Lu=\lambda Du$ から得られる一般化固有ベクトルを順に $k$ 個取り出した集合 $u_1,\dots,u_k$ を得る．
$U\in\mathbb{R}^{n\times k}$ を $k$ 個の固有ベクトルを列にもつ行列とし， $y_i\in\mathbb{R}^k$ を $U$ の $i$ 番目の行とする．
k-meansのアルゴリズムを用いて点 $(y_i)_{i=1,\dots,n}$ を $k$ 個のクラスタ $C_1,\dots,C_k$ にクラスタリングする．

このアルゴリズムは一般化固有値問題の解を用いていて，命題3からわかるように，得られる固有ベクトルは $L_{rw}$ の固有ベクトルと等しい．よってアルゴリズム上はunnormalized Laplacianを使っているが，理論的にはnormalized Laplacianである $L_{rw}$ を使っている．

Normalized spectral clustering according to Ng, Jordan, and Weiss (2002)

入力として，類似度行列 $S\in\mathbb{R}^{n\times n}$ ，クラスタ数 $k$ が与えられる．

その１の記事で紹介した方法のどれかを用いてグラフを構成し，重み付き隣接行列 $W$ を得る．
そこからnormalized Laplacian $L_{sym}$ を計算し，Laplacianの固有ベクトルを順に $k$ 個取り出した集合 $u_1,\dots,u_k$ を得る．
固有ベクトルを列ベクトルとする行列 $U\in\mathbb{R}^{n\times k}$ を作る．
各行のノルムを $t_{ij}=u_{ij}/(\sum_ku_{ik}^2)^{1/2}$ のように1になるように正規化することで行列 $T\in\mathbb{R}^{n\times k}$ を作る．
$T$ の $i$ 番目の行を $(y_i)_{i=1,\dots,n}$ とする．k-meansを用いて $y_i$ を $k$ 個のクラスタ $C_1,\dots,C_k$ にクラスタリングする．

3つのアルゴリズムは異なるgraph Laplaciansを使うだけでおおよその手順は等しい．どのアルゴリズムも肝となるのはデータ点 $x_i$ の表現を $y_i\in\mathbb{R}^k$ に変える事にある．

資料ではtoyデータに対して $k$ -nnを使ってグラフを作った際とfully connectedによりグラフを作った際，さらにんそれぞれのグラフ構成法においてnormalized spectral clusteringをした場合とunnormalized spectral clusteringをした場合の全4パターンで固有値と固有ベクトルを可視化して考察を行っている．ここでは詳細は割愛．

Graph cut point of view

ここではgraphを分割するという観点からspectral clusteringを見る．隣接行列 $W$ を持つsimilarity graphが与えられた時，最も単純かつ直接的なグラフ分割方法はmincut問題を解く事．つまり重みの小さい(=類似度の低い)エッジを切る事でクラスタを形成しようというもの．これを定義するために再度 $W(A,B):=\sum_{i\in A,k\in B}w_{ij}$ ， $A$ の補集合 $\bar{A}$ を与える． $k$ 個の部分集合が与えられた時，mincutは以下を最小化する分割 $A_1,\dots,A_k$ を探す．

$\displaystyle \mathrm{cut}(A_1,\dots,A_k):=\frac{1}{2}\sum_{i=1}^kW(A_i,\bar{A}_i)$

上記のmincutは $k=2$ においては特別簡単に計算が可能ということが知られているが，多くの場合は良い分割を導く事は難しく，また一般的にはmincutの解は単純にグラフから一つの頂点を分割する事であり，クラスタリングの目的に合わない．これを避ける一つの方法として集合 $A_1,\dots,A_k$ は十分大きいという条件を陽に加えることがあげられる．各集合が十分大きいという条件を付け加えた目的関数として有名なものはRatioCut (Hagen and Kahng, 1992)とnormalized cut(Ncut) (Shi and Malik, 2000)の二つがある．それぞれの目的関数は以下．

$\displaystyle \mathrm{RatioCut}(A_1,\dots,A_k):=\frac{1}{2}\sum_{i=1}^k\frac{W(A_i,\bar{A}_i)}{|A_i|}=\sum_{i=1}^k\frac{\mathrm{cut}(A_i,\hat{A}_i)}{|A_i|} \\ \displaystyle \mathrm{Ncut}(A_i,\dots,A_k):=\frac{1}{2}\sum_{i=1}^k\frac{W(A_i,\bar{A}_i)}{\mathrm{vol}(A_i)}=\sum_{i=1}^k\frac{\mathrm{cut}(A_i,\hat{A}_i)}{\mathrm{vol}(A_i)}$

これら二つの目的関数はクラスタ $A_i$ が十分に小さくない場合，小さな値をとる．特に関数 $\sum_{i=1}^k(1/|A_i|)$ の最小値は全ての $|A_i|$ が等しい時に達成する．また，関数 $\sum_{i=1}^k(1/\mathrm{vol}(A_i))$ も同様に全ての $\mathrm{vol}(A_i)$ が等しい時に最小になる．すなわち両方の目的関数が達成しようとしているのはクラスタ間の大きさのバランスを取る事で，それぞれクラスタの大きさを頂点の数で測るか，エッジの重みで測るかの違いしかない．ただし，基本的にmincut問題を解く単純な方法はNP hardであることが言われている．Spectral clusteringはNP hardな問題を緩和した解き方で，ここでは緩和Ncutがnormalized spectral clusteringを，緩和RatioCutがunnormalized spetal clusteringを導くことを見る．

Approximating RatioCut for $k=2$

手始めに緩和が最も理解しやすい $k=2$ の場合のRatioCutを見る．目標は以下の最小化問題を解くこと．

$\displaystyle \min_{A\subset V}\mathrm{RatioCut}(A,\bar{A})$

まず，この式をより扱いやすい形に変形する．部分集合 $A\subset V$ が与えられた時，ベクトル $f=(f_1,\dots,f_n)'$ を以下のように定義する．

$\displaystyle f_i=\left\{ \begin{array}{} \sqrt{|\bar{A}|/|A|}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{|A|/|\bar{A}|}\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

Unnormalized graph Laplacianを使えば，RatioCutの目的関数は以下のように導ける．

$\displaystyle f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2 \\ \displaystyle =\frac{1}{2}\sum_{i\in A,j\in\bar{A}}w_{ij}\left(\sqrt{\frac{|\bar{A}|}{|A|}}+\sqrt{\frac{|A|}{|\bar{A}|}}\right)^2+\frac{1}{2}\sum_{i\in\bar{A},j\in A}w_{ij}\left(-\sqrt{\frac{|\bar{A}|}{|A|}}-\sqrt{\frac{|A|}{|\bar{A}|}}\right)^2 \\ \displaystyle =\mathrm{cut}(A,\bar{A})\left(\frac{|\bar{A}|}{|A|}+\frac{|A|}{|\bar{A}|}+2\right) \\ \displaystyle =\mathrm{cut}(A,\bar{A})\left(\frac{|A|+|\bar{A}|}{|A|}+\frac{|A|+|\bar{A}|}{|\bar{A}|}\right) \\ \displaystyle =|V|\cdot\mathrm{RatioCut}(A,\bar{A})$

2行目は $f$ の定義に従って場合分けをし，2乗の項を展開すれば3行目が得られる．また， $|A|+|\bar{A}|=|V|,\:|A|+|\bar{A}|=\sum_i|A_i|$ の関係を使えば最後の式が導ける．また， $f$ に関して以下が成り立つ事に注意．

$\displaystyle \sum_{i=1}^nf_i=\sum_{i\in A}\sqrt{\frac{|\bar{A}|}{|A|}}-\sum_{i\in\bar{A}}\sqrt{\frac{|A|}{|\bar{A}|}}=|A|\sqrt{\frac{|\bar{A}|}{|A|}}-|\bar{A}|\sqrt{\frac{|A|}{|\bar{A}|}}=0 \\ \displaystyle ||f||^2=\sum_{i=1}^nf_i^2=|A|\frac{|\bar{A}|}{|A|}+|\bar{A}|\frac{|A|}{|\bar{A}|}=|\bar{A}|+|A|=n$

以上のことを用いればRatioCutを使った最小化問題は以下のように記述できる．

$\displaystyle \min_{A\subset V}f'Lf\:\mathrm{subject}\:\mathrm{to}\:f\perp\mathbb{1},\:||f||=\sqrt{n}, \: f_i=\left\{ \begin{array}{} \sqrt{|\bar{A}|/|A|}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{|A|/|\bar{A}|}\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

これは $f$ が離散値を取ることから離散最適になっていて，変わらずNP hardになっている．そこで $f$ の元の定義を忘れて $f_i\in\mathbb{R}$ とすることで緩和することを考える．すなわち

$\displaystyle \min_{f_i\in\mathbb{R}^n}f'Lf\:\mathrm{subject}\:\mathrm{to}\:f\perp\mathbb{1},\:||f||=\sqrt{n}$

と緩和する．この最適化問題はRayleigh-Ritz theoremより $L$ の2番目に小さい固有値に対応する固有ベクトル $f$ によって解が与えられる．ただし，グラフの分割結果を得るためには実数値解となっている $f$ を離散値である指示ベクトルに変える必要がある．単純な方法としては以下のような指示関数によって得られる．

$\displaystyle \left\{ \begin{array}{} v_i\in A\:\:\:\mathrm{if}\:f_i\geq 0 \\ v_i\in\bar{A}\:\:\:\mathrm{if}\:f_i\lt 0 \end{array} \right.$

以上が $k=2$ の場合のunnormalized spectral clusteringのアルゴリズムになっている．

Approximating RatioCut for arbitrary $k$

次に一般的な $k$ の場合のRatioCutの最小化問題の緩和法を考える．グラフ $V$ に関して $k$ 個の集合 $A_1,\dots,A_k$ が与えられた時，集合 $j$ の指示ベクトル $h_j=(h_{1,j},\dots,h_{n,j})'$ を以下のように定義する．

$\displaystyle h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{|A_j|}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

ここで $k$ 個の指示ベクトルを列ベクトルとして持つ行列を $H\in\mathbb{R}^{n\times k}$ として定義すれば，各指示ベクトルは直交していることから $H$ は直交行列( $H'H=I$ )になる．前節と同様に計算を行えば( $f$ を $h_i$ に変えて計算すれば)以下の関係が導かれる．

$\displaystyle h_i'Lh_i=\frac{\mathrm{cut}(A_i,\bar{A}_i)}{|A_i|}$

$h'_iLh_i$ とある一つのクラスタ $i$ に関する式になっているのは $H$ が直交行列，すなわち異なる行同士の積は0になるため．すなわちクラスタごとに独立に計算が可能で，上の式を行列 $H$ を用いて次のように表現する事にする．

$\displaystyle h_i'Lh_i=(H'LH)_{ii}$

すると最終的な目的関数は以下のように表現できる．

$\displaystyle \mathrm{RatioCut}(A_1,\dots,A_k)=\sum_{I=1}^kh_i'Lh_i=\sum_{i=1}^k(H'LH)_{ii}=\mathrm{Tr}(H'LH)$

ただし， $\mathrm{Tr}$ は行列のトレースを表す．以上の関係を用いて最小化問題を書き表わせば，

$\displaystyle \min_{A_1,\dots,A_k}\mathrm{Tr}(H'LH)\:\mathrm{subject}\:\mathrm{to}\:H'H=I, \: h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{|A_j|}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

となる．先ほどと同様，やはりこれは離散最適でNP hardなので行列 $H$ を任意の実数値に緩和する．すなわち最適化問題は以下のようになる．

$\displaystyle \min_{H\in\mathbb{R}^{n\times k}}\mathrm{Tr}(H'LH)\:\mathrm{subject}\:\mathrm{to}\:H'H=I$

これは一般的なトレースの最小化問題になっていて，やはり先ほどと同様Rayleight-Ritz theoremから $L$ の $k$ 個の固有ベクトルから構成された行列を $H$ として選ぶことで解が得られる．これは $H$ がunnormalized spectral clusteringで使われていた行列 $U$ と等しいことを表す．最終的な解を得るためにはやはり実数値として得られた解 $H$ を離散値として求め直す必要がある．これは $U$ の各行をデータ点としてk-meansをすることで実現される．

Approximating Ncut

同様に今度はNcutについて最小化問題の緩和を考える．まずは $k=2$ の場合について．Ncutではクラスタの指示ベクトル $f$ を以下のように定義する．

$\displaystyle f_i=\left\{ \begin{array}{} \sqrt{\frac{\mathrm{vol}(\bar{A})}{\mathrm{vol}(A)}}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{\frac{\mathrm{vol}(A)}{\mathrm{vol}(\bar{A})}}\:\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

単純にRatioCutの $|A|$ が $\mathrm{vol}(A)$ に変わっただけ．なので満たす性質や計算結果もほぼ変わらず， $(Df)'\mathbb{1}=0,\:f'Df=\mathrm{vol}(V),$ and $f'Lf=\mathrm{vol}(V)\mathrm{Ncut}(A,\bar{A})$ が得られる．するとNcutの最小化問題は以下のようにかける．

$\displaystyle \min_Af'Lf\:\mathrm{subject}\:\mathrm{to}\:Df\perp\mathbb{1},\:f'Df=\mathrm{vol}(V), \: f_i=\left\{ \begin{array}{} \sqrt{\frac{\mathrm{vol}(\bar{A})}{\mathrm{vol}(A)}}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{\frac{\mathrm{vol}(A)}{\mathrm{vol}(\bar{A})}}\:\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

やはり，RatioCutと同様に $f$ を任意の実数値に緩和する．

$\displaystyle \min_{f\in\mathrm{R}^n}f'Lf\:\mathrm{subject}\:\mathrm{to}\:Df\perp\mathbb{1},\:f'Df=\mathrm{vol}(V)$

さらに， $g:=D^{1/2}f$ を導入すれば

$\displaystyle \min_{g\in\mathrm{R}^n}g'D^{-1/2}LD^{-1/2}g\:\mathrm{subject}\:\mathrm{to}\:g\perp D^{1/2}\mathbb{1},\:||g||^2=\mathrm{vol}(V)$

と書き換えることができ， $D^{-1/2}LD^{-1/2}=L_{sym}$ であり， $L_{sym}$ の最小固有値に対応する固有ベクトルが $D^{1/2}\mathbb{1}$ であることを思い出せば，Rayleight-Ritz theoremから解 $g$ は $L_{sym}$ の2番目の固有ベクトルで与えられる．

続いて $k\gt 2$ の場合を考える．クラスタの指示ベクトル $h_j=(h_{1,j},\dots,h_{n,j})'$ を以下のように定義する．

$\displaystyle h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{\mathrm{vol}(A_j)}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

やはりRatioCutの $|A|$ が $\mathrm{vol}(A)$ に変わっただけなのでRatioCutと同様の導出から， $H'H=I,\:h_i'Dh_i=1,\:h_i'Lh_i=\mathrm{cut}(A_i,\bar{A}_i)/\mathrm{vol}(A_i)$ が導かれる．するとNcutの最小化問題は以下のようにかける．

$\displaystyle \min_{A_1,\dots,A_k}\mathrm{Tr}(H'LH)\:\mathrm{subject}\:\mathrm{to}\:H'DH=I,\\ \displaystyle h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{\mathrm{vol}(A_j)}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

ここで $T=D^{1/2}H$ を導入し，Tが任意の実数を要素に持つように緩和すれば，最小化問題は以下のように緩和できる．

$\displaystyle \min_{T\in\mathbb{R}^{n\times k}}\mathrm{Tr}(T'D^{-1/2}LD^{-1/2}T)\:\mathrm{subject}\:\mathrm{to}\:T'T=I$

この式も一般的なトレースの最小化問題でその解は $L_{sym}$ の $k$ 個の固有ベクトルによって構成される行列によって与えられる．この最小化問題はnormalized spectral clusteringになっていることが証明されている．

Comments on the relaxation approach

今まで色々と導出してきた緩和された最適化問題は元の最適化問題と比べて解の良さは保証されていない．それどころか，仮に $A_1,\dots,A_k$ を真のRatioCutの最小化の解として， $B_1,\dots,B_k$ を緩和された問題の解とすれば， $\mathrm{RatioCut}(B_1,\dots,B_k)-\mathrm{RatioCut}(A_1,\dots,A_k)$ は任意に大きくなるらしい．これについてはGuattery and Miller (1998)で言及されているようで，論文中で著者らはcockroach graphsなるグラフを取り上げて考えている．cockroach graphsは梯子状に $4k$ 個のデータが分布していて，RatioCutによって二つのクラスタに分割されることが望ましいような形になっている．しかも分割されたグラフは $|A|=|\bar{A}|=2k$ ， $\mathrm{cut}(A,\bar{A})$ となるように設計されている．にも関わらず，著者らはunnormalized graph Laplacianを使ったunnormalized spectral clusteringは常に $\mathrm{RatioCut}(A,\bar{A})=2/k,\:\mathrm{RatioCut}(B,\bar{B})=1$ となることを証明したらしいこれが意味するところは，理想的なカットに対し，RatioCutは $k/2$ 倍悪い結果を導くことを意味している．一般的にbalanced graph cutsを近似する効果的なアルゴリズムは存在しないということが知られていて，しかも近似問題自身がNP hardらしい．ただ，現状いろんな近似方法が提案されていて実験的には良い結果を導いている上，基本的な線形代数の問題として解けることから現状いろんなところで使われてるとのこと．