陳猛 洪偉

摘 要 決策樹分類算法是數(shù)據(jù)挖掘的一種典型數(shù)據(jù)分析方法。本文提出一種基于C4.5的隨機(jī)決策樹分類器集成算法對(duì)數(shù)據(jù)集進(jìn)行分類，該算法對(duì)屬性選擇進(jìn)行隨機(jī)化處理，并對(duì)集成過程進(jìn)行控制，該分類器集成算法有較高的分類準(zhǔn)確率。

關(guān)鍵詞 集成;決策樹;隨機(jī);C4.5

引言

分類是數(shù)據(jù)挖掘的一個(gè)重要分支，目前已有許多成熟的算法，如決策樹、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等。集成分類法在同一問題上學(xué)習(xí)多個(gè)基分類器，再將其預(yù)測(cè)結(jié)果結(jié)合得出最終分類結(jié)果，它能夠有效地提高預(yù)測(cè)性能，因此受到了廣泛的關(guān)注[1]。

為保證模型分類效果，單個(gè)基分類器的精度要高，同時(shí)基分類器之間差異要大。本文提出了一種基于C4.5的隨機(jī)決策樹集成分類算法，在隨機(jī)決策樹的生成中對(duì)屬性選擇進(jìn)行隨機(jī)化處理，并對(duì)集成過程進(jìn)行控制[2]。

本文的組織如下：第二部分介紹背景知識(shí)。第三部分介紹基于C4.5的隨機(jī)決策樹集成分類算法。

1知識(shí)背景

1.1 基于決策樹的分類算法

在20世紀(jì)80年代初，機(jī)器學(xué)習(xí)研究者J.Ross Quinlan開發(fā)了ID3算法，算法的計(jì)算過程不需要任何領(lǐng)域知識(shí)和參數(shù)設(shè)置，適合于探索式知識(shí)發(fā)現(xiàn)。決策樹歸納的學(xué)習(xí)和分類步驟簡(jiǎn)單快速，學(xué)習(xí)的模型用樹形式表示，直觀且易于理解，并且決策樹分類一般情況下具有較好的準(zhǔn)確率。后來Quinlan提出了C4.5[4]算法，它降低了計(jì)算復(fù)雜度，增強(qiáng)了計(jì)算的效率， 克服了ID3方法選擇偏向取值多的屬性。C4.5算法還針對(duì)連續(xù)值屬性的數(shù)據(jù)進(jìn)行了處理，彌補(bǔ)了ID3算法只能處理離散值屬性數(shù)據(jù)的缺陷。

1.2 集成學(xué)習(xí)方法

與單個(gè)算法相比，集成分類可以提高分類準(zhǔn)確率，而且不容易出現(xiàn)過適應(yīng)現(xiàn)象。在每個(gè)基本分類器的學(xué)習(xí)過程之中引入隨機(jī)，使得學(xué)習(xí)出來的每個(gè)基本分類器都不同，然后利用投票表決的方法進(jìn)行集成，也是有效的系綜學(xué)習(xí)方法。在集成學(xué)習(xí)中引入隨機(jī)可以對(duì)改進(jìn)學(xué)習(xí)的精度，取得更好的學(xué)習(xí)效果[3]。

2隨機(jī)決策樹集成分類算法

本文使用的決策樹構(gòu)造算法是C4.5。C4.5算法在構(gòu)造每一層樹結(jié)構(gòu)時(shí)，選擇信息增益最高的屬性進(jìn)行分裂，由于偏置的存在，C4.5在每一步分裂選擇局部最優(yōu)屬性，但很難保證全局最優(yōu)。隨機(jī)決策樹集成分類算法的基本思想是在屬性選擇時(shí)，在信息增益最高的若干屬性中進(jìn)行隨機(jī)選擇，生成的隨機(jī)樹與標(biāo)準(zhǔn)決策樹構(gòu)成集成分類器，投票表決分類測(cè)試數(shù)據(jù)。

由C4.5的算法特點(diǎn)可知，在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性進(jìn)行分裂時(shí)，最上面的幾層對(duì)樹的結(jié)構(gòu)影響較大，越往下往往影響越小，或者沒有影響。在隨機(jī)決策樹集成分類算法中，我們引入了分裂深度。定義如下：

定義1：分裂深度（）

在生成隨機(jī)分類樹的過程中， 分類深度h <時(shí)，在屬性隨機(jī)選擇序列中進(jìn)行隨機(jī)選擇。

隨機(jī)決策樹集成分類算法在決策樹的學(xué)習(xí)過程中引入隨機(jī)，使得學(xué)習(xí)生成的每棵樹都不相同，然后將多棵隨機(jī)樹與標(biāo)準(zhǔn)決策樹集成在一起，利用投票表決的方法對(duì)數(shù)據(jù)進(jìn)行分類。在隨機(jī)樹生成算法中，當(dāng)分裂節(jié)點(diǎn)深度小于分裂深度（），算法在信息增益最高的NUM個(gè)屬中隨機(jī)選擇一個(gè)屬性作為分裂屬性，下文實(shí)驗(yàn)中的N取值為3。當(dāng)分裂節(jié)點(diǎn)深度大于分裂深度（）時(shí)，按標(biāo)準(zhǔn)樹算法劃分。

算法3.1隨機(jī)樹生成算法：

GRDT（D，deep）

輸入：

D：訓(xùn)練元組和它們的對(duì)應(yīng)類標(biāo)號(hào)的集合;

deep; //生成隨機(jī)樹當(dāng)前深度

輸出：

一棵隨機(jī)決策樹

方法：創(chuàng)建結(jié)點(diǎn) N;

if samples 都在同一個(gè)類C then

return N 作為葉結(jié)點(diǎn)，以類C標(biāo)記;

if （（deep + 1） < ）

對(duì)屬性列表的每個(gè)屬性計(jì)算，選擇信息增益最高的NUM個(gè)屬性放入隨機(jī)選擇表中。

在隨機(jī)選擇表中，隨機(jī)選擇一個(gè)屬性，作為分裂屬性splitting_attribute

加一個(gè)由 GRDT （Dsplitting_attribute， deep+1）返回的節(jié)點(diǎn)到N ;

else? 作標(biāo)準(zhǔn)樹劃分

return N;

生成隨機(jī)決策樹后，我們可以生成標(biāo)準(zhǔn)決策樹，構(gòu)造出集成分類器使用投票表決的方法分類測(cè)試數(shù)據(jù)[5]。算法如下：

輸入：D，K

輸出：集成模型M*

方法：

For（i=1;i

{ 使用D，導(dǎo)出隨機(jī)決策樹Ti，加入M*

}

將使用D導(dǎo)出的標(biāo)準(zhǔn)決策樹T加入M*

Return M*

3結(jié)束語

決策樹分類算法是預(yù)測(cè)式數(shù)據(jù)挖掘的一種典型數(shù)據(jù)分析方法，從類標(biāo)記的訓(xùn)練元組歸納決策樹。本文提出一種基于C4.5的隨機(jī)決策樹集成分類算法（標(biāo)準(zhǔn)樹是其一個(gè)成員），對(duì)數(shù)據(jù)集進(jìn)行分類，引入分裂深度的方法對(duì)隨機(jī)樹的產(chǎn)生進(jìn)行控制，該分類器集成算法有較高的分類準(zhǔn)確率。

參考文獻(xiàn)

[1] Breiman L.Bagging Predictors[J].Machine Learning，1996，24（2）：

123-140.

[2] Ho T K.The Random Subspace Method for Constructing DecisionForests[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（8）：832-844.

[3] Breiman L.Random Forests[J]. Machine Learning，2001，45（1）：5-32.

[4] Quinlan J R.C4.5：Programs for Machine Learning[M].San Mateo，

CA：Morgan Kaufmann，1993：109.

[5] Dietterich T G. An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees： Bagging， Boosting， and Randomization[J]. Machine Learning，2000，40（2）：139-157.