《判定树学习算法I》PPT课件.ppt

《《判定树学习算法I》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《判定树学习算法I》PPT课件.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、决策树：分类和回归树决策树：分类和回归树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医疗

2、医疗数据数据例例将上表数据提供给决策树软件，可产生以下决策树将上表数据提供给决策树软件，可产生以下决策树血压血压药物药物A药物药物B药物药物A药物药物B高高正常正常低低不超过不超过40岁岁大于大于40岁岁年龄年龄构造分类树：构造分类树：ID3算法算法1、试探性地选择一个属性放在根节点，对该属性的每个节点、试探性地选择一个属性放在根节点，对该属性的每个节点产生一个分枝。从而分裂根节点上的数据集，并移到子女节点，产生一个分枝。从而分裂根节点上的数据集，并移到子女节点，产生一棵局部树。产生一棵局部树。2、根据局部树的质量，选择一棵局部树。、根据局部树的质量，选择一棵局部树。3、对选定的局部树的每个子

3、女节点重复上述步骤。、对选定的局部树的每个子女节点重复上述步骤。4、如果一个节点上的所有实例都具有相同的类，则停止局部、如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。树的生长。序号序号天气天气气温气温湿度湿度有风有风打网球打网球1晴晴热热高高无无NO2晴晴热热高高有有NO3多云多云热热高高无无YES4雨雨温暖温暖高高无无YES5雨雨凉爽凉爽正常正常无无YES 6雨雨凉爽凉爽正常正常有有NO7多云多云凉爽凉爽正常正常有有YES8晴晴温暖温暖高高无无NO9晴晴凉爽凉爽正常正常无无YES 10雨雨温暖温暖正常正常无无YES11晴晴温暖温暖正常正常有有YES12多云多云温暖温暖高高有有Y

4、ES13多云多云垫垫正常正常无无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)天气天气晴晴多云多云雨

5、雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:yes10:no14:no(a)湿度湿度高高正常正常1:no2:no3:yes4:yes8:no12:yes14:no5:yes 6:no7:yes9:yes10:yes11:yes13:yes(d)选取信息熵最小的局部树作为决策树的顶层。选取信息熵最小的局部树作为决策树的顶层。节点的的信息熵：节点的的信息熵：若节点仅包含若节点仅包含Yes 或仅包含或仅包含No的数据点，信息熵为的数据点，信息熵为0;若节点包含若节点包含Yes 和和No的数据点一样多，信息熵最大。的数据点一样多，

6、信息熵最大。数据的信息度量和信息熵的计算数据的信息度量和信息熵的计算例如例如,其中其中是是的归一化。的归一化。信息值的计算信息值的计算训练样本在包含训练样本在包含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 位位平均信息值为平均信息值为位位局部树局部树(a)导致的信息增益为导致的信息增益为Gain(天气天气)=in

7、fo(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:y

8、es7: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:no

9、10: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理想的情况下，当叶节点包含的实例具有相理想的情况下，当叶节点包含的实例具有相同的类时分枝过程终止。同的类时分枝过程终止。但可能无法达到这种结果。当数据不能进一步但可能无法达到这种结果。当数

10、据不能进一步划分时，停止划分过程。划分时，停止划分过程。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)气温气温

11、热热温暖温暖凉爽凉爽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:y

12、es6:no14:no最终决策树最终决策树作业：假定你是学院的篮球队队长，根据下表给出的记录，设计一作业：假定你是学院的篮球队队长，根据下表给出的记录，设计一种赢得下场比赛的策略。种赢得下场比赛的策略。地点时间Sachin首发Girish进攻Girish防御对手中锋结果学院7pm是中锋前锋高赢学院7pm是前锋中锋矮赢大学7pm是前锋前锋高赢大学9pm是前锋前锋矮输学院7pm是中锋中锋高赢大学7pm是中锋中锋矮赢大学9pm是中锋前锋矮输学院7pm是中锋中锋矮赢学院7pm是中锋前锋矮赢学院7pm是中锋前锋高赢名称名称体温体温表皮表皮覆盖覆盖胎生胎生产蛋产蛋能飞能飞水生水生有腿有腿冬眠冬眠类标记类标

13、记人人恒温恒温毛发毛发是是否否否否否否是是否否哺乳类哺乳类巨蟒巨蟒冷血冷血鳞片鳞片否否是是否否否否否否是是爬行类爬行类鲑鱼鲑鱼冷血冷血鳞片鳞片否否是是否否是是否否否否鱼类鱼类鲸鲸恒温恒温毛发毛发是是否否否否是是否否否否哺乳类哺乳类蛙蛙冷血冷血无无否否是是否否有时有时是是是是两栖类两栖类巨蜥巨蜥冷血冷血鳞片鳞片否否是是否否否否否否否否爬行类爬行类蝙蝠蝙蝠恒温恒温毛发毛发是是否否是是否否是是是是哺乳类哺乳类鸽子鸽子恒温恒温羽毛羽毛否否是是是是否否是是否否鸟类鸟类猫猫恒温恒温皮皮是是否否否否否否是是否否哺乳类哺乳类豹纹鲨豹纹鲨冷血冷血鳞片鳞片是是否否否否是是否否否否鱼类鱼类海龟海龟冷血冷血鳞片鳞片否

14、否是是否否有时有时是是否否爬行爬行企鹅企鹅恒温恒温羽毛羽毛否否是是否否有时有时是是否否鸟类鸟类豪猪豪猪恒温恒温刚毛刚毛是是否否否否否否是是是是哺乳类哺乳类鳗鳗冷血冷血鳞片鳞片否否是是否否是是否否否否鱼类鱼类蝾螈蝾螈冷血冷血无无否否是是否否有时有时是是是是两栖类两栖类练习：对下表数据，使用练习：对下表数据，使用ID3算法构造决策树。算法构造决策树。参考文献：参考文献：数据挖掘基础教程数据挖掘基础教程 原书名：原书名：Insight into Data Mining:Theory and Practice 原出版社：Prentice-HallofIndiaPvt.Ltd作者：(印度印度)K.P.Soman Shyam Diwakar V.Ajay 译者：范明;牛常勇丛书名：计算机科学丛书计算机科学丛书 出版社：机械工业出版社ISBN：9787111255437 出版日期：2009年1月开本：16开页码：305版次：1-1