决策树是一种直观的知识表示方法,由决策树导出的决策规则简单而易于理解.决策树学习目前已被作为一种重要的机器学习方法而被广泛使用,它主要用于概念学习及归纳推理.决策树学习就是一个决策树的构造过程,其基本思想为:自顶向下构造决策树,树的每个非叶结点表示一个属性,从该结点发出的每个分支对应于该属性的一个取值,这样每个样本实例根据其属性值最终在叶结点被决策树分类. 决策树分类的质量取决于叶结点的数量和叶结点的深度,根据Occam剃刀原理,生成的决策树包含的叶结点数越少且每个叶结点的深度越浅,则该决策树的质量越高.因而构造最优决策树是决策树学习算法研究的主要方向,然而这已被证明是一个NP-hard问题.本质上,构造决策树的过程就是一个选择非叶结点属性的过程.因而不同的属性选择标准构成了不同的决策树学习算法.具有较大影响的由Quinlan提出的ID3算法使用信息增益作为选择非叶结点属性的标准.ID3算法在决策树上的每个非叶结点只选择单个属性,且对属性间的相关性考虑不够,因而容易导致决策树中子树的重复和某些属性在同一决策树上被多次选择.为此,许多学者提出了不同的决策树学习算法.特别地,应用粗糙集理论构造属性选择的启发式函数来建造决策树已被许多作者所研究[6～9].本文对此进行了进一步的研究。