A Local Search Approximation Algorithm for k-Means Clustering

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman and Angela Y. Wu. A Local Search Approximation Algorithm for k-Means Clustering. In Proceedings of the eighteenth annual symposium on Computational geometry (2004), pp. 10-18.

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のアルゴリズム

結果

コストについては，良い順に
2-swap + Lloyd，1-swap + Lloyd，Lloyd，2-swap，1-swap
時間は，早い順に
swap，Lloyd，swap + Lloyd
らしい．

戯言

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