Bellona.Analysis でクラスタリング

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

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

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

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

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

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

	using System;
	using System.Drawing;
	using Bellona.Analysis.Clustering;
	namespace ClusteringConsole
	{
	class Program
	{
	static void Main(string[] args)
	{
	// 色のデータを用意します (実際にはもっと多く)。
	var colors = new[] { Color.Red, Color.Orange, Color.Yellow, Color.Green, Color.Blue, Color.Indigo, Color.Violet };
	// ClusteringModel.CreateAuto メソッドでモデルを初期化します。
	// ラムダ式で、特徴量を表すベクトルを指定します。
	// Train メソッドで学習させます。
	var model = ClusteringModel.CreateAuto<Color>(c => new double[] { c.R, c.G, c.B })
	.Train(colors);
	// 学習結果のモデルから、クラスターにアクセスします。
	var cluster0 = model.Clusters[0];
	// 各クラスターには 0 から始まる ID が付けられます。
	Console.WriteLine(cluster0.Id);
	// クラスターに含まれる要素を列挙します。
	foreach (var record in cluster0.Records)
	Console.WriteLine(record.Element.Name);
	// 別の色をクラスターに割り当てます (この場合、学習はしません)。
	var assignedCluster = model.Assign(Color.Gold);
	}
	}
	}

view raw Program.cs hosted with ❤ by GitHub

 

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

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

	// 最大クラスター数および最大偏差値を指定して学習させます。
	// 1.5σ は偏差値 65 を意味します。
	var model = ClusteringModel.CreateAuto<Color>(c => new double[] { c.R, c.G, c.B })
	.Train(colors, 20, 1.5);

view raw Program.cs hosted with ❤ by GitHub

 

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

	// クラスター数を固定するには、ClusteringModel.CreateFromNumber メソッドでモデルを初期化します。
	var fixedModel = ClusteringModel.CreateFromNumber<Color>(c => new double[] { c.R, c.G, c.B }, 10)
	.Train(colors);
	// ClusteringModel オブジェクトを AutoClusteringModel オブジェクトに変換します。
	var autoModel = fixedModel.ToAutoModel()
	.Train(new Color[0]);

view raw Program.cs hosted with ❤ by GitHub

 

サンプル

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 にあります。)

	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	using System.Linq;
	namespace ClusteringConsole
	{
	[DebuggerDisplay(@"\{Clusters: {ClustersNumber}, Iterations: {IterationsNumber}\}")]
	public class KMeans<T>
	{
	public int ClustersNumber { get; private set; }
	public int IterationsNumber { get; private set; }
	public KMeans(int clustersNumber, int iterationsNumber)
	{
	ClustersNumber = clustersNumber;
	IterationsNumber = iterationsNumber;
	}
	public Dictionary<int, Record<T>[]> Train(Record<T>[] records)
	{
	var clusters = InitializeClusters(ClustersNumber, records);
	for (var i = 0; i < IterationsNumber; i++)
	TrainOnce(clusters, records);
	return clusters.ToDictionary(c => c.Id, c => c.Records.ToArray());
	}
	static Cluster<T>[] InitializeClusters(int clustersNumber, Record<T>[] records)
	{
	return RandomUtility.ShuffleRange(records.Length)
	.Take(clustersNumber)
	.Select(i => records[i])
	.Select((r, i) => new Cluster<T>(i, r.Features))
	.ToArray();
	}
	static void TrainOnce(Cluster<T>[] clusters, Record<T>[] records)
	{
	Array.ForEach(clusters, c => c.Records.Clear());
	AssignRecords(clusters, records);
	Array.ForEach(clusters, c => c.TuneCentroid());
	}
	static void AssignRecords(Cluster<T>[] clusters, IEnumerable<Record<T>> records)
	{
	foreach (var record in records)
	{
	var cluster = clusters.FirstToMin(c => FeaturesHelper.GetDistance(c.Centroid, record.Features));
	cluster.Records.Add(record);
	}
	}
	}
	[DebuggerDisplay(@"\{{ToDebugString()}\}")]
	public struct Record<T>
	{
	public T Element { get; set; }
	public double[] Features { get; set; }
	string ToDebugString()
	{
	return string.Format("{0}: {1}", Element, FeaturesHelper.ToString(Features));
	}
	}
	[DebuggerDisplay(@"\{{ToDebugString()}\}")]
	class Cluster<T>
	{
	public int Id { get; private set; }
	public double[] Centroid { get; private set; }
	public List<Record<T>> Records { get; private set; }
	public Cluster(int id, double[] centroid)
	{
	Id = id;
	Centroid = centroid;
	Records = new List<Record<T>>();
	}
	public void TuneCentroid()
	{
	if (Records.Count == 0) return;
	Centroid = Enumerable.Range(0, Centroid.Length)
	.Select(i => Records.Average(r => r.Features[i]))
	.ToArray();
	}
	string ToDebugString()
	{
	return string.Format("{0}: {1}: {2} records", Id, FeaturesHelper.ToString(Centroid), Records.Count);
	}
	}
	public static class FeaturesHelper
	{
	public static double GetDistance(double[] p1, double[] p2)
	{
	return Math.Sqrt(p1.Zip(p2, (x1, x2) => x1 - x2).Sum(x => x * x));
	}
	public static double GetNorm(double[] p)
	{
	return Math.Sqrt(p.Sum(x => x * x));
	}
	public static string ToString(double[] p)
	{
	return string.Join(", ", p.Select(x => x.ToString("F3")));
	}
	}
	}

view raw KMeans.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Drawing;
	using System.Linq;
	using System.Reflection;
	using System.Text;
	using System.Threading.Tasks;
	namespace ClusteringConsole
	{
	class Program
	{
	static void Main(string[] args)
	{
	ClusterColors();
	}
	static void ClusterColors()
	{
	var colors = typeof(Color).GetProperties(BindingFlags.Public | BindingFlags.Static)
	.Where(p => p.PropertyType == typeof(Color))
	.Select(p => (Color)p.GetValue(null))
	.Where(c => c.A == 255) // Exclude Transparent.
	.ToArray();
	var records = colors
	.Select(c => new Record<Color> { Element = c, Features = new double[] { c.R, c.G, c.B } })
	.ToArray();
	var clustering = new KMeans<Color>(20, 50);
	var clusters = clustering.Train(records);
	foreach (var cluster in clusters)
	{
	Console.WriteLine(cluster.Key);
	Console.WriteLine(string.Join(", ", cluster.Value.Select(r => r.Element.Name)));
	}
	}
	}
	}

view raw Program.cs hosted with ❤ by GitHub

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

 

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

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

 

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

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

「クラウドではじめる機械学習 Azure ML でらくらく体験」書評

6 月に発売された書籍「クラウドではじめる機械学習 Azure ML でらくらく体験」を献本していただき、
書評を書くことになりました。

Azure Machine Learning の登場により、機械学習の専門の開発者でなくても、機械学習を Web で利用できるようになりました。
本書では機械学習の仕組みと Azure Machine Learning の手順が示されており、
実際のデータで機械学習を試しながら身に付けることができます。

クラウドではじめる機械学習 Azure ML でらくらく体験

 

主な章の構成

• Chapter 3: 機械学習で実現できること
  • 機械学習とは何かを知るための概要
  • おそらく、多くの読者がまず知りたい部分
• Chapter 4～7: 機械学習の各手法 (回帰、クラスタリングなど) についての理論と実践
  • 数学をベースとした、機械学習の仕組みの説明
  • Azure Machine Learning で各手法を使うための手順
• Chapter 8: Web サービス化
  • 任意のアプリケーションから呼び出して使うには、機械学習の Web サービス化が必要
  • 主にソフトウェア開発者向け

 

本書の特徴

機械学習の各手法の理論について、数学をベースとした説明がなされているため、
アルゴリズムの選択やチューニングの指針の理解が深まり、応用範囲が広がるでしょう。
例えば、「線形回帰」と「ベイズ線形回帰」の違いや使い分けについて理解できるようになります。

 

対象となる読者

「難しそう」という先入観で機械学習に手を出せなかった人におすすめします。
想定されるロールは次のような感じでしょうか。

• ソフトウェア開発者
• データ分析者 (開発者とは限らない)

本書には、数学の知識があまりない人でも理解できるようにと義務教育レベルからの数学の解説があります。
しかし、機械学習の仕組みを理解するには数学 (とくに確率統計) への慣れが必要であり、さすがに無理を感じます。
数学の経験を持つ人でも機械学習を机上だけで理解するのは難しく、理論と実践の反復が必要になると思います。

とはいえ、とりあえず手順通りに実行してみればだんだん理解できるようになるのかもしれません。

 

不足を感じる部分

Azure Machine Learning についての説明がところどころ十分ではないように見えます。
例えば次の内容についてです。

• データ型、カテゴリ、ラベルなど
• Web Service Parameters

必要に応じて公式ドキュメントを参照するとよいでしょう。

 

Azure Machine Learning 自体のよいところ

Azure Machine Learning は Web 上のサービスとして提供されており、
しかもドラッグ アンド ドロップを中心とした GUI でモデリングができるため、
ワークフローを短時間で構築できて学習効率が高いです。

また、任意のアプリケーションから機械学習を利用できるようにするためには、
ワークフローを Web サービスとして発行する必要がありますが、ボタン 1 つで発行できるようになっています。

処理をカスタマイズしたい場合は、R や Python で処理を記述することもできます。

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

前回の Azure Machine Learning で色のクラスタリング (2) では、
学習済みのクラスタリング モデルを利用して、新たなデータをクラスターに割り当てる方法を示しました。

この学習済みのクラスタリング モデルは、保存して再利用することができます。
[Train Clustering Model] の出力の左側の ○ を右クリックして、
[Save as Trained Model] をクリックします。

名前を付けます。

これで保存ができました。

Experiment 上で [Trained Models] から選択できるようになります。

 

では次に、この保存した学習済みクラスタリング モデルを Web サービス化してみましょう。
学習済みモデルに [Assign to Clusters] を接続します。

さて、上の図のようにモデリングして、
最終的に ColorData.csv の部分を Web サービスの入力に差し替えればよいはずなのですが、
なぜかこの入力データの部分の行数が少ないと、
結果の Assignments がすべて行数未満の数値になってしまうという現象が発生しています。
(2 行のときは、0 または 1 にしかならない。)

 

仕方がないので、次の図のように、ダミーのデータを 10 件用意しておき、
入力データに追加して Assign to Clusters を通し、Execute R Script で削除するようにしました。

後方の 10 件を削除するための R のスクリプトは次の通りです。

	ds <- maml.mapInputPort(1) # class: data.frame
	rowscount <- nrow(ds)
	ds <- head(ds, n = rowscount - 10)
	maml.mapOutputPort("ds");

view raw remove-rows.r hosted with ❤ by GitHub

[Prepare Web service] をクリックします。

すると、Web サービスの入力および出力を示す青色のモジュールが追加されます。
次の図のように線を接続します。

この状態で実行します。
完了すると、ボタンが [Publish Web service] に変わるので、これをクリックします。

 

これで、Web サービスが発行されました。

HTTP ベースのインターフェイスの説明をはじめとして、ヘルプ ページが自動的に生成されます。
API を呼び出すための Excel ファイルまで用意されています。

[Test] をクリックして、API のテストをしてみましょう。
必要な情報を入力して実行します (今回は色相だけ入力すれば十分です)。

結果は下の部分に表示されます。

 

さらに、C# のコンソール アプリケーションから API を呼び出してみましょう。
サンプル コードがヘルプ ページ上に生成されているので、これをコピーして使います。

NuGet で Microsoft.AspNet.WebApi.Client をインストールして、API キーを設定します。
あとは入力データを設定します (今回は色相だけ入力すれば十分です)。

実行します。
運が良ければ 1 秒程度で結果が返ってきますが、運が悪いと 20 秒くらいかかることもあります。

試してみた操作はこれで以上です。

 

まとめ・注意点

• Machine Learning を利用するにあたり、.NET の知識は必要ありません。
  (Machine Learning 単体では、.NET とは直接関係ありません。)
• クラスタリングはアルゴリズムの選定で迷うところがないので、とりあえずデータさえあればできるという印象です。
• まったく同一のデータ ファイルおよびアルゴリズムで実行すれば結果は同じになりますが、
  評価に関係ない列の値が変わるだけで結果が変わることがあります。
• 現在の Machine Learning は、米国中南部リージョンでのみ提供されています。

 

前回: Azure Machine Learning で色のクラスタリング (2)

作成したサンプル
Clustering Colors 4: Web service API (Azure ML Gallery)
AzureMLSample (GitHub)

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

前回の Azure Machine Learning で色のクラスタリング (1) では、
色データを色相でクラスタリングし、その結果をストレージに出力するところまで完了しました。

このクラスタリングの結果 (ColorData-Hue-10.csv) を WPF で視覚化したものがこちらです。
(全体のソースコードは GitHub の AzureMLSample にあります。)
クラスター数はもう少し大きめでよかったかもしれません。

 

いろいろ評価条件を変えてクラスタリングを試してみましょう。
次の図のように、先ほどのモデルの右側に、同様のモジュールを 3 種類追加します。
モジュールを複数選択して、コピー アンド ペーストすると速いです。

追加した 3 系統では、次のようにパラメーターを設定します。

(i)
クラスター数: 20
対象列: R, G, B
出力ファイル名: ColorData-RGB-20.csv

(ii)
クラスター数: 20
対象列: Hue, Saturation, Brightness
出力ファイル名: ColorData-HSB-20.csv

(iii)
クラスター数: 20
対象列: R, G, B, Hue, Saturation, Brightness
出力ファイル名: ColorData-All-20.csv

 

また、全列の値のスケールを合わせるため、[Normalize Data] を追加しています。
スケールを合わせないと、値の範囲の大きさにより列ごとに重みが変わります。
[Transformation method] で [MinMax] を選択すれば、0 から 1 までの範囲の値に線形変換されます。

 

実行して結果を見てみましょう。
全体的に、色相以外の彩度および明度の特徴も出ています。

(i) R, G, B

(ii) Hue, Saturation, Brightness

(iii) R, G, B, Hue, Saturation, Brightness

 

次に、学習済みのクラスタリング モデルを使って、新たな色データを各クラスターに振り分けてみましょう。

新たな色データとして、NIPPON COLORS – 日本の伝統色に記載されているものを利用します。
最初の ColorData.csv と同じようにデータを準備します。

この色データ (ColorData-JP.csv) をデータセットとしてアップロードし、
色相でクラスタリングしたときの Experiment を次のように変更します。

[Assign to Clusters] は、新たな入力データを学習済みのクラスターに振り分けるためのものです。
プロパティの対象列で Hue を選択します。

実行結果はこの通りです。
最初の ColorData-Hue-10.csv と同様のクラスターに色が振り分けられています。

 

次回は Web サービス化についてです。

前回: Azure Machine Learning で色のクラスタリング (1)
次回: Azure Machine Learning で色のクラスタリング (3)

作成したサンプル
Clustering Colors 2: by various features (Azure ML Gallery)
Clustering Colors 3: Assign new data to clusters (Azure ML Gallery)
AzureMLSample (GitHub)

参照
NIPPON COLORS – 日本の伝統色