决策树模型

这一部分介绍下决策树算法，决策树是一种基本的分类与回归表示方法，决策树模型呈树形结构，在分类问题中，可以表示为基于特征对实例进行分类的过程。决策树可以认为是”if-then”规则的集合，也可以认为是定义在特征空间与类空间上的概率分分布。本文按照以下四部分进行组织:

• 决策树模型与学习
• 特征选择
• 决策树生成算法
• 决策树剪枝算法

决策树模型与学习

决策树模型定义

首先给出决策树的定义:

决策树： 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点和有向边组成，节点由两种类型：内部节点和叶节点。内部节点表示一个特征或属性，叶节点表示一个类。

一个决策树模型如下图所示：

决策树的逻辑其实与人思考的逻辑非常贴合,都是通过一连串的”if-then”语句来进行判断，这也是决策树算法具有较好可解释性的原因。

决策树与”if-then”规则

一个决策树可以转换成一组”if-then”规则,将决策树转换成”if-then”规则集合的步骤如下:由决策树的根节点到叶节点的每一条路径构建一条规则：路径上内部节点的特征对应着规则的条件，而叶节点的类则对应着规则的结论。
决策树对应的”if-then”规则集合具有一个重要的性质：互斥并且完备，即每一个实例都被一条路径或一条规则所覆盖，而且只被一条规则或一条规则所覆盖。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。
假设$X$为表示特征的随机变量，$Y$为表示类别的随机变量，那么这个条件概率分布可以表示为$P(Y|X)$,$X$取值于给定划分下单元的集合，$Y$取值于类的集合。

决策树学习

假设给定训练数据集:

$$D = \{ (x_1,y_1),(x_2,y_2), \dots, (x_N,y_N)\}$$

其中$x_i \in R^n$为特征向量,$n$为特征个数，$y_i \in {1,2, \dots, K}$为类标记，$N$为样本容量。
决策树学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

决策树学习本质上是从训练数据集中归纳出一组分类规则，这点与前面章节介绍过的规则学习非常类似，不过决策树所针对的问题更加具体。与训练数据集不相矛盾的决策树可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从条件概率分布的角度来看，决策树学习是由训练数据集估计条件概率模型，基于特征空间划分的类的条件概率模型有无穷多个，我们选择的条件概率模型应该不仅对训练数据有很好的拟合，同时也应当对未知的数据有较好的预测。
从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优问题，这样得到的决策树是次最优的。
决策树学习算法通常是一个递归地选取最优特征，并根据该特征对训练数据进行分割，使得各数据集有一个最好的分类的过程。这一过程对应着特征空间的划分，也对应着决策树的构建。构建流程如下:

• 构建根节点，将所有训练数据都放在跟节点
• 选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
• 判断子集中的实例是否都被正确分类，若都已经被正确分类，则构建叶节点
• 若子集不能被正确分类，则返回第二步，选取最优特征并划分子集。

通过上述流程所构建的决策树往往对训练数据有着良好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象，因此往往需要的生成的决策树自下而上进行剪枝。

特征选择

特征选择的目的在于选取具有分类能力的特征，决策树的每一次分叉都是进行特征选择的过程, 所以有一个亟需回答的问题就是：

应当以什么样的标准来评判一个特征的分类能力？

通常评价特征分类能力的指标是信息增益和信息增益比，在前面章节中我已经给出了熵和条件熵的定义：

熵： 在信息论与概率统计中，熵是表示随机变量不确定性的度量，设$X$是一个取有限个值的离散随机变量，其概率分布为:

$$P(X = x_i) = p_i, \quad i =1,2,\dots,n$$

则随机变量$X$的熵定义为:

$$H(X) = - \sum_{i=1}^n p_i \log p_i$$

条件熵： 设有随机变量$(X,Y)$,其联合概率分布为：

$$P(X = x_i,Y = y_i) = p_{ij}\quad i = 1,2,\dots,n;\quad j = 1,2,\dots,m$$

条件熵$H(Y|X)$表示在已知随机变量$X$条件下随机变量$Y$的不确定性。随机变量$X$给定的条件下随机变量$Y$的条件熵$H(Y|X)$,定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望：

$$H(Y|X) = \sum_{i=1}^n p_i H(Y|X = x_i)$$

当熵和条件熵中的概率由数据估计得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵

信息增益

下面给出信息增益的定义：

信息增益： 特征$A$对训练集$D$的信息增益$g(D,A)$,定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差，即：

$$g(D,A) = H(D) - H(D|A)$$

给定数据集$D$和特征$A$,经验熵$H(D)$表示对数据集$D$进行分类的不确定性，而经验条件熵$H(D|A)$则表示在特征$A$给定条件下对数据集$D$进行分类的不确定性。而它们之间的差则表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。由此便可得通过信息增益来选择特征的算法如下:

信息增益算法
输入： 训练数据集$D$及特征$A$
输出： 特征$A$对训练数据集$D$的信息增益$g(D,A)$

• Step1: 计算数据集$D$的经验熵： $$H(D) = -\sum_{k=1}^K \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$$
• Step2: 计算特征$A$对数据集$D$的经验条件熵$H(D|A)$ $$H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K \frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$$
• Step3: 计算信息增益 $$g(D,A) = H(D) - H(D|A)$$

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比则可以对这一问题进行校正，下面给出信息增益比的定义:

信息增益比： 特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即：

$$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$$

其中$HA(D) = -\sum{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$,$n$是特征$A$取值的个数

基尼指数(基尼不纯度)

首先给出基尼指数的定义:

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

$$Gini(p) = \sum_{k=1}^K p_k(1 - p_k) = 1 - \sum_{k=1}^K p_k^2$$

对于二分类问题，若样本点属于第一个类的概率是$p$,则概率分布的基尼指数为:

$$Gini(p) = 2p(1-p)$$

对于给定的样本集合$D$，其基尼指数为:

$$Gini(D) = 1 - \sum_{k=1}^K (\frac{|D_k|}{|D|})^2$$

在特征$a_i$下将特征空间划分成$n$块，各块的样本数为$D_i$,条件Gini指数可以写做:

$$Gini(D|a_i) = \sum_{i=1}^n \frac{|D_i|}{|D|} Gini(D_i)$$

引入特征$a_i$后，集合$D$不确定性降低了:

$$Gini(D) - Gini(D|a_i)$$

决策树的生成

决策树生成流程在前面已经介绍过，不同算法的区别主要在于特征选择标准上的差别，该部分主要介绍两种决策树生成算法：

• ID3算法
• C4.5算法

ID3算法

ID3算法相当于用极大似然法进行概率模型的选择,下面给出ID3算法的流程:

ID3算法
输入： 训练数据集$D$, 特征集$A$阈值$\epsilon$
输出： 决策树$T$

• 若$D$中所有实例属于同一类$C_k$,则$T$为单节点树，并将$C_k$作为该节点的类标记，返回$T$
• 若$A = \varnothing$,则$T$为单节点树，并将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$
• 否则，计算$A$中各特征对$D$的信息增益，选择信息最大的特征$A_g$
• 如果$A_g$的信息增益小于阈值$\epsilon$，则置$T$为单节点树，并将$D$中最大实例数类$C_k$作为类别，返回$T-
• 否则，按照$A_g$的每一特征值将特征空间划分成若干子集，将$D_i$中实例最大的类作为标记，构建子节点，由节点及其子节点构成树$T$，返回$T$
• 对第$i$个子节点，以$D_i$为训练集，以$A - {A_g}$为特征集，递归地调用前述步骤，得到子树$T_i$,返回子树

C4.5算法

C4.5算法选用信息增益比作为特征选择标准，其流程如下：

C4.5算法
输入： 训练数据集$D$, 特征集$A$阈值$\epsilon$
输出： 决策树$T$

• 若$D$中所有实例属于同一类$C_k$,则$T$为单节点树，并将$C_k$作为该节点的类标记，返回$T$
• 若$A = \varnothing$,则$T$为单节点树，并将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$
• 否则，计算$A$中各特征对$D$的信息增益比，选择信息最大的特征$A_g$
• 如果$A_g$的信息增益小于阈值$\epsilon$，则置$T$为单节点树，并将$D$中最大实例数类$C_k$作为类别，返回$T-
• 否则，按照$A_g$的每一特征值将特征空间划分成若干子集，将$D_i$中实例最大的类作为标记，构建子节点，由节点及其子节点构成树$T$，返回$T$
• 对第$i$个子节点，以$D_i$为训练集，以$A - {A_g}$为特征集，递归地调用前述步骤，得到子树$T_i$,返回子树

决策树的剪枝

决策树算法非常容易产生过拟合问题，过拟合的原因在于决策树在学习时过多地考虑了如何提高对训练数据分类准确率，从而构建除了过于复杂的决策树，而剪枝就是为了减轻决策树过拟合的一种操作。剪枝操作按照进行的时间段可以分为前剪枝与后剪枝两种：

• 预剪枝：预剪枝操作是在决策树的构建过程中, 即通过对信息增益/信息增益比/Gini指数设定阈值，当分裂前后相应标准小于该阈值时，决策树便不进行分裂操作，又或者是先验地限制决策树的深度或者节点个数。预剪枝得到的决策树尽管更加简单，泛化能力得到了提升，但这样的剪枝操作是盲目的、缺乏指导的，实际应用中很容易导致决策树训练不充分的问题。
• 后剪枝：后剪枝顾名思义，是在一棵完整的决策树构建完成之后进行剪枝，常用的后剪枝操作有两种:
  • 基于带正则项的损失函数进行剪枝
  • 基于验证集错误率进行后剪枝

预剪枝的思想非常简单，这里便不做过多介绍，下面以带正则化的损失函数为例介绍下后剪枝的流程

基于正则项的损失函数

首先考虑下对于一棵决策树，其似然函数应当怎么写，假设一棵决策树有$|T|$个叶节点，$t$是树$T$的叶节点，该叶节点上有$Nt$个样本点，其中$k$类的样本点有$N{tk}$个，$k=1,2,\dots,K$。可以这么考虑，这$|T|$个叶节点将整个特征空间分成了$|T|$部分，其中$t$节点上一个属于$K$类的样本出现的概率(最大似然估计得到)为$\frac{N{tk}}{N_t}$,而又假设样本之间是彼此独立的，该节点上有$N{tk}$个该类样本，据此可以写出节点$t$上样本出现的概率:

$$\prod_{k=1}^K (\frac{N_{tk}}{N_t})^{N_{tk}}$$

而一共有$|T|$个叶节点，故整个树上的样本出现的概率(似然函数)为：

$$\prod_{t=1}^{|T|} \prod_{k=1}^K (\frac{N_{tk}}{N_t})^{N_{tk}}$$

至此便可以写出对数似然函数:

$$L(T) = \sum_{t=1}^{|T|} \sum_{k=1}^K N_{tk} \log \frac{N_{tk}}{N_t}$$

我们想要似然函数最大，其实也就是负的对数似然函数最小，由此可得损失函数$C(T)$:

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

而我们不仅仅希望决策树$T$在训练集上表现良好，同时希望决策树具有良好的泛化性能，因此需要在上面损失函数的基础上添加正则项，正则项需要与决策树的复杂程度有关，这里选用叶节点个数$|T|$作为损失函数,由此可得正则化的损失函数如下:

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

其中$\alpha$是权重因子，用来平衡模型复杂度与训练数据拟合效果。将叶节点上的经验熵代入损失函数，可以得到损失函数的另一种表达形式:

$$C_\alpha(T) = -\sum_{i=1}^{|T|} N_t H_t(T) + \alpha_t$$

其中$H_t(T)$为叶节点上的经验熵，至此我们便可以写出该后剪枝算法流程:

基于正则损失函数的后剪枝算法
输入： 生成算法产生的整个树$T$,$\alpha$
输出： 修建后的子树$T_\alpha$

• 计算当前树各个叶节点上的经验熵
• 递归地从树的叶节点向上回缩，设一组叶节点回缩到其父节点之前与之后的整体树分别为$TB$与$T_A$,其对应的损失函数分别是$C\alpha(TB)$ 与 $C\alpha(T_A)$,若： $$C_\alpha(T_A) \leq C_\alpha(T_B)$$ 则进行剪枝，将父节点变为新的叶节点
• 返回第2步，直到不能继续为止，得到损失函数最小的子树$T_\alpha$

基于验证集分类错误率进行后剪枝

在基于正则损失函数的后剪枝中，所有的数据集都被拿来训练，而在基于验证集分类错误率方法中，首先会将数据集分为训练集和验证集，该方法的大致流程如下:

• 首先利用训练集得到一棵完全生长的决策树
• 然后测试该决策树在验证集上的错误率$E_1$，同时将某个叶节点向上回缩，即让某个父节点成为新的叶节点，验证新的树在验证集上的错误率$E_2$,若$E_2 \leq E_1$，则考虑将父节点成为新的叶节点
• 重复第二步，直到剪枝不能提升在验证集上的错误率

这种剪枝思路的优点在于是有指导有方向的剪枝，理论上讲在验证集上决策树的性能获得提升，也能够在测试集上获得提升，缺点可能就是有可能会导致模型一定程度上对验证集的过拟合。