基于決策樹驗證的屬性約簡方法

蔡揚　付小斌

摘要：屬性約簡能夠有效地減少冗余，同時，通過約簡去除對預測結(jié)果貢獻極小的屬性能夠有效地提高分類精度。提出了一種屬性約簡方法，該方法在分類前對現(xiàn)有的屬性進行編碼、融合，再通過設(shè)置閾值篩選融合后的屬性，從而減少低價值屬性的數(shù)量，最后利用ID3、C4.5算法對比和測試，結(jié)果證明提出的方法從根本上優(yōu)化了數(shù)據(jù)，提高了分類精度。

關(guān)鍵詞：屬性約簡；編碼；融合；ID3算法；C4.5算法

中圖分類號：TP181 文獻標識碼：A 文章編號：1009-3044（2018）02-0238-02

Attribute Reduction Method Based on Decision Tree Validation

CAI Yang，F(xiàn)U 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

當代社會處于信息爆炸時代，大量的數(shù)據(jù)每天沖擊著人們的生活。在生活中的每一件事，都包含有多樣的屬性，在繁多的屬性中怎么去選擇對人們最有利的屬性，并且通過這些屬性使人們對某一事件做出更好的決策方案或做出更為精準的預測，意義明顯。

1 屬性約簡方案

常見的屬性約簡方法計算復雜，公式繁多，雖然約簡效果較為優(yōu)秀，但不易理解及使用。本文提出的屬性約簡方法是通過屬性之間的融合篩減從而進行約簡，該方法的基本過程如下：

有屬性a0 ～ a9

1） 對屬性，屬性值進行編碼；

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

3） 通過閾值刪除部分融合后的屬性；

4） 調(diào)用ID3算法做多次測試，選擇分類精度最好的閾值；

假設(shè)表1中{A0，A1，A2，A3}是一個簡單的數(shù)據(jù)集，對屬性編碼為{A0（00），A1（01），A2（02），A3（03）}，表中即為屬性之間融合的編碼[1，2，3，9]。

為更好的解釋屬性融合，則假設(shè)有兩組屬性，身高和體重。身高有高（H）、中等（N）、矮（S），體重有重（F）、正常（N）、瘦（T）。要身高體重屬性進行融合、約簡則如圖1：

融合后的屬性將置于所有屬性的最后，不再進行二次融合。

2 實驗

實驗中涉及的數(shù)據(jù)集，為標準UCI數(shù)據(jù)集。多組數(shù)據(jù)集進行測試，每組數(shù)據(jù)集中進行多次的屬性融合，不同的閾值產(chǎn)生不同的結(jié)果，使用ID3算法對不同閾值下產(chǎn)生的結(jié)果做分類測試，并從中選取最優(yōu)結(jié)果[4，5，7，8，10，11]。

以下的實驗都是多次實驗取平均值得出的結(jié)果，在測試時訓練集，測試集所占的比例設(shè)置為70%和30%，實驗結(jié)果均保留小數(shù)點后三位。實驗中閾值的設(shè)置不宜過大，設(shè)置過大則會將多數(shù)的融合數(shù)據(jù)刪除，許多重要的融合屬性值將會被篩除，這樣操作將會直接導致精度降低。因此，在設(shè)置閾值時將會選擇0.5以下的數(shù)值進行測試，所選取的閾值為{0.1 ， 0.2 ， 0.3 ， 0.4， 0.5}。

由圖2表易得，當閾值設(shè)置在0.3時zoo數(shù)據(jù)集可以獲得相對最優(yōu)解，多次實驗平均精度約為98.3%。當閾值設(shè)置為0.5時雖然精度有回升的跡象，但是為了屬性不會被刪除太多，所以本次實驗不會再去測試是否精度會繼續(xù)提升。

由圖表易知，當閾值為0.3時，Breast-cancer數(shù)據(jù)集將會獲得局部最優(yōu)解，精度約為85.2% 。

在voting數(shù)據(jù)集中，實驗結(jié)果基本持平。當閾值設(shè)置為0.4時精度最大，約為97.4%。

在三次的試驗中，zoo和voting這兩組數(shù)據(jù)集基本是符合預期的，但是在breast-cancer數(shù)據(jù)集的測試中就有了一些跳躍，這樣的結(jié)果很可能是試驗次數(shù)太少導致的，畢竟十次的實驗并不能最好地反映出結(jié)果。若想要最接近真實的預測精度，就要進行更多次的實驗。

實驗結(jié)果表明，在選定的三組數(shù)據(jù)集中經(jīng)過屬性約簡后使用ID3算法進行分類，分類精度會有一定的提升。

3 結(jié)論

本文提出了一種屬性約簡方法，在該方法的基礎(chǔ)上使用ID3算法和C4.5算法對數(shù)據(jù)進行分類，分類結(jié)果要優(yōu)于原始數(shù)據(jù)集的分類結(jié)果。證明本文的方法是有效的，可行的。

參考文獻：

[1] Bruce Eckel.Java 編程思想[M]. 陳昊鵬，譯. 4 版.北京：機械工業(yè)出版社，2007：285-376.

[2] Cay S. Horstmann、Gary Cornell. Java 核心技術(shù)卷Ⅰ基礎(chǔ)知識 [M]. 周立新，陳波，葉乃文，等，譯. 9 版.北京：機械工業(yè)出版社，2013：1-274.

[3] 嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C 語言版）[M]. 北京：清華大學出版社，2007：44-152.

[4] 史忠植. 知識發(fā)現(xiàn)[ M]. 北京：清華大學出版社，2002：21-41.

[5] 曹寧，高瑩，徐根祺.決策樹方法的研究進展[J].科技視界，2014（20）：72-72.

[6] 王國胤. Rough集理論與知識獲取[ M]. 西安：西安交通大學出版社，2001：23-152.

[7] 陸光，李想，王彪一種有效的屬性約簡算法[J].計算機與現(xiàn)代化，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