4 决策树

4.1 基本概念

4.1.1 举例子

多分类问题实质上通过划分的方法转化为多个二分类问题进行求解。这次我们将讨论另一种被广泛使用的分类算法–决策树（Decision Tree）。

比如一个相亲——母女对话：

女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。

此例子纯属虚构，不代表广大女性同胞的择偶标准。如有雷同纯属巧合。
我们就可以通过这段对话，画出一个决策树。

4.1.2 决策树

决策树（decision tree）：是构建出的一个基于属性的树形
分类器。

每个非叶节点表示一个特征属性上的测试（分割）（判断）
每个分支代表这个特征属性在某个值域上的输出（分支）
每个叶节点存放一个类别（结果）

使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

4.2 决策树的构建

决策树的构建采用分治法的思想（递归）。而结束递归的条件如下：

① 当前结点样本均属于同一类别，无需划分。（只有一种结果）

Example: 下一个要划分的属性为属性1，显然无论属性为何种，均为 P 类无需划分。

② 当前属性集为空。（没有下一个结点）

Example: 属性1(B)→属性2(A)→属性3(A) 走完该路径已经无属性往下分

③ 所有样本在当前属性集上取值相同，无法划分。（每个结点只有一条分支）

Example: 属性1 的 B分支下，样本子集中所有样本属性值完全一样，再往下划分就没有意义了。

④ 当前结点包含的样本集合为空，不能划分。

Example: 属性 1 → 属性 2 的分支下只有 A ，无其他子集。

伪代码：

4.3 决策树的核心

决策树的核心是：如何选取最佳划分属性。

比如我们举一个极端的例子：

很显然，其实根据属性 3 就可以判断出正负例了。那加入其他的属性进行判断就显得多余了。

4.3.1 最佳划分

最佳划分属性

我们希望经过属性划分后，不同类样本被更好的分离。

理想情况：划分后样本被完美分类。即划分到每个分支的样本都属于同一类。
实际情况：不可能完美划分！尽量使得每个分支某一类样本比例尽量高！即尽量提高划分后子集的纯度（purity）。

最佳划分目标

提升划分后子集的纯度
降低划分后子集的不纯度

因此下面便是介绍量化纯度的具体方法，决策树最常用的算法有三种：ID3，C4.5和CART。

4.3.2 ID3 决策树算法

ID3 算法使用信息增益为准则来选择划分属性，“信息熵”(information entropy)是度量样本结合纯度的常用指标，所以我们先介绍信息熵。

信息熵

假定当前样本集合 D 中第k类样本所占比例为 p_k，则样本集合D的信息熵定义为：

Ent(D)的值越小，则 D 的纯度越高

假定离散属性 a 有 V 个可能的取值{a¹,a²…,a^V}。若使用 a 来对样本集 D 进行划分，那么会产生 V 个分支结点，其中 D^v 表示第 v 个分支结点包含了 D 中所有在属性 a 上取值为 a^v的样本数。然后呢，我们可以根据上面的式子计算出 D^v 的信息熵，再考虑到不同分支结点包含的样本数的不同，我们还需要对分支结点赋予权重 |D^v|/|D|，即样本数越多的分支结点的影响越大，所以就计算出用属性 a 对样本集 D 进行划分所得到的 信息增益:

信息增益越大，表示使用该属性划分样本集D的效果越好，因此ID3算法在递归过程中，每次选择最大信息增益的属性作为当前的划分属性。也就是每次可以得到最佳划分属性。

例子

4.3.3 C4.5 算法

提出

ID3算法存在一个问题，就是偏向于取值数目较多的属性

例如：在学生成绩分类中，考虑学号为一个属性，然而学号基本每个人都有，所以得到得纯度很高，但是对分类毫无用处

因此又提出了 C4.5算法 通过 “增益率”（gain ratio） 来选择划分属性，来避免这个问题带来的困扰。

增益率

首先使用ID3算法计算出信息增益高于平均水平的候选属性，接着C4.5计算这些候选属性的增益率，增益率 Gain_ratio 定义为：

我们称上图的 IV(a) 为属性 a 的 “固有值”。属性 a 的可能取值越多（V 越多），则 IV(a) 通常会越大。

C4.5 算法不是直接选择增益值最大的候选划分属性，而是类似于一种启发式算法：先从划分属性中找到信息增益高于平均水平的属性，再计算它们的增益率，从增益率内找最高的。

4.3.4 CART 算法

CART 是另一种决策树算法，使用 “基尼指数” 来选择划分属性。采用与 Ent(D) 信息熵计算相同的符号p_k，数据集 D 的纯度可以用 基尼值 来度量：

直观的说，Gini(D) 反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D) 越小，则数据集 D 的纯度最高。

同样的,基尼值对应信息熵，CART 的基尼指数也对应信息增益：

Gini_index 和 Gain_ratio 计算过程一样。CART 和 ID3 算法的区别在于 Gini 和 Gain 的区别。一个是 p_klog₂p_k 一个是 p_kp_k’

研究表明: 划分选择的各种准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限。（也就是其实是更改准则对模型的效果影响有限）

例如信息增益与基尼指数产生的结果，仅在约 2% 的情况下不同。

而剪枝方法和程度对决策树泛化性能的影响更为显著。

在数据带噪时甚至可能将泛化性能提升 25%。

4.4 剪枝处理

4.4.1 概念

从决策树的构造流程中我们可以直观地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合（overfitting），即太依赖于训练样本。剪枝（pruning）顾名思义，将多余的分支剪掉，是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：

预剪枝（prepruning）：在构造的过程中先评估，再考虑是否分支。具体是若当前结点向下划分不能提升决策树泛化性能，则进行裁剪，把结点标记为叶结点，不再向下分支。也就是评估分支与不分支的性能进行比较。

后剪枝（post-pruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。具体是自底向上，判断结点对应的子树被替换为叶结点是否能提升决策树泛化能力，是则进行裁剪（将该结点的子树替换为叶结点）。（如果不懂看这里：其实就是从下向上，看我这一层要是成了叶结点是否会更好，更好则裁剪）

4.4.2 性能度量

显然，问题就来了，我怎么知道更好呢？

之前学的2.模型评估与选择就有用了，其实就是所谓的性能度量。之前讲过的 验证集 在这里也就有了用处。

例子

书上是使用的留用法，预留一部分数据作为验证集来进行性能评估。先看西瓜数据集：

我们随机将其划分为了两部分，一部分是训练集，一部分是验证集。我们通过信息增益准则可以进行属性划分选择，生成一个未剪枝的决策树：

开始了啊！

预剪枝

预剪枝，每次选定属性后，要进行一次评估。图 4.6 就是第一次评估。我首先默认，不作划分的话都是好瓜。对于 ① 脐部，划分前，经过它所包含的验证集进行验证，准确率 42.9%，划分后 71.4%，显然需要划分。然后同样的步骤，对于下一层，当然每次划分都需要经过 ① 脐部划分之后再进行，比较验证集精度来进行评估。

后剪枝

后剪枝就直接对 4-2 的未剪枝的决策树进行操作。从纹理层，也就是 ⑥ 开始操作，我们将它剪去，默认分支结果为好瓜，使用它所包含的验证集的{1,2,3,14}测试，看模型精度是否会更好。后面的也是一样的了。

注意：每次使用验证集都是直接使用它所包含的验证集的样本，而非所有，因为包含其它分支的样本进行测试对结果无影响。

比较

时间开销：
- 预剪枝：训练时间开销降低（不需要生成一次未剪枝的决策树），测试时间开销降低
- 后剪枝：训练时间开销增加（需要生成一次未剪枝的决策树），测试时间开销降低
过/欠拟合风险：
- 预剪枝：过拟合风险降低，欠拟合风险增加（没有生成过未剪枝的决策树，剪枝之前得到的信息不全面）
- 后剪枝：过拟合风险降低，欠拟合风险基本不变
泛化性能：后剪枝通常优于预剪枝