决策树 | Hardcore Coder

0.1. ID3

熵：随机变量的不确定性，越不确定的事物，它的熵就越大。 $H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$

条件熵： $H(X|Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)$

信息增益Information Gain：IG(X,Y) = H(X)-H(X|Y). 这里X指label，Y指某个特征。信息增益（IG）是描述某一个特征属性的存在与否，对总体信息熵的变化量影响。

ID3递归建树： 假设当前节点，有数据集D和属性集合{A}。计算D的所有属性 $A_i$ 的IG，选择IG最大的属性进行分裂，子节点个数为该属性所有取值（即完全分裂）。停止分裂条件：节点的数据集属于同一类，D的所有特征均相同，IG小于阈值。

ID3模型：

只能处理类别数据，即离散数据
节点分裂的时候，分裂所有的值

0.2. C4.5

针对ID3的缺点，C4.5的改进：

选择特征的时候用信息增益比代替信息增益
能够处理连续值特征
能够处理缺失值特征
剪枝

0.2.1. 信息增益比

信息增益比Information Gain Ratio：信息增益和特征熵的比值。特征熵又叫Split Information，$IGR(D,A) = \frac{IG(D,A)}{H_A(D)}$

通过 IG 的公式可以推测出，当子树固定时，总的信息熵固定，只要条件熵（就是某一特征属性的信息熵）越小，那么 IG 的值就越大。通过条件熵的计算公式，如果某一个属性的取值越多，那么这个条件熵的值就会越小。从而，选择 IG 最大的属性，可以理解成选择取值较多的属性。

条件熵记为${SplitInfo= -\sum_i{p(v_i)}log_2{p(v_i)}}$，其中$v_i$为某一特征属性下的第$i$个分支属性。注意，在求信息增益的时候，是计算样本label的概率，特征熵是计算某属性所有取值的概率。

特征属性取值多，特征熵会比较大，所以信息增益比可以修正信息增益的偏差。比如连续值属性，不同的特征取值可能会非常多，这个时候就需要采用信息增益比来选择特征进行分裂。

0.2.2. 处理连续值

C4.5处理离散值的方式与ID3一样，分支数是所有的不同取值个数，即完全分裂；对于连续值，分支数是二叉树。所以对于连续值的属性，在子树选特征的时候还可以被使用；离散特征不会，因为一旦分裂了，子树的该特征都取值相同，$IG=0$.

0.2.2.1. 选分裂的值

首先，连续属性离散化：先对连续值进行排序，然后相邻的两个点取中间值作为分裂点的集合，N个值有N-1个分裂点，对每个分裂点<=和>做二叉分裂。另外可优化的是，对排好序的特征，只有在label发生改变（即label发生了变化）的地方才需要分裂，这可以显著减少运算量[2]。

然后，如何从这至多N-1个分裂点选出最优的那个呢？经证明，在决定连续特征的分界点时采用IG这个指标。因为若采用信息增益率，特征熵影响分裂点信息度量准确性，若某分界点恰好将连续属性分成数目相等的两部分时，特征熵最大，对IGR的影响最大。二叉树使用IGR会倾向于等分，所以我们改用IG来计算，每一种分裂方法，计算两个分支的IG之和。反过来考虑，二叉树的时候分支数被限定为2，所以IG无法倾向于选择取值多的方案。

0.2.2.2. 选属性

C4.5在选择哪个属性进行分裂的时候，则是通过Information Gain Ratio来选择。对于离散的属性，跟ID3没有大区别；对于连续变量的特征，IGR是所有不同的连续值都考虑进去。例如一颗子树是这样的：

temperature	2	2	2	3	3	6	7	7	7	7
label	n	n	y	n	n	y	n	y	y	y

温度可理解为连续值，尽管这里是integer格式，这个特征的 $IGR = \frac{IG}{SplitInfo}$ ， $H(X)=-(\frac{5}{10}*\log\frac{5}{10}+\frac{5}{10}*\log\frac{5}{10})$ ， $H(X|T)=\frac{3}{10}(-\frac{2}{3}\log\frac{2}{3}-\frac{1}{3}\log\frac{1}{3}) + \frac{2}{10}(-1\log1-0\log0) + \frac{1}{10}(-1\log1) + \frac{4}{10}(-\frac{1}{4}\log\frac{1}{4}-\frac{3}{4}\log\frac{3}{4})$ ，

假设分解特征为<=2和>2通过上节求得是最优的（IG最大），$SplitInfo(T)=-(\frac{3}{10}\log\frac{3}{10} + \frac{7}{10}\log\frac{7}{10} )$。以上就是这颗子树的温度属性的IGR，我们把所有的属性的IGR都求一遍（无论离散、连续），找到IGR最大的那个即为要进行分裂的属性。

选择连续属性的哪个分界点，用IG来比较；求得每个连续属性的最优分界点之后，再用IGR来比较属性之间哪个最优。

0.2.2.3. 对连续属性的处理如下[2]

对特征的取值进行升序排序
两个特征取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的信息增益。优化算法就是只计算分类属性发生改变的那些特征取值
选择修正后信息增益最大的分裂点作为该特征的最佳分裂点
计算最佳分裂点的信息增益率（Gain Ratio）作为特征的Gain Ratio。注意，此处需对最佳分裂点的信息增益进行修正：减去log2(N-1)/|D|（N是连续特征的取值个数，D是训练数据数目，此修正的原因：当离散属性和连续属性并存时，C4.5算法倾向于选择连续特征做最佳树分裂点）

0.2.3. 处理缺失值

0.2.3.1. 选择属性时

假设10个样本，属性是a,b,c。在计算a属性熵时发现，第10个样本的a属性缺失，那么就把第10个样本去掉，前9个样本组成新的样本集，在新样本集上按正常方法计算a属性的IG，然后结果乘0.9（不含缺失值样本占原始样本的比例），就是a属性最终的IG，即$Gain = ratio*(H(X) - H(X|Y))$ 。求IGR时， $SplitInfo(a) = -\sum_{i=1}^k \frac{|S_i|}{|S|}log_2\frac{|S_i|}{|S|} - \frac{|S_{unknow}|}{|S|}log_2\frac{|S_{unknow}|}{|S|}$ ，其中$S_{unknow}$是含缺失值的数据组成的样本集。[3]

0.2.3.2. 以概率分裂缺失样本

确定了当前子树的分裂方式（属性+分界点），才会知道子节点样本的数量。把缺失值按照子节点样本出现的概率，分配到各个子节点。

还是上面那个温度的例子，这个子树有10个无缺失值的样本，假设选定了温度属性，并按照温度属性<=2和>2为特征，划分了两个子树；假设另外有3个温度有缺失的样本，每个样本按照3/10的权重安排到<=2的子树，7/10的权重安排到>2的子树，其他的10个样本的权重为1。这样后续在算熵的时候，部分样本就带着权重算罢了。

0.2.3.3. 剪枝

[4]介绍了一点简单的简直方法；另外C4.5主要采用后剪枝中的悲观剪枝法。

0.2.4. C4.5模型的特点：

多叉树
只能用于分类
熵模型有对数运算，耗时；处理连续值时要排序，耗时

0.3. CART

针对C4.5的缺点，CART的改进：[5]

简化为二叉树
可以处理分类，也可以处理回归
使用Gini系数来代替信息增益率，不再使用复杂度高的熵模型

0.3.1. Gini系数

在分类问题中，假设有K个类别，第k个label的概率为 $p_k$ , 则基尼系数的表达式为 $Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$ . 如果是二类分类问题，如果属于第一个样本label的概率是p，则基尼系数的表达式为$Gini(p) = 2p(1-p)$. 给定样本D，Gini系数为 $Gini(D) = 1-\sum\limits_{k=1}^{K}(\frac{|C_k|}{|D|})^2$ ，其中$C_k$是D中属于第k类的样本集合； $Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$ ，其中A表示按照某一个特征进行二元分裂，得到子集D1和D2。Gini(D)表示样本D的不确定性，Gini(D,A)表示按照特征A分裂后样本的不确定性。

比较下基尼系数表达式和熵模型的表达式，二次运算比对数简单很多，基尼系数可以做为熵模型的一个近似替代。Gini系数越大，样本不确定性越大。CART分类树算法就是使用的基尼系数来选择决策树的特征。

为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树，可以进一步简化基尼系数的计算。

0.3.2. CART分类树

CART分类树连续值的处理，思想和C4.5相同，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是IG，则CART分类树使用的是基尼系数。对于某个连续值属性，同样也是先排序然后离散化，对每个划分点t做二元分类（<=t，>t），选择Gini系数最小的点。如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
CART分类树离散值的处理，采用的思路是不停的二分离散特征。因为每个节点都是二叉树，所以离散特征一次不会完全分裂，因此后面还有机会在子节点继续选择这个特征。但在ID3和C4.5中，离散属性都是完全分裂，只会参与一次节点的建立。

CART分类树的步骤： 从根节点开始，用训练集递归的建立CART树。

对于当前节点的数据集为D，如果样本个数小于阈值、或者没有特征、或者样本集D的基尼系数$Gini(D)$小于阈值，则返回决策树子树，当前节点停止递归。
计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数$Gini(D,A)$。缺失值的处理方法和C4.5算法相同。
在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
对左右的子节点递归的调用1-4步，生成决策树。
采用叶子节点里概率最大的类别作为当前节点的预测类别。

注意，算法计算Gini系数的时候，用到的是两种Gini系数：

$Gini(D,A)$用于选择特征和分裂点；
$Gini(D)$用于计算$Gini(D,A)$子集的值，以及判断当前节点是否满足停止递归的条件

具体例子参考李书[6]

0.3.3. CART回归树

CART回归树和CART分类树大部分类似，所以这里只讨论CART回归树和CART分类树不同之处：

连续值的处理方法不同。不使用Gini系数，而是用和方差来度量。对于任意属性A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点： $\underbrace{min}_{A,s}\Bigg[\underbrace{min}_{c_1}\sum\limits_{x_i \in D_1(A,s)}(y_i - c_1)^2 + \underbrace{min}_{c_2}\sum\limits_{x_i \in D_2(A,s)}(y_i - c_2)^2\Bigg]$ ，其中x为样本，y为样本的输出值，c1为D1数据集的样本输出均值，c2为D2数据集的样本输出均值。
决策树建立后做预测的方式不同。回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

0.3.4. CART的剪枝

决策树算法容易对训练集过拟合，CART树进行剪枝，增加决策树的泛化能力。CART采用Cost-Complexity Pruning (CCP):

从生成好的决策树（记为$T_0$）的底端开始，不断剪枝，直到$T_0$的根节点为止，得到一个子树序列 $\{T_0, T_1, \dots,T_n\}$ ；
交叉验证，在独立的验证集合上对子树序列测试，从中选择最优子树。

0.3.4.1. 剪枝-得到子树序列

定义损失函数为$C_\alpha(T) = C(T) + \alpha|T|$，其中T为任意子树，C(T)为训练集的预测误差（如Gini系数），|T|为子树叶子节点的个数，$\alpha$为正则化参数，$C_a(T)$是子树复杂度有关的损失函数。

对固定的$\alpha$，一定存在使得损失函数 $C_{\alpha}(T)$ 最小的子树（记为 $T_{\alpha}$ ），这个最优子树是唯一的。

经证明，用递归的方法对树进行剪枝，将 $\alpha$ 从小增大， $0=\alpha_0<\alpha_1<\dots<\alpha_n, i=0,1,\dots,n$ ，区间 $[\alpha_i,\alpha_{i+1})$ 对应着序列中的子树 $T_i$ ， $i=0,1,\dots,n$ . 序列中的子树是嵌套的。

当$\alpha$很小，甚至等于0的时候，$T_0$即是最优；当$\alpha$增大，最优子树的规模变小；当$\alpha$很大时，单个根节点$T_n$是最优的。

现在只知道$\alpha_0=0$和$T_0$，怎么找到序列$\alpha_1,\dots, \alpha_n$和$T_1,\dots, T_n$呢？

从完整的树$T_0$开始，对$T_0$的任意内部结点t，作为剪枝的候选：

如果以t为单节点树， $C_{\alpha}(t) = C(t) + \alpha$ ；以t为根节点的子树， $C_{\alpha}(T_t) = C(T_t) + \alpha|T_t|$ .

参数$\alpha$的临界点为$\alpha = \frac{C(t)-C(T_t)}{|T_t|-1}$，这时子树$T_t$跟单节点t的损失函数一样，而t节点更少，所以t比$T_t$更可取，从$T_0$上把$T_t$剪掉只保留t.

对每个$T_0$上的内部节点都计算$g(t) = \frac{C(t)-C(T_t)}{|T_t|-1}$，在$T_0$上剪去$g(t)$最小的以$t$为根结点的子树，得到$T_1$，并另$\alpha_1 = g(t)$。$T_1$为区间$[\alpha_1,\alpha_2)$的最优子树！

重复此操作，直到得到根节点。

对$\alpha$的理解

剪枝的度量是损失函数 $C_{\alpha}(T)$ 。剪不剪子树T，取决于 $C_{\alpha}(T)$ 是否减小。不同的 $\alpha$ 对应不同的剪枝方式，即剪掉不同的子树。那我们从0开始遍历 $\alpha$ ，来得到不同的剪枝方案 $\{T_0, T_1, \dots,T_n\}$ 。

注意，$C_{\alpha}(T)$是全局的一个损失函数。当$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$时，在节点t处被剪枝时，误差增加了$C(t)-C(T_t)$；但树的复杂程度减少了$\alpha(|T_t|-1)$。可理解为，这时误差的增加量与复杂程度的减少量相抵。

另外，$\alpha$也是剪枝的阈值。对某节点t，当$\alpha=g(t)$时，剪和不剪对总体损失函数一样。如果$\alpha>g(t)$，不剪的整体损失函数更大，应该剪；反之，$\alpha$小于$g(t)$就不该剪。损失函数可以对整个树，也可以是以t为根的子树（对t剪枝前后两者的增减是相同的）。

为什么选择最小的$g(t)$为$\alpha_i$

这个$g(t)$是剪枝的阈值。对同一颗树，$\alpha$从0开始增大，有某一颗树该剪，其他树不该剪，即$\alpha$达到了某个节点的$g(t)$但没有满足其他节点的$g(t)$。假设有多个内部节点 $g(t_1)<g(t_2)<\dots$ ，如果选择剪枝 $t_2$ ， $\alpha=g(t_2)$ ，这时剪不剪$t_2$总体损失函数相同，但是剪 $t_1$ 比不剪 $t_1$ 损失函数更小，所以剪掉 $t_1$ 的子树也是一个剪枝方案，不要在剪 $t_2$ 的子树之前遗漏 $t_1$ 的子树。在剪掉 $t_1$ 子树的基础上再剪掉 $t_2$ 的子树，损失函数进一步减小，所以 $\alpha\in[g(t_1), g(t_2))$ 时，子树 $T_1$ 是最优的；但 $\alpha$ 进一步增大 $>g(t_2)$ 时， $T_2$ 就是最优的了。

所以$\alpha$从小开始意味着自下而上的剪枝。随着$\alpha$逐渐变大，不断的剪枝，得到子树序列 [8]。关键前面提到了：序列的子树是嵌套的！

这颗树$T_0$下所有的$g(t)$先只算一次。
选最小的$g(t)$，剪枝；
剪完剩下的$g(t)$中再选出最小的，再剪枝；……；
剪到只剩根节点为止。每次剪枝可能会剪掉多个节点，所以子树序列的个数n一般比内部结点数要少。

0.3.4.2. 交叉验证得到最优子树

在验证数据集上，比较子树序列 $\{T_0, T_1, \dots,T_n\}$ ，选出Gini系数或平方误差最小的子树。

0.4. 参考资料：

决策树overfitting比较的严重，一般要做boosting