有了关于分类问题的基本认识，本节介绍一种简单的分类算法——决策树。决策的意思就是使用训练数据学习分类的决策依据，从而可以据此对需要分类的数据属于哪一类这样的问题给出决策。决策树是人工智能中的经典算法，既适用于输出结果为连续值的回归问题（又叫回归树），也适用于输出结果为离散值的分类问题，它们的基本想法是一致的，理解了决策树的原理，回归树就很容易掌握了，本节只针对离散值的情形讲解决策树算法。

使用决策树进行分类其实模拟了人类决策的过程。例如，小明想约小红明天去看电影，发生了下述对话过程。

小红：明天有好看的电影吗？

小明：有啊，一部新上映的大片。

小红：看几点的？我只有中午有时间。

小明：正好中午12点有一场。

小红：明天天气怎么样？

小明：天气很舒服，不冷不热。

小红：好的，那你明天按时来接我吧。

小明：明天见。

在这个对话中，小红对明天看电影的事情有“看”和“不看”两类安排，做出“看”的决定需要满足如下要求：电影好看、时间合适，并且天气舒服。这个决策的过程可以通过图3-1来描述。

图3-1

上述图示很好地展示了决策树的直观含义。所谓决策树，指的是一个树形结构，其中每个内部节点代表一个特征属性，内部节点的每个分支路径代表了此特征属性的某个可能的属性值，而每个叶子节点代表一个类别。因为每个内部节点都会生长出几个不同的分支，沿分支可以到达其他的内部节点或叶子节点，所以此内部节点对应的特征属性又叫作分裂属性。

决策树是一个用于分类的预测模型，也就是说，它给出了每个待分类对象到类别的一种映射关系。使用决策树进行决策的过程就是从根节点开始，测试待分类对象相应的特征属性，按照属性值选择分支路径，直至到达某个叶子节点，将此叶子节点存放的类别作为决策结果。

可以结合上面的直观例子理解与决策树相关的概念。所谓树形结构，指的是图3-1就像一棵倒置的树。橙色的节点都是内部节点，代表“电影质量”“时间”“天气”三个特征属性，特别地，“电影质量”叫作根节点。存放决策结果“看”或者“不看”的绿色节点就是叶子节点。有了这个树形结构，根据特征属性的不同取值，沿着决策树的不同路径，就可以做出相应的决策了。

在这个直观的例子中，每个特征属性都有两个可能的取值，所以对应两个分支，这样的树叫作二叉树。决策树对特征属性的取值没有个数限制，所以决策过程对应的树形结构可以更复杂。与决策树复杂程度有关的另外一个因素是决策过程中所使用的特征属性的个数，它决定了树的深度。在这个例子中使用了三个特征属性，所以这是一个三层的决策树。

从这个例子看，决策树的道理很简单，对它进行决策的方式也已经了解得很清楚了。那么读者现在是不是可以完整地针对一个分类问题给出相应的决策树呢？如果尝试一下，会发现还有一个最关键的问题没有解决，就是如何构建一棵决策树。具体地说，关于决策树的构建，需要解决如下两个问题。

（1）如何选择分裂属性

这个问题可以分解成两个小问题：一是选择哪个特征属性作为根节点？二是某个内部节点之下应该选择哪个特征属性作为下一层分裂属性？

（2）何时停止树的生长

在决策树生长成什么样子以后，就可以作为最终进行决策时所使用的决策 树了？

一个分类问题，通常包含多个特征属性。如果可以随意选择根节点和内部节点，当有m个特征属性时，用不同的顺序安排分裂属性，理论上可以生长出m！棵不同的决策树。所谓选择分裂属性的问题，其实是制订一个合理的量化标准，根据这个标准来比较不同的生长顺序的优劣，从而选择出最佳的生长顺序作为最终的决策树。

为了量化各种分裂属性选择方案的好坏，需要引入一个新的数学概念——熵（Entropy）。熵的概念是由信息论的创始人香农提出的，现在在很多学科中都有重要的用处。为了更容易理解这个概念，这里结合分类问题来描述它的定义。

设某个分类问题X包含n个类别m个特征属性，任意样本C属于第i个类别Xi（1≤i≤n）的概率为pi，则I（Xi）=-log2pi称为Xi的信息（Information），X的熵定义为

在分类问题中，如何简单地理解上述定义呢？显然有如下关系。

进而可以看出，类别Xi的信息是随着概率增加而减少的，也就是说，这个量衡量了Xi的不确定性。例如，概率为1时，它是注定会出现的，所以信息为0，不确定性最小；概率为0时，信息为+∞，不确定性最大。

而熵的概念可以结合概率中的全概率公式来理解，它代表了分类问题X的不确定性的期望（概率平均值），也就是对类别进行预测时的不确定性，或者说是预测的难度。

有了这样的认识，就可以很自然地给出确定分裂属性的原则：选择当前可以最大程度减少预测的不确定性的属性作为分裂属性。

衡量不确定性的减少程度有几种不同的计算方式，根据计算方式的不同，衍生出了不同的决策树算法。例如，使用信息增益的ID3算法，使用信息增益比的C4.5算法，还有使用基尼指数的CART算法。它们的原理是类似的，本教材介绍采用信息增益的ID3算法，其他算法只要把信息增益的计算公式替换成相应的其他计算公式就可以了。

在条件熵的基础上，就可以按如下方式定义信息增益（Gain）的概念了。

Gain（X，A）=H（X）-H（X|A）

信息增益还有一个名称叫作互信息，这是信息论中常用的名称。从熵和条件熵的定义可以看出，信息增益反映的是，选择A作为分裂属性后，分类问题的不确定性减少了多少。按照前面所说的选择分裂属性的原则，只要计算当前可供选择的所有特征属性对应的信息增益，以信息增益最大的属性作为决策树的下一个分裂属性即可。

对这个基本原则建立了清楚的认识后，使用信息增益就可以给出完整的构造决策树的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%准确地对训练样本进行分类，但是对训练样本以外的数据，其分类效果可能会不理想甚至很差，这就是过拟合。解决决策树的过拟合问题，一种方法是通过设置合理的信息增益阈值作为终止条件，这被称为关键值剪枝（Critical Value Pruning）策略。剪枝是一种重要的提升决策树性能的方法，也就是剪去生成的决策树中造成过拟合的分叉。常用的剪枝策略还有悲观错误剪枝（Pessimistic Error Pruning）、最小误差剪枝（Minimum Error Pruning）、代价复杂剪枝（Cost-Complexity Pruning）、基于错误的剪枝（Error-Based Pruning）等。读者今后可以通过实践学习不同的剪枝策略。