向卓元 張蕾

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

關鍵詞：粗糙集；屬性約簡；決策樹；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

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

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

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兩種算法結果比較

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

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

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

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

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

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