分层决策树课件.ppt

《分层决策树课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于层次分解思想的决策树2015.04.09分层思想的提出ID3算法典型的基于自顶向下的贪婪算法在每个节点找到局部最优的属性进行扩展，需要更多的附加节点针对多分类问题，ID3算法不容易处理分层思想的提出分层思想解决多类问题的手段是把一个多类问题转为两类问题。这种方法首先通过选择相关程度最大的属性一值对(它尽可能把多个类清晰分割为正、反两大类)把训练集中的多个类转换成正(Y)和反(N)两类，用ID3方法产生第一级决策树。把经过第一层划分后得到的正、反两大类数据集分别在细分为子的正、反两类来产生第二级决策树。对第二级决

2、策树得到的每个子正、反类在重复上述操作，直到把原训练集中所有类分清；最后将各层决策树转化为一组规则。实例基于分层思想生成决策树基于层次分解思想的决策树生成过程从所给例子中选出训练集。对每个属性考察它是否能把多个类分割为正、反两大类:若某些属性能分割，计算由此属性把原数据集转化为正、反两大类后根节点的嫡值，选取分割类后根属性所获得熵最小的属性分割标准作为当前层的最终分割结果，把多类转化为正、反两类。若所有属性都不能分割，则使用经典ID3方法直接产生决策树。用ID3方法产生当前层决策树。分别对所得到的正、反两类递归调用

3、该过程。把每层产生的决策树转化为相应的一组规则。原理的区别算法Step1:统计当前属性下的每个分支所含的类,每个类包含的例子个数Step2:给定阈值k1，对各分支中统计的每个类个数进行如下操作若此分支中的某个类的数据个数在这个类所含全部数据的概率小于给定阈值k1，则此分支中对应类的例子个数可忽略。(k1值随数据库不同而进行调整，通常取值小于0.1)Step3:计算每个类与其他类在每个分支中重叠个数之和占此类中总个数的比例。统计出各个类之间的重叠程度。Step4:判断每个类与其他类重叠程度如果某个或某几个类与其他类的

4、重叠程度接近0，则这个或者这几个类为正类，其他类为反类，得到当前测试属性分割结果否则给定阈值k2，如果两个类的重叠程度都大于给定阈值k2，则这些大于闭值的类组合在一起。考虑剩余的类，分别把剩余的类放入交叠程度大于k2的类组合中，否则，把剩余的类组合在一起，最终转化为正、反两类。(k2值随数据库不同而进行调整，通常取值大于0.8)Car数据集(对于属性A6)交叠程度的计算unacc与acc的交叠程度355/(355+277+576)+277/(355+277+576)=0.523unacc与vgood的交叠程度277

5、/(355+277+576)=0.229unacc与good的交叠程度355/(355+277+576)+277/(355+277+576)=0.523acc与unacc的交叠程度180/(180+204)+204/(180+204)=1acc与vgood的交叠程度204/(180+204)=0.531交叠程度矩阵划分为两类unacc为正类，其他为负类计算信息熵：此时根属性A6分割训练后的信息熵为0.4526Thanks