隨機(jī)森林算法

1、.隨機(jī)森林算法1. 算法簡介隨機(jī)森林由LeoBreiman（2001）提出，它通過自助法（bootstrap）重采樣技術(shù)，從原始訓(xùn)練樣本集N中有放回地重復(fù)隨機(jī)抽取k個(gè)樣本生成新的訓(xùn)練樣本集合，然后根據(jù)自助樣本集生成k個(gè)分類樹組成隨機(jī)森林，新數(shù)據(jù)的分類結(jié)果按分類樹投票多少形成的分?jǐn)?shù)而定。其實(shí)質(zhì)是對(duì)決策樹算法的一種改進(jìn)，將多個(gè)決策樹合并在一起，每棵樹的建立依賴于一個(gè)獨(dú)立抽取的樣品，森林中的每棵樹具有相同的分布，分類誤差取決于每一棵樹的分類能力和它們之間的相關(guān)性。特征選擇采用隨機(jī)的方法去分裂每一個(gè)節(jié)點(diǎn)，然后比較不同情況下產(chǎn)生的誤差。能夠檢測到的內(nèi)在估計(jì)誤差、分類能力和相關(guān)性決定選擇特征的數(shù)目。單棵樹

2、的分類能力可能很小，但在隨機(jī)產(chǎn)生大量的決策樹后，一個(gè)測試樣品可以通過每一棵樹的分類結(jié)果經(jīng)統(tǒng)計(jì)后選擇最可能的分類。2. 算法原理決策樹（decision tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測試，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點(diǎn)開始，測試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果。隨機(jī)森林模型的基本思想是：首先，利用bootstrap抽樣從原始訓(xùn)練集抽取k個(gè)樣本，且每個(gè)樣本的樣本容量都與原始訓(xùn)練集一樣；其次，對(duì)k個(gè)樣本

3、分別建立k個(gè)決策樹模型，得到k種分類結(jié)果；最后，根據(jù)k種分類結(jié)果對(duì)每個(gè)記錄進(jìn)行投票表決決定其最終分類，如下圖所示。在建立每一棵決策樹的過程中，有兩點(diǎn)需要注意采樣與完全分裂。首先是兩個(gè)隨機(jī)采樣的過程，random forest對(duì)輸入的數(shù)據(jù)要進(jìn)行行、列的采樣。對(duì)于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個(gè)，那么采樣的樣本也為N個(gè)。這樣使得在訓(xùn)練的時(shí)候，每一棵樹的輸入樣本都不是全部的樣本，使得相對(duì)不容易出現(xiàn)over-fitting。然后進(jìn)行列采樣，從M個(gè)feature中，選擇m個(gè)（m M）。之后就是對(duì)采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹，這樣

4、決策樹的某一個(gè)葉子節(jié)點(diǎn)要么是無法繼續(xù)分裂的，要么里面的所有樣本的都是指向的同一個(gè)分類。一般很多的決策樹算法都一個(gè)重要的步驟剪枝，但是這里不這樣干，由于之前的兩個(gè)隨機(jī)采樣的過程保證了隨機(jī)性，所以就算不剪枝，也不會(huì)出現(xiàn)over-fitting。分裂特征點(diǎn)的選擇：1) 信息增益2) 信息增益比3) 基尼指數(shù)3. 算法流程隨機(jī)森林的具體實(shí)現(xiàn)過程如下：(1) 給定訓(xùn)練集S，測試集T，特征維數(shù)F。確定參數(shù)：決策樹的數(shù)量t，每棵樹的深度d，每個(gè)節(jié)點(diǎn)使用到的特征數(shù)量f，終止條件：節(jié)點(diǎn)上最少樣本數(shù)s，節(jié)點(diǎn)上最少的信息增益m對(duì)于第i棵樹，i=1: t：(2) 從S中有放回的抽取大小和S一樣的訓(xùn)練集S(i)，作為根

5、節(jié)點(diǎn)的樣本，從根節(jié)點(diǎn)開始訓(xùn)練(3) 如果當(dāng)前節(jié)點(diǎn)上達(dá)到終止條件，則設(shè)置當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，如果是分類問題，該葉子節(jié)點(diǎn)的預(yù)測輸出為當(dāng)前節(jié)點(diǎn)樣本集合中數(shù)量最多的那一類c(j)，概率p為c(j)占當(dāng)前樣本集的比例；如果是回歸問題，預(yù)測輸出為當(dāng)前節(jié)點(diǎn)樣本集各個(gè)樣本值的平均值。然后繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)沒有達(dá)到終止條件，則從F維特征中隨機(jī)選取f維特征（f F）。利用這f維特征，尋找分類效果最好的一維特征k及其閾值th，當(dāng)前節(jié)點(diǎn)上樣本第k維特征小于th的樣本被劃分到左節(jié)點(diǎn)，其余的被劃分到右節(jié)點(diǎn)。繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。(4) 重復(fù)(2)(3)直到所有節(jié)點(diǎn)都訓(xùn)練過了或者被標(biāo)記為葉子節(jié)點(diǎn)。(5) 重復(fù)(2),(3),(4)直到所有決策樹都被訓(xùn)練過。利用隨機(jī)森林的預(yù)測過程如下：對(duì)于第i棵樹，i=1: t(1)從當(dāng)前樹的根節(jié)點(diǎn)開始，根據(jù)當(dāng)前節(jié)點(diǎn)的閾值th，判斷是進(jìn)入左節(jié)點(diǎn)(=th)，直到到達(dá)，某個(gè)葉子節(jié)點(diǎn)，并輸出預(yù)測值。(2)重復(fù)執(zhí)行(1