3.5 机器学习的其他算法——决策树
除了回归算法外，机器学习还有其他较为常用的学习算法，这里只介绍一个，即决策树算法。
决策树是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。本节主要介绍决策树的构建算法和运行示例。
3.5.1 水晶球的秘密
相信读者都玩过这样一个游戏。一个神秘的水晶球摆放在桌子中央，一个低沉的声音（一般是女性）会问你许多如下问题。
问：你在想一个人，让我猜猜这个人是男性？
答：不是的。
问：这个人是你的亲属？
答：是的。
问：这个人比你年长。
答：是的。
问：这个人对你很好？
答：是的。
那么聪明的读者应该能猜得出来，这个问题的最终答案是“母亲”。这是一个常见的游戏，如果将其作为一个整体去研究，整个系统的结构就如图3-10所示。
图3-10 水晶球的秘密
如果读者使用过项目流程图，那么可以知道，系统最高处代表根节点，是系统的开始。整个系统类似于一个项目分解流程图，其中每个分支和树叶代表一个分支向量，每个节点代表一个输出结果或分类。
决策树用来预测的是一个固定的对象，从根到叶节点的一条特定路线就是一个分类规则，决定这一个分类算法和结果。
由图3-10可以看到，决策树的生成算法是从根部开始，输入一系列带有标签分类的示例（向量），从而构造出一系列的决策节点。其节点又称为逻辑判断，表示该属性的某个分支（属性），供下一步继续判断，一般有几个分支就有几条有向的线作为类别标记。
3.5.2 决策树的算法基础——信息熵
首先介绍决策树的理论基础，即信息熵。
信息熵指的是对事件中不确定的信息的度量。在一个事件或者属性中，信息熵越大，其含有的不确定信息越大，对数据分析的计算就越有益。因此总是选择当前事件中拥有最高信息熵的那个属性作为待测属性。
说了这么多，问题来了，如何计算一个属性中所包含的信息熵？
在一个事件中，计算各个属性的不同信息熵，需要考虑和掌握的是所有属性可能发生的平均不确定性。如果其中有n种属性，其对应的概率为P1，P2，P3…Pn，且各属性之间出现时彼此相互独立无相关性，此时可以将信息熵定义为单个属性的对数平均值，即：
E(P)=E(−logpi)=−∑pilogpi
为了更好地解释信息熵的含义，这里举一个例子。
小明喜欢出去玩，大多数的情况下他会选择天气好的条件下出去，但是有时候也会选择天气差的时候出去，而天气的标准又有如下4个属性：
- 温度
- 起风
- 下雨
- 湿度
为了简便起见，这里每个属性只设置两个值，0和1：温度高用1表示，低用0表示；起风是用1表示，没有用0；下雨用1表示，没有用0；湿度高用1表示，低用0。表3-3给出了一个具体的记录。
表3-3 是否出去玩的记录
本例子需要分别计算各个属性的熵，这里以是否出去玩的熵计算为例演示计算过程。
根据公式首先计算出去玩的概率，其有2个不同的值：0和1。例如，第一列温度标签有两个不同的值，0和1。其中，1出现了4次，而0出现了2次。
即出去玩（out）的信息熵为0.918。与此类似，可以计算不同属性的信息熵，即：
3.5.3 决策树的算法基础——ID3算法
ID3算法是基于信息熵的一种经典决策树构建算法。根据百度百科的解释，ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。
因此可以说，ID3算法的核心就是信息增益的计算。
信息增益指的是一个事件中前后发生的不同信息之间的差值。换句话说，在决策树的生成过程中，属性选择划分前和划分后不同的信息熵差值。用公式可表示为：
Gain(P1,P2)=E(P1)−E(P2)
表3-3构建的最终决策是要求确定小明是否出去玩，因此可以将出去玩的信息熵作为最后的数值，而每个不同的属性被其相减，从而获得对应的信息增益，其结果如下：
通过计算可得，其中信息增益最大的是“起风”，其首先被选中作为决策树根节点，之后对于每个属性，继续引入分支节点，从而可得一个新的决策树，如图3-11所示。
图3-11 第一个增益决定后的分步决策树
其中，决策树左边节点是属性中wind为1的所有其他属性，而wind属性为0的被分成另外一个节点。之后继续仿照计算信息增益的方法依次对左右的节点进行递归计算，最终结果如图3-12所示。
图3-12 出去玩的决策树
从中可以看到，根据信息增益的计算，可以很容易地构建一个将信息熵降低的决策树，从而使得不确定性达到最小。
通过上述分析可以看到，对于决策树来说，其模型的训练是固定的，因此生成的决策树也是一定的；而其中不同的地方在于训练的数据集不同，这点是需要注意的。在本书的后面，会写出一个决策树的代码实现，请读者注意。