基于决策树验证的属性约简方法

蔡扬　付小斌

摘要：属性约简能够有效地减少冗余，同时，通过约简去除对预测结果贡献极小的属性能够有效地提高分类精度。提出了一种属性约简方法，该方法在分类前对现有的属性进行编码、融合，再通过设置阈值筛选融合后的属性，从而减少低价值属性的数量，最后利用ID3、C4.5算法对比和测试，结果证明提出的方法从根本上优化了数据，提高了分类精度。

关键词：属性约简；编码；融合；ID3算法；C4.5算法

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2018）02-0238-02

Attribute Reduction Method Based on Decision Tree Validation

CAI Yang，FU Xiao-bin

（Southwest Petroleum University， School of Computer Science， Chengdu 610500， China）

Abstract：Attribute reduction can effectively reduce the number of redundant data， by reducing the contribution of the prediction results to a minimum， this can effectively improve the classification accuracy. In this paper， a method of attribute reduction is proposed， which encodes and merges the existing attributes before classification， and then filters the merged attributes by setting thresholds to reduce the number of low-value attributes. Finally， using ID3， C4.5 Algorithm test results show that the proposed method fundamentally optimized the data， improve the classification accuracy.

Key words： Attribute reduction； Coding；Fusion；ID3 Algorithm； C4.5 Algorithm

当代社会处于信息爆炸时代，大量的数据每天冲击着人们的生活。在生活中的每一件事，都包含有多样的属性，在繁多的属性中怎么去选择对人们最有利的属性，并且通过这些属性使人们对某一事件做出更好的决策方案或做出更为精准的预测，意义明显。

1 属性约简方案

常见的属性约简方法计算复杂，公式繁多，虽然约简效果较为优秀，但不易理解及使用。本文提出的属性约简方法是通过属性之间的融合筛减从而进行约简，该方法的基本过程如下：

有属性a0 ～ a9

1） 对属性，属性值进行编码；

2） 属性a0，和属性是a1进行融合，得到融合后的新属性；

3） 通过阈值删除部分融合后的属性；

4） 调用ID3算法做多次测试，选择分类精度最好的阈值；

假设表1中{A0，A1，A2，A3}是一个简单的数据集，对属性编码为{A0（00），A1（01），A2（02），A3（03）}，表中即为属性之间融合的编码[1，2，3，9]。

为更好的解释属性融合，则假设有两组属性，身高和体重。身高有高（H）、中等（N）、矮（S），体重有重（F）、正常（N）、瘦（T）。要身高体重属性进行融合、约简则如图1：

融合后的属性将置于所有属性的最后，不再进行二次融合。

2 实验

实验中涉及的数据集，为标准UCI数据集。多组数据集进行测试，每组数据集中进行多次的属性融合，不同的阈值产生不同的结果，使用ID3算法对不同阈值下产生的结果做分类测试，并从中选取最优结果[4，5，7，8，10，11]。

以下的实验都是多次实验取平均值得出的结果，在测试时训练集，测试集所占的比例设置为70%和30%，实验结果均保留小数点后三位。实验中阈值的设置不宜过大，设置过大则会将多数的融合数据删除，许多重要的融合属性值将会被筛除，这样操作将会直接导致精度降低。因此，在设置阈值时将会选择0.5以下的数值进行测试，所选取的阈值为{0.1 ， 0.2 ， 0.3 ， 0.4， 0.5}。

由图2表易得，当阈值设置在0.3时zoo数据集可以获得相对最优解，多次实验平均精度约为98.3%。当阈值设置为0.5时虽然精度有回升的迹象，但是为了属性不会被删除太多，所以本次实验不会再去测试是否精度会继续提升。

由图表易知，當阈值为0.3时，Breast-cancer数据集将会获得局部最优解，精度约为85.2% 。

在voting数据集中，实验结果基本持平。当阈值设置为0.4时精度最大，约为97.4%。

在三次的试验中，zoo和voting这两组数据集基本是符合预期的，但是在breast-cancer数据集的测试中就有了一些跳跃，这样的结果很可能是试验次数太少导致的，毕竟十次的实验并不能最好地反映出结果。若想要最接近真实的预测精度，就要进行更多次的实验。

实验结果表明，在选定的三组数据集中经过属性约简后使用ID3算法进行分类，分类精度会有一定的提升。

3 结论

本文提出了一种属性约简方法，在该方法的基础上使用ID3算法和C4.5算法对数据进行分类，分类结果要优于原始数据集的分类结果。证明本文的方法是有效的，可行的。

参考文献：

[1] Bruce Eckel.Java 编程思想[M]. 陈昊鹏，译. 4 版.北京：机械工业出版社，2007：285-376.

[2] Cay S. Horstmann、Gary Cornell. Java 核心技术卷Ⅰ基础知识 [M]. 周立新，陈波，叶乃文，等，译. 9 版.北京：机械工业出版社，2013：1-274.

[3] 严蔚敏，吴伟民. 数据结构（C 语言版）[M]. 北京：清华大学出版社，2007：44-152.

[4] 史忠植. 知识发现[ M]. 北京：清华大学出版社，2002：21-41.

[5] 曹宁，高莹，徐根祺.决策树方法的研究进展[J].科技视界，2014（20）：72-72.

[6] 王国胤. Rough集理论与知识获取[ M]. 西安：西安交通大学出版社，2001：23-152.

[7] 陆光，李想，王彪一种有效的属性约简算法[J].计算机与现代化，2013，1（8）：68-72.

[8] 李四海， 张忠文. WEKA中的Id3决策树算法[J].长春大学学报， 2011， 21（2）：67-69.

[9] Quinlan J R.Induction of decision trees[J].Machine Learning，1986，（4）：81-106.

[10] Yao Y Y， Zhao Y. Attribute reduction in decision-theoretic rough set models[J].Information Sciences， 2008， 178： 3356-3373.

[11] Li， H.， Zhou， X.： Risk decision making Based on decision-theoretic rough set： athree-way view decision model[J]. International Journal of Computational Intelligence Systems 4，2011：1-11.endprint