陳猛 洪偉

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

關鍵詞 集成;決策樹;隨機;C4.5

引言

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

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

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

1知識背景

1.1 基于決策樹的分類算法

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

1.2 集成學習方法

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

2隨機決策樹集成分類算法

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

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

定義1：分裂深度（）

在生成隨機分類樹的過程中， 分類深度h <時，在屬性隨機選擇序列中進行隨機選擇。

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

算法3.1隨機樹生成算法：

GRDT（D，deep）

輸入：

D：訓練元組和它們的對應類標號的集合;

deep; //生成隨機樹當前深度

輸出：

一棵隨機決策樹

方法：創(chuàng)建結點 N;

if samples 都在同一個類C then

return N 作為葉結點，以類C標記;

if （（deep + 1） < ）

對屬性列表的每個屬性計算，選擇信息增益最高的NUM個屬性放入隨機選擇表中。

在隨機選擇表中，隨機選擇一個屬性，作為分裂屬性splitting_attribute

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

else? 作標準樹劃分

return N;

生成隨機決策樹后，我們可以生成標準決策樹，構造出集成分類器使用投票表決的方法分類測試數(shù)據(jù)[5]。算法如下：

輸入：D，K

輸出：集成模型M*

方法：

For（i=1;i

{ 使用D，導出隨機決策樹Ti，加入M*

}

將使用D導出的標準決策樹T加入M*

Return M*

3結束語

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

參考文獻

[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.