决策树1

课程要求1.完成作业要求2.缺课不能多于一次参考书数据挖掘：概念与技术（原书第3版）（美）韩家炜（Han，J.）等著，范明等译，机械工业出版社数据挖掘导论(完整版)，（美）陈封能，（美）斯坦巴赫，（美）库玛尔著，范明等译，人民邮电出版社基于Clementine的数据挖掘，薛薇等编著，中国人民大学出版社数据挖掘Clementine应用实务，谢邦昌主编，机械工业出版社作业一：决策树以实例解释下列算法ID3C4.5CARTCHAID决策树剪枝的一个具体实例ID3算法ID3决策树建立算法1决定分类属性；2对目前的数据表，建立一个节点N；3如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类；4如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别；5否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性6节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏，如果分支数据表非空，则运用以上算法从该节点建立子树。ID3算法信息增益Example(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:作为第一个分类依据Gain(性别)=0.0972Gain(家庭所得)=0.0177Example(续)7Gain(家庭所得)=0.3059I(7,3)=-((3/7)*log2(3/7)+(4/7)*log2(4/7))=0.9852Gain(年龄)=0.9852I(9,1)=-((1/9)*log2(1/9)+(8/9)*log2(8/9))=0.5032Gain(年龄)=0.281Gain(家庭所得)=0.5032Example(end)ID3算法分类规则：IF性别=FemaleAND家庭所得=低所得THEN购买RV房车=否IF性别=FemaleAND家庭所得=小康THEN购买RV房车=否IF性别=FemaleAND家庭所得=高所得THEN购买RV房车=是IF性别=MaleAND年龄35THEN购买RV房车=否IF性别=MaleAND年龄≧35THEN购买RV房车=是资料DecisionTreeC4.5算法C4.5算法也是机器学习算法中的一种分类决策树算法,此算法用信息增益率来选择决策属性，其核心算法是ID3算法。它继承了ID3算法的全部优点，并在ID3的基础上增加了对连续属性的离散化、对未知属性的处理和产生规则等功能，克服了ID3算法的不足。C4.5算法应用实例C4.5分类算法在硕士研究生智育测评中的应用•采用某高校硕士研究生一年级的20名学生的期末考试成绩作为数据集,其中的课程有英语精读、英语听说等英语类课程、自然辩证法、科学社会主义等政治类课程,还有数据挖掘概论、数据库原理、并行计算导论等专业性课程。•在建立决策树的过程中,我们将按以下方式分类:政治成绩(包括自然辩证法和科学社会主义),英语成绩(包括英语精读、英语听说和专业外语),核心专业课成绩(与本专业培养目标最紧密的课程),一般专业课成绩(除核心专业课外的专业课)。•将这四个属性作为决策属性,定义成绩大于等于85分为“优”;大于等于80,小于85分为“良”;大于等于70,小于80为“中”。将四个属性的和作为智育成绩,并按智育测评的标准,将训练样本中智育成绩由高到低按比例分类:10%为优、30%为良、40%为中等、剩余为及格四个标准,并将这四个标准作为分类属性(如表1所示)。C4.5算法应用实例表1决策树训练样本集编号政治英语核心专业课一般专业课智育成绩178.6783.3388.1486336.1428183.6794.8686.44345.97383.3391.3390.4387.06352.15481.3382.593.3388.2345.36571.3378.1790.8685.93326.29683.3379.6787.1480330.1477980.839087.32337.1588282.6788.7182.28335.66972.6781.3387.583.13324.631081.3384.8381.2987.78335.23C4.5算法应用实例表1决策树训练样本集编号政治英语核心专业课一般专业课智育成绩1177.3380.585.1486.53329.501275.6786.591.1390.41343.711381.338489.3389.56344.221484.3385.679181.53342.53158285.588.1782.26337.931679.678586.8686.89338.42177986.178988.75342.921878.6783.8378.2989.38330.171985.6786.6794.2987.94354.572079.3379.1787.8380.72327.05C4.5算法应用实例建立决策树智育成绩中达到优、良、中等、及格四类标准的子集数分别为:r1=2、r2=6、r3=8、r4=4,首先计算集合T分类的信息熵:I(r1、r2、r3、r4,)=I(2,6,8,4)==1.9464393然后计算每个决策属性的期望信息量(即熵值),以决策属性“政治成绩”为例,分别计算它为优、良、中三个类别时的期望信息量,最终得出它的信息增益率。202log202-2206log206-2208log208-2204log204-2C4.5算法应用实例(1)当“政治成绩”为优时,I(u11,u21,u31,u41)=I(1,0,0,0)=0.225;(2)当“政治成绩”为良时,I(u12,u22,u32,u42)=I(1,4,4,0)(3)当“政治成绩”为中时,201log201-2204log204-2392.1204log204-2522.1204log204204log204202log202)4,4,2,0(),,,(I22243332313IuuuuC4.5算法应用实例所以政治成绩的期望信息量为：387.1),,,(2010),,,(209),,,(I201(E433323134232221241312111uuuuIuuuuIuuuu政治成绩）政治成绩的信息增益为：0.559(),,,(I(G4321政治成绩）政治成绩）Errrrain政治成绩的信息增益率为：0.4029096E((（政治成绩）政治成绩）政治成绩）GainRatioC4.5算法应用实例同理,得出决策属性“英语成绩”、“核心专业课成绩”、“一般专业课成绩”的信息增益率分别为:0.366E((（英语成绩）英语成绩）英语成绩）GainRatio0.144E((（核心专业）核心专业）核心专业）GainRatio0.117E((（一般专业课）一般专业课）一般专业课）GainRatioC4.5算法应用实例决策属性“政治成绩”的信息增益率最大,因此将此作为决策树的根节点,对于每个分支按上述步骤,根据信息增益率由大到小,建立从根节点到叶节点的决策树。C4.5算法应用实例C4.5算法应用实例由此决策树可知:(1)英语成绩为优的情况下,核心专业课成绩全为优,一般专业课成绩为优的概率是71.4%。说明英语水平的提高对计算机专业课程的学习有很大的帮助,对于出色的完成培养目标具有至关重要的作用。(2)核心专业课成绩为优的情况下,一般专业课成绩为优的概率是66.7%。说明核心专业课成绩的提高对一般专业课成绩的提高是正相关的。(3)在智育成绩为“良”以上的同学中,他们的核心专业课成绩都是“优”。说明这种课程设置方式,使智育成绩优异的同学,核心专业课成绩也非常优秀,这是研究生教育管理者最希望看到的结果。(4)政治成绩的好坏,对于英语成绩、专业课成绩的好坏没有必然的联系。这些规则,可以帮助硕士研究生认清课程间的联系,指导他们在学习过程中,做出最有利于自身发展的选择。CART算法CART采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。CART算法生成的决策树是结构简洁的二叉树。CART与C4.5/C5.0算法最大的区别是：其在每一个节点上都采用二分法，也就是一次只能够有两个子节点，C4.5/C5.0则在每一个节点上可产生不同数量的分枝。另外，它与ID系列算法和C4.5的另一个不同是使用的属性度量标准是Gini指标，Gini值越小，表明样本的“纯净度”越高。纯净度度量——GINI对于一个给定的结点t：是结点t中类j的相对频率最大值：(1-1/nc)，记录在所有类中等分布最小值：0，所有记录属于同一个类2)]([1)(jtjptGINICART算法实例训练集选择最佳分割点数值型变量对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。分类型变量列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。Gini(t1)=1-(3/3)²-(0/3)²=0Gini(t2)=1-(4/7)²-(3/7)²=0.4898Gini=0.3×0+0.7×0.4898=0.343单身已婚离异否241是201单身或已婚离异否61是21单身或离异已婚否34是30离异或已婚单身否52是12Gini(t1)=1-(2/4)²-(2/4)²=0.5Gini(t2)=1-(0/4)²-(4/4)²=0Gini(t3)=1-(1/2)²-(1/2)²=0.5Gini=4/10×0.5+4/10×0+2/10×0.5=0.3Gini(t1)=1-(6/8)²-(2/8)²=0.375Gini(t2)=1-(1/2)²-(1/2)²=0.5Gini=8/10×0.375+2/10×0.5=0.4Gini(t1)=1-(3/6)²-(3/6)²=0.5Gini(t2)=1-(4/4)²-(0/4)²=0Gini=6/10×0.5+4/10×0=0.3Gini(t1)=1-(5/6)²-(1/6)²=0.2778Gini(t2)=1-(2/4)²-(2/4)²=0.5Gini=6/10×0.2778+4/10×0.5=0.36760707585909510012012522055657280879297110122172230≤≤≤≤≤≤≤≤≤≤≤030303031221303030303007162534343434435261700.4200.4000.3750.3430.4170.4000.3000.3430.3750.4000.420是否Gini拖欠贷款者=否拖欠贷款者=否拖欠贷款者=否拖欠贷款者=是有房者婚姻状况拖欠贷款者=否拖欠贷款者=否有房者年收入是是否否单身离异已婚80K≥80K拖欠贷款者=否拖欠贷款者=否有房者婚姻状况是否单身离异已婚婚姻状况年收入CHAID算法CHAID(卡方自动交互检测)，是一种用卡方统计，以确定最佳的分割，建立多分枝决策树的分类方法。CHAID提供了一种在多个自变量中自动搜索能产生最大差异的变量方案。它以因变量为根结点，对每个自变量（只能是分类或有序变量，也就是离散性的，如果是连续变量，如年龄，收入要定义成分类或有序变量）进行分类，计算分类的卡方值。如果几个变量的分类均显著，则比较这些分类的显著程度（P值的大小），然后选择最显著的分类法作为子节点。CHAID算法实例本案例是一个医学心脏病综合诊断报告案例，现有数据OVERALL_DI