决策树

决策树是一种基本的分类与回归方法。它利用分治的思想，将训练样本集(根节点)按某种准则在特征空间上选择某种特征后递归地分成不同的子集(内部节点)，当子集满足某种条件后，则停止划分。最终得到的不能划分的子集(叶节点)互不相交，共同组成了最初的训练样本集。上述过程可以看成是if-then规则的集合，即决策树的根结点到叶结点的每一条路径构建了一条规则；路径上内部结点的特征对应规则的条件，而叶结点的类别对应规则的结论。也可以理解为类别空间在特征空间上的条件概率分布，即将$P\left( \text{类别} \right) $转为$P\left( \text{类别}\left| \text{特征} \right. \right)$。

决策树学习

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。 最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

综上，决策树学习算法主要包含特征选择、决策树的生成与决策树的剪枝3个过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

特征选择

由决策树学习过程可知，其关键步骤为如何选择最优的划分属性，即通过该属性划分后，决策树的分支节点包含的样本集尽可能属于同一类别，即节点的纯度越来越高，不确定性越来越低。

决策树最开始是按照误分类率进行样本集的划分的，但由于误分类率有时无法分辨两种划分方式的优劣(即使按某种属性划分后，分支节点的纯度较高；按另一种属性划分后，分支节点的纯度较低)，且误分类率不利于数值优化。后面有一个叫昆兰的大牛将信息论中的熵引入到决策树后发现效果明显好于误分类率，并基于信息增益作为划分标准，推出了ID3算法。随着时间的推移，ID3决策树暴露出诸多不足，昆兰又基于信息增益比推出了ID3的进化版C4.5。再后来由于C4.5的不足，又出现了基于基尼指数的CART。

下面分别介绍信息增益、信息增益比和基尼指数三种特征选择准则。

信息增益

定义

假设训练样本集合为$D$，$\left| D \right|$表示集合中的样本个数。其中有$K$个类$C_k,k=1,2,\cdots,K, \left| C_k \right|$表示类别$C_k$中的样本个数，且有$\sum_{k=1}^K{\left| C_k \right|}=\left| D \right|$。设某个特征$A$有$n$个不同的取值 $\left\{ a_1,a_2,\cdots,a_n \right\}$ ,根据特征$A$的不同取值将$D$划分为$n$个子集$D_1、D_2、\cdots D_n,\left| D_i \right|$表示$D_i$的样本个数，且有$\sum_{i=1}^n{\left| D_i \right|}=\left| D \right|$。记子集$D_i$中属于类$C_k$的样本的集合为$D_ik$,$\left| D_ik \right|$表示$D_ik$的样本个数。

则数据集$D$的经验熵为
$H\left( D \right) =-\sum_{k=1}^K{\frac{\left| C_k \right|}{\left| D \right|}\log \frac{\left| C_k \right|}{\left| D \right|}}$
特征$A$对数据集$D$的经验条件熵为
$H\left( D\left| A \right. \right) =-\sum_{i=1}^n{\frac{\left| D_i \right|}{\left| D \right|}}\sum_{k=1}^K{\frac{\left| D_{ik} \right|}{\left| D_i \right|}\log \frac{\left| D_{ik} \right|}{\left| D_i \right|}}$
特征$A$对训练数据集$D$的信息增益为
$g(D, A) = H\left( D \right) - H\left( D\left| A \right. \right)$
【补充: 熵-联合熵-条件熵关系及推导】

设$X,Y$是两个变量集合，$x,y$分别是$X,Y$中的具体元素，变量集合的熵-联合熵-条件熵(衡量信息的不确定性，值越大，不确定性越大)的关系如图所示

左边的椭圆代表$H(X)$,右边的椭圆代表$H(Y)$,中间重合的部分代表互信息或者信息增益$I(X,Y)$, 左边的椭圆去掉重合部分代表$H(X|Y)$,右边的椭圆去掉重合部分代表$H(Y|X)$。两个椭圆的并集代表$H(X,Y)$。

具体地
$H\left( X \right) =-\sum_{x\in X}{p\left( x \right) \log p\left( x \right)}$ $H\left( X,Y \right) =-\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \log p\left( x,y \right)}}$ $H\left( Y\left\| X \right. \right) =H\left( X,Y \right) -H\left( X \right)$
$=\sum_{x\in X}{p\left( x \right) \log p\left( x \right)}-\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \log p\left( x,y \right)}}$ $=\sum_{x\in X}{p\left( x \right) \log p\left( x \right)}-\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \left( \log p\left( x \right) +\log p\left( y\left\| x \right. \right) \right)}}$ $=\sum_{x\in X}{p\left( x \right) \log p\left( x \right)}-\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \log p\left( x \right)}}-\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \log p\left( y\left\| x \right. \right)}}$

又根据联合概率、全概率与边缘概率间的关系可得
$\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \log p\left( x \right)}}=\sum_{x\in X}{\log p\left( x \right) \sum_{y\in Y}{p\left( x,y \right)}}=\sum_{x\in X}{p\left( x \right) \log p\left( x \right)}$
则 $H\left( Y\left\| X \right. \right) =H\left( X,Y \right) -H\left( X \right) =-\sum_{x\in X}{\sum_{y\in Y}{p\left( x,y \right) \log p\left( y\left\| x \right. \right)}}$

条件熵在最大熵模型中有定义，这里特意推导一下，加深印象

实例

考虑如下经典数据集,记录了某个人在14天中根据天气情况是否去打高尔夫。

	Outlook	Temp	Humidity	Wind	Play Golf
0	Rainy	Hot	High	FALSE	No
1	Rainy	Hot	High	TURE	No
2	Overcast	Hot	High	FALSE	Yes
3	Sunny	Mild	High	FALSE	Yes
4	Sunny	Cool	Normal	FALSE	Yes
5	Sunny	Cool	Normal	TURE	No
6	Overcast	Cool	Normal	TURE	Yes
7	Rainy	Mild	High	FALSE	No
8	Rainy	Cool	Normal	FALSE	Yes
9	Sunny	Mild	Normal	FALSE	Yes
10	Rainy	Mild	Normal	TURE	Yes
11	Overcast	Mild	High	TURE	Yes
12	Overcast	Hot	Normal	FALSE	Yes
13	Sunny	Mild	High	TURE	No

由上述定义可知，$K=2$,不打的天数$|C_1|=5$,打的天数$|C_2|=9$,总天数$|D|=14$。令$A=Outlook$，则$A$有3种不同的取值，其中$a_1=Rainy$,$Rainy$的总天数$|D_1|=5$,$Rainy$中不打的天数$|D_{11}|=3$,$Rainy$中打的天数$|D_{12}|=2$,$a_2=Overcast$,$Overcast$的总天数$|D_2|=4$,$Overcast$中不打的天数$|D_{21}|=0$,$Overcast$中打的天数$|D_{22}|=4$, $a_3=Sunny$,$Sunny$的总天数$|D_3|=5$,$Sunny$中不打的天数$|D_{31}|=2$,$Sunny$中打的天数$|D_{32}|=3$

则数据集$D$的经验熵为

$H\left( D \right) =-\frac{5}{14}\times \log \frac{5}{14}-\frac{9}{14}\times \log \frac{9}{14}=0.9402$

特征$A$对数据集$D$的经验条件熵为

$H\left( D\left| A \right. \right) =-\frac{5}{14}\times \left( \frac{3}{5}\times \log \frac{3}{5}+\frac{2}{5}\times \log \frac{2}{5} \right) -\frac{4}{14}\times \left( 0+0 \right)\\ -\frac{5}{14}\times \left( \frac{2}{5}\times \log \frac{2}{5}+\frac{3}{5}\times \log \frac{3}{5} \right) =0.6935$

特征$A$对训练数据集$D$的信息增益为

$g(D, A) = H\left( D \right) - H\left( D\left| A \right. \right)=0.2467$

其他特征的信息增益的计算与特征$Outlook$的相似，选取信息增益最大的某个特征作为根节点的划分依据。

说明
- 熵中的对数以2为底或以$e$为底(自然对数)都可以，其单位分别称作比特(bit)或纳特(nat)
- (经验)熵表示数据集类别的纯度(不确定性)。当数据集中的每个类别都一样时，纯度最高，不确定性最小，熵最小，为$0$;当数据集中的每个类别都不一样时，纯度最低，不确定性最大，熵最大，为$log|D|$
- 熵的取值只与样本的分布有关，而与样本的取值无关
- (经验)条件熵表示在给定某种特征条件下，数据集类别的纯度(不确定性)
- 信息增益表示在给定某种特征下，使数据集类别纯度增大(不确定性减小)的程度。信息增益越大，的某种特征表明其具有更强的分类能力。这个度量在信息论中称为互信息，信息增益与互信息在数值上是相等的
- 在同一样本集中，某种特征的取值个数越多，其信息增益往往越大

信息增益比

定义

特征$A$对训练集$D$信息增益比$g_r(D,A)$定义为其信息增益$g(D,A)$与训练集$D$关于特征$A$的值的熵$H_A(D)$之比，即
$g_r\left( D,A \right) =\frac{g\left( D,A \right)}{H_A\left( D \right)}$
其中
$H_A\left( D \right) =-\sum_{i=1}^n{\frac{\left| D_i \right|}{\left| D \right|}}\log \frac{\left| D_i \right|}{\left| D \right|}$
叫做本征信息(Intrinsic information), 用于”惩罚“分支数目。当本征信息增大时(特征的取值个数比较多)，该特征的重要性也就降低了。
实例

由上述分析可知，对特征$Outlook$有：
$H_A\left( D \right) =-\frac{5}{14}\times \log \frac{5}{14}-\frac{4}{14}\times \log \frac{4}{14}-\frac{5}{14}\times \log \frac{5}{14}=1.577$ $g_r\left( D,A \right) =\frac{g\left( D,A \right)}{H_A\left( D \right)}=\frac{0.2467}{1.577}$
其他特征的信息增益比的计算与特征$Outlook$的相似，选取信息增益比最大的某个特征作为根节点的划分依据。
说明
- 解决了信息增益存在偏向于选择取值较多的特征的问题

基尼指数

定义

分类问题中，假设有$K$个类，样本点属于第$k$类的概率为$p_k$ ，则概率分布的基尼指数定义为

对于给定样本集合$D$，$C_k$是$D$中属于第$k$类的样本子集，其基尼系数为：

如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D_1$和$D_2$两部分，则在特征$A$的条件下，集合$D$的基尼指数为

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

下面通过具体的二分类为例给出基尼指数、熵和误分类的关系图。其中横坐标表示概率$p$,纵坐标表示不同衡量标准下数据集的不确定性。这三种度量相似，但是熵和基尼指数是可导的，更适合数值优化。
```
 import numpy as np
 from matplotlib import pyplot as plt 
 import matplotlib as mpl
 %matplotlib inline
 mpl.rcParams['font.sans-serif'] = ['simHei']
 mpl.rcParams['axes.unicode_minus'] = False
    
 p = np.linspace(0.0001, 0.9999 ,50)
 Gini = 2 * p * (1-p)
 H = (-p * np.log2(p) - (1 - p) * np.log2(1 - p))
 x1 = np.linspace(0,0.5,50)
 y1 = x1
 x2 = np.linspace(0.5,1,50)
 y2 = 1- x2
     
 # plt.figure(figsize=(20,10))
 plt.plot(p, Gini, 'r-', label='基尼指数')
 plt.plot(p, H, 'b-', label='熵')
 plt.plot(x1, y1, 'g-', label='分类误差率')
 plt.plot(x2, y2, 'g-')
 plt.legend() 
 plt.show()
```
实例

以特征$Outlook$为例，分别计算其在取不同特征值时的基尼指数,有：
$Gini\left( D,a_1=Rainy \right) =\frac{5}{14}\times \left( 1-\left( \frac{3}{5} \right) ^2-\left( \frac{2}{5} \right) ^2 \right) +\frac{9}{14}\times \left( 1-\left( \frac{2}{9} \right) ^2-\left( \frac{7}{9} \right) ^2 \right)\\ =0.394$ $Gini\left( D,a_2=Overca \right) =\frac{4}{14}\times \left( 1-\left( \frac{0}{4} \right) ^2-\left( \frac{4}{4} \right) ^2 \right) +\frac{10}{14}\times \left( 1-\left( \frac{5}{10} \right) ^2-\left( \frac{5}{10} \right) ^2 \right)\\ =0.357$ $Gini\left( D,a_3=Sunny \right) =\frac{5}{14}\times \left( 1-\left( \frac{2}{5} \right) ^2-\left( \frac{3}{5} \right) ^2 \right) +\frac{9}{14}\times \left( 1-\left( \frac{3}{9} \right) ^2-\left( \frac{6}{9} \right) ^2 \right)\\ =0.457$
由计算结果可知，在特征$Outlook$中选取$a_2=Overcast$为最优切分点。其他特征最优切分点的选取与$Outlook$相似。选取所有特征中，基尼指数最低的某个特征的某个取值作为根节点最终的最优切分点。
说明
- 基尼指数可以看成是信息熵中﹣$logp$在$p=1$处的一阶泰勒展开，用于简化运算
- 基尼指数越小，数据集的纯度越高，不确定性越小，其性质与信息熵一致

决策树生成

决策树的生成按最优特征的选取准则不同，主要有如下三种生成算法

ID3：以信息增益最大化作为最优特征选取依据，是一种多叉树，且特征必须为离散变量
C4.5：以信息增益比最大化作为最优特征选取依据，也是一种多叉树，不过特征可以是连续变量
CART：分类树以某个特征的某个取值的基尼指数最小化作为最优划分点的选取依据，回归树以平方误差最小化作为最优特征选取依据，是一种二叉树，可用于分类和回归

ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。其采用贪心策略，每次选取的特征都是当前节点的最优选择，并不关心最后生成的决策树是否达到全局最优。具体地，从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点(该特征在之后的特征选择中，将不再起作用)，再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一颗决策树。ID3相当于用极大似然法进行概率模型的选择。

不足点：

ID3算法不能处理连续特征
ID3算法没有考虑到特征值缺失的情况
ID3算法没有考虑过拟合的问题
ID3采用信息增益大的特征优先建立决策树的节点。在相同条件下，取值比较多的特征比取值少的特征信息增益大,特征选择的时候容易偏向于取值较多的特征

C4.5算法

C4.5算法针对ID3算法的不足给出了改进的思路与实现，具体地

对于连续特征的问题，C4.5的解决办法是利用二分法将连续的特征离散化(连续特征的分界点通过信息增益来确定，而属性的选择采用信息增益比)。比如$m$个样本的连续特征$A$按从小到大排列为 $a_1,a_2,\cdots,a_m$ ，取相邻两个样本值的平均数，一共取得$m-1$个划分点，其中第$i$个划分点$T_i$表示为$T_i=\frac{a_i+a_{i+1}}{2}$。对上述$m-1$个点，分别计算以该点作为二元分类点时的信息增益，选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的信息增益最大的点为$a_t$，则小于$a_t$的值为类别1，大于$a_t$的值为类别2，这样就将连续特征离散化了。最后计算离散之后的特征的信息增益比。值得注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的特征选择过程。 具体数值例子见周志华的西瓜书。

对于缺失值的问题，有两种情况待解决:(1)如何在属性值缺失的情况下进行划分属性的选择。(2)给定划分属性后，若某个样本在该属性上的值缺失，如何对该样本进行划分。对于问题(1),C4.5的解决办法是将数据分成两部分，一部分是没有缺失值的数据$D1$，另一部分是有缺失值的数据$D2$。然后对$D1$计算信息增益比，最后再乘上一个权值$\frac{\left| D2 \right|}{\left| D1 \right|+\left| D2 \right|}$。对于问题(2),C4.5的解决办法是将该缺失特征值的样本划分到该特征的所有子节点内，并在不同的子节点内乘上不同的权重系数。具体数值例子见周志华的西瓜书。

对于过拟合问题，C4.5 引入了正则化系数进行初步的剪枝。

对于将信息增益作为选取特征的准则容易偏向于取值较多的特征的问题。C4.5引入信息增益比以校正信息增益容易偏向于取值较多的特征的问题。值得说明的是，信息增益比偏向于特征取值数目较少的特征，因此C4.5算法并不是直接选择信息增益比最大的属性，而是使用了一个启发式：先从候选划分特征中找出信息增益高于平均水平的特征，再从中选择信息增益比最高的。

除了上面的4点，C4.5和ID3的思路区别不大。

不足点：

由于决策树算法非常容易过拟合，因此对生成的决策树必须进行剪枝处理。C4.5的剪枝方法有优化的空间。主要有两种思路，一是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
C4.5生成的是多叉树，而在计算机中二叉树模型比多叉树有更高的运算效率。
C4.5只能用于分类
C4.5使用了熵的模型，含有大量耗时的对数运算，如果是连续值还有大量的排序运算。

CART算法

CART假设决策树是二叉树，其内部结点特征的取值只有”是”和”否”，左分支是取值为”是”的分支，右分支则相反。

分类树生成

CART分类树在C4.5的基础上又做了进一步的改进。具体地

CART分类树使用基尼指数替代信息增益率，大大简化了特征选择时大量的对数运算，同时也保持了与熵模型相似的性质。

在特征选择方面，CART分类树与ID3和C4.5不同，不是去选择某个特征作为划分依据，而是具体到某个特征的某个取值作为划分点依据对样本集进行二分，最终形成一个二叉树。具体数值例子见李航的统计学习方法。值得说明的是，在ID3或者C4.5的分类树中，离散特征只会参与一层节点的建立；CART树中离散的特征可能参与多层节点的建立。

CART分类树对连续值的处理，其思想和C4.5是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益，则CART分类树使用的是基尼指数。

剪枝方面，CART树不用提前确定权衡因子$\alpha$,而是在剪枝的同时找到最优的$\alpha$。

除了上述几点，CART和C4.5的思路区别不大。
回归树生成

CART回归树和CART分类树的生成过程大部分是类似的。不同点在于：

　　样本的输出值不同。分类树输出是离散值，回归树输出是连续值

　　对连续值的处理方法不同。CART分类树采用基尼指数最小化准则，而CART回归树采用平方误差最小化准则。具体地，在输入(特征)空间中任选某个特征(变量)$j$的某个取值$s$作为切分点，将数据集划分成两个子集$R_1\left( j,s \right)$和$R_2\left( j,s \right)$。然后分别求解

$\underset{j,s}{\min}\left[ \underset{c_1}{\min}\sum_{x_i\in R_1\left( j,s \right)}{\left( y_i-c_1 \right) ^2}+\underset{c_2}{\min}\sum_{x_i\in R_2\left( j,s \right)}{\left( y_i-c_2 \right) ^2} \right]$

从而得到最优的切分(特征)变量$j$与切分点$s$。其中 $R_1\left( j,s \right) =\left\{ x\|x^{\left( j \right)}\le s \right\}$ , $R_2\left( j,s \right) =\left\{ x\|x^{\left( j \right)}>s \right\}$ , $c_1=ave\left( y_i\|x_i\in R_1\left( j,s \right) \right)$ , $c_2=ave\left( y_i\|x_i\in R_2\left( j,s \right) \right)$ 。递归的应用上述方法对新分裂的节点的样本集进行相同的操作，直到满足停止条件为止，最终形成一颗回归树。具体数值例子见决策树

　　预测的方式不同。具体地,CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

决策树剪枝

剪枝主要是为了防止生成的决策树过拟合，增大决策树的泛化能力。具体地可分为两种，一种叫预剪枝，另一种叫后剪枝。

预剪枝

预剪枝是指在决策树生成过程中，预先设定阀值，当低于某个阀值指标时，则不再继续分裂生长。常见的方法有：

限制树的深度
限制叶节点数
限制叶节点的样本数
限制信息增益的大小

后剪枝

后剪枝是指先从训练集中生成一颗完整的决策树，然后利用验证集自底向上地对内部节点(非叶子节点)进行测试，若将某个非叶子节点对应的子树替换为叶子节点可以提升决策树的精度(准确度)，则进行剪枝。即将子树替换为叶子。后剪枝方法有好多种，具体见决策树，下面只介绍李航的《统计学习方法》一书中的两种

一般剪枝

决策树的剪枝通过极小化决策树整体的损失函数来实现，损失函数的极小化等价于一种正则化的极大似然估计。具体地，设树$T$的叶节点个数为$|T|$，$t$是树$T$的叶节点，该叶节点有$N_t$个样本点，其中$k$类的样本点有$N_{tk}$个，$k=1,2,\cdots,K$，$H_t(T)$为叶节点$t$上的经验熵，$\alpha \ge 0$为超参数。则决策树的结构损失函数为

$C_{\alpha}\left( T \right) =\sum_{t=1}^{\left| T \right|}{N_tH_t\left( T \right)}+\alpha \left| T \right|$

其中

$H_t\left( T \right) =-\sum_{k=1}^K{\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}}$

令

$C\left( T \right) =\sum_{t=1}^{\left| T \right|}{N_tH_t\left( T \right)}=-\sum_{t=1}^{\left| T \right|}{\sum_{k=1}^K{N_{tk}\log \frac{N_{tk}}{N_t}}}$

则损失函数可进一步表示为

$C_{\alpha}\left( T \right) =C\left( T \right) +\alpha \left| T \right|$

其中$C_{\alpha}\left( T \right)$表示模型对训练数据的预测误差，$|T|$表示模型的复杂度，超参数$\alpha$控制两者的比重。较大的$\alpha$偏向较简单的模型，较小的$\alpha$偏向较复杂的模型。

当给定超参数$\alpha$后，通过不断剪枝来减小决策树模型的整体损失。具体步骤为

(1) 计算每个叶节点的经验熵，从而得到初始的未剪枝的模型的损失值$C_{\alpha}\left( T_B \right)$，并假设其值为最小的$C_{\alpha}\left( T_{min} \right)$

(2) 自底向上，从左往右依次遍历决策树的非叶子节点，计算将其替换为叶子节点后的损失值$C_{\alpha}\left( T_A \right)$，若$C_{\alpha}\left( T_A \right) < C_{\alpha}\left( T_{min} \right)$，则进行替换剪枝，并令$C_{\alpha}\left( T_{min} \right) = C_{\alpha}\left( T_A \right)$。若$C_{\alpha}\left( T_A \right) \ge C_{\alpha}\left( T_{min} \right)$,则进行下一个非叶节点的计算。重复上述步骤，直到遍历完所有内部节点。最终得到的$C_{\alpha}\left( T_{min} \right)$对应的树模型就是最终想要的最优树模型。

说明：训练集训练完后，在验证集上进行上述步骤或者全部都在训练集上进行上述步骤都可以

CART剪枝

相比一般剪枝算法，CART剪枝算法的优势在于，不用提前确定$\alpha$值，而是在剪枝的同时找到最优的$\alpha$值。 其由两步组成：首先从生成算法产生的决策树$T_0$底端开始不断地剪枝，直到$T_0$的根节点，形成一个子树序列 $\left\{T_0,T_1,\cdots,T_n \right\}$ ;然后通过交叉验证法在独立的验证集上对子树序列进行测试，从中选择最优子树。具体地

从整体树$T_0$开始剪枝。对$T_0$的任意内部节点$t$，以$t$为单节点树的损失函数为

$C_{\alpha}\left( t \right) =C\left( t \right) +\alpha$

以$t$为根节点的子树$T_t$的损失函数为

$C_{\alpha}\left( T_t \right) =C\left( T_t \right) +\alpha \left| T_t \right|$

则当$\alpha =\frac{C\left( t \right) -C\left( T_t \right)}{\left| T_t \right|-1}$时，$T_t$与$t$有相同的损失函数值，而$t$的节点少，因此$t$与$T_t$更可取，对$T_t$进行剪枝。

对$T_0$的每一个内部节点$t$,计算

$g(t) =\frac{C\left( t \right) -C\left( T_t \right)}{\left\| T_t \right\|-1}$

它表示剪枝后整体损失函数减少的程度。在$T_0$中剪去$g(t)$最小的$T_t$,将得到的子树记为$T_1$,同时将最下的$g(t)$设为$\alpha_1$,$T_1$为区间$[\alpha_1,\alpha_2)$的最优子树。如此剪枝下去，直到得到根节点。这一过程中，不断地增加$\alpha$的值，产生新的区间。最终得到子树序列 $\left\{T_0,T_1,\cdots,T_n \right\}$ 。

然后通过独立的验证集计算各个子树的平方误差或基尼指数，性能指标最好的子树即是当前最优的决策树。且在子树序列中，每颗子树$T_0,T_1,\cdots,T_n $都对应着一个参数$\alpha_0,\alpha_1,\cdots,\alpha_n $。

基于上述说明，给出如下总结过程：

对应给定的决策树$T_0$

计算所有内部节点的剪枝系数 $g(t) =\frac{C\left( t \right) -C\left( T_t \right)}{\left\| T_t \right\|-1}$
查找最小剪枝系数的节点，剪枝得到决策树$T_k$
重复以上1、2的步骤，直到决策树$T_k$只有一个节点
得到最终的决策树序列$T_0,T_1,\cdots,T_n $和剪枝系数$\alpha_0,\alpha_1,\cdots,\alpha_n $
选择合适的性能指标(平方误差或基尼指数),利用验证集计算决策树序列各个子树的性能指标值，确定出最优的子树及对应的剪枝系数

具体数值例子见决策树

优缺点

优点

分类速度快
相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
能处理非线性的数据，对于异常点的容错能力好，健壮性高
基本不需要预处理，不需要提前归一化，处理缺失值
可以用于特征工程，进行特征的选择(实战部分有涉及)
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值
可以交叉验证的剪枝来选择模型，从而提高泛化能力
可转化为规则，容易软件实现

缺点

决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量、限制决策树深度等方法来改进
决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决，如随机森林
寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善
对类别不平衡的数据不友好，如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决

小结

下面给出三种生成决策树的经典算法的比较，便于理解与记忆

特点\算法	ID3	C4.5	CART
应用类型	分类	分类	分类与回归
特征选择	信息增益	信息增益比	基尼指数
变量类型	只能离散	连续或离散	连续或离散
树结构	多叉树	多叉树	二叉树
终止条件	卡方独立性检验	特征选择标准的下限	叶节点达到最小样本数量
剪枝	不支持	支持	支持
缺失值处理	不支持	支持	支持

备注

无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。

参考

随机森林

除了剪枝可以防止过拟合，随机森林也可以有效防止过拟合。它是一种基于Bagging(Bootstrap aggregating)的集成(ensemble)模型。具体地，从训练集中，每次有放回的随机选取固定大小的一个子训练集，利用得到的多个子训练集同时训练多个CART决策树(可以不剪枝)(弱学习器)。预测的时候综合考虑多个结果做最终预测，实验表明，多个弱学习器的集成能大大提高系统的性能(见周志华的西瓜书)。值得说明的是，由于随机采样，实际上只有$63.2%$的样本集参与了模型的学习，剩下的样本集可作为验证集进行模型的泛化性能测试。

随机性体现在两个方面：

行随机。即随机有放回地选取一定大小的样本集
列随机。在选取最优特征时，随机森林不像决策树那样从所有特征中选取最优的一个，而是随机选择一部分特征，从随机选择的特征中再进行最优特征的选取，作为最终节点分裂的条件

随机森林不仅消除了单一决策树易过拟合的特点，还减小了预测的方差。(预测值不会因训练数据的微小变化而发生剧烈变化)

carlos9310

决策树与随机森林

决策树