决策树

决策树一般有三个重要部分，特征选择、生成、剪枝。

• 特征选择

  有这么四种标准

  构建分类树的话是信息增益、信息增益比、基尼指数

  构建回归树的话是平方误差最小化。

• 生成

  基本思路是，找到最佳分裂点，将数据集分成若干部分（具体地，普通决策树是根据最佳分裂特征的取值有多少个就将数据集分成几个部分，CART是只分成两部分，所以普通决策树一般处理离散型变量，CART离散型和连续型都可以处理，而且普通决策树增长的太快，很容易过拟化），然后对每个部分递归执行上述过程，然后得到一个尽量大的树。

• 剪枝

  得到尽量大的树后，对训练集的数据可以处理的很好，但是对预测集可能会误差很大，也就是常说的过拟化，所以我们要进行剪枝，剪掉没必要的一些节点，使树别那么大。

  ​

预备知识

熵

为了描述这个属性，我们首先定义熵，来度量随机变量的不确定性。

一个有限离散随机变量的熵表示为 $H(X)=H(p)=-\sum_{i=1}^{n}{p_ilogp_i}$ p为随机变量X的概率分布，熵越大，随机变量X的不确定性就越大。

当熵中的概率由数据估计得到时，也叫经验熵。

条件熵

条件熵$H(X\mid Y)$表示在随机变量X给定的条件下，随机变量Y的条件熵，也就是X给定时，Y的条件概率分布的熵对X的数学期望，公式为 $H(Y\mid X)=\sum_{i=1}^{n}p_iH(Y\mid X=x_i)\quad ,其中p_i=P(X=x_i)$ 公式可以理解为将Y按照$p_i$分成n份，分别求了熵再乘以比例，最后加起来。

条件熵可以表示在已知随机变量X的条件下随机变量Y的不确定性。

当条件熵中的概率由数据估计得到时，也叫条件经验熵。

下面介绍这两种决策树，普通决策树和CART(分类与回归树)

1.普通决策树 - 多元切分，只能处理离散型变量

1.1首先是特征选择

普通决策树根据不同的特征选择算法，分为ID3算法和C4.5算法

• ID3算法：根据信息增益作为特征选择算法

  信息增益

  已知集合D的经验熵H(D)，给定特征A下D的经验条件熵为$H(D\mid A)$，将它们作差，也就是 $g(D,A)=H(D)-H(D|A)=-\sum_{k=1}^K\frac{\mid C_k\mid}{\mid D\mid}log_2\frac{\mid C_k\mid}{\mid D\mid}-\sum_{i=1}^n\frac{\mid D_i\mid}{\mid D\mid}·(-\sum_{k=1}^K\frac{\mid D_{ik}\mid}{\mid D_{i}\mid}log_2\frac{\mid D_{ik}\mid}{\mid D_{i}\mid})$

  $$将D根据特征A分成n个D_i,D_{ik}表示D_i集合中属于C_k类的集合,\mid\quad\mid 表示集合个数$$

  我们将它称作信息增益，代表集合D因为特征A而减少的不确定性。

  我们选取特征时，应该对每个特征计算信息增益，选取信息增益最大的特征。

• C4.5算法：根据信息增益比作为特征选择算法

  为什么在信息增益的基础上增加一个信息增益比呢？简单的说来就是：信息增益的缺点是比较偏向选择取值多的属性，因为属性选的越多，对训练集预测的结果越准，信息增益越大，但是这对测试集不一定是好事。信息增益比，在信息增益的基础上除了一项split information,来惩罚值更多的属性。

  具体可参考这个问题信息增益比与信息增益

  信息增益比

  一个特征的取值集合越多，那么它的信息增益更趋向于大，这可能对我们的判断造成影响，因此可以使用信息信息增益比作为另一特征选择准则。

  已知信息增益$g(D,A)$和D关于特征A的熵$H_A(D)=-\sum_{i=1}^n\frac{\mid D_i\mid}{\mid D\mid}log_2\frac{\mid D_i\mid}{\mid D\mid}$

  信息增益比为 $g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

1.2然后是生成

这里觉得李航老师的《统计学习方法》讲的挺好的，这里直接照搬。

输入：训练集D，特征集A，阈值e
输出：决策树T
def create(D,A):
  1.if D中所有实例都为一类Ck:
      则把它作为叶节点，类别为Ck，返回叶节点
  2.if A为空(也就是特征选完了):
      则把D归为叶节点，实例最多的类作为叶节点的类，返回叶节点
  3.否则，对A中每个特征计算信息增益（比），选择最大的特征Ag
    if 信息增益（比）小于阈值:
		则把D归为叶节点里，类别最多的类作为叶节点的类别，返回叶节点
    else:
        构建树T
        for val in Ag的所有可能取值：
        	从D分裂出一个Ag=val的非空集合Di
        	T[val] = create(Di,A-Ag)
   		返回 T

1.3最后是剪枝

• 损失函数

为了避免出现过拟合的现象，我们要对决策树进行剪枝。

设决策树的子节点集合为T，t是T中的一个元素，该叶节点有$N_t$个样本，其中k类的样本有$N_{tk}$个，共K个分类

则损失函数可以定义为 $C_{\alpha}(T)=\sum_{t=1}^{\mid T\mid}N_tH_t(T)+\alpha\mid T\mid$ 右边第一项表示误差大小，第二项表示模型的复杂度，也就是用叶节点表示，防止过拟化。（一般的损失函数都用两项来表示，误差和模型复杂度，具体可以参看另一篇文章损失函数有感）

损失函数就是在精确度和过拟化之间找到一个平衡。第二项很容易理解，$\alpha$为参数，控制两者之间的影响，较大的$\alpha$促使选择简单的模型。第一项怎么理解呢？

对每个叶节点t来说，$H_t(T)$表示t的熵（也就是不确定性）的期望，针对的是t子节点中每个数据实例的熵的期望，t子节点中有$N_t$个实例，那么t子节点总的熵（不确定性）就是$N_tH_t(T)$，整个树有$\mid T\mid$个叶节点，加起来就是整棵树的熵（不确定性，也可以理解成误差）。

• 剪枝算法

设剪枝之前的整体树为$T_A$

剪掉一组叶节点（也就是同一个父节点的叶子节点回退到父节点）后的整体树为$T_B$

计算$C_{\alpha}(T_A)$和$C_{\alpha}(T_B)$，如果剪掉后的损失函数更小，则剪枝。

直到不能剪枝

2.CART - 二元切分，可处理连续型变量

CART是classification and regression tree，分类与回归树，正如名字所说的，它其实有两种树，分类树和回归树。

2.0 首先介绍一下CART与普通决策树的区别

CART树与前面说的树有什么差别呢？

1.之前的生成树的算法在对某个特征切分的时候，将数据集按这个特征的所有取值分成很多部分，这样的切分速度太快，而CART只进行二元切分，对每个特征只切分成两个部分。

2.ID3和C4.5只能处理离散型变量，而CART因为是二元切分，可以处理连续型变量，而且只要将特征选择的算法改一下的话既可以生成回归树。

2.1 特征选择

回归树是平方误差最小化，分类树是基尼指数。

• 回归树：使用平方误差最小化作为特征选择算法

  其思想是将当前节点的数据按照某个特征在某个切分点分成两类，比如$R_1,R_2$，其对应的类别为$C_1,C_2$，我们的任务就是找到一个切分点使误差最小，那么怎么度量误差呢？这里使用的是平方误差，即 $min[min\sum_{x_i\in R_1}(y_i-c_1)^2+min\sum_{x_i\in R_2}(y_i-c_2)^2]$ 遍历某个特征可取的s个切分点（对离散型变量，要么等于要么不等于；对连续型变量，<或者>=），选择使上式最小的切分点。

  对每个确定的集合，c1,c2取平均值$\sum_{x_i\in R_1}(y_i-c_1)^2$和$\sum_{x_i\in R_2}(y_i-c_2)^2 $才会最小，这样的话就是求划分为两个集合后，分别对每个集合求方差*实例数，加起来的最小值。

  ​

• 分类树：使用基尼指数作为特征选择算法

  基尼指数

  概率分布的基尼指数为 $Gini(p)=\sum_{i=1}^np_i(1-p_i)=1-\sum_{i=1}^np_k^2$ 假设有K个类，$C_1,C_2,…,C_K$，给定的集合D的基尼指数为 $Gini(D)=1-\sum_{k=1}^K(\frac{\mid C_k\mid}{\mid D\mid})^2$ 对CART算法，D被特征A的某个值分成两类D1，D2，则在特征A的条件下，集合D的基尼指数为 $Gini(D,A)=\frac{\mid D_1\mid}{\mid D\mid}Gini(D_1)+\frac{\mid D_2\mid}{\mid D\mid}Gini(D_2)$ 基尼指数与熵类似，表示一个集合的不确定性，基尼数值越大，不确定性就越大。

  我们选取特征的时候就应该选取基尼指数最小的特征。

  ​

2.2 生成

根据上述的算法选择最佳的分裂特征和其分裂值，

用选定的切分点划分该节点为2个集合，$R_1和R_2$。

如果满足停止条件，则该节点的类别为划分后所有数据类别的平均值，即 $c_m=\frac{1}{N_m}\sum_{x_i\in R_m}y_i,m=1,2$ 否则，对不满足条件的集合，继续对两个子节点调用上述步骤。

2.3剪枝

我们这里用的是代价复杂度剪枝算法。

首先我们将一颗充分生长的树称为$T_0$ ，我们希望减少树的大小来防止过拟化，但又担心去掉一些节点后预测的误差会增大，那么如何达到这两个变量之间的平衡则是问题的关键，因此我们用一个变量$\alpha$ 来平衡，因此损失函数定义为如下： $C_{\alpha}(T)=C(T)+\alpha|T|$ T为任意子树，C(T)为预测误差，可以是平方误差也可以是基尼指数，|T|为子树T的叶子节点个数，注意是叶子节点，$\alpha$ 是参数，C(T)衡量训练数据的拟合程度，|T|衡量树的复杂度（即大小），$\alpha$ 权衡拟合程度与树的复杂度。

那么我们如何找到这个合适的$\alpha$来使拟合程度与复杂度之间达到最好的平衡呢，最好的办法就是，我们将$\alpha$从0取到正无穷，对于每一个固定的$\alpha$，我们都可以找到使得$C_{\alpha}(T)$最小的最优子树$T(\alpha)$ 。当$\alpha$ 很小的时候，$T_0$ 是这样的最优子树，当$\alpha$ 很大的时候，单独一个根节点是这样的最优的子树。

尽管$\alpha$ 取值无限多，但是$T_0$ 的子树是有限个，因此我们可以生成这样一个子树序列 $T_0>T_1>T_2>...>T_n$ $T_n$ 是最后剩下的那个根节点。（这里的子树生成是根据前一个子树$T_i$ ，剪掉某一个内部节点，生成$T_{i+1}$）然后对这样的子树序列分别用测试集进行交叉验证，找到最优的那个子树作为我们的决策树。

高能预警：(这里不注意的话，后面会有很大的疑惑)

Breiman证明：将$\alpha$ 从小增大，$0=\alpha_0<\alpha_0<…<\alpha_n<+\infty$ ，在每个区间$[\alpha_i,\alpha_{i+1})$ 中，子树$T_i$ 是这个区间里最优的。

这也是代价复杂度剪枝的核心思想。

基于上面的论述，剪枝可分为两部分，第一部分生成子树序列，第二部分交叉验证。

1. 生成子树序列

我们每次剪枝剪的都是某个内部节点的子节点，也就是将某个内部节点的所有子节点回退到这个内部节点里，并将这个内部节点作为叶子节点。因此在计算整体的损失函数时，这个内部节点以外的值都没变，只有这个内部节点的局部损失函数改变了，因此我们本需要计算全局的损失函数，但现在只需要计算内部节点剪枝前和剪枝后的损失函数。

对任意内部节点t，

剪枝前的状态：有$\mid T_t \mid$ 个叶子节点，预测误差是$C(T_t)$

剪枝后的状态：只有本身一个叶子节点，预测误差是$C(t)$

因此剪枝前的以t节点为根节点的子树的损失函数是 $C_{\alpha}(T_t)=C(T_t)+\alpha |T_t|$ 剪枝后的损失函数是 $C_{\alpha}(t)=C(t)+\alpha$ 易得，一定存在一个$\alpha$ 使得$C_{\alpha}(T_t)=C_{\alpha}(t)$ ，这个值为 $\alpha = \frac{C(t)-C_(T_t)}{|T_t|-1}$ 这个$\alpha$ 的值有什么意义，刚才我们高能预警的地方，$0=\alpha_0<\alpha_1<…<\alpha_n<+\infty$ ，在每个区间$[\alpha_i,\alpha_{i+1})$ 中，子树$T_i$ 是这个区间里最优的。为什么呢？原因就在刚才的推导，对于当前这个节点，只要$\alpha$ 大于这个值时，一定有$C_{\alpha}(t)<C_{\alpha}(T_t)$ ，也就是剪掉这个节点后都比不剪要更优。所以每个最优子树对应的是一个区间，在这个区间内都是最优的。

然后我们对$T_i$ 中的每个内部节点t都计算 $g(t)=\frac{C(t)-C_(T_t)}{|T_t|-1}$ (注意这里的t是变量，上面推$\alpha$ 时是针对一个特定的t，也就是t是常量。)

书上说g(t)表示剪枝后整体损失函数减少的程度，然后剪去g(t)最小的$T_t$.

当初这是非常困扰我的一个地方，1.为什么代表整体损失函数减少的程度。2.既然代表减少的程度，为什么剪去g(t)最小的$T_t$ ，而不是剪去g(t)最大的$T_t$ 。3.或者剪去$(C(t)+\alpha)$ 最小的$T_t$.

• 1.首先针对第一个问题

我承认我到现在也没弄懂，我觉得写的有问题或者有歧义？我觉得把它解释成误差减小率 更合适，我觉得它是衡量叶子节点增加的值不值的一个标准。首先分子是误差减小的量，如果我们单一的看误差见效的量有可能会有失偏颇，因为你可能是增加了很多很多的叶子节点才换来的这么一点误差的减小量，因此我们除以增加的叶子节点数，来代表每个叶子节点带来的误差减小量。

• 2.为什么剪去g(t)最小的$T_t$

如刚才说的g(t)代表每个叶子节点带来的误差减小量，如果g(t)越小，也就是增加叶子带来的误差减小量越小，也就是增加这个叶子节点的作用越小，花那么大的功夫增加叶子节点，误差才减小那么一点点，还不如不要，因此优先剪去g(t)最小的t

• 3.为什么不剪去$(C(t)+\alpha)$ 最小的$T_t$.

考虑过这个问题的说明有一定思考了。对当前的$T_i$ ，我们如果希望损失函数最小的话，应该是剪去损失函数最小的那个内部节点啊，这样的话损失函数才会最小嘛。

但是上面那句话真的对嘛？

整体损失函数 = 内部节点t的损失函数 + 其他节点的损失函数和

如果我们剪去的损失函数最小的那个内部节点，那么等号右边第一项是最小了，那第二项呢？所以提出的疑问也就不成立了。

进一步，为什么会让人产生这样的疑问呢？我觉得主要是没弄明白节点t是常量还是变量。

在计算$\alpha$ 时，节点t是常量，也就是只考虑这一个节点，当$\alpha>g(t)$ 时，剪掉会使整体损失函数减小，但跟整体损失函数是否是最小没有关系。考虑我们一开始说的因此在计算整体的损失函数时，这个内部节点以外的值都没变，只有这个内部节点的局部损失函数改变了，因此我们本需要计算全局的损失函数，但现在只需要计算内部节点剪枝前和剪枝后的损失函数。 这个只跟能否使整体损失函数减小有关，与整体损失函数能否达到最小无关。

2. 交叉验证

用交叉验证法在子树序列中选取最优子树。

• ← Previous Post
• Next Post →