kmeans++ - だれかのメモ帖

論文を先生に提出したら、「kmeans法の初期クラスタ中心をどうしてるのかちゃんと書きなさい」と返って来ました。先生、ごめんなさい。

だがしかし！kmeans clusteringの部分はOpenCVに全て任せている！
もう一度OpenCVのリファレンスを調べ直したところ、
「Arthur および Vassilvitskiiによる kmeans++ の中心初期化手法が利用されます．」
とのこと。

なんじゃそりゃ？ということで調べたことをメモしておこうと思います。

まず、kmeans++の前研究として、「KKZ」という初期クラスタ中心生成手法があるらしいです。
このアルゴリズムは非常に単純で

というものでした。

一見これで初期化問題は万事解決に思えたのですが、文献によると外れ値がある場合に良くないらしい。そこで提案されたのがkmeans++というわけですが、手法の流れの記述で躓いたのでこの記事を書いている次第です。

結論から言うとkmeans++では次のクラスタ中心を確率的に選びます。
すでにあるクラスタ中心との最短距離が大きいデータが次のクラスタ中心により選ばれやすくなるようにするのですが、確率的に選ぶことで必ずしも最大のものが選ばれなくなります。すると、外れ値問題にも対応できるというわけです。

つまり

$\phi(x_j')=\frac{D(x'_j)}{\sum_k D(x_k)}$

が大きい順に確率的に選ぼうということです。
ですが、私はこれを元の論文、
k-means++: The Advantages of Careful Seeding
を読んでやっと理解しました。

というのも、最初に読んだ上の文献では以下のように記述されています。

${0 \leq L \leq \sum_k D(x_k)^2}$

${\sum^{l-1}_i D(x_i)^2 \leq L \leq \sum^l_i D(x_i)^2}$

はずかしながら最初は、何を言ってるんだ？こいつは。状態でしたｗ

しかし実際は、文献にはただルーレット選択でkmeans++を実装したときの流れが書いてあっただけでした。(おれのばか！)

ところで、kmeans++では得られる解と最適解とのコスト比の期待値に上限があるということが証明されています。
初期値をランダムに選ぶkmeansは解がいくらでも悪くなる可能性があったのに対すると解の質がある程度保証されているということなんですかね？？

他の機械学習にも言えますが、実行結果の安定性を保証するというのは大変だと思います。
しかし、実応用する際にはそういう所が大事になってきますし、だからこそkmeans++のような研究が重要になりそうですねー