數據挖掘入門筆記——隨機森林(趁熱打鐵)
寫在前面:健忘星人自學筆記,僅供參考。
另外,感謝大神的博客,受益良多。
Bagging與隨機森林演算法原理小結 - 劉建平Pinard - 博客園正文:
前面我們用了三章篇幅詳細介紹決策樹原理,結束的同時也留下了一些遺憾。尋找最優的決策樹是一個NP難的問題,容易陷入局部最優;另外,樣本的一點點改動,容易引起決策樹結構的劇烈變動,等等。
這時候我們會想,如果單獨用一棵樹會出現偏差,如果能把很多棵樹結合起來呢?
打個形象的比喻:森林中召開會議,討論某個動物到底是老鼠還是松鼠?
每棵樹都要獨立地發表自己對這個問題的看法,也就是每棵樹都要投票。該動物到底是老鼠還是松鼠,要依據投票情況來確定,獲得票數最多的類別就是森林的分類結果。
以上就是「集成學習演算法 * 隨機森林「的主要思想。
在更深入學習之前,我們先了解一下「集成學習」的思想:
一、集成學習
集成學習,就是組合多個弱監督模型以期得到一個強監督模型。潛在的思想是,即便某一個弱分類器得到了錯誤的預測,其他的弱分類器也可以將錯誤糾正回來。
將多個模型組合起來的集成學習,自然會面對的2個問題是:
1)怎麼訓練每個演算法?
2)怎麼融合多個演算法?
1、模型訓練
1.1 Bagging
Bagging,Bootstrapped Aggregation的簡稱。Bootstrap是一種有放回的重複抽樣方法,抽樣策略就是簡單的隨機抽樣。
另外,Bagging 各個學習器之間沒有依賴關係,可以並行生成,在如今大數據大樣本的的時代很有誘惑力。
【bootstrap】自助法重採樣技術,從訓練集裡面採集固定個數的樣本,但是每採集一個樣本後,都將樣本放回。也就是說,之前採集到的樣本在放回後有可能繼續被採集到。
隨機森林是bagging的一個「特化進階"版。
所謂的「特化「是因為隨機森林的弱學習器都是決策樹。所謂的「進階「是隨機森林在bagging的樣本隨機採樣基礎上,又加上了特徵的隨機選擇,其基本思想沒有脫離bagging的範疇。
1.2 Boosting
Boosting 各個學習器之間是串連的關係,每一輪的訓練集不變,改變的是樣本的權重。
(1)首先從訓練集用初始權重訓練出一個弱學習器1;
(2)根據學習誤差率來更新訓練樣本的權重,誤差率高的訓練樣本賦予更高的權重,這樣誤差率高的點在後面的弱學習器2中就會得到更多的重視;
(3)然後基於調整權重後的訓練集來訓練弱學習器2;
……
如此重複進行迭代訓練
2. 模型融合
不論採用 Boosting 還是 Bagging,我們都得到了若干個弱學習器,如何將預測結果融合是一下步重點解決的問題。
(1)數值預測問題,可以採用平均值法,包括簡單平均,加權平均等。
(2)分類預測問題,一般採用投票法,簡單的方法就是「少數服從多數」。複雜一點要求「超過半數」,否則拒絕預測。更加複雜的,要求「加權投票」
(3)Stacking——將弱學習器(初級學習器)的預測結果作為輸入,再套上一個模型(次級學習器)預測一次,最終得到輸出
以上就是集成學習的核心內容,我們將之前的描述上升華一下:
集成學習的核心內容:
(1)如何構建具有差異性的分類器;(2)如何對這些分類器的結果進行整合。
二、隨機森林,Random Forest
決策樹和集合學習頗有淵源,將決策樹與上面提到的集成學習演算法框架進行結合所得到的新的演算法:
1)Bagging + 決策樹 = 隨機森林
2)AdaBoost + 決策樹 = 提升樹
3)Gradient Boosting + 決策樹 = GBDT
今天我們主要學習的內容,就是「隨機森林「。
2.1 隨機森林核心
隨機森林,Random Forest 是 Bagging 的一種特化進階版。
首先,在 Random Forest【森林】里,弱學習器全部由CART決策樹構成。各個決策樹之間沒有依賴關係,並列運行。
其次,Random Forest 的 【隨機】體現在兩個方面:
(1) 隨機特徵
每棵樹訓練用的特徵不是全部特徵,而是隨機從M個總特徵中選出的m個特徵子集,每次樹進行分裂時,從這m個特徵中選擇最優的;
選變數個數(m)是決策樹的重要參數,對系統的調優非常關鍵。
如果m=M,M表示全部特徵數量,則此時RF的CART決策樹和普通的CART決策樹沒有區別。
m取值越小,則模型約健壯,當然此時對於訓練集的擬合程度會變差。也就是說m越小,模型的方差會減小,但是偏倚會增大。在實際案例中,一般會通過交叉驗證調參獲取一個合適的m值。
(2) 隨機數據
如果訓練集大小為 N ,對於每棵樹而言,隨機且有放回地從訓練集中的抽取 N 個訓練樣本,作為該樹的訓練集。
放回採樣,必然導致一部分數據被選中,另外一部分數據沒有選中,選中了就放到bag中,沒有選中的就是out of bag(oob)。
按照 Random Forest 的採用方式,每個樣本每次被採集到的概率為 ,不被採集到的概率為 ,m次採樣都沒有被採集中的概率是 。
當m→∞時,
即,在bagging的每輪隨機採樣中,訓練集中大約有36.8%的數據沒有被採樣到。也就是說,對於每棵樹而言(假設對於第k棵樹),大約36.8%的訓練實例沒有參與第k棵樹的生成,它們稱為第k棵樹的 oob 樣本(袋外樣本)。
由於袋外樣本的存在,這些沒有選中的數據不參與建模,所以可以作為驗證數據,評估模型效果。因此,隨機森林沒有必要再進行交叉驗證或者用一個獨立的測試集來獲得誤差的一個無偏估計,可以用 oob error 替代。
oob error 計算步驟:
1)對每個樣本,計算它作為oob樣本的樹對它的分類情況(約1/3的樹); 2)然後以簡單多數投票作為該樣本的分類結果; 3)最後用誤分個數占樣本總數的比率作為隨機森林的oob誤分率。
舉例,
上圖中,每行代表一個樣本,每列代表一棵樹,* 表示參與了模型訓練。
觀察到,Data 1 參加了 Tree 2,4,6 的訓練,沒有參加 Tree 1,3,5,7 的訓練;
首先將 Data 1 投入沒有參與訓練的模型中,即 Tree 1,3,5,7 的樹模型中,得到4個分類結果,按照簡單多數投票,預測Data 1的分類;
在 Data 2,3,4 ,5重複上述過程,取得全部Data的預測分類;
將全部Data的預測分類和實際分類作比較,錯誤預測Data數 Data總數,即全部樣本的oob誤分率。
【隨機特徵】和【隨機數據】這兩個隨機性的引入對隨機森林的分類性能至關重要。由於它們的引入,使得隨機森林不容易陷入過擬合,並且具有很好得抗噪能力(比如:對預設值不敏感)。
也正因為如此,隨機森林相比CART決策樹還有另外一個特點,那就是:通常情況下, 隨機森林不需要剪枝。
回想一下,我們在學習決策樹時剪枝的目的,是為了防止過度擬合。隨機森林裡面每棵樹的產生通過選特徵、選數據的隨機性,已經考慮了避免過擬合。剩下的每棵樹需要做的,就是儘可能的在自己所對應的數據(特徵)集情況下做到最好的預測結果。
因此,隨機森林中的每棵樹都盡最大程度的生長,並沒有剪枝過程。
2.2 影響性能因素
隨機森林模型特別讓人稀罕的一點,就是基本不需要調參。
但我們仍需要了解影響模型性能的因素,方便我們應對實際情況中難以預測的問題。
影響隨機森林性能的因素包括:
(1)森林面積越越大,分類效果越好;(2)森林中的每棵樹越茂盛,分類效果就越好;(3)森林中任意兩棵樹的相關性越大,錯誤率越大;
對應需要調整的參數有:
(1) 決策樹的個數 n_estimators
(2) 遞歸次數(即決策樹的深度)max_depth
(3) 特徵屬性的個數 max_features
—— n_estimators,因為有隨機因素,n_estimators越多結果越穩定,所以只要允許內,決策樹的數目越大越好。通常隨著樹的數量的增加,test error 會逐漸減小,當達到足夠大的時候,test error的變化變得很小,這時候就可以確定較為合理的樹的數量。
—— max_depth,一般來說,數據少或者特徵少的時候可以不管這個值。如果模型樣本量多,特徵也多的情況下,推薦限制這個最大深度,具體的取值取決於數據的分布。深度越小,計算量越小,速度越快。常用的可以取值10-100之間。
—— max_features,減小max_features不僅會提升演算法速度,也有可能降低測試誤差;通常使用的值可以是全部特徵值M的開方,或者取對數,即 或者 ;或者,逐一嘗試max_features的值,直到找到比較理想的數。
2.3 特徵重要性
基於樹的集成演算法還有一個很好的特性,就是模型訓練結束後可以輸出模型所使用的特徵的相對重要度,便於我們選擇特徵,理解哪些因素是對預測有關鍵影響。
在隨機森林中,簡單來說,當某一特徵在所有樹中離樹根的平均距離越近,這一特徵在給定的分類或回歸問題中就越重要。
一般有兩種計算特徵重要性的方法:基於基尼係數、基於oob 袋外數據
(1)基於基尼係數
隨機森林中每棵樹都是CART決策樹,因此樹在選擇向下分裂的特徵時,都是基於基尼係數。
假設某特徵的在某一棵樹上的節點m向下分裂,
分裂前的基尼係數為 GI ,分裂後,左右分支的基尼係數分別為 GIL 、GIR
則,VIm = GI - (GIL+GIR)
假設在這棵數上,該特徵分裂了k次,則在這棵樹上的重要性為
假設隨機森林中,共有n棵數用到該特徵,則整個森林中整個特徵的重要性為
最後把所有求得的M個特徵重要性評分進行歸一化處理就得到重要性的評分:
(2)基於袋外數據
1:對於隨機森林中的每一顆決策樹,使用相應的OOB(袋外數據)數據來計算它的袋外數據誤差,記為errOOB1.
2: 隨機地對袋外數據OOB所有樣本的特徵X加入雜訊干擾,再次計算它的袋外數據誤差,記為errOOB2.3:假設隨機森林中有N棵樹,那麼對於特徵X的重要性=∑(errOOB2-errOOB1)/N
之所以可以用這個表達式來作為相應特徵的重要性的度量值是因為:若給某個特徵隨機加入雜訊之後,袋外的準確率大幅度降低,則說明這個特徵對於樣本的分類結果影響很大,也就是說它的重要程度比較高。
而該方法中涉及到的對數據增加噪音或者進行打亂的方法通常有兩種:
1)是使用uniform或者gaussian抽取隨機值替換原特徵;2)是通過permutation的方式將原來的所有N個樣本的第 i 個特徵值重新打亂分布(相當於重新洗牌)。
一般來說,第二種方法使用得更多。
2.4 隨機森林優缺點
優點:
(1)可以高度並行化運算,大樣本運算有速度優勢
(2)由於採用了隨機採樣,泛化能力強,對缺失值不敏感
(3)訓練後可以輸出特徵重要性
(4)調參較為簡單
缺點:
(1)在某些噪音比較大的樣本集上,RF模型容易陷入過擬合。
(2) 取值劃分比較多的特徵容易對RF的決策產生更大的影響,從而影響擬合的模型的效果。
今天就學習到這裡,感謝觀看~~
後面預計繼續學習決策樹+集成學習組合的模型,再加上實踐的內容
推薦閱讀: