机器学习中决策树的原理与算法

本篇文章4225字，读完约11分钟

雷锋。(公开号码:雷锋。出版社:李相彬，本文作者，毕业于中国科学院自动化研究所复杂系统国家重点实验室，主修机器学习和计算机视觉，算法工程师。雷锋的第一篇文章。

众所周知，机器学习中有两个非常重要的问题，一个是分类问题，另一个是返回问题。我们今天要讨论的是分类和返回问题中使用的一种非常基本的方法，称为决策树。决策树也是一种重要的标签学习方法。本文的一部分来自人工智能大规模开放在线课程学院的《机器学习理论与实战高级专题训练》的课程笔记。

从名称的角度来看，决策意味着在许多类别中，我们需要决定我们分类的东西属于哪一个类别。决策树称为离散值，返回树称为连续值。在学术语言中，决策树的输出是离散随机变量，返回树的输出是连续随机变量。本文的重点是解释输出为离散随机变量的决策树。当你理解决策树的运行机制时，返回树也会是相似的。

顾名思义，树就是模型的结构是一个树形结构，树形结构的主要优点是可读性强，分类速度快。树由树干和树叶组成，决策树中的有向边和节点与它们相对应。还有两种类型的节点，一种是内部节点，另一种是叶节点。

上面提到的所有概念都可以从字面上理解。本质上，决策树是一种预测模型，它表示对象属性和对象值之间的映射关系。树中的每个节点代表一个对象，内部节点代表一个特征或属性，叶节点代表一个类，每个分叉路径代表一个可能的属性值，每个叶节点对应于从根节点到叶节点的路径所代表的对象的值。

我们可以认为决策树是一组假设规则，我们也可以理解它是在空特征和空.类之间定义的条件概率分布因为它是一个如果-那么规则，决策树有一个重要的属性:它是互斥和完整的，也就是说，每个实例都被一个路径或规则覆盖，并且只被一个路径或规则覆盖。

说了这么多抽象的概念，决策树可以用来处理什么样的问题？让我们用一个实际的例子来解释决策树，我也选择了一个非常简单的场景让大家开始。

如果小明去上班，他可以选择两种交通方式，一种是打车上班，另一种是骑自行车上班。这两种方法中的哪一种取决于三个因素，一个是天气状况，可分为坏天气和非坏天气，另一个是小明的心情，可分为好心情和坏心情，最后一个因素是小明是否会迟到。假设这三个因素与小明在下表中的工作方式相对应:

上表就是我们所说的样本集。细心的读者可能会发现上面的样本集少了一个情况，那就是天气不好，小明心情不好，但是工作时间充裕。是的，我故意把这个小组排除在外，让它成为一个测试集，这样每个人都可以通过建立决策树来预测小明在这种情况下会走哪条路去工作。

既然我们有了数据，我们如何建立一个决策树？

构建决策树时，我们需要解决三个问题:

哪个条件属性位于根节点；

哪个属性放在下面的节点中；

何时停止树木生长。

为了解决以上三个问题，我们需要引入一些概念。

第一个引入的概念是信息熵，在英语中称为熵。在汤姆·米切尔的书中，信息熵解释如下:

它确定要编码的集合S中的任何成员(即，以均匀概率随机选择的成员)的分类所需的二进制数字的最小数目。

说实话，当时我花了很大力气才理解这句话。事实上，将它转换成一种流行的语言意味着信息熵是“预测随机变量Y的值”或“测量随机变量Y的不确定性”的难点。

这可以用两个例子来解释。如果你在地球上，手里拿着一个铁块，如果你不用力直接放开铁块，请判断它是会掉下来还是会飞起来。根据我们的常识，我们可以很容易地判断出石头会掉下来，所以很容易判断出这件事情的结果，此时的信息熵可以认为是0。

再举一个例子，如果你被要求判断一枚同质硬币被抛出后是面朝上还是面朝上，我们将很难回答这个问题，因为面朝上和面朝上的概率是相等的，所以我们不能明确判断硬币的哪一面是面朝上的，所以此时很难判断，所以此时的信息熵可以认为是1。

但是，如何将上述词语翻译成数学语言进行定义和描述呢？许多学者提出了他们认为的信息熵的表达式。我们可以通过下表来了解一些当前的信息熵定义。

虽然有这么多的定义，我们通常在很多情况下使用香农信息熵，所以我也用香农信息熵来表达下面的其他定义。

当我们有了信息熵的表达式，我们就可以得到一个二值分类问题的信息熵图像，如下图所示。

我们可以看到，这张图片所表达的信息与我们之前给出的例子完全一致。当一件事情很容易判断，也就是说，我们认为它发生或不发生的概率很大，那么它的信息熵就趋向于0。当一件事情很难判断时，我们可以认为最困难的时候是这个事件的所有可能性都相等的时候，那么它的信息熵就是1。

既然我们有了信息熵的概念，我们引入第二个概念，它需要基于信息熵。这就是条件信息熵。有了信息熵的概念，我们自然可以得到条件信息熵的概念，即衡量“在随机变量x的前提下预测随机变量y”的难度。

信息熵表示判断的难度。当我们有条件这个词的时候，也就是说，在我们知道一个条件之后，让你来判断变量的结果。目前的困难是条件信息熵。就像上面的例子，我们发现只要小明发现他要迟到了，他就会打车上班，所以当我得知小明今天要迟到的时候，我很容易判断他是否要打车，所以此时的条件信息熵可以认为是0，即条件信息熵。如果仍然采用香农的定义方法，那么条件信息熵的数学表达式为

P(y|x)，p(x)，

有了信息熵和条件信息熵的概念，我们自然可以引出第三个概念，即信息增益。信息增益的数学定义是

通过看这个数学表达式，我们可以很容易地看出信息增益的含义。最关键的是信息熵，也就是说，当没有人向我们通风报信时，判断结果的难度；减法是条件信息熵，即当我们知道一个条件时，很难判断结果。可变信息增益意味着条件x在判断结果时降低了多少难度，即测量x对预测y的能力的影响。

就像有一个电视节目叫快乐词典一样，当回答问题的人不能判断答案时，他会选择三种求助方式。事实上，寻求帮助的方式是一个条件，在玩家使用了寻求帮助的方式之后，回答问题的难度的降低就是信息的获得。如果难度大大降低，那么我们可以说信息增益很大。

通过引入上述三个概念，我们可以回答构建决策树时的第一个问题:哪个条件属性被放置在根节点中。

我们的放置方法是选择信息增益最大的属性作为根节点。

由于数据集的信息熵是固定的，这个问题转化为选择条件信息熵最小的属性，所以我们只需要找到条件信息熵最小的属性就可以知道根点。

通过实例计算，我们可以分别计算个体特征的条件信息熵，计算过程如下:

通过计算，我们可以看出小明是否迟到这个属性的条件信息熵最小，所以我们将这个属性作为根节点。所以决策树的雏形如下。

知道了根节点的放置方法，第二个问题就解决了，哪个属性被放置在下一个节点。我们只需要将获得的节点视为新的根节点，并使用最小化条件信息熵的方法。我们把小明不迟到作为条件，所以表如下

然后再次计算条件信息熵，计算过程如下:

我们看到气象因子的条件信息熵最小，为0，所以我们的下一个节点是气象因子。此时，我们实际上可以结束决策树的增长。为什么？那么我们如何判断何时结束决策树的增长呢？

因为我们总是最小化条件信息熵，所以当我们发现所有特征的信息增益都很小时，或者我们没有特征可供选择时，我们可以停止。到目前为止，我们已经构建了决策树。

下图显示了最终的决策树:

通过决策树，我们可以很容易的判断出当天气不好的时候，小明心情不好但是工作时间很充裕，小明的出行方式是打车。

因此，到目前为止，如何建立决策树的方法已经基本上介绍给大家了。在学术上，常用的算法有id3算法、c4.5算法和cart算法。事实上，这些算法与我上面介绍的方法和思想基本相同，但是在选择目标函数时有一些不同。我说的是最小化条件信息熵，id3使用信息增益，c4.5使用信息增益比，cart使用基尼系数。

基本介绍了决策树的原理和算法，因为防止模型过拟合也是机器学习中的一个重要问题，所以我将简要介绍决策树的剪枝。

发生拟合的原因是我们在学习过程中过多考虑了如何提高训练数据的正确分类，所以有时我们会构建一个过于复杂的决策树。一旦决策树变得复杂，测试数据的分类就不那么准确，也就是说，过度拟合。因此，根据奥卡姆剃刀的精神，为了简化决策树，这个过程被称为修剪。

决策树剪枝是通过最小化整个决策树的损失函数来完成的。决策树的损失函数定义为:

其中，树t的叶节点数为|t|，c(t)表示模型对训练数据的预测误差，即模型与训练数据的拟合度，|t|表示模型的复杂度，参数α为非负数，控制两者之间的影响。

C(t)的计算方法是

其中，t是树t的叶节点，树t有nt个样本，其中有k类的ntk个样本点，k = 1，2，…，k。

可以用上面的表达式计算损失函数，并且从叶节点向上递归计算损失函数。如果在一组叶节点返回到它们的父节点之前和之后的整个树分别是tb和ta，则相应的损失函数分别是cα(tb)和cα(ta)，如果

执行修剪，即父节点被改变成新的叶节点。

因为决策树的生成已经在开源库opencv中实现了，最后，我附上了一个使用opencv来训练我上面例子的代码，目的是让每个人都实现一个类似hello world的程序。这里不重复opencv的配置方法，所以您可以使用下面的代码作为练习。对opencv内部实现过程感兴趣的学生也可以学习源代码，源代码也可以从opencv的官方网站下载。

需要说明的一点是，我们需要将上述场景数字化，我们将上述情况作为0和1来表示决策树的构造。所以新表如下:

使用这个程序，你可以看决策树的预测，当天气不好，心情不好的时候，小明会选择哪种交通工具，但是还有很多时间。我在这里偷偷告诉你，人工智能给出的答案如下

这和我们推断的结果一样吗？

雷锋网友情提醒:

作为人工智能领域的一项黑色技术，深度学习一直是许多学生的梦想。艾大规模开放在线课程学院在6月17 -18日有一个12小时的深度学习课程。fastai中文社区的四位最活跃的贡献者将为您开启深入学习的大门。

本课程采用“探索+实践”的硅谷教学模式，让您从一个门外汉快速进入深度学习工程师的角色，完成一个又一个项目挑战。最受欢迎的深度学习技巧，你会在这里一个接一个地体验，学习整个课程，你会学到最新的技术，如cnn、rnn、vgg16、resnet和inceptioncnn。快速构建您的深度学习应用程序不再是梦想。

只要你有基本的python编程经验，你就能学好这门课程！即使你没有编程基础，我们也可以带你飞！

雷锋的特别贡献。严禁擅自转载。详情请参考转载说明。

来源：搜狐微门户