文档介绍：第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 算法; 熵
中图分类号: T P 18 .. .. .. .. .. 文献标识码: A.. .. .. .. .. 文章编号: 0438..0479( 2007) 04..0496..05
.. .. 决策树( Decision T ree) 是用于分类和预测的主要
技术, 它着眼于从一组无规则的事例推理出决策树表
示形式的分类规则, 采用自顶向下的递归方式, 在决策
树的内部节点进行属性值的比较, 并根据不同属性判
断从该节点向下分支, 在决策树的叶节点得到结论. 因
此, 从根节点到叶节点就对应着一条合理规则, 整棵树
就对应着一组表达式规则. 基于决策树算法的一个最
大的优点是它在学****过程中不需要使用者了解很多背
景知识, 只要训练事例能够用属性即结论的方式表达
出来, 就能使用该算法进行学****br/>基于决策树的分类模型有如下几个特点:
( 1) 决策树方法结构简单, 便于理解; ( 2) 决策树模
型效率高, 对训练集数据量较大的情况较为适合; ( 3)
决策树方法通常不需要接受训练集数据外的知识; ( 4)
决策树方法具有较高的分类精确度.
近年来, 决策树方法在机器学****知识发现等领域
得到了广泛应用. 到目前为止国内外的研究人员先后
提出了十几种与决策树相关的分类方法[ 1- 1 1] , 对分类
问题给出了程度不同的解决方案, 但都存在一定程度
的不足.
.. 几种经典的决策树算法简述
1 .. ID3( Iterative Dichotomizer 3) 算法[2]
ID3 是一种经典的决策树算法, 它从根节点开始,
根节点被赋予一个最好的属性. 随后对该属性的每个
取值都生成相应的分支, 在每个分支上又生成新的节
点. 对于最好的属性的选择标准, ID3 采用基于信息熵
定义的信息增益来选择内节点的测试属性, 熵( Ent ro..
py) 刻画了任意样本集的纯度.
设S 是n 个数据样本的集合, 将样本集划分为c 个
不同的类Ci ( i = 1, 2, .., c) , 每个类Ci 含有的样本数
目为n i , 则S 划分为c 个类的信息熵或期望信息, 有
E( S) =
c
i = 1
p i log2 ( p i ) ,
其中p i 为S 中样本属于第i 类Ci 的概率, 即p i =
ni
n
.
假设属性A 的所有不同值的集合为X A , Sv 是S 中
属性A 的值为v 的样本子集, 即Sv = { s ! S ∣ A ( s)
= v} , 在选择属性A 后的每一个分支节点上, 对该节
点的样本集Sv 分类的熵为E ( S v ) . 选择A 导致的期望
熵定义为每个子集Sv 的熵的加权和, 权值为属于S v 的
样本占原始样本S 的比例| S v |
| S |
, 即期望熵为
E( S, A) = v ! X
A
| S v |
| S |
E( S v ) ,
其中, 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 算法就是将每个节点选择
信