淺談隨機決策樹

摘要:該文介紹了隨機決策樹分類模型及如何啟發(fā)式選擇隨機決策樹的深度及棵樹，通過實驗證明了該算法的有效性和高效性。

關(guān)鍵詞:隨機決策樹;深度;棵樹

中圖分類號:TP181文獻標(biāo)識碼:A文章編號:1009-3044(2009)25-7206-02

Discussion on Random Decision Tree

LIU Xue-jing1，2， JI Jun-zhong1

(1.School of Computer Science， Beijing University of Technology， Beijing 100022， China ; 2.School of Information Engineering， Shijiazhuang University of Economics， Shijiazhuang 050031， China)

Abstract: This paper introduces the classification model of random decision tree and how to heuristic selected the depth and the number， the experiment shows that the algorithm is effectiveness and efficiency.

Key words: random decision tree; depth; number

啟發(fā)式學(xué)習(xí)算法被廣泛的用于決策樹分類模型中，其思想在于尋求一個最優(yōu)化假設(shè)，該假設(shè)使得預(yù)先給定的誤差函數(shù)的誤差減至最小。近來，由于多種模型混合的成功，如bagging模型，boosting模型，meta-learning模型等等，大大提高了最簡化假設(shè)的準(zhǔn)確性。隨機決策樹的方法和一般算法不同，它不是構(gòu)建最佳的單元樹，而是通過條件屬性集合構(gòu)建多棵樹，那么每棵樹的深度如何確定，是不是把所有的條件屬性都拿來測試，還是僅僅取部分屬性進行測試就已經(jīng)可以滿足需求;另外，創(chuàng)建多少棵樹才能達到可信度的要求。成為隨機決策樹構(gòu)建過程中非常重要的兩個問題。

1 樹的深度的選擇

使用多個隨機樹的主要特色是它的多樣性。然而，當(dāng)隨機樹太深的時候，多樣性實際上是減弱了。多樣性不是隨深度的增長而線性增長的。恰恰相反，當(dāng)隨機樹的深度等于屬性個數(shù)的極端的情況下，產(chǎn)生的每一棵隨機樹都是完全相同的，可能一點多樣性也沒有。

這里采用組合數(shù)學(xué)的方法確定隨機決策樹的深度。假設(shè)條件屬性集合中總共有k個屬性，i是我們將要確定的測試屬性的數(shù)目。Cik表示從k個屬性中無次序的選擇i個測試屬性的組合數(shù)。即可以產(chǎn)生:Cik=(k)!/i!(k-i)!條獨立的決策路徑

我們希望得到最大的組合數(shù)，從而使隨機決策樹最大程度的擁有多樣性。對于Cik本身而言，無論k是奇數(shù)還是偶數(shù)，當(dāng)i=k/2時都可以取得最大值。所以當(dāng)我們限制隨機樹的深度為k/2時，也就是樹的深度是條件屬性數(shù)目的一半時，隨機決策樹有最強的多樣性、最佳的效果。

2 樹的個數(shù)的選擇

因為每棵樹被隨機的構(gòu)建，故對于給定深度的樹，其數(shù)目是一個有效的隨機樣本，多棵樹的平均將接近一個大的樣本的真實平均數(shù)。當(dāng)每個屬性的取值都是二元時，樹的規(guī)模將達到2k/2。平均概率是使用棵樹的樣本平均值。這存在一個問題是是否值得使用更大的樣本，也就是說更多的隨機決策樹。統(tǒng)計上，非常驚奇的發(fā)現(xiàn)，當(dāng)N=10時，對大多數(shù)的應(yīng)用己經(jīng)足夠了。

我們分析了源自較低置信區(qū)間，最糟情況下算法的效果，已此證明多棵隨機決策樹模型是最佳的模型。數(shù)據(jù)集中的最壞情況是僅有一個相關(guān)的屬性，其他的k-1個屬性都是不相關(guān)的。在這是最壞的情況下，單元樹將忽略所有的不相關(guān)屬性并且選擇單個相關(guān)屬性，從而生成一個最佳模型。然而，隨機樹可能使用所有屬性，不論它是相關(guān)屬性的還是不相關(guān)的。我們得到隨機樹的數(shù)目N，能確保它在可信度為p的前提下是最佳模型。

后驗概率將由接近于訓(xùn)練數(shù)據(jù)默認概率的不相關(guān)屬性的數(shù)目來確定。如果其中有一棵隨機樹采用了最佳屬性對事例進行分類，那么平均的概率要比缺省概率好。平均概率可以和最佳單元樹輸出的概率不相同，因為在樹的構(gòu)建過程中每個屬性被選擇的概率都是相同的，致使從樹根到樹葉的每一條絕對路徑的出現(xiàn)具有相同的概率。由此，一個屬性在絕對路徑中出現(xiàn)的概率為p=1/k了，在N棵隨機樹中，相關(guān)屬性至少在一條路徑被測試到的概率為

最低限度可信度:p(k，N)=1-(1-1/k)N

即隨機決策樹是最佳模型的可信度至少為p(k，N)。事實上由于在相同的屬性集中部分屬性之間有相互的關(guān)系，導(dǎo)致實際的概率將比以上估計高。

3 算法描述

輸入:訓(xùn)練數(shù)據(jù)集S={(x1，t1)，…，(xn，tn)}，屬性集X={F1，…，F(xiàn)k}，N為隨機決策樹的棵數(shù)。

輸出:N棵隨機決策樹{T1，…，TN}

算法:

RandomTree(S，X，N)

Begin

For i∈{1，…，N} do

BuildTree (Ti，X);

End

For (x，t) ∈S do

For i∈{1，…，N} do

Update (Ti， (x，t));

End

End

Return{ T1，…，TN }

End

BuildTree (T，X)

Begin

If X=φ then

生成葉節(jié)點;

End

Else

隨機選擇屬性F，屬性F有m個值{di};

For j∈{1，…，m} do

BuildTree (nj，，X-{F});

End

End

End

Update (T，(x，t))

Begin

n[t]存放類t的數(shù)量，n[t] <- n[t]+1;

If the node is a not a leaf then

d=F(x)，n 為屬性值d對應(yīng)的子節(jié)點;

Update (n，(x，t));

End

End

CLASSIFY({T1，…，TN}，x)

Begin

for tree Ti，Pi(y|x)=where n[y] is the count at the leaf node that x finally reaches to;

returnfor all class labels y;

for tree Ti，where n[y] is the count at the leaf node that x finally reaches to;

return for all class labels y;

End

4 實驗

實驗結(jié)果與單元最佳未剪枝及剪枝的決策樹比較，通過同時改變隨機樹的數(shù)量和每棵樹的深度來研究在性能方面的變化，證明了隨機樹深度和棵樹選擇的正確。

我們從現(xiàn)實的應(yīng)用中挑選出KDD CUP’98所取的捐款數(shù)據(jù)。實驗運行4次，對每次測試，直到有50棵隨機樹被構(gòu)造出來才停止，測試結(jié)果如表1所示。

觀測結(jié)果有幾點值得重視。第一，當(dāng)隨機樹的數(shù)目超過10時，隨機樹算法取得平均總收益將比最好的方法多:第二在樹從1棵生長到10棵的過程中，精確值將有大大的提升，并且在達到10棵的時候?qū)⑦_到平穩(wěn)狀態(tài)。該算法在生成了10棵樹后將不斷的波動，但其準(zhǔn)確度大多數(shù)比單元最佳決策樹方法高。

參考文獻:

[1] 楊寧，趙連文，郭耀煌. 隨機決策樹[J].西南交通大學(xué)學(xué)報，2000，35(2):212-215.

[2] 趙曉峰，葉震.基于加權(quán)多隨機決策樹的入侵檢測模型[J].計算機應(yīng)用，2007，27(5):1041-1043.

[3] 李楠.基于改進隨機決策樹的入侵檢測方法研究[D].合肥:合肥工業(yè)大學(xué)，2007.