消费频率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）策略。剪枝是一种重要的提升决策树性能的方法，也就是剪去生成的决策树中造成过拟合的分叉。常用的剪枝策略还有悲观错误剪枝（PessimisticErrorPruning）、最小误差剪枝（MinimumErrorPruning）、代价复杂剪枝（Cost-ComplexityPruning）、基于错误的剪枝（Error-BasedPruning）等。读者今后可以通过实践学习不同的剪枝策略。
