第五节–决策树

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

一.决策树模型与学习

1.决策树模型

分类决策树是一种描述对实例进行分类的树形结构.决策树由结点(node)和有向边(directed edge)组成.结点有三种类型：根结点(root node),内部结点(internal node)和叶结点(leaf node).内部结点表示一个特征或属性,叶结点表示一个类

用决策树分类,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时每一个子结点对应着该特征的一个取值.如此递归地对实例进行测试并分配,直至达到叶结点,最后将实例分到叶结点的类中

下图是一个决策树的示意图

from IPython.display import Image
Image(filename="./data/5_1.png",width=500)

2.决策树与if-then规则

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

3.决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布,这一条件概率分布定义在特征空间的一个划分(partition)上.将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布.决策树一条路径对应于划分中的一个单元.决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成.假设X为表示通知的随机变量,Y为表示类的随机变量,那么这个条件概率分布可以表示为$P(Y|X)$.X取值于给定划分下单元的集合,Y取值于类的集合.各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大.决策树分类时将该结点的实例强行分到条件概率大的那一类去

Image(filename="./data/5_3.png",width=500)

图a示意地表示了特征空间的一个划分.图中的大正方形表示特征空间.这个大正方形被若干个小矩形分割,每个小矩形表示一个单元.特征空间划分上的单元构成了一个集合,X取值为单元的集合.为简单起见,假设只有两类：正类和负类,即Y取值为+1和-1.小矩形中的数字表示单元的类.图b示意地表示特征空间划分确定时,特征(单元)给定条件下类的条件概率分布.图b中条件概率分布对应于图a的划分.当某个单元c的条件概率满足$P(Y=+1|X=c)>0.5$时,则认为这个单元属于正类,即落在这个单元的实例都被视为正例.图c为对应于图b中条件概率分布的决策树

4.决策树学习

决策树学习,假设给定训练数据集：
D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} D={ (x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}

其中,$x_i={\left(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}\right)}^{\mathrm{T}}$为输入实例(特征向量),n为特征个数, y i ∈ { 1 , 2 , ⋯   , K } y_{i} \in\{1,2, \cdots, K\} yi​∈{ 1,2,⋯,K}为类标记,$i=1,2,\cdots ,N$,N为样本容量.学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类

决策树学习本质上是从训练数据集中归纳出一组分类规则.与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有.我们需要的是一个与训练数据矛盾较小的决策树.同属具有很好的泛化能力.从另一个角度看,决策树学习是由训练数据集估计条件概率模型.基于特征空间划分的类的条件概率模型有无穷多个.我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测

二.条件选择

1.特征选择问题

特征选择在于选取对训练数据具有分类能力的特征.这样可以提高决策树学习的效率.如果利用一个特征进行分类的结果与随机分类的结果没有很大差别.则称这个特征是没有分类的能力的.经验上扔掉这样的特征对决策树学习的精度影响不大,通常特征选择的准则是信息增益或信息增益比

首先通过一个例子来说明特征选择问题

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	是	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

希望通过所给的训练数据学习一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请人的特征利用决策树决定是否批准贷款申请

from IPython.display import Image
Image(filename="./data/5_4.png",width=500)

两个决策树都可以从此延续下去,问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则.直观上,如果一个特征具有更好的分类能力,或者说按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有最好的分类,那么就更应该选择这个特征.信息增益(information gain)就能够很好地表示这一直观的准则

2.信息增益

在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量.设X是一个取有限个值的离散随机度量,其概率分布为：
$$P\left(X=x_i\right)=p_i,i=1,2,\cdots ,n$$

则随机变量X的熵定义为：
$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$

若$p_{\mathrm{i}}=0$,则定义$0\log 0=0$.通常对数以2为底数或以e为底(自然对数),这时熵的单位分布称作比特(bit).由定义可知,熵只依赖X的分布.而与X的取值无关,所以也可将X的熵记作$H(p)$,即：
$$H(p)=-\sum _{i=1}^n{p}_i\log p_i$$

熵越大,随机变量的不确定性就越高.从定义可验证：
$$0⩽H(p)⩽\log n$$

当随机变量只取两个值,例如1,0时,即X的分布为：
$$P(X=1)=p,P(X=0)=1-p,0⩽p⩽1$$

熵为：
$$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$$

这时,熵$H(p)$随概率p变化的曲线如下图(单位为比特)：

Image(filename="./data/5_5.png",width=500)

当p=0或p=1时$H(p)=0$,随机变量完全没有不确定性.当p=0.5时,$H(p)=1$,熵取值最大,随机变量不确定性最大

设有随机变量$(X,Y)$,其联合概率分布为：
$$P\left(X=x_i,Y=y_j\right)=p_{ij},i=1,2,\cdots ,n;j=1,2,\cdots ,m$$

条件熵$H(Y|X)$表示在已知随机变量X的条件下随机变量Y的不确定性.随机变量$X$给定的条件下随机变量$Y$的条件熵(conditional entropy)$H(Y|X)$.定义为$X$给定条件下Y的条件概率分布的熵对$X$的数学期望：
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H\left(Y|X=x_i\right)$$

这里,$p_i=P\left(X=x_i\right),i=1,2,\cdots ,n$

信息增益(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,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征

设训练数据集为D,|D|表示其样本容量,即样本个数.设有K个类$C_k$,k=$1,2,\cdots ,K$,$\left|C_k\right|$为属于类$C_k$的样本个数,${\sum }_{k=1}^K\left|C_k\right|=|D|$.设特征A有n个不同的取值 { a 1 , a 2 , ⋯   , a n } \left\{a_{1}, a_{2}, \cdots, a_{n}\right\} { a1​,a2​,⋯,an​},根据特征A的取值将D划分为n个子集$D_1,D_2,\cdots ,D_n$,$\left|D_t\right|$为$D_i$的样本个数,${\sum }_{i=1}^n\left|D_i\right|=|D|$.记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$,即$D_{lk}=D_i\cap C_k$,$\left|D_{ik}\right|$为$D_{ik}$的样本个数,于是信息增益的算法如下：

信息增益的算法
输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益$g(D,A)$

1. 计算数据集D的经验熵$H(D)$
   $$H(D)=-\sum _{k=1}^K\frac{\left|C_k\right|}{|D|}{\log }_2\frac{\left|C_k\right|}{|D|}$$
2. 计算特征A对数据集D的经验条件熵$H(D|A)$
   $$H(D|A)=\sum _{i=1}^n\frac{\left|D_i\right|}{|D|}H\left(D_i\right)=-\sum _{i=1}^n\frac{\left|D_i\right|}{|D|}\sum _{k=1}^K\frac{\left|D_{ik}\right|}{\left|D_i\right|}{\log }_2\frac{\left|D_{ik}\right|}{\left|D_i\right|}$$
3. 计算信息增益
   $$g(D,A)=H(D)-H(D|A)$$

实例1：对前面贷款所给的训练数据集D,根据信息增益准则选择最优特征

Image(filename="./data/5_6.png",width=500)

最后,比较各特征的信息增益值,由于特征$A_3$(有自己的房子)的信息增益值最大,所以选择特征$A_3$作为最优特征

3.信息增益比

信息增益比的大小是相对于训练数据集而言的,并没有绝对意义.在分类问题困难时,也就是说在训练数据集的经验熵大的时候,信息增益值会偏大,反之,信息增益值会偏小.使用信息增益比(information gain ratio)可以对这一问题进行校正.这是特征选择的另一准则

特征A对训练数据集D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集D的经验熵$H(D)$之比：
$$g_R(D,A)=\frac{g(D,A)}{H(D)}$$

三.决策树的生成

1.ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树.具体方法是：从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再从子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止.最后得到一个决策树.ID3相当于用极大似然法进行概率模型的选择

ID3算法
输入：训练数据集D,特征集A,阈值$\mathcal{E}$
输出：决策树T

实例2：对贷款表的训练数据集,利用ID3算法建立决策树

from IPython.display import Image

Image(filename="./data/5_7.png",width=500)

选择信息增益最大的特征$A_2$(有工作)作为结点的特征.由于$A_2$有两个可能取值,从这一结点引出两个子结点：一个对应"是"(有工作)的子结点,包含3个样本,它们属于同一类,所以这是一个叶结点,类标记为"是";另一个是对应"否"(无工作)的子结点,包含6个样本,它们也属于同一类,所以这也是一个叶结点,类标记为"否"

这样生成一个如下图所示的决策树,该决策树只用了两个特征(有两个内部结点)：

Image(filename="./data/5_8.png",width=500)

实例：用ID3对天气数据集样本数据分析,生成决策树

Day	Outlook	Temperature	Humidity	Wind	Play ball
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

from IPython.display import Image

Image(filename="./data/5_12.png",width=500)

Outlook属性有三种取值—sunny,overcast和rain,分对应3个分支,将数据集划分为3个子集$S_{sunny}$,$S_{overcast}$和$S_{rain}$

Image(filename="./data/5_13.png",width=500)

然后,在Sunny分支下,递归调用Decision Tree($S_{sunny}$,R-outlook,C)分别计算得Temperature属性的信息增益增益度为0.57,Humidity属性的信息增益度为0.97,Wind属性的信息增益度为0.02.因此在此分支下再以属性Humidity对子集$S_{sunny}$划分,得到子集$S{S}_{hign}$和$S{S}_{normal}$,这两个子集的所有样本都属于同一类别,因此停止树的分裂,添加两个叶子节点,并写上子集的类别即可

Image(filename="./data/5_14.png",width=500)

在生成决策树以后,可以方便地提取决策树描述的知识,并表示成if-then形式的分类规则.沿着根节点到叶子节点每一条路径对应一条决策规则.如IF {Outlook=Sunny,Humidity=High} then {Play ball=No}

在生成决策树的过程中,除了要选择测试属性,还要判断是否停止树的分裂.停止树的分裂的条件如下,只要满足以下3个条件中的一条,即可停止树的分支构造：

1. 子集中的所有记录属于同一类时
2. 所有的记录具有相同的属性值
3. 提前终止树的分裂

ID3采用信息增益度作为评价标准.信息增益度的缺点是倾向于选择取值较多的属性,但在有些情况下这类属性可能不会提供太多有价值的信息.其次ID3算法只能对离散型属性的数据集构造决策树

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

2.C4.5的生成算法

C4.5算法与ID3算法相似,C4.5算法对ID3算法进行了改进.C4.5在生成的过程中,用信息增益比来选择特征

C4.5对ID3算法进行了以下几方面的改进：

1. 用信息增益率来选择最佳分裂属性,弥补了用信息增益选择属性时偏向选择取值多的属性的不足
2. 在树构造过程中进行剪枝
3. 能够完成对连续属性的离散化处理
4. 能够对不完整数据进行处理

C4.5的生成算法
输入：训练数据集D,特征集A,阀值$\mathcal{E}$
输出：决策树T

根据信息增益率来选择属性

信息增益率(gain ratio)定义为：
$$GainRatio(X,T)=\frac{\mathrm{Gain}(X,T)}{\text{ SplitInfo }(X,T)}$$

$$SplitInfo(Outlook,T)=-5/14\times {\log }_2(5/14)-4/14\times {\log }_2(4/14)-5/14\times {\log }_2(5/14)=1.577$$
Outlook的增益率是0.25/1.577=0.16

构造过程中进行剪枝

通常进行剪枝是为了处理由于数据中的噪声和离群点导致的过分拟合问题,剪枝一般采用自下而上的方式,在生成决策树后进行

处理连续属性值

C4.5算法对连续属性的处理有两种方法：一种是基于信息增益度的;另一种是基于Risannen的最小描述长度原理

实例：用下表的数据,使用C4.5建立决策树的算法

天气	温度	湿度	风速	适动
晴	炎热	高	弱	取消
晴	炎热	高	强	取消
阴	炎热	高	弱	进行
雨	适中	高	弱	进行
雨	寒冷	正常	弱	进行
雨	寒冷	正常	强	取消
阴	寒冷	正常	强	进行
晴	适中	高	弱	取消
晴	寒冷	正常	弱	进行
雨	适中	正常	弱	进行
晴	适中	正常	强	进行
阴	适中	高	强	进行
阴	炎热	正常	弱	进行
雨	适中	高	强	取消

from IPython.display import Image
Image(filename="./data/5_15.png",width=500)

Image(filename="./data/5_16.png",width=500)

Image(filename="./data/5_17.png",width=500)

四.决策树的剪枝

决策树生成算法递归地产生决策树,直到不能继续下去为止.这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即出现过拟合现象.过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化

在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning).具体地,剪枝从已生成的树上裁掉一些子树或叶结点,并将其根结点或父结点作为新的叶结点,从而简化分类树模型

介绍一种简单的决策树学习的剪枝算法

决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现

决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合,而决策树剪枝通过优化损失函数还考虑了减小模型复杂度.决策树生成学习局部的模型,而决策树剪枝学习整体的模型

树的剪枝算法
输入：生成算法产生的整个T,参数$\alpha$
输出：修剪后的子树$T_{\alpha }$

1. 计算每个结点的经验熵
2. 递归地从树的叶结点向上回缩
3. 返回(2),直至不能继续为止,得到损失函数最小的子树$T_{\alpha }$

Image(filename="./data/5_9.png",width=500)

决策树的剪枝算法可以由一种动态规划的算法实现.类似的动态规划算法可参考文献

五.CART算法

CART同样由特征选择,树的生成及剪枝组成,既可以用于分类也可以用于回归.以下将用于分类与回归的树统称为决策树

CART的输入和输出变量可以是离散型和连续型,而C4.5的输出变量只能是离散型

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

CART算法由以下两步组成：

1. 决策树生成：基于训练数据集生成决策树,生成的决策树要尽量大
2. 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准

1.CART生成

决策树的生成就是递归地构建二叉决策树的过程.对回归树用平方误差最小化准则,对分类树用基尼指数(Gini index)最下化准则,进行特征选择,生成二叉树

基尼指数：在分类问题中,假设有K个类,样本点属于第k类的概率为$p_k$,则概率分布的基尼指数定义为：
$$\mathrm{Gini}(p)=\sum _{k=1}^K{p}_k\left(1-p_k\right)=1-\sum _{k=1}^K{p}_k^2$$

对于二类分类问题,若样本点属于第1个类的概率是p,则概率分布的基尼指数为：
$$\mathrm{Gini}(p)=2p(1-p)$$

对于给定的样本集合D,其基尼指数为：
$$\mathrm{Gini}(D)=1-\sum _{k=1}^K{\left(\frac{\left|C_k\right|}{|D|}\right)}^2$$
这里,$C_k$是D中属于第k类的样本子集,K是类的个数

如果样本结合D根据特征A是否取某一可能值$a$被分割成$D_1$和$D_2$两部分,即：
D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } , D 2 = D − D 1 D_{1}=\{(x, y) \in D | A(x)=a\}, \quad D_{2}=D-D_{1} D1​={ (x,y)∈D∣A(x)=a},D2​=D−D1​

则在特征A的条件下,集合D的基尼指数定义为：
$$\mathrm{Gini}(D,A)=\frac{\left|D_1\right|}{|D|}\mathrm{Gini}\left(D_1\right)+\frac{\left|D_2\right|}{|D|}\mathrm{Gini}\left(D_2\right)$$

基尼指数$\mathrm{Gini}(D)$表示集合D的不确定性,基尼指数$\mathrm{Gini}(D,A)$表示经A=a分割后集合D的不确定性,基尼指数值越大,样本结合的不确定性也就越大,这一点与熵相似

Image(filename="./data/5_10.png",width=500)

实例3：根据贷款表所给训练数据集,应用CART算法生成决策树

Image(filename="./data/5_11.png",width=500)

3.CART剪枝

CART剪枝算法从"完全生长"的决策树的底端剪去一些子树,便决策树变小(模型变简单),从而能够对未知数据有更准确的预测.CART剪枝算法由两步组成,首先从生成算法产生的决策树$T_0$底端开始不断剪枝,直到$T_0$的根结点,形成一个子树序列 { T 0 , T 1 , ⋯   , T n } \left\{T_{0}, T_{1}, \cdots, T_{n}\right\} { T0​,T1​,⋯,Tn​};然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树

3.树选择

因为在树生成过程中可能存在不能提高分类纯度的划分节点,且存在过拟合训练数据的情况,这时需要使用一份单独的测试数据来评估每棵剪枝树的预测性能,从而选取最优树

实例：割草机制造商欲把城市中的家庭成分愿意购买割草机和不愿意购买的两类.在这个城市中随机抽取12个拥有割草机的家庭和12个非拥有割草机的家庭作为样本.这里的自变量是收入($x_1$)和草地面积($x_2$).类别边浪有两个类别：拥有和非拥有

观察序号	收入(千美元)	草地面积(平方尺)	拥有者=1,非拥有者=2
1	60	18.4	1
2	80.5	16.8	1
3	64.8	21.6	1
4	61.5	20.8	1
5	87	23.6	1
6	110.1	19.2	1
7	108	17.6	1
8	82.8	22.4	1
9	69	20	1
10	93	20.8	1
11	51	22	1
12	81	20	1
13	75	19.6	2
14	52.8	20.8	2
15	64.8	17.4	2
16	52.8	20.2	2
17	84	17.6	2
18	49.2	17.6	2
19	59.4	16	2
20	66	18.4	2
21	47.4	16.4	2
22	33	18.8	2
23	51	14	2
24	63	14.8	2

将表图例

from IPython.display import Image
Image(filename="./data/5_18.png",width=800)

在使用CART算法时,首先使用$x_2=19$进行分类.由图可以直观地发现两个矩形部分更加同质(即统一类别的点更多地聚集在一起)

Image(filename="./data/5_19.png",width=500)

通过观察得知,每一个矩形都是同质的.即包含一种类别的点.该算法每一次划分都将节点划分为两个子节点

Image(filename="./data/5_20.png",width=600)