テストの実行

C# を使用したコンセンサス分類

James McCaffrey

コード サンプルのダウンロード

機械学習 (ML) の分類とは、数値以外の離散値を受け取り予測モデルを作成するプロセスです。この場合の予測モデルは、通常、なんらかの数学方程式またはルールの集合です。たとえば、議員の所属政党 (民主党または共和党) を、これまでの投票歴を基に予測することなどが考えられます。モデルのトレーニングとは、値がわかっている出力従属変数値をトレーニング データとして受け取り、そのデータを計算した結果が、これも答えがわかっている出力値になるべく正確に一致するような定数の集合 (数学方程式モデルの場合) またはルールの集合 (ルール ベースのモデルの場合)を見つけるプロセスです。その後、トレーニングを終えたモデルを使用して、結果がわかっていない新しいデータの結果を予測します。

標準の分類アルゴリズムや分類手法は、単純ベイズ分類、ロジスティック回帰分類、ニューラル ネットワーク分類など数多くありますが、問題によっては独自に作成した分類アルゴリズムも効果があります。今回は、私が独自に作成した「コンセンサス分類」と呼んでいる手法 (あまりよい名前を思いつきませんでした) を紹介します。いつものように、コンセンサス分類の雰囲気を感じ、今回の目標を確認するには、図 1 のデモ プログラムを見るのが一番です。

図 1 コンセンサス分類の動作

このデモ プログラムの目的は、16 個の法案に対する米国議会下院議員のこれまでの投票を基に、議員の政党 (民主党または共和党) を予測するモデルを作成することです。データそのものは 100 項目から構成されます。それぞれの項目が各議員を表し、17 個のフィールドがあります。項目の先頭から 16 個のフィールドはその議員の投票歴です。文字 "y" は賛成票、"n" は反対票を意味します。項目の最終フィールドは、その議員の実際の所属政党です。例として、先頭の 2 つのデータ項目を以下に示します。

n, y, y, n, y, y, n, n, n, n, n, n, y, y, y, y, democrat
n, y, n, y, y, y, n, n, n, n, n, y, y, y, n, y, republican

デモ データは、「Congressional Voting Records Data Set」と呼ばれる有名なベンチマーク セットのサブセットです。ベンチマーク データ セットには全部で 435 項目あり、不明票または棄権票を表す "?" も含まれています。デモで使うサブセットは、ベンチマーク データ セットの先頭から "?" 投票を含まない項目を 100 項目取り出して構成したものです。また、原典のデータ セットでは 1 フィールド目が政党になっていますが、プログラミングするときに便利なので最終フィールドに移動しています。

16 個の投票が何の法案に投じたものかは知らなくてもかまいませんが、各法案の主旨はそれぞれの短縮名から推測できるでしょう。16 個の法案の短縮名は、handicapped-infants (障碍者)、water-project (水道事業)、adopt-budget (予算可決)、physician-fees (診療報酬)、el-salvador (エルサルバドル)、school-religion (学校宗教)、anti-satellite (対人工衛星)、nicaraguan-contras (ニカラグア反革命軍)、mx-missile (MX ミサイル)、immigration-bill (移民法案)、synfuels-cutback (合成燃料削減)、education-spending (教育費)、superfund-sue (スーパーファンド訴訟)、crime-bill (犯罪法案)、duty-free (免税)、および south-africa (南アフリカ) でした。

デモ プログラムは、データ セット 100 項目を、モデルのトレーニングに使用する 80 項目と、出力したモデルの正確性評価に使用する 20 項目に分割します。今回のコンセンサス分類のモデルは簡単なルールの集合で構成します。たとえば、「議員が法案 0 に "y"、法案 3 に "y"、法案 15 に "y" と投票した場合、その議員は共和党である」といったルールです。デモでは、簡単な各ルールのブール条件数を 5 に設定し、ルールの総数を 500 に設定しています。また、各ルールには、そのルールを当てはめるトレーニング データ項目に対して 90% 以上の正確性が求められます。

デモのトレーニング プロセスでは、500 個の簡単なルールが生成されました。モデル生成後、モデルのルールをトレーニング データに当てはめたところ、デモ プログラムでは 93.75% の正確性が得られました。次に、モデルを 20 個のテスト セットに当てはめたところ、84.21% の正確性 (正確に予測したのが 16 個、不正確だったのが 3 個、モデルの 500 個のルールがどれも当てはまらなかったのが 1 個) になりました。

今回は、中級レベルのプログラミング スキルと ML 分類に関する基本知識を有することを前提とします。このデモは C# を使用してコーディングしていますが、コードを Visual Basic .NET や Python などの別の言語にリファクタリングしても大きな問題は起きません。デモ コードは長すぎてコラムにすべて掲載することはできませんが、完全なソース コードは、このコラム付属のコード ダウンロード (msdn.microsoft.com/magazine/msdnmag1114) から入手できます。

プログラムの全体構造

デモ プログラムの全体構造を 図 2 に示します。スペースを節約するために WriteLine ステートメントをいくつか削除し、少し編集しています。デモを作成するには、Visual Studio を起動し、新しい C# コンソール アプリケーションを作成して、「ConsensusClassification」という名前を付けます。デモは、Microsoft .NET Framework との大きな依存関係がないので、比較的新しいバージョンの Visual Studio であれば動作します。テンプレートによって生成されたコードが読み込まれたら、ソリューション エクスプローラー ウィンドウで Program.cs ファイルの名前を ConsensusProgram.cs という名前に変更します。この変更により、Program クラスの名前が Visual Studio によって自動的に変更されます。

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

using System;
using System.Collections.Generic;
namespace ConsensusClassification
{
  class ConsensusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin consensus classification demo");
      Console.WriteLine("Goal is predict political party");
      string[][] allData = new string[100][];
      allData[0] = new string[] { "n", "y", "y", "n", "y", "y", "n", "n",
        "n", "n", "n", "n", "y", "y", "y", "y", "democrat" };
      allData[1] = new string[] { "n", "y", "n", "y", "y", "y", "n", "n",
        "n", "n", "n", "y", "y", "y", "n", "y", "republican" };
      // Etc.
      allData[99] = new string[] { "y", "n", "y", "n", "n", "y", "y", "y",
        "y", "y", "y", "n", "n", "n", "y", "y", "democrat" };
      Console.WriteLine("All data: ");
      ShowData(allData, 5, true);
      Console.WriteLine("Creating 80-20 train-test data");
      string[][] trainData;
      string[][] testData;
      MakeTrainTest(allData, 0, out trainData, out testData); // 0 = seed
      Console.WriteLine("Training data: \n");
      ShowData(trainData, 3, true);
      Console.WriteLine("Test data: \n");
      ShowData(testData, 3, true);
      int numConditions = 5; // Conditions per rule
      int maxNumRules = 500;
      double minAccuracy = 0.90; // Min % rule accuracy
      Console.WriteLine("Setting number conditions per rule = " + 
        numConditions);
      Console.WriteLine("Setting max number simple rules    = " + 
        maxNumRules);
      Console.WriteLine("Setting simple rule min accuracy   = " +
        minAccuracy.ToString("F2"));
      ConsensusClassifier cc =
        new ConsensusClassifier(numConditions, maxNumRules);
      Console.WriteLine("Starting training");
      cc.Train(trainData, minAccuracy);
      Console.WriteLine("Done");
      Console.WriteLine("Created " + cc.RuleCount() + " simple rules");
      double trainAcc = cc.Accuracy(trainData);
      Console.WriteLine("Accuracy on train data = " + 
        trainAcc.ToString("F4"));
      int numCorrect, numWrong, numUnknown;
      double testAcc = cc.Accuracy(testData, out numCorrect,
        out numWrong, out numUnknown);
      Console.WriteLine("Accuracy on test data  = " + 
        testAcc.ToString("F4"));
      Console.WriteLine("Number correct = " + numCorrect);
      Console.WriteLine("Number wrong   = " + numWrong);
      Console.WriteLine("Number unknown = " + numUnknown);
      Console.WriteLine("End consensus classification demo\n");
      Console.ReadLine();
    }
    static void MakeTrainTest(string[][] allData, int seed,
      out string[][] trainData, out string[][] testData) { . . }
    static void ShowData(string[][] rawData, int numRows,
      bool indices) { . . }
  } // Program
  public class ConsensusClassifier { . . }
} // ns

すべてのプログラム ロジックは、Main メソッドに含まれています。デモには、MakeTrainTest と ShowData という 2 つの静的ヘルパー メソッドがあります。分類のロジックは、ConsensusClassifier という 1 つのプログラム定義のクラスに含めています。このクラスでは、1 つのコンストラクター、RuleCount (モデル内の簡単なルールの実際の数)、ComputeOutput (モデル作成後の予測を行う)、Train (モデルを作成する)、オーバーロードされる Accuracy (予測の確度を計算する) の 6 つのパブリック メソッドを公開します。

このデモ プログラムでは、Main メソッドで 100 項目のソース データを配列の配列形式の文字列行列でハード コーディングしています。

string[][] allData = new string[100][];
allData[0] = new string[] { "n", "y", "y", "n", "y", "y", "n", "n",
  "n", "n", "n", "n", "y", "y", "y", "y", "democrat" };
...

デモではない実際のシナリオでは、データをテキスト ファイルに含め、ヘルパー メソッドを使ってデータを読み込むようにします。ソース データは、以下のようにトレーニング セットとテスト セットに分割します。

string[][] trainData;
string[][] testData;
MakeTrainTest(allData, 0, out trainData, out testData);

80 対 20 の分割の比率もハードコーディングしています。MakeTrainTest メソッドに渡している 0 という引数値は Math.Random オブジェクト用のシード値で、データ項目をトレーニング セットとテスト セットにランダムに割り当てるために使用します。他にも、トレーニング行列とテスト行列に含まれる民主党と共和党のデータ項目の比率が、ソース データ全体の比率とおおよそ同じになるように、階層化アプローチを使用する方法があります。

デモでは、以下のコードを使用してモデルを作成します。

int numConditions = 5;
int maxNumRules = 500;
double minAccuracy = 0.90;
ConsensusClassifier cc = 
  new ConsensusClassifier(numConditions, maxNumRules);
cc.Train(trainData, minAccuracy);

ここでは、各ルールのブール条件数と作成するルールの最大数をコンストラクターに渡し、トレーニング データへの参照と各ルールが満たす必要のある最低限の正確性を Train メソッドに渡しています。多くの開発者は、関係のあるすべてのパラメーターをコンストラクターに渡すことを好みます (多くのパラメーターを受け取るコンストラクターになる)。ここでは、各メソッドに最も直接関係のある値だけを渡しています (かなり気まぐれに見える呼び出しインターフェイスになる)。

このデモ プログラムは、モデルの正確性を計算し、それを表示して終わります。

double trainAcc = cc.Accuracy(trainData);
Console.WriteLine("Accuracy on train data = " + trainAcc.ToString("F4"));
int numCorrect, numWrong, numUnknown;
double testAcc = cc.Accuracy(testData, out numCorrect, out numWrong,
  out numUnknown);
Console.WriteLine("Accuracy on test data  = " + testAcc.ToString("F4"));
Console.WriteLine("Number correct = " + numCorrect);
Console.WriteLine("Number wrong   = " + numWrong);
Console.WriteLine("Number unknown = " + numUnknown);

Accuracy メソッドの最初のオーバーロードは、分類の正確性だけを返します。Accuracy メソッドの 2 つ目のオーバーロードは、分類の正確性に加えて、正確に一致した数、一致しなかった数、モデルのルールがいずれも当てはまらなかったデータ項目の数を返します。たとえば、条件数のパラメーターが 3 で、特定のデータ項目が vote0 = 'y'、vote1 = 'y'、vote2 = 'n' を保持しているとします。500 個のルールがあるとしても、この投票の組み合わせに当てはまるルールがなくても不思議ではありません。Accuracy メソッドは、なるべく当てはまらないデータ項目が出現しなくなるように設計します。そのためによく使われるのは、最後のルールに「これらの条件に当てはまらないのは民主党」のようにして、既定値を民主党にする方法です。既定値とは、通常、最も共通する従属変数値のことです。

このデモ プログラムは、議員の所属政党の予測にモデルを使用しません。法案 [0] から法案 [7] まで "賛成" と投票し、法案 [8] から法案 [15] まで "反対" と投票した議員の所属政党を予測するコードは次のようになります。

string[] newData = new string[] { "y", "y", "y", "y", "y", "y", "y", "y",
  "n", "n", "n", "n", "n", "n", "n", "n" };
int party = cc.ComputeOutput(newData);
Console.WriteLine("Predicted party = " + party);

ComputeOutput メソッドは、共和党を表す 0 または民主党を表す 1 のいずれかの整数値を返します。

コンセンサス アルゴリズム

コンセンサス分類で重要なのはルールの集合です。主なテーマは、ルールの表現方法とルールの生成方法を決めることです。デモ プログラムでは、ルールを整数の配列で表現します。このしくみを具体的な例で考えてみましょう (図 3 参照)。各ルールのブール条件数は 3 個に設定しているとします。1 つのルールは 7 つのセルから成る配列で表現します。配列の値が { 3, 0, 8, 1, 15, 1, 0 } の場合、このルールは「投票 [3] が 0、投票 [8] が 1、投票 [15] が 1 の場合、政党は 0」を表します。ルールの集合は、ルールのジェネリック List コレクションです。

図 3 コンセンサス分類のデータ構造

0 と 1 の意味は、列や投票ごとに異なります。デモ プログラムでは、列または投票ごとに、Dictionary コレクションの配列を構築します。トレーニング データの各列で値を見つけたときに、各文字列値にゼロから始まる整数 ID を割り当てます。たとえば、トレーニング データの列 [0] の投票 [0] では、最初に "n" を見つけて 0 を割り当て、次に "y" を見つけて 1 を割り当てます。しかし、列 [1] では、最初に "y" を見つけて 0 を割り当て、次に "n" を見つけて 1 を割り当てます。

同様に、列 [16] では、"republican" を最初に見つけて "0" に割り当て、次に "democrat" を見つけて 1 を割り当てます。最後の列は、従属変数値として "democrat" または "republican" を保持します。文字列から整数値へのマッピング情報は、stringToInt というクラス メンバーの配列に格納します (図 3 参照)。そのため、stringToInt[1]["y"] という式は、投票 [1] の賛成票のゼロから始まるインデックス値を返します。デモのトレーニング データの場合は "0" を返します。

分類モデルを定義するルールを作成する大まかな擬似コードは以下のとおりです。

loop while numRules < maxRules && trial < maxTrials
  ++trial
  select a random row of training data
  select numConditions random columns of selected row
  create candidate rule from selected columns of selected row
  if candidate rule already in rule list, continue
  if candidate rule does not meet minimum accuracy, continue
  candidate rule is good so add rule to rule list
end loop

わかりやすく、具体的な例で考えてみましょう。メイン ループで、トレーニング データの行 [0] がランダムに選択されるとします。次に、numConditions は 3 に設定され、ランダムに選択された 3 つの列は [1]、[2]、および [15] だとします。トレーニング データでは、これらの列に "y" 値、"n" 値、"y" 値が保持されていて、従属変数には "republican" 値が保持されています。列の値を Dictionary コレクションの配列で検索すると、0、0、0 が返されます。したがって、ルールの候補は、「列 1 が 0、列 2 が 0、列 15 が 0 の場合、政党は 0」と解釈できる { 1, 0, 2, 0, 15, 0, 0 } という値を保持する整数配列になります。

次に、トレーニング データの 80 項目をスキャンして、ルールの候補が最低限の正確性を満たしているかどうかを確認します。ルールの候補は、少なくとも 1 個のデータ項目 (このルールの作成に使用した項目) には一致します。ただし、ルールの候補は、必ずしもすべてのトレーニング項目に当てはまるわけではありません。たとえば、データ項目 [0] から生成された { 1, 0, 2, 0, 15, 0, 0 } というルールの候補は、列 [2] に必要な 0 ではなく 1 を保持するため、データ項目 [1] には当てはまりません。

ルールの集合の作成後、入力データの特定のセットの出力は、開票結果によって決まります。データ項目ごとに、ルールの集合に含まれるすべてのルールを分析します。ルールの集合に 500 個のルールがあるとします。特定のデータ項目について、220 個のルールが共和党と予測し、250 個のルールが民主党と予測し、30 個のルールが当てはまらないとします。この場合、コンセンサス分類では、そのデータに関連付けられている議員の所属政党は民主党であると予測します。つまり、出力はルールの集合のコンセンサス (総意) になります。

コメントをいくつか

今回紹介したコンセンサス分類手法は、少し前に取り組んだ研究プロジェクトがきっかけです。具体的には、インスタント メッセージのユーザーの地域、年齢カテゴリなどの変数を基に、ユーザーの性別 (男または女) を予測しようとしたのが動機です。直感的には手掛かりになるだけの情報がデータに含まれていると思いましたが、既存の ML ツールを使用して、思いつく標準分類アプローチをすべて試してみたところ、効果的な予測モデルを生成できませんでした。

試してみた基本的な分類アプローチの中では、単純ベイズ分類が最も優れているように思えました。単純ベイズでは、それぞれの予測変数は数学的に独立しているものと想定します。この想定は多くの場合正しくありませんが、単純ベイズがかなりうまく機能する場合もあります。私が問題としたのは、予測変数がほぼ確実に何らかの方法で関連しているとしても、どの変数が関連しているかがわからなかったことです。そのため、複数の ML 手法からパーツを取り出して、今回紹介したアプローチを組み立てることにしました。最終的には、標準手法のモデルよりもかなり正確な予測モデルを作成できました。

従属変数は "Democrat" と "Republican" のどちらかになるので、バイナリ分類の問題です。さらに、予測のすべての因子は "賛成" と "反対" のいずれかになるので、バイナリ カテゴリの変数です。コンセンサス分類では、多項式の分類問題 (たとえば、民主党、共和党、無所属) を処理することや、2 つ以上の値 (たとえば、賛成、反対、欠席、棄権) を保持するカテゴリ予測因子を扱うことができます。実験では、年齢のように予測変数が数値となる問題が与えられ、これをカテゴリ (若年、中年、老年) に分けた場合、コンセンサス分類の効果がどの程度になるかは明確ではありません。

複数のルールまたはモデルを組み合わせて分類結果を生成する場合、ML 用語ではアンサンブル学習 (ensemble learning) と呼びます。簡単なルールを多数生成する考え方は ML 手法で使用されていて、ブースト手法 (boosting techniques) と呼ばれることもあります。「テストの実行」コラムでは、常に明確な研究に基づいた ML 手法を紹介しています。ただし、今回は例外です。今回紹介した手法はまだ研究されておらず、本格的な研究対象になることもありません。数人の同僚研究者から、独自の新しい ML 手法を使用する大胆な試みに取り組むように勧められてきましたが、いつも少し不機嫌に「エレガントな数学理論を確立することよりも、結果を得ることに関心がある」と答えてきました。標準 ML 手法を使用することは、ML 問題に取り組む際の最初のアプローチとして最適です。ただし、従来の手法でうまくいかない場合は、独自のソリューションを作成すると驚くほどの効果を発揮することもあります。

---

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

この記事のレビューに協力してくれた Microsoft Research 技術スタッフの Marciano Moreno Diaz Covarrubias、Delbert Murphy、David Raskino、および Alisson Sol に心より感謝いたします。