奇书网

第二节 决策树的ID3算法（第2页）

对这个基本原则建立了清楚的认识后，使用信息增益就可以给出完整的构造决策树的ID3算法了。

第一步，初始化信息增益阈值。

第二步，生成根节点。通过计算分类问题的熵和不同特征属性对应的条件熵，选择信息增益最大并且大于增益阈值的属性作为第一个分裂属性生成根节点，并将该属性从候选属性中去除。

第三步，根据上层节点的不同取值，生成新的训练数据，计算不同的候选属性的信息增益，选择增益最大并且大于增益阈值的属性作为分裂属性生成新的节点，并将该属性从候选属性中去除。

第四步，重复第三步，直至满足终止条件。

该过程会重复使用第三步，这个方法被称为递归方法。现在还剩下一个问题需要说明，即与决策树构建有关的问题：何时停止树的生长？也就是在上述流程的最后一步中，终止条件是什么？常用的终止条件如下所列。

①如果所有属于分裂属性某个取值的训练数据都属于同一类别，则生成此类别的叶子节点并终止程序；

②如果特征属性已经使用完毕，即候选属性为空，则以当前训练数据中出现最多的类别生成叶子节点并终止程序；

③如果所有候选属性的信息增益都小于阈值，则以当前训练数据中出现最多的类别生成叶子节点并终止程序。

下面以上一节的电商消费数据为例，演示决策树ID3算法的实现过程，以帮助读者建立直观的认识。在实际操作中，一般以训练数据中相应的频率来代替概率。下面计算中四舍五入后都取两位小数，并且规定0×log20=1×log21=0。

（1）设定信息增益阈值

信息增益阈值设为0。03，认为小于这个阈值的增益对于改善分类的不确定性已经没有意义。

（2）生成根节点

H（X）=-{0。3×log2（0。3）+0。7×log2（0。7）}=0。88

消费频率F的条件熵为

上述计算中类别按照非优质、优质的顺序，属性按照低、中、高的顺序进行。类似地，可以算出平均消费金额N与是否接受广告A的条件熵为

H（X丨N）=0。33

H（X丨A）=0。85

所以三个特征属性对应的信息增益分别为

Gain（X，F）=0。88-0。55=0。33

Gain（X，N）=0。88-0。33=0。55

Gain（X，A）=0。88-0。85=0。03

平均消费金额N对应的信息增益最大，所以选它作为根节点，从候选属性中删除N。按照不同的属性取值生成三个分支，可以看到N的值为“中”或“高”的所有训练数据类别都是“优质客户”，按照终止条件，这两个分支生成叶子节点“优质客户”；N的值为“低”的训练数据同时包含两种类别，需要使用其他属性继续分裂。此时生成的树形结构如图3-2所示。

图3-2

（3）继续计算信息增益进行分裂

此时注意候选属性只有消费频率和是否接受广告。因为在平均消费金额为“低”的分支进行分裂，所以此时的训练数据只包含原表格中平均消费金额取值为“低”的数据，如表3-4所示。

表3-4

类似于第二步，在此训练数据下，计算可得X的熵为0。81，消费频率的条件熵为0，是否接受广告的条件熵为0。79，这两个特征属性对应的信息增益分别是0。81和0。02，所以选择消费频率作为第二层的分裂属性。注意到此时消费频率的三个取值对应的样本都只属于一个类别。例如，消费频率为“低”一定属于“非优质客户”，所以满足程序终止的条件，生成叶子节点后即可得到最终的决策树，树形结构如图3-3所示。

图3-3

通过训练数据生成上述决策树后，就可以使用决策树进行未知类别数据的分类了。例如，某个客户消费频率“低”，平均消费金额“低”，不接受广告，则此决策树将把它归入“非优质客户”的类别。读者也可以尝试把训练数据输入决策树，此时会发现决策树对训练数据的分类是完全正确的。

值得一提的是，决策树是人工智能发展过程中出现较早的基本分类方法，但它并不过时，在很多问题中仍然发挥着重要作用。它具有区别于其他分类算法的显著优点——分类过程和结果都具有高度的描述性和可读性。它构建方法简单，在构造过程中不需要任何领域的知识或参数设置，一次构建后可以反复使用，非常适用于探测式的知识发现，而且构建完成后分类效率高，每一次预测分类的计算次数都不超过决策树的深度。它还有一个重要性质——互斥并且完备，即每一个分类实例都被且仅被一条路径规则覆盖。它的分类准确率也是有保障的，数学上可以证明决策树方法的误差可以任意小。

当然，决策树也有缺点。例如，它比较难以处理连续取值的特征属性。此外，由于其最底层叶子节点是通过上层节点中的单一规则生成的，所以通过手动修改样本的特征属性比较容易欺骗分类器。比如，使用决策树的垃圾邮件识别系统，用户可以通过修改某一关键特征骗过识别系统。另外，采用递归的方式生成决策树，随着数据规模的增大，计算量以及内存消耗会变得越来越大。

决策树依然在不断发展，以改进决策树算法的某些缺点。例如，使用信息增益比生成决策树的C4。5算法、集成学习的重要算法随机森林等、基于决策树但使用“进化”思想的XGBoost方法等，它们在互联网、金融、交通等领域都有广泛应用。在深度学习成为人工智能主流方法的背景下，现在研究人员甚至还利用决策树来帮助理解“深度学习”的内在机制。

最后，关于决策树算法还有一点是需要说明的。本节利用电商客户数据建立的决策树，对训练数据可以做出完全正确的分类，这在某种程度上反映了决策树算法的一个问题——过拟合。人工智能的各类方法中过拟合是一个普遍需要注意的现象。具体地，对决策树算法来说，完全训练的决策树（未剪枝，未合理限制信息增益阈值）能够100%准确地对训练样本进行分类，但是对训练样本以外的数据，其分类效果可能会不理想甚至很差，这就是过拟合。解决决策树的过拟合问题，一种方法是通过设置合理的信息增益阈值作为终止条件，这被称为关键值剪枝（CriticalValuePruning）策略。剪枝是一种重要的提升决策树性能的方法，也就是剪去生成的决策树中造成过拟合的分叉。常用的剪枝策略还有悲观错误剪枝（PessimisticErr）、最小误差剪枝（MinimumErr）、代价复杂剪枝（plexityPruning）、基于错误的剪枝（Error-BasedPruning）等。读者今后可以通过实践学习不同的剪枝策略。