判定树学习算法ID3-文档资料

决策树：分类和回归树Breiman在20世纪80年代早期创造了该术语。该技术在医疗、市场调查统计、营销和顾客关系等方面得到了很好的应用。分类树是使用树结构算法将数据分成离散类的方法。性别年龄血压药物1男20正常A2女73正常B3男37高A4男33低B5女48高A6男29正常A7女52正常B8男42低B9男61正常B10女30正常A11女26低B12男54高A医疗数据例将上表数据提供给决策树软件，可产生以下决策树血压药物A药物B药物A药物B高正常低不超过40岁大于40岁年龄构造分类树：ID3算法1、试探性地选择一个属性放在根节点，对该属性的每个节点产生一个分枝。从而分裂根节点上的数据集，并移到子女节点，产生一棵局部树。2、根据局部树的质量，选择一棵局部树。3、对选定的局部树的每个子女节点重复上述步骤。4、如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。序号天气气温湿度有风打网球1晴热高无NO2晴热高有NO3多云热高无YES4雨温暖高无YES5雨凉爽正常无YES6雨凉爽正常有NO7多云凉爽正常有YES8晴温暖高无NO9晴凉爽正常无YES10雨温暖正常无YES11晴温暖正常有YES12多云温暖高有YES13多云垫正常无YES14雨温暖高有NO气象状况与是否打网球这关系数据集实例分析天气状况有4种属性，因此有4棵可能的局部树：气温热温暖凉爽1:no2:no8:yes13:yes4:yes8:no10:yes11:yes12:yes14:yes5:yes6:no7:yes9:yes(b)有风FalseTrue1:yes3:no4:yes5:yes8:yes9:no10:yes13:yes2:no6:no7:yes11:yes12:yes14:no(c)天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:yes10:no14:no(a)湿度高正常1:no2:no3:yes4:yes8:no12:yes14:no5:yes6:no7:yes9:yes10:yes11:yes13:yes(d)选取信息熵最小的局部树作为决策树的顶层。节点的的信息熵：若节点仅包含Yes或仅包含No的数据点，信息熵为0;若节点包含Yes和No的数据点一样多，信息熵最大。数据的信息度量和信息熵的计算n12n12ni2ii1info([C,C,...,C])entropy(p,p,...,p)plogp例如222234223344info([2,3,4])entropy(,,)log()log()log()999999999,其中nii1p11,2npp,...,p是12nC,C,...,C的归一化。信息值的计算训练样本在包含9个YES和5个NO的根节点上，信息值为Info([9,5])=0.940位局部树(a),在叶节点上YES和No的个数分别是[2,3],[4,0],和[3,2],信息值分别是Info([2,3])=0.971位Info([4,0])=0位Info([3,2])=0.971位平均信息值为222222info([2,3],[4,0],[3,2])5223344400[loglog][loglog]14555514444453322[loglog]1455550.693位局部树(a)导致的信息增益为Gain(天气)=info([9,5])-info([2,3],[4,0],[3,2])=0.940-0.693=0.247位它可以解释在“天气”属性上创建分枝的信息值。用同样的方法计算局部树(b),(c),(d)的信息值，并计算信息增益Gain(气温)=0.029位Gain(湿度)=0.152位Gain(有风)=0.048位局部树(a)导致的信息增益最大，故选择天气作为根节点的划分属性。天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no(a)继续递归地选择。天气为晴时所达到的节点上的可能深一层的分枝：天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no(e)气温1:No2:No8:No9:yes11:Yes热温暖凉爽天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no(f)湿度1:No2:No8:No9:yes11:yes高正常Gain(气温)=0.571位Gain(湿度)=0.971位天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:No10:yes14:no(g)有风1:No8:No9:Yes2:No11:yesFalseTrue理想的情况下，当叶节点包含的实例具有相同的类时分枝过程终止。但可能无法达到这种结果。当数据不能进一步划分时，停止划分过程。Gain(有风)=0.020位天气为雨时所达到的节点上的可能深一层的分枝：天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no(h)湿度高正常4:yes14:no5:yes6:no10:yes天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no(i)气温热温暖凉爽4:yes10:yes14:no5:yes6:no天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no(j)有风FalseTrue4:yes5:yes10:yes6:no14:no天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10:yes14:no湿度1:No2:No8:No9:yes11:yes高正常有风FalseTrue4:yes5:yes10:yes6:no14:no最终决策树作业：假定你是学院的篮球队队长，根据下表给出的记录，设计一种赢得下场比赛的策略。地点时间Sachin首发Girish进攻Girish防御对手中锋结果学院7pm是中锋前锋高赢学院7pm是前锋中锋矮赢大学7pm是前锋前锋高赢大学9pm是前锋前锋矮输学院7pm是中锋中锋高赢大学7pm是中锋中锋矮赢大学9pm是中锋前锋矮输学院7pm是中锋中锋矮赢学院7pm是中锋前锋矮赢学院7pm是中锋前锋高赢名称体温表皮覆盖胎生产蛋能飞水生有腿冬眠类标记人恒温毛发是否否否是否哺乳类巨蟒冷血鳞片否是否否否是爬行类鲑鱼冷血鳞片否是否是否否鱼类鲸恒温毛发是否否是否否哺乳类蛙冷血无否是否有时是是两栖类巨蜥冷血鳞片否是否否否否爬行类蝙蝠恒温毛发是否是否是是哺乳类鸽子恒温羽毛否是是否是否鸟类猫恒温皮是否否否是否哺乳类豹纹鲨冷血鳞片是否否是否否鱼类海龟冷血鳞片否是否有时是否爬行企鹅恒温羽毛否是否有时是否鸟类豪猪恒温刚毛是否否否是是哺乳类鳗冷血鳞片否是否是否否鱼类蝾螈冷血无否是否有时是是两栖类练习：对下表数据，使用ID3算法构造决策树。参考文献：数据挖掘基础教程原书名：InsightintoDataMining:TheoryandPractice原出版社：Prentice-HallofIndiaPvt.Ltd作者：(印度)K.P.SomanShyamDiwakarV.Ajay译者：范明;牛常勇丛书名：计算机科学丛书出版社：机械工业出版社ISBN：9787111255437出版日期：2009年1月开本：16开页码：305版次：1-1