Making k-means even faster - todo314 @ ウィキ

Making k-means even faster

• Greg Hamerly
• In SDM 2010

参考

• http://d.hatena.ne.jp/ny23/20101126/p2

概要

• Lloyd's algoの高速化
• ベクトル間の距離の計算を刈る
• Using the Triangle Inequality to Accelerate k-Meansの改良
• 省メモリになったらしい

アイデア

• 各点に対し、upper bound(割当クラスタ中心)/lower bound(2番目に近いクラスタ中心)を1つ持つ

アルゴリズム

• 各点について、
• Elkanのように、u(x)で刈れるかチェック
  • $$ u(i) \leq l(i) $$ or $$ u(i) \leq s(a(i))/2 $$ なら刈れる
  • 刈れなかったらu(x)を計算しなおしてまたチェック
• それでも刈れなかったら、O(kd)で一番近いのとupper bound、lower boundを計算
  • 全部計算するので、tightな値。lower boundは2番目
• sqrtの計算は省いているらしい

クラスタ中心の移動とboundの更新

• どのくらい動いたかをメモっておく（論文内p）
• upper boundは割当クラスタなので、↑のp(a(i))だけ増やしておく
• lower boundは2番目なので、p(j)からゴニョゴニョする

実験

• seedはk-means++で与える

データセット

結果

• 距離計算の回数では無く実行時間で
  • getrusageを使ったとまで書いてある
    • ｲｹﾒｿ
• Elkanのには高次元では劣るらしい

SDM k-means

2013-10-12 18:16:29 (Sat)