向卓元 張蕾

摘要：該文提出了一種將粗糙集理論和C4.5決策樹(shù)算法結(jié)合在一起的一種改進(jìn)算法。該算法利用粗糙集理論中的屬性的約簡(jiǎn)功能首先將初始數(shù)據(jù)進(jìn)行規(guī)約，然后再將規(guī)約后的數(shù)據(jù)作為C4.5的輸入進(jìn)而構(gòu)造出決策樹(shù)。通過(guò)粗糙集的屬性約簡(jiǎn)，提高了訓(xùn)練數(shù)據(jù)表達(dá)的清晰度，也降低了無(wú)關(guān)屬性對(duì)構(gòu)造決策樹(shù)的影響，從而減小了決策樹(shù)的大小，提高了效率，同時(shí)也提高了結(jié)果的準(zhǔn)確率。

關(guān)鍵詞：粗糙集；屬性約簡(jiǎn)；決策樹(shù)；C4.5

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

決策樹(shù)分類技術(shù)在數(shù)據(jù)挖掘中應(yīng)用廣泛，有分類效率高、速度快、理解性好等特點(diǎn)，并在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域被廣泛地應(yīng)用。決策樹(shù)算法有很多種，如ID3算法、C4.5算法、CARPT算法、CHAID算法、PUBLIC算法、SLIQ算法以及SPRLN算法[1]。C4.5算法是在ID3算法基礎(chǔ)上改進(jìn)的決策樹(shù)生成算法，它除了擁有ID3算法的功能外，還新增了一下功能：利用信息增益率來(lái)創(chuàng)建分枝；具有處理連續(xù)屬性值的能力；可以處理缺少屬性值的訓(xùn)練樣本；通過(guò)使用不同的修建技術(shù)以避免樹(shù)的不平衡；以及K次迭代交叉驗(yàn)證。因此C4.5算法憑借其獨(dú)特的特點(diǎn)和突觸的優(yōu)勢(shì)在各行各業(yè)的數(shù)據(jù)挖掘中得到了成功的應(yīng)用。

但是C4.5算法仍然存在一些不足，C4.5評(píng)價(jià)決策最主要的依據(jù)是決策樹(shù)的錯(cuò)誤率，對(duì)樹(shù)的深度、節(jié)點(diǎn)的個(gè)數(shù)等并沒(méi)有進(jìn)行考慮，而樹(shù)的平均深度直接對(duì)應(yīng)著決策樹(shù)的預(yù)測(cè)速度，樹(shù)的節(jié)點(diǎn)個(gè)數(shù)則代表樹(shù)的規(guī)模[2]。特別是在現(xiàn)實(shí)數(shù)據(jù)中，決策表中的條件屬性往往存在很多與決策屬性關(guān)聯(lián)性很小甚至毫無(wú)關(guān)聯(lián)的冗余屬性，利用C4.5算法構(gòu)造出的決策樹(shù)往往比較龐大，節(jié)點(diǎn)較多，且存在很多無(wú)義分支。因此該文提出一種將粗糙集理論與C4.5相結(jié)合的算法，利用粗糙集理論中的約簡(jiǎn)算法先將冗余屬性去掉，篩選出與決策屬性關(guān)聯(lián)性強(qiáng)的條件屬性，再將篩選后的樣本信息提供給決策樹(shù)算法進(jìn)行訓(xùn)練以及分類，以減小樹(shù)的規(guī)模，提高效率和準(zhǔn)確率。

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算法得到的決策樹(shù)和利用粗糙集與C4.5結(jié)合后的算法得到的結(jié)果：

表1兩種算法結(jié)果比較

以上比較結(jié)果顯示，改進(jìn)后的算法得到的決策樹(shù)屬性數(shù)量由19變?yōu)?，減少了63.2%；葉節(jié)點(diǎn)個(gè)數(shù)由21變?yōu)?3，減少了38.1%；樹(shù)的規(guī)模由34減小到22，減少了35.3%；樹(shù)的深度由7變?yōu)?，減少了28.6%；分類的正確率由79.5455 %變?yōu)?1.8182 %，增加了2.27%。由此可以看出利用粗糙集和C4.5結(jié)合后的算法使得決策樹(shù)得到了大大簡(jiǎn)化，提高了效率，同時(shí)準(zhǔn)確率也有所提高。

該文提出將粗糙集理論與決策樹(shù)相結(jié)合的思想，利用粗糙集理論將決策表中的條件屬性進(jìn)行過(guò)濾，去掉大量冗余屬性從而篩選出對(duì)據(jù)測(cè)屬性影響比較大的那部分屬性，得到約簡(jiǎn)后的結(jié)果再作為C4.5算法的輸入進(jìn)行計(jì)算，最終得到?jīng)Q策樹(shù)。通過(guò)實(shí)驗(yàn)數(shù)據(jù)證明加入粗糙集理論的篩選后，最終的到?jīng)Q策樹(shù)更加簡(jiǎn)潔，準(zhǔn)確率更高，也更符合實(shí)際情況。并且在實(shí)際的數(shù)據(jù)中，噪聲無(wú)處不在，決策系統(tǒng)中可能會(huì)存在大量無(wú)關(guān)的冗余屬性，這時(shí)利用粗糙集與決策樹(shù)相結(jié)合的算法的效果會(huì)顯得明顯。

[1]朱玉權(quán).數(shù)據(jù)挖掘技術(shù)[M].南京:東南大學(xué)出版社,2006.

[2]李瑞,魏現(xiàn)梅,黃明,等.一種改進(jìn)的決策樹(shù)學(xué)習(xí)算法[M].北京:科學(xué)技術(shù)與工程,2009.

[3] Han Jiawei,Kamaber M.數(shù)據(jù)挖掘與數(shù)學(xué)建模[M].范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2005.

[4]蔣良孝,蔡之華,劉釗.一種基于粗糙集的決策規(guī)則挖掘算法[J].微機(jī)與應(yīng)用,2004(3).