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

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

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

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

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

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

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

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

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

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

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

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

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

13、zflfaMore 廿”7羯25%5%CART 1 ： VviAblQ Aeohlary felrtd1*GerxlerMele70%17%IhQmjki內(nèi),mJM(AKT S 1 Vari國(guó) 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假如要預(yù)測(cè)的某個(gè)人的信息如下(見(jiàn)圖5-2):1. Age : 35 years ; 2. Gender : Male ; 3. HighestEducational Qualification : Diploma holder; 4. Industry :Manufacturing; 5. Residence : Metro.根據(jù)這五棵CART樹(shù)的分類(lèi)結(jié)果，可以針對(duì)此人的信息建立收入層次的分布情況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é)論：這個(gè)人的收入層次70%是一等，24%是二等，6%是三等。所以我們得出結(jié)論:這個(gè)人的收入層次是一等(小于$40000) 。3 實(shí)驗(yàn)3.1 數(shù)據(jù)集選取數(shù)據(jù)集選擇UCI 數(shù)據(jù)集中的紅葡萄酒的數(shù)據(jù)集。此數(shù)據(jù)集包含有紅葡萄酒的11 個(gè)特征：非揮發(fā)性酸、揮發(fā)性酸度、檸檬酸、殘?zhí)恰?氯化物、游離硫二氧化物、總二氧化硫、密度、PH、硫酸鹽、酒精。通過(guò)紅葡萄

16、酒的11 個(gè)特征判斷紅葡萄酒的品質(zhì)，類(lèi)標(biāo)簽用110 的數(shù)字來(lái)表示。共有 1599 個(gè)紅葡萄酒的樣本。3.2 測(cè)試代碼%清空環(huán)境變量clear allclcwarning off%導(dǎo)入數(shù)據(jù)%1.隨機(jī)產(chǎn)生訓(xùn)練集測(cè)試集a=randperm(1599);Train=winequalityred(a(1:1200),:); % 產(chǎn)生 1200 個(gè)訓(xùn)練集Test=winequalityred(a(1201:end),:); % 剩下的是測(cè)試集399 個(gè)%2.訓(xùn)練數(shù)據(jù)P_train=Train(:,1:11);T_train=Train(:,12);%3.測(cè)試數(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 類(lèi)型的 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;%十算測(cè)試集數(shù)而的標(biāo)簽預(yù)測(cè)準(zhǔn)確率本次測(cè)試調(diào)用隨機(jī)森林算法，對(duì)其參數(shù)NVarToSample和Method進(jìn)行設(shè)置，也可以通過(guò)測(cè)試其他的參數(shù)來(lái)提高隨即森領(lǐng)算法的預(yù)測(cè)率。3.3 測(cè)試結(jié)果如圖6-1名稱(chēng)，一m士前E筠.回工 Ba.回EE若Ek白c匚 btree Ptest P