データ クラスタリング
単純ベイズ推定を利用したデータ クラスタリング
データ クラスタリングとは、販売データをグループに分けて顧客の購買動向を明らかにしたり、ネットワーク データをグループに分けて通信パターンを分析するなど、さまざまな場面で有効かつ実用的に利用できる機械学習の手法です。データ クラスタリングは、異常データの特定にも有効です。今回は、ソフトウェア システムへのクラスタリング機能の追加や、強力なスタンドアロン クラスタリング ユーティリティの作成基盤として使用できる完全な C# プログラムを紹介します。
クラスタリング アルゴリズムの効果はクラスター化するデータの特性にある程度左右されることから、多種多様なクラスタリング アルゴリズムが存在します。最も一般的なのは、K- 平均法 （K-means） クラスタリングというアルゴリズムです。残念ながら、このアルゴリズムは数値データ項目にしか適用できません。これに対して、今回紹介するクラスタリング アルゴリズムは、単純ベイズ推定という手法に基づいており、カテゴリ データと数値データの両方を処理できます。今回のアルゴリズムで使用する考え方は、すべてよく知られたものですが、アルゴリズム全体と固有の実装については、私の知る限り、これまで公開されていません。他のクラスタリング手法と区別するために、このアルゴリズムと実装を、反復的単純ベイズ推定凝集型クラスタリング (INBIAC: Iterative Naive Bayesian Inference Agglomerative Clustering) と名付けました。単純ベイズ推定はデータ分類の非常に一般的な手法ですが、ベイズ推定がデータ クラスタリングにも利用できることはあまり知られていません。
今回の目的は、図 1 をご覧いただければ一目瞭然です。このデモ プログラムでは、まず、8 人の架空の人物について、住所 (Urban (都市)、Suburban (郊外)、Rural (地方))、収入 (Low (低)、Medium (中)、High (高)、VeryHigh (超高))、および政治的態度 (Liberal (進歩)、Conservative (保守)) を示す、8 つのランダムなデータの組を生成します。次に、メモリに未加工の文字列データを読み込み、適切な処理ができるようにそのデータを整数値に変換します。たとえば、(Rural, Low, Conservative) という最後の組は、(2, 0, 1) として格納します。
.png)
図 1 単純ベイズ推定を利用したデータ クラスタリング
INBIAC を含めて多くのクラスタリング アルゴリズムでは、クラスターの数を指定する必要があります。ここでは、変数 numClusters を 3 に設定しています。デモ プログラムではデータをクラスター化し、クラスター化した結果として [2, 0, 2, 1, 1, 2, 1, 0] が表示されます。内部では、アルゴリズムにより組 1、6、0 をそれぞれクラスター 0、1、2 にシードし、次に、残りの 5 組をクラスターに一度に 1 つずつ割り当てています。この種のアルゴリズムを凝集型と呼びます。
データの訓練やユーザーによる操作が不要なため、クラスタリングは「教師なし学習」と呼ばれることもあります。クラスタリング配列の各インデックスは、組を示しており、配列の値はクラスターの ID です。つまり、組 2 (Suburban, VeryHigh, Conservative) はクラスター 2 に割り当て、組 1 (Rural, Medium, Conservative) はクラスター 0 に割り当てています。
デモ プログラムは、クラスター化した形式でオリジナルの未加工データを表示して終了します。ご覧のとおり、最終的なクラスタリングは合理的なように見えます。オリジナルのデータを見ると、このデータを手作業でクラスター化したら、データ セットがとても小さくても非常に難しいことがわかると思います。
今回は、C 言語ファミリーの高度なプログラミング スキルがあることを前提としていますが、単純ベイズ推定やクラスタリング アルゴリズムに関する経験がなくても問題ありません。図 1 に示したデモ プログラムは、スタンドアロンの C# コンソール アプリケーションです。このアプリケーションは、OOP が完全にサポートされない言語に簡単にリファクタリングできるよう、OOP 手法を使用しないでコーディングしています。
考え方ができるだけわかりやすくなるように、エラー チェックはすべて取り除きました。デモ プログラムのコードは非常に長く、ここではすべてを紹介できないため、アルゴリズムの重要な部分の説明に重点を置きます。デモ プログラムのソース コード全体は、archive.msdn.microsoft.com/mag201303INBIAC (英語) で入手できます。
プログラムの構造
プログラムの全体構造は、いくつかのコメントと WriteLine ステートメントを削除していますが、図 2 に示すとおりです。
図 2 クラスタリングのプログラム構造
using System;
using System.Collections.Generic;
namespace ClusteringBayesian
{
class ClusteringBayesianProgram
{
static Random random = null;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin data clustering using Naive Bayes demo\n");
random = new Random(6); // Seed of 6 gives a nice demo
int numTuples = 8;
Console.WriteLine("Generating " + numTuples +
"tuples of location-income-politics data");
string[] rawData = MakeData(numTuples);
Console.WriteLine("\nRaw data in string form is:\n");
ShowData(rawData, numTuples);
string[] attNames = new string[] { "Location", "Income", "Politics" };
string[][] attValues = new string[attNames.Length][];
attValues[0] = new string[] { "Urban", "Suburban", "Rural" };
// Location
attValues[1] = new string[] { "Low", "Medium", "High", "VeryHigh" };
// Income
attValues[2] = new string[] { "Liberal", "Conservative" };
// Politics
Console.WriteLine("Loading raw data into memory\n");
string[][] tuples = LoadData(rawData, attValues);
Console.WriteLine("Converting raw data to int form and" +
"storing in memory\n");
int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
Console.WriteLine("Data in int form is:\n");
ShowData(tuplesAsInt, numTuples);
int numClusters = 3;
int numTrials = 10; // Times to get good seed indexes (different tuples)
Console.WriteLine("\nSetting numClusters to " + numClusters);
Console.WriteLine("\nInitializing Naive Bayes joint counts with " +
"Laplacian smoothing");
int[][][] jointCounts = InitJointCounts(tuplesAsInt, attValues,
numClusters);
int[] clusterCounts = new int[numClusters];
Console.WriteLine("\nBegin clustering data using Naive Bayes " +
"(with equal priors) ");
int[] clustering = Cluster(tuplesAsInt, numClusters, numTrials,
jointCounts, clusterCounts, true);
Console.WriteLine("Clustering complete");
Console.WriteLine("\nClustering in internal form is:\n");
for (int i = 0; i < clustering.Length; ++i)
Console.Write(clustering[i] + " ");
Console.WriteLine("Raw data displayed in clusters is:\n");
DisplayClustered(tuplesAsInt, numClusters, clustering, attValues);
Console.WriteLine("\nEnd demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// Other methods go here
} // class
} // ns
今回は Visual Studio 2010 を使用して、ClusteringBayesian という C# コンソール アプリケーションを作成しました。ソリューション エクスプローラー ウィンドウで、ファイル Program.cs の名前をわかりやすく ClusteringBayesianProgram.cs に変更しました。これにより、唯一のクラスの名前も自動的に変更されます。テンプレートによって生成された .NET 名前空間への不要な参照を削除しました。このプログラムには依存関係がほとんどなく、必要なのは Systems.Collections.Generic 名前空間だけです。
random というクラス スコープの Random オブジェクトを宣言します。このオブジェクトは、半ランダムの未加工データを生成したり、各クラスターにシードする組を判断したりするために使用します。Main メソッドでは、シード値 6 を指定して random のインスタンスを作成します。6 を指定するのは、見栄えのよいデモにするためです。
デモ プログラムの次の数行は、ダミー データを 8 行生成して表示するヘルパー メソッドの MakeData と ShowData です。MakeData では、サブヘルパー メソッドの MakeParty、MakeLocation、MakeIncome、および MakePolitics を呼び出します。特定のデータの組をハードコードして実験する場合は、このコードを次のように置換してもかまいません。
int numTuples = 4;
string[] rawData = new string[] { "Urban,VeryHigh,Liberal",
"Rural,Medium,Conservative", "Urban,Low,Liberal",
"Suburban,Medium,Liberal" };
次に、デモ プログラムでは、Location、Income、および Politics という属性をハードコードしています。未加工のデータがヘッダーを含むテキスト ファイルや列名を含む SQL テーブルに含まれるようなシナリオでは、データをスキャンしてプログラムで属性名を判断することが必要になる場合もあります。
デモ プログラムでは、Location 用の属性値 (Urban、Suburban、Rural)、Income 用の属性値 (Low、Medium、High、VeryHigh)、および Politics 用の属性値 (Liberal、Conservative) もハードコードしています。ここでも、シナリオにより、未加工のデータをスキャンして、プログラムで属性値を判断する必要が生じることもあります。
デモ プログラムでは、未加工の文字列データをメモリ内の配列の配列に読み込むヘルパー メソッド LoadData を呼び出します。大きなデータ セットでは、このような処理はできません。そのような場合は、データの複数のブロックを一度に読み込むか、外部に格納した未加工のデータを一度に 1 行または 1 列ずつ反復処理する必要があります。
未加工の文字列データを直接処理してもかまいませんが、整数型にエンコードしたデータを処理する方が効率的です。そのため、次にヘルパー メソッド TuplesToInts で文字列型の配列の配列を取得して、その配列をスキャンし、各文字列を 0 から始まるインデックスに変換して、そのデータをすべて整数型の配列の配列に格納します。ここでも、大きなデータ セットでは、未加工のデータを一度に 1 行ずつ読み込み、実行中に属性値を整数に変換してもかまいません。
デモ プログラムでは、2 つのパラメーター値を設定して、クラスタリング ルーチンを準備します。パラメーター numClusters は、生成するクラスターの数です。通常、データ クラスタリングは探索処理で、numClusters をさまざまな値にして実験する必要があります (ただし、プログラムで適切なクラスターの数を決定する手法には、興味深いものがいくつかあります)。パラメーター numTrials は、初期クラスタリングを生成するときのクラスタリング ルーチンで使用します。これについて簡単に説明します。
クラスタリング メソッドには、INBIAC アルゴリズムの特定の時点で割り当てられている組の総数を保持する 2 つの配列が必要です。配列 jointCounts は、特定の属性値と特定のクラスターを設定した、クラスター化した組の数を保持します。配列 jointCounts は少し複雑なので、詳細を簡単に説明します。ラプラス スムージングと呼ばれるベイズ流手法の重要な手順の一環として jointCounts の各値を 1 に初期化します。もう 1 つの配列 clusterCounts は、特定の時点で各クラスターに割り当てる組の数を保持します。clusterCounts のインデックスは、クラスターを示し、その値は関連付けられている数です。
クラスタリングは、Cluster メソッドで実行します。Cluster メソッドは、各組に割り当てられたクラスターをエンコードする配列を返します。デモ プログラムでは、最後に、クラスタリング配列を表示し、ヘルパー メソッド DisplayClustered を使用して、クラスターでグループ化した未加工のデータを表示します。
単純ベイズ推定
INBIAC アルゴリズムを理解してデモ コードをニーズに合う形に変更できるようになるには、単純ベイズ推定を理解することが重要です。単純ベイズは、例を見るとよくわかります。図 1 に示したような 8 組があり、各組を 3 つのクラスターのどれかに当てはめるとします。
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
[3] Suburban Low Liberal
[4] Suburban High Liberal
[5] Suburban Low Conservative
[6] Urban Low Liberal
[7] Rural Low Conservative
まず、組 1 をクラスター 0 に、組 6 をクラスター 1 に、組 0 をクラスター 2 にという割り当てで、各クラスターが 1 つのシード組を受け取るとします (方法については後述します)。このようにクラスタリングを行う方法はいくつかありますが、INBIAC アルゴリズムではこの情報を配列として格納します。
[ 2, 0, -1, -1, -1, -1, 1, -1 ]
この配列では、配列インデックスが組、配列値がクラスターを表し、-1 という値は関連付けられた組がクラスターに割り当てられていないことを示しています。したがって、考えとしては、この時点でのクラスタリングは次のとおりです。
c0 : Rural Medium Conservative (tuple 1)
c1 : Urban Low Liberal (tuple 6)
c2 : Suburban VeryHigh Liberal (tuple 0)
次の目標は、まだ割り当てられていない最初の組である、組 2 (Suburban, VeryHigh, Conservative) を、3 つのクラスターのうちの 1 つに割り当てることです。単純ベイズでは、組 2 がクラスター 0、1、および 2 に属する確率を計算して、最も確率が高いクラスターにその組を割り当てます。X = (Suburban, VeryHigh, Conservative)、c0 がクラスター 0 を意味するとして、次のような記号表現にして結果を求めます。
P(c0 | X)
P(c1 | X)
P(c2 | X)
最初の確率は、「X 値が与えられたときのクラスター 0 の確率」と解釈できます。計算は少し待ってください。これらの条件付き確率を計算するには、ここでは部分確率 (PP) と呼ぶ項を計算する必要があります。各クラスターの確率は、各条件付き確率の部分確率を計算した後、その部分確率をすべて足し合わせたものでそのクラスターの部分確率を割ったものに等しくなります。記号で示すと次のようになります。
P(c0 | X) = PP(c0 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c1 | X) = PP(c1 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c2 | X) = PP(c2 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c0 | X) の部分確率は次のとおりです。
PP(c0 | X) = P(Suburban | c0) *
P(VeryHigh | c0) *
P(Conservative | c0) *
P(c0)
= count(Suburban & co) / count c0 *
count(VeryHigh & co) / count c0 *
count(Conservative & c0) / count c0 *
P(c0)
これらの方程式はベイズの定理から導かれており、確率は一意に決まりません。単純ベイズの「単純」という言葉は、部分確率の各確率項が数学的に独立していると仮定することを表します。このことにより、確率項が数学的に依存関係を持つ場合に比べて非常に簡単に計算できます。
最後の項 P(c0) は、「クラスター 0 の確率」です。この項は、事前確率と呼ばれることもあり、2 つの方法のいずれかで計算できます。1 つは、事前確率が等しいと仮定して、P(c0) = P(c1) = P(c2) = 1/3 と計算します。もう 1 つは、事前確率が等しいとは仮定しないで、割り当てられた組の現在の総数を使用して、P(c0) = count(c0) / (count(c0) + count(c1) + count(c2)) と計算します。INBIAC アルゴリズムの場合は、事前確率を等しいと仮定する方が適切です。
方程式では結合数と呼ばれるものが必要なことがわかります。たとえば、count(Suburban & c0) はクラスターが 0 で、組の住所が Suburban である、割り当て済みの組の数です。
現在のクラスタリングをもう一度見てみると、問題があることがわかります。この時点では、最初の 3 つのシード組のみがクラスターに割り当てられており、count(Suburban & c0) は 0 です。そのため、その項は 0 になり、部分確率全体が 0 になります。この問題を避けるために、結合数をすべて値 1 に初期化します。これがラプラス スムージングです。ラプラス スムージングでは、クラスター数の 3 を条件付き確率に加算します (非条件付き確率項には加算しません)。c0 の部分確率を計算し直すと次のようになります。
PP(c0 | X) = P(Suburban | c0) *
P(VeryHigh | c0) *
P(Conservative | c0) *
P(c0)
= count(Suburban & co) / (count c0 + 3) *
count(VeryHigh & co) / (count c0 + 3) *
count(Conservative & c0) / (count c0 + 3) *
1 / numClusters
= (1 / 4) * (1 / 4) * (2 / 4) * (1 / 3)
= 0.0104
同様に、c1 と c2 の部分確率は次のようになります。
PP(c1 | X) = count(Suburban & c1) / (count c1 + 3) *
count(VeryHigh & c1) / (count c1 + 3) *
count(Conservative & c1) / (count c1 + 3) *
1 / numClusters
= (1 / 4) * (1 / 4) * (1 / 4) * (1 / 3)
= 0.0052
PP(c2 | X) = count(Suburban & c2) / (count c2 + 3) *
count(VeryHigh & c2) / (count c2 + 3) *
count(Conservative & c2) / (count c2 + 3) *
1 / numClusters
= (2 / 4) * (2 / 4) * (1 / 4) * (1 / 3)
= 0.0208
各クラスターの部分確率を計算すれば、組 1 をクラスターに割り当てるために必要な各クラスターの確率計算が簡単になります。次にその計算を示します。
P(c0 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0104 / (0.0104 + 0.0052 + 0.0208)
= 0.2857
P(c1 | X) = PP(X | c1) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0052 / (0.0104 + 0.0052 + 0.0208)
= 0.1429
P(c2 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0208 / (0.0104 + 0.0052 + 0.0208)
= 0.5714
最も確率の高いクラスターに組を割り当てます。この場合はクラスター c2 です。
まとめると、組をクラスターに割り当てるには、既に割り当てられている組の結合数を使用して、各クラスターの部分確率を計算します。部分確率は、組が各クラスターに属する確率を計算するのに使用します。最も確率の高いクラスターに組を割り当てます。
重要なデータ構造
INBIAC クラスタリング アルゴリズムで使用するさまざまなデータを格納する方法はいくつかあります。図 3 に、デモ プログラムで使用しているデータ構造の大部分を示します。配列 jointCounts は、部分確率の計算に使用するため、クラスターの確率計算、ひいてはクラスターへの組の割り当てに使用します。属性値とクラスターの組み合わせすべてに結合数 1 が存在します。そのため、デモでは、9 つの属性値 (Urban、Suburban、... Conservative) と 3 つのクラスターがあるため、9 * 3 = 27 の結合数があります。jointCounts の最初のインデックスは属性を、2 つ目のインデックスは属性値を、3 つ目のインデックスはクラスターを示します。たとえば、jointCounts[1][3][2] は、Income (1) が VeryHigh (3) で、クラスターが (2) である割り当て済みの組数を保持します。
.png)
図 3 重要なデータ構造
配列クラスタリングでは組をクラスターに割り当てる方法をエンコードします。配列クラスタリングのインデックスは組を示し、セル値はクラスターを示します。たとえば、clustering[0] = 2 の場合、組 0 をクラスター 2 に割り当てます。セル値 -1 は、関連付けられた組をまだクラスターに割り当てていないことを示します。
クラスタリング メソッドの実装
図 4 に、メソッド Cluster を示します。このメソッドでは、配列 tuplesAsInt (クラスター化するデータ)、numClusters (使用するクラスターの数)、numTrials (クラスターに割り当てる初期組数)、jointCounts (説明済み)、clusterCounts (各クラスターに割り当てる組数。等しくないと仮定する事前確率を計算する場合に必要)、および equalPriors (部分確率を計算するときに各クラスターの確率を計算する方法を示すブール値) を入力として受け取ります。
図 4 Cluster メソッド
static int[] Cluster(int[][] tuplesAsInt, int numClusters,
int numTrials, int[][][] jointCounts, int[] clusterCounts,
bool equalPriors)
{
int numRows = tuplesAsInt.Length;
int[] clustering = new int[numRows];
for (int i = 0; i < clustering.Length; ++i)
clustering[i] = -1;
int[] goodIndexes = GetGoodIndexes(tuplesAsInt, numClusters, numTrials);
for (int i = 0; i < goodIndexes.Length; ++i)
{
int idx = goodIndexes[i];
clustering[idx] = i;
}
for (int i = 0; i < goodIndexes.Length; ++i)
{
int idx= goodIndexes[i];
for (int j = 0; j < tuplesAsInt[idx].Length; ++j)
{
int v = tuplesAsInt[idx][j];
++jointCounts[j][v][i]; // Very tricky indexing
}
}
for (int i = 0; i < clusterCounts.Length; ++i)
++clusterCounts[i];
for (int i = 0; i < tuplesAsInt.Length; ++i)
{
if (clustering[i] != -1) continue; // Tuple already clustered
double[] allProbabilities = AllProbabilities(tuplesAsInt[i],
jointCounts, clusterCounts, equalPriors);
int c = IndexOfLargestProbability(allProbabilities);
clustering[i] = c; // Assign tuple i to cluster c
for (int j = 0; j < tuplesAsInt[i].Length; ++j)
{
int v = tuplesAsInt[i][j];
++jointCounts[j][v][c];
}
++clusterCounts[c];
} // Main loop
return clustering;
}
メソッド Cluster では、まずクラスタリング配列用にメモリを確保し、各セルに値 -1 を割り当てて、関連付けられた組に割り当て済みのクラスターがないことを示します。次に、ヘルパー メソッド GetGoodIndexes を呼び出し、互いに最も違いが大きい組のインデックスを取得します。メソッド GetGoodIndexes について簡単に説明します。メソッド Cluster では、続いて適切なインデックスを使用してクラスター化配列を初期化し、jointCounts と clusterCounts 配列を更新します。
メイン処理ループでは、各データ組を順番に反復処理し、メソッド AllProbabilities を使用して現在の組が各クラスターに属する確率を計算します。次に、最も高い確率のインデックスを、ヘルパー IndexOfLargestProbability を使用して判断します。クラスターは 0 から始まり、そのインデックスが最適クラスターも表すため、現在の組をクラスター (クラスター化配列内) の割り当てや、jointCounts と clusterCounts 配列の更新に使用します。
処理ループは常に組 [0] から始まるので、実際は、インデックス番号の小さい組の方が重み付けが高くなります。代わりに、ランダムな順序で組を処理する方法もあります。INBIAC アルゴリズムでは、クラスターに属する確率の高さに基づいて組を割り当てているのがわかります。最も高い確率の平均を計算して返すこともできます。その結果は、クラスター割り当ての信頼基準になります。その場合は、メソッド Cluster を複数回呼び出して、最も高い信頼を返す呼び出しで作成されたクラスタリングを返すようにします。
よく使用するもう 1 つの方法は、より適切なクラスタリングを試して生成するために、メソッド Cluster で作成したクラスタリングの結果を後処理することです。擬似コードの考え方を次に示します。
loop n times
select a random tuple index
unassign the tuple from its curr cluster
assign the tuple using non-equal priors computation
end loop
INBIAC では現在の組が属する確率が最も高いクラスターを検索して、一度に 1 組をクラスターに割り当てることを思い出してください。確率は事前確率を等しいものとして計算します。つまり、各クラスターの確率は等しいと想定されます。しかし、クラスタリングの後には、各クラスターの相似度合いに関する情報がわかり、その情報をクラスタリングの結果の向上に利用できることがあります。コード ダウンロードでは、このオプションを Refine というメソッドに実装しています。
適切な初期シード組の取得
INBIAC アルゴリズムでは、各クラスターに 1 つの組をシードします。このときのシードする組ができる限り互いに似ていないことが重要です。クラスタリング アルゴリズムで使用する相違点の判断基準はさまざまです。メソッド GetGoodIndexes では、候補インデックスのセットをランダムに生成し、異なる組属性の合計数 (ハミング距離と呼ばれるメトリック値) を計算します。この処理を numTrials 回繰り返し、最も相違点の多い組のインデックスを返します。
たとえば、図 1 のデータを考えてみます。候補のインデックスを、0、1、および 2 とします。対応するデータ組は次のとおりです。
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
組 [0] と組 [1] は 3 点異なります。組 [0] と組 [2] は 1 点異なります。組 [1] と組 [2] は 2 点異なります。差の合計は、3 + 1 + 2 = 6 です。メソッド GetGoodIndexes を擬似コードで表すと次のようになります。
init a result array
loop numTrials times
generate numClusters distinct random tuple indexes
compute their dissimilarity
if curr dissimilarity > greatest dissimilarity
greatest dissimilarity = curr dissimilarity
store curr indexes into result array
end if
end loop
return result array
別のアプローチが必要な場合、Low、Medium、High、および VeryHigh の値を持ち、本質的には数値である Income 属性を監視する高度な方法もあります。その場合は、メソッド GetGoodIndexes を修正して、Low と VeryHigh の差が Low と Medium の差よりも大きくなるようにできます。
異なる候補シード組インデックスの生成には、興味深いちょっとした副作用があります。これは、ヘルパー メソッド GetRandomIndexes により実行されます。このメソッドを擬似コードで表すと次のようになります。
init a dictionary to store result indexes
init a result array
set count = 0
while count < numClusters
generate a random tuple index
if index not in dictionary
add index to result set
add index to dictionary
increment count
end if
end while
return result
この手法はかなり力ずくのアプローチですが、実際、適切に機能します。
まとめ
デモ プログラムのコードに沿って進めてきた今回は、単純ベイズ クラスタリングを実験し、ソフトウェア システムにクラスタリング機能を追加するための基本を詳しく説明しました。ここでは、数字とカテゴリの両方のデータを含む非常に大きなデータ セットを扱うプロジェクトに取り組みながら INBIAC クラスター化アルゴリズムを開発しました。既存のクラスタリング ツールは、非常に低速で、まったく機能しなかったり、結果が不十分だったりしました。今回紹介したアルゴリズムは、カテゴリ データと数値データ (数値データがカテゴリに収められている場合) の両方を処理でき、大きなデータ セットにも対応し、非常に高速です。
冒頭でも触れましたが、最適なクラスタリング アルゴリズムは存在せず、最適の結果を得るためにさまざまなアルゴリズムを試す必要があることが、調査からわかります。単純ベイズ推定に基づくクラスタリングを使用してデータ セットを調査する能力は、お持ちの技術スキルにとって価値あるプラスになるでしょう。
Dr. James McCaffrey は Volt Information Sciences Inc. に勤務し、ワシントン州レドモンドにあるマイクロソフト本社で働くソフトウェア エンジニアの技術トレーニングを管理しています。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。彼は、『.NET Test Automation Recipes』(Apress、2006 年) の著者でもあり、jammc@microsoft.com (英語のみ) から連絡できます。
この記事のレビューに協力してくれた技術スタッフの Dan Liebling に心より感謝いたします。