k-means++: The Advantages of Careful Seeding

一人輪講

David Arthur and Sergei Vassilvitskii, k-means++: The Advantages of Careful Seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (2007), pp. 1027-1035.

言わずと知れたk-meansアルゴリズム（Lloydのアルゴリズム）の改良版．元のアルゴリズムの問題点である初期値依存性を解決し，Θ(log k)近似を達成．

問題

d:id:todo314:20121007 参照．

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アルゴリズムを実行

競合比

k-means++が出力した解のコストの期待値は，最適コストの8(ln k+2)倍で抑えられる．また，Ω(log k)近似でもある．（なので論文で証明している近似は結構タイト）

一般化

k-meansクラスタリングは，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)近似になることを証明できることだと思う（そのまんまか…）．