监督学习_决策树

异世界.png

[TOC]

决策树(Decision Tree)

决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶结点表示类别。从顶部根结点开始，所有样本聚在一起。经过根结点的划分，样本被分到不同的子结点中。再根据子结点的特征进一步划分，直至所有样本都被归到某一个类别(即叶结点)中。

决策树作为最基础、最常见的有监督学习模型，常被用于分类问题和回归问题，在市场营销和生物医药等领域尤其受欢迎，主要因为树形结构与销售、诊断等场景下的决策过程十分相似。将决策树应用集成学习的思想可以得到随机森林、梯度提升决策树等模型。

决策树的生成包含了特征选择、树的构造、树的剪枝三个过程

特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。

如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，称这个特征是没有分类能力的。

经验上扔掉这样的特征对决策树学习的精度影响不大。

通常特征选择的准则是信息增益或信息增益比。

信息增益

在信息论与概率统计中，熵(entropy)是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为

$$P(X=x_i)=p_i,i=1,2,...,n$$

则随机变量X的熵定义为

$$H(X)=-\sum_{i=1}^{n}{p_i \log (p_i)}$$

在式中，若$p_i＝0$，则定义$0log0＝0$。

通常，式中的对数以2为底或以e为底(自然对数)，这时熵的单位分别称作比特(bit)或纳特(nat)。

由定义可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵记作$H(p)$，即

$$H(p)=-\sum_{i=1}^{n}{p_i \log {(p_i)}}$$

熵越大，随机变量的不确定性就越大。从定义可验证

$$0 \leq H(p) \leq log(n)$$

当随机变量只取两个值，例如1，0时，即X的分布为

$$P(X=1)=p,P(X=0)=1-p,0 \leq p \leq 1$$

熵为

$$H(p)=-p \log_{2}{p}-(1-p) \log_2(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,...,n$$

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

随机变量$X$给定的条件下随机变量$Y$的条件熵(conditional entropy)$H(Y|X)$，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望

$$H(Y|X)=\sum_{i=1}^{n}{p_iH(Y|X=x_i)}$$

这里，$p_i＝P(X＝x_i),i＝1,2,...,n$。

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

此时，如果有0概率，令$0log0＝0$。

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

信息增益比

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。

使用信息增益比(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)}$$

ID3—最大信息增益

对于样本集合$D$，类别数为$K$，数据集$D$的经验熵表示为

$$H(D)=-\sum_{k=1}^{K}{\frac{|C_k|}{|D|} log_2{\frac{|C_k|}{|D|}}}$$

其中$C_k$是样本集合$D$中属于第$k$类的样本子集，$|C_k|$为该子集的元素个数，$|D|$为样本集合的元素个数。

然后计算某个特征$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_2{\frac{|D_{ik}|}{|D_i|}}})}$$

其中，$D_i$表示$D$中特征$A$取第$i$个值的样本子集，$D_{ik}$表示$D_i$中属于第$k$类的样本子集。

于是信息增益$g(D,A)$可以表示为二者之差，可得

$$g(D,A)=H(D)-H(D|A)$$

计数	年龄	收入	学生	信誉	是否购买
64	青	高	否	良	不买
64	青	高	否	优	不买
128	中	高	否	良	买
60	老	中	否	良	买
64	老	低	是	良	买
64	老	低	是	优	不买
64	中	低	是	优	买
128	青	中	否	良	不买
64	青	低	是	良	买
132	老	中	是	良	买
64	青	中	是	优	买
32	中	中	否	优	买
32	中	高	是	良	买
64	老	中	否	优	不买

有了上面的这些概念，我们就可以手工实现以下$ID3$算法的决策树生成过程。 (1) 计算对给定样本分类所需的信息熵。 如表所示，类别标签$S$被分两类：买或不买。其中$S_1(买)=640$；$S_2(不买)=384$。 那么总$S=S_1+S_2=1024$。

​ $S_1$的概率$p_1=640/1024=0.625$；$S_2$的概率$P_2=384/1024=0.375$。

​

$$I(S_1,S_2)=I(640,384)=-p_1log(p_1)-p_2log(p_2)\\ =-(p_1log(p_1)+p_2log(p_2))=0.9544$$

(2) 计算每个特征的信息熵

​ ① 先计算“年龄”特征的熵。

​ 年龄共分三组：青年(0)、中年(1)、老年(2)。

​ 其中青年占总样本的概率为：$p(0)=384/1024=0.375$；

​ 青年中买/不买比例为：$128/256$， $S_1(买)=128$，$p_1=128/384$；$S_2(不买)=256$，$p_2=256/384$； $S=S_1+S_2=384$。 ​ 根据公式：

$$I(S_1,S_2)=I(128,256)=0.9183$$

​ 其中中年占总样本的概率为：$p(1)=256/1024=0.25$；中年买/不买比例为：$256/0$，$S_1(买）=256$， $p_1=1$；$S_2(不买)=0$，$p_2=0$；$S=S_1+S_2=256$。 ​ 根据公式：

$$I(S_1,S_2)=I(256,0)=0$$

​ 其中老年占总样本的概率为：$P(2)=384/1024=0.375$；老年买/不买比例为：$257/127$，

​ $S_1(买)=257$，$p_1=257/384$；$S_2(不买)=127$,$p_2=127/384$；$S=S_1+S_2=384$。 ​ 根据公式3.3：

$$I(S_1,S_2)=I(257,127)=0.9157$$

​ 那么，年龄的平均信息期望：

$$E(年龄)=0.375 \times 0.9183+0.25 \times 0+0.375 \times 0.9157=0.6877\\ G(年龄)=0.9544-0.6877=0.2667$$

​ ② 计算“学生”特征的熵。

​ 学生共分两组：是(0)、否(1)。

​ 学生的平均信息期望：

$$E(学生)=0.7811 \\ G(学生)=0.9544-0.7811=0 1733$$

③ 计算“收入”特征的熵。

​ 收入共分三组：高(0)、中(1)、低(2)。

​ 收入的平均信息期望：

$$E(收入)=0.9361 \\ G(收入)=0.9544-0.9361=0.0183$$

​ ④ 计算“信誉”特征的熵。

​ 信誉共分两组：优(0)、良(1)。

​ 信誉的平均信息期望：

$$E(信誉)=0.9048 \\ G(信誉)=0.9544-0.9048=0.0496$$

(3) 从所有的特征列中选出信息增益最大的那个作为根节点或内部节点—划分节点，划分整列，首次递归选择年龄列($G=0.2667$)来划分。 (4) 根据划分节点的不同取值来拆分数据集为若干个子集，然后删去当前的特征列， 再计算剩余特征列的信息熵。如果有信息增益，就重复第二步直至划分结束。

首次划分 后，青年和老年内含有多个标签，所以可以继续划分；中年选项就只剩一个标签，就作为叶子节点。 (5) 划分结束的标志为：子集中只有一个类别标签，停止划分。 按照这样的逻辑产生的决策树结果如图所示

​

从图中可以看到，使用信息熵生成的决策树要比自己计算的决策树层数少。

如果数据集的特征很多，那么使用信息熵创建决策树在结构上要明显优于其他方法，可形成最优的决策树结构。

​ ID3算法是比较早的机器学习算法，在1979年Quinlan就提出了该算法的思想。它以信息熵为度量标准，划分出决策树特征节点，每次优先选取信息量最多的属性，也就是使信息熵变为最小的属性，以构造一棵信息熵下降最快的决策树。 缺点

1. ID3算法的节点划分度量标准采用的是信息增益，信息增益偏向于选择特征值个数较多的特征。

   而取值个数较多的特征并不一定是最优的特征，所以需要改进选择属性的节点划分度量标准。

2. ID3算法递归过程中需要依次计算每个特征值的，对于大型数据会生成比较复杂的决策树：层次和分支都很多，而其中某些分支的特征值概率很小，如果不加忽略就会造成过拟合的问题。即决策树对样本数据的分类精度较高，但在测试集上，分类的结果受决策树分支的影响很大。

C4.5—最大信息增益比

特征$A$对于数据集$D$的信息增益比定义为

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

其中

$$H_A(D)=-\sum_{i=1}^{n}{\frac{|D_i|}{D}log_2{\frac{D_i}{D}}}$$

称为数据集$D$关于$A$的取值熵。

	年龄	长相	工资	写代码	类别
小A	老	帅	高	不会	不见
小B	年轻	一般	中等	会	见
小C	年轻	丑	高	不会	不见
小D	年轻	一般	高	会	见
小E	年轻	一般	高	不会	不见

针对上述问题，我们可以求出数据集关于每个特征的取值熵为

$$H_{年龄}=-\frac{1}{5}log_2{\frac{1}{5}}-\frac{4}{5}log_2{\frac{4}{5}}=0.722 \\ H_{长相}=-\frac{1}{5}log_2{\frac{1}{5}}-\frac{3}{5}log_2{\frac{3}{5}}-\frac{1}{5}log_2{\frac{1}{5}}=1.371 \\ H_{工资}=-\frac{3}{5}log_2{\frac{3}{5}}-\frac{1}{5}log_2{\frac{1}{5}}-\frac{1}{5}log_2{\frac{1}{5}}=1.371 \\ H_{写代码}=-\frac{3}{5}log_2{\frac{3}{5}}-\frac{2}{5}log_2{\frac{2}{5}}=0.971$$

于是可计算出各个特征的信息增益比为

$$g_R(D,年龄)=0.236 \\ g_R(D,长相)=0.402 \\ g_R(D,工资)=0.402 \\ g_R(D,写代码)=1$$

信息增益比最大的是特征“写代码”，但通过信息增益比，特征“年龄”对应的指标上升了，而特征“长相”和特征“工资”却有所下降。

• 缺点：信息增益比偏向取值较少的特征

• 原因： 当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

• 使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

CART—最大基尼指数(Gini)

Gini描述的是数据的纯度，与信息熵含义类似。

$$Gini(D)=1-\sum_{k=1}^{n}{(\frac{|C_k|}{|D|})^2}$$

CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义为

$$Gini(D|A)=\sum_{i=1}^{n}{\frac{|D_i|}{|D|}}Gini(D_i)$$

还是考虑上述的例子，应用CART分类准则，根据式（3.24）可计算出各个特征的Gini指数为

$$Gini(D|年龄=老)=0.4, Gini(D|年龄=年轻)=0.4, \\ Gini(D|长相=帅)=0.4, Gini(D|长相=丑)=0.4, \\ Gini(D|写代码=会)=0, Gini(D|写代码=不会)=0, \\ Gini(D|工资=高)=0.47, Gini(D|工资=中等)=0.3, \\ Gini(D|工资=低)=0.4$$

在“年龄”“长相”“工资”“写代码”四个特征中，我们可以很快地发现特征“写代码”的Gini指数最小为0，因此选择特征“写代码”作为最优特征，“写代码=会”为最优切分点。按照这种切分，从根结点会直接产生两个叶结点，基尼指数降为0，完成决策树生长。

构造准则比较

通过对比三种决策树的构造准则，以及在同一例子上的不同表现，我们不难总结三者之间的差异。

首先，ID3是采用信息增益作为评价标准，除了“会写代码”这一逆天特征外，会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。这在实际应用中是一个缺陷。比如，我们引入特征“DNA”，每个人的DNA都不同，如果ID3按照“DNA”特征进行划分一定是最优的（条件熵为0），但这种分类的泛化能力是非常弱的。因此，C4.5实际上是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。

其次，从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。

从应用角度，ID3和C4.5只能用于分类任务，而CART（Classification and Regression Tree，分类回归树）从名字就可以看出其不仅可以用于分类，也可以应用于回归任务（回归树使用最小平方误差准则）。

此外，从实现细节、优化过程等角度，这三种决策树还有一些不同。比如，ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

至此，我们从构造、应用、实现等角度对比了ID3、C4.5、CART这三种经典的决策树模型。这些区别与联系总结起来容易，但在实际应用中还需要读者慢慢体会，针对不同场景灵活变通。

剪枝操作

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。

在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型，提升模型的泛化能力。

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

设树$T$的叶结点个数为$|T|$，$t$是树$T$的叶结点，该叶结点有$N_t$ 个样本点，其中$k$类的样本点有$N_{tk}$个，$k＝1,2,...,K$，$H_t(T)$为叶结点$t$上的经验熵，$a \geq 0$为参数，则决策树学习的损失函数可以定义为

$$C_a(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}}}$$

在损失函数中，将式右端的第1项记作

$$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 \geq 0$控制两者之间的影响。

较大的$\alpha$促使选择较简单的模型(树)，

较小的$\alpha$促使选择较复杂的模型(树)。

$\alpha=0$意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当$\alpha$确定时，选择损失函数最小的模型，即损失函数最小的子树。

当$\alpha$值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

可以看出，决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合。

而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。

决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

定义的损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择

决策树的剪枝通常有两种方法，预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。

预剪枝

预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法。

1. 当树到达一定深度的时候，停止树的生长。

2. 当到达当前结点的样本数量小于某个阈值的时候，停止树的生长。

3. 计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。

预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。但如何准确地估计何时停止树的生长（即上述方法中的深度或阈值），针对不同问题会有很大差别，需要一定经验判断。

且预剪枝存在一定局限性，有欠拟合的风险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著上升。

后剪枝

后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。

剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。

相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。

常见的后剪枝方法包括错误率降低剪枝(Reduced Error Pruning，REP)、悲观剪枝(Pessimistic Error Pruning，PEP)、代价复杂度剪枝(Cost Complexity Pruning，CCP)、最小误差剪枝(Minimum Error Pruning，MEP)、CVP(Critical Value Pruning)、OPP(Optimal Pruning)等方法，这些剪枝方法各有利弊，关注不同的优化角度。

CART剪枝

CART的代价复杂剪枝CCP

代价复杂剪枝主要包含以下两个步骤。

1. 从完整决策树$T_0$开始，生成一个子树序列$\{T_0,T_1,*,...,T_n\}$，其中$T_{i+1}$由$T_i$生成，$T_n$为根节点。
2. 在子树序列中，根据真实误差选择最佳的决策树。

步骤1从$T_0$开始，裁剪中$T_i$关于训练数据集合误差增加最小的分支以得到$T_{i+1}$。

具体地，当一棵树$T$在结点$t$处剪枝时，它的误差增加可以用$R(t)−R(T_t)$表示，其中$R(t)$表示进行剪枝之后的该结点误差，$R(T_t)$表示未进行剪枝时子树$T_t$的误差。

考虑到树的复杂性因素，我们用$|L(T_t)|$表示子树$T_t$的叶子结点个数，则树在结点$t$处剪枝后的误差增加率为

$$\alpha = \frac{R(t)-R(T_t)}{|L(T_t)|-1}$$

在得到$T_i$后，我们每步选择$\alpha$最小的结点进行相应剪枝。

用一个例子简单地介绍生成子树序列的方法。

假设把场景中的问题进行一定扩展，女孩需要对80个人进行见或不见的分类。

假设根据某种规则，已经得到了一棵CART决策树$T_0$，如图所示

此时共5个内部结点可供考虑，其中

$$a(t_0)=\frac{25-5}{6-1}=4, \\ a(t_1)=\frac{10-(1+2+0+0)}{4-1}=2.33, \\ a(t_2)=\frac{5-(1+1)}{2-1}=3, \\ a(t_3)=\frac{4-(1+2)}{2-1}=1, \\ a(t_4)=\frac{4-0}{2-1}=4$$

可见$\alpha (t_3)$最小，因此对进$t_3$进行剪枝，得到新的子树$T_1$，如图所示。

而后继续计算所有结点对应的误差增加率，分别为$\alpha(t_1)=3$，$\alpha(t_2)=3$，$\alpha(t_4)=4$。因此对$t_1$进行剪枝，得到$T_2$，如图所示。

此时$\alpha (t_0)=6.5$，$\alpha (t_2)=3$，选择$t_2$进行剪枝，得到$T_3$。

于是只剩下一个内部结点，即根结点，得到$T_4$。

在步骤2中，我们需要从子树序列中选出真实误差最小的决策树。

CCP给出了两种常用的方法：

1. 一种是基于独立剪枝数据集，该方法与REP类似，但由于其只能从子树序列$\{ T_0,T_1,...,T_n \}$中选择最佳决策树，而非像REP能在所有可能的子树中寻找最优解，因此性能上会有一定不足。
2. 另一种是基于$k$折交叉验证，将数据集分成$k$份，前$k−1$份用于生成决策树，最后一份用于选择最优的剪枝树。重复进行$N$次，再从这$N$个子树中选择最优的子树。

代价复杂度剪枝使用交叉验证策略时，不需要测试数据集，精度与REP差不多，但形成的树复杂度小。

而从算法复杂度角度，由于生成子树序列的时间复杂度与原始决策树的非叶结点个数呈二次关系，导致算法相比REP、PEP、MEP等线性复杂度的后剪枝方法，运行时间开销更大。