Streaming k-means approximation

論文

実家に帰省中，電車の中で読んでた論文の紹介。

概要

k-meansはクラスタリングテクニックとして非常に基本的な手法である。
しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。
ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている

ストリームアルゴリズムについて

本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。

k-meansとは

k-meansとはデータ点 X = {x_1 , ... x_n}に対してクラスタ中心 C={c_1, ... , c_k}を考えたとき、以下の量
\phi = \sum_{i=1}^n D(x_i,C)
を最小にするCを求めるアルゴリズムである。ここでD(x,C)はCの中で最もxに近いものの距離である。アルゴリズムに関してはWikipedia:K平均法を参考にされたい。

k-means++

k-meansの弱点として初期値が良くない場合，得られるクラスタの質が悪い事がある。そこでk-means++と言う方法が提案されている[2]。
k-means++については著者のページ以外に以下のサイトが参考になる

概要だけ話すと

  • 1. ランダムにXの中から1点選び，Cに追加
  • 2. k-1回繰り返す
  • 2.1 Xの中からD(x,C)^2に比例する確率でxを選択しCに追加する

というアルゴリズムである。これを用いる事によって最適解のO(log k)近似の解を得る事が出来る。

k-means #

k-means #はk-means++を発展させた方法で次のようなアルゴリズムである

  • 1. ランダムにXの中から3 log k点選び，Cに追加
  • 2. k-1回繰り返す
  • 2.1 Xの中からD(x,C)^2に比例する確率でxを3log k個独立に選択しCに追加する

k-means++と比べ，一回の選択で3log k個の点を取っている。これによって最適解に比べO(1)の近似解が得られる。

ワンパスアルゴリズム

前述のk-means #は例えば1000個のクラスタに分割したいのに30000個のクラスタ中心を求めるのは，一見意味の無い事のように思える。

しかし，この方法はストリームアルゴリズムに応用することができる。
(追記：このアルゴリズムの小さなクラスタを作って併合するというのは論文のオリジナルではなく，文献[3]の手法を用いているとあります。あと，論文のAlgorithm 3ではA,A'などk-means++，k-means#だけではなく任意のクラスタリングアルゴリズムを利用できるような形で書いてある。)

  • 1. データ集合SをS_1,...S_l に分割する
  • 2. 各S_iに対して
  • 2.1 k-means #を実行してO(k log k)の個数のクラスタ中心T_iを求める
  • 3. S_w <- T_1 \cup ... \cup T_lとして各ストリームにおけるクラスタ中心を合併する。ここで各中心に対してそのクラスタに帰属する点の個数の重みをのせる
  • 4. k-means++ をS_wに対して実行してk個のクラスタ中心を得る。

各S_iに関してT_iを求めたあとはS_iの中のデータ点の情報はメモリから捨てて良い事に注意する。
ここで各S_iのサイズがO(sqrt(nk))であればO(sqrt(log k sqrt(nk)))のメモリが必要となり，これは通常のk-meansで必要なO(n)のメモリ量に比べ少なくすんでいる。またTheorem 3.1.によりこの方法により得られる解がO(log k)の近似解となっていることが示される。

また論文では上の手続きを更に階層化する方法について述べている。これについてはVideo Lectureのスライドが参考になる。*1

実験

いくつかのデータセットに対して彼らの手法を普通のk-meansと比較している。論文の説明とVideo Lectureのスライドのグラフの説明をみるとBLが普通のk-means，OLがOnline版のk-means，DC-1は上のストリームアルゴリズムk-means#のところにk-means++を用いているもの，DC-2は上のストリームアルゴリズムである。これを見るとストリームアルゴリズムであるDC-1,DC-2の方が通常のk-meansよりも良い解が出ている事がわかる。

その他

上述のアルゴリズムにおいては4が終了するまでクラスタ中心が確定しないのでデータ点がどのクラスに割り当てられるかは直接には得る事が出来ないけど，このあたりをうまいこと出来ないかなと思った。
あと，実験では目的関数の値しか出してないけど実際のデータを使った場合に精度とか中心点の様子とかがどうなるのかについて追試してみようかと思いました。

参考文献

[1] Nir Ailon, Ragesh Jaiswal, Claire Monteleoni: Streaming k-means approximation. NIPS, 2009.
[2] David Arthus and Sergei Vassilvitskii: k-means++:the advantages of careful seeding. SODA, 2007.
[3] S. Guha, A. Meyerson, N. Mishra, R. Motwani and O'Callaghan. "Clustering data streams: Theory and practice" , IEEE Transactions on Knowledge and Data Engineering, 2003

*1:これはICMLのワークショップなのですが，このあと論文にしてNIPSに通したみたいです