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

《《判定树学习算法I》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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医疗数据例将上表数据提供给决策树软件，可产生以下决策树血压药物A药物B药物A药物B高正常低不超过40岁大于40岁年龄构造分类树：ID3算法1、试探性地选择一个属性放在根节点

2、，对该属性的每个节点产生一个分枝。从而分裂根节点上的数据集，并移到子女节点，产生一棵局部树。2、根据局部树的质量，选择一棵局部树。3、对选定的局部树的每个子女节点重复上述步骤。4、如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。序号天气气温湿度有风打网球1晴热高无NO2晴热高有NO3多云热高无YES4雨温暖高无YES5雨凉爽正常无YES6雨凉爽正常有NO7多云凉爽正常有YES8晴温暖高无NO9晴凉爽正常无YES10雨温暖正常无YES11晴温暖正常有YES12多云温暖高有YES13多云垫正常无YES14雨温暖高有NO

3、气象状况与是否打网球这关系数据集实例分析天气状况有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:y

4、es6: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的数据点一样多，信息熵最大。数据的信息度量和信息熵的计算例如,其中是的归一化。信息值的计算训练样本在包含9个YES和5个NO的根节点上，信息值为Info([9,5])=0.940位局部树(a),在叶节点上Y

5、ES和No的个数分别是[2,3],[4,0],和[3,2],信息值分别是Info([2,3])=0.971位Info([4,0])=0位Info([3,2])=0.971位平均信息值为位局部树(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

6、.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

7、: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理想的情况下，当叶节点包含的实例具有相同的类时分枝过程

8、终止。但可能无法达到这种结果。当数据不能进一步划分时，停止划分过程。Gain(有风)=0.020位天气为雨时所达到的节点上的可能深一层的分枝：天气晴多云雨1:no2:no8:no9:yes11:yes3:yes7:yes12:yes13:yes4:yes5:yes6:no10