决策树分类算法

《决策树分类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1就是一棵典型的决策树决策树分类算法决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。1.决策树的组成决策树的基本组成部分有：决策节点、分支和叶,树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类1决策树决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。下面介绍一个具体的构造决策树的过程，该方法是以信息论原理为基础，利用信息论中信息增

2、益寻找:据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量(熵)最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。首先，假设训练集C中含有P类对象的数量为p，N类对象的数量为n，则利用判定树分类训练集中的对象后，任何对象属于类P的概率为p/(p+n)，属于类N的概率为n/(p+n)。当用判定树进行分类时，作为消息源“P”或“有关的判定树，产生这些消息所需的期望信息为：Kp，n)plog,P

3、p+np+nn.nlog.'2如果判定树根的属性A具有m个值{AnA2,Am},它将训练集C划分成{CHC2,-,Cm},其中4包括C中属性A的值为Ai的那些对象。设q包括Pi个类P对象和A个类N对象，子树q所需的期望信息是KPbiii)。以属性A作为树根所要求的期望信息可以通过加权平均得到E(A)=I^4(p:，ni)（Pi+ni）/（p+n）就是第i个分支的权值，显然，它与训练集C中属于C的对象数量成比例。所以按A分支的信息增益为:Gain(A)=I(p，n)-E(A)ID3算法在构造树的过程中，选择增益最大的属性人1＜作为根节点。然后，对子树cnc2，…，c

4、U故同样处理，递归形成判定树。假设表1是一个天气情况的气候数据，描述气候的特征属性有四个：outlook、temperature、humidity、windy，而每个特征属性的可取值为：outlook={sunny,overcast,rain},temperature={cool,mild，hot},humidity={high,normal},windy={true,false}如果某天早晨的天气描述为:Outlook（天象）Temperature（温度）Humidity（湿度）Windy（风）:overcast(明)coolnormal:false那么，它属于哪

5、种类型的气候呢?解:下面介绍用ID3算法如何从表1所给的训练集中构造出一棵能对训练集进行正确分类的判定树。表1气候训练集No.AttributesClassOutlookTemperatureHumidityWindy1SunnyHotHighFalseN2SunnyHotHighTrueN3OvercastHotHighFalseP4RainMildHighFalseP5RainCoolNormalFalseP6RainCoolNormalTrueN7OvercastCoolNormalTrueP8SunnyMildHighFalseN9SunnyCoolNorm

6、alFalseP10RainMildNormalFalseP11SunnyMildNormalTrueP12OvercastMildHighTrueP13OvercastHotNormalFalseP14RainMildHighTrueN在表1所示的训练集中，总共有14个对象，其中9个正例（P类），5个反例（N类）。分类要求的信息是I(p，n)=-(9/14)log(9/14)-(5/14)log(5/14)=0.94bit下面分别计算四个属性Ax=outlook,A2=temperature，A3=humidity,A4=windy的信息増益，选择信息增益最大的属

7、性作为判定树的树根。Ax=outlook的取值为｛sunny,overcast，rain｝。训练集C中14个对象有5个是sunny,2个是正例P，3个是反例N，即Pi=2ni=3I(Pi,110=0.97同理可得：P2=4n2=0I(P2,n2)=0P3=3n3=2I(p3,n3)=0.971则属性Ai=outlook的期望信息要求为:E(A1)=(5/14)I(Pl，110+(4/14)I(p2,n2)+(5/14)I(p3,n3)=0.694bit属性outlook的信息增益为：Gain(outlook)=I(p，n)-E(A1)=0.940-0.694=0