データ クラスタリング

  • [アーティクル]

K- 平均法クラスタリングを使用して異常データを検出する

James McCaffrey

 

 

非常に大きなデータ セットの中にある異常データ項目を特定する問題を考えてみます。たとえば、不正なクレジット カード取引や危険なローン アプリケーションなどを特定するような場面です。異常データを検出する 1 つの方法に、データ項目を類似クラスターに振り分け、各クラスターの中でなんらかの形で他と異なるデータ項目を探す方法があります。

さまざまなクラスタリング アルゴリズムがありますが、最も古くから、広く使われているものの 1 つに K- 平均法 (K-Means) アルゴリズムがあります。今回は、K- 平均法アルゴリズムのしくみを説明し、完成した C# デモ プログラムを紹介します。これまで数多くのスタンドアロン データ クラスタリング ツールが作成されています。それなのに、なぜ、今回 K- 平均法クラスタリングのコードをゼロから作成するのでしょう。これまでのクラスタリング ツールはソフトウェア システムに組み込むのが困難または不可能なものが多く、通常とは異なるシナリオを扱うためにカスタマイズすることができず、著作権などの知的所有権の問題が生じる可能性があります。しかし、今回の記事を一読すれば、K- 平均法クラスタリングを試して、.NET アプリケーションにクラスタリング機能を追加する基礎知識が身に付きます。

K- 平均法クラスタリングの概要を把握し、今回の内容を知るために、まず図 1 をご覧ください。このデモ プログラムでは、まず 20 個のデータ項目から成るダミー セットを作成しています。クラスタリングの用語では、データ項目をタプルと呼ぶことがあります。今回の場合、各タプルは人を表し、身長 (インチ単位) と体重 (ポンド単位) の 2 つの数値属性を持ちます。K- 平均法アルゴリズムには、データのタプルがすべて数値でなければならないという制限があります。

Clustering Using K-Means図 1 K- 平均法を使ったクラスタリング

ダミー データはメモリ内の配列に読み込みます。クラスターの数は 3 にします。使用する最適なクラスター数を提案できる高度なクラスタリング技法もありますが、一般には、データ クラスタリングは探索的なプロセスで、使用するクラスターの最適な数は多くの場合試行錯誤の末に見出されます。この後説明するように、K- 平均法クラスタリングは反復プロセスです。デモ プログラムの変数 maxCount を、クラスタリングのメイン ループの実行回数の制限に使用し、ここでは意図的に 30 回に設定しています。

次に、K- 平均法アルゴリズムを使って、各データ タプルを 3 つのクラスターのいずれかに配置します。クラスタリング コードの作成には、さまざまな方法があります。今回は、クラスタリングを int 型の配列で定義します。この配列では、配列のインデックスが 1 つのタプルを表し、関連する配列値は 0 から始まるクラスター ID を表します。図 1 では、タプル 0 (65.0, 220.0) がクラスター 0 に、タプル 1 (73.0, 160.0) がクラスター 1 に、タプル 2 (59.0, 110.0) がクラスター 2 に、タプル 3 (61.0, 120.0) がクラスター 2 に、というように割り当てられ、クラスター 0 には 8 個のタプル、クラスター 1 には 5 個のタプル、クラスター 2 には 7 個のタプルが割り当てられているのがわかります。

次に、デモ プログラムはクラスター単位に分けられたデータを表示します。クラスター化されたデータを調べると、クラスター 0 には体重の重い人、クラスター 1 には背の高い人、クラスター 2 は背の低い人が振り分けられているのがわかります。デモ プログラムでは、クラスター 0 に割り当てられたタプルを分析し、ある基準で判断した結果、タプル 5 (67.0, 240.0) が最も異常なタプルであると結論付けています。

ここからは、コードを読者のニーズに合わせて修正できるように、図 1 のスクリーンショットを生成するコードについて説明します。今回は、C ファミリーの言語の中級以上のプログラミング スキルがあることを前提にしていますが、データ クラスタリングについては何も知らなくても問題ありません。デモ プログラムは C# を使ってコーディングしましたが、OOP ではない手法を採用したため、デモを他の言語にリファクタリングする必要があってもそれほど難しくは感じないでしょう。ここでは、デモ プログラムのすべてのソース コードを示します。ソース コードは、archive.msdn.microsoft.com/mag201302kmeans (英語) からも入手できます。

K- 平均法アルゴリズム

少なくとも、K- 平均法アルゴリズムの原理は非常に単純です。ただ、後で示す実装は、細かい部分にやや複雑なところもあります。K- 平均法アルゴリズムの中心にある考え方は、重心です。データ クラスタリングでは、グループを最も代表的に表している 1 つのタプルが、データ タプルのセットの重心です。わかりやすいように例を使って説明します。図 1 で示したのとよく似た身長と体重から成る 3 つのタプルがあるとします。

[a] (61.0, 100.0)
[b] (64.0, 150.0)
[c] (70.0, 140.0)

どのタプルが最も代表的なタプルと言えるでしょうか。1 つの方法は、数学的にタプルの平均を計算し、その平均値に最も近いタプルを重心として選択する方法です。つまり、上記の 3 つのタプルの平均タプルは次のように計算されます。

[m] = ((61.0 + 64.0 + 70.0) / 3, (100.0 + 150.0 + 140.0) / 3)
    = (195.0 / 3, 390.0 / 3)
    = (65.0, 130.0)

では、この (65.0, 130.0) に最も近いのは 3 つのタプルのうちどれでしょう。最も近いタプルを定義する方法もいくつかあります。デモ プログラムで使用しているのは、ユークリッド距離を使う最も一般的な方法です。2 つのタプルの間のユークリッド距離は、タプルの構成要素の差をそれぞれ 2 乗して合計した値の平方根です。ここでも、例を使って説明する方がわかりやすいでしょう。タプル (61.0, 100.0) と平均タプル (65.0, 130.0) のユークリッド距離は次のようになります。

dist(m,a) = sqrt((65.0 - 61.0)^2 + (130.0 - 100.0)^2)
          = sqrt(4.0^2 + 30.0^2)
          = sqrt(16.0 + 900.0)
          = sqrt(916.0)
          = 30.27

同様に、他の 2 つのタプルの距離は次のようになります。

dist(m,b) = sqrt((65.0 - 64.0)^2 + (130.0 - 150.0)^2)
          = 20.02
dist(m,c) = sqrt((65.0 - 70.0)^2 + (130.0 - 140.0)^2)
          = 11.18

3 つの距離のうち最も小さいのは、数学平均とタプル [c] の距離なので、3 つのタプルの重心はタプル [c] になります。デモ プログラムの 2 つのタプル間の距離とは異なる定義を使って、生成される最終的なクラスタリングにどのように影響するかを試してみたいと思うかもしれません。

クラスター重心の考え方を決めれば、K- 平均法アルゴリズムは比較的シンプルです。擬似コードは次のようになります。

assign each tuple to a randomly selected cluster
compute the centroid for each cluster
loop until no improvement or until maxCount
  assign each tuple to best cluster
   (the cluster with closest centroid to tuple)
  update each cluster centroid
   (based on new cluster assignments)
end loop
return clustering

Web を検索すると、実際の K- 平均法アルゴリズムの優れたオンライン アニメーションがいくつか見つかります。図 2 の画像は、今回のデモ プログラムで生成したクラスタリングを示しています。各クラスターの円で囲んだデータ項目が、そのクラスターの重心です。

Clustered Data and Centroids
図 2 クラスタ－に振り分けたデータと重心

プログラムの全体構造

図 1 に示したデモ プログラムの全体構造は、いくつか小さな変更を加え、図 3 にリストを示しています。今回は Visual Studio 2010 を使用して ClusteringKMeans という新しい C# コンソール アプリケーションを作成しましたが、最近のバージョンの Visual Studio ならすべて同様に機能します。ソリューション エクスプローラー ウィンドウで、Program.cs というファイル名を ClusteringKMeansProgram.cs に変更したため、テンプレートで生成されたクラスも自動的に名前が変更されています。ファイルの先頭で using ステートメントを使用して不要な名前空間参照を削除しています。

図 3 プログラムの全体構造

using System;
namespace ClusteringKMeans
{
  class ClusteringKMeansProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin outlier data detection demo\n");
        Console.WriteLine("Loading all (height-weight) data into memory");
        string[] attributes = new string[] { "Height", "Weight" };
        double[][] rawData = new double[20][];
        rawData[0] = new double[] { 65.0, 220.0 };
        rawData[1] = new double[] { 73.0, 160.0 };
        rawData[2] = new double[] { 59.0, 110.0 };
        rawData[3] = new double[] { 61.0, 120.0 };
        rawData[4] = new double[] { 75.0, 150.0 };
        rawData[5] = new double[] { 67.0, 240.0 };
        rawData[6] = new double[] { 68.0, 230.0 };
        rawData[7] = new double[] { 70.0, 220.0 };
        rawData[8] = new double[] { 62.0, 130.0 };
        rawData[9] = new double[] { 66.0, 210.0 };
        rawData[10] = new double[] { 77.0, 190.0 };
        rawData[11] = new double[] { 75.0, 180.0 };
        rawData[12] = new double[] { 74.0, 170.0 };
        rawData[13] = new double[] { 70.0, 210.0 };
        rawData[14] = new double[] { 61.0, 110.0 };
        rawData[15] = new double[] { 58.0, 100.0 };
        rawData[16] = new double[] { 66.0, 230.0 };
        rawData[17] = new double[] { 59.0, 120.0 };
        rawData[18] = new double[] { 68.0, 210.0 };
        rawData[19] = new double[] { 61.0, 130.0 };
        Console.WriteLine("\nRaw data:\n");
        ShowMatrix(rawData, rawData.Length, true);
        int numAttributes = attributes.Length;
        int numClusters = 3;
        int maxCount = 30;
        Console.WriteLine("\nk = " + numClusters + " and maxCount = " + maxCount);
        int[] clustering = Cluster(rawData, numClusters, numAttributes, maxCount);
        Console.WriteLine("\nClustering complete");
        Console.WriteLine("\nClustering in internal format: \n");
        ShowVector(clustering, true);
        Console.WriteLine("\nClustered data:");
        ShowClustering(rawData, numClusters, clustering, true);
        double[] outlier = Outlier(rawData, clustering, numClusters, 0);
        Console.WriteLine("Outlier for cluster 0 is:");
        ShowVector(outlier, true);
        Console.WriteLine("\nEnd demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main
    // 14 short static method definitions here
  }
}

説明を簡単にするために、ここでは静的メソッドを使い、すべてのエラー チェックを省略しました。デモ コードの冒頭部分で、クラスタリングする身長と体重のデータを設定しています。20 個のタプルしかないため、データをハードコーディングし、rawData というメモリ配列にデータを格納しました。一般に、データはテキスト ファイルか SQL テーブルに格納します。このような場合はヘルパー関数を作成して、データをメモリに読み込みます。データ ソースが大きすぎてコンピュータ－のメモリに収まらない場合は、デモのコードを修正してデータ配列ではなく外部のデータ ソースを反復処理するようにする必要があります。

データそのもの (rawData) を設定したら、ヘルパー関数 ShowMatrix を呼び出してデータを表示します。次に、変数 numAttributes に 2 (身長と体重)、numClusters に 3、maxCount に 30 を代入します。前述したように、maxCount はアルゴリスムのメイン処理ループの反復回数の上限です。K- 平均法アルゴリズムはすぐに収束する傾向がありますが、maxCount の値を変えて少し実験してみることも必要です。

クラスタリングの作業は、すべて Cluster メソッドで実行します。このメソッドは、各タプルをいずれかのクラスターに割り当てる方法を定義する int 配列を返します。完了すると、クラスタリングをエンコードして表示し、クラスターに従ってグループに振り分けたデータそのものも表示します。

最後に、Outliers メソッドを使用して、クラスタリングしたデータから異常である可能性がある外れ値のタプルを分析します。このメソッドはクラスター ID を受け取り、クラスターの重心 (最も代表的なタプル) から最も遠い (ユークリッド距離で測定) データ タプルの値を返します。ここでは、体重の重い人のクラスターであるクラスター 0 の外れ値タプルは (67.0, 240.0) で、最も重い人を表します。

クラスターの重心を計算する

クラスターの重心はクラスターに割り当てられたすべてのタプルを最もよく表すタプルで、クラスターの重心の算出方法の 1 つはタプルの数学平均を計算し、その平均タプルに最も近いタプルを見つける方法だと説明しました。クラスターごとに数学平均タプルを計算しているのが UpdateMeans ヘルパー メソッドです (図 4 参照)。

図 4 UpdateMeans メソッド

static void UpdateMeans(double[][] rawData, int[] clustering,
  double[][] means)
{
  int numClusters = means.Length;
  for (int k = 0; k < means.Length; ++k)
    for (int j = 0; j < means[k].Length; ++j)
      means[k][j] = 0.0;
  int[] clusterCounts = new int[numClusters];
  for (int i = 0; i < rawData.Length; ++i)
  {
    int cluster = clustering[i];
    ++clusterCounts[cluster];
    for (int j = 0; j < rawData[i].Length; ++j)
      means[cluster][j] += rawData[i][j];
  }
  for (int k = 0; k < means.Length; ++k)
    for (int j = 0; j < means[k].Length; ++j)
      means[k][j] /= clusterCounts[k]; // danger
  return;
}

UpdateMeans メソッドでは、配列を作成して返すのではなく、means という配列の配列が既に存在するものとしています。そのため、配列 means を参照パラメーターにしています。配列 means は、次の Allocate というヘルパー メソッドを使用して作成します。

static double[][] Allocate(int numClusters, int numAttributes)
{
  double[][] result = new double[numClusters][];
  for (int k = 0; k < numClusters; ++k)
    result[k] = new double[numAttributes];
  return result;
}

配列の配列 means の最初のインデックスはクラスター ID を、2 つ目のインデックスは属性を表します。たとえば、means[0][1] = 150.33 の場合、クラスター 0 のタプルの体重 (1) の平均値が 150.33 であることを表します。

UpdateMeans メソッドは、配列 means の既存の値をゼロにして、それぞれのデータ タプルを反復処理し、各クラスターのタプル数を集計して、それぞれの属性の合計を積算し、該当するクラスター数でそれぞれの積算した合計値を除算します。クラスター数が 0 だとメソッドが例外をスローするため、エラー チェックを追加する必要があります。

ComputeCentroid メソッド (図 5 参照) は、重心 (クラスターの平均タプル値に最も近いタプル値) を算出します。

図 5 ComputeCentroid メソッド

static double[] ComputeCentroid(double[][] rawData, int[] clustering,
  int cluster, double[][] means)
{
  int numAttributes = means[0].Length;
  double[] centroid = new double[numAttributes];
  double minDist = double.MaxValue;
  for (int i = 0; i < rawData.Length; ++i) // walk thru each data tuple
  {
    int c = clustering[i]; 
    if (c != cluster) continue;
    double currDist = Distance(rawData[i], means[cluster]);
    if (currDist < minDist)
    {
      minDist = currDist;
      for (int j = 0; j < centroid.Length; ++j)
        centroid[j] = rawData[i][j];
    }
  }
  return centroid;
}

ComputeCentroid メソッドは、指定したクラスターに含まれていないタプルをスキップしながら、データ セットの各タプルを反復処理します。指定したクラスターのタプルごとに、Distance ヘルパー メソッドを使用して、タプルとクラスターの平均タプルとのユークリッド距離を計算します。平均タプルに最も近い (距離が最も短い) タプル値を格納して返します。

UpdateCentroids メソッドは、クラスターごとに ComputeCentroid を呼び出して、すべてのクラスターの重心を求めます。

static void UpdateCentroids(double[][] rawData, int[] clustering,
  double[][] means, double[][] centroids)
{
  for (int k = 0; k < centroids.Length; ++k)
  {
    double[] centroid = ComputeCentroid(rawData, clustering, k, means);
    centroids[k] = centroid;
  }
}

UpdateCentroids メソッドは、centroids という配列の配列が存在するものとしています。配列 centroids は、配列 means とよく似ていて、最初のインデックスはクラスター ID を、2 つ目のインデックスはデータ属性を表します。

つまり、各クラスターには重心があり、それはそのクラスターを最も表すタプルです。各クラスターで平均タプル (mean) に最も近い 1 つのタプルを見つけ、重心値を計算します。各データ タプルには、クラスターの重心が平均タプルに最も近いクラスターを割り当てます。

Distance 関数とデータの正規化

ComputeCentroid メソッドは、Distance メソッドを呼び出してクラスター平均に最も近いデータ タプルを決定します。既に説明したように、タプルと平均タプルの距離を求めるには、ユークリッド距離を使うのが最も一般的です。

static double Distance(double[] tuple, double[] vector)
{
  double sumSquaredDiffs = 0.0;
  for (int j = 0; j < tuple.Length; ++j)
    sumSquaredDiffs += Math.Pow((tuple[j] - vector[j]), 2);
  return Math.Sqrt(sumSquaredDiffs);
}

距離の定義方法を変えたい場合は、構成要素の差異を表す絶対値を合計する方法もよく使われます。ユークリッド距離は差を 2 乗するため、小さな差よりも大きな差の方が大きく重み付けされます。

K- 平均法クラスタリング アルゴリズムの距離関数の選択に関わるもう 1 つの重要な要素にデータの正規化があります。デモ プログラムでは、未加工のデータ、つまり正規化していないデータを使用しています。体重のタプルは 160.0 、身長のタプルは 67.0 といった値になるため、体重差の方が身長差よりも大きく影響します。多くの状況では、データに手を加えずにクラスタリングを調べるよりも、クラスタリングの前にデータを正規化する方が有効です。データの正規化にはさまざまな方法があります。一般には、属性ごとに平均 (m) と標準偏差 (sd) を計算し、次に属性値 (v) ごとに正規化した値 nv = (v-m)/sd を計算します。

各タプルをクラスターに割り当てる

各クラスターの重心を計算する前述のメソッドを使用して、各タプルをクラスターに割り当てるメソッドを作成できます。その Assign メソッドを図 6 にリストします。

図 6 Assign メソッド

static bool Assign(double[][] rawData, 
  nt[] clustering, double[][] centroids)
{
  int numClusters = centroids.Length;
  bool changed = false;
  double[] distances = new double[numClusters];
  for (int i = 0; i < rawData.Length; ++i)
  {
    for (int k = 0; k < numClusters; ++k)
      distances[k] = Distance(rawData[i], centroids[k]);
    int newCluster = MinIndex(distances);
    if (newCluster != clustering[i])
    {
      changed = true;
      clustering[i] = newCluster;
    }
  }
  return changed;
}

Assign メソッドは、重心値の配列を受け取り、各データ タプルを反復処理します。データ タプルごとに、クラスターの重心との距離を計算し、distances というローカル配列に格納します。この配列のインデックスはクラスター ID を表します。次に、MinIndex ヘルパー メソッドは、配列 distances の中から最短距離値のインデックスを求めます。このインデックスが、タプルに最も近い重心を持つクラスターのクラスター ID です。

以下に、MinIndex ヘルパー メソッドを示します。

static int MinIndex(double[] distances)
{
  int indexOfMin = 0;
  double smallDist = distances[0];
  for (int k = 0; k < distances.Length; ++k)
  {
    if (distances[k] < smallDist)
    {
      smallDist = distances[k]; indexOfMin = k;
    }
  }
  return indexOfMin;
}

Assign では、計算したクラスター ID が配列 clustering に格納されている既存のクラスター ID と異なる場合、配列 clustering を更新し、クラスタリングで 1 つ以上の変化があることを示す Boolean フラグを切り替えます。このフラグを使用して、アルゴリズムのメイン ループを停止します。メイン ループは、最大反復回数を超えたとき、またはクラスタリングに変化がないときに停止します。

この K- 平均法アルゴリズムの実装は、各クラスターに常に 1 つ以上のデータ タプルが割り当てられるものとしています。図 6 に示したように、Assign メソッドではクラスターにタプルが割り当てられていないことは考慮していません。実際には、これは通常問題になりません。このエラー状況を回避するのは、やや複雑です。一般には、配列 centroids と連動する centroidIndexes という配列を作成する方法を使います。既に説明したように、配列 centroids には重心値が格納されていて、たとえばクラスター 2 の重心は (61.0, 120.0) でした (図 2 参照)。配列 centroidIndexes には、[3] など、重心に関連付けられたタプル インデックスを格納します。Assign メソッドの最初の手順では、各クラスターに重心値を格納したデータ タプルを割り当ててから、残りのそれぞれのタプルを反復処理し、クラスターに割り当てます。その結果、すべてのクラスターに少なくとも 1 つのタプルが含まれるようになります。

Cluster メソッド

Cluster メソッド (図 7 参照) は、ここで説明したヘルパー メソッドとサブヘルパー メソッドをすべて呼び出す高度なルーチンで、データ クラスタリングを実際に実行します。

図 7 Cluster メソッド

static int[] Cluster(double[][] rawData, int numClusters,
  int numAttributes,  int maxCount)
{
  bool changed = true;
  int ct = 0;
  int numTuples = rawData.Length;
  int[] clustering = InitClustering(numTuples, numClusters, 0);
  double[][] means = Allocate(numClusters, numAttributes);
  double[][] centroids = Allocate(numClusters, numAttributes);
  UpdateMeans(rawData, clustering, means);
  UpdateCentroids(rawData, clustering, means, centroids);
  while (changed == true && ct < maxCount)
  {
    ++ct;
    changed = Assign(rawData, clustering, centroids);
    UpdateMeans(rawData, clustering, means);
    UpdateCentroids(rawData, clustering, means, centroids);
  }
  return clustering;
}

メインの while ループは、各データ タプルをクラスターに繰り返し割り当て、クラスターごとに新しいタプルの平均を計算して、その平均値から各クラスターの新しい重心値を計算します。クラスターの割り当てに変化がないか、最大回数に達したら、ループは終了します。配列 means は重心の計算のみに使用するため、UpdateCentroids メソッド内部で UpdateMeans を呼び出す方がよいかもしれません。

処理ループを開始する前に、InitClustering メソッドで配列 clustering を初期化します。

static int[] InitClustering(int numTuples, 
  int numClusters, int randomSeed)
{
  Random random = new Random(randomSeed);
  int[] clustering = new int[numTuples];
  for (int i = 0; i < numClusters; ++i)
    clustering[i] = i;
  for (int i = numClusters; i < clustering.Length; ++i)
    clustering[i] = random.Next(0, numClusters);
  return clustering;
}

InitClustering メソッドは、タプル 0 から numClusters-1 までをそれぞれクラスター 0 から numClusters-1 までに割り当て、すべてのクラスターに 1 つ以上のタプルが割り当てられた状態で始まるようにします。残りのタプルは、無作為に選択したクラスターに割り当てます。

K- 平均法クラスタリングの初期化については多くの研究が行われており、ここで紹介した以外の手法も試すことができます。多くの場合、K- 平均法アルゴリズムによって生み出される最終的なクラスタリングは、クラスタリングを初期化する方法によって決まります。

異常データを探す

データ クラスタリングを使用する 1 つの目的は、単にさまざまなクラスタリングを調べ、予期しない異常値を探すことです。クラスター内で通常と異なるデータ タプルを探すこともできます。デモ プログラムでは、Outlier というメソッド (図 8 参照) を使用してクラスター 0 を確認し、そのクラスター内でクラスターの重心から最も遠いタプルを見つけています。

図 8 Outlier メソッド

static double[] Outlier(double[][] rawData, int[] clustering,
  int numClusters, int cluster)
{
  int numAttributes = rawData[0].Length;
  double[] outlier = new double[numAttributes];
  double maxDist = 0.0;
  double[][] means = Allocate(numClusters, numAttributes);
  double[][] centroids = Allocate(numClusters, numAttributes);
  UpdateMeans(rawData, clustering, means);
  UpdateCentroids(rawData, clustering, means, centroids);
  for (int i = 0; i < rawData.Length; ++i)
  {
    int c = clustering[i];
    if (c != cluster) continue;
    double dist = Distance(rawData[i], centroids[cluster]);
    if (dist > maxDist)
    {
      maxDist = dist;
      Array.Copy(rawData[i], outlier, rawData[i].Length);
    }
  }
  return outlier;
}

Outlier メソッドは、平均値と重心の配列を初期化後、指定したクラスターの各タプルを反復処理し、タプルからクラスターの重心までのユークリッド距離を計算して、重心から最も遠いタプルの値を返します。最も遠いデータ タプルのインデックスを返す方法も、別の方法を考える候補の 1 つです。

クラスタリングしたデータから異常データを見つける方法は他にもたくさんあります。たとえば、各タプルと代入したクラスターの重心との平均距離を計算する方法や、クラスターの重心の相互の距離を調べる方法などがあります。

表示ルーチン

最後に、簡略化した表示ルーチンを示します。コード ダウンロードには、多少手を加えたバージョンを含めています。これらの簡略化したルーチンを使用する場合は、Main メソッドの呼び出しを修正する必要があります。データそのもの、平均値、および重心を表示するには、次のルーチンを使用します。

static void ShowMatrix(double[][] matrix)
{
  for (int i = 0; i < numRows; ++i)
  {
    Console.Write("[" + i.ToString().PadLeft(2) + "]  ");
    for (int j = 0; j < matrix[i].Length; ++j)
      Console.Write(matrix[i][j].ToString("F1") + "  ");
    Console.WriteLine("");
  }
}

配列 clustering を表示するには、次のルーチンを使用します。

static void ShowVector(int[] vector)
{
  for (int i = 0; i < vector.Length; ++i)
    Console.Write(vector[i] + " ");
  Console.WriteLine("");
}

外れ値を表示するには、次のルーチンを使用します。

static void ShowVector(double[] vector)
{
  for (int i = 0; i < vector.Length; ++i)
    Console.Write(vector[i].ToString("F1") + " ");
  Console.WriteLine("");
}

クラスター別に振り分けられたデータそのものを表示するには、次のルーチンを使用します。

static void ShowClustering(double[][] rawData, 
  int numClusters, int[] clustering)
{
  for (int k = 0; k < numClusters; ++k) // Each cluster
  {
    for (int i = 0; i < rawData.Length; ++i) // Each tuple
      if (clustering[i] == k)
      {
        for (int j = 0; j < rawData[i].Length; ++j)
          Console.Write(rawData[i][j].ToString("F1") + " ");
        Console.WriteLine("");
      }
    Console.WriteLine("");
  }
}

まとめ

データ クラスタリングは、データの分類と密接に関連していて、混同されることもあります。クラスタリングとは、振り分けるグループについて前提を置かずにデータ項目をグループに振り分ける、特別な規定のない手法です。クラスタリングは、多くの場合、探索的なプロセスです。それに対して、分類とは、振り分けるグループがあらかじめ決められ、振り分け方法が規定されている手法で、各データ タプルはこのようなグループのいずれかに配置されます。分類は、多くの場合、予測の目的に使用します。

今回で紹介したコードと説明では、K- 平均法データ クラスタリングを試し、完全にカスタマイズ可能なスタンドアロン クラスタリング ツールを作成して、外部依存関係に頼らないで .NET アプリケーションにクラスタリング機能を追加するのに必要な情報を提供しました。K- 平均法以外にも多くのクラスタリング アルゴリズムがあり、そのうちデータ エントロピーの最小化、カテゴリ ユーティリティ、単純ベイズ推定などを今後の MSDN マガジンの記事で取り上げる予定です。

Dr. James McCaffrey は Volt Information Sciences Inc. に勤務し、ワシントン州レドモンドにあるマイクロソフト本社で働くソフトウェア エンジニアの技術トレーニングを管理しています。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。彼は、『.NET Test Automation Recipes』(Apress、2006 年) の著者でもあり、jammc@microsoft.com (英語のみ) から連絡できます。

この記事のレビューに協力してくれた技術スタッフの Darren Gehring に心より感謝いたします。