なるべく良いSpectral Clusteringの離散解を得るためのアルゴリズムを提案した論文

前置き: Multi-class Spectral Clustering

Multi-class Spectral Clusteringの目的関数:

f:id:toaruharunohi:20180920211533p:plain

なお、Wは類似度行列、Dは以下に示す通りの次数の行列である:

f:id:toaruharunohi:20180920211542p:plain

この問題(Eq. 11~13)はNP困難であるため、Xを連続値に緩和して解くことを考える。ここで、Zを以下のように定義する:

f:id:toaruharunohi:20180920211531p:plain

このZと連続値緩和により、問題Eq. 11~13は次のように書き換えられる:

f:id:toaruharunohi:20180920211528p:plain

この問題の解集合は次のように書き下せることが簡単な計算で示せる:

f:id:toaruharunohi:20180920211536p:plain

ここで、Pは以下の行列である:

f:id:toaruharunohi:20180920211539p:plain

また、Λ*はPの固有値を対角成分に並べた行列である。

この結果得られたZの解集合をXに戻すことで、当初の問題(Eq. 11~13)でXを連続値緩和した場合のXの解集合が得られる。ここで、XからZへの変換をZ=f(X)とすると、f(X)には次のような逆変換が存在するということに注目したい:

f:id:toaruharunohi:20180920211525p:plain

さらに、f(X)の逆変換について次が成り立つことに注目したい:

f:id:toaruharunohi:20180920211548p:plain

Eq.24とEq.30から、問題Eq. 15~16に対応するXの解集合は次のように表せる:

f:id:toaruharunohi:20180920211546p:plain

連続値緩和した解の離散化

当初の問題(Eq. 11~13)を連続値緩和した問題(Eq. 15~16)のXの解集合は上記の手順で求められることはわかった。この論文ではその解集合を用いて、当初の目的関数Eq. 11をなるべく大きくするような離散解(というかクラスタリング結果)を効率的に求める方法を提案している。

具体的には、Eq. 30の解集合に含まれるいずれかの連続解 $\tilde{X}$ までの距離が最も小さくなる離散解Xを求めて出力することを提案している:

f:id:toaruharunohi:20180920211551p:plain

問題Eq. 31~33を解くために、この論文ではXとRの交互最大化に基づくアルゴリズムを提案している。

Rを固定したときはEq. 31のφ(X, R)を最大化させるXは次のように効率的に求められる:

f:id:toaruharunohi:20180920211554p:plain

逆にXを固定したときはEq. 31のφ(X, R)を最大化させるRは次のように効率的に求められる:

f:id:toaruharunohi:20180920211557p:plain

ここで、Eq. 40の右側は左側の特異値分解である。

この論文のSpectral Clusteringのアルゴリズムをまとめると、一旦連続値緩和した場合の解を得た上で、それをもとにEq. 36とEq. 39を交互に解くことで離散解Xを求めるというアルゴリズムである。

k-meansほど初期値依存性などがなくて良いとのこと。

scikit-learnのSpectral Clusteringでassign_labelsという引数に”discretize”という文字列を渡すことでこのアルゴリズムを利用できる。