基于決策樹(shù)驗(yàn)證的屬性約簡(jiǎn)方法

蔡揚(yáng)　付小斌

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

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

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

1 屬性約簡(jiǎn)方案

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

有屬性a0 ～ a9

1） 對(duì)屬性，屬性值進(jìn)行編碼；

2） 屬性a0，和屬性是a1進(jìn)行融合，得到融合后的新屬性；

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

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

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

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

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

2 實(shí)驗(yàn)

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7] 陸光，李想，王彪一種有效的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)與現(xiàn)代化，2013，1（8）：68-72.

[8] 李四海， 張忠文. WEKA中的Id3決策樹(shù)算法[J].長(zhǎng)春大學(xué)學(xué)報(bào)， 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