《统计学习方法》笔记五 决策树

知识概要

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

决策树与if-then规则

可以把决策树看成一个if-then规则的集合，则应满足互斥并且完备，即每一条实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布，定义在特征空间的一个划分上，将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。设X为表示特征的随机变量，Y为表示类的随机变量，则条件概率分布表示为P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合。

特征选择

包括以下

• 信息增益
• 信息增益比
• 基尼指数

特征选择在于选取对训练数据具有分类能力的特征，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比。

信息增益

1 熵

熵表示随机变量不确定性的度量，熵越大，随机变量的不确定性越大。设X是一个取有限个值的离散随机变量，概率分布为

P(X = xi) = pi,  i = 1,2,...n

则随机变量X的熵定义为

以2或e为底，此时熵的单位分别称作比特（bit）或纳特（nat），熵只依赖X的分布，与X的取值无关，所以也可记为H(p)

2 条件熵

H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性 

定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

信息增益比

当训练数据集的经验熵大的时候，信息增益值偏大，反之偏小，使用信息增益比校正。

基尼指数

CART中生成分类树中使用，用基尼指数选择最优特征，同时决定该特征的最优二值且分点。

决策树的生成

ID3算法

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

C4.5

与ID3相似，在生成过程中，用信息增益比来选择特征

决策树的剪枝

决策树生成往往对训练数据分类很准确，但对未知的测试数据的分类却没有那么准确，即过拟合。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已生成的树进行简化，成为剪枝（pruning），具体指从生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点。

设树T的叶结点个数为| T | , t 是树T的叶结点有 Nt 个样本点，其中k类的样本点有 Ntk 个，k = 1, 2, · · · , K，Ht(T) 为叶结点 t 上的经验熵，a ≥ 0为参数，则决策树学习的损失函数可以定义为

CART算法

可用于分类也可用于回归，给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值是“是”和“否”，左分支取值为是，右取值为否，等价于递归的二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

由决策树生成和剪枝两个步骤组成。

回归树生成

一个回归树对应输入空间（即特征空间）的一个划分以及在划分的单元上的输出值，假设已将输入空间划分为M个单元，R1，...RM，并在每个单元RM上有一个固定的输出值Cm，则回归树模型可表示为

如何划分，选择第j个变量和它的取值s，作为切分变量和且分点，并定义两个区域

然后寻找足有切分变量j和最优切分点s

对固定输入变量j可找到最优切分点s

遍历所有输入变量，找到最优的切分变量j，构成一个对（j，s），依次将输入空间划分成两个区域，对每个区域重复上述步骤，直到满足停止条件为止。这样的回归树称为最小二乘回归树。

分类树生成

输入：训练数据集D，停止计算条件

输出：CART决策树

1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A = a的测试为"是"或者“否”将D分割为D1和D2两部分，计算其基尼系数。

2）在所有可能的特征A以及他们所有可能的切分点a中，选择基尼系数最⼩小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点⽣生成两个⼦子结点，将训练数据集依特征分配到两个⼦子结点中去。

3）对两个⼦子结点递归地调⽤用上述两个步骤，直⾄至满⾜足停⽌止条件。

4）⽣生成CART决策树

CART剪枝

CART剪枝算法从“完全⽣生⻓长”的决策树的底端减去⼀一些⼦子树，使决策树变⼩小（模型变简单），从⽽而能够对未知数据有更更准确的预测