本頁使用了標題或全文手工轉換

隨機森林

維基百科,自由的百科全書
跳至導覽 跳至搜尋

機器學習中,隨機森林是一個包含多個決策樹分類器,並且其輸出的類別是由個別樹輸出的類別的眾數而定。 Leo BreimanAdele Cutler發展出推論出隨機森林的演算法。而"Random Forests"是他們的商標。這個術語是1995年由貝爾實驗室的Tin Kam Ho所提出的隨機決策森林random decision forests)而來的。這個方法則是結合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method" 以建造決策樹的集合。

歷史[編輯]

隨機森林的引入最初是由Leo Breiman在一篇論文中提出的。[1]這篇文章描述了一種結合隨機節點最佳化和bagging,利用類CART過程構建不相關樹的森林的方法。此外,本文還結合了一些已知的、新穎的、構成了現代隨機森林實踐的基礎成分,特別是

  1. 使用out-of-bag誤差來代替泛化誤差
  2. 通過排列度量變數的重要性

演算法[編輯]

預備:決策樹學習[編輯]

決策樹是各種機器學習任務的常用方法。 Hastie et al.說:「樹學習是如今最能滿足於資料探勘的方法,因為它在特徵值的縮放和其他各種轉換下保持不變,對無關特徵是魯棒的,而且能生成可被檢查的模型。然而,它通常並不準確。」[2]

特別的,生長很深的樹容易學習到高度不規則的模式,即過學習,在訓練集上具有低偏差和高方差的特點。隨機森林是平均多個深決策樹以降低方差的一種方法,其中,決策樹是在一個資料集上的不同部分進行訓練的。[2]這是以偏差的小幅增加和一些可解釋性的喪失為代價的,但是在最終的模型中通常會大大提高效能。

Bagging[編輯]

隨機森林訓練演算法把bagging的一般技術應用到樹學習中。給定訓練集X = x1, ..., xn和目標Y = y1, ..., yn,bagging方法重複(B次)從訓練集中有放回地採樣,然後在這些樣本上訓練樹模型:

For b = 1, ..., B:
  1. Sample, with replacement, n training examples from X, Y; call these Xb, Yb.
  2. Train a classification or regression tree fb on Xb, Yb.

在訓練結束之後,對未知樣本x的預測可以通過對x上所有單個回歸樹的預測求平均來實現:

或者在分類任務中選擇多數投票的類別。

這種bagging方法在不增加偏置的情況下降低了方差,從而帶來了更好的效能。這意味著,即使單個樹模型的預測對訓練基的噪聲非常敏感,但對於多個樹模型,只要這些樹並不相關,這種情況就不會出現。簡單地在同一個資料集上訓練多個樹模型會產生強相關的樹模型(甚至是完全相同的樹模型)。Bootstrap抽樣是一種通過產生不同訓練集從而降低樹模型之間關聯性的方法。

此外,x'上所有單個回歸樹的預測的標準差可以作為預測的不確定性的估計:

樣本或者樹的數量B是一個自由參數。通常使用幾百到幾千棵樹,這取決於訓練集的大小和性質。使用交叉驗證,或者通過觀察out-of-bag誤差(那些不包含xᵢ的抽樣集合在樣本xᵢ的平均預測誤差),可以找到最佳的B值。當一些樹訓練到一定程度之後,訓練集和測試集的誤差開始趨於平穩。

從bagging到隨機森林[編輯]

上面的過程描述了樹的原始的bagging演算法。隨機森林與這個通用的方案只有一點不同:它使用一種改進的學習演算法,在學習過程中的每次候選分裂中選擇特徵的隨機子集。這個過程有時又被稱為「特徵bagging」。這樣做的原因是bootstrap抽樣導致的樹的相關性:如果有一些特徵預測目標值的能力很強,那麼這些特徵就會被許多樹所選擇,這樣就會導致樹的強相關性。Ho分析了不同條件下bagging和隨機子空間投影對精度提高的影響。[3]

典型地,對於一個包含p個特徵的分類問題,可以在每次劃分時使用個特徵。[2]:592對於回歸問題,作者推薦p/3 但不少於5個特徵。[2]:592

極限樹[編輯]

再加上一個隨機化步驟,就會得到極限隨機樹extremely randomized trees),即極限樹。與普通的隨機森林相同,他們都是單個樹的整合,但也有不同:首先,每棵樹都使用整個學習樣本進行了訓練,其次,自上而下的劃分是隨機的。它並不計算每個特徵的最佳劃分點(例如,基於資訊熵或者基尼不純度),而是隨機選擇劃分點。該值是從特徵經驗範圍內均勻隨機選取的。在所有隨機的劃分點中,選擇其中分數最高的作為結點的劃分點。與普通的隨機森林相似,可以指定每個節點要選擇的特徵的個數。該參數的預設值,對於分類問題,是,對於回歸問題,是,其中 是模型的特徵個數。[4]

性質[編輯]

特徵的重要性[編輯]

隨機森林天然可用來對回歸或分類問題中變數的重要性進行排序。下面的技術來自Breiman的論文,R語言套件randomForest包含它的實現。[5]

度量資料集 的特徵重要性的第一步是,使用訓練集訓練一個隨機森林模型。在訓練過程中記錄下每個資料點的out-of-bag誤差,然後在整個森林上進行平均。

為了度量第個特徵的重要性,第個特徵的值在訓練資料中被打亂,並重新計算打亂後的資料的out-of-bag誤差。則第個特徵的重要性分數可以通過計算打亂前後的out-of-bag誤差的差值的平均來得到,這個分數通過計算這些差值的標準差進行標準化。

產生更大分數的特徵比小分數的特徵更重要。這種特徵重要性的度量方法的統計定義由Zhu et al.[6]給出。

這種度量方法也有一些缺陷。對於包含不同取值個數的類別特徵,隨機森林更偏向於那些取值個數較多的特徵,partial permutations[7][8] 、growing unbiased trees[9][10]可以用來解決這個問題。如果資料包含一些相互關聯的特徵組,那麼更小的組更容易被選擇。[11]

與最近鄰演算法的關係[編輯]

Lin和Jeon在2002年指出了隨機森林演算法和k近鄰演算法 (k-NN)的關係。[12] 事實證明,這兩種演算法都可以被看作是所謂的「加權鄰居的方案」。這些在資料集上訓練的模型通過檢視一個點的鄰居來計算一個新點x'的預測值,並且使用權重函式W對這些鄰居進行加權:

其中, 是第i個點在同一棵樹中相對於新的資料點x'的非負權重。對於任一特定的點x'的權重的和必須為1。權重函式設定如下:

  • 對於k-NN演算法,如果xi是距離x'最近的k個點之一,則,否則為0。
  • 對於樹,如果xix'屬於同一個包含k'個點的葉結點,則,否則為0。

因為森林平均了m棵樹的預測,且這些樹具有獨立的權重函式,故森林的預測值是:

上式表明了整個森林也採用了加權的鄰居方案,其中的權重是各個樹的平均。在這裡,x'的鄰居是那些在任一樹中屬於同一個葉節點的點。只要x'在某棵樹中屬於同一個葉節點,就是x'的鄰居。

基於隨機森林的非監督學習[編輯]

作為構建的一部分,隨機森林預測器自然會導致觀測值之間的不相似性度量。還可以定義未標記資料之間的隨機森林差異度量:其思想是構造一個隨機森林預測器,將「觀測」資料與適當生成的合成資料區分開來。[1][13] 觀察到的資料是原始的未標記資料,合成資料是從參考分布中提取的。隨機森林的不相似性度量之所以吸引人,是因為它能很好地處理混合變數類型,對輸入變數的單調變換是不敏感的,而且在存在異常值的情況下度量結果依然可靠。由於其原生變數的選擇,隨機森林不相似性很容易處理大量的半連續變數。

學習演算法[編輯]

根據下列演算法而建造每棵樹:

  1. N來表示訓練用例(樣本)的個數,M表示特徵數目。
  2. 輸入特徵數目m,用於確定決策樹上一個節點的決策結果;其中m應遠小於M
  3. N個訓練用例(樣本)中以有放回抽樣的方式,取樣N次,形成一個訓練集(即bootstrap取樣),並用未抽到的用例(樣本)作預測,評估其誤差。
  4. 對於每一個節點,隨機選擇m個特徵,決策樹上每個節點的決定都是基於這些特徵確定的。根據這m個特徵,計算其最佳的分裂方式。
  5. 每棵樹都會完整成長而不會剪枝(Pruning,這有可能在建完一棵正常樹狀分類器後會被採用)。

優點[編輯]

隨機森林的優點有:

  • 對於很多種資料,它可以產生高準確度的分類器。
  • 它可以處理大量的輸入變數。
  • 它可以在決定類別時,評估變數的重要性。
  • 在建造森林時,它可以在內部對於一般化後的誤差產生不偏差的估計。
  • 它包含一個好方法可以估計遺失的資料,並且,如果有很大一部分的資料遺失,仍可以維持準確度。
  • 它提供一個實驗方法,可以去偵測variable interactions。
  • 對於不平衡的分類資料集來說,它可以平衡誤差。
  • 它計算各例中的親近度,對於資料探勘、偵測離群點(outlier)和將資料視覺化非常有用。
  • 使用上述。它可被延伸應用在未標記的資料上,這類資料通常是使用非監督式群集。也可偵測偏離者和觀看資料。
  • 學習過程是很快速的。

開源實現[編輯]

  • The Original RF by Breiman and Cutler written in Fortran 77.
  • ALGLIB contains a modification of the random forest in C#, C++, Pascal, VBA.
  • party Implementation based on the conditional inference trees in R.
  • randomForest for classification and regression in R.
  • Python implementation with examples in scikit-learn.
  • Orange data mining suite includes random forest learner and can visualize the trained forest.
  • Matlab implementation.
  • SQP software uses random forest algorithm to predict the quality of survey questions, depending on formal and linguistic characteristics of the question.
  • Weka RandomForest in Java library and GUI.
  • ranger A C++ implementation of random forest for classification, regression, probability and survival. Includes interface for R.


外部連結[編輯]

  • ^ 1.0 1.1 參照錯誤:沒有為名為breiman2001的參考文獻提供內容
  • ^ 2.0 2.1 2.2 2.3 Template:ElemStatLearn
  • ^ Ho, Tin Kam. A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors (PDF). Pattern Analysis and Applications. 2002: 102–112. 
  • ^ Geurts P, Ernst D, Wehenkel L. Extremely randomized trees (PDF). Machine Learning. 2006, 63: 3–42. doi:10.1007/s10994-006-6226-1. 
  • ^ Liaw A. Documentation for R package randomForest (PDF). 16 October 2012 [15 March 2013]. 
  • ^ Zhu R, Zeng D, Kosorok MR. Reinforcement Learning Trees. Journal of the American Statistical Association. 2015, 110 (512): 1770–1784. PMC 4760114. PMID 26903687. doi:10.1080/01621459.2015.1036994. 
  • ^ Deng,H.; Runger, G.; Tuv, E. Bias of importance measures for multi-valued attributes and solutions (PDF). Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN): 293–300. 2011. 
  • ^ Altmann A, Toloşi L, Sander O, Lengauer T. Permutation importance: a corrected feature importance measure. Bioinformatics. May 2010, 26 (10): 1340–7. PMID 20385727. doi:10.1093/bioinformatics/btq134. 
  • ^ Strobl C, Boulesteix AL, Augustin T. Unbiased split selection for classification trees based on the Gini index (PDF). Computational Statistics & Data Analysis. 2007: 483–501. 
  • ^ Painsky A, Rosset S. Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2017, 39 (11): 2142–2153. PMID 28114007. arXiv:1512.03444. doi:10.1109/tpami.2016.2636831. 
  • ^ Tolosi L, Lengauer T. Classification with correlated features: unreliability of feature ranking and solutions. Bioinformatics. July 2011, 27 (14): 1986–94. PMID 21576180. doi:10.1093/bioinformatics/btr300. 
  • ^ Lin, Yi; Jeon, Yongho. Random forests and adaptive nearest neighbors (Technical report). Technical Report No. 1055. University of Wisconsin. 2002. 
  • ^ Shi, T., Horvath, S. Unsupervised Learning with Random Forest Predictors. Journal of Computational and Graphical Statistics. 2006, 15 (1): 118–138  . JSTOR 27594168. doi:10.1198/106186006X94072.  已忽略未知參數|citeseerx= (幫助)