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) \} $$
アイデア
-
xがcに属している
-
$$ d(c,c')/2 \geq d(x,c) $$ なら $$ d(x,c') \geq d(x,c) $$
-
$$ 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) $$
-
$$ 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)が期限切れであることを示す
実験
データセット
結果
-
距離関数の呼び出し回数で比較
-
ばらつきはあるけど、早くなっている
-
kが大きいほうが効果的
-
低次元のほうが効果的っぽい
ICML k-means
2013-10-12 18:00:36 (Sat)
最終更新:2013年10月12日 18:00