决策树

1 概述

        决策树(decision tree)是一种基本的分类回归方法。在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性,分类速度快。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测时,对新的数据,利用决策树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。

2  学习基本算法

        决策树学习的策略是以损失函数为目标函数的最小化。 决策树学习的目的是为了产生一棵泛化能力强,即处理未见实例能力强的决策树,其基本流程遵循简单且直观的“分而治之”策略,如下所示:


        显然,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回:(1) 当前结点包含的样本全属于同一类别,无需划分;(2) 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分;(3)当前结点包含的样本集合为空,不能划分。

        在第(2)种情形下,我们把当前结点标记为叶结点,并将其类别设定为该结点所含样本最多的类别;在第(3)种情形下,同样把当前节点标记为叶结点,但将其类别设定为其父结点所含样本最多的类别。注意这两种情形的处理实质不同:情形(2)是在利用当前结点的后验分布,而情形(3)则是把父结点的样本分布作为当前节点的先验分布

3 特征选择

        由算法4.2可知,决策树学习的关键是第8行,即如何选择最优化分属性。一般而言,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”越来越高。

3.1 信息增益

       熵(entropy)是表示随机变量不确定性的度量。 “信息熵”是度量样本集合纯度最常用的一种指标。加点当前样本集合D中第k类样本所占的比例为p_{k} (k=1,2,...,|y|),则D的信息熵定义为

                                                                                        Ent(D)=-\sum_{k=1}^{|y|}p_{k} \log_2 p_{k}

Ent(D)的值越小,则D的纯度越高。由定义可知,熵只依赖于D的分布,而与D的取值无关。

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

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

信息增益,就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

        根据信息增益准则的特征选择方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。

3.2 信息增益比

        信息增益值的大小是相对于训练数据集而言的,并没有绝对意义。在分类问题困难时,也就是说在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益比(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。

定义5.3(信息增益比) 特征A对训练数据集D的信息增益比g_{R}(D,A) 定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比:

                                                                                      g_{R}(D,A)= \frac{g(D,A)}{H(D)}                  (5.10)

4 决策树的生成

4.1 ID3算法

        ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。

算法5.2(ID3算法)
输入:训练数据集D,特征集A,阈值 \varepsilon
输出:决策树T。
(1)若D中所有实例属于同一类C_{k} ,则T为单结点树,并将类C_{k} 作为该结点的类标记,返回T;
(2)若A=Ø,则T为单结点树,并将D中实例数最大的类C_{k} 作为该结点的类标记,返回T;
(3)否则,计算A中各特征对D的信息增益,选择信息增益最大的特征A_{g}
(4)如果A_{g} 的信息增益小于阈值\varepsilon ,则置T为单结点树,并将D中实例数最大的类C_{k} 作为该结点的类标记,返回T;
(5)否则,对A_{g} 的每一可能值a_{i} ,依A_{g}=a_{i}  将D分割为若干非空子集D_{i} ,将D_{i} 中实例数最大的类作为标记,构建子结点,由结点及其子结点构成树T,返回T;
(6)对第i个子结点,以D_{i} 为训练集,以A-{A_{g} }为特征集,递归地调用步(1)~步(5),得到子树T_{i} ,返回T_{i}

4.2 C4.5算法

        C4.5算法与ID3算法相似,C4.5算法对ID3算法进行了改进。C4.5在生成的过程中,用信息增益比来选择特征。

算法5.3(C4.5的生成算法)
输入:训练数据集D,特征集A,阈值\varepsilon
输出:决策树T。
(1)如果D中所有实例属于同一类C_{k} ,则置T为单结点树,并将C_{k} 作为该结点的类,返回T;
(2)如果A=Ø,则置T为单结点树,并将D中实例数最大的类C_{k} 作为该结点的类,返回T;
(3)否则,按式(5.10)计算A中各特征对D的信息增益比,选择信息增益比最大的特征A_{g}
(4)如果A_{g} 的信息增益比小于阈值 ,则置T为单结点树,并将D中实例数最大的类C_{k} 作为该结点的类,返回T;
(5)否则,对Ag的每一可能值ai,依Ag=ai将D分割为子集若干非空D_{i} ,将D_{i} 中实例数最大的类作为标记,构建子结点,由结点及其子结点构成树T,返回T;
(6)对结点i,以D_{i} 为训练集,以A-{Ag}为特征集,递归地调用步(1)~步(5),得到子树T_{i} ,返回T_{i}

5 决策树的剪枝

        决策树生成算法递归地产生决策树,直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树。在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。

        决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数 (cost function)来实现。设树T的叶结点个数为|T|,t是树T的叶结点,该叶结点有N_{t} 个样本点,其中k类的样本点有N_{tk} 个,k=1,2,…,K,H_{t}(T) 为叶结点t上的经验熵,a≥0为参数,则决策树学习的损失函数可以定义为

                                                                C_{a}(T)=\sum_{t=1}^{|T|}N_{t} H_{t}(T) +a|T|                                                    (5.11)

其中,经验熵为                                     H_{t} (T)=-\sum_{k}\frac{N_{tk} }{N_{t} }log  \frac{N_{tk} }{N_{t} }                                                        (5.12)

损失函数中,将式(5.11)右端第1项记作

                                                                   C(T)=\sum_{t=1}^{|T|}N_{t} H_{t}(T)=\sum_{t=1}^{|T|}\sum_{k=1}^K N_{tk}log \frac{N_{tk} }{N_{t} }                    (5.13)

这时有                                                              C_{a}(T)=C(T)+a|T|                                                                 (5.14)

式(5.14)中,C(T)表示模型对训练数据的预测误差,即模型与训练数据的拟合程度|T|表示模型复杂度,参数a≥0控制两者之间的影响。较大的a促使选择较简单的模型(树),较小的a促使选择较复杂的模型(树)。a=0意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。

算法5.4(树的剪枝算法)
输入:生成算法产生的整个树T,参数a;
输出:修剪后的子树T_{a}
(1)计算每个结点的经验熵。
(2)递归地从树的叶结点向上回缩。
         设一组叶结点回缩到其父结点之前与之后的整体树分别为T_{B} T_{A} ,其对应的损失函 数值分别是C_{a}(T_{B} ) C_{a}(T_{A} ) ,如果
                                                                                            C_{a}(T_{A} ) \leq C_{a}(T_{B} )                                         (5.15)
则进行剪枝,即将父结点变为新的叶结点。
(3)返回(2),直至不能继续为止,得到损失函数最小的子树T_{a} 。 

6 CART算法

        分类与回归树(classification and regression tree,CART)模型由Breiman等人在1984年提出,是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成,既可以用于分类也可以用于回归

        CART算法由以下两步组成:
(1)决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大;
(2)决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。

6.1 CART 生成

        决策树的生成就是递归地构建二叉决策树的过程。对回归树平方误差最小化准则, 对分类树基尼指数(Gini index)最小化准则,进行特征选择,生成二叉树。

6.1.1 回归树的生成

算法5.5(最小二乘回归树生成算法)
输入:训练数据集D; 输出:回归树f(x)。
在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子 区域上的输出值,构建二叉决策树:
(1)选择最优切分变量j与切分点s,求解
                                            \min_{j,s} [\min_{c_{1} }\sum_{x_{i\in R_{1}(j,s) } }(y_{i}-c_{1}  )^2+\min_{c_{2} }\sum_{x_{i\in R_{2}(j,s) } }(y_{i}-c_{2}  )^2 ]                             (5.21)
遍历变量j,对固定的切分变量j扫描切分点s,选择使式(5.21)达到最小值的对 (j,s)。
(2)用选定的对(j,s)划分区域并决定相应的输出值:
                                                    R_{1}(j,s)={{x|x^{(j)}\leq s }  }    ,       R_{2}(j,s)={{x|x^{(j)}> s } }

                                                    \hat{c_{m}}=\frac{1}{N_{m} } \sum_{x_{i\in R_{m}(j,s) } }y_{i}, x\in R_{m}   ,m=1,2

(3)继续对两个子区域调用步骤(1),(2),直至满足停止条件。

 (4)将输入空间划分为M个区域R1,R2,…Rm,生成决策树:
                                                f(x)=\sum_{M}^{m=1}\hat{c_{m} }  I(x\in R_{m} )

6.1.2 分类树的生成

        分类树用基尼指数选择最优特征,同时决定该特征的最优二值切分点

定义5.4(基尼指数) 分类问题中,假设有K个类,样本点属于第k类的概率为p_{k} ,则概率分布的基尼指数定义为
                                                    Gini(p)=\sum_{k=1}^K p_{k}(1- p_{k})=1-\sum_{k=1}^K p_{k}^2

        对于给定的样本集合D,其基尼指数为                             Gini(p)==1-\sum_{k=1}^K (\frac{|C_{k}| }{|D|} )
这里,C_{k} 是D中属于第k类的样本子集,K是类的个数。

        如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分,则在特征A的条件下,集合D的基尼指数定义为
                                                        Gini(D,A)=\frac{|D_{1} |}{D}Gini(D_{1})+ \frac{|D_{2} |}{D}Gini(D_{2})            (5.25)
        基尼指数Gini(D)表示集合D的不确定性,基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性.基尼指数值越大,样本集合的不确定性也就越大。

算法5.6(CART生成算法)
输入:训练数据集D,停止计算的条件;
输出:CART决策树。
根据训练数据集,从根结点开始,递归地对每个结点进行以下操作,构建二叉决策 树:
(1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。此时,对每 一个特征A,对其可能取的每个值a,根据样本点对A=a的测试为“是”或“否”将D分割成D1 和D2两部分,利用式(5.25)计算A=a时的基尼指数。
(2)在所有可能的特征A以及它们所有可能的切分点a中,选择基尼指数最小的特征 及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点,从现结点生成 两个子结点,将训练数据集依特征分配到两个子结点中去。
(3)对两个子结点递归地调用(1),(2),直至满足停止条件。
(4)生成CART决策树。

        算法停止计算的条件是结点中的样本个数小于预定阈值,或样本集的基尼指数小于预定阈值(样本基本属于同一类),或者没有更多特征。

6.2 CART剪枝

        CART剪枝算法由两步组成:首先从生成算法产生的决策树T_{0} 底端开始不断剪枝,直到T_{0} 根结点,形成一个子树序列{T_{0} T_{1} ,…,T_{n} };然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树。

算法5.7(CART剪枝算法)
输入:CART算法生成的决策树T_{0} ; 输出:最优决策树T_{a}
(1)设k=0,T=T_{0}
(2)设a=+inf 。
(3)自下而上地对各内部结点t计算C(T_{t}) ,|T_{t} |以及
                                            g(t)=\frac{C(T)-C(T_{t}) }{T_{t}-1 }         a=min(a,g(t))
这里,T_{t} 表示以t为根结点的子树,C(T_{t})是对训练数据的预测误差,|T_{t}|T_{t} 的叶结点个数。
(4)对g(t)=a的内部结点t进行剪枝,并对叶结点t以多数表决法决定其类,得到树T。
(5)设k=k+1,a_{k} =a,T_{k} =T。
(6)如果T_{k} 不是由根结点单独构成的树,则回到步骤(2),否则令T_{k}= T_{n}
(7)采用交叉验证法在子树序列T_{0} ,T_{1},…,T_{n}中选取最优子树T_{a}。 

7 缺失值处理

        现实任务中常会遇到不完整样本,即样本的某些属性值缺失。我们需解决两个问题: (1)如何在属性值缺失的情况下进行划分属性选择?(2)给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?
        给定训练集D和属性a,令\tilde{D} 表示D中在属性a上没有缺失值的样本子集。对问题(1),显然我们仅可根据\tilde{D} 来判断属性a的优劣。假定属性a有V个可取值{a^1, a^2,...,a^V},令\tilde{D} ^V表示\tilde{D} 中在属性a上取值为a^V的样本子集.假定我们为每个样本x赋予一个权重\omega _{x} ,并定义
                                            \tilde{p_{k} }=\frac{\sum_{x\in \tilde{D_{k} } }^b \omega _{x}  }{\sum_{x\in \tilde{D} }^b \omega _{x}}    (1\leq k\leq |Y|),
                                            \tilde{r_{v} }=\frac{\sum_{x\in \tilde{D_{k} } }^b \omega _{x}  }{\sum_{x\in \tilde{D} }^b \omega _{x}}      (1\leq v\leq V)
    直观地看,对属性a, ρ表示无缺失值样本所占的比例,\tilde{p_{k} } 表示无缺失值样本中第k类所占的比例,\tilde{r_{v} } 则表示无缺失值样本中在属性a上取值a^v 的样本所占的比例。
                                            Gain(D,a)=\rho \times (Ent(\tilde{D}-\sum_{v=1}^V \tilde{r_{v} }Ent(\tilde{D^v } )  )
对问题(2),若样本x在划分属性a上的取值已知,则将x划入与其取值对应的子结点,且样本权值在子结点中保持为\omega _{x}
若样本x在划分属性a上的取值未知,则将x同时划入所有子结点,且样本权值在与属性值a^v对应的子结点中调整为\tilde{r_{v} }  ·\omega _{x};直观地看,这就是让同-一个样本以不同的概率划入到不同的子结点中去。

8 小结

        (1)决策树学习旨在构建一个与训练数据拟合很好,并且复杂度小的决策树。决策树学习算法包括3部分:特征选择、树的生成和树的剪枝。常用的算法有ID3、C4.5和CART。
        (2)

        (3)由于生成的决策树存在过拟合问题,需要对它进行剪枝,以简化学到的决策树。
        (4)CART回归树预测结果是根据叶子节点的中位数均值作为预测结果,而CART分类树是根据叶节点的类别概率最大的作为预测结果。
        (5)ID3、C4.5生成的是多叉树,CART生成的是二叉树。CART和C4.5之间主要差异在于分类结果上。ID3只能对分类变量进行处理,C4.5和CART可以处理连续和分类两种自变量。


参考资料:
(1)《统计学习方法》 李航
(2)《机器学习》 周志华
(3)https://mp.weixin.qq.com/s/7ISR9TtPtpp_txSknZXk5Q

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,233评论 6 495
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,357评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,831评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,313评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,417评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,470评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,482评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,265评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,708评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,997评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,176评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,827评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,503评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,150评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,391评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,034评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,063评论 2 352

推荐阅读更多精彩内容

  • 决策树理论在决策树理论中,有这样一句话,“用较少的东西,照样可以做很好的事情。越是小的决策树,越优于大的决策树”。...
    制杖灶灶阅读 5,845评论 0 25
  • 决策树是一种基本分类与回归方法。其不要优点是模型具有可读性,分类速度快。学习时,利用训练数据,根据损失函数最小化的...
    rosyxiao阅读 1,069评论 0 0
  • 1.前言 决策树是一种基本的分类和回归方法。决策树呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。采用...
    胜利主义章北海阅读 2,642评论 0 0
  • 决策树 1.概述 决策树由节点和有向边组成,节点有两种类型,内部节点和叶节点,内部节点表示一个特征或属性,叶节点表...
    Evermemo阅读 2,287评论 0 1
  • Decision Trees (DTs) 是一种用来classification和regression的无参监督学...
    婉妃阅读 6,102评论 0 8