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
実験
比較手法
-
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)
最終更新:2013年10月07日 15:40