隨機(jī)森林算法

《隨機(jī)森林算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

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

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

5、訓(xùn)練集S(i)，作為根節(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)樣本集各個樣本值的平均值。然后繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)沒有達(dá)到終止條件，則從F維特征中隨機(jī)選取f維特征（f<

6、為葉子節(jié)點(diǎn)。(5)重復(fù)(2),(3),(4)直到所有決策樹都被訓(xùn)練過。利用隨機(jī)森林的預(yù)測過程如下：對于第i棵樹，i=1:t(1)從當(dāng)前樹的根節(jié)點(diǎn)開始，根據(jù)當(dāng)前節(jié)點(diǎn)的閾值th，判斷是進(jìn)入左節(jié)點(diǎn)(=th)，直到到達(dá)，某個葉子節(jié)點(diǎn)，并輸出預(yù)測值。(2)重復(fù)執(zhí)行(1)直到所有t棵樹都輸出了預(yù)測值。如果是分類問題，則輸出為所有樹中預(yù)測概率總和最大的那一個類，即對每個c(j)的p進(jìn)行累計(jì)；如果是回歸問題，則輸出為所有樹的輸出的平均值。