決策樹幾種分類算法的分析比較

1、    決策樹幾種分類算法的分析比較    徐夢(mèng)茹 王學(xué)明摘要：對(duì)數(shù)據(jù)的處理一直是現(xiàn)代科技一直在力爭(zhēng)攻克的難關(guān)?，F(xiàn)代社會(huì)的數(shù)據(jù)量每天都在急速增長(zhǎng)，那么面臨的難關(guān)也就會(huì)越來越多，例如，如何從海量數(shù)據(jù)中獲取有用的數(shù)據(jù)，進(jìn)而將有用的數(shù)據(jù)轉(zhuǎn)化為“知識(shí)”。本文將首先對(duì)數(shù)據(jù)挖掘中決策樹分類算法中的id3算法、c4.5算法、cart算法進(jìn)行詳細(xì)分析，然后總結(jié)出各個(gè)算法的優(yōu)缺點(diǎn)，并提出每種算法應(yīng)該應(yīng)用于何種情況之下。關(guān)鍵詞：決策樹分類算法；id3算法；c4.5算法；cart算法：tp31 ：a ：1009-3044（2018）20-0193-03隨著現(xiàn)代科技的發(fā)展，數(shù)據(jù)

2、已經(jīng)成為人們生活中必不可少的元素之一，幾乎沒有人的生活是可以離開數(shù)據(jù)的，大到宇宙星體間的關(guān)聯(lián)，小到超市商品的信息，可以說生活處處是數(shù)據(jù)。每人每天都會(huì)產(chǎn)生大量的數(shù)據(jù)，國(guó)際著名的數(shù)據(jù)公司idc報(bào)告稱，2013年全球產(chǎn)生的數(shù)據(jù)量已達(dá)4.4zb，且將以每?jī)赡攴环乃俣仍鲩L(zhǎng)，到2020年，全球數(shù)據(jù)量將高達(dá)44zb。1由此可知全球每天產(chǎn)生的數(shù)據(jù)量是極其龐大的，各領(lǐng)域的學(xué)者都希望能充分利用這些數(shù)據(jù)，通過分析，獲得大量有用的信息。然而實(shí)際上，有用的數(shù)據(jù)是很少的，要從這些數(shù)據(jù)中發(fā)現(xiàn)有用的信息猶如大海撈針，更不用說再尋找它們之間的聯(lián)系，因而需要一種能夠在海量數(shù)據(jù)中快速找出有用信息的技術(shù)，并對(duì)這些信息之間的關(guān)系加

3、以分析，從而發(fā)掘出對(duì)人們生產(chǎn)和生活有用的“知識(shí)”。由此產(chǎn)生的一項(xiàng)技術(shù)就是數(shù)據(jù)挖掘技術(shù)。數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)有用知識(shí)的過程，是一種專業(yè)技術(shù)，也是一種分析數(shù)據(jù)的手段，用于發(fā)現(xiàn)海量數(shù)據(jù)所隱藏的各種規(guī)律。數(shù)據(jù)挖掘技術(shù)在對(duì)數(shù)據(jù)進(jìn)行處理的過程中需要對(duì)數(shù)據(jù)進(jìn)行分類，這樣才能方便之后數(shù)據(jù)的處理與預(yù)測(cè)。通常所用到的數(shù)據(jù)分類技術(shù)是決策樹分類法。決策樹，顧名思義，它是一種樹形結(jié)構(gòu)，如圖1所示，是一個(gè)典型的決策樹。決策樹包含決策節(jié)點(diǎn)、分支和葉節(jié)點(diǎn)三部分，其中決策節(jié)點(diǎn)代表某個(gè)待分類數(shù)據(jù)集合的某個(gè)屬性，例如圖1的“是否有房”和“是否有車”屬性，在該屬性上的不同測(cè)試結(jié)果對(duì)應(yīng)一個(gè)分支，每個(gè)葉節(jié)點(diǎn)表示一種可能的分類結(jié)果，

4、例如圖1中的“可以”代表可以給貸款人進(jìn)行貸款，而“不可以”則表示不能給貸款人進(jìn)行貸款。用決策樹進(jìn)行分類一般有兩個(gè)步驟：第一步是利用給定的數(shù)據(jù)集合建立一棵決策樹模型；第二步是利用生成的決策樹模型對(duì)需要分類的樣本進(jìn)行分類。決策樹在構(gòu)建過程中需要重點(diǎn)解決兩個(gè)問題：1）如何選擇合適的屬性作為決策節(jié)點(diǎn)去劃分?jǐn)?shù)據(jù)集合。2）如何在適當(dāng)位置停止劃分，從而得到大小合適的決策樹。對(duì)于何時(shí)停止決策樹的劃分，一般我們認(rèn)為當(dāng)屬性列表為空，或者數(shù)據(jù)集中樣本都已經(jīng)分類，此時(shí)就可以停止決策樹分支的形成及劃分，從而得到初始的決策樹。而對(duì)于第一個(gè)問題，不同的決策樹算法則給出了不同的解決方法來劃分屬性，下面依次做出分析。1 id3

5、算法分析1.1 hunt算法簡(jiǎn)析在討論決策樹算法之前，需要先了解一下hunt算法，此算法是幾種經(jīng)典決策樹算法的基礎(chǔ)。hunt算法的基本步驟為：當(dāng)集合中的數(shù)據(jù)都屬于同一個(gè)類，就可以將他們放一起，作為葉子節(jié)點(diǎn)；若集合中數(shù)據(jù)的屬性各種各樣，就可以先篩選出所有需要的屬性，然后從其中選擇一個(gè)屬性，將其分類出來，形成節(jié)點(diǎn)，再對(duì)剩下的數(shù)據(jù)進(jìn)行上述過程，直至全部分離出來。決策樹的幾個(gè)經(jīng)典算法的主要過程就如以上所述，但是根據(jù)什么來將屬性分離出來，則是值得進(jìn)一步探討和改進(jìn)的問題。1.2 id3算法id3算法于1986年由quinlan提出，使用信息增益作為屬性選擇標(biāo)準(zhǔn)。2信息增益是數(shù)據(jù)劃分前后的熵的差值，id3算

6、法采用使得信息增益最大的特征來劃分當(dāng)前的數(shù)據(jù)。算法的執(zhí)行過程如下：首先對(duì)所有屬性計(jì)算其相應(yīng)的信息增益值，并選擇值最大的屬性作為決策樹的一個(gè)節(jié)點(diǎn)，之后由該屬性的不同取值建立此節(jié)點(diǎn)下的分支，再對(duì)各分支的子集遞歸調(diào)用以上過程，建立決策樹節(jié)點(diǎn)和分支，直到剩下的數(shù)據(jù)集合都屬于同一類別為止，最后得到一棵決策樹，用來對(duì)新的樣本進(jìn)行分類。1.2 id3算法的用途及優(yōu)缺點(diǎn)id3算法是一個(gè)典型的決策樹分類算法，以一種從簡(jiǎn)單到復(fù)雜的策略遍歷空間。id3算法具有以下的優(yōu)點(diǎn)：（1） id3在建樹過程中會(huì)包含所有可能的樹，建立過程從空的樹開始，然后逐步考慮更加復(fù)雜的情況。（2） id3算法采用自頂向下的搜索策略，分類速度

7、較快。（3） id3算法與hunt算法一樣，非常適合處理離散的樣本數(shù)據(jù)。當(dāng)然，此算法也有自己的弊端，例如此種算法不能在搜索中進(jìn)行回溯，因而不能判斷有多少其他的決策樹也是與現(xiàn)有的訓(xùn)練數(shù)據(jù)一致的，這樣算法只能收斂到局部最優(yōu)的答案，而不能得到全局最優(yōu)的答案，且此算法依賴于屬性值數(shù)目較多的屬性，但是屬性值較多的屬性不一定是分類最優(yōu)的屬性，同時(shí)此算法不能處理連續(xù)型屬性4。2 c4.5算法分析2.1 c4.5算法c4.5算法也是用于生成決策樹的一種經(jīng)典算法，是id3算法的另一種延伸和優(yōu)化。c4.5算法與id3算法生成決策樹的過程基本相同，但是 id3算法不能處理連續(xù)型屬性，而c4.5算法可以先離散化連續(xù)型

8、屬性，然后進(jìn)行屬性的選擇分類；屬性分類時(shí)，id3算法利用信息增益進(jìn)行屬性分類選擇，c4.5算法則用信息增益率進(jìn)行計(jì)算。在用c4.5算法構(gòu)造決策樹時(shí)，信息增益率最大的屬性即為當(dāng)前節(jié)點(diǎn)的分裂屬性，隨著遞歸計(jì)算，被計(jì)算的屬性的信息增益率就會(huì)變得越來越小，到后期則選擇相對(duì)比較大的信息增益率的條件屬性作為分裂屬性。2.2 c4.5算法的用途及優(yōu)缺點(diǎn)c4.5算法的主要優(yōu)點(diǎn)有：（1） 可以處理數(shù)據(jù)不完整和連續(xù)型屬性的數(shù)據(jù)集；（2） 分類的正確率比較高；（3） 建模速度較快。c4.5算法的缺點(diǎn)：（1） 在建立決策樹的步驟流程中，必須重復(fù)地對(duì)相應(yīng)的數(shù)據(jù)集合進(jìn)行一次掃描和逐個(gè)排序，所以造成了算法的分類效率不高；（

9、2） c4.5算法的計(jì)算公式涉及了大量的對(duì)數(shù)運(yùn)算，計(jì)算機(jī)在進(jìn)行計(jì)算時(shí)，會(huì)頻繁地調(diào)用函數(shù)，增加了算法的時(shí)間開銷；（3） c4.5算法盡管是id3算法的改進(jìn)，但是還不能處理很多其他形式的數(shù)據(jù)集。3 cart算法分析3.1 cart算法cart決策樹算法是breiman于1984年提出的決策樹構(gòu)建算法，采用二元切分法，每次把數(shù)據(jù)切成兩份，分別進(jìn)入左子樹、右子樹，并且每個(gè)非葉節(jié)點(diǎn)都有兩個(gè)孩子，這樣建立起來的樹就是二叉樹。cart算法采用基尼指數(shù)（gini）來選擇要分割的屬性，cart每一次迭代都會(huì)降低gini系數(shù)，當(dāng)數(shù)據(jù)所含的類別越多，此系數(shù)就越大，只有當(dāng)系數(shù)越小，那么數(shù)據(jù)所含不同種類越少，特征就越好

10、，當(dāng)一個(gè)節(jié)點(diǎn)中所有樣本數(shù)據(jù)都屬于一個(gè)類時(shí)，gini系數(shù)為0。cart算法的主要過程包含以下三個(gè)方面：（1）二分：在每次判斷過程中，都是對(duì)觀察變量進(jìn)行二分。算法總是將當(dāng)前數(shù)據(jù)集合分割為兩個(gè)子數(shù)據(jù)集，使得生成的決策樹的每個(gè)非葉節(jié)點(diǎn)都只有兩個(gè)分支，因此cart算法生成的決策樹是結(jié)構(gòu)簡(jiǎn)潔的二叉樹。算法對(duì)于連續(xù)特征的處理則與c4.5算法相似。（2）單變量分割：每次最優(yōu)劃分都是針對(duì)單個(gè)變量。（3）剪枝策略：是cart算法的關(guān)鍵點(diǎn)。剪枝過程在最優(yōu)決策樹生成過程中占有特別重要的地位。有研究表明，剪枝過程的重要性要比樹的生成過程更為重要，對(duì)于不同的劃分標(biāo)準(zhǔn)生成的決策樹，在剪枝之后都能夠保留最重要的屬性劃分，于是

11、剪枝方法的不同對(duì)決策樹尤其是最優(yōu)決策樹的生成顯得尤為重要。常用的剪枝方法有rep、pep、ccp等。3.2 cart算法的用途及優(yōu)缺點(diǎn)cart算法雖然可以通過剪枝來避免過擬合的情況，但是此算法效率較低，在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描；且此算法只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練的數(shù)據(jù)集大得內(nèi)存中無法容納時(shí)，程序無法執(zhí)行。4 結(jié)束語通過上述對(duì)三種算法的分析與比較，可以知道，面對(duì)不同的情況可以選擇不同的算法來進(jìn)行決策樹的構(gòu)造，從而來對(duì)數(shù)據(jù)集進(jìn)行分類，完成數(shù)據(jù)挖掘過程中的重要的一步。這三種算法是決策樹分類算法中最經(jīng)典的算法，之后有大量學(xué)者對(duì)此類算法進(jìn)行了不同程度的改進(jìn)，例如有c5.0算法，還有很多基于實(shí)際應(yīng)用的改進(jìn)算法。通過對(duì)分類算法的一步步優(yōu)化與改進(jìn)，數(shù)據(jù)挖掘技術(shù)得以更好地發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)，從而可以廣泛地應(yīng)用到實(shí)際生活中，對(duì)人們的生活和生產(chǎn)產(chǎn)生極為重大的作用。參考文獻(xiàn)：1 米允龍，米春橋，劉文奇.海量數(shù)據(jù)挖掘過程相關(guān)技術(shù)研究進(jìn)展j.計(jì)算機(jī)科學(xué)與探索，2015，9（06）：641-659