资源描述：
《决策树DecisionTrees-智能科学与人工智能.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、高级人工智能第七章归纳学习（2）史忠植中国科学院计算技术所10/5/20211史忠植高级人工智能决策树发现概念描述空间一种特别有效的方法是形成决策树。Hunt、Marin、和Stone于1966年研制了一个概念学习系统CLS,可以学习单个概念，并用此学到的概念分类新的实例。Quinlan于1983年研制了ID3(1983)。Schlimmer和Fisher于1986年构造了ID4算法，允许递增式地构造决策树。Utgoff于1988年提出ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树10/5/20212史忠植高级人工智能决策树10
2、/5/20213史忠植高级人工智能决策树10/5/20214史忠植高级人工智能决策树DecisionTreesTreestructureNode=queryonattributeLink=attributevalueLeaf=classRecursivelyseparatedataintosub-populationsPrediction:Traversepath,yieldmostprobableclass10/5/20215史忠植高级人工智能CLS算法(1)如果C中全部实例为正例，则建立一个YES结点，并且停止。如果C中全部实例为反例，则建立一个
3、NO结点，并且停止。否则选择一个属性A,根据它的值v1,…,vn建立决策树。(2)根据值V，将训练实例$C$划分为子集C1,…,Cn。(3)对每个集合Ci递归地应用此算法。10/5/20216史忠植高级人工智能决策树CLS算法可以产生所有可能的决策树，正确分类训练实例，并能选择最简单的决策树。但是，它的学习问题不能太大。为了克服这种限止，ID3采用训练实例的子集，即可以选择窗口来形成决策树。这种树可以正确分类窗口中的所有对象。然后，使用该树可以分类训练集中的所有其它对象。如果该树对所有对象给以正确的解答，那么，它对整个训练集是正确的，算法就结束。如果
4、不是这样，选择一个例外加到窗口继续处理，直到发现正确的决策树为止。10/5/20217史忠植高级人工智能决策树ID3采用信息论方法，减小对象分类的测试期望值。属性选择是基于可能性假设，即决策树的复杂性与消息传递的信息量有关。设C包括类P的对象p和类N的对象n,假设：(1)任何C的正确决策树，以C中表示同样的比例将对象分类。任何对象属于类P的概率为p/(p+n)，属于类N的概率为n/(p+n)。10/5/20218史忠植高级人工智能决策树(2)当用决策树进行分类时，返回一个类。作为消息源`P'或`N'有关的决策树，产生这些消息所需的期望信息为：I(p,
5、n)=-p/p+nlog2(p/(p+n))-n/p+nlog2(n/(p+n))10/5/20219史忠植高级人工智能决策树决策树根的属性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)10
6、/5/202110史忠植高级人工智能决策树ID3检查所有的候选属性，选择增益最大的属性A作为根结点，形成树。然后，对子树C1,C2,…,Cm以同样处理，递归地形成决策树。10/5/202111史忠植高级人工智能信息熵InformativeEstablishesGooddecisiontreesEntropyMeasurehowinformativeisanodeDefinition:P=(p1,p2,…,pn)ThenEntropyofPis:I(P)=-(p1*log(p1)+p2*log(p2)+…+pn*log(pn))10/5/202112史
7、忠植高级人工智能GolfExampleOutlookTemperatureHumidityWindyPlaySunny8585FalseDon’tPlaySunny8090TrueDon’tPlayOvercast8378FalsePlayRain7096FalsePlayRain6880FalsePlayRain6570TrueDon’tPlayOvercast6465TruePlaySunny7295FalseDon’tPlaySunny6970FalsePlayRain7580FalsePlaySunny7570TruePlayOvercast
8、7290TruePlayOvercast8175FalsePlayRain7180TrueDon’tPlay
