[アーティクル]
09/03/2015

2015 年 8 月

Volume 30 Number 8

テストの実行 - K- 平均法++ データクラスタリング

James McCaffrey データクラスタリングとは、類似項目が同じグループになるようにデータ項目をグループ化するプロセスです。グループ化が終わったら、データのクラスターを調べて、有効なリレーションシップが存在するかどうかを確認します。たとえば、大量の売上データをクラスタリングした場合、各クラスターに含まれるデータに関する情報から、ターゲットにする市場に使用できるパターンが明らかになる可能性があります。

クラスタリングには複数のアルゴリズムがあります。最もよく使われるクラスタリングアルゴリズムの 1 つが K- 平均法です。K- 平均法には、いくつかバリエーションがあります。今回は、K- 平均法++ アルゴリズムという比較的新しい手法について説明します。

まずは、図 1 のデモプログラムをご覧ください。プログラムは 20 個のデータ項目を用意するところから始まります。各項目は、身長 (インチ) と体重 (ポンド) で構成されます。次に、クラスターの数を 3 に設定しています。データクラスタリングのシナリオの多くは、利用者がクラスターの数を指定しなければなりません。

図 1 K- 平均法++ クラスタリングの動作

続いてデモプログラムは、K- 平均法++ アルゴリズムを使用してデータをクラスターに振り分けます。20 個のデータ項目はそれぞれ、ID 0、1、2 のいずれかのクラスターに振り分けられます。クラスターへの振り分けは配列に格納されます。この配列のインデックスはデータのインデックスに対応し、配列の値は振り分けたクラスターの ID です。例として、デモデータのクラスタリング結果を以下に示します。

0 2 1 1 2 . . . 1

この結果は、データ項目 0 (身長 = 65.0、体重 = 220.0) がクラスター 0 に、データ項目 1 がクラスター 2 に、データ項目 2 がクラスター 1 にという具合に振り分けられたことを示しています。デモの最後にクラスター別にグループ化されたデータを表示します。ここでは非常に明確なパターンが明らかになります。中肉中背の人が 8 人、身長が低く体重も少ない人が 7 人、身長が高く、体重が普通の人が 5 人いるというパターンになっています。

今回は、少なくとも中級レベルのプログラミングスキルがあることを前提としますが、K- 平均法++ アルゴリズムの知識は問いません。デモプログラムは C# を使用してコーディングしていますが、コードを Python や JavaScript などの別の言語にリファクタリングするのもそれほど難しくはありません。デモコードは長すぎてすべて掲載することはできませんが、完全なソースコードは本稿付属のコードダウンロードから入手できます。

K- 平均法++ アルゴリズムについて

K- 平均法++ アルゴリズムは、標準の K- 平均法アルゴリズムのバリエーションなので、K- 平均法++ アルゴリズムを理解するには、まず、標準の K- 平均法を理解しなければなりません。K- 平均法アルゴリズムの歴史には興味深い点もあり、ロイドアルゴリズムと呼ばれたこともあります。K- 平均法の "K" は、クラスターの数を表します。標準の K- 平均法の最も一般的な形式を以下のように非常に大まかな擬似コードで表すと、わりとシンプルです。

pick k initial means
loop until no change
  assign each data item to closest mean
  compute new means based on new clusters
end loop

見た目のシンプルさと違って、実際の標準 K- 平均法アルゴリズムは非常に難解で、実装は驚くほど複雑になります。クラスタリングするデータが 20 個のデータ項目で構成されていて、k に 3 が指定されたとします (図 1 参照)。最初の手順では、出発点となる平均値として 3 つのデータ項目を選択します。一般的には、無作為にデータ項目を選択します。たとえば、クラスター 0 の平均として項目 2 (59.0, 110.0)、クラスター 1 の平均として項目 4 (75.0, 150.0)、クラスター 2 の平均として項目 6 (68.0, 230.0) を無作為に選択したとします。

メインの処理ループの内側で、各データ項目を調査して、データ項目の値に最も近い平均値を持つクラスターに振り分けます。つまり、データ項目 0 (65.0, 220.0) は、平均値 (68.0, 230.0) に最も近いため、クラスター 2 に振り分けます。残りの 19 個のデータ項目もそれぞれ、特定のクラスターに振り分けます。最初に平均値に採用したデータ項目は、距離が 0 になるため、当然自身が平均値である正しいクラスターに振り分けられます。

各データ項目をいずれかのクラスターに振り分けたら、各クラスターの新しい平均値を求めます。現時点ではクラスター 0 に (59.0, 110.0)、(70.0, 210.0)、(61.0, 130.0) という 3 つのデータ項目のみが振り分けられたとします。このクラスターの新しい平均値を以下のように求めます。

( (59 + 70 + 61)/3, (110 + 210 + 130)/3 ) =
(190/3, 450/3) =
(63.3, 150.0)

クラスター 1 と 2 の新しい平均値も同様に求めます。新しい平均値は、必ずしも実際のデータ項目のいずれかに該当するわけではありません。技術的には、新しい平均値は "重心" になりますが、一般的には "平均値" という用語が使用されます。

新しい平均値を求めたら、各データ項目を再度調査して、最も近い新しい平均値を持つクラスターに振り分けます。この平均値の更新とクラスターへの再振り分けのプロセスは、クラスターに振り分けられるデータ項目が変化しなくなるまで継続します。

この手順は全体として比較的シンプルですが、標準 K- 平均法アルゴリズムの実装では多くの問題が発生する可能性があります。特に、最初の平均値の選択を誤ると、データのクラスタリングが非常に不適切になり、安定するまでかなり時間が必要になることがあります。結論から言うと、最初に選択する優れた平均値は、互いの距離が離れるようにします。K- 平均法++ アルゴリズムを使用して、互いの距離が離れた平均値を最初の平均値として選択したら、標準 K- 平均法アルゴリズムを使用して、クラスタリングを行います。

K- 平均法++ の初期化メカニズム

K- 平均法++ の平均値の初期選択アルゴリズムを大まかな擬似コードにすると以下のようになります。

select one data item at random as first mean
loop k-1 times
  compute distance from each item to closest mean
  select an item that has large distance-squared
    as next initial mean
end loop

こちらの擬似コードもわりとシンプルです。K- 平均法++ の初期化メカニズムを図 2 に示します。9 つのデータポイントがあり、それぞれ 2 つの要素で構成されます。クラスターの数を 3 に設定した場合、最初の平均値として 3 つのデータ項目を選択しなければなりません。

図 2 K- 平均法++ の初期化メカニズム

図 2 は、3 つの初期平均値のうち 2 つの平均値を選択した後の、K- 平均法++ の初期化プロセスを示しています。最初の平均値の点 (3, 6) は無作為に選択したものです。この最初の平均値からの 8 つのデータ項目への平方距離を計算し、計算結果を基に、点 (4, 3) を 2 つ目の平均値として選択します (この方法については後ほど説明します)。

3 つ目の平均値となるデータ項目を選択するには、各データポイントから最も距離が近い平均値までの平方距離を計算します。この距離を破線で示しています。求めた平方距離値を使用して、平方距離値の短いデータ項目を選択する確率が低く、平方距離値の長いデータ項目を選択する確率が高くなるように、3 つ目の平均値を選択します。この手法を、比例適合度選択と呼ぶこともあります。

比例適合度選択が、K- 平均法++ の初期化メカニズムの中心部です。実装方法はいくつかあります。今回のデモプログラムでは、ルーレット方式という手法を使用します。今回使用したルーレット方式の形式を大まかな擬似コードで示すと、以下のようになります。

p = random value between 0.0 and 1.0
create an array of cumulative probabilities
loop each cell of cum prob array
  if cum[i] >= p
    return i
  end if
end loop

このルーレット方式をわかりやすく、具体的な例で考えてみます。4 つの候補項目 (0、1、2、3) があり、それに値 (20.0、10.0、40.0、30.0) が関連付けられているとします。値の合計は 20.0 + 10.0 + 40.0 + 30.0 = 100.0 になります。比例適合度選択では、項目 0 の確率値を 20.0/100.0 = 0.20、項目 1 の確率値を 10.0/100.0 = 0.10、項目 2 の確率値を 40.0/100.0 = 0.40、項目 3 の確率値を 30.0/100.0 = 0.30 とし、この確率値を使って選択を行います。

この選択の確率値を (0.20, 0.10, 0.40, 0.30) という配列として格納し、ここから累積確率値を求め、(0.20, 0.30, 0.70, 1.00) という配列として格納します。ここで、ランダム値 p が値 0.83 を持つように生成されるとします。累積確率値の配列のインデックスを i とすると、i = 0 では cum[i] = 0.20 となり、p = 0.83 以下のため、i を増やし 1 にします。i=1 では cum[i] = 0.30 となり、依然 p 以下のため、さらに i を増やし 2 にします。i=2 では cum[i] = 0.70 となり、依然 p 以下のため、さらに i を増やし 3 にします。i=3 では cum[i] = 1.00 となり、p 以上になるため、この項目を選択し i = 3 を返します。

累積確率値どうしの距離は一定ではなく、選択確率の高い項目ほど対応する項目間の差異が大きくなるのがわかります。

まとめると、K- 平均法++ アルゴリズムでは、平均値が似通らないように初期平均値を選択した後に、標準 K- 平均法アルゴリズムを使用してデータのクラスタリングを行います。初期化プロセスでは比例適合度選択を使用します。比例適合度選択は複数の方法で実装できます。今回デモプログラムでは、ルーレット方式を使用します。

プログラムの全体構造

スペースを節約するために少し編集したデモプログラムの全体構造を図 3 に示します。デモプログラムを作成するには、Visual Studio を起動して、KMeansPlus という新しい C# コンソールアプリケーションプロジェクトを作成します。このデモプログラムは、Microsoft .NET Framework との大きな依存関係がないので、比較的新しいバージョンの Visual Studio であれば動作します。

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

using System;
using System.Collections.Generic;
namespace KMeansPlus
{
  class KMeansPlusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-means++ demo");
      // All program code here
      Console.WriteLine("End k-means++ demo");
      Console.ReadLine();
    }
    public static int[] Cluster(double[][] rawData,
      int numClusters, int seed) { . . }
    public static double[][] InitMeans(int numClusters,
      double[][] data, int seed) { . . }
    private static double[][] Normalized(double[][] rawData) { . . }
    private static double[][] MakeMatrix(int rows, int cols) { . . }
    private static bool UpdateMeans(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static bool UpdateClustering(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static double Distance(double[] tuple,
      double[] mean) { . . }
    private static int MinIndex(double[] distances) { . . }
    static void ShowData(double[][] data, int decimals,
      bool indices, bool newLine) { . . }
    static void ShowVector(int[] vector, bool newLine) { . . }
    static void ShowClustered(double[][] data, int[] clustering,
      int numClusters, int decimals)
  }
} // ns

テンプレートコードがエディターに読み込まれたら、ソリューションエクスプローラーウィンドウで Program.cs ファイルを右クリックし、名前を「KMeansPlusProgram.cs」というわかりやすい名前に変更します。Program クラスの名前が Visual Studio によって自動的に変更されます。エディターのウィンドウでは、テンプレートによって生成されたコードの先頭にある、最上位レベルの System 名前空間と Collections.Generic名前空間を除くすべての名前空間参照を削除します。

Main メソッドでは、まず 20 個のデータ項目をセットアップします。

double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
...
rawData[19] = new double[] { 61.0, 130.0 };

実際のシナリオでは、おそらく、テキストファイルや SQL データベースからデータを読み取ることになります。プログラム定義の ShowData ヘルパーメソッドを使用してセットアップしたデータを表示した後、データのクラスタリングを行います。

int numClusters = 3;
int[] clustering = Cluster(rawData,   numClusters, 0);

最適なクラスター数を推測するのに使用できるテクニックはいくつかありますが、一般的には試行錯誤が必要です。Cluster メソッドは、配列の配列の形式でクラスタリング対象の数値データ、使用するクラスターの数 ("k" を使用してもかまいませんが、読みやすさを考慮して "numClusters" を使用しています)、および乱数の発生に使用するシード値を受け取ります。

Main メソッドは、クラスタリング配列と、クラスター別にグループ化されたデータ項目を表示して終了します。

ShowVector(clustering, true);
ShowClustered(rawData, clustering, numClusters, 1);

今回は OOP のアプローチではなく、静的メソッドのアプローチを使用します。Cluster メソッドは、4 つのヘルパーメソッドを呼び出します。Normalized ヘルパーメソッドはデータ項目の行列を受け取り、すべての値がほぼ同じ大きさ (通常は、-6.0 ～ +6.0) になるように正規化したデータの行列を返します。InitMeans メソッドは、K- 平均法++ の初期化メカニズムを実装します。UpdateClustering メソッドと UpdateMeans メソッドは、標準 K- 平均法アルゴリズムの中核部分を実装します。

InitMeans メソッドと UpdateClustering メソッドはどちらも、2 つのデータ項目間のユークリッド距離を返す Distance ヘルパーメソッドを呼び出します。たとえば、データの 1 つ目の組が (3.0, 9.0, 5.0) で、2 つ目の組が (2.0, 6.0, 1.0) の場合、2 つの項目間のユークリッド距離は以下のように計算します。

Sqrt( (3-2)^2 + (9-6)^2 + (5-1)^2) ) =
Sqrt( 1 + 9 + 16 ) =
Sqrt(26) = 5.1

別の距離定義を使用することもできます。一般的には、K- 平均法や K- 平均法++ を使用すると、カテゴリデータではなく、厳密な数値データのクラスタリングを行うことができます。

K- 平均法++ の実装

Cluster メソッドのコードを図 4 に示します。Cluster メソッドでは、データ項目の数値が大きな要素 (今回のデモでは体重) が、数値が小さな要素 (身長) よりも優位にならないように、まずデータ項目を正規化します。今回のデモでは、ガウス正規化を使用します。一般的には、代わりに最小最大正規化や桁正規化なども使用できます。前処理手順でデータ項目を正規化してから、正規化したデータを Cluster メソッドに直接渡すという考え方もあります。

図 4 Cluster メソッド

public static int[] Cluster(double[][] rawData,
 int numClusters, int seed)
{
  double[][] data = Normalized(rawData);
  bool changed = true;
  bool success = true;
  double[][] means = InitMeans(numClusters, data, seed);
  int[] clustering = new int[data.Length];
  int maxCount = data.Length * 10;
  int ct = 0;
  while (changed == true && success == true &&
    ct < maxCount)
  {
    changed = UpdateClustering(data, clustering, means);
    success = UpdateMeans(data, clustering, means);
    ++ct;
  }
  return clustering;
}

InitMeans メソッドは K- 平均法++ の初期化メカニズムを実装し、互いのユークリッド距離が遠く離れた平均値のセットを返します。メインのクラスタリングループの内側では、UpdateClustering メソッドがそれぞれのデータ項目を反復処理し、最も近い現在平均値/重心を持つクラスターにデータ項目を振り分けます。クラスターの振り分けに変化がない (クラスタリングが完了した) 場合、新しいクラスタリングでデータ項目が 1 つも振り分けられないクラスターが生じた (問題が発生した) 場合、UpdateClustering メソッドは false を返します。データ項目が 1 つも振り分けられないクラスターが生じた場合に例外をスローしてもかまいません。

UpdateMeans メソッドは、各クラスターに振り分けられたデータを反復し、各クラスターの新しい平均値/重心を計算します。UpdateMeans メソッドは、クラスターにデータ項目が 1 つも振り分けられていないため平均値を求められない状況が 1 つ以上生じると false を返します。

メインのクラスタリングループでは、サニティカウントチェックを使用して無限ループに陥らないようにします。一般に K- 平均法アルゴリズムはかなり迅速に安定しますが、必ず安定するわけではありません。maxCount 値には任意の値を設定できます。今回はデータ項目数の 10 倍に設定しましたが、上手く機能しました。

InitMeans メソッドの定義は以下のように始めます。

public static double[][] InitMeans(int numClusters,
  double[][] data, int seed)
{
  double[][] means = MakeMatrix(numClusters, data[0].Length);
  List<int> used = new List<int>();
...

means という配列の配列形式のローカル行列は、このメソッドから返す行列を保持します。この行列の行インデックスはクラスター ID、行列の各行は関連する平均値の要素を保持する配列です。used という List<int> は、初期平均値に割り当てたデータ項目のインデックスを保持し、初期平均値が重複しないようにしています。このアプローチでは、同じ値を持つデータ項目は存在しないと想定しています。クラスタリングを行う場合、重複するデータ項目の処理方法は、問題の具体的なシナリオによって異なります。ソースデータから重複項目を削除する方法以外に、頻度に基づいて重複項目に重みを付ける方法もあります。

次に、最初の初期平均値を選択して格納します。

Random rnd = new Random(seed);
int idx = rnd.Next(0, data.Length);
Array.Copy(data[idx], means[0], data[idx].Length);
used.Add(idx);

最初の初期平均値は、すべてのデータ項目からランダムに選択します。初期平均値は既存のデータ項目になり、このデータ項目をメドイド (medoid) と呼ぶこともあります。

次に、for ループを作成して、残りの k-1 平均値を選択します。

for (int k = 1; k < numClusters; ++k)
{
  double[] dSquared = new double[data.Length];
  int newMean = -1;
...

dSquared 配列は、各データ項目と最も近い既存の初期平均値間の平方距離を保持します。newMean 変数は、次の初期平均値となるデータ項目のインデックスを保持します。続いて、それぞれの (正規化した) データ項目を調べ、dSquared 値を計算して格納します。

for (int i = 0; i < data.Length; ++i)
{
  if (used.Contains(i) == true) continue;
  double[] distances = new double[k];
  for (int j = 0; j < k; ++j)
    distances[j] = Distance(data[i], means[k]);
  int m = MinIndex(distances);
  dSquared[i] = distances[m] * distances[m];
}

あるデータ項目を既に初期平均値に使用したかどうかを判断するチェックは実際には必要ありません。データ項目を既に使用している場合、最も近い平均値への平方距離は自身への距離 (0) となるためです。distances という配列は、現在のデータ項目から今まで選択した既存の各 K- 初期平均値へのユークリッド距離を保持します。

Distance メソッドのユークリッド距離は、データ項目の要素どうしの差の 2 乗を合計した値の平方根として求めます。K- 平均法++ では平方距離を使用するため、InitMeans の平方演算は、Distance の平方根演算を相殺します。したがって、平方距離を直接返すメソッドを定義して、コードを簡素化することができます。

次に、ルーレット方式用の累積確率値をスキャンするループを準備します。

double p = rnd.NextDouble();
double sum = 0.0;
for (int i = 0; i < dSquared.Length; ++i)
  sum += dSquared[i];
double cumulative = 0.0;
int ii = 0;
int sanity = 0;

比例適合度選択のところで説明したように、0.0 ～ 1.0 のランダム値を生成して、平方距離の合計を計算します。累積確率値の配列を明示的に作成するのではなく、実行時に現在の累積確率値を生成する方が効率的です。

各累積確率値は、ルーレット方式を実装する while ループで計算およびテストします。

while (sanity < data.Length * 2)
{
  cumulative += dSquared[ii] / sum;
  if (cumulative >= p && used.Contains(ii) == false)
  {
    newMean = ii; // the chosen index
    used.Add(newMean); // don't pick again
    break;
  }
  ++ii; // next candidate
  if (ii >= dSquared.Length) ii = 0; // past the end
  ++sanity;
}

while ループは、累積確率値がランダムな p 値以上になるまで継続します。ただし、初期平均値の重複は許可されないため、選択した平均値が "used" List<int> に存在する場合、次に利用可能なデータ項目を選択します。ii インデックスはデータの最後に達したら 0 にリセットします。特定のデータ項目が既に初期平均値に選択されている場合、次に利用可能なデータ項目が次に最も可能性のある項目にはなるとは限りません。

InitMeans メソッドは、選択した初期平均値を保存して終了し、選択した平均値の配列を返します。

...
    Array.Copy(data[newMean], means[k], data[newMean].Length);
  } // k, each remaining mean
  return means;
} // InitMean

InitMeans メソッドの目的は、初期平均値に使用する k 個の異なるデータ項目を見つけることです。ルーレット方式の選択は、選択した平均値の相互の差異が最大になることを保証するものではなく、ごくわずかですが、相互の差異が近くなることがあります。そのため、InitMeans メソッドのリファクタリングを行って、ルーレット方式の選択を複数回使用して候補となる平均値のセットを生成後に、相互の差異が最も大きくなる平均値のセットを返してもかまいません。

まとめ

今回は、D. Arthur と S. Vassilvitskii による 2007 年の研究論文「K-Means++: The Advantages of Careful Seeding」(K- 平均法++: シード値を慎重に選択する利点、英語) に基づいています。一般的な研究論文によくあることですが、実装の詳細が記載されることはめったにありません。ただし、この研究論文では、K- 平均法++ の初期化のしくみと、その動作の理論的境界の確立方法が丁寧に説明されています。

Dr. James McCaffrey は、ワシントン州レドモンドにある Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。McCaffrey 博士の連絡先は、jammc@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれたマイクロソフト技術スタッフの Kirk Olynyk (Microsoft Research) に心より感謝いたします。

次の方法で共有

テストの実行 - K- 平均法++ データクラスタリング

K- 平均法++ アルゴリズムについて

K- 平均法++ の初期化メカニズム

プログラムの全体構造

K- 平均法++ の実装

まとめ

その他のリソース

次の方法で共有

テストの実行 - K- 平均法++ データ クラスタリング

K- 平均法++ アルゴリズムについて

K- 平均法++ の初期化メカニズム

プログラムの全体構造

K- 平均法++ の実装

まとめ

その他のリソース

テストの実行 - K- 平均法++ データクラスタリング