Using the Triangle Inequality to Accelerate k-Means

Using the Triangle Inequality to Accelerate k-Means

  • Charles Elkan
  • In ICML 2003

参考

概要

  • Lloyd's algoの高速化
  • ベクトル間の距離の計算を刈る

補題

Lemma 1

  • $$ d(b,c) \geq 2d(x,b) \Rightarrow d(x,c) \geq d(x,b) $$

Lemma 2

  • $$ d(x,c) \geq \max\{ 0, d(x,b)-d(b,c) \} $$

アイデア

  • 三角不等式、距離の上限・下限を利用
  1. xがcに属している
  • $$ d(c,c')/2 \geq d(x,c) $$ なら $$ d(x,c') \geq d(x,c) $$
  1. $$ d(x,c) $$の上限$$ u \geq d(x,c) $$が既知
  • $$ u \leq \min_{c' \neq c} d(c,c')/2 $$ なら $$ d(x,c') \geq d(x,c) $$
  1. $$ u(x) \geq d(x,c) $$ をx-c間の上限、$$ l(x,c') \leq d(x,c')$$ をx-c'間の下限
  • $$ u(x) \leq l(x,c') $$ なら $$ d(x,c) \leq u(x) \leq l(x,c') \leq d(x,c') $$

アルゴリズム

  • 上の条件を使って枝刈りしながら最近傍のクラスタ中心を求める
  • そのあと、下限と上限をそれぞれ更新する
    • この更新はベクトルの計算をしないで三角不等式で見積もる
  • 各点に対し、upper boundは1種類(割当クラスタ中心)、lower boundはk種類(各クラスタ中心)持つ
  • クラスタ中心同士の距離も計算しておく
  • r(x)は、今のu(x)が期限切れであることを示す

実験

データセット

  • 点数は高々10^5
  • 次元数は2~1000

結果

  • 距離関数の呼び出し回数で比較
  • ばらつきはあるけど、早くなっている
  • kが大きいほうが効果的
  • 低次元のほうが効果的っぽい

ICML k-means

2013-10-12 18:00:36 (Sat)

タグ:

k-means ICML
最終更新:2013年10月12日 18:00