Flyaway's Blog

This blog will not update anymore. For new blog, please go to zhouyichu.com.

此博客已停止更新，最新的博客请访问zhouyichu.com

决策树1-建模过程

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

  • 特征选择

  • 决策树生成

  • 剪枝操作

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

特征选择

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

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

信息熵

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

P(X=xi)=pi,i=1,2,⋯,n

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

H(X)=−n∑i=1pilogpi

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

0≤H(X)≤logn

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

P(X=1)=p,X(X=0)=1−p,0≤p≤1

则熵为

H(X)=−plog2p−(1−p)log2(1−p)

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

熵

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

条件熵

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

P(X=xi,Y=yi)=pij,i=1,2,⋯,n;j=1,2,⋯,m

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

H(Y|X)=n∑i=1piH(Y|X=xi)

信息增益

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

g(D,A)=H(D)−H(D|A)

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

信息增益比

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

gR(D,A)=g(D,A)H(D)

Gini指数

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

Gini(X)=K∑k=1pk(1−pk)=1−K∑k=1p2k

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

Gini指数

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

总结

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

  • ID3: 信息增益最大

  • C4.5: 信息增益比最大

  • CART: Gini指数最小

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

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

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

决策树生成

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

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

  1. 若D中所有实例都属于同一个类别(或方差小于预设阈值)，则停止生长，返回决策树T.
  2. 若A=∅，则将D中数量最多的类别(平均值)作为该节点的标记,返回T.
  3. 若A≠∅，则从A中选择一个最优的特征Ai进行子节点的分裂(利用上面所说的分裂标准).分裂得到n个子节点，用Di表示。
  4. 遍历每一个子节点，将Di作为新的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的叶节点个数为|T|,t是T的叶节点，且该节点有N_t个样本

Cα(T)=C(T)+α|T|=|T|∑i=1NtHt(T)+α|T|

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

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

我们的目标是在剪枝的过程中，使得上述的损失函数Cα(T)取得最小值。

具体的剪枝过程如下:

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

写在最后

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

另外，决策树的具体算也不止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)

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

参考资料

  1. July大神的<从决策树学习谈到贝叶斯分类算法、EM、HMM>
  2. Decision Tree：Analysis
  3. <统计机器学习>——李航
  4. 决策树-上-ID3 C4.5 CART及剪枝
  5. C4.5决策树

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

Share on: Twitter ❄ Facebook ❄ Email

Flyaway is the owner of this blog.

Published

Category

machine-learning

Tags

Contact