數(shù)據(jù)挖掘之隨機森林算法論文

1、摘要隨機森林(Random Forests )算法是一種集成分類、是簡單而有效的集成學習分類算法，它在屬性屬性較多的數(shù)據(jù)上有極佳的分類效果，廣泛應(yīng)用于文本分類與檢索、生物醫(yī)學數(shù)據(jù)分類等實際應(yīng)用中。通過對隨機森林算法進行分析，并用通過代碼實驗來體會其算法中參數(shù)對分類效果的高效性，通過對比其最終分類的準確率來判斷隨機森林算法設(shè)計的好壞。關(guān)鍵詞 隨機森林集成學習121 引言 32 理論介紹 32.1 信息、熵以及信息增益的概念 32.2 決策樹算法 32.3 CART 決策樹算法 32.3.1 CART算法的認識 32.3.2 CART算法的原理 32.4 C4.5 決策樹算法 42.5 集成學習

2、42.5.1 集成學習的發(fā)展 42.5.2 集成學習定義 42.6 隨機森林的生成 42.6.1 隨機森林的生成 42.6.2 隨機森林的生成規(guī)則 42.7 決定隨機森林分類效果(錯誤率)的兩個因素: 52.7.1 袋外錯誤率(OOB error) 52.8 隨機森林的簡單實例分析 53 實驗 73.1 數(shù)據(jù)集選取 73.2 測試代碼 73.3 測試結(jié)果 83.4 總結(jié) 84 結(jié)束語 8數(shù)據(jù)挖掘之隨機森林算法研究與實現(xiàn)作者： XXX1 引言隨機森林就是通過集成學習的思想將多棵樹集成的一種算法，它的基本單元是決策樹，而它的本質(zhì)屬于機器學習的一大分支集成學習（ Ensemble Learning）

3、方法。隨機森林的名稱中有兩個關(guān)鍵詞，一個是“隨機”，一個就是“森林”。 “森林”我們很好理解，一棵叫做樹，那么成百上千棵就可以叫做森林了，這樣的比喻還是很貼切，其實這也是隨機森林的主要思想-集成思想的體現(xiàn)。通過此次對隨機森林算法的研究與實驗分析，更好的理解并掌握此算法。2 理論介紹2.1 信息、熵以及信息增益的概念信息熵：信息論中最核心的概念和度量方法。熵：描述變量取值的概率的不確定性。不確定性越大，熵值越大。信息增益：在決策樹算法中是用來選擇特征的指標，信息增益越大，則這個特征的選擇性越好2.2 決策樹算法決策樹算法是一種逼近離散函數(shù)值的方法。它是一種典型的分類方法，首先對數(shù)據(jù)進行處理，利用

4、歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數(shù)據(jù)進行分析。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。2.3 CART 決策樹算法2.3.1 CART 算法的認識Classification And Regression Tree ，即分類回歸樹算法，簡稱CART 算法，它是決策樹的一種實現(xiàn)。CART 算法是一種二分遞歸分割技術(shù)，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結(jié)點都有兩個分支，因此 CART 算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。由于CART 算法構(gòu)成的是一個二叉樹，它在每一步的決策時只能是“是 ”或者 “否 ”，即使一個feature有多個取值，也是把數(shù)據(jù)分為兩部分

5、。在 CART算法中主要分為兩個步驟（ 1）將樣本遞歸劃分進行建樹過程；（ 2）用驗證數(shù)據(jù)進行剪枝。2.3.2 CART 算法的原理設(shè)代表單個樣本的個屬性，表示所屬類別。CART 算法通過遞歸的方式將維的空間劃分為不重疊的矩形。劃分步驟大致如下：（ 1 ）選一個自變量，再選取的一個值，把維空間劃分為兩部分，一部分的所有點都滿足，另一部分的所有點都滿足，對非連續(xù)變量來說屬性值的取值只有兩個，即等于該值或不等于該值。（2）遞歸處理，將上面得到的兩部分按步驟（1）重新選取一個屬性繼續(xù)劃分，直到把整個維空間都劃分完。2.4 C4.5決策樹算法C4.5是決策樹算法的一種。決策樹算法作為一種分類算法，目標

6、就是將具有p維特征的n個樣本分到c個類別中去。相當于做一個投影，c=f（n）,將樣本經(jīng)過一種變換賦予一種類別標簽。決策樹為了達到這一目的，可以把分類的過程表示成一棵樹，每次通過選擇一 個特征pi來進行分叉。2.5 集成學習2.5.1 集成學習的發(fā)展集成學習的理論基礎(chǔ)是 PAC理論、強可學習與弱可學習理論。集成學習的理論基礎(chǔ)表 明強可學習器與弱可學習器是等價的，因此可以尋找方法將弱可學習器轉(zhuǎn)換為強可學習器，而不必去直接尋找較難發(fā)現(xiàn)的強可學習器。具有代表性的集成學習方法有Boosting , Bagging ,隨機森林。見圖3-1。匚 P&CI BoosiingBaggingRandom

7、Forest I|1984| 型二師一絆! Weakly and Strongly I I teamingEnsemble Leming|（c）1994|圖3-12.5.2 集成學習定義集成學習通過建立幾個模型組合的來解決單一預測問題。它的工作原理是生成多個分 類器，各自獨立地學習和作出預測。這些預測最后結(jié)合成單預測，因此優(yōu)于任何-一個單分類的做出預測。隨機森林是集成學習的一一個子類，它依靠于決策樹的投票選擇來決定最后的分類結(jié) 果。2.6 隨機森林的生成2.6.1 隨機森林的生成隨機森林中有許多分類樹。如果要將一個分類樹進行分類，需要將樣本輸入到每棵樹 中進行分類。Bootstraping采樣

8、方法：有放回采樣。隨機森林的bagging思想：將若干個弱分類器（多棵樹）的分類結(jié)果進行投票選擇， 通過表決從而組成一個強分類器。2.6.2 隨機森林的生成規(guī)則1）如果訓練集大小為N,隨機且有放回地從訓練集中抽取N個訓練樣本，構(gòu)成一個新的樣本集（含重復的訓練樣本）。2）如果每個樣本的特征維度為M ,指定一個常數(shù) m ,且m< M ,隨機地從 M個特征中選取m個特征子集，每次樹進行分裂時，從這m個特征中選擇最優(yōu)的，決策樹成長期間 m 的大小始終不變。（注意：此處采用無放回的選擇）3）每棵樹都盡可能最大程度地（完全地）生長，并且沒有剪枝過程。（將預測結(jié)果累加起來從而得到整個隨機森林的預測結(jié)果

9、）通過之前的三步就可以得到一棵決策樹，重復 X 次這樣的過程那么就能得到X 棵決策樹。來一個測試樣本就對它分類一遍，就得到X 個分類結(jié)果。使用簡單的投票機制（或用最終分類結(jié)果）來判別該樣本的所屬類。注意：兩類隨機性的引入對隨機森林的生成至關(guān)重要。2.7 決定隨機森林分類效果（錯誤率）的兩個因素:1 .森林中任意兩棵樹的相關(guān)性:相關(guān)性越大，錯誤率越大;2 .森林中每棵樹的分類能力:每棵樹的分類能力越強，整個森林的錯誤率越低。減小m （特征選擇個數(shù)），樹的相關(guān)性和分類能力也會相應(yīng)的降低；增大m,兩者也會隨之增大。所以關(guān)鍵問題是如何選擇最優(yōu)的m （或者是范圍），這也是隨機森林唯一的一個參數(shù)。2.7.

10、1 袋外錯誤率（OOB error ）構(gòu)建隨機森林的關(guān)鍵問題就是如何選擇最優(yōu)的m,要解決這個問題主要依據(jù)計算袋外錯誤率。在構(gòu)建每棵樹時,我們對訓練集使用了隨機且有放回抽樣。所以對于每棵樹而言,大約有1/3 的訓練實例沒有參與樹的生成,它們稱為樹的袋外樣本數(shù)據(jù)。這些數(shù)據(jù)沒有參與訓練模型的擬合，因此可以用來檢測模型的泛化能力。而這樣的采樣特點就允許進行袋外估計,它的計算方式如下：a對每個樣本，計算它作為袋外樣本的樹對它的分類情況（約1/3的樹）；b.然后以簡單多數(shù)投票作為該樣本的分類結(jié)果；c.最后用誤分個數(shù)占樣本總數(shù)的比率作為隨機森林的袋外錯誤率。OOB 錯誤率是隨機森林泛化誤差的一個無偏估計，它

11、的結(jié)果近似于需要大量計算的k折交叉驗證。所以沒有必要對它進行交叉驗證或者用一個獨立的測試集來獲得誤差的一個 無偏估計。它可以在內(nèi)部進行評估，也就是說在生成的過程中就可以對誤差建立一個無偏 估計。當我們知道了 OOB的計算方法，我們可以通過選取不同的m,計算OOB error,找出OOB error 最小時對應(yīng)的m 的值，就可以知道最優(yōu)的m。2.8 隨機森林的簡單實例分析根據(jù)已有的訓練集已經(jīng)產(chǎn)生了對應(yīng)的隨機森林，隨機森林如何利用某一個人的年齡（ Age） 、 性別 （ Gender） 、 教育情況 （ Highest Educational Qualification ） 、 工作領(lǐng)域 （ In

12、dustry） 以及住宅地（Residence）共5個字段來預測他的收入層次。收入層次：Band1 ： Below$40000Band 2:$40000 -150000Band3:More than $150000隨機森林中每一棵樹都可以看做是一棵CART （ 分類回歸樹），這里假設(shè)森林中有5 棵CART 樹，總特征個數(shù)N=5， 取 m=1 （m 為建立決策樹時，隨機選取的特征個數(shù)，這里假設(shè)每個CART樹對應(yīng)一個不同的特征）。（表格中的百分數(shù)指的是在不同條件下的數(shù)據(jù)樣本 占對應(yīng)類別的比例）見圖5-1。!5占 g iJkiM1上JM叫口叫電W5410%由，過27然k14%70H23%森OOfHa

13、zflfaMore 廿”7羯25%5%CART 1 ： VviAblQ Aeohlary felrtd1*GerxlerMele70%17%IhQmjki內(nèi),mJM(AKT S 1 Vari國 r：*即、fund1?4zGUCJtiCftjHigh 5<hn. 1技順in%5稀14«kfcatftei jFt77%(JH白泓比W ： VnrAbl# t.4JCBTinn51-邙日孑由-12indu y中Fina，££三%ftcturmg5%Qt*ir5?0%5科CftJCT b ： Varldblh lrnl3krvUAKT 4 ； Tsri%ble Rns

14、iSis旬制T Aril11Mrirn-TflftXJ%RE -ipriirpNon-Metro20%15，圖5-1假如要預測的某個人的信息如下(見圖5-2):1. Age : 35 years ; 2. Gender : Male ; 3. HighestEducational Qualification : Diploma holder; 4. Industry :Manufacturing; 5. Residence : Metro.根據(jù)這五棵CART樹的分類結(jié)果，可以針對此人的信息建立收入層次的分布情況CARTBand1123Age2S-4070%23%7%GenderMale70%2

15、7%3%EducationDiploma80%14%r e%IndustryManufacturing60%35%5%ResidenceMetro70%20%10%Final probabitityr 70%'24%6%圖 5-2最后，我們得出結(jié)論：這個人的收入層次70%是一等，24%是二等，6%是三等。所以我們得出結(jié)論:這個人的收入層次是一等(小于$40000) 。3 實驗3.1 數(shù)據(jù)集選取數(shù)據(jù)集選擇UCI 數(shù)據(jù)集中的紅葡萄酒的數(shù)據(jù)集。此數(shù)據(jù)集包含有紅葡萄酒的11 個特征：非揮發(fā)性酸、揮發(fā)性酸度、檸檬酸、殘?zhí)恰?氯化物、游離硫二氧化物、總二氧化硫、密度、PH、硫酸鹽、酒精。通過紅葡萄

16、酒的11 個特征判斷紅葡萄酒的品質(zhì)，類標簽用110 的數(shù)字來表示。共有 1599 個紅葡萄酒的樣本。3.2 測試代碼%清空環(huán)境變量clear allclcwarning off%導入數(shù)據(jù)%1.隨機產(chǎn)生訓練集測試集a=randperm(1599);Train=winequalityred(a(1:1200),:); % 產(chǎn)生 1200 個訓練集Test=winequalityred(a(1201:end),:); % 剩下的是測試集399 個%2.訓練數(shù)據(jù)P_train=Train(:,1:11);T_train=Train(:,12);%3.測試數(shù)據(jù)P_test=Test(:,1:11);T_

17、test=Test(:,12);%調(diào)用Random Forest 算法btree=TreeBagger(50,P_train,T_train,'NVarToSample','all','Method','classification');pred_labels,scoresl=predict(btree,Test);predict_label=cellfun(x)str2double(x),pred_labels);%將 cell 類型的 pred_labels 轉(zhuǎn)化為 double 型的 predict_labelT_test1

18、=table2cell(T_test);%將 table 型的 T_test 轉(zhuǎn)化為 cell 型的 T_test1T_test2=cell2mat(T_test1);%各cell型的T_test轉(zhuǎn)化為double型的T_test2accuray=sum(T_test2( :,1)=predict_label( :,1)/399;%十算測試集數(shù)而的標簽預測準確率本次測試調(diào)用隨機森林算法，對其參數(shù)NVarToSample和Method進行設(shè)置，也可以通過測試其他的參數(shù)來提高隨即森領(lǐng)算法的預測率。3.3 測試結(jié)果如圖6-1名稱，一m士前E筠.回工 Ba.回EE若Ek白c匚 btree Ptest P