机器学习笔记-决策树(二)

决策树

上一篇笔记决策树(一)里学习了决策树的ID3算法，和ID3算法的改进版C4.5算法。对于C4.5算法，我们也提到了它的不足，比如模型是用较为复杂的熵来度量，使用了相对较为复杂的多叉树，只能处理分类不能处理回归等。对于这些问题，CART算法大部分做了改进。下面我们就来学习CART算法的相关内容。

1. CART算法

分类与回归树(classification and regression tree, CART)是应用广泛的决策树学习方法。顾名思义，CART既可以由于分类也可以用于回归。

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

CART算法有以下两步组成：

1）决策树生成：基于训练集生成决策树，生成的决策树要尽量大；

2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART的生成就是递归地构建二叉决策树的过程。对于回归树用平方误差最小化准则，对于分类树用基尼指数(Gini index)最小化准则，进行特征选择，生成二叉树。

1.1 回归树

假设给定数据集$D=\{(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)\}$，其中$y$是连续型变量。考虑如何生成回归树。

一棵回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为$N$个单元$R_1, R_2,\dots,R_N$，并在每个单元$R_n$上有一个固定的输出值$c_n$，于是回归树模型可表示为

\[f(x) = \sum_{n=1}^Nc_nI(x\in R_n) \tag{1.1} \]

当输入空间的划分确定时，可以用平方误差

\[\sum_{x_i \in R_n}(y_i - f(x_i))^2 \tag{1.2} \]

来表示回归树对于训练数据的预测误差，用平方误差最小化准则求解每个单元上的最优输出值。易知，单元$R_n$上的$c_n$的最优值$\hat{c}_n$是$R_n$上的所有输入实例$x_i$对应的输出$y_i$的均值，即

\[\hat{c}_n = ave(y_i | x_i \in R_n) \tag{1.3} \]

与ID3和C4.5一样，关键问题是如何对输入空间进行划分。回归树的方法是：选择第$j$个特征$x^j$和它的取值$s$，分别作为切分变量和切分点，并定义两个区域：

\[R_1(j, s) = \{x|x^j \le s\} \qquad R_2(j, s) = \{x|x^j \gt s\} \tag{1.4} \]

然后根据式$(1.2)$准则寻找最优切分变量$j$和最优切分点$s$。具体可表示为：

\[\smash{\min_{j,s}}[\smash{\min_{c_1}}\sum_{x_i \in R_1(j,s)}(y_i- c_1)^2+\smash{\min_{c_2}}\sum_{x_i \in R_2(j,s)}(y_i- c_2)^2] \tag{1.5} \]

式$(1.5)$看上去有点绕，式中要求$\sum_{x_i \in R_1(j,s)}(y_i- c_1)^2$和$\sum_{x_i \in R_2(j,s)}(y_i- c_2)^2$的最小值，根据式$(1.3)$，当$c_1, c_2$取区间输出值的平均值时其平方误差达到最小。即

\[\hat{c}_1 = ave(y_i|x_i \in R_1(j,s)) \qquad \hat{c}_2 = ave(y_i|x_i \in R_2(j,s)) \tag{1.6} \]

于是，式$(1.5)$也可以写成

\[\smash{\min_{j,s}}[\sum_{x_i \in R_1(j,s)}(y_i- \hat{c}_1)^2+\sum_{x_i \in R_2(j,s)}(y_i- \hat{c}_2)^2] \tag{1.7} \]

至此，对固定输入变量$j$就可以找到最优切分点$s$。

为了找到最优的切分变量$j$，使平方误差最小，我们需要依次对每个特征的每个取值进行遍历，计算出当前每一个可能的切分点的误差，最后选择切分误差最小的点将输入空间切分为两个部分，然后递归上述步骤，直到满足停止条件切分结束。这样就生成了一棵回归树。这样的回归树通常称为最小二乘回归树(least squares regression tree)。

总结最小二乘回归树算法如下：

输入：训练数据集$D$

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

1）选择最优划分变量$j$和切分点$s$，求解式$(1.5)$；遍历变量$j$，对固定的变量$j$扫描切分点$s$，选择使式$(1.5)$达到最小值的$(j,s)$组合。
2）用选定的$(j,s)$划分区域并决定相应的输出值，输出值是区域$R_n$上的所有输入实例$x_i$对应的输出$y_i$的均值。
3）继续对两个子区域调用步骤(1)，(2)，直至满足停止条件。
4）将输入空间划分为$N$个单元$R_1, R_2,\dots,R_N$，生成决策树。

输出：回归树$f(x)$

1.2 分类树

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。我们已经在上一篇笔记中学习过基尼指数了，这里不再赘述。基尼指数定义为：

\[\begin{aligned} Gini(D) &= 1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 \end{aligned} \tag{1.8}\]

在特征$a$的条件下，数据集$D$的基尼指数定义为

\[Gini\_index(D,a) = \sum_{v=1}^{V}\cfrac{|D^v|}{|D|}Gini(D^v) \tag{1.9} \]

分类树生成算法，如下：

输入：训练数据集$D$，停止计算的条件；

根据训练数据集，从根结点开始，递归地对每一个结点进行以下操作，构建二叉决策树：

1）设结点的训练数据集为$D$，计算现有特征对该数据集的基尼指数。此时，对每一个特征$a$，对其可能的取的每一个值$a^v$，根据样本点对$a = a^v$的测试为“是”或“否”将$D$分割成$D_1$和$D_2$两部分，利用式$(1.9)$计算$a = a^v$时的基尼指数。

2）在所有可能的特征$a$以及它们所有可能的切分点$a^v$中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征和最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

3）对两个子结点递归调用(1)，(2)，直至满足停止条件，生成决策树。

输出：CART决策树

算法什么时候停止：

结点中样本个数小于预定阈值
样本集的基尼指数小于预定阈值，样本基本属于同一类别
没有更多特征用于划分

举一个例子，根据表1中所给的训练数据集，应用CART算法生成决策树。表1与上一篇决策树(一)笔记中的数据相同，因此这里我们使用相同的记号。分别以$a_1$，$a_2$，$a_3$，$a_4$表示年龄、有工作、有自己的房子、和信贷情况4个特征。

表1 贷款申请样本数据表

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	1	2	2	3	否
2	1	2	2	2	否
3	1	1	2	2	是
4	1	1	1	3	是
5	1	2	2	3	否
6	2	2	2	3	否
7	2	2	2	2	否
8	2	1	1	2	是
9	2	2	1	1	是
10	2	2	1	1	是
11	3	2	1	1	是
12	3	2	1	2	是
13	3	1	2	2	是
14	3	1	2	1	是
15	3	2	2	3	否

首先，计算特征$a_1$的基尼指数：

\[\begin{aligned} Gini\_index(D,a_1 = 1) &= \cfrac{5}{15}(1-[(\cfrac{2}{5})^2+(\cfrac{3}{5})^2)]) + \cfrac{10}{15}(1-[(\cfrac{7}{10})^2+(\cfrac{3}{10})^2)]) \\ &=0.44 \end{aligned}\]

\[Gini\_index(D,a_1 = 2) = 0.48 \]

\[Gini\_index(D,a_1 = 3) = 0.44 \]

由于$a_1 =1$和$a_1=3$的基尼指数相等，所以都可以作为最优切分点。

计算特征$a_2$和$a_3$的基尼指数：

\[Gini\_index(D,a_2 = 1) = 0.32 \]

\[Gini\_index(D,a_3 = 1) = 0.27 \]

计算特征$a_4$的基尼指数：

\[Gini\_index(D,a_4 = 1) = 0.36 \]

\[Gini\_index(D,a_4 = 2) = 0.47 \]

\[Gini\_index(D,a_4 = 3) = 0.32 \]

在$a_1$，$a_2$，$a_3$，$a_4$几个特征中，$Gini\_index(D,a_3 = 1) = 0.27$最小，所以选择$a_3$作为最优特征，$a_3=1$最为最优切分点。于是根结点生成两个子结点，一个是叶结点。对另一个结点继续使用以上方法，在$a_1$，$a_2$，$a_4$特征中选择最优特征和最优切分点，结果是$a_2=1$。依次计算得知，所得结点都是叶结点，决策树生成结束。

2. 决策树剪枝处理

剪枝(pruning)是决策树学习算法对付"过拟合"的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，构建出过于复杂的决策树，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，要考虑决策树的复杂度，通过主动去掉一些分支降低过拟合的风险。

决策树剪枝的基本策略有"预剪枝" (prepruning) 和"后剪枝 "(post-pruning) 。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

如何判断决策树泛化性能是否提升呢？可以采用留出法等模型性能评估方法，即预留一部分数据用作"验证集"以进行性能评估。下面我们先学习一种简单的决策树剪枝算法，最后在看看CART算法时怎么实现剪枝的。

2.1 剪枝算法

决策树的剪枝往往通过极小化决策树整体的损失函数来实现。

假设决策树$T$的叶结点个数为$|T|$，$t$表示树$T$的叶结点，该叶结点有$N_t$个样本点，其中类别标记为$k$的样本点有$N_{tk}$个，$k=1,2,\cdots,K$，$H_t(T)$为叶结点$t$上的经验熵，$\alpha \ge 0$为参数，则决策树学习的损失函数可定义为：

\[C_\alpha(T) = \sum_{t=1}^{|T|}N_tH_t(T) + \alpha |T| \tag{2.1} \]

其中经验熵为

\[H_t(T) = -\sum_{k} \cfrac{N_{tk}}{N_t}log_2\cfrac{N_{tk}}{N_t} \tag{2.2} \]

在损失函数中，令

\[C(T) = \sum_{t=1}^{|T|}N_tH_t(T) = -\sum_{t=1}^{|T|}\sum_{k=1}^K N_{tk}log_2\cfrac{N_{tk}}{N_t} \tag{2.3} \]

于是得到

\[C_\alpha(T) = C(T) + \alpha |T| \tag{2.4} \]

式$(2.4)$中，$C(T)$表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$|T|$表示模型复杂度，参数$\alpha \ge 0$控制两者之间的影响。较大的$\alpha$促使选择较简单的模型，较小的$\alpha$促使选择较复杂的模型，$\alpha = 0$意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当$\alpha$确定时，选择损失函数最小的模型，即损失函数最小的子树。当$\alpha$确定时，子树越大，往往与训练数据的拟合越好，但模型复杂度高；反之，子树越小，模型复杂度越低，往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

树的剪枝算法

输入：生成算法产生的整个树$T$，参数$\alpha$;

1）计算每个结点的经验熵。
2）递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树的损失函数值分别是$C_\alpha(T_B)$和$C_\alpha(T_A)$，如果$C_\alpha(T_B) \ge C_\alpha(T_A)$，则进行剪枝，即将父结点变为新的叶结点。
3）返回$(2)$，直至不能继续为止，得到损失函数最小的子树$T_\alpha$

输出：修剪后的子树$T_\alpha$。

在《机器学习 - 周志华》第4.3节有很直观的决策树剪枝的例子

2.2 CART剪枝

CART回归树和CART分类树的剪枝策略除了在度量损失的时候一个使用平方误差，一个使用基尼系数，算法基本完全一样。CART采用的办法是后剪枝法，即先生成决策树，进而产生所有可能的剪枝后的CART树，最后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

也就是说，CART剪枝算法可以概括为两步：

从原始决策树生成各种剪枝效果的决策树，形成一个子树序列；
用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的树作为最终的CART树。

1）剪枝，形成一个子树序列

在剪枝过程中，根据式$(2.4)$，我们可以计算任意时刻子树$T$的损失函数值。其中，$C(T)$为对训练数据的预测误差，分类树是用基尼系数度量，回归树是平方误差度量。$|T|$为子树的叶结点个数，$C_\alpha(T)$为参数是$\alpha$时子树$T$的整体损失。参数$\alpha$权衡训练数据的拟合程度与模型的复杂度。

当$\alpha=0$时，原始生成的CART树即为最优子树。当$\alpha= \infty$时，即正则化强度达到最大，此时由原始生成的CART树的根节点组成的单节点树为最优子树。当然，这是两种极端情况。一般来说，$\alpha$越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的$\alpha$，一定存在使损失函数$C_\alpha(T)$最小的唯一子树。

看过剪枝的损失函数度量后，我们再来看看剪枝的思路，具体的，从整体树$T_0$开始剪枝。对于其任意内部结点$t$，以$t$为单结点树的损失函数是

\[C_\alpha(t) = C(t) + \alpha \tag{2.5} \]

其中，因$t$为单结点树，所以$|T| = 1$。以$t$为根结点的子树$T_t$的损失函数是

\[C_\alpha(T_t) = C(T_t) + \alpha|T_t| \tag{2.6} \]

因为$T_t$是以$t$为根结点按照划分准则划分产生的，所以损失函数必然是减小的，所以当$\alpha = 0$及$\alpha$充分小时，有不等式

\[C_\alpha(T_t) \lt C_\alpha(t) \tag{2.7} \]

当$\alpha$增大时，在某一$\alpha$有

\[C_\alpha(T_t) = C_\alpha(t) \tag{2.8} \]

即树分支前和之后损失函数值相等。

当$\alpha$继续增大时，不等式$(2.7)$反向。也就是说，如果想要$T_t$与$t$的损失函数值相同，即式$(2.8)$成立，只要

\[\alpha = \cfrac{C(t)-C(T_t)}{|T_t| -1} \tag{2.9} \]

而此时，因为$t$的结点更少，根据奥卡姆剃刀准则，$t$比$T_t$更可取，因此可以对子树$T_t$进行剪枝，也就是将它的子结点全部剪掉，变为一个叶结点。

接下来我们用同样的方法对整体树$T_0$中每一个内部结点$t$计算得到相应的$\alpha_n$和剪枝后子树$T_n$，如此一只剪下去，直至根结点。

2）在剪枝得到的子树序列中通过交叉验证选取最优子树$T_\alpha$

具体地，利用独立的验证数据集，比如开始我们说的留出法预留的部分数据，测试第一步产生的子树序列中的各棵子树的平方误差或基尼指数。其值最小的决策树被认为是最优的决策树。第一步中我们知道每棵子树$T_n$都对应一个参数$\alpha_n$，所以当最优子树确定后，对应的参数$\alpha$也确定了，有了这个$\alpha$，我们就可以用对应的最优子树作为最终结果，即$T_\alpha$。

CART剪枝算法

输入：CART生成算法产生的整个树$T_0$$;

1）设$k=0, T=T_0$;
2）设$\alpha=+\infty$;
3）自下而上地对各内部结点$t$计算$C_(T_t)$，$|T_t|$以及$g(t) = \cfrac{C(t)-C(T_t)}{|T_t| -1}$，$\alpha = min(\alpha, g(t))$;
4）对$g(t) = \alpha$的内部结点$t$进行剪枝，并对叶结点$t$以多数表决法决定其类别，得到树$T$;
5）设$k= k+1, \alpha_k = \alpha, T_k=T$;
6）如果$T_k$不是由根结点及两个叶结点构成的树，则回到步骤2）；否则令$T_k = T_n$;
7）采用交叉验证法在子树序列$T_0$到$T_n$中选取最优子树$T_\alpha$。

输出：最优决策树$T_\alpha$。

3. 决策树算法小结

3.1 ID3，C4.5和CART的比较总结

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益率	支持	支持	支持
CART	分类，回归	二叉树	基尼系数，平方误差	支持	支持	支持

看起来CART算法高大上，那么CART算法还有没有什么缺点呢？

应该大家有注意到，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1[Murthy et al., 1994]，有机会再进行学习。
如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

3.2 决策树算法的优缺点

终于到了最后的总结阶段了，这里我们不再纠结于ID3, C4.5和 CART，我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。这部分总结于scikit-learn的英文文档。

首先我们看看决策树算法的优点：

1）简单直观，生成的决策树很直观。

2）基本不需要预处理，不需要提前归一化，处理缺失值。

3）使用决策树预测的代价是$O(log_2m)$。$m$为样本数。

4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

5）可以处理多维度输出的分类问题。

6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释

7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

8）对于异常点的容错能力好，健壮性高。

我们再看看决策树算法的缺点:

1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考来源：

1）统计学习方法 - 李航
2）机器学习-周志华
3）https://www.cnblogs.com/pinard/p/6053344.html 决策树算法原理(下)