决策树学习笔记

机器学习

决策树是依托于决策一步步建立起来的树形数据模型。
建立决策树时需要解决的问题有：

• 1.数据如何分割
• 2.何时停止数据分割
• 3.如何剪枝

1. 数据划分

划分数据主要目的就是为了让数据集从无序变的有序，根据描述数据无序程度的方法不同，有多种划分数据的方法。

1.1 基于信息增益的节点划分方法 ID3

ID3是一种基于信息增益的数据分割方法

1.1.1 描述数据的无序程度——信息熵

熵(entropy)是度量集合纯度的一种常用指标，计算方法为：
$Entropy(D) = -\sum_{k=1}^{n}p_klog_2p_k$
其中n代表样本共有n类，$p_k$表示第k类样本所占的比例。

例：节点D的数据集如下，该数据集根据描述了西瓜的各种特征并且标注了该瓜是不是好瓜：

则该节点的信息熵为：
$Entropy(D)=-\sum_{k=1}^{2}p_klog_2p_k=-(\frac{8}{17})*log_2(\frac{8}{17})-(\frac{9}{17})*log_2(\frac{9}{17})=0.998$
注：
计算熵时约定：若$p=0$，则$plog_2p=0$
$Entropy(D)$最小值是0，最大值为$log_2n$
熵值越小，$D$的纯度就越高。

1.1.2 节点分裂——信息增益

对于离散特征$a$，有$n$个可能的取值，记为$\{a_i,a_2,a_3,...,a_n\}$，若使用$a$对样本$D$进行划分，就会产生$n$个分支，则第$k$个分支包含了$D$中所有的在属性$a$上取值为$a_k$的样本，记为$D_k$。则用属性$a$对节点$D$进行划分所获得的信息增益(information gain):
$Gain(D,a) = Entropy(D)-\sum_{k=1}^{n}\frac{|D^k|}{|D|}Entropy(D^k)$
信息增益值越大，意味着用属性$a$来进行划分所获得的信息纯度提升越大。
同样，对于上面节点$D$的数据:
用属性“色泽”对节点进行划分，可知该属性有3个可能的取值{ 青绿， 乌黑， 浅白 }，用该属性对D进行划分，可得3个分支节点：
$D^1(色泽=青绿)$ 包含6个样本，3个是好瓜，3个否
$D^2(色泽=乌黑)$ 包含6个样本，4个是好瓜，2个否
$D^3(色泽=浅白)$ 包含5个样本，1个是好瓜、4个否
分别计算他们的信息熵：
$Entropy(D^1) = -(\frac{3}{6})*log_2(\frac{3}{6})-(\frac{3}{6})*log_2(\frac{3}{6}) = 1.000$
$Entropy(D^2) = -(\frac{4}{6})*log_2(\frac{4}{6})-(\frac{2}{6})*log_2(\frac{2}{6}) = 0.918$
$Entropy(D^3) = -(\frac{1}{5})*log_2(\frac{1}{5})-(\frac{4}{5})*log_2(\frac{4}{5}) = 0.722$
属性“色泽”的信息增益为：
$\begin{align*} Gain(D,“色泽”) &= Entropy(D)-\sum_{k=1}^{3}\frac{|D^k|}{|D|}Entropy(D^k)\\ &= 0.998 - \frac{6}{17}*1.000 - \frac{6}{17} * 0.918 - \frac{5}{17}*0.722\\ &= 0.109 \end{align*}$
同样的方法求出其他属性的信息增益：
$Gain(D,“根蒂”) = 0.143$
$Gain(D,“敲声”) = 0.141$
$Gain(D,“纹理”) = 0.381$
$Gain(D,“脐部”) = 0.289$
$Gain(D,“触感”) = 0.006$
此处，“纹理”的信息增益值较大，所以用“纹理”作为节点划分的特征。
第一步划分结束，然后再根据第一步划分出的节点一步步继续划分下去。

1.2 基于信息增益率的节点划分方法 C4.5

C4.5采用信息增益率作为数据分割的依据。
回到上边的例子，假如我们把数据集$D$中的第一列“编号”也作为一个属性，基于该属性划分节点，就会产生17个节点，我们可以求出
$Gain(D,“编号”) = 0.998-0*7 = 0.998$
远远大于其他的候选属性。
信息增益准则就是对可取数目较多的属性有所偏好。
为了消除这种情况C4.5算法采用“增益率(gain ratio)”来选择最佳的划分属性。信息增益率公式：
$Gain\_ratio(D, a) = \frac{Gain(D,a)}{IV(a)}$
其中
$IV(a) = -\sum_{k=1}^{n}\frac{|D^k|}{|D|}log_2\frac{|D^k|}{|D|}$
$IV(a)$称为属性的固有值，对于上面的数据集$D$，求得
$IV(色泽) = -\frac{6}{17}log_2\frac{6}{17}-\frac{6}{17}log_2\frac{6}{17}-\frac{5}{17}log_2\frac{5}{17} = 1.580(n=3)$
$IV(根蒂) = -\frac{8}{17}log_2\frac{8}{17}-\frac{7}{17}log_2\frac{7}{17}-\frac{2}{17}log_2\frac{2}{17} = 1.402 (n=3)$
$IV(敲声) = -\frac{5}{17}log_2\frac{5}{17}-\frac{2}{17}log_2\frac{2}{17}-\frac{10}{17}log_2\frac{10}{17} = 1.333 (n=3)$
$IV(纹理) = -\frac{3}{17}log_2\frac{3}{17}-\frac{9}{17}log_2\frac{9}{17}-\frac{5}{17}log_2\frac{5}{17} = 1.447 (n=3)$
$IV(脐部) = -\frac{7}{17}log_2\frac{7}{17}-\frac{4}{17}log_2\frac{4}{17}-\frac{6}{17}log_2\frac{6}{17} = 1.549 (n=3)$
$IV(触感) = -\frac{5}{17}log_2\frac{5}{17}-\frac{12}{17}log_2\frac{12}{17} = 0.874 (n=2)$
$IV(编号) = -\frac{1}{17}log_2\frac{1}{17}*17 = 4.088 (n=17)$
得到各属性的信息增益率：
$Gain\_ratio(D,“色泽”) = 0.069$
$Gain\_ratio(D,“根蒂”) = 0.102$
$Gain\_ratio(D,“敲声”) = 0.106$
$Gain\_ratio(D,“纹理”) = 0.263$
$Gain\_ratio(D,“脐部”) = 0.187$
$Gain\_ratio(D,“触感”) = 0.007$
$Gain\_ratio(D,“编号”) = 0.244$
此处“纹理”的信息增益率最大，所以将该属性作为节点划分的属性。

1.3 CART

CART(Classification And Regression Trees, 分类回归树)
CART既能是分类树，又能是回归树。

1.3.1 GINI指数构建分类树

GINI指数计算公式
$Gini(D)=\sum_{k=1}^{n}\sum_{k'\neq k}p_kp_{k'}=1 - \sum_{k=1}^{n}p_k^2$
基尼指数表示了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率，所以GINI值越小表示数据集的纯度越高。
对于数据集$D$的属性$a$的基尼指数定义为：
$Gini\_index(D,a) = \sum_{k=1}^{n}\frac{|D^k|}{|D|}Gini(D^k)$
在划分属性的时候，我们选择使得划分后的基尼指数最小的属性作为最优划分属性，即：
$a_*=\underset{a\in A}{arg min}(Gini_index(D,a))$
例，对于数据集$D'$:

$Gini(D') = 1-(\frac{4}{6})^2-(\frac{2}{6})^2 = 0.444$
用属性“色泽”划分
$D'^1(色泽=青绿)$包含4个样本，2个是好瓜，2个否
$D'^2(色泽=乌黑)$包含2个样本，2个是好瓜，0个否
则
$Gini(D'^1) = 1 - (2/4)^2 - (2/4)^2 = 0.5$
$Gini(D'^2) = 1 - (2/2)^2 - (0)^2 = 0$
最终，属性“色泽”的基尼指标为：
$Gini(D',色泽) = \frac{4}{6}*0.5+\frac{2}{6}*0 = 0.333$
同样的方法可以求出：
$Gini(D',脐部) = \frac{5}{6}*(1-(\frac{4}{5})^2-(\frac{1}{5})^2)+\frac{1}{6}*(1-(\frac{1}{1})^2) = 0.267$
属性“脐部”的基尼指标较小，所以就选它作为分裂节点。

CART构成的决策树是二叉树，当某离散属性有多个取值时，处理办法是将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点。例如某属性共有{X,Y,Z}三个取值，则该属性的分裂方法是{X}{Y,Z}、{Y}{X,Z}、{Z}{X,Y}，分别计算他们的样本基尼指数值。

GINI处理连续值
(1)可以将待计算的属性按照属性值排序。
(2)在两个相邻的属性值中选择中间值作为划分点，分别计算他们的GINI指数。
(3)进一步优化一下，可以只选择具有不同类标号的相邻记录之间的中间值作为测试的划分节点。

1.3.2 样本方差最小值构建决策树

回归方差计算公式：
$\sigma^2 = \sum_{i\in I}(x_i-\mu)^2 = \sum_{i\in I}x_i-n\mu^2$
方差越大，表示该节点的数据越分散，预测的效果就越差。
$Gain = SS_T-(SS_L+SS_R)$
其中$SS_T=\sum_{i\in I}(x_i-\mu)^2$是根节点的方差和，$SS_L$和$SS_R$是左右节点的方差和。
例,对于数据集$E$：

首先计算“含糖率”的方差和$SS_T$，然后依次选取“密度”各属性值作为分割点计算左右节点的方差和，当$SS_T-(SS_L+SS_R)$达到最大值时该点就是分割点。
通常情况下在依次分割中$SS_T$的值是固定的，所以只要找$(SS_L+SS_R)$的最小值即可。
$SS_T-(SS_L+SS_R)$可以作为一个预剪枝的threshold，当方差的提升小于threshold时则停止继续向下分裂。

2. 分割停止

决策树节点停止分裂的一般性条件：
1. 最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂。有两点原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
2. 熵或者基尼值小于阀值
由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。
3. 决策树的深度达到指定的条件
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
4. 所有特征已经使用完毕，不能继续进行分裂
被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。

3. 剪枝

决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越高。
考虑极端的情况，如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所有的噪声数据都”准确划分”了，强化了噪声数据的作用。
剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合出现的概率。
剪枝有预剪枝和后剪枝两种方法。

3.1 预剪枝

预剪枝就是在节点划分之前先进行估计，如果当前节点的划分不能带来决策树泛化性能的提升则停止划分并将当前节点标记为叶节点。

3.2 后剪枝

后剪枝是先从训练集中生成一颗完整的决策树，然后子弟向上的对非叶节点进行考察，然后根据一定的规则决定是否应将该节点变为叶节点。
后剪枝一般需要验证集。
下面介绍几种常用的后剪枝方法。

3.2.1 CCP

CCP(cost-complexity pruning 代价复杂度剪枝)方法，CART即采用这种剪枝方法。
CCP选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。CCP方法可以描述如下：
(1) 从原始的决策树开始生成一个子树序列（均非叶子节点）$\{T_0,T_1,...,T_n\}$，其中$T_{i+1}$从$T_i$产生，$T_n$为根节点。
(2) 计算所有节点的误差率增益值，选择误差率增益值最小的非叶子节点。
(3) 对选中的节点进行剪枝。
(4) 重复上边的步骤。
误差率增益值的计算公式为：
$\alpha = \frac{R(t)-R(T)}{N(T)-1}$
其中：
$\alpha$又叫做complexity parameters(复杂度参数)。
$R(t)$:叶子节点的误差代价，$R(t)=r(t)p(t)$，$r(t)$为节点的错误率，$p(t)$为节点的数据量占比。
$R(T)$:表示子树的误差代价，$R(T) = \sum_{i}^{m}r_i(t)p_i(t)$，$r_i(t)$为子节点$i$的错误率，$p_i(t)$表示节点$i$的数据量占比。
$N(T)$:表示子树的结点个数。
例，决策树如下所示，A、B表示训练集的两类，节点的类别标号为该节点中类别较多的那个类。

已知总的样本容量为80，对于非叶子节点$t_4$的子树：
$R(t) = r(t)*p(t) = \frac{4}{50}*\frac{50}{80} = \frac{1}{20}$
$R(T) = \sum r_i(t)p_i(t) = \frac{1}{45}*\frac{45}{80}+\frac{2}{5}*\frac{5}{80} = \frac{3}{80}$
$N(T) = 2$
$\alpha = \frac{R(t)-R(T)}{N(T)-1} = \frac{\frac{1}{20}-\frac{3}{80}}{2-1} = 0.0125$
对于非叶子节点$t_2$的子树：
$R(t) = r(t)*p(t) = \frac{10}{60}*\frac{60}{80} = \frac{1}{8}$
$R(T) = \sum r_i(t)p_i(t) = \frac{1}{45}*\frac{45}{80}+\frac{2}{5}*\frac{5}{80}+\frac{0}{6}*\frac{6}{80}+\frac{0}{4}*\frac{4}{80} = \frac{3}{80}$
$N(T) = 4$
$\alpha = \frac{R(t)-R(T)}{N(T)-1} = \frac{\frac{1}{8}-\frac{3}{80}}{4-1} = 0.0292$
关于上面决策树的所有节点的$\alpha$值计算结果为：
$T_0:$
$\alpha(t_4)=0.0125$    $\alpha(t_5)=0.0500$
$\alpha(t_2)=0.0292$    $\alpha(t_3)=0.0375$
$T_1:$
$\alpha(t_5)=0.0500$    $\alpha(t_2)=0.0375$    $\alpha(t_3)=0.0375$
$T_2:$
$\alpha(t_3)=0.0375$
从上面可以看出，在原始树$T_0$行，$t_4$的$\alpha$值最小，所以裁剪将$t_4$节点变为叶节点，得到$T_1$；在$T_1$行，$t_2$和$t_3$的$\alpha$值相同，但是裁减掉前者可以得到更小的决策树，所以裁剪将$t_2$节点变为叶节点，得到$T_2$。

3.2.2 REP

REP(reduced error pruning 降低误差剪枝)方法。
该方法的基本思路是：对于决策树$T$的每棵非叶子树$S$，将该子树变成叶子节点，如果$S$被叶子替代后形成的新树关于数据集$D$的误差等于或小于$S$关于$D$所产生的误差,则用叶子替代子树$S$。这里的$D$是和训练集不同的新的数据集，如果用旧的数据集，不可能出现分裂后的错误率比分裂前错误率要高的情况。
例：

对于节点$t_4$的关于剪枝数据集的误差是0，而他的子树$t_8$和$t_9$的误差之和是1，则将$t_4$转化为叶子节点。

REP 是当前最简单的事后剪枝方法之一，REP常作为一种基准来评价其它剪枝方法的性能.

3.2.3 PEP

PEP(pessimistic error pruning 悲观剪枝)方法，C4.5中就是使用该方法进行剪枝的。
悲观剪枝的主要思想是：如果决策树的精度在剪枝前后没有影响的话，则进行剪枝。怎样才算是没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果与剪枝前的效果一致，此时要进行剪枝。
PEP方法认为，如果公式：
$e'(t)\leqslant e'(T_t)+S(e'(T_t))$
满足，则将$T_t$应该被裁剪，变成叶节点。
其中
$e'(t)$表示剪枝后节点的误差，$e'(t) = [e(t)+0.5]$
$e'(T_t)$表示剪枝前子树的误差，$e'(T_t) = \sum e(t_i)+\frac{N_t}{2}$
$S(e'(T_t)) = \sqrt {e'(T_t)*\frac{n(t)-e'(T_t)}{n(t)}}$
例：
对于图1中$t_4$
$e'(t) = [e(t)+0.5] = 4 + 0.5 = 4.5$
$e'(T_t) = \sum e(t_i)+\frac{N_t}{2} = 1 + 2 + 2/2 = 4$
$S(e'(T_t)) = \sqrt {e'(T_t)*\frac{n(t)-e'(T_t)}{n(t)}} = \sqrt{4*\frac{50-4}{50}} = 1.92$
由于$e'(t) = 4.5 \leqslant e'(T_t)+S(e'(T_t)) = 4 + 1.92 = 5.92$
所以$t_4$应该被剪掉。
应用PEP方法剪裁图1的计算结果：

PEP方法被认为是当前决策树事后剪枝方法中精度较高的算法之一，不需要分离的剪枝数据集，采用自顶向下的方式。

参考文献

《机器学习》 周志华 著
《数据挖掘导论》 Pang-Ning Tan 等著
《决策树剪枝方法的比较》 魏红宁