Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with ...

Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup

  • Yufei Ding, Yue Zhao, Xipeng Shen, Madanlal Musuvathi, Todd Mytkowicz
  • ICML 2015

概要

  • k-meansのLloydアルゴリズムの距離計算枝刈り+中心再計算省略による高速化手法

提案手法

  • 三角不等式 $$ |d(x,b)-d(b,c)| \leq d(x,c) \leq d(x,b)+d(b,c) $$
  • $$C,c$$: クラスタ中心の集合、クラスタ中心(のどれか)
  • $$b(x)$$: xの属するクラスタ中心
  • $$C',c',b'(x)$$: 次の反復における対応する点/集合
  • $$\delta(c)=d(c,c')$$: クラスタ中心の移動距離
  • やること
  1. Global filtering: 「各点xのクラスタ中心が変わらない」条件
  2. Group filtering: 「各点xについて、この集合中のクラスタ中心には絶対所属しない」条件
  3. Local filtering: 「各点について、このクラスタ中心には所属しない」条件
  4. 最終的に距離計算をするが、所属クラスタ中心が変わった所だけ見れば、クラスタ中心を更新できる

Global filtering

  • 各点$$x$$について、
  • 上限: $$ \mathrm{ub}(x) \geq d(x,b(x)) $$
    • 「所属クラスタ中心までの距離は高々これこれですよ」
  • 下限: $$ \mathrm{lb}(x) \leq d(x,c) \forall c \in C-b(x) $$
    • 「任意の所属外クラスタ中心までの距離は少なくともこれこれですよ」
  • 下限・上限の更新を自明にやる:
    • $$\mathrm{lb}'(x)=\mathrm{lb}(x)-\max_{c \in C}\delta(c)$$
    • $$\mathrm{ub}'(x)=\mathrm{ub}(x)+\delta(b)$$
  • 補題1:
    • もし、$$ \mathrm{lb}'(x) \geq \mathrm{ub}'(x) $$
      • 展開すると、$$ \mathrm{lb}(x)-\max_{c \in C}\delta(c) \geq \mathrm{ub}(x) + \delta(b) $$
    • なら、xの所属クラスタは変わらない=b(x)を維持
    • あたり前田のクラッカー: (左辺)=任意の所属外クラスタ中心について、(右辺)=所属クラスタ中心について
  • 曲者: lb更新時のmaxδ(c)がデカすぎる時がある
  • →( ^ω^)適当に分割するお!

Group filtering

  • クラスタ中心達をt個$$G_1,\ldots,G_t$$に分割(とりあえず戦略は置いておいて)
  • 下限達: $$ \mathrm{lb}(x,G_i) \leq d(x,c) \forall c \in G_i-b(x) $$
    • 「Gi中の任意の所属外クラスタ中心までの距離は少なくともこれこれですよ」
    • $$\mathrm{lb}'(x, G_i)=\mathrm{lb}(x)-\max_{c \in G_i}\delta(c)$$
  • もし、$$ \mathrm{lb}'(x, G_i) \geq \mathrm{ub}'(x) $$
  • なら、xの所属クラスタはGiの何れにもならない
  • 実際的な話し
    • t=k/10がちょうどよい
    • 最初の分割は、初期クラスタ中心をクラスタリングすると良いらしい
  • 各点xについて、filterされなかったGi達については、更に次を適用:

Local filtering

  • 補題2:
    • $$c' \in G_i'$$について、もし、$$p' \neq c'$$があり、
    • $$ d(x,p') < \mathrm{lb}(x, G_i) - \delta(c) $$
    • なら、c'はxの最近点では無い
  • 各Giのクラスタ中心との距離計算をこれで大幅に省ける
  • p'=これまでに見つかったsecond closest
    • 何故か: $$ \mathrm{lb}'(x, G_i) $$の厳密計算が出来るので、将来お役立ち

クラスタ中心更新

  • 自明な効率的計算をするだけ

実験

  • 比較手法: [Elkan. 2003]と[Drake-Hamerly. 2012]
  • 色々なデータセット(超高次元ではない)でk=4,64,1024,10000
  • Elkanは全クラスタ中心との下限を持っているので、k増大で実は遅くなる
  • Yinyangはt=1ではそこそこ速い、t=k/10の時に既存手法を圧倒
  • 距離計算をどのくらい省けたかとかも調べる

まとめ

  • 2015年にk-meansアルゴリズムの高速化手法
  • Lloydと全く同じ(タイブレークは置いておいて)なのがかなり大事
  • 既存のソフトウェアをそっくりそのまま置き換えられるから
  • Groupingだけがちょっと綺麗でないので、そこを上手くやりたい

ICML k-means

2017/01/01

タグ:

ICML k-means
最終更新:2017年01月01日 18:03