何为决策树

决策树(Decision Tree)是一种分类和回归方法，是基于各种情况发生的所需条件构成决策树，以实现期望最大化的一种图解法。由于这种决策
分支画成图形很像一棵树的枝干，故称决策树。它的运行机制非常通俗易通，因此被誉为机器学习中，最友好的算法。下面通过一个简单的例子来阐述它的执行流程。假设根据大量数据（含 3 个指标：天气、温度、风速）构建了一棵“可预测学校会不会举办运动会”的决策树（如下图所示）。

在对任意数据进行预测时，都需要从决策树的根结点开始，一步步走到叶子结点（执行决策的过程）。如，对下表中的第一条数据（ [ 阴天，寒冷，强 ] ）：首先从根结点出发，判断 “天气” 取值，而该数据的 “天气” 属性取值为 “阴天”，从决策树可知，此时可直接输出决策结果为 “举行”。这时，无论其他属性取值为什么，都不需要再执行任何决策（类似于 “短路” 现象）。对下表中的第二条数据（ [ 晴天，炎热，弱 ] ）：首先从根结点出发，判断 “天气” 取值为 “晴天”，然后我们顺着决策树走到温度节点，取值为“炎热”，顺着决策树来到湿度节点，取值为“弱”，此时对应的决策结果为 “不举行”。对于这种情况，我们只需按图索骥，就能找出对应的结果。

天气	温度	风速	预测结果
阴天	寒冷	强	举行
晴天	炎热	弱	不举行
晴天	寒冷	弱	举行
雨天	正常	弱	不举行

决策树的组成

决策树由结点和有向边组成。结点有两种类型：内部结点（圆）和叶结点（矩形）。其中，内部结点表示一个特征（属性）；叶结点表示一个类别。而有向边则对应其所属内部结点的可选项（属性的取值范围）。

在用决策树进行分类时，首先从根结点出发，对实例在该结点的对应属性进行测试，接着会根据测试结果，将实例分配到其子结点；然后，在子结点继续执行这一流程，如此递归地对实例进行测试并分配，直至到达叶结点；最终，该实例将被分类到叶结点所指示的结果中。

在决策树中，若把每个内部结点视为一个条件，每对结点之间的有向边视为一个选项，则从根结点到叶结点的每一条路径都可以看做是一个规则，而叶结点则对应着在指定规则下的结论。这样的规则具有互斥性和完备性，从根结点到叶结点的每一条路径代表了一类实例，并且这个实例只能在这条路径上。

决策树的构建

决策树的本质是从训练集中归纳出一套分类规则，使其尽量符合以下要求：

1. 具有较好的泛化能力；
2. 在 1 的基础上尽量不出现过拟合现象。

注意到一件事：当目标数据的特征较多时，构建的具有不同规则的决策树也相当庞大（成长复杂度为 𝑂(𝑛!) ）。如当仅考虑 5 个特征时，就能构建出 5×4×3×2×1=120 种。在这么多树中，选择哪一棵才能达到最好的分类效果呢？实际上，这个问题的本质是：应该将样本数据的特征按照怎样的顺序添加到一颗决策树的各级结点中？这便是构建决策树所需要关注的问题核心。

如，在前面的例子中，为什么要先对“天气”进行划分，然后再是“温度”和“风速”呢（下图1）？可不可以先对“风速”进行划分，然后再是“温度”和“天气”呢（下图2）？

一种很直观的思路是：如果按照某个特征对数据进行划分时，它能最大程度地将原本混乱的结果尽可能划分为几个有序的大类，则就应该先以这个特征为决策树中的根结点。接着，不断重复这一过程，直到整棵决策树被构建完成为止。

基于此，引入信息论中的“熵”。