第5章 决策树

1．分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个if-then规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。

2．决策树学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是NP完全问题。现实中采用启发式方法学习次优的决策树。

决策树学习算法包括3部分：特征选择、树的生成和树的剪枝。常用的算法有ID3、C4.5和CART。

3．特征选择的目的在于选取对训练数据能够分类的特征。特征选择的关键是其准则。常用的准则如下：

（1）样本集合D 对特征A 的信息增益（ID3）

其中，H ( D )是数据集D 的熵，H ( D i ) 是数据集D i 的熵，H(D|A)是数据集D 对特征A 的条件熵。 D i 是D 中特征A AA取第i ii个值的样本子集，C k  是D 中属于第k kk类的样本子集。n 是特征A 取 值的个数，K KK是类的个数。

（2）样本集合D 对特征A AA的信息增益比（C4.5）

其中，g ( D , A ) 是信息增益，H ( D )是数据集D 的熵。

（3）样本集合D 的基尼指数（CART）

特征A 条件下集合D 的基尼指数：

4．决策树的生成。通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。决策树的生成往往通过计算信息增益或其他指标，从根结点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。

5．决策树的剪枝。由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点，从而简化生成的决策树。

特征选择

熵

熵只与X的分布有关，与X取值无关

定义0log0=0，熵是非负的

表示随机变量不确定性的度量

对数以2为底或以e为底(自然对数)，这时单位分别为比特(bit)或纳特(nat)，相差一个系数

条件熵

随机变量(X,Y)联合概率分布为

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

其中p i = P ( X = x i ) , i = 1 , 2 , … , n

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

信息增益

特征A 对训练数据集D DD的信息增益g ( D ∣ A )，定义为集合D 的经验熵H ( D )与特征A给定的条件下D DD的经验条件熵H ( D ∣ A )之差

熵H ( Y )与条件熵H ( Y ∣ X )的差称为互信息(mutual information)

决策树中的信息增益等价于训练数据集中的类与特征的互信息

考虑ID这种特征， 本身是唯一的。按照ID做划分， 得到的经验条件熵为0, 会得到最大的信息增益。所以， 按照信息增益的准则来选择特征， 可能会倾向于取值比较多的特征

信息增益比

• 使用信息增益比可以对上面倾向取值较多的特征的问题进行校正，这时特征选择的另一准则

其中， n 是特征取值的个数。

决策树的生成

ID3算法

输入：训练数据集D DD, 特征集A AA，阈值ϵ \epsilonϵ

输出：决策树T TT

如果D 中所有实例属于同一类C k ，则T 为单节点树，并将类C k 作为该节点的类标记，返回T 如果A 是空集，则T 为单节点树，并将实例数最多的类作为该节点类标记，返回T 计算g, 选择信息增益最大的特征A g 如果A g 的信息增益小于ϵ ，则置T 为单节点树，D 中实例数最大的类C k 作为类标记，返回T 否则，依A g = a i 将D划分若干非空子集D i ，D i 中实例数最大的类C k 作为类标记，构建子结点，由结点及其子结点 构成树T ，返回T D 训练集，A − A g 为特征集，递归调用前面步骤，得到T i ，返回T i 不过对于ID3算法来说，只有树的生成，所以该算法生成的树容易产生过拟合。

利用ID3算法，可以构建例5.1的树

C4.5的生成算法

与ID3相似，改用信息增益比来选择特征

输入：训练数据集D , 特征集A ，阈值ϵ

如果D 属于同一类C k  ，T 为单节点树，类C k 作为该节点的类标记，返回T 如果A 是空集, 置T 为单节点树，实例数最多的作为该节点类标记，返回T 计算g , 选择信息增益比最大的特征A g 如果A g 的信息增益比小于ϵ，T 为单节点树，D 中实例数最大的类C k 作为类标记，返回T 否则，依A g = a i 将D划分若干非空子集D i ，D i 中实例数最大的类C k 作为类标记，构建子结点，由结点及其子结点 构成树T TT，返回T D i 训练集，A − A g 为特征集，递归调用前面步骤，得到T i ，返回T i

ID3和C4.5在生成上，差异只在准则的差异

决策树的剪枝

树的剪枝

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现的树T 的叶结点个数为∣ T ∣ ，t是树T 的叶结点，该结点有N t 个样本点，其中k kk类的样本点有N t 个，H t ( T ) (T)为叶结点t tt上的经验熵， α ⩾ 0为参数，决策树学习的损失函数可以定义为

其中

这时有

其中C ( T ) 表示模型对训练数据的误差，∣ T ∣表示模型复杂度，参数α ⩾ 0 控制两者之间的影响

较大的α 促使选择较简单的模型（树）

较小的α 促使选择较复杂的模型（树）

α = 0 以为只考虑模型与训练的拟合程度，不考虑模型的复杂度

剪枝算法

输入：生成算法生成的整个树T ，参数α

输出：修剪后的子树T α

计算每个结点的经验熵

递归地从树的叶结点向上回缩

假设一组叶结点回缩到其父结点之前与之后的整体树分别是T B 和T A ，其对应的损失函数分别是C α ( T A ) 和C α ( T B ) ，如果C α ( T A ) ⩽ C α ( T B ) )则进行剪枝，即将父结点变为新的叶结点返回2，直至不能继续为止，得到损失函数最小的子树T α

决策树的剪枝算法可以由一种动态规划的算法实现

CART

• 决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼系数最小化准则，并进行特征选择，生成二叉树