决策树及应用

第5章决策树及应用5.1问题概述各个领域的人工智能实现，常常要涉及这样的问题：从实际问题中提取数据，并从数据中提炼一组数据规则，以支持知识推理实现智能的功能。知识规则一般以“原因一结果”形式表示。一般地，获取知识规则可以通过样本集｛（老）,考），…，X,）,|/c=1,2,建模实现。由于推理结果是有限个，艮IJy的取值是有限的，所以这样的建模属于分类问题。利用神经网络可以实现分类问题建模，但当影响因素变量&的个数较大时，建模后的知识规则不易表示，特别地，当默写变量勤的取值缺失时，即使神经网络具有容错性，也会在一定程度上影响分类结果的不确定性。实际应用中，决定分类结果可能只是几个主要影响因素取值，不依赖全部因素变量，因此，知识规则的提取，可以转换为这样的问题：某一分类卜哪些变量是主要的影响因素，这些主要影响因素与分类结果的因素规则表示如何获取？决策树就是解决这些问题的方法之一。5.2决策树概述决策树学习算法是一组样本数据集（一个样本数据也可以称为实例）为基础的一种归纳学习算法，它着眼于从一组无次序、无规则的样本数据（概念）中推理出决策树表示形式的分类规则。假设这里的样本数据应该能够用“属性一结论”。决策时是一个可以自动对数据进行分类的树形结构，是树形结构的知识表示，可以直接转换为分类规则。它能被看做基于属性的预测模型，树的根节点是整个数据集空间，每个分结点对应一个分裂问题，它是对某个单一变量的测试，该测试将数据集合空间分割成两个或更多数据块，每个叶结点是带有分类结果的数据分割。决策树算法主要针对“以离散型变量作为属性类型进行分类”的学习方法。对于连续性变量，必须被离散化才能被学习和分类。基于决策树的决策算法的最大的有点就在于它在学习过程中不需要了解很多的背景知识，只从样本数据及提供的信息就能够产生一颗决策树，通过树结点的分叉判别可以使某一分类问题仅与主要的树结点对应的变量属性取值相关，即不需要全部变量取值来判别对应的范类。5.2.1决策树基本算法一颗决策树的内部结点是属性或属性的集合，儿叶结点就是学习划分的类别或结论，内部结点的属性称为测试属性或分裂属性。当通过一组样本数据集的学习产生了一颗决策树之后，就可以对一组新的未知数据进行分类。使用决策树对数据进行分类的时候，采用自顶向卜•的递归方法，对决策树内部结点进行属性值的判断比较并根据不同的属性值决定走向哪一条分支，在叶节点处就得到了新数据的类别或结论。从上面的描述可以看出从根结点到叶结点的一条路径对应着一条合取规则，而整棵决策树对应着一组合取规则。图5.1简单决策树根据决策树内部结点的各种不同的属性，可以将决策树分为以卜几种：（1） 当决策树的每一个内部结点都只包含一个属性时，称为单变量决策树：当决策树存在包含多个变量的内部结点时，称为多变量决策树。（2） 根据测试属性的不同属性值的个数，可•能使得每一个内部结点有两个或者是多个分支，如果每一个内部结点只有两个分支则称之为二叉树决策。（3） 分类结果可能是两类也可能是多类，二叉树决策的分类结果只能有两类，股也称之为布尔决策树。5.2.2CLS算法CLS学习算法是1966年有Hunt等人提出的。它是最早的决策树学习算法。后来的许多决策树算法都可以看作是CLS学习算法的改进与更新。CLS的算法的思想就是从一个空的决策出发，根据样本数据不断增加新的分支结点，直到产生的决策树能够正确地将样本数据分类为止。CLS算法的步骤如下：（1）令决策树T的初始状态只含有一个树根（X,Q）,其中X是全体样本数据的集合,Q是全体测试属性的集合。（2） 如果T中所有叶结点（X，，Q'）都有如下状态：或者X，中的样本数据都是属于同一个类，或者Q'为空，则停止执行学习算法，学习的结果为T。（3） 否则，选择一个不具有（2）所描述状态的叶节点3,Q'）.（4） 对于Q',按照一定规则选取属性beQ',设X，被b的不同取值分为m个不同的子集X',1<i<m,从（XLQ）伸出m个分支，每个分支代表属性b的一个不同取值，从而形成m个新的叶结点（X',Q-|b|）,1<i<mo（5） 转（2）o在算法步骤（4）中，并没有明确地说明按照怎样的规则来选取测试属性，所以CLS有很大的改进空间，而后来很多的决策树学习算法都是采取了各种各样的规则和标准来选取测试属性，所以说后来的各种决策树学习算法都是CLS学习算法的改进。5.2.3信息炳Shannon在1948年提出并发展了信息论的观点，主张用数学方法度量和研究信息，提出了以下的一些概念。决策树学习算法是以信息炳为基础的，这些概念将有助于理解后续的算法。（1） 自信息量：在收到％之前，接收者对信源发出％的不确定性定义为信息符号位的自信息量［（缶）=一10g2P（a‘），其中P（缶）是取值为叫的概率。自信息量反映了接收㈤的不确定性，自信息量越大，不确定性越大。（2） 信息炳：自信息量只能反映符号的不确定性，而信息上可以用来度量整个信源X整体的不确定性。H（X）=［-p（ai）log2p（ai）］+…+［-「（如）log2p（an）］=-器iP（q）1哈P（«i） （5.1）式中：n是信源X所有可能的符号数：缶是可能取到的值；p（缶）是取值为叫的概率：信息炳是各个自信息量的期望。（3） 条件炳：如果信源X与随机变量Y不是相互独立的，接收者收到信息Y,那么用条件炳H（X|Y）来度量接信者收到随机变量Y之后，对随机变量X仍然存在的不确定性。X对应信源符号a^i=1,2,…，n）,Y对应信源符号饥（i=l,2,…，s）,?（叫|如）为当Y为与时X为％的概率，则有H（X|Y）=A（bj）H（X|bj）J=1S 71=2p（》J）一£p（a曲）log2P（&|bj）j=l i=lS71=一£2p（S）P（a也）log2P（a#j）j=li=lS71=一£2P（%，®）log2P（a也）j=li=l即条件炳是各种不同条件卜的信息炳期望。（4）平均互信息量：用来表示信号Y所能提供的关于X的信息量的大小，用下式表示,即I（X|Y）=H（X）—H（X|Y）ID3算法上一节己经提到的CLS算法并没有明确地说明按照怎样的规则和标准来确定不同层次的树结点（即测试属性），Quinlan于1979年提出的以信息炳的下降速度作为选取测试属性的标准。ID3算法是各种决策树学习算法中最有影响力、使用最广泛的一种决策树学习算法。5.3.1基本思想设样本数据集为X,目的是要把样本数据集分为n类。设属于第i类的样本数据个数是G,X中总的样本数据个数是|X|,则一个样本数据属于第i类的概率P（G）=协。此时决策树对划分C的不确定程度（即信息炳）为H（x,C）=H（X）=-嚣1P（G）10g2p（G）若选择属性a（设属性a有m个不同的取值）进行测试，其不确定程度（即条件炳）为H(X|a)=—££p(G，a=%)log2P(G|a=印)1=1j=lnm=—=a；)p(G|a=a；)log2p(Cj|a=a；)i=lj=l=〉p(a=a；)£p(q|a=a;)log2p(Cf|a=a；)j=l i=l则属性a对于分类提供的信息量为I（X,a）=H（X）_H（X|a）式中：I（X,a）表示选择了属性a作为分类属性之后信息炳的下降程度，亦即不确定性下降的程度，所以应该选择时的I（X，a）最大的属性作为分类的属性，这样得到的决策树的确定性最大。可见ID3算法继承了CLS算法，并旦根据信息论选择时的I（X,a）最大的属性作为分类属性的测试属性选择标准。另外，ID3算法除了引入信息论作为选择测试属性的标准之外，并且引入窗II的方法进行增量学习。ID3算法的步骤如下：（1） 选出整个样本数据集X的规模为W的随机子集X]（W称为窗I1规模，子集称为窗口）。（2） 以I（X,a）=H（X）-H（X|a）的值最大，即H（X|a）的值最小为标准，选取每次的测试属性，形成当前窗II的决策树。（3） 顺序扫描所有样本数据，找出当前的决策树的例外，如果没有例外则结束。（4） 组合当前窗II的一些样本数据与某些（3）中找到的李哇哦形成新的窗II,转（2）。5.3.2ID3算法应用实例表5.1是有关天*的数据样本集合。每一样本有4个属性变量:Outlook,Temperature,Humidity和Windyo样本被分为两类，P和N,分别表示正例和反例。表5.1天气样本数据

P摩性OutlookemperaturHunidityWindy类别1OvercastHotHighNot1-12OvercastHotHighVeryN3OvercastHotHighMediumN4SunnyHotHighNotP5SunnyHotHighMediumP6RainKildHighNot1-17RainMildHighMedii-unN8RainHotNormalNotp9RainCoolNormalMedimriN10RainHotNormalVeryN11SunnyCoolNormalVeryF12SunnyCoolNormalMediumF13OvercastKildHighNotN14OvercastMildHighMediumN15OvercastCoolNormalNotP16OvercastCoolNormalMedimnF17RainTiTildNormalNotN18RainMildNormalMedimriN19OvercastMildNormalMediumP20OvercastKildNormalVeryP21SunnyMildHighVeryF22SunnyMildHighMediumF23SunnyHotNormalNotP24RainMildHighVeryN首先计算信息炳H(X),由表5.1nJ知，一共有24条记录，其中P类的记录和N类的记录都是12条，则根据上面介绍的信息炳和条件炳的算法，可以得到信息炳值为,、 12 1212 12H(X)=-弱10g2西-护Og2冗=1如果选取Outlook属性作为测试属性，则计算条件炳值H(X|O顽00幻。有表5.1可■知，Outlook属性共有3个属性值，分别是Overcast、Sunny和Rain。Outlook属性取Overcast属性值的记录共有9条，其中P类的记录和N类的记录分别是4条和5条，因此有Overcast引起的炳值为一土⑨哈：+：1哈而Outlook属性取Sunny属性值的记录共有7条，其中P类的记录和N类的记录分别是7条和0条，因此有Sunny引起的炳值为一£(；1。&2；)。同理，Outlook属性取Rain属性值的记录共有8条，其中P类的记录和N类的记录分别是1条和7条，因此有Rain引起的燔值为—£弓1哈§+：log2齐因此条件炳值H(X|O却。。k)应为上述三个式子之和，得到

9/4 45 5\H(X\Outlook)=-—log2-+-log2-j-£(国)一土Glog2i+il°g2i)=05528仿照上面条件炳值H(X|OuHook)的计算方法，可以得到，如果选取Temperature属性为测试属性，则条件炳值为8/4 44 4、H{X\Temperature)=-—-log2-+-log2-

Z4*\oooo/一芬偿1昭2普+£】昭2£)-^04+>g2i)=0.9172如果选取Humidity属性为测试属性，则条件炳值为H(X|Humidity)=H(X|Humidity)=-芬③。位£+浏哈苔)-^(^log2^+]llog2]l)=°.922如果选取Windy属性为测试属性，则条件炳值为, 8z444 4H(X|WZindy)=_^7(plog2+plog2p

Z4-\O OOO.一鳄(会1哈号+&1哈会)=1可见H(X|。国。决)的值最小，所以应该选择Outlook属性作为测试属性，得到根据结点为Outlook属性，根据不同记录的Outlook属性取值的不同，向下引出三条分支，如图5.2所示,其中的数字代表第几条记录。(123,13,14,15,16,19,20)(4,5,11,12,21,2423)(6,7,8,9,10,17,18,24)(123,13,14,15,16,19,20)(4,5,11,12,21,2423)(6,7,8,9,10,17,18,24)图5.2ID3算法第一次分类的决策树综合表5.1和图5.2可以看出,由Sunny引出的分支包括(4,5,11,12,21,22,23)共7条记录,这7条记录都是属于P类的，因此由Sunny音粗的分支得到的是P类。由Overcast引出的分支包括（1,2,343,14,15,16,19,20）共9条记录，类似上面的做法，可以求得3/3 3\H(X|Temperatiire)=—-(^-log2-j-|Qlog2^)=04444. 5/5 5\ 4/4 4\Humidity)=--^-log2-J 6(丁°&1)=0H(X|Windy)= log2|+|log21-|(|log2|+|log2|)一言（：1哈：+：1哈9=0.9728可见HQX\Humidity）的值最小,因此,对于由Overcast引出的分支包括的9条记录(1,2,3,13,14,15,16,19,20)应该选择Humidity作为测试属性。重复上面的做法，直到每一个分支的记录的都是属于同一类，算法结束。最后得到的决策树如图5.3所示。图5.3ID3算法下的决策树C4.5算法C4.5算法（信息比算法）是由Quinlan自己扩充ID3算法提出来的，是ID3算法的改进，它在ID3的基础上增加了对连续属性、属性空缺情况的处理，对树剪枝也有了较成熟的方法。5.4.1基本思想与ID3算法不同，C4.5算法挑选具有最高信息增益率的属性最为测试属性。对样本集T,假设变量a有n个属性，属性取值四，气，…，勤，对应a取值为叫出席那的样本个数分别为叩若n是样本的总数，则应有*+n2+…+nk=noQuinlan利用属性a的炳值H（X,a）来定义为了获取样本关于属性a的信息所需要付出的代价，即k kH（X’a）=-，P（q）log?一（缶）&->,l°g2:

i=l i=l信息增益率定义为平均互信息与获取a信息所付出代价的比值，即（ 、I（X,a）E（X,a）=—JH（X,a）即信息增益率是单位代价所获得的信息量，是一种相对的信息量不确定性度量。一信息增益率作为测试属性的选择标准，是选择E（X,a）最大的属性a作为测试属性。算法C4.5在如下几个方面改进ID3算法：（1） 一些样本的某些属性取值可能为空，字啊构建决策树时，可以简单地忽略确实的属性，即再计算增益率时，即考虑具有属性值的记录。为了对一个具有缺失属性值的记录进行分类,可以基于己知属性值的其他记录来预测缺失的属性值。（2） C4.5算法不仅可以处理离散属性，而且可以处理连续属性。基本思想是基于训练样本中元祖的属性值将数据划分为一些区域。（3） 增加了剪枝算法。在C4.5中，有两种基本的剪枝策略：子树替代法剪枝是指用就叶结点替代子树。仅当替代后的误差率与原始树的误差率接近时才替代。子树替代是从树枝向树根方向进行的。子树上升法剪枝是指用一颗子树中最常用的子树来代替这颗子树。子树从当前位置上升到树中较高的结点处。对于这种替代也需要确定误差率的增加量。（4） 分裂时ID3算法偏袒具有较多值得属性，因而可能导致过拟合，而信息增益率函数可以弥补这个缺陷。但是这个算法同样存在缺点，它偏向于选择对统一属性取值比较集中的属性（即炳值最小的属性），而并不一定是对分类贡献最大、最重要的属性。5.4.2基于信息增益率建模的决策树数据仍按表5.1所列，为了计算Outlook属性作为测试属性的增益比率，首先要计算在忽略类别情况下该测试属性的炳，即9 9 7 7 8 8Outlook)=--l0g2---log2---log2-=1.5774又根据上一节有又根据上一节有12 1212 12H(X)= logo logo—=1'7 245224245224因此，对于Outlook属性增益比率值为1-0.5528105774=0.2835/ 、 1(X91-0.5528105774=0.2835E(X,Outlook)= =H(X,Outlook)仍照上面炳值H(X,Outlook)的计算方法，可以得到，如果选取Temperature属性为测试属性，则有8 8 11 11 5 5^^Temperature)=一万】°g2元一无】°g2万一疝】°g2^=1-5156E(X,Temperature)E(X,Temperature)=1-0.9183 =0.0817112 1212 12如果选取Humidity属性为测试属性，则有12 1212 12H(X|Wumidity)=-—log2—log2—=*E(X,Humidity)=E(X,Humidity)=1-0.91721.5156=0.0546如果选取Windy属性为测试属性，则有8 8 6 6 10 10H(X|Windy)=-—log2—-—log2—log2—=1.5546/、1—1E(X'风知=辰=。可见E(X,Outlook)的值最大，所以应该选择Outlook属性作为测试属性。在该例中，ID3算法与信息增益率法建模得到的决策树没有区别，即以获取信息量确定性的绝对定义与相对定义在该例建数中没有区别。这里去下的信息增益率的递归算法略去。CART算法5.5.1基本思想在ID3与C4.5算法中，当确定作为某层树结点的变量属性取值较多时，按每一属性值引出一分支进行递归算法，就会出现引出的分支较多，对应算法次数也多，使决策树算法速度缓慢，是否可以是每一树结点引出分支尽可能少，以提高算法速度？分类与回归算法(ClassificationandRegressionTrees,CART)是一种产生二叉决策树的技术，即每个树结点(即测试属性)与ID3算法一样，以平均互信息作为分裂属性的度量，对于取定的测试属性变量t,若t有n个属性值Si，S2，…，s’，应选取哪个属性值为作为分裂点引出两个分支

以使分类结果是尽可能合理正确？“最佳〃分裂属性值So被定义为满足条件0（s（）/t）=max（st/t）i其中m0（s/t）=2Pz,Pr£|P（C也）—P（q|tR）|j=i0（5/t）主要度量在结点t的S属性值引出的两个分支时，两只分支的出现的可能性以及两分支每个分类结果出现的可■能性差异大小。当0（5/t）较大时，表示两分支分类结果出现的可能性差异大，即分类不均匀，特别地，当一分支完全含有同一类别结果的样本而另一分支不含有时，差异最大，这种情况越早出现，表示利用越少结点，可以越快获得分类结果O0（S/t）中的L和R是指树中当前结点的左子树和右子树。Pl和&分别指在训练集（样本集）中的样本在树的左边和右边的概率，具体定义为左子树中的样本数

P,= 样本总数右分支的定义为_右子树中的样本数

PR=~样本总数-p（g电）和p（g电）分别指在左子树和右子树中的样本属于类别a的概率，定义为…、左子树属于Cl类的样本数

P（G= h结点样本数P(G|t&)=右子树属于P(G|t&)=右子树属于C\类的样本数

以结点样本数5.5.2基于CART算法建模的决策树表5.2给出了一个光宇身高的数据集合。它有两个属性：性别和身高，被分为三类，分别是矮、中和高。表5.2身高样本数据也 名轮沮1Kristino女"6摇Jim2Masue：i&女1.9中Mamha女1-SS中Stzorjbianio女"7Bob1.锐Kaxhy女1.6Dave男1.722St—x/cc2.1Debbi女L8中Todd男1.95中Kim女"9中Z¥ny女L8中Wyneizte女1L75中设应用平均互信获得当前树结点是身高属性t,t的取值s被划分为6个自区间：(0,1.6),[1.6,1.7),[1.7,1.8),[1.8,1.9),[1.9,2.0),[2.0,8)。利用这些区间，可得到潜在的分裂值1.6,1.7,1.8,1.9,2.0。因此，一句上述分裂点定义，需要从6个可能的属性值中选择一个分裂点，CART算法如下：当S=l.6时，由于Pl(身高vL6)=%=0,所以0(1.6|身蜀=0。XD当S=1.7时，设％代表矮类，C2代表中类，