October 2015
Volume 30 Number 10
テストの実行 - C# を使用した線形判別分析
二項分類の問題は、変数が取り得る 2 つの値のうち、どちらになるかを予測することを目指します。たとえば、株の平均販売数、インサイダー取引の数、株価の収益率などの予測変数に基づいて、ある企業の株価の変動 (増減) を予測します。あるいは、年齢、年収、学歴などに基づいて、政治的傾向 (リベラル派か保守派か) を予測します。
二項分類に使われる主要アルゴリズムは 10 個以上あります。線形判別分析 (LDA: Linear Discriminate Analysis) は、1930 年代に考案された最も歴史のあるアプローチの 1 つです。今回は、この LDA の概要、しくみ、およびコードで LDA を実装する方法について説明します。
現実的には、LDA のコードを記述する必要性はあまりないかもしれませんが、今回のコラムが役に立つ理由は 3 つあります。まず、LDA のプログラミング方法を理解すれば、LDA のしくみがわかり、いざというときに戸惑いません。次に、LDA の実装に使用するコーディング テクニックの一部は、一般的なプログラミング シナリオにも活かせます。最後に、LDA を支える考え方は特別気が利いているため、それだけで LDAに興味を持つかもしれません。
LDA 二項分類の雰囲気を感じ、今回の目標を確認するには、図 1 のデモ プログラムを見るのが一番です。
.png "線形判別分析二項分類のデモ")
図 1 線形判別分析二項分類のデモ
このデモ プログラムの目標は、年齢と年収に基づいて、政治的傾向 (リベラル派か保守派か) を予測することです。デモでは、LDA 予測モデルを作成するために 8 つの項目から成る小さなトレーニング データ セットを使用します。年齢と年収はどちらも値の大きさがほぼ同じになるように、なんらかの方法で正規化します。
政治的傾向は、リベラル派を 0、保守派を 1 にエンコードします。他の多くの二項分類アルゴリズムとは異なり、LDA では、予測対象の変数にあらゆる種類のエンコーディングを許可します。たとえば、政治的傾向を、-1 と +1、"A" と "B" にエンコードしてもかまいません。
基本 LDA 二項分類は、予測変数の数とは無関係に機能します。また、基本 LDA を拡張して、3 つ以上の値のいずれかになり得る変数を予測することもできます。たとえば、リベラル派、保守派、穏健派を候補値として政治的傾向を予測することができます。今回は、二項分類のみを取り上げます。
LDA で鍵になるのは線形判別と呼ばれる項目です。これは通常小文字の "w" で表します。このデモでは、8 つのデータ項目を使用して、w = (-0.868, -0.496) を計算しています。配列 w は、予測変数と同じ数の値を持つことになります。w を求めるとき、このデモでは 2 つのクラスでそれぞれ平均を計算した後、この平均を使用してクラスごとに分散行列を計算します。最後に、この分散行列を使用して、組み合わせクラス内分散行列を計算します。クラス内分散行列は、w の計算に必要です。
w を計算後、その w を使用して、正規化した age = 4.0 と income = 5.0 を持つ新しい人物のクラスを予測します。LDA の予測では、この新しい人物の政治的傾向はリベラル派になります。
今回は、少なくとも中級レベルのプログラミング スキルがあることを前提としますが、LDA 分類アルゴリズムの知識は問いません。このデモは C# を使用してコーディングしていますが、コードを Visual Basic .NET や JavaScript などの別の言語にリファクタリングしても大きな問題は起きません。
LDA 二項分類について
LDA 二項分類の主となる考え方を 2 つのグラフで示します (図 2 参照)。最初のグラフは、デモ プログラムのデータを示しています。3 つの青い点は、リベラル派の 3 名を示します。5 つの赤い点は、保守派です。黄色の点 (4.0, 5.0) は、政治的傾向が不明な人物です。このような単純な問題でも、政治的傾向が不明な人物は、リベラル派なのか保守派なのかは定かではありません。
.png "判別ベクトルを使用した LDA 予測")
.png "判別ベクトルを使用した LDA 予測")
図 2 判別ベクトルを使用した LDA 予測
図 2 のようにデモ データをグラフで示せるのは予測変数が 2 つしかないためです。予測変数が 2 つ以上あるとデータを 2D グラフで上手く示せないこともありますが、適用する LDA の原理は同じです。二項分類 LDA の予測変数の数には関係なく、クラスは 2 つだけです。予測変数の数 (2 つ以上) と、予測対象の変数が取る値の数 (二項分類では常に 2 つ) を混同しないでください。
ほんとんどの二項分類アルゴリズムは、2 つのクラスを明確に区分する線 (技術的にはベクトル) を見つけようと試みることになります。たとえば、図 2 の最初のグラフでは、(3, 9) から (5, 0) へと延びる仮の区分線があると想像できます。仮の区分線の左側にあるデータ点はリベラル派に、右側にあるデータ点は保守派に分類できます。しかし、LDA が機能する方法はまったく異なります。
LDA の最初の手順は、判別と呼ばれる線を見つけることです。図 2 では、判別線を緑色の線で、判別を (0.868, 0.496) で示しています。LDA では、判別線は 1 つの終了点で決まり、始点は常に暗黙のうちに (0, 0, . ., 0) となります。
しかし、図 1 のデモ プログラムの出力では、判別が (+0.868, +0.496) ではなく、(-0.868, -0.496) と示されています。結局のところ、判別の成分には任意の定数を乗算できるため、結果には影響しません。そのため、重要な考え方を示し、図 2 下のグラフの見栄えをよくするために、w には実際の計算で求められる負の値ではなく、(+0.868, +0.496) を使用しています。つまり、両方の成分に -1 を乗算します。
言い換えると、判別は、図 2 に示す緑色の直線上にある任意の点 (-2 * (-0.868, -0.496) = (1.736, 0.992) など) で特定できます。LDA の標準 (世界標準ではない) では、原点からの長さが 1 となるように判別を決めます。つまり、(0, 0) から (0.868, 0.496) への長さが、sqrt( (0 - 0.868)^2 + (0 - 0.496)^2 ) = sqrt(0.754 + 0.246) = sqrt(1.000) = 1 になっています。
では、判別ベクトルの重要性について考えます。図 2 では、各データ点から判別線上に投影される点へと延びる黒い破線が示されています。この黒い破線は判別線に対して垂直です。結局、判別線とは (0, 0) を始点とする直線で、クラスごとの投影点までの距離を最小にし、同時に投影点の 2 つのグループ間の距離を最大にする直線です。これは、明確とはあまりいえない考え方です。
では、データのセットに対して判別ベクトルを計算できるとしても、この判別ベクトルを使用して予測する方法についてはまだ明確ではありません。図 2 で、「mean」(中点) という紫色のひし形は、2 つのクラスの中点の平均データ点です。この中点は、データ点の 2 つのグループの中央にあるのがわかります。ここで、紫色の中点から緑色の判別線へと垂直に延びる破線を考えます。この投影線は、ほぼ点 (5.2, 3.0) で判別線に交わります。
今度は、分類の対象となる黄色の点から緑色の判別線へと延びる垂線を考えます。分類対象の点からの投影線は、中点の投影線の交点よりも左側で交わり、リベラル派のデータ点の投影点により近いことから、リベラル派に分類されます。政治的傾向が不明な点から判別線へと延びる投影線が、中点の投影線よりも右側で交わる場合、この点は保守派に分類されます。非常に気の利いた考え方です。
LDA 二項分類の実装
デモ プログラムの全体構造を図 3 に示します。スペースを節約するために WriteLine ステートメントをいくつか削除し、少し編集しています。デモ プログラムを作成するには、Visual Studio を起動して、LinearDiscriminate という新しい C# コンソール アプリケーションを作成します。このデモは特定の .NET バージョンとの依存関係はないため、どのバージョンの Visual Studio でも動作します。テンプレート コードをエディターに読み込んだ後、最上位レベルの System 名前空間への 1 つの参照を除いて、すべての using ステートメントを削除します。次に、ソリューション エクスプローラー ウィンドウで、Program.cs ファイルの名前を LinearDiscriminateProgram.cs に変更します。これにより Program クラスの名前が Visual Studio によって自動的に変更されます。
図 3 デモ プログラムの全体構造
using System;
namespace LinearDiscriminate
{
class LinearDiscriminateProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin LDA demo");
// All program control statements here
Console.WriteLine("End LDA demo");
Console.ReadLine();
}
static int Prediction(double[][] data,
double[] x, double[][] w) { . . }
static int Prediction(double[][] data,
double[][] x, double[][] w) { . . }
static double[][] Mean(double[][] data,
int c) { . . }
static double[][] Discriminate(double[][] data,
bool unitize) { . . }
static double[][] ScatterWithin(double[][] data) { . . }
static double[][] Scatter(double[][] data, int c) { . . }
static double[][] Unitize(double[][] vector) { . . }
// Matrix helper methods here
}
} // ns
デモ プログラムは長すぎてここにすべて掲載することはできませんが、完全なソース コードは本稿付属のコード ダウンロードから入手できます。今回はオブジェクト指向プログラミングのアプローチではなく、静的メソッドのアプローチを使用しています。
Main メソッドでは、まず、配列の配列形式の行列でハード コーディングした 8 項目のトレーニング データ セットを設定します。
double[][] data = new double[8][];
data[0] = new double[] { 1.0, 4.0, 0 };
data[1] = new double[] { 2.0, 2.0, 0 };
// Etc. for [2] through [6]
data[7] = new double[] { 9.0, 8.0, 1 };
ShowMatrix(data, 2, true);
実際のシナリオでは、おそらく、LoadData のような名前のメソッドを使用して、テキスト ファイルからメモリにデータを読み取ることになります。判別の計算は以下のように実行します。
double[][] w = Discriminate(data, true);
Console.WriteLine("Discriminate is: ");
ShowMatrix(w, 6, true);
Discriminate メソッドの戻り値は、配列ではなく、配列の配列形式の行列にしているのがわかります。LDA で使用する演算のほとんどは、行列乗算や逆行列計算といった行列演算です。ここで w は、2 つのセルを持つ配列ではなく、2 行 1 列の行列です。このような 1 列の行列は列ベクトルとも呼びます。行列の使用経験が少ないと、配列ではなく行列の操作に慣れるまで、しばらく時間がかかるかもしれません。
図 1 では、いくつか中間オブジェクトを計算して表示しています。LDA を理解しやすくするために、このような表示ステートメントを Discriminate メソッドやヘルパー メソッドの内部に置いていますが、運用コードでは、おそらく表示ステートメントを削除することになります。
予測対象の項目を設定するステートメントを以下に示します。
double[] x = new double[] { 4.0, 5.0 };
Console.WriteLine("Predicting class for Age Income =");
ShowVector(x, 1);
ここでは説明を簡単にするために予測対象の項目を通常の数値配列にしていますが、後で 1 列の行列に変換する必要があります。予測のステートメントを以下に示します。
int c = Prediction(data, x, w);
Console.Write("Predicted class: " + c);
if (c == 0)
Console.WriteLine(" (liberal)");
else
Console.WriteLine(" (conservative)");
Prediction メソッドは、平均の平均を計算するために data 行列を受け取ります (図 2 参照)。このメソッドには、予測対象の項目 x と判別ベクトル w も必要です。
判別の計算
Discriminate メソッドは、LDA 判別ベクトルを計算します。ほぼすべての作業はヘルパー メソッドによって実行されるため、WriteLine ステートメントと表示ステートメントを削除したコードは、驚くほど短くなります。
static double[][] Discriminate(double[][] data, bool unitize)
{
double[][] mean0 = Mean(data, 0);
double[][] mean1 = Mean(data, 1);
double[][] Sw = ScatterWithin(data);
double[][] SwInv = MatrixInverse(Sw);
double[][] diff = MatrixSubtract(mean0, mean1);
double[][] w = MatrixProduct(SwInv, diff);
if (unitize == true) return Unitize(w);
else return w;
}
LDA 判別を行う演算は非常に複雑ですが、結果はごくシンプルです。ヘルパー メソッド Mean は、特定のクラス (0 または 1) の平均を計算します。たとえば、リベラル派 (クラス 0) を表す 3 つのデータ項目は、(1, 4)、(2, 2)、および (3, 3) です。この場合の平均は、( (1+2+3) / 3, (4+2+3)/3 ) = (2.0, 3.0) です。
クラス内分散行列は、データ セットの変位を測定します。mean0 と mean1 という 2 つのクラス平均と、クラス内分散行列 (Sw: scatter-within) があるとすると、判別は、Sw の逆行列と、mean0 と mean1 の行列差との行列積です。
判別の方程式を求める複雑な計算を説明している資料は、インターネット上でいくつも見つけることができます。w の導関数には多くのバージョンがあります。特に、共分散やクラス間分散 (Sb: Scatter-between) を引用するものを目にします。共分散は、数学的にはクラス内分散 (Scatter-within) に相当します。クラス間分散は、数学的には LDA 判別の方程式の導出に使用されますが、判別の計算や予測の作成を目的として明示的に使用されることはありません。
Discriminate メソッドには、判別を単位長 (1.0) に倍率変換するかどうかを示す unitize というブール値のパラメーターがあります。多くの場合、この引数には true を渡します。
予測
デモ プログラムには、オーバーロード Prediction メソッドが 2 つあります。1 つは、通常の数値配列として予測対象項目 x を受け取ります。
static int Prediction(double[][] data, double[] x, double[][] w)
{
double[][] xm = MatrixFromVector(x);
return Prediction(data, xm, w);
}
このバージョンは呼び出しを簡単にすることが目的で、実際に演算を実行するもう 1 つのバージョンのラッパーにすぎません。
static int Prediction(double[][] data, double[][] x, double[][] w)
{
int dim = data[0].Length - 1; // at least 2
double[][] wT = MatrixTranspose(w); // 1 x d
double[][] m0 = Mean(data, 0); // d x 1
double[][] m1 = Mean(data, 1); // d x 1
double[][] m = MatrixAdd(m0, m1); // d x 1
m = MatrixProduct(m, 0.5); // d x 1
double[][] tc = MatrixProduct(wT, m); // ((1xd)(dx1) = 1 x 1
double[][] wTx = MatrixProduct(wT, x); // (1xd)(dx1) = 1 x 1
if (wTx[0][0] > tc[0][0]) return 0; else return 1;
}
Prediction メソッドは w の転置を計算するため、行列乗算で使用されます。2 つのクラスの中央値を計算後、各成分値に 0.5 を乗算して行列 m に格納することによって、これら 2 つの中央値の平均を計算します。
行列 tc はしきい定数で、判別ベクトルの転置 wT とクラス中央値の平均 m との積です。行列 tc は常に、1 つの値を保持する 1 行 1 列の行列です。行列 tc の値は、平均から判別ベクトルへの投影を表します。
予測対象項目 x から判別ベクトルへの投影は、同様に、判別ベクトルの転置と x との行列積として計算されます。ただし、判別の投影は正にも負にもなり得るため、使用するブール値の比較演算子 (< または >) は、問題によって異なります。最も簡単なアプローチは、> を使用して有意義な結果が得られるかどうか試してみることです。使用する演算子をプログラムで指定することもできますが、このアプローチを採用すると、追加するコード量が想像以上に多くなります。
予測を行う場合、各クラスの確率を考慮に入れることによって、クラス中央値の平均の投影を調整することも可能です。この調整係数が log(p0 / p1) です。p0 はクラス 0 の確率、p1 はクラス 1 の確率を示します。このデモ データでは、p0 = 3/8 = 0.375、p1 = 5/8 = 0.625 として、調整係数 log(0.375 / 0.625) = log(0.6) = -0.22 を求めています。2 つの確率が等しいとすると、p0 = p1 となり、調整係数は log(1) = 0 になります。
コメントと制限事項
実際には、LDA のバリエーションは複数あります。今回紹介したバリエーションは通常、フィッシャーの LDA と呼ばれます。LDA は、フィーチャーの選択 (あまり役に立たない予測変数を無視できるように、最も有用な予測変数を特定する) や分類に使用することもできます。自然言語の処理で使用する、まったく異なる静的 LDA (Latent Dirichlet Allocation: 潜在的ディリクレ配分法) もあることに注意してください。
LDA 二項分類は数学的には明解ですが、重要な制限事項がいくつかあります。LDA 内部での想定がバージョンごとに異なります。たとえば、予測変数を正規分布させるものや、相似共分散を持たせるものがあります。多くの状況には、このような想定が当てはまりません。ただし、数学上の想定が当てはまらなくても、LDA は多くの場合にまったく正常に機能します。もう 1 つ数学上の制限事項として、LDA では、クラス内分散行列の逆行列を計算する必要があります。逆行列を求めるのは非常に厄介なプロセスで、失敗しやすいプロセスです。
おそらく、LDA 二項分類の最大の制限事項は、2 つのクラスを線形分離できると想定している点です。大まかに言えば、図 2 のようなグラフにした場合、2 つのクラスを区分する直線を見つけなければなりません。多くの問題のデータは、簡単には線形分離できません。
個人的な意見として、LDA 二項分類は美しいと考えていますが、ロジスティック回帰分類やニューラル ネットワーク分類など、他にも実用性の高い分類アルゴリズムがあります。とは言え、LDA が興味深いことは確かです。
Dr. James McCaffrey は、ワシントン州レドモンドにある Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。McCaffrey 博士の連絡先は、jammc@microsoft.com (英語のみ) です。
この記事のレビューに協力してくれた Microsoft Research 技術スタッフの Madison Minsk および Amy Shan に心より感謝いたします。