要約
スペクトルクラスタリングは、非凸かつ交差しない多様体を分離できる能力により、多くの注目を集めているが、その高い計算複雑性が応用の広がりを著しく制限している。Dhillon（2001）によるドキュメント-用語の共同クラスタリング枠組みに着想を得て、ランドマークに基づくスケーラブルなスペクトルクラスタリング手法を提案する。本手法では、まず選定されたランドマーク集合と与えられたデータを用いて二部グラフを構築し、その後そのグラフ上で拡散過程を実行することで、クラスタリングに用いる拡散座標の族を取得する。本研究では、提案手法が与えられたデータと選定されたランドマーク間の類似度行列に対する非常に効率的な演算に基づいて実装可能であることを示し、大規模データ処理にも対応可能であることを明らかにする。最後に、いくつかのベンチマークデータセットを用いた実験により、最先端のスケーラブルなアルゴリズムと比較して、本手法の優れた性能を実証する。