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

徐夢(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算法

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）20-0193-03

隨著現(xiàn)代科技的發(fā)展，數(shù)據(jù)已經(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)系加以分析，從而發(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é)果，例如圖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算法分析

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算法采用使得信息增益最大的特征來劃分當(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算法采用自頂向下的搜索策略，分類速度較快。

（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ù)型屬性，然后進(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è)排序，所以造成了算法的分類效率不高；

（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ù)所含不同種類越少，特征就越好，當(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)生成的決策樹，在剪枝之后都能夠保留最重要的屬性劃分，于是剪枝方法的不同對(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.

[2] J R Quinlan Induction of Decision Tree [J]. Machine Learning， 1986（1）：81-106.

[3] 趙微，蘇健民.基于ID3算法決策樹的研究與改進(jìn)[J].科技信息（科學(xué)教研），2008（23）：383+392.

[4] 馬明莉，決策樹分類方法及其應(yīng)用研究[D].河北工業(yè)大學(xué)，2010，22.