在SIGAI之前的公眾號文章“大話AdaBoost算法”中我們介紹了集成學習的思想以及Boosting算法，今天的文章中我們將為大家介紹另外一種集成學習算法-隨機森林。隨機森林由多棵決策樹組成，采用多棵決策樹聯合進行預測可以有效提高模型的精度。這些決策樹用對訓練樣本集隨機抽樣構造出的樣本集訓練得到。由于訓練樣本集由隨機抽樣構造，因此稱為隨機森林。隨機森林不僅對訓練樣本進行抽樣，還對特征向量的分量隨機抽樣，在訓練決策樹時，每次尋找最佳分裂時只使用一部分抽樣的特征分量作為候選特征進行分裂

集成學習 集成學習（ensemble learning）是機器學習中的一種思想，而不是指某一具體算法，它通過多個模型的組合形成一個精度更高的模型，參與組合的模型稱為弱學習器（weak learner）。在預測時使用這些弱學習器模型聯合進行預測；訓練時需要用訓練樣本集依次訓練出這些弱學習器。這種集體決策的例子在我們的日常生活中經常會見到，如醫生集體會診，如果對某一病人的情況拿不定主意，可以讓多位醫生一起來診斷，用他們各自的診斷結果進行投票，得到最終的診斷結果。因此，集成學習是一種非常符合人類思維習慣的方法。
Bootstrap抽樣 在概率論與數理統計中，我們學習過隨機抽樣的概念，統計學的核心思想是用樣本推斷整體，即用隨機抽取的樣本來研究所有樣的特征。Bootstrap抽樣是一種數據抽樣方法，它是構成Bagging算法和隨機森林的基礎。所謂抽樣是指從一個樣本數據集中隨機抽取一些樣本，形成新的數據集。這里有兩種選擇：有放回抽樣和無放回抽樣。對于前者，一個樣本被抽中之后會放回去，在下次抽樣時還有機會被抽中。對于后者，一個樣本被抽中之后就從抽樣集中去除，下次不會再參與抽樣，因此一個樣本最多只會被抽中一次。在這里Bootstrap使用的是有放回抽樣。我們可以給這種做法一個形象的解釋，公司年會抽獎時，有兩種做法，第一種是一個人中獎之后不能再繼續參與抽獎，這是無放回抽樣；否則就是有放回抽樣，這會造成運氣好的人多次中獎。 Bootstrap抽樣的做法是在n個樣本的集合中有放回的抽取n個樣本形成一個數據集。在這個新的數據集中原始樣本集中的一個樣本可能會出現多次，也可能不出現。例如，如果有有10個樣本，Bootstrap抽樣從它們中隨機的抽取出10個，下面兩種情況都是可能發生的： 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 第一種結果是10次都抽中了1，第二種是1-10這10個樣本每個都被抽中一次。 假設樣本集中有n個樣本，每次抽中其中任何一個樣本的概率都為1/n，即等概率，一個樣本在每次抽樣中沒被抽中的概率為1-1/n。由于是有放回的抽樣，每兩次抽樣之間是獨立的，因此對于連續n次抽樣，一個樣本沒被抽中的概率為： 可以證明，當n趨向于無窮大時這個值的極限是1/e，約等于0.368，其中e是自然對數的底數。即如下結論成立：
證明過程很簡單，在微積分中，有這樣一個重要極限： 我們只要湊出這樣的形式就可以了，感興趣的讀者可以自己證明。 如果樣本量很大，在整個抽樣過程中每個樣本有0.368的概率不被抽中。由于樣本集中各個樣本是相互獨立的，在整個抽樣中所有樣本大約有36.8%沒有被抽中。這部分樣本稱為包外（Out Of Bag，簡稱OOB）數據，后面我們會看到它的用途。
Bagging算法 在日常生活中我們會遇到這樣的情況：對一個決策問題，如果一個人拿不定主意，可以組織多個人來集體決策。如果要判斷一個病人是否患有某種疑難疾病，可以組織一批醫生來會診。會診的做法是讓每個醫生做一個判斷，然后收集他們的判斷結果進行投票協商，得票最多的那個判斷結果作為最終的結果。這種思想在機器學習領域的應用就是集成學習算法。 在Bootstrap抽樣的基礎上可以構造出Bagging（Bootstrap Aggregating）算法。這種方法對訓練樣本集進行多次Bootstrap抽樣，用每次抽樣形成的數據集訓練一個弱學習器模型，得到多個獨立的弱學習器（對于分類問題，稱為弱分類器），最后用它們的組合進行預測。訓練流程為： 循環，對i = 1, ..., T 對訓練樣本集進行Bootstrap抽樣，得到抽樣后的訓練樣本集 用抽樣得到的樣本集訓練一個模型 h_{i}(x)結束循環 輸出模型組合 h_{1}(x),...,h_{T}(x) 其中T為弱學習器的數量。Bagging算法是一個抽象的框架，并沒有指明每個弱學習器是什么類型的。如果弱學習器是決策樹，這種方法就是隨機森林

隨機森林 隨機森林由Breiman等人提出[1]，它由多棵決策樹組成。在數據結構中我們學過森林的概念，它由多棵數組成，這里沿用了此概念。對于分類問題，一個測試樣本會送到每一棵決策樹中進行預測，然后進行投票，得票最多的類為最終分類結果。對于回歸問題隨機森林的預測輸出是所有決策樹輸出的均值。例如隨機森林有10棵決策樹，有8課樹的預測結果是第1類，1棵決策樹的預測結果為第2類，2棵決策樹的預測結果為第3類，則我們將樣本判定成第1類。 使用多棵決策樹聯合進行預測可以有效降低模型的方差，下面給出一種不太嚴格的解釋。對于n個獨立同分布的隨機變量 x_{i}，假設它們的方差為 \sigma^{2}，則它們均值的方差為： 即將多個隨機變量相加取均值，方差會減小。如果將每棵決策樹的輸出值看作隨機變量，多棵樹的輸出值的均值的方差會比單棵樹小，因此可以降低模型的方差。 由于使用了決策樹進行投票，而決策是分段常數函數，因此隨機森林也是分段常數函數，是一個非線性模型，而且是判別模型。下圖是用隨機森林對平面上2類樣本（紅色和藍色）進行訓練和分類的結果（來自SIGAI云端實驗室）： 按照前面介紹的，隨機森林不僅可以用于分類問題，還可以用于回歸問題。另外，它也支持多分類問題，這是由決策樹的能力所保證的。 訓練算法 隨機森林在訓練時，循環依次訓練每一棵決策樹，每棵樹的訓練樣本都是從原始訓練集中進行Bootstrap抽樣得到。在訓練決策樹的每個節點時所用的特征也是隨機抽樣得到的，即從特征向量中隨機抽出部分特征參與訓練。在SIGAI之前的公眾號文章“理解決策樹”中，我們已經介紹了決策樹訓練算法的原理，尤其是訓練每個內部節點時尋找最佳分裂的原理，如果對此不清楚，可以先閱讀這篇文章。隨機森林對訓練樣本和特征向量的分量都進行了隨機采樣。 在這里決策樹的訓練算法與“理解決策樹”中介紹的相同，這里唯一的不同是訓練決策樹的每個節點時只使用隨機抽取的部分特征分量。下圖是隨機森林訓練過程的示意圖（來自SIGAI云端實驗室），下圖是完整的樣本集：
下圖是訓練一棵決策樹時隨機抽取的一部分樣本形成的樣本集以及用它訓練出來的決策樹： 關注SIGAICN公眾號，回復“試用卡”，即可申請云端實驗室試用賬號 每次訓練決策樹時，都是從整個樣本集隨機選取的部分樣本。最后訓練得到的隨機森林如下圖所示：
樣本的隨機抽樣可以用均勻分布的隨機數構造，如果有m個訓練樣本，只需要將隨機數變換到區間[0, m-1]即可。每次抽取樣本時生成一個該區間內的隨機數，然后選擇編號為該隨機數的樣本。對特征分量的采樣是無放回抽樣，可以用隨機洗牌算法實現，即將樣本先隨機亂序，然后挑選出前面的一部分。在c++的STL庫中，random_shuffle函數實現了隨機洗牌的功能，在其他語言中，也有類似的函數。 這里需要確定決策樹的數量以及每次分裂時選用的特征數量，對此并沒有標準的答案。第一個問題根據訓練集的規模和問題的特點而定。第二個問題也沒有一個精確的理論答案，可以通過實驗確定。 正是因為有了這些隨機性，隨機森林可以在一定程度上消除過擬合。對樣本進行采樣是必須的，如果不進行采樣，每次都用完整的訓練樣本集訓練出來的多棵樹是相同的，這沒有任何意義。

包外誤差 訓練每一棵決策樹時有一部分樣本未參與訓練，可以在訓練時利用這些沒有被選中的樣本做測試，統計它們的預測誤差，稱為包外誤差。這種做法與交叉驗證類似。二者都是把樣本集切分成多份，輪流用其中的一部分樣本進行訓練，用剩下的樣本進行測試。不同的是交叉驗證把樣本均勻的切分成份，在訓練集中同一個樣本不會出現多次；后者在每次Bootstrap抽樣時同一個樣本可能會被選中多次。 利用包外樣本作為測試集得到的包外誤差與交叉驗證得到的誤差基本一致，因此可以用來代替交叉驗證的結果，因此可以使用包外誤差作為泛化誤差的估計。下面給它包外誤差的計算方法。對于分類問題，包外誤差定義為被錯分的包外樣本數與總包外樣本數的比值。對于回歸問題，所有包外樣本的回歸誤差和除以包外樣本數。 實驗結果證明，增加決策樹的數量包外誤差與測試誤差會下降。這個結論為我們提供了確定決策樹數量的一種思路，可以通過觀察誤差來決定何時終止訓練。當訓練誤差穩定之后停止訓練。

計算變量的重要性 隨機森林有一個特點，可以在訓練過程中輸出變量的重要性，即哪個特征分量對分類更有用。實現的方法是置換法。它的原理是，如果某個特征分量對分類很重要，那么改變樣本的該特征分量的值，樣本的預測結果就容易出現錯誤。也就是說這個特征值對分類結果很敏感。反之，如果一個特征對分類不重要，隨便改變它對分類結果沒多大影響。 對于分類問題，訓練某決策樹時在包外樣本集中隨機挑選兩個樣本，如果要計算某一變量的重要性，則置換這兩個樣本的這個特征值。統計置換前和置換后的分類準確率。變量重要性的計算公式為： 這翻譯的是置換前后的分類準確率變化值。 上面定義的是單棵決策樹的變量重要性，計算出每棵樹的變量重要性之后，對該值取平均就得到隨機森林的變量重要性。計算出每個變量的重要性之后，將該值歸一化得到最終的重要性值。

實際應用 因為采用了決策樹作為弱學習器，隨機森林同樣具有運算量小、實現簡單的優點，得到了廣泛的應用。典型的應用包括各種圖像和數據的分類[2][3]，人臉檢測與關鍵點定位問題[4]。

總結 隨機森林是一種集成學習算法，它將多棵決策樹進行整合來完成預測。對于分類問題預測結果是所有決策樹預測結果的投票；對于回歸問題，是所有決策樹預測結果的均值。訓練時，通過Bootstrap抽樣來形成每棵決策樹的訓練集，訓練每棵決策樹的每個節點時，所用的特征也是從整個特征向量中抽取的一部分特征。通過將多棵決策樹集成，以及每次用采樣的樣本和特征分量訓練每棵決策樹，可以有效的降低模型的方差。 隨機森林是一種判別模型，既支持分類問題，也支持回歸問題，并且支持多分類問題。它是一種非線性模型，其預測函數為分段常數函數。
參考文獻 [1] Breiman, Leo. Random Forests. Machine Learning 45 (1), 5-32, 2001. [2] Jisoo Ham, Yangchi Chen, Melba M Crawford, Joydeep Ghosh. Investigation of the random forest framework for classification of hyperspectral data. IEEE Transactions on Geoscience and Remote Sensing. 2005. [3] M Pal. Random forest classifier for remote sensing classification.International Journal of Remote Sensing. 2005. [4] Dong Chen, Shaoqing Ren, Yichen Wei, Xudong Cao, Jian Sun. Joint Cascade Face Detection and Alignment. european conference on computer vision. 2014.
推薦閱讀： 關注SIGAICN公眾號，回復文章獲取碼，即可獲得全文鏈接 [1] 機器學習-波瀾壯闊40年 【獲取碼】SIGAI0413. [2] 學好機器學習需要哪些數學知識？【獲取碼】SIGAI0417. [3] 人臉識別算法演化史 【獲取碼】SIGAI0420. [4] 基于深度學習的目標檢測算法綜述 【獲取碼】SIGAI0424. [5] 卷積神經網絡為什么能夠稱霸計算機視覺領域？【獲取碼】SIGAI0426. [6] 用一張圖理解SVM的脈絡 【獲取碼】SIGAI0428. [7] 人臉檢測算法綜述 【獲取碼】SIGAI0503. [8] 理解神經網絡的激活函數 【獲取碼】SIGAI0505. [9] 深度卷積神經網絡演化歷史及結構改進脈絡-40頁長文全面解讀 【獲取碼】SIGAI0508. [10] 理解梯度下降法 【獲取碼】SIGAI0511. [11] 循環神經網絡綜述—語音識別與自然語言處理的利器 【獲取碼】SIGAI0515. [12] 理解凸優化 【獲取碼】SIGAI0518. [13] 【實驗】理解SVM的核函數和參數 【獲取碼】SIGAI0522. [14] 【SIGAI綜述】行人檢測算法 【獲取碼】SIGAI0525. [15] 機器學習在自動駕駛中的應用—以百度阿波羅平臺為例(上)【獲取碼】SIGAI0529. [16] 理解牛頓法 SIGAI 2018.5.31 [17] 【群話題精華】5月集錦—機器學習和深度學習中一些值得思考的問題 【獲取碼】SIGAI0601. [18] 大話Adaboost算法 【獲取碼】SIGAI0602. [19] FlowNet到FlowNet2.0：基于卷積神經網絡的光流預測算法 【獲取碼】SIGAI0604. [20] 理解主成分分析(PCA)【獲取碼】SIGAI0606. [21] 人體骨骼關鍵點檢測綜述 【獲取碼】SIGAI0608. [22] 理解決策樹 【獲取碼】SIGAI0611. [23] 用一句話總結常用的機器學習算法 【獲取碼】SIGAI0613. [24] 目標檢測算法之YOLO 【獲取碼】SIGAI0615. [25] 理解過擬合 【獲取碼】SIGAI0618. [26] 理解計算：從√2到AlphaGo ——第1季 從√2談起 【獲取碼】SIGAI0620. [27] 場景文本檢測——CTPN算法介紹 【獲取碼】SIGAI0622. [28] 卷積神經網絡的壓縮和加速 【獲取碼】SIGAI0625. [29] k近鄰算法 【獲取碼】SIGAI0627. [30] 自然場景文本檢測識別技術綜述 【獲取碼】SIGAI0629. [31] 理解計算：從√2到AlphaGo ——第2季 神經計算的歷史背景 【獲取碼】SIGAI0702. [32] 機器學習算法地圖 【獲取碼】SIGAI0704. [33]反向傳播算法推導-全連接神經網絡【獲取碼】SIGAI0706. [34]生成式對抗網絡模型綜述【獲取碼】SIGAI0709. [35]怎樣成為一名優秀的算法工程師【獲取碼】SIGAI0711. [36] 理解計算：從√2到AlphaGo ——第3季 神經網絡的數學模型【獲取碼】SIGAI0702. [37] 人臉檢測算法之S3FD 【獲取碼】SIGAI6 [38]基于深度負相關學習的人群計數方法 【獲取碼】SIGAI0718 [39] 流形學習概述 【獲取碼】SIGAI0721 [40] 關于感受野的總結 【獲取碼】SIGAI0723

總結

以上是生活随笔為你收集整理的随机森林概述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。