如果森林中的一棵树倒下了，但是没有人听见，那么它是否发出了声音？

        规则是一种将知识模块用让人易于理解的方式结合起来的方法。如果“客户很富有”，那么“他将会购买我的产品”。如果“体温超过 37 摄氏度”，那么“这个人生病了”。决策规则普遍应用于医疗、银行和保险领域，以及与客户打交道的特定流程中。

        在一条规则中，人们区分前件或前提（一系列测试）和后件或结论。结论是对应输入并使得前提成立的输出类别；如果类别不能 100% 确定，就给出这些类别的概率分布。通常，这些前提都是用“且”连接起来的，也就是说，如果我们要“发射”这条规则，即得到结论，那么所有测试都必须通过。如果“距离小于 2 英里”且“晴天”，那么“步行”。一条测试可以针对类型变量的值（“晴天”），或者数值变量简单运算的结果（“距离小于 2 英里”）。如果想要让人理解，计算就必须简单。一个实用的改进是将前提为假时的分类也加入到同一个语句中。如果“距离小于 3 公里”且“没有私家车”，那么“步行”，否则“坐公交车”。

        提取知识模块形成一个简单规则的集合是诱人的。但是手动设计和维护规则是昂贵且困难的。当规则集变大时，复杂性就会显现，就像图 1 中的规则会导致不同的甚至矛盾的分类。在这些情况下，分类可能与不同规则在数据上进行测试的排列顺序有关。从数据中自动提取不矛盾的规则的方法是很宝贵的。

        相比处理带很多测试的非常长的前提，将规则分解成一串简单的问题更有价值。在贪心法中，那些信息量最大的问题最好放在这一序列的前面，这样可以给问题加上层次结构，从信息量最大的问题到信息量最小的问题。如上这些动机很自然的让我们考虑到决策树，它是决策规则的有组织的分层排列，并且没有矛盾（见图2）。

图 1 一套非结构化规则会导致矛盾的分类 图 2 决策树 图 3 同一棵树中达到分类的一种情况

        决策树，以及同一棵树中达到分类的一种情况（图3）。抵达拆分节点的数据点根据测试函数的结果被发送到其左子节点或右子节点。

        决策树在机器学习（ ML ）诞生之初就非常普及了。现在，确实只有小而浅的树能够被人们“理解”，但是近年来由于计算和存储能力的极大提升，决策树的普及度越来越广了。很多树（在某些情况下可达到上百棵）可以组合使用，称为决策森林，来得到具有健壮性的分类器。当考虑森林时，关心人们是否能理解这一问题被移至幕后，务实地寻找没有过度训练风险的、具有健壮性的高性能表现成为台前的主角。

1、构造决策树

        决策树是以层次的方式组织起来的一个问题集，并且用一棵树的图形来表示。由于历史的原因，机器学习中的树，如同所有在计算机科学领域中的树那样，常常把根画在上方 —— 如果你在北半球，那就想象澳大利亚的那些树。对于一件给定的事物，决策树通过连续地提出关于其已知属性的问题来估计它的一个未知属性。下一个问题问什么取决于前一个问题的答案，如果用图形来表示，这一事物对应于这棵树中的一条路径，如图 3 的粗线条所显示的。决策则根据这条路径的终端节点来做出。终端节点称作叶子。决策树可以被看作将复杂问题分解为简单问题集的一种方法，分解过程在这个问题已足够简单，即已到达叶子节点并找到已有的答案时结束。

        一个从已标记的实例来构造决策树的基本方法是按照贪心法来进行的：在层次结构中，信息量越大的问题就越靠前。考虑一下初始的被标记的实例集。一个有两个可能输出（“是”或“否”）的问题将这一实例集分为两个子集，其中一个子集包括答案为“是”的实例，另一个子集包括答案为“否”的实例。初始的实例集是混乱的，包含不同类的实例。当问完一串问题，从根到了叶子时，叶子中余下的集合就应该几乎是“纯”的了，也就是只包含同一类的实例。这一类别也就是所有到达这片叶子的实例所对应的输出。

        我们需要从初始的混乱的集合过渡到最终一系列（几乎）纯的集合。一个瞄准这一目标的贪心法就是从“信息量最大的”问题开始。这会把初始的集合划分为两个子集，分别对应答案“是”或“否”，也是初始根节点的子节点（见图 4）。贪心法将以尽可能接近最终目标这一原则迈出第一步。在贪心法中，第一个问题的设计要使得这两个子集尽可能纯净。第一次划分完成之后，以递归的方式（见图 5），继续对左右两个子集使用同样的方法，设计合适的问题，如此重复，直到剩下的集合足够纯净，递归停止。完全的决策树是由一个从上到下的过程导出的，这一过程通过在创造的子集中实例的相对比例来引导。

图 4 纯化集（两个类的实例）: 问题 2 产生的子节点的实例子集更纯净 图 5 树构建中的递归步骤：经过问题 2 初步纯化后，将同样的方法应用在左边和右边的实例子集上。在这个例子中，问题 3 就足以完全净化这些子集。不需要在纯子集上执行额外的递归调用

        决策树的两个最主要的组成部分，一是纯度的定量度量，二是每个节点问的问题的类型。我们都同意纯度最大值是在子集中只有一个类别的实例时取到，而不同的度量负责测量那些不只一个类别的情况。其他的组成部分与终止条件有关：记住我们的目标是泛化，因此我们不希望构造一棵非常大的树，而每片叶子只有一两个实例。某些情况下，我们允许在子集尚未达到十分纯净时停止训练，并且当一些实例到达某个给定的叶子节点时，输出一个概率值。

在下面的描述中，假设所有涉及的变量都是类别变量（即名称，像上面例子中的“欧洲人”）。还有两种广泛使用的子集纯度度量，一是信息增益，二是基尼混度。注意我们处理的是有监督分类，因此我们知道这些训练实例的正确输出分类（有目标的）。

信息增益 设想我们从一个内部节点或叶子节点对应的集合中进行抽样。我们得到 y 类实例的概率 Pr(y) 正比于集合中该类实例所占的比例。所得类的统计不确定性由标记概率分布的香农熵来度量：

                                                

        在信息论中，熵量化了确定某件事件发生所需的平均信息（见图6 ）。如果对数的底为 2 ，信息（也就是熵）的单位是二进制位（ bit ）。当所有 n 个类别的实例均分了一个集合时，熵就达到最大值， H(Y ) = logn ；而当所有实例都属于同一类别时（这种情况下，不需要任何信息，我们已经知道我们会得到什么类别了），熵就达到最小值， H(Y ) = 0 。

图 6 有着差别很大的熵的两个分布。高熵（左）：事件有相似的可能性，不确定性接近最高（ logn ）。低熵（右）：事件有非常不同的可能性，不确定性非常小，接近零，因为某个事件占了大多数的概率

        在信息增益方法中，一个集合的混度由类别概率分布的熵来度量。

        知道一个问题的答案将会降低熵，或者熵保持不变，仅当答案不取决于类别时。令 S 表示目前的实例集，并且让 表示问过一个关于某属性问题之后的划分。理想的问题不会留下难以决策的情况：中所有实例是一类，而中所有实例是另一类，因此这两个生成的子集熵为零。

        在知道了答案后，熵的平均减少量被称为“信息增益”，它也是答案与类别变量之间的互信息（ MI ）。信息增益（互信息）可表述如下：

                        

        计算熵所需的概率可以用样本子集内各类别的相应频率来逼近。信息增益是由 Quinlan 率先在 ID3 、 C4.5 和 C5.0 方法中使用的。值得注意的是，由于我们感兴趣的是泛化，信息增益对此是有用的，但并不完美。假设我们为描述某项业务客户的数据构造一棵决策树，每个节点可以有多于两个子节点。一个输入属性可能是客户的信用卡号码。因为这一属性唯一地标识每个客户，所以它与任何分类都有很高的互信息，然而我们不希望将其包含在决策树中：根据客户的信用卡号码来对客户作出相应决策，这一做法不太可能推广到之前没有见过的客户（这就是过拟合）。

        基尼混度 试想一下，我们从一个集合中随机抽取一个元素，并随机贴上标签，概率正比于不同类别在这个集合中所占的比例。尽管这种方法看起来很原始，如果集合是纯的，这种简单直接的方法的误差为零；如果某个类别在集合中占据了主要部分，这种方法的错误率也是很小的。

        一般情况下，基尼混度（ GI ）测量从集合中随机选择的元素会被错误地标记的频率，标记是按照集合中标记的分布随机进行的。它可以用错误率的期望来计算：对于每个类别，将该类别中某个元素被误分为其他类的概率（即将其分配给任何不正确类别的概率： ）相加，再乘以该元素属于该类别的概率 () ，然后将这些乘积加起来。假设有 m 个类，并且令表示集合中标记为 i 的元素比例。然后，通过频率来估计概率（  ≈  ）：

    

        当节点中所有实例都属于单一目标类别时， GI 为最小值（零）。 GI 被用在 Breiman 提出的CART 算法（分类回归树）中。

        当考虑每个节点所问的问题类型时，实际上只需要考虑那些有二元输出的问题就足够了。对于类别变量，这个测试可以基于该变量的可能值的某个子集（例如，若某天是“星期六或星期天”，则回答 YES ，否则 NO ）。对于实值变量，每个节点对应的测试可以基于单一变量（例如，距离小于 2 英里）或者变量的简单组合，例如变量子集的一个线性函数与一个阈值进行比较（例如，客户花在汽车和摩托车上的钱的平均值多于 2 万美元）。上述概念可以被推广到要预测的数值变量，发展为回归树。每片叶子要么包含到达这里的所有实例的平均输出值，要么包含从这些实例推导出的一个简单模型，比如线性拟合（后一种情况称为模型树）。

        实际的数据中，缺失值就像冬天的雪花漫天飞舞。缺失值有两种可能的意义。在某些情况下，一个值如果缺失了，它会提供一些有用的信息（例如，在市场营销中，如果一个客户没有回答某个问题，我们可以假设他对此不是很感兴趣），缺失值可以被当作一个类型变量的另一个可能值。其他情况下，一个值的缺失并不提供任何明显的信息（例如，一个粗心的业务员忘了记录某个客户的数据）。决策树为处理第二种情况提供了一种自然的方法。如果一个实例到达了一个节点，但是由于数据缺失而无法回答该节点对应的问题，人们可以理想化地“将这个实例分成小块”，并且根据所包含训练实例数的比例，将这些小块送往各个分支。如图 7 所示，如果 30% 的训练实例往左走，那么一个有缺失值的实例在这个决策节点就被分为两部分，比重 0.3 的那一部分往左走，而比重 0.7 的那一部分往右走。当这个实例不同的小块最终都到达叶子节点时，我们计算对应叶子节点输出值的加权平均，或者计算出一个分布。加权平均中的权重与到达叶子部分的比重成正比。在这个例子中，输出值是 0.3 乘以左边的输出加上 0.7 乘以右边的输出。不用说，以左、右子树作为参数的同一程序的递归调用，是获得非常紧凑的软件实现的一个方法。

图 7 缺失的身份信息。到达顶部节点的数据点被发送到其左侧和右侧的两个子节点，权重根据答案“是”和“否”在训练集中出现的频率而有所不同

        最后提醒一下，不要将构建中的决策树（使用已标记实例、纯度度量，以及选择合适的问题）和使用已构建好的决策树相混淆。当使用决策树时，通过一系列决策，输入样本会迅速从树的根节点分配到叶子节点。

2、民主与决策森林

        在 20 世纪 90 年代，研究人员发现了如何用民主的方式将学习机集成起来（例如，比随机猜测性能略好的通用“弱”分类器），以得到更好的准确性和泛化性能。这可以类比于人类社会：很多情况下，设立专家团体是做出更优质决策的一个方法，专家或者达成共识，或者提出不同的方案并表决（在其他情况下，这也是推迟决策的方法，毕竟所有类比都有它的缺点）。“群众的智慧”是近来用以强调民主决策积极作用的一个术语。在机器学习中，输出常常由多数决定（对于分类）或由平均决定（对于回归）。

        在处理高维数据时，民主式集成这一点似乎尤其正确，因为在现实的应用中，高维数据里可能有很多不相关的属性。这一话题并不像它看起来那样抽象：从光学字符识别中用到的神经网络到游戏机输入设备中树的集成 ，已经出现了很多相关的应用 。

        为了让专家团体来做出高明的决策，这些专家需要有不同的思维方式（即不受群体思维的影响，以同样方式思考的专家是没有用的）并且具有较高的素质。获得不同的树的方式有多种，例如，用不同的实例集来训练它们，或者以不同的随机选择来训练它们（用人来打比方，想想学生会选择同一科目的不同课程）。

• 可以用自助法从初始集合中产生不同的训练实例集：给定一个大小为的标准训练集 D ，自助法通过从 D 中均匀带放回（有些实例可以重复）的抽样产生新的训练集。抽样之后，每个训练集中大概有 1 − 1/e ≈ 63.2% 的实例是互不相同的，其他的都是重复的。想想随机投球入筐：对于较大的 ，大概只有63.2% 的筐里有一个或以上的球。筐中的每个球对应一个实例。在每个自助法的训练集中，大概有三分之一的实例被排除了。将自助法用于创造不同样本集的方法称为装袋法（ bagging ，“自助汇合”）：用不同的随机自助样本来构造不同的树，输出是不同树的输出的平均（对于回归问题）或着表决（对于分类问题）。

• 在选择一个节点的最优问题时，可以通过限制选择，在训练时进行不同的随机选择。作为上述划分方法的一个例子，这里来看看它们是如何在随机决策森林中实现的。

• 每棵树用原始数据集的一个自助抽样（即允许重复）来进行训练；

• 每当一个叶子节点必须被分裂的时候，只考虑属性随机选择的一个子集。在极端情况下，只考虑一个随机属性（一维）。

        更准确地说，令 d 为输入变量的总数，每棵树是这样构造的：选择 d' 个输入变量用以确定一个节点上的决策，d' 是个较小的数，通常比 d 要小得多（在极端情况下就是 1 ）。一个自助抽样（“包”）引导一棵树的构造，而那些不在包里的实例可以用来估计树的误差。对于树上的每个节点， d' 个属性是随机选择的，它们是在这个节点上做出决策的基础。我们计算基于这 d' 个变量的最优分割（“最优”要根据所选的纯度标准而定， IG 或者 GI ）。每次选择一个类型变量来对一个节点进行分割，可以随机选择这些类型的子集，并定义一个替换变量，当类型值在这个子集中就为 1 ，否则为 0 。每棵树都完全成长而不修剪（就像构造一棵普通的分类树那样。

        通过上述步骤，我们实际上已经组建了一个团体（“森林”），其中的每一个专家（“树”）都已经接受了不同的训练，因为他们已经看到了一组不同的实例（包），也因为他们用不同的观点看待问题（每一个节点使用不同的随机选择的标准）。然而没有哪位专家可以完全保证胜任工作：每个专家关注变量的顺序远远没有达到贪心的标准，因此信息量最大的问题并没有最受关注，如此一来，单独的一棵树是非常弱的；然而，大多数专家都比随机分类器要好，因此多数占优原则（或者加权平均）将会提供合理的答案。

        使用自助法时的泛化估计可以在训练过程中以一种自然的方式得到：记录包外的误差（不在包中的实例上的误差），并在整片决策森林上求平均。

        不同变量（特征或属性排序）的相关性也可以在决策森林中用一种简单方式来估计。主体思路是：如果一个类别特征是重要的，那么随机地置换其值应该会导致其性能显著降低。用决策森林拟合数据之后，为了推导第 i 个特征的重要性，将第 i 个特征的值进行随机置换，并重新计算这个扰乱的数据集上的包外误差。求得扰乱前后的包外误差之差，并在所有树上求平均值。误判率增加的百分比与所有变量不变时包外误差率的比值就是该特征所得的分数。误判率增加较多的特征比误判率增加较少的特征更重要。

        可以使用大量树（数以千计并不罕见）这一事实意味着，对于需要进行分类或预测的每个实例，会有非常多的可用的输出值。通过收集和分析如此多树的输出的分布，可以得出回归的置信界或者分类的概率。例如，如果有 300 棵树预测“晴天”，剩下的 700 棵树预测“下雨”，那么可以说估计“下雨”的概率是 70% 。

总结

        简单的“如果 – 那么”规则提炼出在某种程度上可以被人们理解的信息金块。避免可能的规则矛盾所带来的混乱，有一个简单方法是以层次结构来处理问题（首先是信息量最大的），由此引出带组织结构的简单的连续问题，称为决策树。

        树可以用贪心和递归的方式习得：从一整套的实例集开始，选择一个测试，将它分为两个尽可能纯的子集，再重复产生子集。当子集的纯度足以在树叶上得到分类输出值时，递归过程终止。

        充足的内存和强大的计算能力允许我们训练大量不同的树。通过收集所有输出以及平均（对于回归）或投票（对于分类），它们可以卓有成效地用作决策森林。决策森林有各种优点：像所有树那样，它们能自然地处理两类以上的分类问题以及缺失的属性；能提供基于概率的输出，以及概率和误差线；不会有过度训练的风险，因此能很好地泛化到从未见过的数据；由于其并行性，以及每个数据点上减少的测试问题集，它快速而高效。

        虽然一棵树的树荫很小，但即使是最火热的机器学习应用，数以百计的树也可以带来清凉。