摘要：该文提出了一种将粗糙集理论和C4.5决策树算法结合在一起的一种改进算法。该算法利用粗糙集理论中的属性的约简功能首先将初始数据进行规约，然后再将规约后的数据作为C4.5的输入进而构造出决策树。通过粗糙集的属性约简，提高了训练数据表达的清晰度，也降低了无关属性对构造决策树的影响，从而减小了决策树的大小，提高了效率，同时也提高了结果的准确率。
关键词：粗糙集；属性约简；决策树；C4.5
中图分类号：TP312文献标识码：A文章编号：1009-3044(2012)16-3782-04
Research of an Optimized C4.5 Algorithm Based on Rough Theory
XIANG Zhuo-yuan, ZHANG Lei
(Information and Safety Engineering Department, Zhongnan University of Economics and Law,Wuhan 430081,China)
Abstract: This paper proposes an improved algorithm based on the rough set theory and C4.5 decision tree. The algorithm uses rough set theory to reduce the attributes in the decision system, and uses the reduced data as the input of C4.5 algorithm to construct a decision tree. The new algorithm improves the clarity of training data, and also reduces the influence of irrelevant attributes, therefore, the size of deci sion tree can be reduced and the accuracy of the result can be improved.
Key words: data mining; rough set; reduce attributes; decision tree; C4.5
决策树分类技术在数据挖掘中应用广泛，有分类效率高、速度快、理解性好等特点，并在数据挖掘、机器学习、人工智能等领域被广泛地应用。决策树算法有很多种，如ID3算法、C4.5算法、CARPT算法、CHAID算法、PUBLIC算法、SLIQ算法以及SPRLN算法[1]。C4.5算法是在ID3算法基础上改进的决策树生成算法，它除了拥有ID3算法的功能外，还新增了一下功能：利用信息增益率来创建分枝；具有处理连续属性值的能力；可以处理缺少属性值的训练样本；通过使用不同的修建技术以避免树的不平衡；以及K次迭代交叉验证。因此C4.5算法凭借其独特的特点和突触的优势在各行各业的数据挖掘中得到了成功的应用。
但是C4.5算法仍然存在一些不足，C4.5评价决策最主要的依据是决策树的错误率，对树的深度、节点的个数等并没有进行考虑，而树的平均深度直接对应着决策树的预测速度，树的节点个数则代表树的规模[2]。特别是在现实数据中，决策表中的条件属性往往存在很多与决策属性关联性很小甚至毫无关联的冗余属性，利用C4.5算法构造出的决策树往往比较庞大，节点较多，且存在很多无义分支。因此该文提出一种将粗糙集理论与C4.5相结合的算法，利用粗糙集理论中的约简算法先将冗余属性去掉，筛选出与决策属性关联性强的条件属性，再将筛选后的样本信息提供给决策树算法进行训练以及分类，以减小树的规模，提高效率和准确率。
changes_in_node = lacunar
| no_of_nodes_in <= 2: metastases (21.0/7.0)
| no_of_nodes_in > 2: malign_lymph (21.0/4.0)
changes_in_node = lac_margin
| block_of_affere = no
| | special_forms = no: metastases (3.0)
| | special_forms = chalices
| | | dislocation_of = no: metastases (2.0)
| | | dislocation_of = yes: malign_lymph (3.0/1.0)
| | special_forms = vesicles
| | | dislocation_of = no: metastases (6.0/2.0)
| | | dislocation_of = yes: malign_lymph (5.0)
| block_of_affere = yes: metastases (56.0/3.0)
changes_in_node = lac_central
| no_of_nodes_in <= 1
| | block_of_affere = no: malign_lymph (3.0)
| | block_of_affere = yes: metastases (2.0)
| no_of_nodes_in > 1: malign_lymph (20.0)
6）分析比较只用C4.5算法得到的决策树和利用粗糙集与C4.5结合后的算法得到的结果：
表1两种算法结果比较
以上比较结果显示，改进后的算法得到的决策树属性数量由19变为7，减少了63.2%；叶节点个数由21变为13，减少了38.1%；树的规模由34减小到22，减少了35.3%；树的深度由7变为5，减少了28.6%；分类的正确率由79.5455 %变为81.8182 %，增加了2.27%。由此可以看出利用粗糙集和C4.5结合后的算法使得决策树得到了大大简化，提高了效率，同时准确率也有所提高。
该文提出将粗糙集理论与决策树相结合的思想，利用粗糙集理论将决策表中的条件属性进行过滤，去掉大量冗余属性从而筛选出对据测属性影响比较大的那部分属性，得到约简后的结果再作为C4.5算法的输入进行计算，最终得到决策树。通过实验数据证明加入粗糙集理论的筛选后，最终的到决策树更加简洁，准确率更高，也更符合实际情况。并且在实际的数据中，噪声无处不在，决策系统中可能会存在大量无关的冗余属性，这时利用粗糙集与决策树相结合的算法的效果会显得明显。
[1]朱玉权.数据挖掘技术[M].南京:东南大学出版社,2006.
[2]李瑞,魏现梅,黄明,等.一种改进的决策树学习算法[M].北京:科学技术与工程,2009.
[3] Han Jiawei,Kamaber M.数据挖掘与数学建模[M].范明,孟小峰,译.北京:机械工业出版社,2005.
[4]蒋良孝,蔡之华,刘钊.一种基于粗糙集的决策规则挖掘算法[J].微机与应用,2004(3).