资源描述：
《决策树算法的研究与改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、决策树算法的研究与改进第46卷・・第4期厦门大学学报（自然科学版）Vol.46.・No.4..2007年7月JournalofXiamenUniversity（NaturalScienee）Jul.2007..决策树算法的研究与改进冯少荣*（华南理工大学计算机科学与工程学院，广东广州510641）••••收稿口期：2006..06..01基金项目：福建省自然科学基金（A0310008）,福建省高新技术研究开放计划重点项目（2003H043）资助*现工作单位：厦门大学计算机科学系Email:sha
2、orong@xmu.edu.on摘要：决策树是数据挖掘中重要的分类方法，本文在研究和比较几种经典的决策树算法基础上，提出了一种改进的决策树算法：基于度量的决策树（MBDT）・这种决策树实际上是把线性分类器和决策树结合在一起.实验证明，用该方法构造的决策树能有效地减少决策树的层数，从而提高决策树的分类效率.通过MBDT分类实验，验证了上而结论的正确性和有效性.关键词：决策树；度量；ID3算法；嫡中图分类号：TP18文献标识码：A文章编号：0438..0479（2007）04..0496..05・・
3、・・决策树（DecisionTree）是用于分类和预测的主要技术，它着眼于从一组无规则的事例推理出决策树表示形式的分类规则，采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同属性判断从该节点向下分支，在决策树的叶节点得到结论.因此，从根节点到叶节点就对应着一条合理规则，整棵树就对应着一组表达式规则.基于决策树算法的一个最大的优点是它在学习过程中不需要使用者了解很多背景知识，只要训练事例能够用属性即结论的方式表达出来，就能使用该算法进行学习.基于决策树的分类模型有如下几个特点：
4、(1)决策树方法结构简单，便于理解；(2)决策树模型效率高，对训练集数据量较大的情况较为适合；(3)决策树方法通常不需要接受训练集数据外的知识；(4)决策树方法具有较高的分类精确度.近年来，决策树方法在机器学习、知识发现等领域得到了广泛应用.到目前为止国内外的研究人员先后提岀了十儿种与决策树相关的分类方法[1-11],对分类问题给出了程度不同的解决方案，但都存在一定程度的不足.1・・儿种经典的决策树算法简述1.1..ID3(IterativeDichotomizer3)算法[2]ID3是一种经典
5、的决策树算法，它从根节点开始，根节点被赋予一个最好的属性.随后对该属性的每个取值都生成相应的分支，在每个分支上又生成新的节点.对于最好的属性的选择标准，ID3采用基于信息燔定义的信息增益来选择内节点的测试属性，慵(Entro・・py)刻画了任意样本集的纯度.设S是n个数据样本的集合，将样本集划分为c个不同的类Ci(1=1,2,・・，c),每个类Ci含有的样本数冃为ni,则S划分为c个类的信息炳或期望信息，有E(S)二ci二1pilog2(pi),其中Pi为S中样木属于第i类Ci的概率，即pi二假
6、设属性A的所有不同值的集合为XA,Sv是S中属性A的值为v的样本子集，即Sv二{s!S
7、A(s)=v},在选择属性A后的每一个分支节点上，对该节点的样本集Sv分类的嫡为E(Sv)•选择A导致的期望爛定义为每个了集Sv的嫡的加权和，权值为属于Sv的样本占原始样本S的比例丨SV
8、S,即期望爛为E(S,A)二v!XAE(Sv),其中，E(Sv)是将Sv中的样本划分到c个类的信息爛.属性A相对样本集合S的信息增益Gain(S,A)定义为Gain(S,A)二E(S)-E(S,A),其中Gain(S,A)是
9、指因知道属性A的值后导致的爛的期望压缩.Gain(S,A)越大，说明选择测试属性A对分类提供的信息越多・ID3算法就是将每个节点选择信息增益Gain(S,A)最大的属性作为测试属性.ID3算法的局限是它的属性只能取离散值，为了使决策树能应用于连续属性值，Quinlan给出了ID3的一个扩展算法，即C4.5算法.1.2..C4.5算法[4]C4・5算法是ID3的改进，其中属性的选择依据同ID3.它对于实值变量的处理与下节论述的CART(ClassificationAndRegressionTree
10、s)算法一致，采用多重分支.C4.5算法能实现基于规则的剪枝.因为算法生成的每个叶子都和一条规则相关联，这个规则可以从树的根节点直到叶节点的路径上以逻辑合取式的形式读岀.1.3・・CART算法[1]决策树的分类过程就是把训练集划分为越来越小的了集的过程.理想的结果是决策树的叶子节点的样本都有同类标记.如果是这样，显然决策树的分支应该停止了，因为所有的类别己经被分开了.但是，一般情况下，很难一步就达到目标，所以，如果不止一步才能结束的话，这个分类的过程就是一个递归树的生长过程，CART是仅有的一种
