2015 年 10 月

第 30 卷，第 10 期

此文章由机器翻译。

测试运行 - 使用 C# 实现线性判别分析

通过 James McCaffrey

二进制分类问题的目标是变量的预测在两个可能值之一可以执行的值。例如，您可能想要预测股票价格的一些公司 （增加或减少） 中基于预测值变量平均共享已销售的数，深入了解事务，与收入的比率的价格数，等等类似的更改。或者您可能想要预测某人 (自由或保守) 政治倾角基于年龄、 收入、 教育水平，等等。

中有大约十几个可用于二进制分类的主要算法。线性鉴别分析 (LDA) 是一种最早的方法，可以追溯 1930s年。这篇文章说明了什么 LDA，介绍其工作原理以及演示如何使用代码实现 LDA。

实际上，不太可能您将需要编写 LDA 代码。不过，有三个原因您可能会发现这篇文章很有用。首先，了解如何进行编程 LDA 为您提供全面掌握如何 LDA 以防您曾经遇到过它的工作原理。第二，一些实现 LDA 时使用的编码技术可以是其他，更常见的编程方案中非常有用。最后，LDA 理念是非常聪明，您可能发现 LDA 有趣本身。

若要获得有个大概了解是哪些 LDA 二进制分类并查看本文所述观点的最佳方法是看一下在演示程序 图 1。

图 1 线性 Descriminate 分析二进制分类演示

演示程序的目标是预测政治倾角，自由或保守的基于此人的存在时间和年收入的人员。演示使用随只是八个项的一个小的定型数据集来创建 LDA 预测模型。Age 和 income 具有已规范化以某种方式，以便其数量级都大致相同。

因此，该自由是 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 中。因此应运行任何版本的 Visual Studio，演示并没有明显的.NET 版本依赖性。模板代码载入编辑器后，我将删除所有 using 语句对顶级 System 命名空间的单个引用除外。在解决方案资源管理器窗口中，我将文件 Program.cs 重命名为 LinearDiscriminateProgram.cs 并允许 Visual Studio 会自动为我中重命名类 Program。

图 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 和其帮助器方法和主要是为了帮助您了解 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 和显示的语句中删除，则非常短因为大部分工作通过帮助器方法：

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 背后的数学函数是相当复杂，但结果却相当简单。帮助器方法平均值计算给定类 （0 或 1） 的平均数。例如，该表示自由 (类 0) 的三个数据项是 (1，4)，(2，2) 和 (3，3)。其平均值为 ((1 + 2 + 3) / 3，(4 + 2 + 3) / 3) = (2.0，3.0)。

散点图中矩阵是度量值的变量数据集的方式。使用了两个类一种方法、 mean0 和 mean1 和散点图中的矩阵 Sw 手中，鉴别就是软件的逆和矩阵之间 mean0 mean1 的差异的矩阵乘积。

您可以找到介绍派生的计算公式为鉴别相当复杂数学 Internet 上的多个资源。请注意 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 将始终为 1 x 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。请注意，如果两个概率都被认为是相等，则 p0 = p1 和调整因子将是 log(1) = 0。

注释和限制

有一些实际几个不同变体 LDA。本文中介绍的一个通常称为 Fisher 的 LDA。LDA 还可用于功能选择 （标识哪些预测值的变量最有用，这样可以忽略不太有用的预测值) 以及分类。请注意其中是在自然语言处理过程中使用完全不同统计 LDA （潜在 Dirichlet 分配）。

尽管 LDA 二进制分类是数学上完善，但它具有几个关键限制。在后台，不同版本的 LDA 做出各种假设，例如预测值的变量通常是分布式而具有类似协。在许多情况下，这些假设不是 true。即便如此，在实践中，LDA 时通常非常很好地甚至数学假设不满足时。另一个数学限制是 LDA 必须计算的散点图中矩阵反函数。矩阵反转是一件非常麻烦的过程，并且可以轻松地失败。

也许 LDA 二进制分类的最大限制是假定两个类是线性可分离。简单来说，这意味着，当作为 in 制成图表 图 2, ，就可以找到一条直线分隔两个类。很多问题的数据只是不是线性可分离。

在我看来，LDA 二进制分类是太棒了，但有备用的分类算法，值得注意的是逻辑回归分类和神经网络分类是更为实用。但 LDA 是确保有趣。

Dr.James McCaffrey供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和 Bing。Scripto可通过 jammc@microsoft.com 与 McCaffrey 取得联系。

衷心感谢以下 Microsoft Research 技术专家对本文的审阅： Madison 明斯克和 Amy 山