【机器学习】算法原理详细推导与实现(七):决策树算法

在之前的文章中，对于介绍的分类算法有逻辑回归算法和朴素贝叶斯算法，这类算法都是二分类的分类器，但是往往只实际问题中$y$y不仅仅只有$\{0,1\}${0,1}，当出现一个新的类别$y=2$y=2时，之前的分类器就不太适用，这里就要介绍一个叫做决策树的新算法，该算法对于多个目标的离散特征往往有比较好的分类效果，用以解决$x$x是离散型的数据，这是判别模型，也是一个生成学习算法。

ID3决策树

熵

假设当前网上有很多机器学习的教程，我想学机器学习，但是不知道哪一个教程比较好；又或者想买一个榴莲，不知道哪一只肉比较厚实，不知道该挑那一只，对于这种不确定性就叫做熵。

当一个事情有多种可能情况时，这件事情对于观察人而言具体是哪种情况的不确定性叫做熵。

信息

当你不知道选择哪一篇教程来学习机器学习时，有人和你说TTyb的机器学习教程很好，这个人对你提供的TTyb的机器学习教程很好就是信息；又或者在买榴莲的时候，卖榴莲的人和你说这个榴莲的肉肯定很厚实，卖榴莲的人和你说的这个榴莲的肉肯定很厚实就是信息。当某件事情存在不确定性，能够消除观察人对于某件事情的不确定性，也就是前面说的熵，能够消除不确定性的事物叫做信息。

信息有很多种表现形式，能够调整不确定的概率的事物可以叫做信息

例如卖榴莲的老板说有很大概率这个榴莲的肉可能很厚实；能够排除干扰的事物可以叫做信息，例如卖榴莲的老板说这个榴莲壳厚，肉肯定小不要选择这个；能够确定情况的事物可以叫做信息，卖榴莲的老板说这个榴莲肉肯定很厚实，开了不厚实算我的。

熵和信息数量相等，意义相反，获取信息意味着消除了不确定性熵。

信息熵

假设有4个榴莲只有一个肉是厚实的，老板和你说榴莲A的肉不厚实，给你提供了$0.4bit$0.4bit的信息，榴莲B的肉不厚实，给你提供了$0.6bit$0.6bit的信息，榴莲C的肉不厚实，给你提供了$1bit$1bit的信息，最后让你确定了榴莲D肉是厚实的。老板每次都给你提供了一次信息，为什么提供的信息量却是不一样的？信息是如何量化的？回想一下什么东西有单位，质量、温度等物理量，信息也是一个物理量，要测量这个物理量，不妨回想一下我们是怎样测量质量的，“千克”最初又是怎么被定义出来的。

其实我们最初并不知道千克的质量，而是选定了一个参照物，把这个物体的质量就称为千克。当想要测量其他物体的质量时，就看这个物体的质量相当于多少个参照物体的质量，这里的“多少个”便是千克，如果参照物体换成“斤”，那么单位就会变化。

测量信息也是一样，既然信息消除的是不确定性，那么就选择另外一个事件的不确定性作为参照事件，当想要测量其他事件的信息时，就看待测事件的不确定性相当于“多少个”参照事件的不确定性，这里的多少个便是信息量。即待测物体质量为$m$m，参照物体个数(信息量)为$n$n，参照物体质量(千克)为$x$x，那么：

$m=n\times x$m=n×x

均匀分布的信息熵

当选择的参照物事件是像抛硬币这样，只有两种等概率情况的事件时，测得的信息量的单位就被称为比特(bit)，然而测量参照物体个数(信息量)$n$n时，我们是用待测物体质量$m$m除以参照物体质量(千克)$x$x，即:

$n=\frac{m}{x}$n=xm​

可是测量信息时却不能用除法，因为抛掷3个硬币能够产生的等可能结果并非$3\times 2=6$3×2=6，而是$2^3=8$23=8种，也就是说信息量不是线性关系，而是指数关系：

|正正正|反正正|
|正反正|正正反|
|反反正|反正反|
|正反反|反反反|

所以当知道可能情况的个数$m$m，想求这些情况相当于多少个$n$n参照事件$x$x所产生的，用指数运算的反函数，即对数运算计算：

$n=log_xm$n=logx​m

而这里硬币只有正面和反面，那么这里的参照事件$x=2$x=2，公式变换为：

$n=log_2m$n=log2​m

上面的式子代表，在抛硬币的实验中，假设8个不确定情况就相当于3个硬币抛出来结果$3=log_28$3=log2​8，即信息量为$3bit$3bit;4个不确定情况就相当于2个硬币抛出来结果$2=log_24$2=log2​4，即信息量为$2bit$2bit。

一般分布的信息熵

而上面讲的时抛掷硬币，被测事件的所有可能情况都是等概率事件，但是如果存在如下假设，这里有4个榴莲，只有一个榴莲的肉是厚实的，其他3个榴莲的肉是不厚实的：

那么买到肉是厚实榴莲的不确定性(信息熵)为$log_24=2bit$log2​4=2bit，因为这里可能情况的个数$m=4$m=4，所以不确定性是$2bit$2bit。但是如果老板和你说最大的那个(最右边圆圈)榴莲有50%概率是肉厚的，那么从概率上来说买最大的那个(最右边圆圈)是肉厚的概率为$\frac{1}{2}$21​，取出不是肉厚的概率是$\frac{1}{3}\times \frac{1}{2}$31​×21​，这里代表剩下3个榴莲要瓜分剩下的$\frac{1}{2}$21​概率，所以剩下3个榴莲每个的概率是$\frac{1}{6}$61​，这时候各个情况的概率不一样了：

这时该如何计算总信息量了呢？这时候就要分别测量每种可能情况的信息量后，乘以他们各自发生的概率再相加即可，即这时候买到肉厚的榴莲的不确定性(信息熵)为：

$\frac{1}{6}log_2m_1+\frac{1}{6}log_2m_2+\frac{1}{6}log_2m_3+\frac{1}{2}log_2m_4$61​log2​m1​+61​log2​m2​+61​log2​m3​+21​log2​m4​

不过怎么测量每种情况的信息量$log_2m$log2​m呢，怎么知道概率为$\frac{1}{6}$61​的情况的不确定性相当于抛掷多少个硬币所产生的不确定性呢？我们确实没有办法用$log_2m$log2​m这个公式了，但是我们知道$1$1会发生的情况，相当于从100个等概率情况中确定实际情况，即$p=1$p=1，概率的倒数等于等概率情况的个数，即$m=\frac{1}{100}=\frac{1}{p}$m=1001​=p1​，用概率的倒数$\frac{1}{p}$p1​替换等概率情况的个数$m$m后，我们就可以计算每种情况的信息量了：

$m_1=\frac{1}{\frac{1}{6}},m_2=\frac{1}{\frac{1}{6}},m_3=\frac{1}{\frac{1}{6}},m_4=\frac{1}{\frac{1}{2}}$m1​=61​1​,m2​=61​1​,m3​=61​1​,m4​=21​1​

再用每个情况的信息量乘以对应事件发生的概率，再相加后就能算出总信息量了：

$\frac{1}{6}log_2\frac{1}{\frac{1}{6}}+\frac{1}{6}log_2\frac{1}{\frac{1}{6}}+\frac{1}{6}log_2\frac{1}{\frac{1}{6}}+\frac{1}{2}log_2\frac{1}{\frac{1}{2}}=1.79bit$61​log2​61​1​+61​log2​61​1​+61​log2​61​1​+21​log2​21​1​=1.79bit

由此可得到，任何随机变量$X$X信息熵为：

$H(X)=\sum_{i=1}^n p_ilog_2\frac{1}{p_i}$H(X)=i=1∑n​pi​log2​pi​1​

信息增益

既然任何随机变量$X$X信息熵为：

$H(X)=\sum_{i=1}^n p_ilog_2\frac{1}{p_i}$H(X)=i=1∑n​pi​log2​pi​1​

那么假设$p$p是随机变量$X$X发生的概率，如果存在多个变量$X$X和$Y$Y，则他们的联合熵为：

$H(X,Y)=\sum_{i=1}^n p(x_i,y_i)log_2p(x_i,y_i)$H(X,Y)=i=1∑n​p(xi​,yi​)log2​p(xi​,yi​)

其中$p(x_i,y_i)$p(xi​,yi​)代表事件$X=x$X=x和$Y=y$Y=y一起出现的联合概率。有了联合熵，又可以得到条件熵的表达式$H(X|Y)$H(X∣Y)，条件熵类似于条件概率,当事件$Y$Y发生过后，事件$X$X还剩下的不确定性(信息熵)：

$\begin{aligned} H(X|Y)&=\sum_{y} p(y)H(X|Y=y) \\ &=-\sum_{y} p(y)\sum_{x}p(x|y)log(p(x|y)) \\ &=-\sum_{y}\sum_{x}p(x,y)log(p(x|y)) \\ &=-\sum_{x,y}p(x,y)log(p(x|y)) \end{aligned}$H(X∣Y)​=y∑​p(y)H(X∣Y=y)=−y∑​p(y)x∑​p(x∣y)log(p(x∣y))=−y∑​x∑​p(x,y)log(p(x∣y))=−x,y∑​p(x,y)log(p(x∣y))​

其中$H(X|Y)=H(X,Y)−H(Y)$H(X∣Y)=H(X,Y)−H(Y)，信息熵和信息增益的关系如下图所示：

左边的椭圆代表随机变量$X$X的信息熵$H(X)$H(X),右边的椭圆代表随机变量$Y$Y的信息熵$H(Y)$H(Y),中间重合的部分就是信息增益$I(X,Y)$I(X,Y), 左边的椭圆去掉重合部分就是$H(X|Y)$H(X∣Y),右边的椭圆去掉重合部分就是$H(Y|X)$H(Y∣X)，两个椭圆的并就是$H(X,Y)$H(X,Y)，由此可以得到信息增益的公式为：

$I(X,Y)=H(X)−H(X|Y)$I(X,Y)=H(X)−H(X∣Y)

回到最初的问题，当4个榴莲中不知道那个是肉厚的榴莲的时候，随机变量$X=肉厚$X=肉厚，不确定性(信息熵)的套用公式为:

$\begin{aligned} H(X)&=\sum_{i=1}^n p_ilog_2\frac{1}{p_i} \\ &=\frac{1}{4}log_2\frac{1}{\frac{1}{4}}+\frac{1}{4}log_2\frac{1}{\frac{1}{4}}+\frac{1}{4}log_2\frac{1}{\frac{1}{4}}+\frac{1}{4}log_2\frac{1}{\frac{1}{4}} \\ &=2 \end{aligned}$H(X)​=i=1∑n​pi​log2​pi​1​=41​log2​41​1​+41​log2​41​1​+41​log2​41​1​+41​log2​41​1​=2​

假设每个榴莲从左到右记为随机变量$X1$X1、$X2$X2、$X3$X3、$X4$X4，老板告诉说最大的那个$X4$X4(最右边圆圈)榴莲有50%概率是肉厚的，即提供了信息$Y$Y，求肉厚的信息熵。这时候先计算的信息熵为条件熵$H(X|Y)$H(X∣Y)：

$\begin{aligned} H(X|Y)&=H(X1)+H(X2)+H(X3)+H(X4|Y=y) \\ &=\frac{1}{6}log_2\frac{1}{\frac{1}{6}}+\frac{1}{6}log_2\frac{1}{\frac{1}{6}}+\frac{1}{6}log_2\frac{1}{\frac{1}{6}}+\frac{1}{2}log_2\frac{1}{\frac{1}{2}} \\ &=1.79bit \end{aligned}$H(X∣Y)​=H(X1)+H(X2)+H(X3)+H(X4∣Y=y)=61​log2​61​1​+61​log2​61​1​+61​log2​61​1​+21​log2​21​1​=1.79bit​

最后由总的不确定性(信息熵)减去后面的不确定性(信息熵)，得到老板说的话“最大的那个(最右边圆圈)榴莲有50%概率是肉厚的”提供的信息为：

$\begin{aligned} I(X,Y)&=H(X)−H(X|Y) \\ &=2-1.79 \\ &=0.21bit \end{aligned}$I(X,Y)​=H(X)−H(X∣Y)=2−1.79=0.21bit​

提供的信息$0.21bit$0.21bit也叫做信息增益

ID3决策树算法步骤

输入的是$m$m个样本，样本输出集合为$X$X，每个样本有$n$n个离散特征，特征集合即为$Y$Y，输出为决策树$T$T。例如存在样本如下所示：

天气	气温	湿度	风力	外出
晴朗	高温	高	无风	否
晴朗	高温	高	有风	否
多云	高温	高	无风	是
下雨	温暖	高	无风	是
下雨	寒冷	正常	无风	是

则样本数量$m=5$m=5；输出集合为是或者否，即$X_1=是,X_2=否$X1​=是,X2​=否；每个样本的离散特征为$n=4$n=4，即天气、气温、湿度、风力；特征集合为$Y$Y，当离散特征$Y'$Y′是天气时，特征集合$Y_i$Yi​为{晴朗,多云,下雨}。算法的过程为：

1. 计算$m$m中的各个特征（一共$n$n个）对输出$X$X的信息增益，选择信息增益最大的特征$Y'$Y′，其中$Y' \in Y$Y′∈Y
2. 按特征$Y'$Y′的不同取值$Y_i$Yi​将对应的样本输出$X$X分成不同的类别$X_i$Xi​，其中$i \in n$i∈n。每个类别产生一个子节点。对应特征值为$Y_i$Yi​。返回增加了节点的数$T$T。
3. 对于所有的子节点，令$X=X_i,m=m−\{Y'\}$X=Xi​,m=m−{Y′}递归调用1-2步，得到子树$T_j$Tj​并返回。

C4.5决策树

ID3算法虽然提出了新思路，但是还是有如下4点需要改进的地方：

1. ID3没有考虑连续特征，比如长度、密度都是连续值，无法在ID3运用，这大大限制了ID3的用途。–数据分箱即可解决
2. ID3采用信息增益大的特征优先建立决策树的节点，但信息增益准则对可取值数目较多的属性有所偏好。
3. 算法对于缺失值的情况没有做考虑。–特征工程即可解决
4. 没有考虑过拟合的问题。–预剪枝和后剪枝

对于上面的第2点需要做一下解释。从上面可以知道，ID3信息增益的计算公式为：

$I(X,Y)=H(X)−H(X|Y)$I(X,Y)=H(X)−H(X∣Y)

信息增益的大小取决于随机变量$Y$Y信息熵的大小，$H(X|Y)$H(X∣Y)越小则信息增益越大，而什么情况下$H(X|Y)$H(X∣Y)会有极小的信息熵呢？举一个极端的例子，如果上面的例子中，变量天气的特征互不相同变成：

天气	气温	湿度	风力	外出
大晴	高温	高	无风	否
小晴	高温	高	有风	否
多云	高温	高	无风	是
大雨	温暖	高	无风	是
小雨	寒冷	正常	无风	是

那么天气的信息熵会等于0，计算如下，当天气为大晴时，$\frac{1}{1}$11​的概率不外出，$0$0的概率外出，那么大晴的信息熵$H(X=外出|Y=大晴)$H(X=外出∣Y=大晴)为：

$\begin{aligned} H(X=外出|Y=大晴)&=\frac{1}{1}log_2\frac{1}{\frac{1}{1}}+0log_20 \\ &=0 \end{aligned}$H(X=外出∣Y=大晴)​=11​log2​11​1​+0log2​0=0​

同理天气条件下其他特征的信息熵都是$0$0，那么天气的信息熵$H(X=外出|Y=天气)=0$H(X=外出∣Y=天气)=0，得到天气的信息增益就最大了。也就是说决策树给天气这个属性下的离散特征都单独分成了一个子类，也就是说有多少种天气情况就有多少种取值，那么原数据集中有多少个离散特征，就会被划分为多少个子类。虽然这种划分毫无意义，但是从信息增益准则来讲，这就是最好的划分结果。

对于这种结果看似完美划分了随机变量的特征，然而根据大数定律，只有当样本数足够多的时候，频率才可以准确的近似概率。也就是说，样本数越少，对概率的估计结果的方差就会越大，结果也就越不准。想象一下做抛硬币实验来近似正面向上的概率，如果只抛两次，那么得到的正面向上的概率可能会非常离谱。而如果抛1万次，不论何时何地几乎总能得到近似0.5的概率。

而C4.5就是为了解决信息增益准则对可取值数目较多的属性有所偏好这种问题，由此提出了信息增益比，计算公式为：

$Ir=(X,Y)=\frac{I(X,Y)}{IV(Y)}$Ir=(X,Y)=IV(Y)I(X,Y)​

其中$IV(Y)$IV(Y)计算方式为：

$IV(Y)=\sum_yp_ylogp_y$IV(Y)=y∑​py​logpy​

$p_y$py​等于随机变量$Y=y$Y=y的概率。当信息熵$H(X|Y)$H(X∣Y)最小时，也就是分类各不相等的时候，$IV(Y)$IV(Y)也相对最小，这样就减轻了划分行为本身的影响。

cart决策树

基尼系数

有一个盒子里面放着小球，如果小球的颜色都是绿色，那么代表绿色的概率是$p_绿=1$p绿​=1，我们可以称随机变量$X=绿$X=绿是纯正的：

如果盒子里面的小球包含不同的颜色，不同颜色发生的概率为$p_1,p_2,...$p1​,p2​,...，我们可以称随机变量$X$X不纯正的：

假设某组样本存在多个随机变量$X_1,X_2,...,X_n$X1​,X2​,...,Xn​，他们各自发生的概率是$\{p_1,p_2,...,p_n\}${p1​,p2​,...,pn​}，那么这组样本的纯正程度可以使用基尼系数(Gini)衡量：

$Gini=1-p_1^2-p_2^2-...-p_n^2$Gini=1−p12​−p22​−...−pn2​

假设一个盒子存在3种颜色的小球，他们的概率是：$\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\}${31​,31​,31​}，那么基尼系数为：$Gini=1-(\frac{1}{3})^2-(\frac{1}{3})^2-(\frac{1}{3})^2=0.6666$Gini=1−(31​)2−(31​)2−(31​)2=0.6666。其他情况的基尼系数计算：

$\{\frac{1}{10},\frac{2}{10},\frac{7}{10}\}${101​,102​,107​},$\{1,0,0\}${1,0,0}

计算的基尼系数为：

$Gini=1-(\frac{1}{10})^2-(\frac{2}{10})^2-(\frac{7}{10})^2=0.46$Gini=1−(101​)2−(102​)2−(107​)2=0.46

$Gini=1-(1)^2-(0)^2-(0)^2=0$Gini=1−(1)2−(0)2−(0)2=0

基尼系数越大，代表样本越不纯净;基尼系数越小，代表样本越纯净，最终会找出$Gini$Gini指数最小的来作为最优的划分点

剪枝

决策树算法为了避免过拟合和简化决策树模型，提出了剪枝的方法，剪枝分为预剪枝和后剪枝，剪枝的原理如下：

• 预剪枝：在构造决策树的同时进行剪枝，也就是在节点划分前进行判断。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。

• 后剪枝：在决策树生长完全构造好了过后，对树进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点。后剪枝是目前最普遍的做法。

常见的剪枝有REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、CCP(Cost Complexity Pruning)和MEP(Minimum Error Pruning)算法，以下分别进行说明。

Reduced-Error Pruning(REP,错误率降低剪枝）

REP是最简单粗暴的一种后剪枝方法，其目的减少误差样本数量。该算法是从下往上依次遍历所有的子树，直至没有任何子树可以替换使得在验证集上的表现得以改进时，算法就可以终止。

假设树$T$T存在很多结点$t$t，其中$t \in T$t∈T，$e(t)$e(t)表示节点$t$t下训练样本误判的数量，则有训练样本误判总数量$f(T)$f(T)为：

$f(T)=-\sum_{t \in T}e(t)$f(T)=−t∈T∑​e(t)

假设树$T$T去掉某个节点$t'$t′变成树$T'$T′,则有训练样本误判总数量$f(T')$f(T′)为：

$f(T')=-\sum_{t \in T'}e(t)$f(T′)=−t∈T′∑​e(t)

如果误判的数量降低，即剪枝之后使得误差降低:

$f(T) \leqslant f(T')$f(T)⩽f(T′)

那么代表剪枝后能使误差降低，剪枝成功。反复进行上面的操作，从底向上的处理结点，删除那些有害的结点，直到进一步修剪不能减低误差为止。例如：存在如下一棵树：

Step 1： 将节点4删掉替换成8和9，测试在验证集上的表现，若表现更好，则将节点4删掉并替换成8和9的并集，若表现不好则保留原树的形状
Step 2： 将节点2删掉替换成8、9和5，测试在验证集上的表现
Step 3： 将节点3删掉替换成6和7，测试在验证集上的表现

REP是最简单的后剪枝方法之一，不过由于使用独立的验证集，如果数据量较少(数据要分为训练集、验证集、测试集三份)，那么在使用验证集进行剪枝的时候，可能会在验证集出现的稀有实例，却在测试集中没有出现，那么就会存在过度剪枝的情况。如果数据集较小，通常不考虑采用REP算法。尽管REP有这个缺点，但还是能够解决一定程度的过拟合问题。

Pesimistic-Error Pruning(PEP,悲观错误剪枝）

上文的REP方法思想简单且易于使用，不过最大的问题在于它需要一个新的验证集来修正我们的决策树在，PEP方法中不需要新的验证集，并且PEP是自上而下剪枝的。PEP的剪枝是把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代，如下所示：

原来子树1可以分成(4,5,6,7)多个类，但是剪枝变成只能分成一个类(1)。同样的样本子集，如果用子树分类可以分成多个类，准确率肯定要高一些，而用单颗叶子节点来分的话只能分成一个类，准确肯定要低一些，所以$PEP$PEP的误判率肯定是上升的。训练数据也带来错分误差偏向于训练集，为了解决这一问题，给每个子叶节点加入修正项$\frac{1}{2}$21​。具有$T$T个节点的树的错误率为：

$E(T) = \sum_{t \in T}\frac{e(t)+1/2}{N(t)}$E(T)=t∈T∑​N(t)e(t)+1/2​

去掉节点$K$K个子叶节点之后T′个节点的树的错误率为：

$E(T')=\sum_{t \in T, excep K}\frac{e(t)+1/2K}{N(t)}$E(T′)=t∈T,excepK∑​N(t)e(t)+1/2K​

其中$e(t)$e(t)表示节点$t$t下训练样本误判的数量，$N(t)$N(t)表示节点$t$t下训练样本的总数量。

PEP悲观错误剪枝剪枝法定义，如果 E(剪枝后误判数均值)−E(剪枝前误判数均值)<std(剪枝前误判数标准差)，则可以剪枝，假设在子树中每一个样本的误判服从一个二项分布$B(N,p)$B(N,p)，其中$N$N表示子树所包含的所有样本个数。

所以，在剪枝前，其期望的误判数为：

$e(t)=N(t)∗E(t)$e(t)=N(t)∗E(t)

其误判的标准差为：

$std(t)=\sqrt{N(t)∗E(T)*(1-E(T))}$std(t)=N(t)∗E(T)∗(1−E(T))​

当剪枝后的误判数小于剪枝前的误判数一个标准差之后，就决定剪枝：

$e(t')-e(t)<std(t)=\sqrt{N(t)\times E(T)\times (1-E(T))}$e(t′)−e(t)<std(t)=N(t)×E(T)×(1−E(T))​

例如：存在如下一棵树：

对于节点T4而言，剪枝前后的计算过程如下：

已知$E(T7)=0 ；E(T8)=2；E(T9)=1；E(T10)=1；E(T4)=7；N(t)=20$E(T7)=0；E(T8)=2；E(T9)=1；E(T10)=1；E(T4)=7；N(t)=20，所以，剪枝前的误判概率为：

$E(T)=\frac{(0+2+1+1)+4∗0.5}{20}=0.3$E(T)=20(0+2+1+1)+4∗0.5​=0.3

所以：

$e(t)=20*0.3=6$e(t)=20∗0.3=6

$std(t)=\sqrt{20*0.3*(1-0.3)}=2.05$std(t)=20∗0.3∗(1−0.3)​=2.05

在我们对T4进行剪枝后，即将T4直接作为叶节点，剪枝后的误判概率:

$E(T')=\frac{7+0.5}{20}=0.375$E(T′)=207+0.5​=0.375

剪枝后的误判期望数为：

$e(t')=20*0.375=7.5$e(t′)=20∗0.375=7.5

$7.5-2.05<6$7.5−2.05<6

因此满足条件，所以我们将把T4节点剪枝

Cost-Complexity Pruning（CCP，代价复杂度剪枝)

该算法为子树$T_t$Tt​定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数$\alpha$α，其中，代价指在剪枝过程中因子树$T_t$Tt​被叶节点替代而增加的错分样本，复杂度表示剪枝后子树$T_t$Tt​减少的叶结点数，$\alpha$α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为:

$α= \frac{R(t)−R(T_t)}{∣N∣−1}​$α=∣N∣−1R(t)−R(Tt​)​​

其中，

• $|N|$∣N∣：子树$T_t$Tt​中的叶节点数;
• $R(t)$R(t)：结点$t$t的错误代价，计算公式为$R(t)=r(t)*p(t)$R(t)=r(t)∗p(t);
• $r(t)$r(t)为结点t的错分样本率，$p(t)$p(t)为落入结点t的样本占所有样本的比例;
• $R(T_t)$R(Tt​)：子树$T_t$Tt​错误代价，计算公式为$R(T_t)=\sum R(i)$R(Tt​)=∑R(i)，$i$i为子树$T_t$Tt​的叶节点。

CCP算法可以分为两个步骤，
Step 1： 按照上述公式从下到上计算每一个非叶节点的αα值，然后每一次都剪掉具有最小αα值的子树。从而得到一个集合$\{T_0,T_1,T_2,...,T_M\}${T0​,T1​,T2​,...,TM​}，其中，$T_0$T0​表示完整的决策树，$T_M$TM​表示根节点
Step 2： 根据真实的错误率在集合$\{T_0,T_1,T_2,...,T_M\}${T0​,T1​,T2​,...,TM​}选出一个最好的决策树

假设在下图中有数据100条，从下往上开始计算:

先以节点T4为例，那么可以得到:

$R(t)=r(t)*p(t)=\frac{7}{9+7}*\frac{9+7}{100}=\frac{7}{100}$R(t)=r(t)∗p(t)=9+77​∗1009+7​=1007​

$R(T_t)=\sum R(i)=R(7)+R(8)+R(6)=\frac{2}{3+2}*\frac{3+2}{100}+\frac{0}{0+2}*\frac{0+2}{100}+\frac{3}{6+3}*\frac{6+3}{100}=\frac{5}{100}$R(Tt​)=∑R(i)=R(7)+R(8)+R(6)=3+22​∗1003+2​+0+20​∗1000+2​+6+33​∗1006+3​=1005​

$α= \frac{R(t)−R(T_t)}{∣N∣−1}​=\frac{\frac{7}{100}-\frac{5}{100}}{3-1}=\frac{1}{100}$α=∣N∣−1R(t)−R(Tt​)​​=3−11007​−1005​​=1001​

	REP	PEP	CCP
剪枝方式	自底向上	自顶向下	自底向上
计算复杂度	0(n)	0(n)	o(n2)
误差估计	验证集上误差估计	使用连续纠正	标准误差

总结

对一般三种决策树进行总结，区分如下所示：

算法	支持模型	特征选择	连续值处理	确实值处理	剪枝
ID3	分类	信息增益	不支持	不支持	不支持
C4.5	分类	信息增益比	支持	支持	支持
CART	分类、回归	基尼系数	支持	支持	支持

实例

假设观测到历史有如下一组信息：

天气	气温	湿度	风力	外出
晴朗	高温	高	无风	否
晴朗	高温	高	有风	否
多云	高温	高	无风	是
下雨	温暖	高	无风	是
下雨	寒冷	正常	无风	是
下雨	寒冷	正常	有风	否
多云	寒冷	正常	有风	是
晴朗	温暖	高	无风	否
晴朗	寒冷	正常	无风	是
下雨	温暖	正常	无风	是
晴朗	温暖	正常	有风	是
多云	温暖	高	有风	是
多云	高温	正常	无风	是
下雨	温暖	高	有风	否

计算逻辑

可以看到这个树的根节点是外出，而根节点往下的一个节点，该怎么定义用哪一个条件呢？决策树构建树节点的条件在于：该节点能最大程度的提供有用的信息，使得不确定性(信息熵)减少得最快。也就是说，天气、气温、湿度、风力这四个条件，哪一个条件为结果外出提供更多的信息：

要计算哪一个条件能提供更多的信息，只要计算根节点和另一节点的信息熵差值，就是提供的信息增益了。由上面的表格可以知道，外出的概率为$\frac{9}{14}$149​，不外出的概率是$\frac{5}{14}$145​，很显然这是一个不均匀分布，要使用一般分布的信息熵计算：

$\sum p_ilog_2\frac{1}{p_i}$∑pi​log2​pi​1​

则根节点外出的信息熵$H(X=外出)$H(X=外出)为：

$\begin{aligned} H(X=外出)&=\frac{9}{14}log_2\frac{1}{\frac{9}{14}}+\frac{5}{14}log_2\frac{1}{\frac{5}{14}} \\ &=0.940 \end{aligned}$H(X=外出)​=149​log2​149​1​+145​log2​145​1​=0.940​

接着分别计算各个条件的信息熵，先计算天气各个情况的信息熵：

• 天气为晴朗时，2/5的概率外出，3/5的概率不外出，晴朗的信息熵$H(X=外出|Y=晴朗)$H(X=外出∣Y=晴朗)为:

$\begin{aligned} H(X=外出|Y=晴朗)&=\frac{2}{5}log_2\frac{1}{\frac{2}{5}}+\frac{3}{5}log_2\frac{1}{\frac{3}{5}} \\ &=0.971 \end{aligned}$H(X=外出∣Y=晴朗)​=52​log2​52​1​+53​log2​53​1​=0.971​

• 天气为多云时，0的概率外出，0的概率不外出，信息熵$H(X=外出|Y=多云)$H(X=外出∣Y=多云)为:

$\begin{aligned} H(X=外出|Y=多云)&=0+0 \\ &=0 \end{aligned}$H(X=外出∣Y=多云)​=0+0=0​

• 天气为下雨时，3/5的概率外出，2/5的概率不外出，信息熵$H(X=外出|Y=下雨)$H(X=外出∣Y=下雨)为:

$\begin{aligned} H(X=外出|Y=下雨)&=\frac{3}{5}log_2\frac{1}{\frac{3}{5}}+\frac{2}{5}log_2\frac{1}{\frac{2}{5}} \\ &=0.971 \end{aligned}$H(X=外出∣Y=下雨)​=53​log2​53​1​+52​log2​52​1​=0.971​

而天气是 晴朗 的概率为5/14，天气是 多云 的概率为4/14，天气是 下雨 的概率为5/14，所以 天气 的信息熵$H(X=外出|Y=天气)$H(X=外出∣Y=天气)为：

$\begin{aligned} H(X=外出|Y=天气)&=\frac{5}{14} \times H(X=外出|Y=晴朗)+0 \times H(X=外出|Y=多云)+\frac{4}{14} \times H(X=外出|Y=下雨) \\ &=\frac{5}{14} \times 0.971+0 \times 0+\frac{4}{14} \times 0.971 \\ &=0.693 \end{aligned}$H(X=外出∣Y=天气)​=145​×H(X=外出∣Y=晴朗)+0×H(X=外出∣Y=多云)+144​×H(X=外出∣Y=下雨)=145​×0.971+0×0+144​×0.971=0.693​

天气的信息增益$I(X=外出,Y=天气)$I(X=外出,Y=天气)为：

$\begin{aligned} I(X=外出,Y=天气)&=H(X=外出)-H(X=外出|Y=天气) \\ &=0.940-0.693 \\ &=0.247 \end{aligned}$I(X=外出,Y=天气)​=H(X=外出)−H(X=外出∣Y=天气)=0.940−0.693=0.247​

同理计算得到，气温的信息熵$H(X=外出|Y=气温)$H(X=外出∣Y=气温)为：

$\begin{aligned} H(X=外出|Y=气温)&=\frac{4}{14}H(X=外出|Y=高温)+\frac{6}{14}H(X=外出|Y=温暖)+\frac{4}{14}H(X=外出|Y=寒冷) \\ &=\frac{4}{14}(\frac{2}{4}log_2\frac{1}{\frac{2}{4}}+\frac{2}{4}log_2\frac{1}{\frac{2}{4}})+\frac{6}{14}(\frac{4}{6}log_2\frac{1}{\frac{4}{6}}+\frac{2}{6}log_2\frac{1}{\frac{2}{6}})+\frac{4}{14}(\frac{3}{4}log_2\frac{1}{\frac{3}{4}}+\frac{1}{4}log_2\frac{1}{\frac{1}{4}}) \\ &=\frac{4}{14}\times 1.0+\frac{6}{14}\times 0.918296+\frac{4}{14}\times 0.811278 \\ &=0.911 \end{aligned}$H(X=外出∣Y=气温)​=144​H(X=外出∣Y=高温)+146​H(X=外出∣Y=温暖)+144​H(X=外出∣Y=寒冷)=144​(42​log2​42​1​+42​log2​42​1​)+146​(64​log2​64​1​+62​log2​62​1​)+144​(43​log2​43​1​+41​log2​41​1​)=144​×1.0+146​×0.918296+144​×0.811278=0.911​

气温的信息增益$I(X=外出,Y=气温)$I(X=外出,Y=气温)为：

$\begin{aligned} I(X=外出,Y=气温)&=H(X=外出)-H(X=外出|Y=气温) \\ &=0.940-0.911 \\ &=0.029 \end{aligned}$I(X=外出,Y=气温)​=H(X=外出)−H(X=外出∣Y=气温)=0.940−0.911=0.029​

湿度的信息熵$H(X=外出|Y=湿度)$H(X=外出∣Y=湿度)为：

$\begin{aligned} H(X=外出|Y=湿度)&=\frac{7}{14}H(X=外出|Y=高)+\frac{7}{14}H(X=外出|Y=正常) \\ &=\frac{7}{14}\times (\frac{6}{7}log_2\frac{1}{\frac{6}{7}}+\frac{1}{7}log_2\frac{1}{\frac{1}{7}})+\frac{7}{14}\times (\frac{3}{7}log_2\frac{1}{\frac{3}{7}}+\frac{4}{7}log_2\frac{1}{\frac{4}{7}}) \\ &=\frac{7}{14}\times 0.591673+\frac{7}{14}\times 1.159856 \\ &=0.788 \end{aligned}$H(X=外出∣Y=湿度)​=147​H(X=外出∣Y=高)+147​H(X=外出∣Y=正常)=147​×(76​log2​76​1​+71​log2​71​1​)+147​×(73​log2​73​1​+74​log2​74​1​)=147​×0.591673+147​×1.159856=0.788​

湿度的信息增益$I(X=外出,Y=湿度)$I(X=外出,Y=湿度)为：

$\begin{aligned} I(X=外出,Y=湿度)&=H(X=外出)-H(X=外出|Y=湿度) \\ &=0.940-0.788 \\ &=0.152 \end{aligned}$I(X=外出,Y=湿度)​=H(X=外出)−H(X=外出∣Y=湿度)=0.940−0.788=0.152​

风力的信息熵$H(X=外出|Y=风力)$H(X=外出∣Y=风力)为：

$\begin{aligned} H(X=外出|Y=风力)&=\frac{6}{14}E_{有风}+\frac{8}{14}E_{无风} \\ &=\frac{6}{14}\times (\frac{3}{6}log_2\frac{1}{\frac{3}{6}}+\frac{3}{6}log_2\frac{1}{\frac{3}{6}})+\frac{8}{14}\times (\frac{6}{8}log_2\frac{1}{\frac{6}{8}}+\frac{2}{8}log_2\frac{1}{\frac{2}{8}}) \\ &=\frac{6}{14}\times 1.0+\frac{8}{14}\times 0.811278 \\ &=0.892 \end{aligned}$H(X=外出∣Y=风力)​=146​E有风​+148​E无风​=146​×(63​log2​63​1​+63​log2​63​1​)+148​×(86​log2​86​1​+82​log2​82​1​)=146​×1.0+148​×0.811278=0.892​

风力的信息增益$I(X=外出,Y=风力)$I(X=外出,Y=风力)为：

$\begin{aligned} I(X=外出,Y=风力)&=H(X=外出)-H(X=外出|Y=风力) \\ &=0.940-0.892 \\ &=0.048 \end{aligned}$I(X=外出,Y=风力)​=H(X=外出)−H(X=外出∣Y=风力)=0.940−0.892=0.048​

可以看到，信息增益：$I(X=外出,Y=天气)>I(X=外出,Y=湿度)>I(X=外出,Y=风力)>I(X=外出,Y=气温)$I(X=外出,Y=天气)>I(X=外出,Y=湿度)>I(X=外出,Y=风力)>I(X=外出,Y=气温)，所以对是否外出提供信息最多的条件是天气。也就是说在决定是否外出的时候，天气是最重要的一个影响因素，天气的好坏很大程度决定了当天是否会外出，减少是否外出的不确定性。

但是天气分为多云、下雨、晴朗，由数据集可以知道多云的时候，无论气温、湿度和风力如何，都会外出；而下雨和晴朗的时候，会根据气温、湿度和风力的情况再来决定是否外出，因此决策树的构造变成了：

而下雨和晴朗的时候，会根据气温、湿度和风力的情况再来决定是否外出，这时就需要计算：

下雨时，选择信息增益最大的属性(气温、湿度或风力)来作为下一个节点
晴朗时，选择信息增益最大的属性(气温、湿度或风力)来作为下一个节点

在天气=下雨的情况下：

由前面知道$H(X=外出,Y=下雨)=0.971$H(X=外出,Y=下雨)=0.971，在下雨时气温、湿度和风力外出情况如下所示：

天气	气温	湿度	风力	外出
下雨	温暖	高	无风	是
下雨	寒冷	正常	无风	是
下雨	寒冷	正常	有风	否
下雨	温暖	正常	无风	是
下雨	温暖	高	有风	否

则气温的信息熵$H(X_1=外出,X_2=下雨|Y=气温)$H(X1​=外出,X2​=下雨∣Y=气温)为：

$\begin{aligned} H(X_1=外出,X_2=下雨|Y=气温)&=H(X_1=外出,X_2=下雨|Y=温暖)+H(X_1=外出,X_2=下雨|Y=寒冷) \\ &=\frac{3}{5}\times (\frac{2}{3}log_2\frac{1}{\frac{2}{3}}+\frac{1}{3}log_2\frac{1}{\frac{1}{3}})+\frac{2}{5}\times (\frac{1}{2}log_2\frac{1}{\frac{1}{2}}+\frac{1}{2}log_2\frac{1}{\frac{1}{2}}) \\ &=0.951 \end{aligned}$H(X1​=外出,X2​=下雨∣Y=气温)​=H(X1​=外出,X2​=下雨∣Y=温暖)+H(X1​=外出,X2​=下雨∣Y=寒冷)=53​×(32​log2​32​1​+31​log2​31​1​)+52​×(21​log2​21​1​+21​log2​21​1​)=0.951​

同理可得 湿度的信息熵$H(X_1=外出,X_2=下雨|Y=湿度)=0.951$H(X1​=外出,X2​=下雨∣Y=湿度)=0.951，风力的信息熵$H(X_1=外出,X_2=下雨|Y=风力)=0$H(X1​=外出,X2​=下雨∣Y=风力)=0，

在天气=晴朗的情况下：

$H(X_1=外出,X_2=晴朗|Y=湿度)$H(X1​=外出,X2​=晴朗∣Y=湿度)最大，那么新得到的树形如下所示：

而上面却发现没有气温选项？因为在其他三个的条件下就能决定是否外出了，气温对于外出没有直接影响。

计算代码

将文本转化为数字：

data[data == u'晴朗'] = 2
data[data == u'多云'] = 1
data[data == u'下雨'] = 0
data[data == u'高温'] = 2
data[data == u'温暖'] = 1
data[data == u'寒冷'] = 0
data[data == u'高'] = 1
data[data == u'正常'] = 0
data[data == u'有风'] = 1
data[data == u'无风'] = 0
data[data == u'是'] = 1
data[data == u'否'] = 0

基于信息熵来计算：

# 建立决策树模型，基于信息熵
dtc = DTC(criterion='entropy')
dtc.fit(x_train, y_train)

预测：

print(dtc.predict(x_test))
print(dtc.score(x_test, y_test))

这里样本比较小，所以得到的准确率分数为1.0：

数据和代码下载请关注公众号【 机器学习和大数据挖掘 】，后台回复【 机器学习 】即可获取