决策树DecisionTrees-智能科学与人工智能

2020/2/5史忠植高级人工智能1高级人工智能第七章归纳学习（2）史忠植中国科学院计算技术所2020/2/5史忠植高级人工智能2决策树发现概念描述空间一种特别有效的方法是形成决策树。Hunt、Marin、和Stone于1966年研制了一个概念学习系统CLS,可以学习单个概念，并用此学到的概念分类新的实例。Quinlan于1983年研制了ID3(1983)。Schlimmer和Fisher于1986年构造了ID4算法，允许递增式地构造决策树。Utgoff于1988年提出ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树2020/2/5史忠植高级人工智能3决策树2020/2/5史忠植高级人工智能4决策树2020/2/5史忠植高级人工智能5决策树DecisionTreesTreestructureNode=queryonattributeLink=attributevalueLeaf=classRecursivelyseparatedataintosub-populationsPrediction:Traversepath,yieldmostprobableclass2020/2/5史忠植高级人工智能6CLS算法(1)如果C中全部实例为正例，则建立一个YES结点，并且停止。如果C中全部实例为反例，则建立一个NO结点，并且停止。否则选择一个属性A,根据它的值v1,…,vn建立决策树。(2)根据值V，将训练实例$C$划分为子集C1,…,Cn。(3)对每个集合Ci递归地应用此算法。2020/2/5史忠植高级人工智能7决策树CLS算法可以产生所有可能的决策树，正确分类训练实例，并能选择最简单的决策树。但是，它的学习问题不能太大。为了克服这种限止，ID3采用训练实例的子集，即可以选择窗口来形成决策树。这种树可以正确分类窗口中的所有对象。然后，使用该树可以分类训练集中的所有其它对象。如果该树对所有对象给以正确的解答，那么，它对整个训练集是正确的，算法就结束。如果不是这样，选择一个例外加到窗口继续处理，直到发现正确的决策树为止。2020/2/5史忠植高级人工智能8决策树ID3采用信息论方法，减小对象分类的测试期望值。属性选择是基于可能性假设，即决策树的复杂性与消息传递的信息量有关。设C包括类P的对象p和类N的对象n,假设：(1)任何C的正确决策树，以C中表示同样的比例将对象分类。任何对象属于类P的概率为p/(p+n)，属于类N的概率为n/(p+n)。2020/2/5史忠植高级人工智能9决策树(2)当用决策树进行分类时，返回一个类。作为消息源`P'或`N'有关的决策树，产生这些消息所需的期望信息为：I(p,n)=-p/p+nlog2(p/(p+n))-n/p+nlog2(n/(p+n))2020/2/5史忠植高级人工智能10决策树决策树根的属性A具有A1,A2,…,Am，它将C划分为C1,C2,…,Cm,其中Ci包括C中属性A的值为Ai的那些对象。设Ci包括类P的对象pi和类N的对象ni。子树Ci所需的期望信息是I(pi,ni)。以属性A作为树根所要求的期望信息可以通过权值平均得到：E(A)={pi+ni}/{p+n}I(pi,ni)其中第i个分支的权值是与C中属于Ci的对象成比例。所以按A分支的信息增益为：gain(A)=I(p,n)-E(A))(AE2020/2/5史忠植高级人工智能11决策树ID3检查所有的候选属性，选择增益最大的属性A作为根结点，形成树。然后，对子树C1,C2,…,Cm以同样处理，递归地形成决策树。2020/2/5史忠植高级人工智能12信息熵InformativeEstablishesGooddecisiontreesEntropyMeasurehowinformativeisanodeDefinition:P=(p1,p2,…,pn)ThenEntropyofPis:I(P)=-(p1*log(p1)+p2*log(p2)+…+pn*log(pn))2020/2/5史忠植高级人工智能13GolfExampleOutlookTemperatureHumidityWindyPlaySunny8585FalseDon’tPlaySunny8090TrueDon’tPlayOvercast8378FalsePlayRain7096FalsePlayRain6880FalsePlayRain6570TrueDon’tPlayOvercast6465TruePlaySunny7295FalseDon’tPlaySunny6970FalsePlayRain7580FalsePlaySunny7570TruePlayOvercast7290TruePlayOvercast8175FalsePlayRain7180TrueDon’tPlay2020/2/5史忠植高级人工智能14信息熵EntropyForexample:1.IfP=(0.5,0.5)I(P)=12.IfP=(2/3,1/3)I(P)=0.923.IfP=(1,0)I(P)=0Whatdousee?EntropyofpreviousgolfexampleI(P)=I(9/14,5/14)=-(9/14*log(9/14)+5/14*log(5/14))=0.942020/2/5史忠植高级人工智能15信息熵EntropyofanattributeForexample:I(Outlook,T)=5/14*I(2/5,3/5)+4/14*I(4/4,0)+5/14*I)(3/5,2/5)=0.694WhileI(windy,T)=0.8922020/2/5史忠植高级人工智能16信息增益InformationGainGain(T,A)=I(T)–I(T,A)I(T)=expectedinformationfordistinguishingclasses=-(p/(p+n)log2(p/(p+n))+n/(p+n)log2(n/(p+n)))I(T,A)=expectedinformationoftreewithAasroot=i(pi+ni)/(p+n)*I(Ti)p,n:numberofpositive/negativetrainingdatapi,ni:numberofpositive/negativetrainingdatainthetrainingdataTipartitionedbytheattributevalueAi•SelectanattributewithhighestinformationgainPreferanattributeAwithsmallestI(T,A)i.e.,Prefertheattributethatmakesnon-uniformdistribution2020/2/5史忠植高级人工智能17信息增益TheinitialinformationI(T)=I(9/14,5/14)=0.94TheinformationforOutlookattributeSunny,Overcast,RainI(T,Outlook)=5/14*I(2/5,3/5)+4/14*I(4/4,0/4)+5/14*I(3/5,2/5)=0.694Gain(T,Outlook)=0.94-0.694=0.246TheinformationforWindyattributeTrue,FalseI(T,Windy)=6/14*I(3/6,3/6)+8/14*I(6/8,2/8)=0.892Gain(T,Windy)=0.94-0.892=0.048selectOutlookattributeforthefirstpartition2020/2/5史忠植高级人工智能18信息增益EntropyofanattributeDefinitionofGain()Gain(X,T)=I(T)–I(X,T)Gain(Outlook,T)=I(T)–I(Outlook,T)=0.94–0.694=0.246Gain(Windy,T)=I(T)–I(Windy,T)=0.94–0.892=0.048Wesay,OutlookismoreinformativethanWindy,Why?2020/2/5史忠植高级人工智能19ID3算法(1)选择给定训练实例的随机子集（称为窗口）。(2)重复(a)形成一条规则解释当前窗口。(b)从其余实例中寻找该规则的例外。(c)由当前窗口和规则例外生成新的窗口。直到该规则没有例外为止。2020/2/5史忠植高级人工智能20决策树学习算法ID3DecisionTreeLearningAlgorithmID3(Examples,Target,Attributes)•Createarootnode•IfallExampleshavethesameTargetvalue,givetherootthislabel•ElseifAttributesisemptylabeltherootaccordingtothemostcommonvalue•Elsebegin•Calculatetheinformationgainforeachattribute,accordingtotheaverageentropyformula•Selecttheattribute,A,withthelowestaverageentropy(highestinformationgain)andmakethistheattributetestedattheroot•end2020/2/5史忠植高级人工智能21决策树学习算法•Foreachpossiblevalue,v,ofthisattribute•Addanewbranchbelowtheroot,correspondingtoA=v•LetExamples(v)bethoseexampleswithA=v•IfExamples(v)isempty,makethenewbranchaleafnodelabelledwiththemostcommonvalueamongExamples•ElseletthenewbranchbethetreecreatedbyID3(Examples(v),Target,Attributes-{A})•end2020/2/5史忠植高级人工智能22C4.5ExtensionsC4.5isanextensionsofID3accountsforDepth-firststrategyisusedUnavailablevaluesEx:onlygivenOutlooktobeSunnyContinuousattributevaluerangesEx:humidityisgreaterthan75PruningofdecisiontreesRulederivation2020/2/5史忠植高级人工智能23c4.5–fgolfdecisiontreerepresentedgraphically2020/2/5史忠植高级人工智能24c4.5rules–fgolf:inducedrules2020/2/5史忠植高级人工智能25DecisionTrees:Training[C4.5,Quinlan,1993]Generate_tree(R,C,T)//R:setofnon-categoricalattribute//C:categoricalattribute,T:trainingdata1.ifThasthesamecategoricalvaluethenreturnasinglenodewiththevalue2.ifR={}thenreturnasinglenodewithmostfrequentcategoricalvalueinT3.A=attributewithhighestinfo