5决策树

1决策树(DecisionTree)2019/8/2921、分类的意义数据库了解类别属性与特征预测分类模型—决策树分类模型—聚类一、分类(Classification)2019/8/293数据库分类标记性别年龄婚姻否是否是FemaleMale35≧35未婚已婚2019/8/292、分类的技术（1）决策树4（2）聚类2019/8/293、分类的程序5模型建立(ModelBuilding)模型评估(ModelEvaluation)使用模型(UseModel)2019/8/29决策树分类的步骤6数据库2019/8/29训练样本(trainingsamples)建立模型测试样本(testingsamples)评估模型例：7资料训练样本婚姻年龄家庭所得否是否是未婚已婚35≧35低高否小康1.建立模型测试样本2.模型评估错误率为66.67%修改模型3.使用模型2019/8/294、分类算法的评估8预测的准确度：指模型正确地预测新的或先前未见过的数据的类标号的能力。训练测试法(training-and-testing)交叉验证法(cross-validation)例如，十折交叉验证。即是将数据集分成十分，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10倍交叉验证求均值，例如10次10倍交叉验证，更精确一点。2019/8/292019/8/299速度：指产生和使用模型的计算花费。建模的速度、预测的速度强壮性：指给定噪声数据或具有缺失值的数据，模型正确预测的能力。可诠释性：指模型的解释能力。102019/8/29决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART、SLIQ及SPRINT算法等）。二、决策树(DecisionTree)信息增益信息越明确，所包含的信息量越大，熵越小，信息增益越大，反正，熵越大比如明天太阳从东边出来,熵最小比如投硬币，谁都不知道下一次将会是那一面，熵最大决策树分裂的基本原则是数据集被分裂为若干个子集后，要使每个子集中的数据尽可能的纯，也就是说子集中的记录要尽可能属于同一个类别，即要使分裂后各子集的熵尽可能的小。要让树尽可能的简洁，不能太复杂，因此选择熵最小的属性作为分裂节点2019/8/2911（一）决策树的结构12根部节点(rootnode)中间节点(non-leafnode)(代表测试的条件)分支(branches)(代表测试的结果)叶节点(leafnode)(代表分类后所获得的分类标记)2019/8/292019/8/2913（二）决策树的形成例：14根部节点中间节点停止分支？2019/8/29（三）ID3算法(C4.5,C5.0)152019/8/29Quinlan(1979)提出，以Shannon(1949)的信息论为依据。ID3算法的属性选择度量就是使用信息增益，选择最高信息增益的属性作为当前节点的测试属性。信息论：若一事件有k种结果，对应的概率为Pi。则此事件发生后所得到的信息量I(熵，视为Entropy)为：I=-(p1*log2(p1)+p2*log2(p2)+…+pk*log2(pk))Example1：设k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25I=-(.25*log2(.25)*4)=2Example2：设k=4p1=0,p2=0.5,p3=0,p4=0.5I=-(.5*log2(.5)*2)=1Example3：设k=4p1=1,p2=0,p3=0,p4=0I=-(1*log2(1))=02019/8/29162019/8/2917信息增益18Example(Gain)n=16n1=4I(16,4)=－((4/16)*log2(4/16)+(12/16)*log2(12/16))=0.8113E(年龄)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946Gain(年龄)=I(16,4)-E(年龄)=0.0167Gain(年龄)=0.0167Max:作为第一个分类依据2019/8/29Gain(性别)=0.0972Gain(家庭所得)=0.0177Example(续)19Gain(家庭所得)=0.688I(7,3)=-((3/7)*log2(3/7)+(4/7)*log2(4/7))=0.9852Gain(年龄)=0.9852Gain(年龄)=0.2222I(9,1)=-((1/9)*log2(1/9)+(8/9)*log2(8/9))=0.5032Gain(家庭所得)=0.50322019/8/29Example(end)ID3算法20分类规则：IF性别=FemaleAND家庭所得=低所得THEN购买RV房车=否IF性别=FemaleAND家庭所得=小康THEN购买RV房车=否IF性别=FemaleAND家庭所得=高所得THEN购买RV房车=是IF性别=MaleAND年龄35THEN购买RV房车=否IF性别=MaleAND年龄≧35THEN购买RV房车=是资料DecisionTree2019/8/29计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第1步计算决策属性的熵决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-1步计算年龄的熵年龄共分三个组：青年、中年、老年青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-2步计算年龄的熵年龄共分三个组：青年、中年、老年中年买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-3步计算年龄的熵年龄共分三个组：青年、中年、老年老年买与不买比例为125/127S1(买)=125S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-4步计算年龄的熵年龄共分三个组：青年、中年、老年所占比例青年组384/1025=0.375中年组256/1024=0.25老年组384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年龄信息增益）=0.9537-0.6877=0.2660（1）决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第3步计算收入的熵收入共分三个组：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第4步计算学生的熵学生共分二个组：学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811=0.1726（3）决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第5步计算信誉的熵信誉分二个组：良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048=0.0453（4）决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第6步计算选择节点年龄信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年龄信息增益=0.9537-0.7811=0.1726（3）信誉信息增益=0.9537-0.9048=0.0453（4）决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中