Bellona.Analysis でクラスタリング

以前にクラスタリングを実装する (C#) を投稿しましたが、
クラスタリングの機能をライブラリ化して Bellona.Analysis (GitHub) を作成しました。
NuGet にも同じ名前で登録してあります。

基本となるアルゴリズムは k 平均法 (k-means 法) です。
しかし通常の k 平均法では、

  • 生成されるクラスターの数をあらかじめ指定しなければならない
  • 初期クラスターの重心をランダムで決定するため、再現性がない
    • 偏りがあって納得感のない結果になることもある

という問題点がありました。
そこでこのライブラリでは、クラスター数をあらかじめ指定する通常の方法に加えて、
クラスター数が自動で決定される方法も用意しました。

クラスター数を自動で決定するために、各クラスター内において値のばらつき具合を判定して調整します。
すなわち、ある偏差値を閾値として、それを超える値がクラスター内に存在する場合はクラスターを分割します。
これにより、クラスターとして納得感のない状態を回避します。
また、クラスター数が 1 の状態から開始してクラスターを分割していくため、自然にどこかで収束し、
同じデータを使えば同じ結果が得られます。

基本的な使い方は次の通りです。

 

Train メソッドには、オプション引数として
最大クラスター数 (maxClustersNumber) および最大偏差値 (maxStandardScore) を指定できます。

maxStandardScore の既定値を 1.645 としています。これは、正規分布において 90% 以内を意味します。
データの性質に応じて、この maxStandardScore をチューニングするとよいでしょう。
(maxStandardScore の単位は標準偏差 σ です。偏差値 50, 60, 70 はそれぞれ 0, σ, 2σ に対応します。)

 

なお、クラスター数が 1 の状態から開始してクラスターを分割していくため、処理時間はかなりかかります。
したがってデータ数が大きい場合は、まずクラスター数が固定されたモデルで学習させ、
次に自動モードに変換して再学習するとよいでしょう。

 

サンプル

Bellona.Analysis を利用したサンプルのソースコードは ClusteringSample にあります。

System.Drawing.Color 構造体に含まれる色:

日本の都道府県庁所在地の緯度・経度:

 

バージョン情報
.NET Framework 4.5

広告

クラスタリングを実装する (C#)

以前に Azure Machine Learning で色のクラスタリングを投稿しましたが、
このときはクラウド サービスである Azure Machine Learning を利用してクラスタリングを実行させていました。
しかし、この方法ではネットワークが必要であり、少なくとも現在提供されている機能では、
クライアント アプリケーションなどでリアルタイムに再学習させていくのは難しそうです。

そこで今回は、k 平均法 (k-means 法) によるクラスタリングを自前で実装してみます。

クラスタリングの対象となる各データはそれぞれの特徴を表す属性の集合を持ちますが、
k 平均法は、この属性の集合をベクトル (次元数は属性数) と見なし、
それらの距離が近いもの同士を同じクラスターに振り分けるという単純なものです。

k 平均法の詳細の手順は次の通りです。
なお、各クラスターにおけるデータの平均値を表すベクトルを重心 (centroid) と呼びます。

(0) クラスター数および反復回数を与える

(1) データの集合の中からクラスターの数だけデータを選び、各クラスターの初期の重心とする

(2) すべてのデータを、重心との距離が最も小さいクラスターに割り当てる

(3) (2) の結果として得られた各クラスターで、重心を再計算する

(4) (2)(3) を与えられた回数だけ反復する

この k 平均法のアルゴリズムについては、K-means 法を D3.js でビジュアライズしてみたを参照するとよいでしょう。
クラスタリングの処理が収束していく様子が視覚化されており、理解しやすいと思います。

さて、このアルゴリズムを C# で次のように実装してみました。
(ただし、ここに載せているのは一部です。完全なものは ClusteringConsole – GitHub にあります。)

対象のデータとして System.Drawing.Color で定義されている色の集合を利用し、属性は R, G, B の 3 つとしました。
このコンソール アプリケーションを実行すると、次の図のように結果が出力されます (結果は毎回異なります)。

ClusteringConsole

 

とりあえず単純な方法で実装してみましたが、この方法では、
(1) の段階で等しい値のデータが別々のクラスターの重心として割り当てられると、
データを持たないクラスターが出てくる可能性があります。
したがって、初期の重心を分散させるなど、改良の余地はありそうです。

ちなみに今回はコンソール アプリケーションで作成しましたが、
クラスタリングの結果を視覚化すれば Azure Machine Learning で色のクラスタリング (2) の結果と同じようになるでしょう:

Azure Machine Learning で色のクラスタリング

 

作成したサンプル
ClusteringConsole (GitHub)

参照
k平均法 – Wikipedia
K-means 法を D3.js でビジュアライズしてみた
Azure Machine Learning で色のクラスタリング (1)
「クラウドではじめる機械学習 Azure ML でらくらく体験」書評