CLR
使用自适应增强进行分类和预测
分类是一种计算机学习方法，它使用训练数据生成模型（通常是单个复杂规则或数学等式），将数据项分配给几个不同类别中的一个。 然后，可使用模型对类别未知的新数据项进行预测。 示例包括，根据各种医疗检查数据预测患者是否患有癌症（是、否），根据申请者的财务历史记录预测贷款申请的风险类别（低、中、高）。
有许多不同的分类算法和方法，包括朴素贝叶斯、神经网络和逻辑回归。 本文将介绍一种有趣的方法，这种方法称为自适应增强分类，与试图确定单个复杂预测规则的方法不同，它使用训练数据生成大量十分简单的粗略经验规则。 然后，计算每个经验规则的权重。 对新输入进行预测的过程包括：组合这些经验规则，考虑每个简单规则的权重，获得一致的结果。 “增强”一词源于这样一个事实：通过组合简单规则可以增强（提高）这些规则的预测质量。
自适应增强是一种元启发式算法。 也就是说，自适应增强是一组可用于创建特定分类算法的准则。 自适应增强算法有许多变体，并且有许多现有的独立工具可实现某种形式的自适应增强，那么为什么还要不厌其烦地从头开始编写自适应增强分类的代码呢？ 现有的自适应增强分类工具可能很难或无法自定义，可能难以集成到软件系统中，并且可能会导致版权或知识产权问题。
具体示例是了解什么是自适应增强的最佳途径。 请看一下图 1。 演示程序需要解决的最终问题是，预测西雅图球队在即将到来的比赛中主场迎战一支底特律球队的输赢，打赌的一致结果（分差）是西雅图有微弱优势（小）。 图 1 上部显示 10 个结果已知的假设训练数据项。 第一个训练元组 (Detroit, Home, Large, Win) 表示在与底特律球队进行的上次比赛中，西雅图球队在主场比赛，分差为大，西雅图球队在比赛中获胜。
.png)
图 1 自适应增强分类和预测
演示程序的下一部分显示 10 个训练数据项从字符串数据转换为从零开始的整数形式，以便更有效地进行处理，然后以矩阵形式存储在计算机内存中。 例如，(Detroit, Home, Large, Win) 存储为 (3, 0, 2, 1)。 请注意，本例中预测结果只有两个值，即赢和输。 这称为二进制分类问题。 自适应增强也可用在相关变量有三个或更多值的情况（多项分类）。 大部分二进制分类方法将相关变量编码为使用 (0, 1) 机制进行预测，但自适应增强几乎总是使用 (-1, +1) 机制，因为这种编码方式可略微简化某些算法实现过程。 请注意，所有独立变量预测器值都是分类值（“Home”、“Medium”等）而非数值。 当训练数据有数值时，也可使用自适应增强，稍后将进行介绍。
图 1 的第三部分显示从训练数据生成了八个经验规则。 在自适应增强术语中，经验规则通常称为弱学习器或弱分类器。 第一个弱学习器是“IF Opponent IS Buffalo THEN Result IS Win”，以用户友好的形式表示，原始误差率为 0.00。 第二个弱学习器为“IF Opponent IS Chicago THEN Result IS Lose”，它更具说明性，误差率为 0.33。 此弱学习器从何而来？ 如果查看一下训练数据，可以发现有三次对手为芝加哥。 在这些训练实例中，有两次的结果为输，因此该弱学习器的正确率为三分之二 (0.67)，误差率为三分之一 (0.33)。
请注意，并非所有训练项预测器值都会生成弱学习器；当对手为亚特兰大时，不存在任何规则。 因为对手为亚特兰大的培训元组有两个，其中一个的结果为赢，另一个的结果为输，所以该学习器的误差率为 0.50，这并不能提供任何有用的信息。 本文中演示的自适应增强分类版本假定所有弱学习器的原始误差率均小于 0.50。
图 1 的下一部分说明自适应增强算法如何在后台处理这些弱学习器以找到每个学习器的权重。 这些权重用于衡量每个弱分类器的重要性，它们在自适应增强术语中称为 alpha 值。 确定 alpha 值是自适应增强的关键部分。 弱学习器组及其 alpha 权重构成了分类模型。
演示程序的最后一部分介绍用于针对西雅图球队进行预测的分类模型，对手为底特律球队，场地为主场，分差为小。 如果看一下所生成的弱学习器组，可以看到有三个学习器适用： [2] IF Opponent IS Detroit THEN Result IS Win (+1)、[3] IF Field IS Home THEN Result IS Win (+1) 和 [5] IF Spread IS Small THEN Result IS Lose (-1)。 为弱学习器 2、3 和 5 计算出的 alpha 值分别为 0.63、3.15 和 4.49。 由此得出，一致预测 = (0.63)(+1) + (3.15)(+1) + (4.49)(-1) = -0.72（经过四舍五入），因为值为负，所以表示结果为输。 请注意，即使三个弱学习器中有两个（2 和 3）预测赢，但弱学习器 5 的较大 alpha 值超过了这两个赢预测，因而得到的总体预测为输。
在接下来的几部分中，我将详细说明演示程序的工作原理，以便你可以向 .NET 系统或应用程序添加预测功能。 本文假定你具备 C 系列语言高级编程技能，对自适应增强分类一无所知。 我使用 C# 编写演示程序代码，但是这些说明应为你提供足够信息，使你可以将该代码重构为其他语言（如 Visual Basic .NET 或 Python 等）。 演示程序的代码太长，无法在本文中完全列出， archive.msdn.microsoft.com/mag201304AdaptiveBoost 提供了完整的源代码。
自适应增强算法
自适应增强分类的核心是一个例程，该例程检查每个弱学习器并向其分配一个 alpha 权重。 这种算法十分复杂，最好通过一个具体示例加以说明。 假设有 10 个训练元组和 8 个弱学习器，如图 1 所示。 每个训练元组都分配有一个权重，权重在自适应增强文献资料中通常称为 D。 D 权重的总和为 1.0，这使 D 值成为一种分布。 最初，所有训练数据项都分配有相同的 D 权重；在本例中为 0.10，因为共有 10 个数据项：
[0] (D = 0.10) Detroit Home Large Win [1] (D = 0.10) Detroit Away Medium Win [2] (D = 0.10) Buffalo Home Small Win [3] (D = 0.10) Buffalo Home Medium Win [4] (D = 0.10) Atlanta Away Large Win [5] (D = 0.10) Chicago Home Medium Win [6] (D = 0.10) Chicago Away Small Lose [7] (D = 0.10) Chicago Home Small Lose [8] (D = 0.10) Atlanta Away Medium Lose [9] (D = 0.10) Detroit Away Large Lose
每个学习器都有一个 epsilon 值和一个 alpha 值。 epsilon 值是用于计算 alpha 值的加权误差率。 最初，所有学习器都有未知 alpha 值（假设 a = 0.00）和未知 epsilon 值（假设 e = -1.0）：
[0] (a = 0.00) (e = -1.0) IF Opponent IS Buffalo THEN Result IS Win [1] (a = 0.00) (e = -1.0) IF Opponent IS Chicago THEN Result IS Lose [2] (a = 0.00) (e = -1.0) IF Opponent IS Detroit THEN Result IS Win [3] (a = 0.00) (e = -1.0) IF Field IS Home THEN Result IS Win [4] (a = 0.00) (e = -1.0) IF Field IS Away THEN Result IS Lose [5] (a = 0.00) (e = -1.0) IF Spread IS Small THEN Result IS Lose [6] (a = 0.00) (e = -1.0) IF Spread IS Medium THEN Result IS Win [7] (a = 0.00) (e = -1.0) IF Spread IS Large THEN Result IS Win
在伪代码中，找到每个学习器的 alpha 权重的算法如下：
set t=0 while not done loop update all learners' epsilons (weighted errors) find best (smallest epsilon) unused learner compute and save the alpha of best learner using its epsilon update the D weights for each training item using the best learner normalize the D weights so they sum to 1.0 ++t end loop
主处理循环在以下情况下中止：所有弱学习器均已处理并分配有 alpha 权重；循环计数器变量超过某个最大值；最佳未用弱学习器的加权误差率 epsilon 达到某个值（如 0.45 或 0.49），这表示没有剩下任何相对较好的未用学习器可供处理。
循环内的第一步是更新所有 epsilon。 epsilon 值是错误分类的训练元组的 D 权重总和。 对于学习器 [0] (IF Opponent IS Buffalo THEN Result IS Win)，有两个适用的训练元组 [2] 和 [3]，该规则在这两个实例中是正确的，因此 epsilon 为 0.00。 对于学习器 [1] (IF Opponent IS Chicago THEN Result IS Lose)，有三个适用的训练元组 [5]、[6] 和 [7]。 其中，元组 [5] 不正确，因此 epsilon 只是元组 [5] 的 D 权重 = 0.10。
虽然并非显而易见，但是如果仔细看一下计算 epsilon 的方法，你将发现 epsilon 值始终介于 0.0 与 0.5 之间。 在进行所有更新后，学习器的 epsilon 如下：
[0] (a = 0.00) (e = 0.00) IF Opponent IS Buffalo THEN Result IS Win [1] (a = 0.00) (e = 0.10) IF Opponent IS Chicago THEN Result IS Lose [2] (a = 0.00) (e = 0.10) IF Opponent IS Detroit THEN Result IS Win [3] (a = 0.00) (e = 0.10) IF Field IS Home THEN Result IS Win [4] (a = 0.00) (e = 0.20) IF Field IS Away THEN Result IS Lose [5] (a = 0.00) (e = 0.10) IF Spread IS Small THEN Result IS Lose [6] (a = 0.00) (e = 0.10) IF Spread IS Medium THEN Result IS Win [7] (a = 0.00) (e = 0.10) IF Spread IS Large THEN Result IS Win
此时选择了最佳学习器。 它就是学习器 [0]，因为其 epsilon 最小，为 0.00。 关联 alpha 的计算方法如下：
alpha = 0.5 * log((1.0 - epsilon) / epsilon)
从自适应增强理论上来说，这实际上是一个奇妙的等式。 其中，log 是自然（以 e 为底数）对数。 回想一下，alpha 值是决定学习器重要性的权重。 上述等式旨在使较小的 epsilon（学习器误差）值产生较大的 alpha（学习器重要性）值。
在这一特定情况下，如果 epsilon 为 0，会产生问题，因此会出现除以 0 错误。 为避免这一问题，演示程序任意将任何值为 0 的 epsilon 转换为 0.000001。 因此，学习器 [0] 的 alpha 计算为 0.5 * log(0.999999 / 0.000001) = 6.91，该值分配给学习器 [0]，并且学习器 [0] 标记为已完成。
算法循环中的下一步是根据刚刚计算出的最佳学习器更新 D 训练元组权重。 基本思路是，增加被最佳学习器错误分类的训练元组的 D 权重，减少被最佳学习器正确分类的训练元组的 D 权重。 乍一看，D 更新等式有些复杂：
D(new) = D(old) * exp(-alpha * actualY * predictedY)
最佳学习器是学习器 [0] (IF Opponent IS Buffalo THEN Result IS Win)，其 alpha 为 6.91。 在 10 个训练元组中，学习器 [0] 适用于元组 [2] 和 [3]，因此将更新这些 D 值。 对于训练元组 [2]：
D(new) = 0.10 * exp(-6.91 * (+1) * (+1)) = 0.10 * exp(-6.91) = 0.0000997758
训练元组 [3] 的新 D 值的计算方法和结果与元组 [2] 相同。
在本例中，得到了一个很小的新 D 权重，因为这两个训练元组是被最佳学习器正确分类的。 请注意，如果实际 Y 值与预测 Y 值相同（同时为 -1 或同时为 +1），则相乘时会得到 +1，并且指数参数为负数（因为 -alpha 始终为负），这会使产生的结果小于 1.0。 但是，如果实际 Y 值和预测 Y 值不同，其乘积为 -1，并且指数参数为正，这会产生大于 1.0 的数字（可能很大）。 这一 D 更新方法就是为何自适应增强分类通常对相关变量值使用 -1 和 +1 而非 0 和 +1 的原因所在。
此时，初始近似 D 值（经过四舍五入）如下：
[0] (D = 0.1000) Detroit Home Large Win [1] (D = 0.1000) Detroit Away Medium Win [2] (D = 0.0001) Buffalo Home Small Win [3] (D = 0.0001) Buffalo Home Medium Win [4] (D = 0.1000) Atlanta Away Large Win [5] (D = 0.1000) Chicago Home Medium Win [6] (D = 0.1000) Chicago Away Small Lose [7] (D = 0.1000) Chicago Home Small Lose [8] (D = 0.1000) Atlanta Away Medium Lose [9] (D = 0.1000) Detroit Away Large Lose
主算法循环中的下一步是对 D 值进行规范化，使其总和为 1.0，具体方法是将每个初始 D 值除以其总和。 10 个 D 值的总和约为 0.8002，因此训练元组 [0] 的规范化 D 值约为 0.1000/0.8002 = 0.1249。 最终更新后的 D 权重如下：
[0] (D = 0.1249) Detroit Home Large Win [1] (D = 0.1249) Detroit Away Medium Win [2] (D = 0.0001) Buffalo Home Small Win [3] (D = 0.0001) Buffalo Home Medium Win [4] (D = 0.1249) Atlanta Away Large Win [5] (D = 0.1249) Chicago Home Medium Win [6] (D = 0.1249) Chicago Away Small Lose [7] (D = 0.1249) Chicago Home Small Lose [8] (D = 0.1249) Atlanta Away Medium Lose [9] (D = 0.1249) Detroit Away Large Lose
这里的思路是，我们希望算法现在以 [2] 和 [3] 之外的训练元组为重点，因为学习器 [0] 已考虑了这两个元组。 此时，算法跳回循环顶部，根据新计算的 D 权重更新所有学习器的 epsilon 值，确定最佳未用学习器（学习器 [5]），计算最佳学习器的 alpha 值 (4.49)，更新适用训练元组（[2]、[6] 和 [7]）的 D 值并计算所有训练元组的规范化 D 值。
在本例中，该过程会一直执行，直到计算出所有八个弱学习器的 alpha 值；但通常来说，并非所有弱学习器都一定会被视为良好学习器并分配有 alpha 值。
程序的整体结构
图 1 中所示的演示程序是单个 C# 控制台应用程序。 我使用的是 Visual Studio 2010，但是支持 Microsoft .NET Framework 2.0 或更高版本的任何 Visual Studio 版本都适用。 我创建了一个名为 AdaptiveBoosting 的新项目，然后在解决方案资源管理器窗口中将 Program.cs 重命名为更具描述性的 AdaptiveBoostingProgram.cs，这样也会自动重命名类 Program。 除了对 System 和 Collections.Generic 命名空间的引用以外，我删除了源代码顶部由模板生成的所有 using 语句。 图 2 列出了 Main 方法，其中删除了部分 WriteLine 语句，进行了一些其他细微编辑工作，包含一个重要的程序定义类来定义弱学习器对象。
图 2 程序的整体结构
using System; using System.Collections.Generic; namespace AdaptiveBoosting { class Program { static void Main(string[] args) { try { Console.WriteLine("\nBegin adaptive boosting classification demo\n"); string[] features = new string[] { "Opponent", "Field", "Spread", "Result" }; string[][] values = new string[4][]; values[0] = new string[] { "Atlanta", "Buffalo", "Chicago", "Detroit" }; // opponent values[1] = new string[] { "Home", "Away" }; // Field values[2] = new string[] { "Small ", "Medium", "Large " }; // Note: Spaces added values[3] = new string[] { "Lose", "Win" }; // The dependent/predicted variable string[][] rawTrain = new string[10][]; rawTrain[0] = new string[] { "Detroit", "Home", "Large ", "Win" }; rawTrain[1] = new string[] { "Detroit", "Away", "Medium", "Win" }; rawTrain[2] = new string[] { "Buffalo", "Home", "Small ", "Win" }; rawTrain[3] = new string[] { "Buffalo", "Home", "Medium", "Win" }; rawTrain[4] = new string[] { "Atlanta", "Away", "Large ", "Win" }; rawTrain[5] = new string[] { "Chicago", "Home", "Medium", "Win" }; rawTrain[6] = new string[] { "Chicago", "Away", "Small ", "Lose" }; rawTrain[7] = new string[] { "Chicago", "Home", "Small ", "Lose" }; rawTrain[8] = new string[] { "Atlanta", "Away", "Medium", "Lose" }; rawTrain[9] = new string[] { "Detroit", "Away", "Large ", "Lose" }; Console.WriteLine("Raw (string) training data for team seattle:\n"); Console.WriteLine("Opponent Field Spread Result"); Console.WriteLine("==============================="); ShowMatrix(rawTrain); Console.WriteLine("\nConverting and storing training data"); int[][] train = RawTrainToInt(rawTrain, values); Console.WriteLine("Training data in int form:\n"); ShowMatrix(train, true); Console.WriteLine( "\nCreating weak categorical stump learners from training data"); List<Learner> learners = MakeLearners(values, train); Console.WriteLine("Completed.
Weak learners are:\n"); for (int i = 0; i < learners.Count; ++i) Console.WriteLine("[" + i + "] " + Description(learners[i], features, values)); Console.WriteLine("\nInitializing list of best learner indexes"); List<int> bestLearners = new List<int>(); // Indexes of good weak learners Console.WriteLine( "\nUsing adaptive boosting to find best learners and alphas"); MakeModel(train, values, learners, bestLearners); Console.WriteLine("\nModel completed"); int numGood = bestLearners.Count; Console.Write("Algorithm found " + numGood + " good learners "); Console.WriteLine("and associated alpha values"); Console.WriteLine("\nThe good learners and their alpha value are:"); for (int i = 0; i < bestLearners.Count; ++i) { int lrn = bestLearners[i]; Console.Write("[" + lrn + "] " + learners[lrn].alpha.ToString("F2") + " "); } Console.Write("\nPredicting outcome when Opponent = Detroit, "); Console.WriteLine("Field = Home, Spread = Small\n"); int[] unknownTuple = new int[] { 3, 0, 0 }; // Detroit, Home, Small int Y = Classify(unknownTuple, learners, bestLearners); Console.Write("Predicted Y = " + Y + " => "); Console.WriteLine("seattle will " + YValueToString(Y, values)); Console.WriteLine("\nEnd\n"); } catch (Exception ex) { Console.WriteLine(ex.Message); } } // Main // (Many) static methods here } // Class Program public class Learner // Weak learner { // Definition code here } } // ns
Main 方法首先为特征“Opponent”、“Field”、“Spread”和“Result”设置了硬编码字符串。 然后，Main 中的代码为每个特征设置了硬编码值： “Atlanta”、“Buffalo”、“Chicago”、“Detroit”、“Home”、“Away”、“Small”、“Medium”、“Large”、“Lose”和“Win”。为了使输出井井有条，我运用了一点变化，在“Small”和“Large”末尾插入一个空格。
为了简单起见，训练数据也硬编码到演示程序中。 在许多情况下，训练数据将存储在一个文本文件或 SQL 表中。 在这些情况下，你可能希望考虑以编程方式扫描训练数据以确定特征名称（可能来自文本文件标题行或 SQL 表列名称）和特征值。
方法 RawTrainToInt 将字符串形式的训练数据转换为从零开始的整数，并将这些整数存储到一个名为 train 的 int[][] 矩阵中。 RawTrainToInt 调用一个名为 ValueToInt 的帮助程序。 train 矩阵的相关变量值 (Result) 存储在最后一列中。 你可能希望将相关变量值单独存储在一个列数组中。 在训练数据集很大的情况下，可能无法在计算机内存中存储整个训练数据集。 这种情况下，必须通过外部数据存储而不是内部矩阵进行流式处理。
演示程序使用方法 MakeLearners 和一个程序定义的类 Learner 确定弱学习器。 本文下一部分将详细介绍该方法和该类。 在创建弱学习器后，演示程序调用方法 MakeModel。 如上一部分所示，MakeModel 是自适应增强算法的核心。 最终的结果是一个名为 bestLearners 的排序列表，其中包含分配有 alpha 值的学习器的索引。
Main 方法最后预测具有以下一组输入的 Seattle 的结果：Opponent 为“Detroit”、Field 为“Home”且 Spread 为“Small”。 在本例中，Classify 的返回值为 -0.72，这解释为“Lose”。
创建弱学习器
特定自适应增强算法的实现在某种程度上取决于弱学习器的特定定义。 程序定义的类 Learner 有六个字段：
public int feature; public int value; public int predicted; public double error; public double epsilon; public double alpha;
为了简单起见，我使用公共作用域声明了所有六个字段。 feature 字段存放一个整数，指示哪个独立变量是学习器的关键。 例如，如果 feature 为 0，则弱学习器基于 opponent 的值。 value 字段存放一个整数，指示 feature 的值。 例如，如果 value 为 3，则弱学习器基于条件“opponent is Detroit”。 predicted 字段为 -1 或 +1，具体取决于 feature 值的实际类别是 Lose 还是 Win。
error 字段是 double 类型，是与训练数据的弱学习器关联的原始误差率。 例如，如果弱学习器的 feature = 0、value = 3 且 predicted = +1（表示如果 Opponent 为 Detroit 时，则结果为 Win），那么图 1 中训练数据的原始误差率为 0.33，因为有三分之一的训练数据项被错误预测。 请注意，原始误差将同等对待每个训练项。 结果证明，本文中所演示的自适应增强算法实际上并不需要原始误差字段，因此可忽略该字段，但我认为此信息很有用。
epsilon 字段是加权误差项。 弱学习器的 epsilon 是考虑分配给每个训练项的内部 D 权重的误差项。 自适应增强算法使用 epsilon 值计算 alpha 权重。 总之，有两组权重用在自适应增强分类中。 alpha 权重为每个弱学习器分配重要性，并用于确定总体预测。 epsilon 误差是与弱学习器关联的内部误差，用于计算 alpha 权重。 每个训练元组都有一个内部权重（在自适应增强文献资料中称为 D），用于计算 epsilon 误差。
在伪代码中，方法 MakeLearners 的工作原理如下所示：
initialize an empty result list of learners for each feature loop for each value of curr feature loop scan training data to determine most likely -1, +1 result if no most likely result, skip curr value create a new learner object with feature, value, predicted add learner object to result list end each value end each feature for each learner in result list for each training data item if learner isn't applicable to data, skip curr data item compute raw error rate store raw error into learner end each training data item end each learner
这里的思路是，每个 feature 值（如“Atlanta”(opponent) 或“Medium”(point spread)）都将根据训练数据生成一个弱学习器规则，除非该值未显示在训练数据（例如“New York”的对手）中或者因与该值关联的输赢次数相同（例如，在演示数据中 opponent 为“Atlanta”时，输赢各一次）而未生成最可能的结果。
总结
对本文介绍的算法的一项重要变化是处理具有数值的数据。 例如，假设 point spread 特征的值是数值（如 1.5、3.0 和 9.5），而不是分类值“Small”、“Medium”和“Large”。 与其他分类方法相比，自适应增强分类的一个主要优势在于，自适应增强可以方便地直接处理分类和数值数据。 你可以创建一个一目了然的专用学习器类，类似于“if Spread is less than or equal to 5.5 then Result is Lose”；也可以创建一个比较复杂的学习器，使用以下代码行：“if Spread is between 4.0 and 6.0 then Result is Win”。
在我看来，如果要预测的相关变量只有两个可能的值，最合适使用自适应增强分类。 不过，高级自适应增强方法也可以处理多维分类。 如果要对此或一般自适应增强的基础理论进行深入研究，建议搜索一下研究人员 R. Schapire 和 Y. Freund 所著的文章。
计算机学习研究表明，没有任何单一的最佳数据分类/预测方法。 但是自适应增强是一种非常强大的方法，它可以形成向 .NET 软件系统添加预测功能的基础。
Scripto James McCaffrey 供职于 Volt Information Sciences Inc.，负责管理华盛顿地区雷蒙德市沃什湾 Microsoft 总部园区的软件工程师技术培训。 他参与过多项 Microsoft 产品的研发工作，其中包括 Internet Explorer 和 MSN Search。 他是《.NET Test Automation Recipes》（Apress，2006）的作者，你可以通过以下电子邮箱地址与他联系：jammc@microsoft.com。
衷心感谢以下技术专家对本文的审阅： Darren Gehring (Microsoft)