《决策树分类算法.doc》由会员分享，可在线阅读，更多相关《决策树分类算法.doc（10页珍藏版）》请在三一文库上搜索。
1、决策树分类算法决策树是一种用来表示人们为了做出某个决策而 进行的一系列判断过程的树形图。决策树方法的基本 思想是：利用训练集数据自动地构造决策树，然后根 据这个决策树对任意实例进行判定。1.决策树的组成决策树的基本组成部分有： 决策节点、分支和叶， 树中每个内部节点表示一个属性上的测试，每个叶节 点代表一个类。图1就是一棵典型的决策树。片龄0教师。购买城纠不购浜购买不!）列买昨买图1决策树决策树的每个节点的子节点的个数与决策树所使 用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有 多于两个子节点的树称为多叉树。F面介绍一个具体的构造决策树的过程，该
2、方法是以信息论原理为基础，利用信息论中信息增益寻找 数据库中具有最大信息量的字段，建立决策树的一个 节点，然后再根据字段的不同取值建立树的分支，在 每个分支中重复建立树的下层节点和分支。ID3算法的特点就是在对当前例子集中对象进行 分类时，利用求最大熵的方法，找出例子集中信息 量(熵)最大的对象属性，用该属性实现对节点的 划分，从而构成一棵判定树。首先，假设训练集C中含有P类对象的数量为p， N类对象的数量为n，则利用判定树分类训练集中的 对象后，任何对象属于类P的概率为p/(p+n)，属于类N的概率为n/(p+n)。当用判定树进行分类时，作为消息源“ P”或“ N ”有关的判定树，产生这些消
3、息所需的期望信息为：pI（P，n）_/g2log如果判定树根的属性A具有m个值Ai, A2,Am,它将训练集C划分成 C1, C2, , , Cm,其中 Ai包括C中属性A的值为Aj的那些对象。设 Ci包 括pi个类P对象和ni个类N对象，子树Ci所需的 期望信息是I(Pi, ni)。以属性A作为树根所要求的期 望信息可以通过加权平均得到pi + nE(A) -I(p, nJv p + n(Pi+m)/(p+n)就是第i个分支的权值，显然，它与训 练集C中属于Ci的对象数量成比例。所以按 A分 支的信息增益为：Gain(A)=l(p, n)-E(A)ID3算法在构造树的过程中，选择增益最大的属
4、性Ak作为根节点。然后，对子树C1, C2, , , Cm做同样处理，递归形成判定树。例1假设表1是一个天气情况的气候数据，描述气候的特征属性有四个：outlook、temperature、humidity、windy，而每个特征属性的可取值为： outlook=sunny, overcast, rain ,temperature=cool， mild，hot，humidity=high，normal，windy=true， false。如果某天早晨的天气描述为:overcast （阴）:cool:normal:falseOutlook （天象）Temperature （温度）Humidity
5、 （湿度）Windy （风） 那么，它属于哪种类型的气候呢？解：下面介绍用ID3算法如何从表1所给的训练集中构造出一棵能对训练集进行正确分类的判定树。表1气候训练集No.AttributesClassOutlookTemperatureHumidityWindy1SunnyHotHighFalseN2SunnyHotHighTrueN3OvercastHotHighFalseP4RainMildHighFalseP5RainCoolNormalFalseP6RainCoolNormalTrueN7OvercastCoolNormalTrueP8SunnyMildHighFalseN9Sunny
6、CoolNormalFalseP10RainMildNormalFalseP11SunnyMildNormalTrueP12OvercastMildHighTrueP13OvercastHotNormalFalseP14RainMildHighTrueN在表1所示的训练集中，总共有 14个对象，其中9个正例(P类)，5个反例(N类)。分类要求的信息是l(p, n)=-(9/14)log(9/14)-(5/14)log(5/14)=0.94bit下面分别计算四个属性A1= outlook, A2 = temperature, A3=humidity , A4= windy的信息增益，选择信息增益
7、最大的 属性作为判定树的树根。A1 = outlook 的取值为sunny, overcast, rain。训练集C 中 14 个对象有 5 个是 sunny, 2 个是正例 P, 3 个是反例 N ,即P1 = 2“1=3I(p1, n1)=0.97同理可得：p2= 4n2=0I(p 2, n2)=0p3= 3n3=2I(p3, n3)=0.971则属性 A1= outlook 的期望信息要求为：E(A1)=(5/14) I(p 1, n1)+(4/14) I(p 2, n2)+(5/14) I(p 3, n3) = 0.694bit属性 outlook 的信息增益为：Gain(outloo
8、k)=I(p, n)-E(A 1)=0.940-0.694=0.246bit 类似分析可得：Gain (temperature)=0.029 bitGain (humidity) =0.151 bitGain (windy) =0.048 bit 构建判定树的树根和分枝ID3 算法将选择信息增益最大的属性 outlook 作为判定树的根节点，在14个例子中对outlook的3个取值进行分枝，3 个分枝对应 3 个子集，分别是：F1=1 ， 2， 8， 9， 11， F2=3， 7， 12， 13，F3=4， 5， 6， 10， 14其中F2中的例子全属于 P类，因此对应分枝标记为P,其余两个子
9、集既含有正例又含有反例，将递归调用建树算 法。 递归建树算法分别对F,和F3子集利用ID3算法，在每个子集中对各 特征(仍为四个特征)求信息增益。(a) F1 中的 outlook 全取 sunny 值，贝U I(p, n)= E(outlook), 有Gain(outlook) = 0,在余下三个特征属性中求出 humidity 的信息增益最大，以它为该分枝的根结点， 再向下分枝。 Humidity 取 high 全为 N 类，该分枝标 记N，取值normal全为P类，该分枝标记 P。(b) 在F3中，对四个特征属性求信息增益，得到windy特征属性的信息增益最大，贝以它为该分枝根结点，再 向下分枝，它取 ture 时全为 N 类，该分枝标记为 N， 取 false 时全为 P 类，该分枝标记 P。这样就得到如图 2 所示的判定树。图 2 用 ID3 算法得到的有关气候的判定树