k-means をさらに速くする
昨日，今日と電車に乗っている時間が長かったので，暇つぶしに論文を読んでいた．
この論文では，Elkan の三角不等式を用いた k-means の高速化手法
のアイデアを元に，空間計算量を悪化せず k-means を高速化する手法を提案している．手法自体の新規性はそれほどない感じだけど，空間使用率を大幅に改善しつつ，かつ実際に幾つかのデータで Elkan の手法以上の高速化が得られたことに意義があるのかな．
[追記; 2013/02/20] 別解出力をサポートした高速 k-means の C++ 実装を公開 - ny23の日記 で実装を公開しました．自分の専門分野だと，クラスタリングする対象のベクトルの次元数が非常に大きくてかつ疎な場合が多いので（ほとんどの次元の値が 0），疎ベクトルに適用した場合にどうなるか知りたいのだけど，この論文では次元数が小さいデータを用いた実験しかやっていなくて（次元数が大きくなると Elkan の手法に有意に劣る，としか言っていない）あまりよく分からない．というわけで，疎ベクトルを処理するように少し工夫して，電車の中で実装して実験してみたら，確かに効果はあった（素の k-means 比で数倍ぐらい）．
いずれにしても，重要な基本問題（ハードクラスタリング）のためのシンプルで有用なアイデアであることは間違いない．こういうのは道具として持っておいて損はない．初期化に k-means++ を使って c++ で 200+ 行ぐらいなので，速い人なら半日ぐらいで実装できる．
初期化に k-means++ を使う場合と使わない場合で目的関数の値を比較していて思ったのだけど，k-means ではデータやパラメタ（クラスタ数 k）によって，局所最適解の分布がかなり違うような感触がある（目的関数の値に差がつきやすいデータ／パラメタとそうでないデータ／パラメタがある）．クラスタリングと言えば，k-means と PLSA (EM) ぐらいしか実装したことがない全くの門外漢なのだけど，5年以上前 PLSA で確率的な辞書を作った時も，クラス数が小さい時に良くない局所最適解に陥りやすくて困ったことがあった（100回ぐらい初期値を試して，数回非常に良い解に収束する; 初期値の与え方に問題があったのかも知れないけど）．クラスタリングに限らず，大域最適解が求められない問題で，局所最適解の（目的関数の値）分布を知ることはできないのだろうか（それが分かれば，十分最適解に近い解を得るために必要な試行回数の目安が分かる気がする）．
ところで，全然話は変わるけど，自分の専門分野以外の学会から読む論文を選ぶのは，鼻がきかないためなかなか難しい．古い論文だと引用件数で記念碑的な論文かどうか（読んで損がないか）分かるのだけど，この論文ぐらい新しいと，学会の格と著者で判断するしかない．この著者は，たまたま k-means で最適な k を決める G-means (Learning the k in k-means, NIPS 2003) を提案した人と知っていて，かつ G-means の論文では今回の提案手法の元になっている手法を提案した Elkan と共著だったので，読む価値があるかなと思って読んでみたのだった．
[追記] 論文にあった covtype で軽く実験してみた．k=3, 20, 100, 500 と論文と同じ設定でクラスタリングしたところ，（Intel Xeon 3.20 Ghz CPUで）素の k-means が 1.2s (22), 5.6s (76), 69.7s (218), 298.2s (204) のところ，0.7s, 2.0s, 11.3s, 61.1s だった（括弧内は繰り返し回数）．論文では Intel Xeon 2.66 GHhz で素の k-means が 3.5s (19), 48.0s (204), 322.3s (320), 564.1s (111) のところ，3.0s, 7.4s, 42.8s, 169.5s なので（繰り返し回数がズレているのは，150K のサンプル方法の違いか，k-means++ の初期化のランダム性のため）．CPU の差や繰り返し回数の違いを考慮しても2-3倍くらい速くなっているが，これは多分，疎ベクトルの実装が効いているのだと思われる（covtype は非ゼロの次元の割合 r が 0.25 程度なので，密／疎ベクトルのトレードオフを調べてみた - ny23の日記 の結果から推測するに密ベクトルの実装より距離計算は数倍速いはず）．
[追記] バグが取れたらしく，目的関数の値が素の k-means と完全に一致したので，再実験して，実行時間の数値を更新しておいた．もう一つこの論文のいいところを言うと，（既存研究と比較する上でその方が有利だっただけかもしれないが）実際の実行時間で手法の効果を評価しているところがよい（既存研究は距離計算の回数の削減という（理論的には適切な評価基準であるものの）実用上はあまり直接的でない基準で手法の効果を検証している）．そう言えば探索問題で状態数の削減率しか報告しないとか論文とか，どこかの学会でもあったなあ．
