在上一篇文章中说明了什么是决策树模型，以及它的优缺点。本篇文章主要是用来说明决策树模型是如何建模的，回顾上一篇文章中的内容，决策树的学习过程主要分为以下3个部分:

特征选择
决策树生成
剪枝操作

本文的重点在于说明以上三个步骤是如何操作的，但是并不会给出具体的代码，只是从原理上进行分析，代码实现部分会在下一篇博文中给出。

特征选择

特征选择可以说是整个决策树生长过程中最重要的一个部分，如果特征选择的好，决策树的性能就会很好，相反如果特征选择的不好，则性能就可能不理想。

目前来说，主要的选择标准是信息增益,信息增益比,Gini指数,针对不同的实现算法，采用不同的选择标准。在具体说明这三个概念之前，首先需要说明几个重要的概念:

信息熵

在概率论中，熵(entropy)¹是用来衡量随机变量不确定性的。假设$X$是一个取有限值的离散随机变量，其概率分布为:

$$ \begin{equation} P(X=x_i) = p_i, i=1,2,\cdots,n \end{equation} $$

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

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

熵越大，随机变量的不确定就越大，从定义中可知:

$$ \begin{equation} 0\leq H(X)\leq \log n \end{equation} $$

当随机变量只取两个值时，即$X$的分布为

$$ \begin{equation} P(X=1)=p,X(X=0)=1-p, 0\leq p \leq 1 \end{equation} $$

则熵为

$$ \begin{equation} H(X) = -p\log_2p-(1-p)log_2(1-p) \end{equation} $$

此时，熵$H(X)$随概率$p$变化的曲线如下图所示:

根据上面的公式，我们可以看到当$p_i=0$或$p_i=1$时，$H(X)=0$，从直观上很好理解，当某个事件出现的概率是0或1时，则我们认为这是一个确定事件，其中并不包含不确定性,因此其信息熵为0.

条件熵

假设有随机变量$(X,Y)$，其联合概率分布为:

$$ \begin{equation} P(X=x_i,Y=y_i) = p_{ij},i=1,2,\cdots,n; j=1,2,\cdots,m \end{equation} $$

则条件熵($H(Y\big\vert X)$)表示在已知随机变量$X$的条件下随机变量$Y$的不确定性，其定义为$X$在给定条件下$Y$的条件概率分布的熵对$X$的数学期望:

$$ \begin{equation} H(Y\big\vert X) = \sum_{i=1}^{n}p_iH(Y\big\vert X=x_i) \end{equation} $$

信息增益

信息增益(information gain)表示得知特征$X$的信息后，而使得$Y$的不确定性减少的程度。定义为:

$$ \begin{equation} g(D,A) = H(D) - H(D\big\vert A) \end{equation} $$

上面说明了那么多，终于到了这个关键概念了，在决策树节点分裂的过程中，算法会遍历所有的特征，从中选择使得当前节点的信息增益最大的那一维特征进行分裂。

信息增益比

可以看到，上面的信息增益是基于绝对数值的，当数据集本身的信息熵很大的时候，信息增益就会偏大。为了解决这个问题，我们可以使用信息增益比(information gain)来解决这个问题，信息增益比的定义如下:

$$ \begin{equation} g_R(D,A) = \frac{g(D,A)}{H(D)} \end{equation} $$

Gini指数

除了使用信息熵相关的概念来作为节点的分裂标准，有些算法还使用了其他的标准。比如Gini指数,其定义如下:

$$ \begin{equation} Gini(X) = \sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^K p_k^2 \end{equation} $$

Gini指数和熵的概念类似，也是用来表示一个随机变量的不确定性的，但是它和熵又有少许差别，如下图所示:

Gini指数

从上图中可以看出，Gini指数与信息熵的图像很相似，只是收敛速度不同而已。

总结

上面提到的三个概念信息增益,信息增益比和Gini指数都是可以用来作为节点分裂的标准，针对不同的算法，采用不同的标准:

ID3: 信息增益最大
C4.5: 信息增益比最大
CART: Gini指数最小

上面三种算法是决策树实现中最经典的算法，也各有利弊，具体对这三个算法的分析，将会在下一篇博文中说明。

但是还有一些特殊情况，如果需要解决的问题是一个回归问题，而不是分类问题，那么上述三种分裂标准将没有计算意义，在这种情况下，可以选择是用方差最小的标准来选择最优的分裂特征。

最后需要强调的是，上面各个公式中的概率$p$都是可以从训练数据中利用极大似然估计得到，因此每一个节点的信息熵及其对每一维特征的条件熵都是比较容易计算的。具体计算的例子请参阅李航老师的《统计学习方法》决策树一章，此处不再给出。

决策树生成

之前提到过，寻找一棵最优的决策树是一个NP难题，因此只能采用一种基于启发式的贪心策略来寻找最优决策树。

决策树的生长过程主要有如下几步(假设训练数据集为$D$,特征集为$A$):

若$D$中所有实例都属于同一个类别(或方差小于预设阈值)，则停止生长，返回决策树T.
若$A = \varnothing$，则将$D$中数量最多的类别(平均值)作为该节点的标记,返回T.
若$A\neq \varnothing$，则从$A$中选择一个最优的特征$A_i$进行子节点的分裂(利用上面所说的分裂标准).分裂得到$n$个子节点，用$D_i$表示。
遍历每一个子节点，将$D_i$作为新的$D$，从第一步开始重复上述操作。

上面的算法过程是我自己理解的，这篇文章主要关注点是模型本身，因此这里的算法比较抽象，和原始论文中的算法应该有些出入，但是基本思想还是一致的。

剪枝操作

决策树在生长过程中是很有可能发生过拟合的，因为决策树长得越大(层次越深)说明它分类分得越细，在训练数据上能够取得非常好的效果，但是对于未知的数据来说，就缺泛化性了，导致过拟合的现象。

解决这个问题的方法是通过剪枝操作，剪枝操作又分为预剪枝和后剪枝。

预剪枝是指在树的生长过程中就做好预防措施，防止树长得过于庞大。比如设定树的最深层次(max-depth)、节点停止分裂的阈值等。

后剪枝是指在树完全生长之后，对树进行修剪操作，也就是说将决策树的学习过程分成两部分:1. 尽可能的生长树 2.对完全生长的树进行剪枝。

常见的后剪枝操作主要有:

降低错误剪枝(REP:Reduced Error Pruning)
悲观错误剪枝(PEP:Pessimistic Error Pruning)
基于错误剪枝(EBP:Error-Based Pruning)
代价-复杂度剪枝(CCP:Cost-Complexity Pruning)

这里虽然列出了很多的后剪枝方法，但是我并不是全部理解的，这里只能选择最简单的一种操作来进行说明。

降低错误剪枝(REP:Reduced Error Pruning)

在剪枝操作开始之前，我们首先需要判断一棵决策树是好的还是不好的,也就是说是否会发生过拟合现象。通常来说，我们可以用一个损失函数来表征一棵树的好坏。假设一棵树$T$的叶节点个数为$\vert T\vert$,$t$是$T$的叶节点，且该节点有$N\_t$个样本

$$ \begin{equation} C_{\alpha}(T) = C(T) + \alpha\vert T \vert = \sum_{i=1}^{\vert T \vert}N_tH_t(T) + \alpha\vert T \vert \end{equation} $$

其中$H_t(T)$表示节点$t$所包含的信息熵。

在上面的损失函数中，$C(T)$表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，而后面的一项$\alpha \vert T\vert$表示模型本身的复杂程度，参数$\alpha$是用来控制两者之间的影响力的。$\alpha$比较大的时候，会导致比较简单的树，而当$\alpha=0$时，表示不考虑模型本身的复杂度。

我们的目标是在剪枝的过程中，使得上述的损失函数$C_{\alpha}(T)$取得最小值。

具体的剪枝过程如下:

自底向上的遍历每一个非叶节点(除了根节点)，将当前的非叶节点从树中减去，其下所有的叶节点合并成一个节点，代替原来被剪掉的节点。
计算剪去节点前后的损失函数，如果剪去节点之后损失函数变小了，则说明该节点是可以剪去的，并将其剪去；如果发现损失函数并没有减少，说明该节点不可剪去，则将树还原成未剪去之前的状态。
重复上述过程，直到所有的非叶节点(除了根节点)都被尝试了。

写在最后

本文主要对决策树模型的三个步骤进行了一些说明，但是真正的关于决策树的内容还有很多，比如在节点进行分裂的时候，不一定是只看一个特征的，可以由多个个特征共同决定如何分裂，这就是所谓的多变量决策树。

另外，决策树的具体算也不止ID3、C4.5和CART这三种，还有很多其他的变种算法，比如:

Quest(Quick unbiased efficient statistical tree)
SLIQ(Supervised Learning In Quest)
SPRINT(Scalable Parallelizable Induction of Classification Tree)
PUBLIC(Pruning and Building Integrated in Classification)
CHAID(Chi-squard Automatic Interaction Detector)

有兴趣深入研究的朋友可以找找相关的论文学习一下。

参考资料

熵在信息论中是一个非常重要的概念，很多机器学习的算法都会利用到这个概念。它首次是由香农在1948年从物理学中引入到信息论中，信息熵给了我们一种度量不确定性的方式。 ↩

Flyaway is the owner of this blog.

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

决策树1-建模过程

特征选择

信息熵

条件熵

信息增益

信息增益比

Gini指数

总结

决策树生成

剪枝操作

降低错误剪枝(REP:Reduced Error Pruning)

写在最后

参考资料

Comments

Published

Category

Tags

Contact