ディリクレ過程混合モデルでオンラインクラスタリング

データをいくつかのグループに分けるのがクラスタリングですが、
ベーシックなクラスタリングでは、
初めにいくつグループに分けるかを指定しないといけません。

いくつのグループがあるか分からないけど、
クラスタリングしたいということも多いので、
グループの数自体もデータから勝手に判断してくれると便利ですよね。

そこで、グループの数も未知としたモデルとして、
ディリクレ過程混合モデルを使います。

また、通常は、データが揃ってから、
それぞれのデータをグループ分けしていくのですが、
次々に到着するデータを順番にグループ分けしたいという状況もあります。
例えば、受信したメールを受信したタイミングで、
振り分けていくようなイメージですね。

このように、全てのデータが揃っておらず、
逐次的に到着したデータを分類する方法は、
オンラインクラスタリングと呼ばれます。

ということで、グループの数が未知で、逐次分類するという、
クラスタリングの問題に取り組んでみましょう。

ディリクレ過程混合モデル

まずは、ディリクレ過程混合モデルについて簡単にまとめておきましょう。

ディリクレ過程混合モデルは、名前の通り混合モデルの一種なので、
まずは混合モデルって何というところから説明します。

混合モデルとは

混合モデルとは、複数の種類の分布からデータが生成されるモデルで、
グループAはαという分布、
グループBはβという分布に従ったデータが得られるようなモデルです。

このデータを生成する分布の違いを頼りに、
そのデータはどのグループに属するものなのかを、
逆推定することができるので、
混合モデルはクラスタリングの問題と相性が良いのです。

ディリクレ過程混合モデルとは

混合モデルで、いくつの分布があるか、
つまり、いくつのグループが存在するかを、
混合度と呼びます。

簡単なクラスタリングでは、この混合度を固定して、
グループ分けを行います。

一方で、混合度が事前に分からず、
混合度自体もデータから推定したい場合があります。

つまり、モデル上では、
混合度は未知（任意の混合度があり得る）となるような、
混合モデルをベースにクラスタリングを行う必要があります。

このようなモデルとして、ディリクレ過程混合モデルがあります。

ディリクレ過程混合モデルでは、
常に新しい分布からデータが発生する確率があるとすることで、
混合度を制限しない混合モデルを構成しています。

ディリクレ過程混合モデルでは、
あるデータが、グループから得られる確率は、
次のようにモデル化されます。

未知の新しいグループから得られる確率は、

ただし、 はすでに得られたデータの個数です。

一方で、既存のグループから得られる確率は、
そのグループから得られたデータの個数に応じて、

となります。

つまり、沢山のデータが生まれるグループほど、
より多くのデータを生成するモデルです。

が0なら、新しいグループからデータは生まれませんが、
そうでなければ、
常に新しいグループからデータが生まれる可能性があります。

背景にこのようなモデルがあると考えることで、
モデル上は、任意のグループが存在し得ることになります。

粒子フィルタによるオンライン推定

背景のモデルが決まれば、
後はデータと突き合せて推定を行えばクラスタリングができます。

今は、得られたデータを逐次的に処理していきたいので、
その目的に合った粒子フィルタを用いることとします。

粒子フィルターは、逐次的に得られたデータを基に、
背景モデルの推定を行う方法の一つです。

基本的には、モデルを基に、膨大なサンプル点を生成し、
データとサンプル点を照らしながら、
データに合ったサンプル点を残していくことで、
推定を行います。

実行例

それでは、3つの平均が異なる正規分布から生成されたデータを、
上の方法で、逐次的にクラスタリングしていきましょう。

当然、混合度が3であることは、知らない状態で分類を行い、
また、それぞれの分布の平均値が
どこにあるかも知らない状態から始まります。

下のグラフが分類結果（アニメーション）です。
3つの正規分布の平均は、(0,0), (0,1), (1,0) としています。
それぞれ分類されたグループ毎に色付けしています。

最初は、どのグループがどの平均かが定まっていないので、
かなり自由に色付けされていることが分かります。

ある程度分類されたデータが増えてくると、
グループ毎の平均も定まって来て、
左上は緑、左下は赤、右下は黒という風にグループ分けされていきます。

概ね上手くいっていると言って良さそうです。

実行例2（同じグループが続く場合）

上の実行例ではランダムに異なるグループからデータがやってきて、
それを分類するということを行いました。
つまり、1つめのデータは左上のグループから生成されるけど、
2つめは、また別のグループから生成されるという状況です。

これが、続けて同じグループからデータがやってくる場合になるとどうなるでしょう。
つまり、しばらくの間左上のグループからデータが生成された後に、
別のグループから、また、続けてデータが生成されるという状況です。

実際に、そのようなデータを分類させると、
下のような結果になりました。

初めは、左下のグループからデータが生成され続けていて、
それを一つのまとまりとして、黒色に分類できています。

次に、右下のグループからデータがやってくると、
1つめは新しいグループとして、赤色に分類しましたが、
次第に、右下のグループも黒に分類するようになりました。

これは、新しいグループからデータが来たというよりも、
グループの平均値が違っていたと分類器が判断したためです。

ただ、最後に、左上のグループのデータが到着した時には、
新しいグループとして、赤色に分類されています。

この時は、平均値が違うというより新しいグループだとした方が、
モデルに合っていると分類器が判断したことになります。

ディリクレ過程混合モデルでは、
データが続けて同じグループから生成されるというモデルではなく、
グループのサイズに応じて常に確率的に決まります。
このため、毎回、ランダムに別のグループから生成されるようなシチュエーションの方が、
モデルに合っており、1つめの実行例は上手くいきました。

一方で、データが同じグループから続けて生成される、
2つめの実行例では、3つのグループを正しく判別することができませんでした。

まとめ

クラスターの数が分からない状況で、
到着したデータを逐次的に分類する方法を、
ディリクレ過程混合モデル＋粒子フィルターで行ってみました。

データが、ランダムに異なるグループから生成される場合は、
データの蓄積によってうまく分類できるようになるのに対して、
データが、同じグループから続けて生成される場合は、
新しいグループの判断が上手くいかないことがあることが分かりました。