クラスタリングを実装する (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 でらくらく体験」書評

コメント / トラックバック2件 to “クラスタリングを実装する (C#)”

  1. Bellona.Analysis でクラスタリング | Do Design Space Says:

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

  2. K-means++もどきをC#で作ろう | kitayama lab Says:

    […] K-meansそのものを組むのはさすがに嫌なので クラスタリングを実装する(C#) | Do Design Space のものをぱk参考にさせてもらいましょう。 […]


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。