K-means法によるクラスタリングのスマートな初期値選択を行うK-means++

Algorithm

K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不適切な初期値選択をすると間違った解に収束してしまいます。

以下は、Introduction to Information Retrievalの16章に出てくる例です。

{d1, d2, ..., d6}をK=2でクラスタリングする場合、{{d1, d2, d4, d5}, {d3, d6}}が大域最適解ですが、初期クラスタの中心をd2, d5で与えると、{{d1, d2, d3}, {d4, d5, d6}}という誤った解に収束してしまいます。

この問題を改善するK-means++という手法を見つけたので、試してみました。

K-means++では、初期値を単純にランダムに選択する代わりに、以下の手順をとります。

  • 1個目の中心は、ランダムに選択する。
  • 2個目以降の中心は、それまでに選択済みの中心と各個体の最小距離に基づく確率分布によって選択する。

このような初期値選択を行うことで、クラスタリングの正確性が向上し、さらに収束も速くなるようです。アルゴリズムの詳細は、リンク先のPDFを参照してください。

上記の{d1, d2, ..., d6}を使ってK-means++を試してみたところ、97％程度の確率で大域最適解が得られるようになりました（K-means法では66.6％）。

早速HatenarMapsでも、それまで使っていたK-means法をK-means++に置き換えてみたので、今後の地図更新ではクラスタリングの精度が多少上がるのではないかと思います。