文档介绍：决策树算法的研究与改进第 46卷..第4 期厦门大学学报( 自然科学版) Vol. 46.. No. 4 .. 2007 年7月 Journal of Xiamen U niversity ( Natural Science) Jul. 2007.. 决策树算法的研究与改进冯少荣*( 华南理工大学计算机科学与工程学院, 广东广州 510641) .. .. 收稿日期: 2006..06..01 基金项目: 福建省自然科学基金( A0310008) , 福建省高新技术研究开放计划重点项目( 2003H043) 资助* 现工作单位: 厦门大学计算机科学系 Email : shaorong@ xmu. edu. cn 摘要: 决策树是数据挖掘中重要的分类方法, 本文在研究和比较几种经典的决策树算法基础上, 提出了一种改进的决策树算法: 基于度量的决策树( MBDT ). 这种决策树实际上是把线性分类器和决策树结合在一起. 实验证明, 用该方法构造的决策树能有效地减少决策树的层数, 从而提高决策树的分类效率. 通过 M BDT 分类实验, 验证了上面结论的正确性和有效性. 关键词: 决策树; 度量; ID3 算法;熵中图分类号:TP 18 .. .. .. .. .. 文献标识码: A.. .. .. .. .. 文章编号: 0438..0479( 2007) 04..0496..05 .. .. 决策树( Decision T ree) 是用于分类和预测的主要技术, 它着眼于从一组无规则的事例推理出决策树表示形式的分类规则, 采用自顶向下的递归方式, 在决策树的内部节点进行属性值的比较, 并根据不同属性判断从该节点向下分支, , 从根节点到叶节点就对应着一条合理规则, 整棵树就对应着一组表达式规则. 基于决策树算法的一个最大的优点是它在学****过程中不需要使用者了解很多背假设属性 A 的所有不同值的集合为 XA, Sv是S中属性 A 的值为 v 的样本子集,即 Sv={s!S∣A( s) = v}, 在选择属性 A 后的每一个分支节点上, 对该节点的样本集 Sv 分类的熵为 E(Sv). 选择 A 导致的期望熵定义为每个子集 Sv 的熵的加权和, 权值为属于 Sv的样本占原始样本 S 的比例|Sv| |S|, 即期望熵为 E( S, A)=v!XA|Sv||S| E(Sv), 其中, E( Sv) 是将 Sv 中的样本划分到 c 个类的信息熵. 属性 A 相对样本集合 S 的信息增益 Gain( S,A) 定义为 Gain( S,A)= E( S)-E( S, A), 其中 Gain( S,A) 是指因知道属性 A 的值后导致的熵的期望压缩. Gain( S,A) 越大, 说明选择测试属性 A对分类提供的信息越多. ID3 算法就是将每个节点选择信息增益 Gain( S,A) 最大的属性作为测试属性. ID3 算法的局限是它的属性只能取离散值, 为了使决策树能应用于连续属性值, Quinlan 给出了 ID3 的一个扩展算法,即 C4. 5 算法. .. C4. 5 算法[ 4] 然, 从叶节点开始剪枝并非必要. 基于不纯度增长的判断标准, 可以从任何节点开始剪枝. 剪枝技术的一个缺陷是, 如果样本数很大的话,则计算量代价会非常高, 甚至无法实现. 不过, 在一般的情况下, 剪枝的方法优于上一节提到的分支停止方法. 2 .. 改进的决策树算法(Metric Based Decision Tree, MBDT) 第4期.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..冯少荣: 决策树算法的研究与改进% 497 %