决策树是一种简单但是应用广泛的分类器。最开始了解到决策树的时候认为它太简单了，就像代码里的 if 语句一样。事实上，决策树虽然简单，但是也是一种非常有效的分类方式。将决策树通过袋装的方式组合为随机深林更是在很多数据环境中拥有比 svm 等经典分类器更优异的性能。周志华老师还提出孤立森利和深度深林等基本单元为决策树等算法。本文主要对决策树的基本概念，决策树的生成剪枝算法进行简述。
决策树的基本概念
决策树一种分类算法，也可以用来进行回归。决策树应用树结构对输入结果进行判定，每一个内部节点代表对某一个属性进行测试，而每一条边作为一个测试结果，每一个叶子节点代表一中分类。通过不断的比较将数据分配到某一个叶子节点代表的类中。生成一个决策树有以下步骤:
- 特征选择: 选择一个特征作为当前节点的判断标准
- 生成子树: 利用选择的特征递归的分裂，直到数据不可分或达到停止条件
- 剪枝: 减掉一些子树避免过拟合
以下将详细的介绍这三个步骤。
特征选择
划分方式
特征选择的具体意义是选择一个特征，利用该特征将数据划分为 N 个子集。划分有二元划分和多路划分两种方式：
离散特征的划分:
注意对于有顺序的离散属性，划分时不能打乱其顺序。例如对于产品质量有:不合格 合格 优良三种类型。作为二元划分可以为: {不合格} $\cup$｛合格、优良｝但是不能为是{合格} $\cup$ {不合格，优良}
连续特征的换分:
特征选择准则
选择准则决定了在某个节点选择哪一个特征进行划分。一般有信息增益和信息增益比两种方式:
信息增益
数据的纯度可以用来表示数据含有的信息量大小，纯度越高，信息量越大。如果根据某特征划分后，子集的纯度减小，则说明通过该特征获得了未划分之前的信息。如果子集与原始数据的纯度差别越大，则划分的特征就是一个越优的特征。具体请参照数据挖掘基础－熵。判断子节点不纯度的度量有熵和基尼系数。设特征值对样本数据进行了 N 个划分，其中每个划分为$D_1 D_2 … D_N$。对每一个划分$D_m$中熵和基尼系数定义如下:
$$
Entropy(D_m) = -\sum_{i=1}^{K}p(C_i)log(p(Ci))
$$
$$
Gini(D_m)=\sum_{i=1}^{K}p(C_i)(1-p(C_i))
$$
其中 $p(C_i)$ 表示类 $C_i$ 属于划分 $D_m$ 的概率。即是:
$$
p(C_i) = \frac{|p(C_i)|}{|D_m|}
$$
$|.|$表示集合中元素的个数。
对于下面个人情况和是否同意贷款的数据如下:
| ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | N | N | 一般 | N |
| 2 | 青年 | N | N | 好 | N |
| 3 | 青年 | Y | N | 好 | Y |
| 4 | 青年 | Y | Y | 一般 | Y |
| 5 | 青年 | N | N | 一般 | N |
| 6 | 中年 | N | N | 一般 | N |
| 7 | 中年 | N | N | 好 | N |
| 8 | 中年 | Y | Y | 好 | Y |
| 9 | 中年 | N | Y | 非常好 | Y |
| 10 | 中年 | N | Y | 非常好 | Y |
| 11 | 老年 | N | Y | 非常好 | Y |
| 12 | 老年 | N | Y | 好 | Y |
| 13 | 老年 | Y | N | 好 | Y |
| 14 | 老年 | Y | N | 非常好 | Y |
| 15 | 老年 | N | N | 一般 | N |
利用熵作为不纯度的度量，计算每一个特征划分后子节点的不纯度。特征年龄将数据进行三个划分，分别为:
$D_1={N N Y Y N } ,D2={N N Y Y N },D3={Y Y Y Y N} $
对于每一个划分的熵为:
$E(D_1)=-\frac 2 5log_2(\frac 2 5)-\frac 3 5 log_2(\frac 3 5)$
$E(D_2)=-\frac 2 5log_2(\frac 2 5)-\frac 3 5 log_2(\frac 3 5)$
$E(D_3)=-\frac 1 5log_2(\frac 1 5)-\frac 4 5 log_2(\frac 4 5)$
利用每一个划分集合大小占总数据集合大小比例作为权值，最终的熵为:
$E(D)=\frac 1 3E(D_1)+\frac 1 3 E(D_2)+\frac 1 3 E(D_3)$
利用同样的方法，计算有工作、有自己的房子、信贷情况等特征的熵为:
0.674 0.551 0.608
未划分前数据熵相同，所以在当前节点应该选择特征有自己的房子作为划分的特征。
信息增益比
信息增益趋向于选择取值较多的特征。信息增益比则是使用信息增益/划分后的熵
生成子树
在选择了合适的特征进行换分之后，对通过划分得到的每一个集合继续递归的进行寻找特征，进行划分步骤，直到子节点的数据无法划分。
例如，对于表中的数据，在根节点利用有自己的房子作为划分后，得到两个子集合编号为:
$D_1={4 ,8 ,9, 10, 11, 12} \ D_2={1,2,3,5,6,7,13,14,15}$
对应的类别为:
$D_1={Y,Y,Y,Y,Y,Y} \ D_2={N,N,Y,N,N,N,Y,Y,N} $
可以看出 $D_1$中的数据所有类别相同，无需再划分。对于 $D_2$ 中的数据，剩下年龄、有工作、信贷情况这几个特征，计算所有特征对应划分的不纯度，得到不纯度最高的特征为有工作。使用有工作对 $D_2$ 进行划分，得到:
$D_3={1,2,5,6,7,15} \ D_4={3,13,14}$
对应的类别为:
$D_3={N,N,N,N,N,N} \ D_4={Y,Y,Y}$
可以看出$D_3$和$D_4$中都有含有一种类别的数据，无需继续划分。因此最终学得的决策树为:
一般来说，生成子树的停止条件有很多种。例如:
- 叶子节点中的数据都能被分为同一类
- 叶子节点中的不纯度小于一定的阈值
- 叶子节点包含样本的数据量小于一定的数量
剪枝
用上面方法学的决策树可以完全拟合训练数据，容易出现过拟合。将已经学得的决策树进行简化以避免过拟合的过程称之为剪枝。这里介绍一种简单的剪枝算法。
对于决策树，可以通过极小化决策树整体的损失函数来进行实现。设树$T$的叶节点个数为$|T|$，$N$是其中的一个叶节点。该节点含有的样本数量为$|N|$，其中$k$类的样本数有$|N_k|$个。$E(N)$为节点$N$上的熵，$\alpha \ge 0 $表示模型复杂度对损失函数的影响。决策树模型的最终的损失函数可以表示为:
$$
C_a(T)=\sum_{i=1}^{|T|}|N|E(N)+\alpha|T|
$$
即表示为每一个叶节点的熵 x 该节点的个数 + 模型的复杂度。模型的复杂度用叶节点的个数表示。很明显，叶节点的个数越多，模型越复杂。而熵表示叶节点的纯度。熵越小，叶节点越不纯，拟合度就越高。因此损失函数有两部分组成，一部份表示模型对训练数据的拟合程度，一部分表示模型的复杂度。可以写为:
$$
C_a(T)=C(T)+\alpha|T|
$$
模型越复杂，对训练数据拟合就越好，$C(T)$ 就越小，同时$\alpha|T|$就越大。反正模型越简单，$\alpha|T|$就越小，但是对模型的拟合度就低，$C(T)$也就越大。因此要想使得$C_a(T)$越小，就要在模型拟合程度和模型复杂度上取得一个权值。
剪枝的一个示意图如下:
对整个决策树进行剪枝的步骤为:
- 计算$Ca(T)$
- 选择一个叶子节点，设减掉该节点得到的子树为$Ta$。若$Ca(T)>Ca(T_a)$，则需要减掉该叶子节点。
- 重复步骤1,2直到无法减掉任何一个叶子节点。
CART 回归与分类与分类树
回归与分类树(classification and regression tree,CART)是一种应用广泛的的决策树模型。算法包括了决策树特征的选择，生成，剪枝操作。既可以用于回归，也可以用于分类。CART 决策树模型为二叉树，递归的二分每个特征。
回归树
回归树通过最小化平方误差来进行特征的选择以及划分点的选择。
对于训练样本$(X,Y)$。$X=[x_1,x_2,…,x_n]$，其对应的输出$Y=[y_1,y_2,…,y_n]$。划分的原则是找到$x_i$第个j个特征$x^{(j)}$及其取值s。使得数据称为两个划分:
$$
D_1=x_i|x_i^{(j)}\le s \ \ \ \ \ D_2 =x_i|x_i^{(j)}>s
$$
划分的准则是使得根据该特征划分后的平方误差最小，即:
$$
\sum_{i=1}^{N1}(y_{1i}-\hat{y_1})^2 + \sum_{i=1}^{N2} (y_{2i}-\hat{y_2})
$$
其中 $N_j$表示第 j 个划分样本的个数。$y_{ji}$表示第 j 个划分中的第 i 个样本对应的输出。$\hat{y_j}$表示第 j 个划分的期望输出，$j=1,2$。期望输出定义为:
$$
\hat{y_j} =\frac 1 N_j \sum_{i=1}^{N_j} y_{ji}
$$
如我们想用回归树拟合函数$y=3a^2+2b^2$。样本为:
| id | a | b | c |
|---|---|---|---|
| 1 | 0 | 1.5 | 4.5 |
| 2 | 0.1 | 1.4 | 3.94 |
| 3 | 0.2 | 1.3 | 3.5 |
| 4 | 0.3 | 1.2 | 3.15 |
| 5 | 0.4 | 1.1 | 2.9 |
| 6 | 0.5 | 1.0 | 2.75 |
| 7 | 0.6 | 0.9 | 2.7 |
| 8 | 0.7 | 0.8 | 2.75 |
| 9 | 0.8 | 0.7 | 2.9 |
| 10 | 0.9 | 0.6 | 3.15 |
由于这里的变量都是单调递增或者递减的，因此两个变量产生的划分点完全相同。不妨选择变量$a$，不同的划分点对应的平方误差:
| 划分点(a) | 误差 |
|---|---|
| 0 | 0.15 |
| 0.1 | 0.14 |
| 0.2 | 0.19 |
| 0.3 | 0.27 |
| 0.4 | 0.35 |
| 0.5 | 0.40 |
| 0.6 | 0.41 |
| 0.7 | 0.39 |
| 0.8 | 0.35 |
| 0.9 | 0.31 |
因此应该选择$a=0.1$作为划分点。划分后两个划分的 id 为:
$D_1 = 1,2 \ D2 = 3,4,5,6,7,8,9$
不断的按照此种方法进行划分，直到满足停止条件。最后叶节点的输出就为该节点的期望输出。
分类树
分类树采用基尼系数作为特征选择的指标。具体的生成方式与普通的决策树类似。这里不再重复。
剪枝
CART 树的剪枝方式是从生成的完整的树的底端依次的减去一些子树，得到简化后的子树序列 $T_1,T_2,T_3,..,T_N$。然后用交叉验证的方式检验其中的每一个子树，得到一个子树序列。
对于某一个节点 $N$ ，进行剪枝后该节点变为变为叶子节点$N_t$。则以节点$Ｎ$为根节点的子树的损失函数:
$$
C_a(T) = C(T) + \alpha(|T|)
$$
剪枝之后得到的以$N$为单节点的子树$T_t$的损失函数为:
$$
C_a(T_t)=C(T_t)+\alpha
$$
当$\alpha＝０$或足够小时，$C_a(Tt) > C_a(t)$。当$\alpha$慢慢增大到某一个值时，此时有$C_a(Tt) = C_a(t)$。也就是说，只要:
$$
\alpha = \frac{C_a(T)-C_a(T_t)}{1-|T|}
$$
$T$ 和 $T_t$ 有相同的损失函数，而此时 $T_t$ 比 $T$ 更小的节点树。因此应该对$T$进行剪枝。
因此 CART 树的剪枝方式为，对于完整树$T_0$的每一个内部节点，计算:
$$
\alpha ＝ \frac{C_a(T)-C_a(T_t)}{1-|T|}
$$
得到其中最小的节点，对该节点进行剪枝操作。对得到的子树重复这种剪枝操作，直到只剩下根节点。随后利用交叉验证的方式对子树序列进行测试，找到误差最小的子树。这种剪枝方式的优点在于不断的增大$\alpha$的值，即不断简化树的结构，得到最优的拟合误差与结构复杂度的均衡。