决策树（理论知识1）

何为决策树

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

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

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

在用决策树进行分类时，首先从根结点出发，对实例在该结点的对应属性进行测试，接着会根据测试效果，将实例分配到其子结点；然后，在子结点继续执行这一流程，如此递归地对实例进行测试并分配，直至到达叶结点；最终，该实例将被分类到叶结点所指示的效果中。
在决策树中，若把每个内部结点视为一个条件，每对结点之间的有向边视为一个选项，则从根结点到叶结点的每一条路径都可以看做是一个规则，而叶结点则对应着在指定规则下的结论。这样的规则具有互斥性和完备性，从根结点到叶结点的每一条路径代表了一类实例，并且这个实例只能在这条路径上。
决策树的构建

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

• 具有较好的泛化能力；
  
• 在 1 的底子上尽量不出现过拟合现象。
  

注意到一件事：当目的数据的特征较多时，构建的具有不同规则的决策树也相称庞大（成长复杂度为