FUSE: Full Spectral Clustering(KDD2016) を読んだ

べき乗法と独立成分分析を用いたマルチスケールに頑強なクラスタリング手法の提案

• べき乗法では近似固有ベクトル(Pseudo-eigenvectors)は複数の真の固有ベクトルの線形結合からなる。有益でない固有ベクトルも含まれるのでいかにそれを除去するか
• Fig.1 で言ってることがいまいちわからない。ｃ,ｄも変化がないように見える。論文で言及してる stripe が何を指してるかが不明 分かった。赤・青・黒の３つのクラスタで分かれている。最初は黒色がクラスタ境界面に見えた。論文内での multi scale というのは、データの幾何的な分布を指している？
• 固有値計算は O(n³）かかるから計算量が~~って毎回言われるが、行列の状態に依存するので毎回最悪の場合を主張されてるも困る
• ZP self-turining spectral clustering をなぜ対抗馬にして比較してるのかは謎。
• ICA¹を行ったあとにその行列に対して回転処理を行い情報量の最小化を狙う
• クラスタ数が多い場合、PIC では良い結果が出づらい multi scale なデータの場合標準の spectral clustering では失敗することが多々ある
• fig.2 (a) 見ればわかるがk-means では分離が困難
• fig.2(b) ４－５本目の固有ベクトルを基底ベクトルにもつ空間ではクラスタのオーバーラップが少ない
• つまり１－５本目の固有ベクトル全て含めてクラスタリングすれば結果が良好になるのではないか？（仮説）
• fig.2 © ４回べき乗法を行った。結果が似てる。（縦軸が何を表してるかは不明）。四回が上から四本求めたのか、一番上の固有ベクトルを４回求めたのか分からない
• fig. (d) 提案手法を適用。k-means で分離可能 行列Vをp回べき乗法を行って構築 E=MVの最小化を行う
• ICA を最小化するために Jacobi Rotation を用いる。探索には貪欲法を採用

Contribution

• マルチスケール（多種多様な）データ分布に対してクラスタリングが可能
• 計算時間は従来（ncut)と同等

感想

• PIC(Power Itetaion Clusterg)をまさか拡張してくるとは思わなかったなので、興味深い論文。(実装して再現実験したけど、Early stopping の段階で高確率でクラスタリングが失敗していて使い物にならなかった印象があるので…)
• データの分布が多様な場合、上位数本のベクトルではなく、そこから更に下の固有ベクトルに着目したほうが結果が良好になるのは面白い
• KDD の論文、相変わらず読みやすかった。