決策樹算法的改進

摘要：決策樹算法是數(shù)據(jù)挖掘中非常活躍的研究領域。通過對數(shù)據(jù)挖掘中決策樹的基本思想進行闡述，討論了決策樹經(jīng)典算法(ID3算法)的計算復雜度問題，并針對這一問題提出了利用統(tǒng)計理論知識和條件概率的思想來改進構造決策樹的算法。實驗表明，這種構造決策樹算法的計算復雜度明顯優(yōu)于傳統(tǒng)的算法，其效率也有很大的提高。

關鍵詞：決策樹；算法；ID3；改進

圖書分類號：TP301文獻標識碼：A 文章編號：1009-3044(2008)15-20ppp-0c

The Improvement of Decision Tree Algorithm

ZHAN Ning，XU Jie

(Xinyang Vocational and Technical College，Xinyang 464000，China)

Abstract:Decision Tree Algorithm data mining is a very active research field.Through the Data Mining Decision Tree on the basic thinking，discussed the complexity problem of classic Decision Tree Algorithm (ID3 algorithm)，and in response to this issue and the use of statistical theory of conditional probability knowledge and thinking to improve the structure of the Decision Tree Algorithm.Experimental results show that the structure of the decision tree algorithm is superior to the traditional complexity of the algorithm， its efficiency also improved greatly.

Key words:Decision Tree;Algorithm;ID3;Improvement

隨著信息技術的飛速發(fā)展，數(shù)據(jù)量以驚人的速度增長。“豐富的數(shù)據(jù)與貧乏的知識”之間的矛盾日見突出，各個領域的人們迫切需要有一種能夠從這些超大數(shù)據(jù)中尋求有用信息的工具，數(shù)據(jù)挖掘就是在這種需要下出現(xiàn)的。目前，決策樹已成為一種重要的數(shù)據(jù)挖掘方法，是1986年有Quinlan提出的，很多專家學者對決策樹和ID3算法在分類過程中有偏向于取值叫多的屬性的缺點，因此人們開始懷疑ID3算法的信息熵的完美性，并對其提出了改進。

1 決策樹概念

所謂決策樹，就是在對數(shù)據(jù)進行決策分類時利用樹的結構將數(shù)據(jù)記錄進行分類，其中樹的一個葉結點就代表符合某個條件的屬性集，根據(jù)屬性的不同取值建立決策樹的各個分支，隨后遞歸的構造每個子節(jié)點的子樹。由于決策樹結構簡單便于人們認識理解以及決策樹不需要額外的數(shù)據(jù)訓練，因此決策樹是數(shù)據(jù)挖掘中常用的一種分類方法，而現(xiàn)在最常用的是基于信息熵的算法。

2 ID3算法（Iterative Dicho to mizer 3）

Quinlan的ID3算法是國際上公認的最早有影響的決策樹算法。ID3算法是基于信息熵的決策樹算法，它是根據(jù)屬性集的取值分類。ID3的優(yōu)缺點：ID3采用自頂向下不回溯的策略搜索全部的屬性空間，它建立決策樹的算法簡單，深度小，分類速度快。但是ID3對于大的屬性集則執(zhí)行效率下降快，準確性降低，并且學習能力低下。

3 改進的決策樹算法(Metric Based Decision Tree ，MBDT)

對任何數(shù)量的訓練集，總是能找到相應的多個線性判別函數(shù)把它分類，但是這樣生成的樹的深度可能太大。因為，雖然使用了最好的特征進行分類，但還是可能存在一些特征對分類很有用，盡管不是像最好的特征那樣有用，卻沒有用到。一個直覺是：有些特征對某些類別有效，但是對另外一些則無效，甚至可能有副作用，如果能把這些特征選擇出來，一次就能最大限度地把多個類別分開。MBDT正是基于這個直覺。MBDT通過在每個子集上選擇最能有效分類的那些特征使用馬氏距離進行分類。如果某個子集無法有效分類(通過閾值判斷)，就選擇最好的一個進行分類。由于事先需要有標簽的分類訓練集，所以這是有監(jiān)督的算法。

3.1 MBDT的度量方法

度量數(shù)據(jù)相似性的線性方法有多種，常用的有歐氏距離、棋盤距離、馬氏距離和切比雪夫距離等。馬氏距離的特點是對于比例尺的變換有不變性。令y=Ax，那么向量x1，x2和mx之間的距離與經(jīng)過變換后的y1，y2和my之間的距離顯然不同，甚至會出現(xiàn)這樣的情況：即‖x1-mx‖G>‖x2-mx‖G ，但是‖y1-my ‖G <‖y2-my‖G。其中G表示某個范式。這樣的話，數(shù)據(jù)之間的相近程度就不是客觀的，我們無法度量。馬氏距離具有在改變比例尺的情況下，保持距離尺度的特性。馬氏距離為

‖x-m‖M=(x-m)TC-1(x-m)(8)在馬氏距離尺度下，選擇合適的協(xié)方差矩陣，可以調(diào)整分類器(也就是對x進行變換)，使得樣本可以聚類為任何一種形式的超橢球體，從而為使用距離判據(jù)提供了基礎。

3.2 MBDT的算法

MBDT算法也是遞歸的。它的分支準測采用閾值方式。令T= {ti}，1≤i≤c表示樣本集合，其中c是樣本類別個數(shù)。令A={ai} ，1≤i≤m表示特征空間，其中m是屬性的個數(shù)，則B={b0bAA}就是A的冪空間。令βe表示誤分類閾值，βc表示交叉誤分類閾值.i)對于一個超集CAT，C包含幾個類別的樣本。對于一個屬性集合b ∈B，如果C中的樣本在這個屬性集上的取值x=(x1 ，?，xn)，xi∈b，n=0b0與某個類的典型模式的馬氏距離最小，就把樣本歸入這個類。我們的目標是選擇一個屬性集合bbest ∈B，使得C中的樣本盡可能多地被正確分類。在實踐中，總存在一些數(shù)據(jù)無法正確分類，所以如果誤分類的比例小于βe就判定是盡可能地被正確分類了。如果類ti的樣本被誤分類到tj的比例大于βc，ti和tj就被歸入同一類，等待下一層再繼續(xù)分類.ii)如果找不到一個屬性集合滿足i)，就選擇最好的情況進行分類.iii)如果所有的樣本被分類或者無法繼續(xù)進行分類，那么這個過程結束。需要強調(diào)的是，這個過程得到的最終結果未必是最優(yōu)的，特別是在i)中滿足條件的分類方式不止一個的時候，所以，如果要得到最優(yōu)的結果，需要搜索整個B空間中的不同分類情況。另外，根據(jù)試驗的結果，如果只用一個屬性進行分類的話，歐氏距離的效果比馬氏距離更好。最后，對MBDT一個改進可能會使得分類的效果更好，即把MBDT和別的方法結合起來，比如說CART。MBDT能快速地把多個類別分開，所以可以在使用MBDT后，再用CART進行分類，因為樣本類別的數(shù)目己經(jīng)相當少了。

4 結論

網(wǎng)絡數(shù)據(jù)的極大豐富給傳統(tǒng)的信息檢索任務帶來了巨大的挑戰(zhàn)。為了使計算機能夠更加智能地幫助用戶查找有用信息，激起學習的方法越來越多地被引入網(wǎng)絡信息檢索的研究。但由于面臨著一個有史以來從未有過的龐大處理對象——網(wǎng)絡信息，傳統(tǒng)的機器學習方法必須進行一定程度的改進才能適合處理大規(guī)模且質(zhì)量參差不齊的數(shù)據(jù)的要求。針對關鍵資源判定的問題，傳統(tǒng)的決策樹學習的方法需要進行改進，以應付反例樣本缺乏的困境。對決策樹學習算法的改進也帶給我們更多的思考：其他機器學習方法能否也利用類似的思路進行改進，以進行關鍵資源判定？如果有可能，何種機器學習方法進行關鍵資源判定的效果更好？關鍵資源頁面判定的方法應該如何應用，以提高網(wǎng)絡信息檢索工具（如搜索引擎）的檢索性能？這些都將是我們今后需要考察的問題。

參考文獻：

[1]毛國君，段立娟，王實，石云.數(shù)據(jù)挖掘原理與算法（高等學校教材）.清華大學出版社，2003-8-1.

[2]朱明.數(shù)據(jù)挖掘.中國科學技術大學出版社，2002-05-01.

[3]章兢，張小剛.數(shù)據(jù)挖掘算法及其工程應用.機械工業(yè)出版社，2006-6-1.

[4]唐華松，姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討.計算機應用研究，2001.

[5]史忠植.知識發(fā)現(xiàn)[M].北京:清華大學出版社，2002.22-28.

[6]格羅思，著.侯迪，宋擒豹，譯.數(shù)據(jù)挖掘-構筑企業(yè)競爭優(yōu)勢[M].西安:西安交通大學出版社，2001.

收稿日期：2008-02-07

作者簡介：湛寧（1980-），女，信陽職業(yè)技術學院計算機教師，助講，武漢理工大學研究生，主要研究方向為：多媒體軟件開發(fā)。