楊小軍 錢魯鋒 別 致

（國防大學(xué)聯(lián)合勤務(wù)學(xué)院后勤與裝備信息資源教研室 北京 100858）

1 引言

決策樹算法是數(shù)據(jù)挖掘領(lǐng)域廣泛研究和應(yīng)用的一種分類算法，具備計算量小、速度快、分類準(zhǔn)確率高、分類規(guī)則容易被人理解等優(yōu)點(diǎn)，主要的決策樹算法有ID3、C4.5、CART、SLIQ、SPRINT等。在數(shù)量眾多的決策樹算法中，不同的決策樹算法在處理數(shù)據(jù)類型、建模機(jī)制的選取、決策樹構(gòu)建方法、分類規(guī)則表達(dá)方式等方面存在很大的區(qū)別。對于這些各具特色的算法，該如何比較和評定它們的性能好壞呢？用來比較和評估決策樹算法性能優(yōu)劣的指標(biāo)主要有以下五個［2］：

l）預(yù)測準(zhǔn)確率。模型正確地預(yù)測數(shù)據(jù)類別的能力；

2）速度。產(chǎn)生和使用模型的計算時間花費(fèi)；

3）強(qiáng)壯性。模型對數(shù)據(jù)包含噪聲或有空缺值時正確預(yù)測的能力；

4）可伸縮性。對于大型數(shù)據(jù)集，能有效構(gòu)造模型的能力；

5）可解釋性。模型是否易于理解。

WEKA是新西蘭Waikato大學(xué)開發(fā)的數(shù)據(jù)挖掘系統(tǒng)，實(shí)現(xiàn)了基本的決策樹分類算法，提供了適用于各類數(shù)據(jù)集的數(shù)據(jù)預(yù)處理以及算法性能評估方法，具有很強(qiáng)的擴(kuò)展性和兼容性。本文對WEKA平臺中的三個經(jīng)典的決策樹算法C4.5、CART和NBTree算法進(jìn)行算法性能分析和比較。

2 三種決策樹算法實(shí)現(xiàn)原理

用決策樹算法對訓(xùn)練樣本數(shù)據(jù)集進(jìn)行挖掘后會生成一棵形如二叉樹或多叉樹的決策樹。該決策樹的葉子節(jié)點(diǎn)代表數(shù)據(jù)的某一類別，非葉節(jié)點(diǎn)代表某個非類別屬性的一個判斷，判斷的一個結(jié)果形成非葉節(jié)點(diǎn)的一個分枝，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的一條路徑形成一條分類規(guī)則。如此一棵決策樹就能夠轉(zhuǎn)化為若干條分類規(guī)則，再根據(jù)這些生成的分類規(guī)則就可以快速地對未知類別的數(shù)據(jù)樣本進(jìn)行預(yù)測。構(gòu)造一棵決策樹的通用算法描述如下［3］：

BuildDecisionTree（Training Dataset E）

if（E滿足某個中止條件）Then return；

For（i=l；i＜=E中屬性的個數(shù)；i++）

評估每個屬性關(guān)于給定的屬性選擇度量的分裂特征；

找出最佳的測試屬性并據(jù)此將E劃分為E1和E2；

BuildDeeisionTree（E1）；

BuildDeeisionTree（E2）；

EndIf

算法的終止條件一般有三種情況［3］：

1）訓(xùn)練數(shù)據(jù)集E中所有的樣本都屬同一個類，則將此節(jié)點(diǎn)當(dāng)作一個葉子節(jié)點(diǎn)，并以該類標(biāo)記此節(jié)點(diǎn)；

2）無屬性可以作為測試屬性；

3）訓(xùn)練樣本的數(shù)量少于用戶提供的閾值。

后兩種情況中一般以訓(xùn)練樣本中占優(yōu)勢的類標(biāo)記該葉子節(jié)點(diǎn)。屬性選擇度量有信息增益、信息增益率和Gini指數(shù)等。通常，一棵能完全分類訓(xùn)練樣本集的決策樹并不是最好的，因為這樣的樹對訓(xùn)練樣本集過于敏感，而訓(xùn)練樣本集均無可避免地存在噪聲和孤立點(diǎn)。需要對生成的樹進(jìn)行剪枝，以去除過分適應(yīng)訓(xùn)練樣本集的枝條，避免過擬合現(xiàn)象產(chǎn)生。C4.5、CART和NBTree三種決策樹分類算法的不同之處在于屬性選擇標(biāo)準(zhǔn)各異。

2.1 C4.5算法

C4.5決策樹算法是基于ID3算法改進(jìn)而來的，假設(shè)樣本集E分為C類樣本訓(xùn)練集，每類樣本數(shù)量為 pi，i=1，2，…C。如果用屬性A為測試屬性，屬性A的v個不同的值分別為{v1，v2，…vv}，用屬性A將樣本集E劃分為v個子集{E1，E2，…Ev}，假設(shè)Ei中含有第j類樣本數(shù)為 pij，j=1，2，…C，子集 Ei的熵為

屬性A的信息熵為

一棵決策樹對一樣例作出正確類別判斷所需要的信息為

屬性A的信息增益為

信息增益是ID3算法的屬性選擇標(biāo)準(zhǔn)，ID3算法具有存在著只能處理離散屬性，構(gòu)造的決策樹與數(shù)據(jù)之間容易過擬合，對噪聲敏感等問題。在ID3算法的基礎(chǔ)上進(jìn)行改進(jìn)形成以信息增益率為屬性選擇標(biāo)準(zhǔn)的C4.5算法。屬性A的信息增益率計算如下：

C4.5算法以信息增益率為標(biāo)準(zhǔn)決定決策樹分支的準(zhǔn)則，尋找最佳分組變量和分割點(diǎn)，從而建立決策樹。其具備分類規(guī)則易于理解、算法復(fù)雜度低等優(yōu)點(diǎn)。C4.5算法克服了ID3算法屬性偏向的問題，增加了對連續(xù)屬性的處理，通過剪枝，在一定程度上避免了過擬合現(xiàn)象。但是該算法將連續(xù)屬性離散化時，需遍歷該屬性的所有值，效率有所降低。

2.2 CART算法

CART算法全稱為分類回歸樹，既可以處理分類問題又能處理回歸問題，本文只關(guān)注其處理分類問題的能力。CART算法進(jìn)行分類時采用Gini指數(shù)作為測試屬性的選擇標(biāo)準(zhǔn)。Gini指數(shù)計算如下：

其中 |E|，|E1|，|E2|分別是樣本集E、E1和 E2中的樣本個數(shù)。

其中 pi是類別i在樣本集E中出現(xiàn)的概率。CART算法生成的決策樹精度較高，但隨著決策樹復(fù)雜度的提高，分類精確度會有所降低，用該算法建立的決策樹不宜太復(fù)雜。

2.3 NBTree算法

NBTree算法是樸素貝葉斯和決策樹算法兩種分類技術(shù)的融合，提取了兩種算法的優(yōu)勢。該算法在樹的構(gòu)建過程中，對產(chǎn)生的每個結(jié)點(diǎn)構(gòu)建樸素貝葉斯分類器，并循環(huán)這個過程，直至所有結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)，最后對每一個葉子結(jié)點(diǎn)都構(gòu)建一個樸素貝葉斯分類算法。NBTree算法的分類標(biāo)準(zhǔn)為，對于屬性（A1，A2，…，An），計算各屬性 Ai的效用μ（Ai），取得效用最高為μ的屬性。當(dāng)μ不能顯著優(yōu)于當(dāng)前結(jié)點(diǎn)的效用時，則為當(dāng)前結(jié)點(diǎn)構(gòu)造一個樸素貝葉斯分類算法，再返回。根據(jù)各屬性上的效用測試來劃分樣本集。NBTree算法優(yōu)點(diǎn)為，首先，算法過程清晰、直觀；其次，在計算復(fù)雜度不高的前提下能保持較高的分類正確率。

3 算法性能分析實(shí)驗

本文試驗中的數(shù)據(jù)來自于UCI數(shù)據(jù)集，UCI數(shù)據(jù)集是美國加洲大學(xué)爾灣學(xué)院公開的科研數(shù)據(jù)集，本文從UCI數(shù)據(jù)集中選取了8個樣本數(shù)據(jù)集，用于決策分類算法的比較分析，這些數(shù)據(jù)集需要經(jīng)過簡單的預(yù)處理：去除具有唯一值的ID和Name屬性，將序數(shù)型的類標(biāo)轉(zhuǎn)化為標(biāo)稱型。完成預(yù)處理后的數(shù)據(jù)集基本信息如表1所示。使用WEKA平臺中現(xiàn)有的 C4.5（J48）、CART（SimpleCart）和 NBTree算法對實(shí)驗數(shù)據(jù)集進(jìn)行分類，實(shí)驗采用10折交叉驗證法。實(shí)驗機(jī)器選用聯(lián)想臺式機(jī)，具體配置：處理器為Intel i5-4590 3.30GHz處理器；4G內(nèi)存；64位windows操作系統(tǒng)。實(shí)驗最終的結(jié)果體現(xiàn)在表2、表3、表4和表5四個表格中。

表1 WEAK平臺下決策樹算法性能分析實(shí)驗數(shù)據(jù)基本信息

表2 算法分類準(zhǔn)確率比較

表3 算法建模時間比較

表4 算法生成決策樹情況

表5 規(guī)則數(shù)目與葉子節(jié)點(diǎn)數(shù)目的比值情況

4 實(shí)驗結(jié)論分析

根據(jù)表3的實(shí)驗結(jié)果，從建模速度來看，大部分情況下，三種算法中C4.5算法的建模速度最快，CART算法建模速度次之，NBTree算法建模速度最慢。但在 Bank Marketing、Skin Segmentation、Nursery三個數(shù)據(jù)集上，NBTree算法建模速度要優(yōu)于CART算法，在Bank Marketing和Skin Segmentation這兩個數(shù)據(jù)集上表現(xiàn)得更明顯，原因于這三個數(shù)據(jù)集的記錄數(shù)量分別為45211、245057、12960，是實(shí)驗所用的八個數(shù)據(jù)集中最大的三個，隨著數(shù)據(jù)集中數(shù)據(jù)量的增長，CART算法的建模速度有所下降，不及NBTree算法。

從分類的效果來看，依據(jù)表2，大部分情況下，CART算法準(zhǔn)確率最高，NBTree算法次之，C4.5算法準(zhǔn)確率最低。個別情況下，如在Iris和Skin Segmentation兩個數(shù)據(jù)集上，C4.5算法無論建模速度還是分類準(zhǔn)確率都是最好的。從表1我們可以看出，Iris數(shù)據(jù)集的屬性數(shù)量只有4個，Skin Segmentation數(shù)據(jù)集的屬性數(shù)為3，數(shù)據(jù)之間的關(guān)系相對簡單，C4.5算法在簡單數(shù)據(jù)集上的分類準(zhǔn)確率比NBTree算法和CART算法都要高。

一個算法，如果能以較少的葉子結(jié)點(diǎn)生成較多的規(guī)則，則算法的可解釋性強(qiáng)，根據(jù)表5，當(dāng)數(shù)據(jù)量不大且數(shù)據(jù)之間關(guān)系相對簡單時，C4.5算法的可解釋性最好，CART算法次之，NBTree算法的可解釋性最差。當(dāng)數(shù)據(jù)量和數(shù)據(jù)的復(fù)雜程度提高時，CART算法的可解釋性最好，C4.5算法次之，NBTree算法的可解釋性仍舊最差。以上是三種算法的總體情況，由于進(jìn)行比較的八個數(shù)據(jù)集都是成熟的公開科研數(shù)據(jù)集，數(shù)據(jù)集規(guī)模不大，只有個別的數(shù)據(jù)集有少量的噪聲數(shù)據(jù)，本文沒有從可伸縮性和強(qiáng)壯性方面來對這三個算法進(jìn)行實(shí)驗比較。

5 結(jié)語

C4.5算法、CART算法和NBTree算法是三種經(jīng)典的決策樹分類算法，面對不同的數(shù)據(jù)集時，分類準(zhǔn)確率、建模速度和可解釋性都在發(fā)生變化，因此不存在可以解決所有分類問題的理想算法，進(jìn)行分類時，需要根據(jù)數(shù)據(jù)集的情況，具體問題具體分析，選擇合適的算法。當(dāng)數(shù)據(jù)量不大或是數(shù)據(jù)關(guān)系比較簡單時，優(yōu)先采用C4.5算法。當(dāng)數(shù)據(jù)量增長或是數(shù)據(jù)關(guān)系比較復(fù)雜時，優(yōu)先采用CART算法，NBTree算法可以作為替補(bǔ)。本文討論的三種算法均是基于內(nèi)存構(gòu)造樹，針對的是百萬條記錄以下的數(shù)據(jù)集，在大規(guī)模數(shù)據(jù)情況下，需要加以改進(jìn)，增強(qiáng)算法的可伸縮性。