決策樹(shù)算法的改進(jìn)

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

關(guān)鍵詞：決策樹(shù)；算法；ID3；改進(jìn)

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

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

1 決策樹(shù)概念

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

2 ID3算法（Iterative Dicho to mizer 3）

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

3 改進(jìn)的決策樹(shù)算法(Metric Based Decision Tree ，MBDT)

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

3.1 MBDT的度量方法

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

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

3.2 MBDT的算法

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

收稿日期：2008-02-07

作者簡(jiǎn)介：湛寧（1980-），女，信陽(yáng)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)教師，助講，武漢理工大學(xué)研究生，主要研究方向?yàn)椋憾嗝襟w軟件開(kāi)發(fā)。