【机器学习】决策树（理论）

决策树（理论）

---

一、何为决策树

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

接下来，当我们拿到某个数据时，就能做出对应预测。

在对任意数据进行预测时，都需要从决策树的根结点开始，一步步走到叶子结点（执行决策的过程）。如，对下表中的第一条数据（ [ 阴天，寒冷，强 ] ）：首先从根结点出发，判断 “天气” 取值，而该数据的 “天气” 属性取值为 “阴天”，从决策树可知，此时可直接输出决策结果为 “举行”。这时，无论其他属性取值为什么，都不需要再执行任何决策（类似于 “短路” 现象）。

1、决策树的组成

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

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

在决策树中，若把每个内部结点视为一个条件，每对结点之间的有向边视为一个选项，则从根结点到叶结点的每一条路径都可以看做是一个规则，而叶结点则对应着在指定规则下的结论。这样的规则具有互斥性和完备性，从根结点到叶结点的每一条路径代表了一类实例，并且这个实例只能在这条路径上。从这个角度来看，决策树相当于是一个 if-then 的规则集合，因此它具
有非常好的可解释性（白盒模型），这也是为什么说它是机器学习算法中最“友好”的一个原因。

2、决策树的构建

前面介绍了决策树的相关概念，接下来讨论如何构建一棵决策树。

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

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

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