k-means++: The Advantages of Careful Seeding - todo314 @ ウィキ

k-means++: The Advantages of Careful Seeding

• David Arthur, Sergei Vassilvitskii
• In SODA 2007

メモ

• Stanford大学の人々

概要

• k-meansアルゴリズム（Lloydのアルゴリズム）の改良版
  • 元のアルゴリズムの問題点である初期値依存性を解決し、Θ(log k)近似を達成。

k-meansアルゴリズムの問題点

• 最適コストとの比に上界が無い
• nとkの値が固定でも、コストがいくらでも悪くなるような入力を作れる

k-means++

• k個のクラスタ中心c1,…ckの初期値を確率的に選択する。

1. 入力点から一様ランダムに初期点c1を選択し、C←{c1}とする
2. 以下をk-1回繰り返す
3. 各入力点xが選ばれる確率を$$ \frac{d^2(x, C)}{\sum_{i}d^2(x_i, C)} $$とし、点を一つ選び（ci）、C←C∪{ci}とする
4. Cを初期値とする、普通のk-meansアルゴリズムを実行

競合比

• 8(ln k+2)-近似
  • 結構タイト？

一般化

• l2以外の距離尺度にも適用可
• 目的関数値の冪がLだった場合は、確率の冪もLに
• この時の近似比を示すには、l2ノルムの時に使っていた内積が使えない
• 三角不等式を使うと（若干弱いけど）近似比が得られる
• 期待値は最適コストの$$ 2^{2L}(\ln k+2) $$倍で抑えられる。

実験

データセット

• Norm25
  • 計算機で生成
  • 25個のクラスタ中心を超次元立方体上で一様ランダムに決定
  • 各中心の付近にガウス分布で点をばらまく
  • 点数：10000
  • 次元数：15
• Cloud, Intrusion, Spam
  • UCI Machine Learning Repositoryから
  • 点数：1024, 494019, 4601
  • 次元数：10, 35, 58

実験設定

• kの値：10, 25, 50
• 各設定の試行回数：20

測定基準

• 最小コスト
• 平均コスト
• 計算時間の中央値

実験結果

• k-means++の圧勝。コストも計算時間もk-meansに比べて優れている。

戯言

• この論文の意義は、元のk-meansアルゴリズムには近似比保証が無いにも関わらず、初期値をイイ感じに選択するだけで、（期待値が）Θ(log k)近似になることを証明できることだと思う（そのまんまか…）。

SODA k-means

2013-10-07 16:00:46 (Mon)