[关闭]
@chanvee 2015-09-10T05:36:07.000000Z 字数 2499 阅读 3691

决策树

数据挖掘 决策树


决策树是一种简单的机器学习方法。决策树经过训练之后,看起来像是以树状形式排列的一系列if-then语句。一旦我们有了决策树,只要沿着树的路径一直向下,正确回答每一个问题,最终就会得到答案。沿着最终的叶节点向上回溯,就会得到一个有关最终分类结果的推理过程。今天要总结的包括三种决策树算法:ID3,C45和CART,其中ID3和C45常用来解决分类问题,CART常用来解决回归问题。


ID3

ID3是最基础的一种决策树算法,其思想就是根据特征(feature)的值逐步把数据分类,直到所有的叶子节点属于同一个类型结束。那么这些特征及其值应该怎么来选呢,这里我们就要引入一个概念叫做,熵最早是由香农为了解决对系统信息量化度量的问题而提出的,它的计算公式如下:

Entropy(S)=i=1kpilog2(pi)

其中k表示类别的个数,pi表示类别i的比例。数学上,熵反映了随机变量的随机程度,熵越大表示越随机也就是越无序,反之亦然。

在引入熵之后,接下来我们就可以解决上面的问题了。方法是根据某一个特征划分数据集,其划分前后信息熵会有变化,优先选择的特征是让给让信息熵变化最大或者信息熵增益比最大的特征。根据这样的准侧,我们就可以递归的生成决策树了。


C45

C45算法是在ID3算法上的改进,它与ID3算法最大区别在于其不是根据信息熵增益最大来选择特征,而是根据信息熵增益率来选择。这是因为信息增益存在的一个问题:假设某个属性存在大量的不同值,在划分时将每个值成为一个结点,这样决策树在选择属性时,将偏向于选择该属性,但这肯定是不正确(导致过拟合)的。因此有必要使用一种更好的方法,那就是C4.5中使用的信息增益率(Info Gain Ratio),其考虑了分支数量和尺寸的因素,使用称为内在信息(Intrinsic Information)的概念[1]。 信息熵增益率计算如下:
设样本集S按照离散属性FV个不同取值划分为,s1,s2...sv V个不同的子集,定义Split(S,F):

Split(S,F)=vV|si||S|log2(|si||S|)

Gain(S,F)=i=1kpilog2(pi)vVofFp(v)Entropy(sv)

信息增益率为:
GainRatio(S,F)=Gain(S,F)Split(S,F)

除了选特征的策略不同,相比于ID3,C45还有一些其他的优点:


CART

CART(Classification and Regression Trees)分类回归树,它使用基尼不纯度(Gini Impurity)来决定划分,基尼不纯度的定义为:

Gini(S)=i=1kpi(1pi)=i=1kpii=1kp2i=1i=1kp2i

基尼不纯度表达了一个事件变为其对立事件的概率,基尼不纯度越小表示越纯,所以CART选择特征的策略是选择划分后能使基尼不纯度最小的特征。
CART和C45基本上是类似的算法,主要区别:1)它的叶节点不是具体的分类,而是是一个函数f(),该函数定义了在该条件下的回归函数。2)CART是二叉树,而不是多叉树。
具体而言:
设t代表某个数的节点,t中的样本集合为:{(x1,y1),(x2,y2)...(xn,yn)}, N(t)表示节点t中样本的个数,节点t的应变量的均值为:
y¯=1N(t)i=1,xitN(t)yi

节点内的平方残差为:

SS(t)=i=1,xitN(t)(yiy¯)2

划分(属性)F将t划分为左右节点tL和tR,得到:
Φ(S,F)=SS(t)SS(tL)SS(tR)

能最大化上式的就是最佳划分:
Φ(S,F)=max(Φ(S,F))


剪枝

这里只简单的介绍一下思想。之所以要剪枝,是因为当决策树分支太多或深度太深,就很有可能出现过拟合,因此需要剪枝。一种很naive的方法是预剪枝,就是当树的深度大于某个阈值时停止,但是我们很难去定义这个阈值;另外一种方法时当熵的增加小于某个阈值时停止,这种方法存在的问题是决策树的构建过程中,往往是在熵增加很小后然后熵才会较大的增加。因此,常用的剪枝方法是后剪枝。所谓后剪枝是指在树创建成功后再进行剪枝操作,其方法是,对具有相同节点的一组节点进行检查,判断如果将其合并,熵的增加小于某个阈值的话则进行合并(剪枝)。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注