周亮

（六九零二科技有限公司，江蘇 南京 210009）

決策樹構(gòu)造算法的分析

周亮

（六九零二科技有限公司，江蘇 南京 210009）

隨著互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的發(fā)展，以及軟硬件技術(shù)的極速更新，各種數(shù)據(jù)爆發(fā)式增長，多維大數(shù)據(jù)集開始出現(xiàn)。迫切需要從中提取有用的模式，簡化信息處理，將數(shù)據(jù)轉(zhuǎn)換成有價值的知識。決策樹（Decision Tree）是一種分類預(yù)測模型，可用于挖掘有用知識，包括ID3、C4.5、C5.0、PUBLIC、CHAID、SLIQ和SPRINT等，對比分析了常用的幾種決策樹算法。

數(shù)據(jù)挖掘；決策樹；ID3；C4.5

隨著云計算和各類互聯(lián)網(wǎng)的興起，我們逐步進(jìn)入了云時代。各種交易數(shù)據(jù)、通信數(shù)據(jù)、傳感器數(shù)據(jù)以及其他開放數(shù)據(jù)源迅速積聚了大量的數(shù)據(jù)。決策樹是一種通過對已有數(shù)據(jù)進(jìn)行分類，尋找數(shù)據(jù)中的特征以實現(xiàn)對新數(shù)據(jù)進(jìn)行分類和預(yù)測的技術(shù)，并以此為依據(jù)對新產(chǎn)生的數(shù)據(jù)結(jié)果進(jìn)行預(yù)測。

1 決策樹的構(gòu)建過程

構(gòu)造決策樹由樹構(gòu)造（Tree Building）和樹剪枝（Tree Pruning）兩個階段組成。

1.1 樹構(gòu)造

采用無回溯的貪心策略來構(gòu)造樹。這個過程從根決策節(jié)點開始，從上到下測試待分類項中相應(yīng)的特征屬性，并按照其結(jié)果選擇輸出分支，直至到達(dá)葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結(jié)果。其非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放至一個類別。

1.2 樹剪枝

樹剪枝的目的是為了簡化決策樹規(guī)模，避免過度分割。剪枝通常分為預(yù)剪枝和后剪枝，在決策樹生成過程中就對樹進(jìn)行了剪枝，提前停止了樹的分支生長，稱為預(yù)剪枝；后剪枝就是在樹完全構(gòu)造之后，通過特定標(biāo)準(zhǔn)對樹進(jìn)行剪枝，去掉部分分支，得到更簡潔的決策樹。

2 主要決策樹算法分析比較

2.1 ID3算法

可以進(jìn)一步得到信息增益為Gain（X，T）=H（T）－H（X，T），ID3算法生成的決策樹規(guī)則簡單、易理解，且分類速度快，但也存在不少的缺點：①抗噪性差，對噪聲比較敏感；②小規(guī)模數(shù)據(jù)集構(gòu)造的樹會存在過擬合問題；③由于ID3不能接受增量訓(xùn)練集，使得每次增加實例都必須重構(gòu)新決策樹，開銷大；④多值屬性的偏向性會導(dǎo)致最后選取的屬性并不總是最優(yōu)的屬性。

2.2 C4.5算法

以ID3為基礎(chǔ)使用信息增益率為標(biāo)準(zhǔn)選擇屬性，在樹構(gòu)造中剪枝以降低擬合度，可以處理連貫屬性。假設(shè)用離散屬性X來劃分訓(xùn)練數(shù)據(jù)集T，劃分為T1，T2，…，Tn，共n個子集，則用X對T進(jìn)行劃分所得分割信息量為：

根據(jù)分割信息量可以得出信息增益率為：

C4.5以信息增益率為屬性劃分標(biāo)準(zhǔn)，產(chǎn)生的分類規(guī)則簡單易懂，可解釋性高，準(zhǔn)確率較高。用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足，遇到大量連續(xù)屬性可以實現(xiàn)離散化處理，但C4.5算法也存在一些不足：①C4.5適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行；②在決策樹構(gòu)造出來之后，C4.5就很難再調(diào)整樹結(jié)構(gòu)和內(nèi)容，難于改善決策樹的性能。

2.3 PUBLIC算法

PUBLIC算法由Rajeev等人提出，在構(gòu)建決策樹過程中引入樹剪枝過程，剪枝基于MDL策略，使用基于最小編碼代價的算法。PUBLIC是一種典型的預(yù)剪枝算法，它采用GINI系數(shù)作為屬性分裂標(biāo)準(zhǔn)構(gòu)造一棵最二叉決策樹。PUBLIC在決策樹開始但未完成時進(jìn)行剪枝。為了降低工作量，提升工作效率不會再繼續(xù)分裂，將成為葉子的節(jié)點。

同等數(shù)據(jù)集規(guī)模下，PUBLIC的優(yōu)勢在于相較于采用預(yù)剪枝算法生成的決策樹效率大幅提高，但可以得到相同的決策樹。

2.4 SPRINT算法

SPRINT算法基于SLIQ對其缺陷進(jìn)行了改進(jìn)，是一種并行化可伸縮歸納決策樹算法。SPRINT計算速度快，真正突破了主存限制，特別是對于多核對線程處理器，可以發(fā)揮并行計算的優(yōu)勢。SPRINT對SLIQ的改進(jìn)主要包括改進(jìn)SLIQ的數(shù)據(jù)結(jié)構(gòu)，合并類表和屬性表，只有屬性列表，沒有類列表。SPRINT的屬性列表有一個特殊的數(shù)據(jù)結(jié)構(gòu)，包括類別、屬性值和ID關(guān)鍵字。當(dāng)一個節(jié)點分解時，對應(yīng)的屬性列表也同時分裂為兩個子列表，所以，有序的連續(xù)屬性列表分裂后的列表依然是有序的而無需再排序。

SPRINT也存在缺點，比如，屬性列表的大小有可能是初始數(shù)據(jù)的脊背，而每個節(jié)點都會保存一個屬性列表，這導(dǎo)致存儲屬性列表代價很大。此外，很多計算資源都用在了維護節(jié)點屬性列表，開銷較大。

3 結(jié)論

本文選取了經(jīng)典的4種決策樹構(gòu)造算法，并進(jìn)行了分析對比，指出了主要差異，總結(jié)出了各自的優(yōu)、缺點，對于不同算法的適用場景進(jìn)行了分析，有助于根據(jù)不同場景選擇最優(yōu)的決策樹構(gòu)造算法。

［1］楊明.決策樹學(xué)習(xí)算法ID3的研究［J］.微機發(fā)展，2002（05）.

TP311.13

A

10.15913/j.cnki.kjycx.2017.21.062

2095－6835（2017）21－0062－02

周亮（1983—），男，江蘇淮安人，碩士學(xué)位，工程師，中級職稱，主要研究方向為計算機科學(xué)與通信技術(shù)。

〔編輯：張思楠〕