超スケーラブルなスペクトラルクラスタリングとアンサンブルクラスタリング

本論文は、リソースが限られている極大規模データセットのスペクトラルクラスタリングのスケーラビリティと堅牢性に焦点を当てています。2つの新しいアルゴリズムが提案されており、これらは超スケーラブルなスペクトラルクラスタリング（U-SPEC）と超スケーラブルなアンサンブルクラスタリング（U-SENC）です。U-SPECでは、ハイブリッド代表点選択戦略とK近傍代表点の高速近似手法が提案され、疎親和部分行列の構築に利用されます。この疎部分行列を二部グラフとして解釈し、転送カットを利用することで効率的にグラフを分割し、クラスタリング結果を得ることができます。U-SENCでは、複数のU-SPECクラスタラーがさらにアンサンブルクラスタリングフレームワークに統合され、堅牢性を向上させつつ高い効率性を維持します。複数のU-SPECを使用して生成されたアンサンブルに基づき、オブジェクトと基本クラスター間で新しい二部グラフが構築され、その後効率的に分割されてコンセンサスクラスタリング結果が得られます。特筆すべきは、U-SPECおよびU-SENCはほぼ線形時間と空間の複雑さを持ち、64GBメモリーのPC上で1000万件以上の非線形分離可能なデータセットを堅牢かつ効率的に分割できるという点です。さまざまな大規模データセットに対する実験により、当方のアルゴリズムのスケーラビリティと堅牢性が示されています。MATLABコードおよび実験データはhttps://www.researchgate.net/publication/330760669 から入手可能です。