テストの実行

[アーティクル]
07/30/2015

数値データをカテゴリデータに変換する

James McCaffrey 機械学習分野の基本タスクは、数値データをカテゴリデータに変換することです。たとえば、59.5、64.0、および 75.5 というインチ単位の身長のデータセットがある場合に、この数値データを低、中、高を表す 0、1、2 などのカテゴリデータに変換することが考えられます。この処理はビニングデータという通称で呼ばれることがあり、機械学習に関する文献では通常、連続データの離散化と呼ばれます。

データの離散化が必要になるシナリオは多数あります。単純ベイズの分類や予測など、多くの機械学習アルゴリズムはカテゴリデータのみを処理対象としています。したがって、未加工のデータが数値の場合に単純ベイズを適用するときは、データを離散化する必要があります。また、Excel スプレッドシートでよく見られるデータのように、数値データとカテゴリデータが混ざっている場合もあります。混合データを処理する機械学習アルゴリズムはほとんどないため、数値データをカテゴリデータに変換して、カテゴリデータを処理する機械学習アルゴリズムを使用する必要があります。カテゴリユーティリティを利用したデータクラスタリングは、その一例です。

このトピックがあまり魅力的でないためか、離散化アルゴリズムの実装方法を説明する資料はほとんど公開されていません。このコラムでは、強力な離散化アルゴリズムを紹介します。アイデア自体はそれほど新しいものではありませんが、私が知っている限り、このコラムで紹介する実装はこれまで公開されたことがありません。

このコラムの目的を理解する一番の方法は、図 1 のデモプログラムを調べることです。デモでは、まずインチ単位の身長を表す 20 個のデータ要素を作成します。未加工のデータを図 2 のヒストグラムに示します。続いて、データを分析して Discretizer オブジェクトを作成し、Discretizer オブジェクトの内部表現を表示します。Discretizer オブジェクトは、未加工データの個別の値のコピーを (小さい順に) 並べ替えて、data という名前の配列に保持します。カテゴリ数は 3 と算出済みで、メンバー変数 k に格納されています。

Converting Numeric Data to Categorical Data
図 1 数値データからカテゴリデータへの変換

The Raw Data to Categorize
図 2 カテゴリ化対象の未加工のデータ

各データ要素は、3 つのカテゴリのうちいずれかに割り当て済みです。各カテゴリを 0 から始まる整数 (0 ～ 2) にエンコードし、割り当て情報を clustering という名前の配列に格納しています。最初の 3 つのデータ要素 (60.0、61.0、62.0) をカテゴリ 0 に割り当て、次の 4 つのデータ要素 (66.0、67.0、68.0、69.0) をカテゴリ 1 に割り当てて、最後の 4 つのデータ要素 (73.0、74.0、76.0、78.0) をカテゴリ 2 に割り当てています。カテゴリ 0 の最初の 3 つのデータ要素の算術平均は 61.00 になり、カテゴリ 1 とカテゴリ 2 ではそれぞれ 67.50 と 75.25 になります。

Discretizer オブジェクトを作成したら、デモプログラムでは 3 つの既存のデータ値 (62.0、66.0、73.0) と 3 つの新しいデータ値 (59.5、75.5、80.5) を作成します。ここで重要なのは、固定データセットを利用できる場合もあれば、新しいデータを動的に生成したために変換が必要になる場合もあることです。Discretizer オブジェクトでは、6 つの数値データ要素すべてをカテゴリデータ (それぞれ 0、1、2 と 0、2、2) に変換します。

今回は、中級以上のプログラミングスキルがあることを前提にしています。離散化アルゴリズムは C# で記述しましたが、Python や Visual Basic など、他の言語へのリファクタリングもそれほど難しくないでしょう。コードのサイズを小さくして中心となるアイデアを明確にするために、通常のエラーチェックの大半を省略しています。デモコードは非常に長いのですべてをこのコラム内に掲載することはできませんが、archive.msdn.microsoft.com/mag201308TestRun (英語) で完全なソースコードを入手できます。

見かけほど簡単ではない

一見すると、数値データからカテゴリデータへの変換は簡単そうに思えます。単純な手法の 1 つとしては、未加工のソースデータを等間隔に分割することが挙げられます。たとえば、デモや図 2 のデータの場合、データの分布範囲は 78.0 - 60.0 = 18.0 インチです。これを k = 3 の間隔で分けると、間隔の幅は 6.0 インチになります。したがって、60.0 ～ 66.0 のデータがカテゴリ 0 に、66.0 ～ 72.0 のデータがカテゴリ 1 に、72.0 ～ 78.0 のデータがカテゴリ 2 に割り当てられます。この等間隔手法の問題点は、データの自然な区切りが無視されることです。図 2 をご覧になれば、優れた離散化アルゴリズムなら 66.0 ではなく 63.0 ～ 65.0 のどこかで区切る必要があることがわかります。

2 つ目の単純な手法は、等頻度を使用して離散化することです。サンプルデータの場合、データ要素が 11 個あり、k = 3 のカテゴリを使用すると (小数部を切り捨てる整数除算により) 11 / 3 = 3 となるので、最初の 3 つのデータ要素をカテゴリ 0 に、次の 3 つのデータ要素をカテゴリ 1 に、最後の 5 つのデータ要素をカテゴリ 2 に割り当てることができます。しかし、等頻度手法でも、データの自然な区切りが無視されます。

このコラムで説明する離散化アルゴリズムでは、データクラスタリング手法を使用しています。K- 平均法 (K-Means) アルゴリズム (データの自然な区切りを考慮したアルゴリズム) を使用して未加工のデータをクラスタリングし、クラスタリングアルゴリズムから生成された平均を使用して新しいデータをカテゴリに割り当てます。たとえば、図 1 の場合、3 つの平均は 61.00、67.50、および 75.25 です。62.5 という数値をカテゴリ値に関連付けるには、Discretizer オブジェクトで 3 つの平均値のうち 62.5 に最も近い値 (61.0) を判定し、61.0 に関連付けられているクラスター値 (0) を 62.5 のカテゴリ値として割り当てます。

K- 平均法クラスタリング

K- 平均法クラスタリングアルゴリズムはかなりシンプルです。このアルゴリズムにはさまざまなバリエーションがあります。最も基本的な形式の場合、特定のデータ要素のセットと特定のクラスター数 k について、初期化プロセスではランダムに選択したクラスターに各データ要素を割り当てます。さらに、各クラスターのデータ要素の平均を計算します。続いて、各データ要素をスキャンして、そのデータ要素に最も近い平均値のクラスターに再割り当てします。データ要素を新しいクラスターに再割り当てする必要がなくなるまで、平均の計算とクラスターへの再割り当ての処理を繰り返します。

プログラムの全体構造

図 1 で示したデモプログラムは、スタンドアロンのコンソールアプリケーションです。今回は Visual Studio 2012 を使用しましたが、このデモには大きな依存関係がないので、Microsoft .NET Framework 2.0 以上を使用するあらゆるバージョンの Visual Studio で動作します。最初に、新しい C# コンソールアプリケーションを作成して BinningData という名前を付けました。テンプレートコードが読み込まれたら、ソリューションエクスプローラーで Program.cs ファイルの名前を BinningProgram.cs というわかりやすい名前に変更しました。このプログラムのクラス名は Visual Studio によって自動的に変更されます。ソースコードの冒頭で、System と Collections.Generic を除くすべての名前空間の参照を削除しました。

いくつか小さな変更を加えたプログラムの全体構造を図 3 に示します。主な呼び出しステートメントをまとめると、以下のようになります。

double[] rawData = new int[] { 66.0, 66.0, ... };
Discretizer d = new Discretizer(rawData);
double numericVal = 75.5;
int catVal = d.Discretize(numericVal);

図 3 デモプログラムの構造

using System;
using System.Collections.Generic;
namespace BinningData
{
  class BinningProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin discretization of continuous data demo\n");
        double[] rawData = new double[20] {
          66, 66, 66, 67, 67, 67, 67, 68, 68, 69,
          73, 73, 73, 74, 76, 78,
          60, 61, 62, 62 };
        Console.WriteLine("Raw data:");
        ShowVector(rawData, 2, 10);
        Console.WriteLine("\nCreating a discretizer on the raw data");
        Discretizer d = new Discretizer(rawData);
        Console.WriteLine("\nDiscretizer creation complete");
        Console.WriteLine("\nDisplaying internal structure of the discretizer:\n");
        Console.WriteLine(d.ToString());
        Console.WriteLine("\nGenerating three existing and three new data values");
        double[] newData = new double[6] { 62.0, 66.0, 73.0, 59.5, 75.5, 80.5 };
        Console.WriteLine("\nData values:");
        ShowVector(newData, 2, 10);
        Console.WriteLine("\nDiscretizing the data:\n");
        for (int i = 0; i < newData.Length; ++i)
        {
          int cat = d.Discretize(newData[i]);
          Console.WriteLine(newData[i].ToString("F2") + " -> " + cat);
        }
        Console.WriteLine("\n\nEnd discretization demo");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    } // Main
    public static void ShowVector(double[] vector, int decimals,
      int itemsPerRow) { . . }
  } // Program
  public class Discretizer
  {
    public Discretizer(double[] rawData) { . . }
    private static double[] GetDistinctValues(double[] array) { . . }
    private static bool AreEqual(double x1, double x2) { . . }
    public int Discretize(double x) { . . }
    public override string ToString() { . . }
    private void InitializeClustering() { . . }
    private int[] GetInitialIndexes() { . . }
    private int InitialCluster(int di, int[] initialIndexes) { . . }
    private void Cluster() { . . }
    private bool ComputeMeans() { . . }
    private bool AssignAll() { . . }
    private int MinIndex(double[] distances) { . . }
    private static double Distance(double x1, double x2) { . . }
  }
} // ns

Discretizer クラス

Discretizer クラスには、以下の 4 つのデータメンバーがあります。

private double[] data;
private int k;
private double[] means;
private int[] clustering;

Discretizer コンストラクターでは数値データを使用して Discretize メソッドを使用可能にし、このメソッドで数値を受け取って 0 から始まる整数のカテゴリ値を返します。Discretizer コンストラクターでは自動的にカテゴリ数を特定していることに注意してください。

data 配列には未加工のデータから抽出した個別の値を格納し、clustering の作成に使用します。整数値 k はデータの割り当て先クラスター数であり、データカテゴリ数でもあります。means という名前の配列はサイズが k で、クラスタリングアルゴリズム実行中の特定の時点で各クラスターに割り当てられているデータ要素の算術平均を格納します。

clustering という名前の配列は、特定の時点でのデータのクラスタリング状態をエンコードします。clustering 配列のインデックスは data 配列に格納しているデータ要素のインデックスを示し、clustering 配列の値は現在のクラスター割り当てを示しています。たとえば、clustering[9] = 2 の場合、data[9] のデータ要素にはクラスター 2 が割り当てられています。

Discretizer コンストラクター

Discretizer コンストラクターの定義は以下のとおりです。

public Discretizer(double[] rawData)
{
  double[] sortedRawData = new double[rawData.Length];
  Array.Copy(rawData, sortedRawData, rawData.Length);
  Array.Sort(sortedRawData);
  this.data = GetDistinctValues(sortedRawData);
  this.clustering = new int[data.Length];
  this.k = (int)Math.Sqrt(data.Length); // heuristic
  this.means = new double[k];
  this.Cluster();
}

最初の段階では、未加工のデータから個別の値を抽出します。これを実行する方法はいくつかありますが、今回のコードでは、未加工のデータを並べ替えてから、GetDistinctValues というヘルパーメソッドを呼び出します。個別のデータを特定すれば、clustering 配列を割り当てられます。

GetDistinctValues メソッドの内容を以下に示します。

private static double[] GetDistinctValues(double[] array)
{
  List<double> distinctList = new List<double>();
  distinctList.Add(array[0]);
  for (int i = 0; i < array.Length - 1; ++i)
    if (AreEqual(array[i], array[i + 1]) == false)
      distinctList.Add(array[i+1]);
  double[] result = new double[distinctList.Count];
  distinctList.CopyTo(result);
  return result;
}

ソースデータを並べ替え済みなので、このメソッドでは、1 回スキャンするだけで、連続する 2 つの値が等しくないデータ要素を検出できます。未加工のデータは double 型なので、完全に等しいかどうかを基準に 2 つの値を比較しても目的どおりの結果を得られない可能性があります。そのため、AreEqual というヘルパーメソッドを使用します。

private static bool AreEqual(double x1, double x2)
{
  if (Math.Abs(x1 - x2) < 0.000001) return true;
  else return false;
}

AreEqual メソッドでは、任意の 0.000001 という精度のしきい値を使用します。この値は Discretizer オブジェクトに入力パラメーターとして渡してもよいでしょう。そのようなシナリオでは、epsilon という名前の変数を使用することがよくあります。

未加工のデータから個別の値を抽出したら、次の段階では、クラスター数でもカテゴリ数でもある k を決定します。ここでは、おおまかな方法を使用して、k をデータ項目数の平方根としています。k の値をパラメーターとして渡せるように Discretizer コンストラクターを作成する方法もあります。最適な k の値を特定することは、本質的に、機械学習の調査に関する未解決の課題です。

k の値を計算したら、Discretizer コンストラクターでは means 配列の領域を割り当てて、Cluster メソッドを呼び出します。Cluster メソッドでデータに対して K- 平均法クラスタリングを実行すると、最終的な means 配列の値を使用して、あらゆる数値にカテゴリ値を割り当てます。

クラスタリングアルゴリズム

Discretizer クラスの核心は、K- 平均法クラスタリングを実行するコードです。Cluster メソッドを図 4 に示します。

図 4 Cluster メソッド

private void Cluster()
{
  InitializeClustering();
  ComputeMeans();
  bool changed = true; bool success = true;
  int ct = 0;
  int maxCt = data.Length * 10; // Heuristic
  while (changed == true && success == true && ct < maxCt) {
    ++ct;
    changed = AssignAll();
    success = ComputeMeans();
  }
}

Cluster メソッドは、難しい処理をヘルパーメソッドに別途実装しているため、比較的短くなっています。まず、InitializeClustering メソッドで、すべてのデータ要素を初期クラスターに割り当てます。次に、各クラスターに割り当てたデータ要素の平均を、クラスタリングの割り当てを使用して計算します。

メインのクラスタリングアルゴリズムのループ内では、AssignAll メソッドを使用して、すべてのデータ要素をクラスターに割り当てます。AssignAll メソッドは、Distance と MinIndex というヘルパーメソッドを呼び出します。このうち Distance メソッドでは 2 つのデータ要素間の距離を定義します。

private static double Distance(double x1, double x2)
{
  return Math.Sqrt((x1 - x2) * (x1 - x2));
}

このコードでは、(差の 2 乗に対する平方根として定義されている) ユークリッド距離を使用します。データ要素がベクトルではなく個々の値なので、ユークリッド距離は Math.Abs(x1 - x2) と等しくなります。そのため、このシンプルな計算を使用することをお勧めします。

このループが終了するのは、AssignAll の戻り値が示す clustering 配列に変化がないとき、クラスターに割り当てられている値がないために means 配列を計算できないとき、またはループカウンターの最大値に達したときです。ここでの最大値 (maxCt) は、任意に割り当てたデータ要素数を 10 倍した値です。一般的に、ここで説明するクラスタリングアルゴリズムはごく短時間で収束し、maxCt に達するというループ終了条件が成立する場合は論理エラーが発生している可能性が高いため、これを確認することをお勧めします。

クラスタリングプロセスでは、クラスターに値を繰り返し再割り当てするため、クラスターに割り当てられている値の数が 0 になり、平均を計算できなくなることがあります。ComputeMeans ヘルパーメソッドではすべての K- 平均を計算しようとしますが、値数が 0 の場合は false を返します。このメソッドについては、図 5 を参照してください。

図 5 ComputeMeans メソッド

private bool ComputeMeans()
{
  double[] sums = new double[k];
  int[] counts = new int[k];
  for (int i = 0; i < data.Length; ++i)
  {
    int c = clustering[i]; // Cluster ID
    sums[c] += data[i];
    counts[c]++;
  }
  for (int c = 0; c < sums.Length; ++c)
  {
    if (counts[c] == 0)
      return false; // fail
    else
      sums[c] = sums[c] / counts[c];
  }
  sums.CopyTo(this.means, 0);
  return true; // Success
}

クラスタリングを初期化する

クラスタリングの初期化プロセスはやや複雑です。データが図 1 のように 11 個の並べ替え済みの値で構成され、クラスター数 k が 3 に設定されているとします。初期化後の目標は、配列メンバーのクラスタリングで、セル 0 ～ 2 の 3 セルに 0、セル 3 ～ 5 の 3 セルに 1、セル 6 ～ 10 の残り 5 セルに 2 を設定することです。

最初の段階では、0 ～ 2、3 ～ 5、および 6 以上という間隔を暗黙に定義する境界値 {3, 6, 9} を生成します。これは、クラスター数単位でデータ要素を分割する以下のような GetInitialIndexes ヘルパーメソッドで実行します。

private int[] GetInitialIndexes()
{
  int interval = data.Length / k;
  int[] result = new int[k];
  for (int i = 0; i < k; ++i)
    result[i] = interval * (i + 1);
  return result;
}

次の段階では、境界値を使用して特定のデータインデックス値に対するクラスター値を計算する、以下のようなヘルパーメソッドを定義します。

private int InitialCluster(int di, int[] initialIndexes)
{
  for (int i = 0; i < initialIndexes.Length; ++i)
    if (di < initialIndexes[i])
      return i;
  return initialIndexes.Length - 1; // Last cluster
}

最後の段階では、すべてのデータインデックスをクラスターに割り当てます。

private void InitializeClustering()
{
  int[] initialIndexes = GetInitialIndexes();
  for (int di = 0; di < data.Length; ++di)
  {
    int c = InitialCluster(di, initialIndexes);
    clustering[di] = c;
  }
}

初期化プロセスの本質は、このコラムの前半で説明した等頻度手法です。

Discretize メソッド

データをクラスタリングしたら、means 配列の最終的な値を使用して、0 から始まるカテゴリ値を数値に割り当てることができます。Discretize メソッドは以下のとおりです。

public int Discretize(double x)
{
  double[] distances = new double[k];
  for (int c = 0; c < k; ++c)
    distances[c] = Distance(x, data[means[c]]);
  return MinIndex(distances);
}

Discretize メソッドは入力値 x から各 K- 平均までの距離を計算して、最も近い平均のインデックスを返し、これがクラスター ID 兼カテゴリ値となります。たとえば、最終的な平均が 61.00、67.50、および 75.25 で、x が 70.00 の場合、x から平均までの距離はそれぞれ、mean[0] = sqrt((70.00 - 61.00)^2) = sqrt(81.00) = 9.00、mean[1] = sqrt((70.00 - 67.50)^2) = 2.50、および mean[2] = sqrt((70.00 - 75.25)^2) = 5.25 となります。最短距離はインデックス [1] の 2.50 なので、70.00 をカテゴリ値 1 に割り当てます。

まとめ

このコラムで説明したコードをそのまま使用して、数値データからカテゴリデータへの機械学習向けの高品質な変換を利用できます。Discretizer クラスをアプリケーションに直接実装する代わりに、クラスライブラリにカプセル化することもできます。

最もカスタマイズをお勧めする機能は、カテゴリ数 k の特定機能です。たとえば、しきい値を設定してもよいでしょう。しきい値を下回った場合に、各データ要素からカテゴリ値を生成します。たとえば、年齢を扱っていて、その年齢が 1 から 120 までの範囲に分布しているとします。k を 120 の平方根として計算する (その結果 10 個のカテゴリを生成する) 代わりに、120 個の個別の値候補を利用するだけで、k を 120 に等しくできます。

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

この記事のレビューに協力してくれた技術スタッフの Richard Hughes (Microsoft Research) に心より感謝いたします。