A Dual-tree Algorithm for Fast k-means Clustering with Large k - todo314 @ ウィキ

A Dual-tree Algorithm for Fast k-means Clustering with Large k

• Ryan R. Curtin
• SDM 2017

概要だけ

• Lloydのアルゴリズムと同じ結果を出力するk-means高速化アルゴリズム
• 基本戦略
  • 点集合と中心集合をそれぞれ木（kd-木、cover tree等）で管理する
  • 点部分集合と中心部分集合の対の関係をまとめて見る
  • 枝刈りをまとめて行える（各点の属する中心の更新とか）
  • 枝刈り条件が沢山ある（一応強そう）
• 計算時間
  • 結構色々な仮定の下O(N+klogk)時間
  • expansion constant, related quantityの多項式が掛かってくる
  • 実際には速い
• 実験; d次元が低、kが大、かなり速い、他の手法はk^2空間とか食うので
  • blacklist[Pelleg-Moore. Accelerating exact k-means algorithms with geometric reasoning. KDD'99]というのが地味に強い

まとめ

• 理論的な面では期待したほど良くなかった
• 意外と決定版は無い
• 反復回数はどれも同じだけど、複数反復をまとめてスキップ出来ないのだろうか

SDM k-means クラスタリング

2017/04/11