陶道强，马良荔＋，彭 超

（1.海军工程大学 计算机工程系，湖北 武汉430033；2.海军工程大学 校务部，湖北 武汉430033）

0 引 言

分类分析是数据挖掘中的一项重要任务，具有广泛的应用领域［1－2］。分类的关键在于如何构建分类模型，不同分类方法的选择导致分类结果的各异，其中的一种特别有效的方法是决策树算法［3］。决策树以其结构简单，便于理解，模型效率和分类精度高，分类速度快的优点不断的应用到许多规则的提取方法中［4－5］，许多人也不断的改进决策树算法，从而在很多方面得到更好的应用，比如ID3算法的改进［6－7］。

ID3算法是决策树算法中最为典型的算法，于1986年由Quinlan提出。该算法采用自顶向下的策略，搜索全部空间的一部分，确保所做的测试次数较少，但是ID3算法也存在着不足［7－8］：

（1）这种基于信息熵的计算方法容易产生多值偏向问题，即偏向于选择属性取值较多的非类别属性，而属性值较多的非类别属性并不总是最优的；

（2）数据集越大，非类别属性越多，需要的计算时间就会急剧增加。

（3）ID3算法对噪声比较敏感。

1 基本概念

1.1 ID3算法理论基础

Quinlan把Shannon的信息论引入到了决策树算法中，并依据信息熵对训练集进行分类。关于信息熵的定义［9］如下：

定义1 若给定的概率分布P＝（p1，p2，…，pn），则由该分布传递的信息量称为P的熵，即

定义2 若一个记录的集合T根据类别属性的值分成互相独立的类C1，C2，…，Cn，其概率分布为P，定义T的一个元素属于那个类所需要的信息量为

定义3 若属性X的值将T 分为集合T1，T2，…，Tn，则确定T中的一……