A Local Search Approximation Algorithm for k-Means Clustering

A Local Search Approximation Algorithm for k-Means Clustering

  • Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y.Wu
  • In SCG 2002
    • Symposium on Computational Geometry

概要

  • k-meansアルゴリズム
  • 多項式時間で(9+ε)-近似

Single-Swap ヒューリスティクス

  • 山登り法
    • 初期状態から状態遷移していき、局所解を答えとする
    • 状態: k個の施設
    • 遷移: k個の施設の内1つを残りのn-k個と交換(だから、Single-Swap)
  • この時の局所解は、25-近似

Multi-Swap ヒューリスティクス

  • 交換の個数を複数にする
    • 定数pに対して、p'(≦p)個をまとめて交換する
    • 当然、局所解に至るまで時間がかかるが、その局所解より良いものになる
  • 近似比は、(3+2/p)^2
    • pがある程度大きければ、大体9

実験

比較手法

  • 1-swap(提案手法)
  • 2-swap(提案手法)
  • Lloydのアルゴリズム
  • 1-swap + Lloydのアルゴリズム:最初にswapして、その後Lloyd
  • 2-swap + Lloydのアルゴリズム

実験結果

k-meansコスト

  • 良い順に
  • 2-swap + Lloyd、1-swap + Lloyd、Lloyd、2-swap、1-swap

実行時間

  • 早い順に
  • swap、Lloyd、swap + Lloyd

戯言

  • この局所探索法は、ぶっちゃけ遅い。遷移が、O(kn)通りあるし、再計算も上手くやってもO(n)位かかる。ただ、一回だけの実行に関しては最高の解を出してくれる。k-means++とかだと何回か実行した方が良い。

SCG k-means

2013-10-07 15:40:54 (Mon)

タグ:

k-means SCG
最終更新:2013年10月07日 15:40