测试运行

  • 项目

使用 C# 进行一致分类

James McCaffrey

下载代码示例

James McCaffrey在机器学习 (ML) 中，模型用于预测显示为分散的非数值的值，分类则是构建此模型（通常是某种数学公式或规则集合）的过程。例如，您可能要根据一名国会议员的投票记录来预测其政治党派（是民主党还是共和党）。训练模型的过程如下：查找（数学公式模型的）常量集合或（基于规则的模型的）规则集合，以便在通过已知输出因变量值显示训练数据时，计算的输出结果与已知结果近乎一致。然后，可使用该模型对具有未知输出结果的新数据进行预测。

尽管已有众多标准分类算法和技术（包括 Naive Bayes 分类、逻辑回归分类和神经网络分类），但对于某些问题来说，自定义分类算法非常有用。本文介绍了一种自定义技术，由于没有更合适的名称，我称之为一致分类。要了解什么是一致分类以及了解本文要讨论的问题，最好的方法是查看图 1 中的演示程序。

一致分类实战
图 1 一致分类实战

演示程序的目的是构建一个模型，该模型可以根据美国众议院的议员在 16 次法律草案中的投票记录预测其政治党派（是民主党还是共和党）。原始数据集包含 100 个项，每个项对应一个议员，共有 17 个字段。每个项的前 16 个字段为选票，其中，字符“y”表示赞成票，字符“n”表示否决票。每个项的最后一个字段是议员的实际政治党派。例如，前两个数据项为：

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

演示数据是一个名为“国会投票记录数据集”的已知基准集的子集。完整的基准数据集共包含 435 个项，部分项的选票值为“?”，表示选票未知或为弃权票。演示子集包含完整集的前 100 个项，其中不含“?”选票。此外，源数据集的第一列为政治党派，我将党派移至最后一列，这样更方便编程。

尽管无需了解 16 次投票对应的法律草案，但以下 16 个词组足以表达每个草案的主题：新生儿畸形、水利工程、通过预算、就医费用、萨尔瓦多、学校宗教、反卫星、尼加拉瓜反政府游击队、MX 导弹、移民法案、合成燃料削减、教育支出、超级基金控告、打击犯罪法案、免税、南非。

演示程序将 100 个项的数据集一分为二：其中一个含 80 个项的集用于训练模型，另一个含 20 个项的数据集用于评估生成的模型的准确性。一致分类模型包含一组简单的规则，例如“如果议员对法案 0 投票‘y’，对法案 3 投票‘n’，对法案 15 投票‘y’，则该议员为共和党。”在演示中，将每个简单规则中的布尔条件的数量设置为 5，规则总数设置为 500。此外，要求每个简单规则针对规则适用的训练数据项的精确度至少为 90%。

训练过程在后台生成了 500 个简单规则。创建了模型后，演示程序将模型规则应用到训练数据，并得到 93.75% 的精确度。然后，将模型应用到包含 20 个项的测试集，结果得到 84.21% 的精确度，其中含 16 次正确预测、3 次不正确预测，以及模型中的 500 个规则均不适用的一个数据项。

本文假设您至少具备一定的编程技术，并对机器学习分类已有基本的了解。本演示使用 C# 编程，但您也应该能够顺利地将代码重构到其他语言（如 Visual Basic .NET 或 Python）。演示代码太长，无法完全显示，但本文随附的下载部分中提供完整的源代码：msdn.microsoft.com/magazine/msdnmag1114。

程序的整体结构

图 2 显示了演示程序的整体结构（为节省空间，删除了部分 WriteLine 语句，并进行了一些较小的修改）。为创建此演示，我启动了 Visual Studio 并创建了一个新的 C# 控制台应用程序，并命名为 Consensus­Classification。该演示对 Microsoft .NET Framework 的依赖程度并不明显，因此，任何相对较新的 Visual Studio 版本都可以正常运行。加载模板生成的代码后，我在解决方案资源管理器窗口中将文件 Program.cs 重命名为更具描述性的 ConsensusProgram.cs，Visual Studio 将自动重命名 Program 类。

图 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 方法中。演示包含两种静态 Helper 方法，MakeTrainTest 和 ShowData。分类逻辑包含在名为 ConsensusClassifier 的单个程序定义的类中。分类器提供了六种公共方法：单个构造函数 RuleCount（模型中简单规则的实际数量）、ComputeOutput（在创建模型后进行预测）、Train（创建模型），以及一个重载 Accuracy（计算正确预测的百分数）。

在 Main 方法中，演示程序将包含 100 个项的源数据硬编码为“array-of-arrays-style”字符串矩阵：

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

在非演示的情况下，您的数据可能会存在于一个文本文件中，并且您已使用 Helper 方法将数据加载到内存中。源数据分为训练集和测试集，如下所示：

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 还会返回正确的、不正确的和不适用（即没有一个模型规则适用于特定数据项）的数据项的数量。例如，假定将 number-of-conditions 参数设置为 3，其中一个数据项为 vote0 = ‘y’、vote1 = ‘y’、vote2 = ‘n’。即使使用 500 条规则，也可能没有一条规则会考虑使用此投票组合。或者，可以对 Accuracy 方法进行设计，以便不适用的数据项不存在。一个常见方法是添加一条最终规则，类似于：“……否则议员为民主党”，其中“民主党”为默认值，通常为最常用的因变量值。

演示程序没有使用模型来预测议员的政治党派。对于为草案 [0] 到 [7] 投票“yes”，为草案 [8] 到 [15] 投票“no”的议员，其政治党派的预测过程如下所示：

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，其中 0 表示“共和党”，1 表示“民主党”。

一致算法

一致分类器的核心是一个规则集。要解决的两个主要的问题是，决定如何表示规则，以及生成规则。演示程序将规则表示为一个整数数组。一致的示例对方案进行了最好的说明，如图 3 中所示。假定将每条规则中的布尔条件数量设置为 3。单个规则表示为包含 7 个单元格的数组。如果此数组具有值 { 3, 0, 8, 1, 15, 1, 0 }，则规则对应“如果选票 [3] 为 0，选票 [8] 为 1，选票 [15] 为 1，则党派为 0”。规则集是规则的泛型 List 集合。

一致分类数据结构
图 3 一致分类数据结构

0 和 1 所表达的意义因列/选票而异。演示程序构建了一个 Dictionary 集合的数组，与列/选票一一对应。在训练数据的各列中从 0 开始的整数 ID 遇到每个字符串值后，整数 ID 将分配给字符串值。例如，在训练数据的选票 [0] 的第 [0] 列中，首先遇到“n”，将其分配给 0，然后遇到 “y”，将其分配给 1。但是在第 [1] 列中，首先遇到 “y”，将其分配给 0，然后遇到“n”，将其分配给 1。

同样地，在训练数据的第 [16] 列中，最后一列包含因变量值“民主党”和“共和党”，首先遇到“共和党”，因此为 0，“民主党”为 1。字符串到整数的映射信息存储在名为 stringToInt 的类成员数组中，如图 3 中所示。因此，表达式 stringToInt[1]["y"] 将针对选票 [1] 的 yes 选票返回从 0 开始的索引值，对演示训练数据而言，返回 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，随机选择三个列：[1]、[2] 和 [15]。在训练数据中，这些列具有值“y,”、“n,”和“y”，因变量具有值“共和党”。在 array-of-­Dictionary 集合中查找的列值为 0、0 和 0。因此，候选规则是包含值 { 1, 0, 2, 0, 15, 0, 0 } 的整数数组，可以解释为“如果第 1 列为 0，第 2 列为 0，第 15 列为 0，则党派为 0”。

接下来，扫描训练数据中的 80 个项，查看候选规则是否满足最小精确度条件。请注意，至少一个（用于创建规则的）数据项的候选规则是正确的。然而，候选规则无需适用于所有训练项。例如，数据项 [0] 生成的候选规则 { 1, 0, 2, 0, 15, 0, 0 } 不适用于数据项 [1]，这是由于第 [2] 列的值为 1，而不是所要求的 0。

创建了规则集后，给定输入数据集的输出由被描述为计算选票的内容来确定。对于每个数据项，会分析规则集中的所有规则。假定和演示一样，规则集包含 500 条规则。并假定对于某个数据项，220 条规则预测政治党派为共和党，250 条规则预测为民主党，30 条规则不适用。分类器将预测与该数据关联的议员为“民主党”。也就是说，输出是从规则集预测的一致性结果。

几点注释

本文介绍一致分类技术的动机来自我在不久前所做的一项研究项目。具体说来，我尝试根据一些变量（例如用户地区、用户年龄组别等）预测即时消息用户的性别（男、女）。我尝试过能想到的使用现有机器学习工具的所有标准分类方法，但没有一种方法可以生成有效的预测模型，尽管我的直觉是数据包含的信息足以产生一个信号。

我注意到，使用 Naive Bayes 分类好像是尝试过的最好的方法。Naive Bayes 假定每个预测器变量从数学角度来看是独立的。即便此假设通常不正确，但 Naive Bayes 有时也会达到不错的效果。我的问题是，几乎可以肯定预测器变量在某种程度上是相关的，但我不能确定哪些变量相关。因此，我决定使用众多机器学习技术中的一部分来创建本文中介绍的方法。最终，我能够创建一个预测模型，而这个模型明显比任何标准技术模型要精确得多。

演示问题是一个二进制分类问题，因为因变量可以是“民主党”或“共和党”。另外，所有预测器都是二进制分类变量，因为他们可以是“是”，也可以是“否”。一致分类可以处理多项分类问题（例如，“民主党”、“共和党”、“无党派”），还可以处理包含两个值以上（例如，“是”、“否”、“缺席”、“弃权”）的分类预测器。在我的实验中，当遇到预测器变量为数字（例如年龄）且被划分类别（例如，青年、中年和老年）的情况时，一致分类处理此类问题的有效性尚不明确。

组合多条规则或多个模型以生成分类结果在机器学习词汇中通常称为“集成学习”。生成多条简单规则的想法已用于机器学习技术，有时将其称为“增强技术”。声明一下，我的“测试运行”专栏中所介绍的机器学习技术通常都有着坚实的研究基础。本文是一个特例。本文中介绍的技术没有经过专门谨慎的研究。我的一些研究学术的同事对于我贸然使用自定义、非传统的机器学习技术颇有微词，我对此的回复略带嘲讽：我通常更关心结果，而不是为了建立优雅的数学定理。依我看来，使用标准的机器学习技术首当其冲是解决机器学习问题的最好方法，但当传统技术无法解决问题时，创建一个自定义解决方案有时会带来意想不到的效果。

James McCaffrey 博士 任职于华盛顿州雷德蒙德市的 Microsoft Research。他长期从事多个 Microsoft 产品（包括 Internet Explorer 和 Bing）的研发工作。可通过 jammc@microsoft.com 与他联系。

衷心感谢以下 Microsoft Research 技术专家对本文的审阅：Marciano Moreno Diaz Covarrubias、Delbert Murphy、David Raskino 以及 Alisson Sol