DanielLaah

《统计学习方法》笔记 (六) - 决策树(上)


本篇博客为《统计学习方法》笔记系列第6篇, 对应《统计学习方法》中第5章1-4节的内容. 主要介绍熵, 信息增益, 信息增益比, 基尼指数, ID3, C4.5, 决策树的剪枝等.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


决策树(decision tree)是一种基本的分类与回归方法. 它可以认为是if-then规则的集合, 也可以认为是定义在特征空间与类空间上的条件概率分布. 其主要优点是模型具有可读性, 分类速度快. 决策树学习通常包括3个步骤: 特征选择, 决策树的生成和决策树的修剪.

一. 决策树模型与学习

1.1 决策树模型

下图是一个决策树的示意图. 图中圆表示一个特征, 方框表示一个类.

1.2 决策树与if-then规则

可以将决策树看成一个if-then规则的集合. 其过程是这样的: 有决策树的根结点点到叶结点的每一条路径构建一条规则; 路径上内部结点的特征对应着规则的条件, 而叶结点的类对应着规则的结论. 这些规则具有一个重要性质: 互斥并完备. 这就是说, 每一个实例都被且仅被一条规则所覆盖.

1.3 决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布. 这一条件概率分布定义在特征空间的一个划分(partition)上. 将特征空间划分为互不相交的单元(cell)或区域(region), 并在每个单元定义一个类的概率分布就构成了一个条件概率分布.
下图为决策树与条件概率分布的示意图:

1.4 决策树学习

决策树学习的算法通常是一个递归地选择最优特征, 并根据该特征对训练数据进行分割, 使得对各个子数据集有一个最好的分类的过程. 如此递归地进行下去, 直到所有训练数据子集被基本正确分类, 或者没有合适的特征为止. 最后每个子集都被分到叶节点上, 即都有了明确的类. 这就生成了一颗决策树.
但是以上方法存在一个问题, 就是它虽然能对已知数据很好的分类, 但泛化能力较弱, 即可能发生过拟合. 此时就要对生成的决策树进行自下而上的剪枝处理, 将树变得更简单, 从而使他具有更好的泛化能力. 具体地, 去掉过分细分的叶结点, 使其回退到父结点甚至更高的结点, 然后将父结点或更高的结点改为新的叶结点.
如果特征数量过多, 也可以在决策树学开始的时候, 对特征进行选择, 只留下对训练数据由足够分类能力的特征.
可以看出, 决策树学习算法包含特征选择, 决策树的生成以及决策树的剪枝. 由于决策树表示一个条件概率分布, 所以深浅不同的决策树对应着不同复杂度的概率模型. 决策树的生成对只考虑局部最优, 而剪枝考虑全局最优.
决策树学习常用的算法有ID3, C4.5 和CART.

二. 特征选择

从第一节中我们了解到, 特征选择应该是选那些尽可能将类别区分开来的特征, 即分类能力强的特征. 描述这样能力的一个标准通常是信息增益或信息增益比.

2.1 信息增益

2.1.1 熵

首先给出熵的概念.
在信息论与概率统计中, 熵(entropy)是表示随机变量不确定性的度量. 设X是一个取有限个值得离散随机变量, 其概率分布为:
$$P(X=x_i)=p_i, i=1,2,…,n$$
则随机变量$X$的上定义为
$$H(X)=-\sum_{i=1}^np_i\log p_i$$
上式中, 当$p_i=0$时, 定义$0\log0=0$. 有定义可知, 信息熵只和随机变量$X$的分布有关, 而和$X$具体的取值无关, 所以也可以将$X$的熵记作$H(p)$, 即
$$H(p)=-\sum_{i=1}^np_i\log p_i$$
熵越大, 随机变量的不确定性就越大.
$$0\le H(p)\le\log n$$
当随机变量只取两个值, 例如0, 1时, 熵为:
$$H(p)=-p\log p - (1-p)\log(1-p)$$
这时, 熵$H(p)$随概率p变化的曲线如下图所示

当$p=0$或$p=1$时$H(p)=0$, 随机变量完全没有不确定性. 当$p=0.5$时, $H(p)=1$, 熵取值最大, 随机变量不确定性最大.
下面来看看条件熵.
设有随机变量$(X, Y)$, 其联合概率分布为
$$P(X=x_i, Y=y_i)=p_{ij}, i=1,2,…,n; j=1,2,…,m$$
条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性. 随机变量$X$给定的条件下随机变量$Y$的条件熵(conditional entropy)$H(Y|X)$, 定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望.
$$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$$
这里, $p_i=P(X=x_i), i=1,2,…,n$
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时, 所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy). 此时, 如果有0概率, 令$0log0=0$

2.2 信息增益

信息增益(information gain)表示得知特征$X$的信息而使得类$Y$的信息不确定性减少的程度. 下面给出定义:
特征$A$对训练数据集$D$的信息增益$g(D, A)$, 定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$只差, 即
$$g(D, A)=H(D)-H(D|A)$$
一般地, 熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息(mutual information). 决策树学习中的信息增益等价于训练数据集中类与特征的互信息.
决策树学习应用信息增益准则选择特征. 给定训练数据集D和特征A, 经验熵H(D)表示对数据集D进行分类的不确定性. 而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性. 那么它们的差, 即信息增益, 就表示由于特征A而使得对数据集D的分类的不确定性减少的程度. 显然, 对于数据集D而言, 信息增益依赖于特征, 不同的特征往往具有不同的信息增益. 信息增益大的特征具有更强的分类能力.
根据信息增益准则的特征选择方法是:对训练数据集(或子集)D, 计算其每个特征的信息增益, 并比较它们的大小, 选择信息增益最大的特征. 于是信息增益的算法如下:
输入: 训练数据集$D$和特征$A$
输出:特征$A$对训练数据集$D$的信息增益$g(D,A)$
(1)计算数据集$D$的经验熵$H(D)$
$$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log\frac{|C_k|}{|D|}$$
(2)计算特征$A$对数据集$D$的经验条件熵$H(D|A)$
$$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log\frac{|D_{ik}|}{|D_i|}$$
(3)计算信息增益
$$g(D,A)=H(D)-H(D|A)$$
上述算法掌握熟练后, 可以使用表5.1对自己测试, 然后对照例5.2看看自己有没有掌握.

2.3 信息增益比

信息增益存在一个缺陷, 就是当某一个特征包含很多值的时候, 信息增益会更倾向于选这种特征. 例如, 在之前的例子中, 我们把年龄改为如下

此时再计算对年龄的信息增益后发现$g(D, A)= H(D)-H(D|A)=H(D)-0=H(D)$, 这时对于这个特征的信息增益是最大的, 但这显然是个不合理的分法.
使用信息增益比(infomation gain ratio)可以对这一问题进行校正. 这是特征选择的另一准则.
下面给出信息增益比的定义:
特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$的经验熵$H(D)$之比:
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
其中,
$$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log\frac{|D_i|}{|D|}$$

三. 决策树的生成

当使用信息增益作为特征选择的准则来生成决策树时就是ID3算法, 当使用信息增益比时就是C4.5算法. 下面以ID3为例给出算法描述:
输入:训练数据集$D$, 特征集$A$, 阈值;
输出:决策树$T$.
(1)若$D$中所有实例属于同一类$C_k$, 则$T$为单结点树, 并将类$C_k$作为该结点的类标记, 返回$T$;
(2)若$A=Ø$, 则T为单结点树, 并将$D$中实例数最大的类$C_k$作为该结点的类标记, 返回$T$;
(3)否则, 计算$A$中各特征对$D$的信息增益, 选择信息增益最大的特征$A_g$;
(4)如果$A_g$的信息增益小于阈值, 则置$T$为单结点树, 并将$D$中实例数最大的类$C_k$作为该结点的类标记, 返回$T$;
(5)否则, 对$A_g$的每一可能值$a_i$, 依$A_g=a_i$将$D$分割为若干非空子集$D_i$, 将$D_i$中实例数最大的类作为标记, 构建子结点, 由结点及其子结点构成树$T$, 返回$T$;
通过ID3算法对前面的例子构造的决策树如下:

四. 决策树的剪枝

生成了决策树之后, 为了防止过拟合的问题, 需要对其进行剪枝处理.
在决策树学习中将已生成的树进行简化的过程称为剪枝()pruning). 具体地, 剪枝从已生成的树上裁掉一些子树或叶结点, 并将其根结点或父结点作为新的叶结点, 从而简化分类树模型.
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现. 设树$T$的叶结点个数为$|T|$, $t$是树$T$的叶结点, 该叶结点有$N_t$个样本点, 其中$k$类的样本点有$N_{tk}$个, $k=1,2,…,K, H_t(T)$为叶结点$t$上的经验熵, $a≥0$为参数, 则决策树学习的损失函数可以定义为.
$$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$$
其中经验熵为:
$$H_t(T)=-\sum_{k}\frac{|N_{tk}|}{|N_t|}\log\frac{|N_{tk}|}{|N_t|}$$
在损失函数中, 右边第一项记作
$$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}\log\frac{N_{tk}}{N_t}$$
这时有
$$C_{\alpha}(T)=C(T)+\alpha|T|$$
$C(T)$表示模型对训练数据的预测误差, 即模型与训练数据的拟合程度, $|T|$表示模型复杂度, 参数$\alpha\ge0$控制两者之间的影响.
决策树剪枝过程示意图:

剪枝的算法描述:
输入:生成算法产生的整个树$T$, 参数$\alpha$;
输出:修剪后的子树$T_\alpha$
(1)计算每个结点的经验熵
(2)递归地从树的叶结点向上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_B$与$T_B$, 其对应的损失函数值分别是$C_\alpha(T_B)$与$C_\alpha(T_A)$, 如果
$$C_\alpha(T_A)\le C_\alpha(T_B) \tag{5.15}$$
则进行剪枝, 即将父结点变为新的叶结点.
(3)返回(2), 直至不能继续为止, 得到损失函数最小的子树$T_a$
注意, 式(5.15)只需考虑两个树的损失函数的差, 其计算可以在局部进行. 所以, 决策树的剪枝算法可以由一种动态规划的算法实现(在实现算法时再进一步研究).