2015 年 10 月

第 30 卷，第 10 期

本文章是由機器翻譯。

測試回合 - 使用 C# 的線性判別分析

由 James McCaffrey

二進位分類問題的目標是要預測可以採用的兩個可能值的其中一個變數的值。例如，您可能想要預測像是共用的平均數目賣出、 內行人交易、 對盈餘比率價格數目等等根據預測工具變數 (增加或減少) 某家公司的股票價格的變更。或者您可能想要預測的人員 (自由或保守) 政治傾斜根據年齡、 收入、 教育程度等等。

大約有數十個主要的演算法可用於二進位的分類。線性區分分析 (LDA) 是其中一種最舊的方法，從 1930年進行資料。這篇文章說明用途 LDA、 說明其運作方式並示範如何實作 LDA 以程式碼。

實際上，也不太可能全能撰寫 LDA 程式碼。不過，有三個原因可能會發現這篇文章很有用。首先，了解如何撰寫程式 LDA 可讓您深入認識了萬一您曾經無意中發現 LDA 運作的方式。第二，有些實作 LDA 時使用的程式碼撰寫技巧可用於其他較常見的程式設計案例。最後，LDA 背後的觀念是超級聰明和您可能會發現 LDA 有趣為了自己起見。

概略了哪些 LDA 二進位分類是以及查看其中本文開頭都是最佳方式是看看在示範程式 [圖 1。

[圖 1 線性 Descriminate 分析二進位分類示範

示範程式的目標是要預測政治傾斜自由或保守的根據個人的年齡和年收入人員。示範使用只是 8 個項目來建立 LDA 預測模型很小的訓練資料集。年齡與收入已經正規化以某種方式使其範圍都大致相同。

已編碼政治傾斜讓該自由為 0 並保守為 1。不同於許多的二進位的分類演算法 LDA 可以使用任何一種編碼的變數來預測。因此政治傾斜無法被編碼為"-1 和 + 1 或 A"和"B"

基本 LDA 二進位分類可以使用任何數目的預測變數。而且可以擴充基本 LDA 來預測可以採取三個或多個值的其中一個變數。例如，您可以預測的可能值的自由、 保守和中度的政治傾斜。本文將說明只二進位的分類。

LDA 的關鍵在於所謂線性區分通常由小寫"w"。 使用八個資料項目，示範計算 w = (-0.868、-0.496)。W 陣列有預測變數具有相同數目的值。計算 w 時, 在幕後示範計算兩個類別的每個方法則用於表示計算每個類別的散佈圖矩陣並用最後散佈矩陣來計算內類別的組合的散佈矩陣。需要計算 w 類別內矩陣。

之後計算 w，示範會使用它來預測類別的新人已恢復 age = 4.0 和正規化收入 = 5.0。LDA 預測是人可自由政治傾斜。

本文假設您已至少中繼程式設計技巧，但不會假設您知道 LDA 分類演算法。使用 C# 程式碼示範但您不應該沒什麼困難如果您想要重構到另一種語言如 Visual Basic.NET 或 JavaScript 程式碼。

了解 LDA 二進位分類

在兩個所示的圖表中說明 LDA 二進位分類的主要概念 [圖 2。上的圖形顯示示範應用程式的資料。三個藍色點代表三個是大量的人。五個的紅點是 conservatives。在黃點 (4.0、 5.0) 表示具有未知的政治傾斜的人員。即使是針對這類簡單的問題，並不明顯如果未知的人士應該分類為自由或作保守的估計。

[圖 2 LDA 預測使用區分向量

請注意的唯一理由的示範中所示無法以繪製資料 [圖 2 是有兩個預測變數。如果有兩個以上的預測工具變數，不是可能會因此好好 2D 圖形中的資料但 LDA 的相同原則會套用。不論二進位 LDA 中有多少預測工具變數，將只會有兩個類別。它很容易混淆的預測工具變數 (兩個或多個) 要預測的變數可以採取 (一律正好兩個二進位分類) 的值數目與數目。

大部分的二進位的分類演算法會嘗試找到明確分隔的兩個類別的行 (就技術上而言向量)。例如，在頂端的圖表中 [圖 2, ，您可以想像假設分隔從即將執行的那一行 (3，9) 向 (5，0)。線條左邊任何未知的資料點會分類為自由，並在右邊的任何點會作保守的估計。LDA 運作完全不同的方式。

LDA 的第一步是尋找稱為區分一條線。在 [圖 2, 、 區分列是綠色，以及區分識別為 0.868 (0.496)。在 LDA，區分線條一律由單一的結束點和的起始點是一律以隱含方式 (0，0，。。，0)。

但是等一下。中的示範程式的輸出 [圖 1 顯示區分 (-0.868、-0.496) 而不是 +0.868 (+0.496)。其實，乘以任何常數的區分的元件而且會有不會影響結果。因此，藉此在底部圖形 [圖 2 看起來更簡潔並說明這個重要的概念，我使用 (+0.868、 +0.496) w 而非實際的導出的值，這是負數。換句話說，我乘以這兩個元件-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, ，紫色菱形標示為"表示 「 是的平均資料點的兩個類別表示。您可以看到平均值會在中間兩個資料點群組。現在想像一下紫色平均值綠色區分列下垂直虛線。投影列會在叫用相關 (5.2、 3.0)。

然後想像黃色的點來分類到綠色區分線從垂直線條。投影要分類的點落左邊投影的平均值，因為它比較接近大量資料點的預測並因此被歸類為自由。如果從未知點投影至區分一行有平均值破投影的另一端，點會有已分類的溫和。非常聰明的主意。

實作 LDA 二進位分類

示範程式，與幾個 WriteLine 陳述式移除和次要的編輯以節省空間的整體結構所示 [圖 3。若要建立示範程式，我啟動 Visual Studio 並建立新 C# 主控台應用程式名為 LinearDiscriminate。示範有沒有顯著的.NET 版本相依性所以任何版本的 Visual Studio 應該會運作。載入編輯器中的範本程式碼之後，我會刪除所有使用除了最上層系統命名空間的單一參考陳述式。在 [方案總管] 視窗中，我可以重新命名為 LinearDiscriminateProgram.cs 的 Program.cs 檔案並允許 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 方法一開始會設定成陣列的陣列樣式矩陣硬式編碼八項目訓練資料集：

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);

請注意區分方法的傳回值是陣列的陣列矩陣而不是陣列。大部分 LDA 中所使用的作業都是矩陣的作業，例如矩陣相乘和矩陣反轉。在這裡，而非陣列具有兩個資料格 w 是具有兩個資料列和一個資料行的矩陣。這類單一資料行的矩陣有時也稱為資料行向量。除非您經常使用的矩陣，可能需要一段時間才能習慣使用而不陣列。

在 [圖 1, ，您可以看到數個中繼物件會計算並顯示。顯示陳述式是在內部方法 Discriminate 和 helper 方法和要幫助您了解 LDA。您可能會在實際執行程式碼中移除顯示陳述式。

設定項目來預測的陳述式 ︰

double[] x = new double[] { 4.0, 5.0 };
Console.WriteLine("Predicting class for Age Income =");
ShowVector(x, 1);

這裡呼叫方便要預測的項目儲存在一般數字陣列，即使有更新版本轉換成單一資料行的矩陣。預測陳述式是：

int c = Prediction(data, x, w);
Console.Write("Predicted class: " + c);
if (c == 0)
  Console.WriteLine(" (liberal)");
else
  Console.WriteLine(" (conservative)");

預測方法才能計算中所示的方式表示接受資料矩陣 [圖 2。方法也需要要預測的項目、 x 和區分向量，w。

計算區分

方法區別計算 LDA 區分向量。程式碼 WriteLine 和顯示陳述式中移除，是工作的非常簡短因為大部分工作的由 helper 方法：

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 背後的數學原理是相當複雜，但結果是相當簡單。Helper 方法平均值會計算指定的類別 (0 或 1) 的平均值。例如，三個資料項目該代表自由 (類別 0) 是 (1，4) (2，2) 和 (3，3)。其平均值為 ((1 + 2 + 3) / 3、 (4 + 2 + 3) / 3) = (2.0、 3.0)。

散佈圖內的矩陣是量值的變數資料集的方式。使用兩個類別方法、 mean0 和 mean1 和散佈在矩陣 Sw 手邊區分是 Sw 反向和 mean0 與 mean1 矩陣差異矩陣的乘積。

您可以找到數個在網際網路上的資源說明相當複雜的數學衍生區分的方程式。請注意有許多不同 w 衍生版本。特別是，您可能會看到共變數和散佈圖之間 (Sb) 的參考。共變數是相當於 [散佈圖內的數學實體。散佈圖之間是方程式的用於衍生 LDA 的數學實體區別，但散佈之間不明確用來計算區分或進行預測。

方法區別具有名為 unitize 的布林參數會指出要調整區分到單位的長度，也就是長度等於 1.0。在大部分情況下您想要傳遞做為對應的引數則為 true。

做出預測

示範程式有兩個多載的預測方法。第一個可接受的項目來預測，x 為一般的數值陣列:

static int Prediction(double[][] data, double[] x, double[][] w)
{
  double[][] xm = MatrixFromVector(x);
  return Prediction(data, xm, w);
}

這一版的預測是呼叫方便而只是包裝函式進行預測的版本:

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;
}

方法預測計算 w 調換因此用於矩陣相乘。計算兩個類別的方法，然後這些兩種方法的平均值會計算每個元件值乘以 0.5 並且然後儲存在矩陣 m。

矩陣 tc 臨界值常數就必須區分向量、 wT，和類別表示平均調換產品 m。矩陣 tc 一律為 1x1 矩陣保存單一值。此值在矩陣 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。請注意，如果兩個機率會假設等於、 然後 p0 = p1 和調整係數是 log(1) = 0。

註解和限制

有實際數個不同的變數 LDA。在本文中介紹的一個通常會呼叫費雪 LDA。LDA 也可用特徵 (用來識別哪些預測變數最有用的使較有用的預測可略過)，以及分類。也請注意其中自然語言處理中使用完全不同統計 LDA (潛伏狄氏配置)。

雖然 LDA 二進位分類是以數學方式簡潔，它有幾項重要的限制。在幕後不同版本的 LDA 進行各種假設，例如預測變數通常是分散式而有類似的變數。在許多情況下，這些假設不是 true。即便如此，實際上，LDA 通常適用於蠻好甚至符合數學假設不是。另一個數學限制是 LDA 必須計算散佈在矩陣的反向作業。矩陣反轉是非常棘手的程序並可以輕鬆地失敗。

或許 LDA 二進位分類的最大限制是它會假設兩個類別是以線性方式可分隔。鬆散談到，這表示當中繪製圖形 [圖 2, ，就可以找到用來分隔兩個類別的直線。許多問題的資料並不是以線性方式可分隔。

在我看來，LDA 二進位分類是美觀，但有替代的分類演算法，值得注意的是羅吉斯迴歸分類與類神經網路分類更實用。但是 LDA 確定有趣。

Dr。James McCaffreyRedmond，華盛頓中的 Microsoft Research 的運作方式他曾在包括 Internet Explorer 和 Bing 的數個 Microsoft 產品。Dr.McCaffrey 可以到達jammc@microsoft.com。

感謝下列技術專家 Microsoft research 校對本篇文章： Madison 明斯克和 Amy Shan