機器學習-淺談隨機森林的幾個tricks-20170917

這篇文章不會涉及大量原理性的介紹，因為在其他地方，這種介紹已經非常多了，這裡只介紹幾個在隨機森林中容易忽視的點。

1、隨機森林每個分裂點都是隨機選取m個特徵

先假設我們有N個樣本，M個特徵，那麼在這種情況下我們是如何構建隨機森林的：

a、構建一棵樹，我們利用自助法（bootstrap）從N個樣本中選取N個樣本，需要注意的是，這N個樣本是大概率會有重複的，選取的這N個樣本就是根節點待分裂的樣本；

b、在每個待分裂節點上，我們從M個特徵中隨機選取m個特徵（<<M，通常是log2或sqrt的數量），從這m個屬性中根據某種策略（如gini減少或信息增益等）確定分裂屬性；

c、重複b步驟，直到不能分裂或達到我們設定的閾值（如葉子節點數或樹的深度），此時建立了一顆決策樹；

d、重複上面的a、b、c步驟，直到達到預定樹的顆數為止。

以上圖片來自周志華的書，

所以需要注意的是：在隨機森林中不是每棵樹隨機選擇一批特徵來分裂，而是在每個節點上都是隨機選取的。

2、為什麼絕大多數隨機森林演算法中用的都是cart樹

在sklearn中的隨機森林演算法中用的就是cart樹，在分類問題中，分裂方式不限於gini，也可以選entropy，在回歸問題中，用的是mse和mae。

我們知道在決策樹當中，不僅僅有cart演算法，還有ID3和C4.5，那為什麼隨機森林中一般用的都是cart樹呢。

首先我們來看ID3，在ID3和C4.5中都用到了一個叫做「熵」的東西，概念來自資訊理論，主要用來衡量事物的不確定性，如變數x的熵：

事物越不確定，熵就越大。在決策樹中，用到的另外一類熵被稱為條件熵，即在一定的已知條件下的熵值：

那麼在ID3中，我們選擇了一個叫做信息增益的指標來選擇分裂特徵，信息增益越大，說明選擇的變數分裂後的分支下輸出更純。比如我們有15個樣本集合D，輸出為0或者1。其中有9個輸出為0， 6個輸出為1。 樣本中有個特徵A，取值為A1，A2和A3。在取值為A1的樣本的輸出中，有3個輸出為1， 2個輸出為0，取值為A2的樣本輸出中,2個輸出為1,3個輸出為0， 在取值為A3的樣本中，4個輸出為1，1個輸出為0。

樣本D的熵為：

樣本D在特徵下的條件熵為：

對應的信息增益為：

ID3有很多明顯不足的地方：比如不能處理連續性變數；不能處理缺失值；選擇分裂變數時會傾向於選擇類別較多的變數（理解這個問題可以想的極端一點，如ID類的特徵，每一類下都只有一個輸出項）；容易過擬合。

針對ID3演算法的不足，後續又提出了C4.5的演算法。首先第一個問題，ID3不能處理連續變數，在C4.5中，會先將連續變數離散化。如我們有一個連續變數A，共有m個不同的取值 ，演算法首先將連續變數按照一定的順序排列，排列後一共有m-1個切分點，切分點的值總是取相鄰兩個值的均值，即第t個切分點的值表示為 ，然後根據切分點將變數一分為二。第二個問題，ID3不能處理缺失值，C4.5是有一定方法處理缺失值的，這裡不展開說明。第三個問題，ID3傾向於選擇類別較多的的變數，針對這個問題，C4.5引入了一個特徵熵的東西：

其中n為特徵A的類別數，Di為特徵A各類別的數量，D為總樣本數量，特徵熵反映了一個變數類別的信息，類別越多，帶來的不確定信息越多，所以C4.5基於這個指標改良了信息增益，構造了一個信息增益率的概念：

第四個問題，C4.5中引入了正則化係數進行了初步剪枝，這裡不展開。

同樣，C4.5也有一些問題：C4.5生成的是多叉樹，即一個父節點可以有多個節點。很多時候，在計算機中二叉樹模型會比多叉樹運算效率高，如果採用二叉樹，可以提高效率；C4.5隻能用於分類，不能用於回歸；C4.5由於使用了熵模型，裡面有大量耗時的對數運算,如果是連續值還有大量的排序運算，運算效率較低。

基於C4.5演算法的一些缺陷，cart樹可以在一定程度上解決，cart樹既可以做回歸，也可以做分類，為了作比較，這裡只考慮分類樹。

cart樹裡面引入了一個gini係數的概念：

在分類問題中，假設有K個類別，第k個類別的概率為pk：

特別的，對於樣本D,如果根據特徵A的某個值a,把D分成D1和D2兩部分，則在特徵A的條件下，D的基尼係數表達式為：

那麼，你肯定想知道gini係數與熵的關係，這裡有一幅二分類的圖可以看出二者的關係：

可以看出二者非常接近，但gini的計算相比熵要簡單的多，所以可以減少一定的運算量。

cart樹第二個特點在於節點的分裂上，每次節點分裂都是二叉的，所以cart樹就是多個二叉樹組成的，這種特點使得cart演算法與C4.5演算法在處理離散變數上有很大的不同，離散變數在C4.5中只有一次可能出現在分裂節點上，分裂的枝數與離散變數的類別數量有關。

如某個特徵A被選取建立決策樹節點，如果它有A1,A2,A3三種類別，我們會在決策樹上一下建立一個三叉的節點。這樣導致決策樹是多叉樹。但是cart分類樹使用的方法不同，他採用的是不停的二分，CART分類樹會考慮把A分成 ， ， ，若最終選擇 作為分裂類，那麼A2和A3在後續還是有可能會被再次分裂開。

因為每次都是二分裂，所以cart也沒有ID3中傾向於選擇類別較多的變數的缺陷。

cart樹對連續變數的處理與C4.5類似。

3、為什麼說bagging減少了variance，而boosting減少了bias

首先我們來看什麼是variance，什麼是bias，一圖勝千言：

廣義上的bias是指預測值與真實值之間的差值，而variance是指預測值之間的離散程度。bias比較好理解，但如何理解variance呢，variance其實也很好理解，它就是指模型之間的差異性，這個概念雖然不能量化，但理解即可。那麼什麼是模型之間的差異呢，不同演算法之間的衡量差異的東西不一樣，如邏輯回歸，差異主要在於係數的不同，決策樹在於樹結構的不同。如果我選定了演算法，什麼樣的模型variance是高的呢。舉個例子，如果我有一個訓練集D，可分為A1和A2，二者數量足夠，我利用這兩個訓練集訓練了兩個模型分別是F1和F2，你發現這兩個模型之間的有很大不同，如果你用了邏輯回歸，可能發現係數有很大差異，那麼此時意味著用A2的樣本在F1上驗證，或A1的樣本在F2上驗證，會出現準確率很低的現象，那麼這就是過擬合，或者說是模型的variance很高。

我們一般認為集成學習中的基模型是一種弱模型，即bias高，variance高的模型，但在不同的框架下，基模型弱的程度其實是不一樣的。在bagging和boosting框架中，通過計算基模型的期望和方差，我們可以得到模型整體的期望和方差。為了簡化模型，我們假設基模型的權重、方差及兩兩間的相關係數相等。由於bagging和boosting的基模型都是線性組成的，那麼有：

E是期望函數，Var是方差函數，F是整體模型，fi是第i個基模型，gamma是基模型權重， 是基模型相關係數，sigma^2是基模型方差。

對於bagging來說，每個基模型的權重等於1/m且期望近似相等（子訓練集都是從原訓練集中進行子抽樣），那麼bagging的偏差和方差可以表示為：

我們可以看到，整體模型的準確率與基模型的準確率相差無幾；整體模型的方差受基模型的方差，相關係數和基模型個數影響，我們看到基模型個數越大，可以降低模型的過擬合，但當m增大到一定程度時，降低模型過擬合的能力達到極限。同時降低基模型之間的相關性，也可以降低模型的過擬合，這也是為什麼隨機森林中採用行和列隨機的方式構建樹。

對於boosting來說，基模型的訓練集抽樣是強相關的（假設沒有進行子抽樣，雖然不準確），那麼模型的相關係數近似等於1，boosting的偏差和方差：

從原理上很好理解，boosting降低bias，即增加基模型的個數逼近目標，但同樣我們也發現boosting的方差是隨著基模型的個數逐漸增大的，所以當我們增大基模型個數提高準確率時，整體模型的方差也隨之增大了。

4、隨機森林的變數重要性真的能衡量變數的重要程度嗎

上面這個問題的答案既「是」也「不是」，換句話說，隨機森林的變數重要性衡量的並不完全是變數對目標變數預測的貢獻能力，而是在這個模型中對目標變數預測的貢獻能力。

要理解上面這句話，首先我們來看隨機森林中變數的重要性是如何計算的。常見的計算方法有兩種，一種是mean decrease impurity，即平均不純度的減少，現在sklearn中用的就是這種方法；一種是mean decrease accuracy，即平均準確率的減少，常用袋外誤差率去衡量。

以上兩種計算方法從字面上應該都很好理解，但這兩種方法來衡量變數重要性有一定的陷阱。假設我們有兩個變數，分別是A和B，A和B之間有較強的相關性，如果A對模型貢獻度較大，由於B很像A，所以B也應該對模型貢獻較大，但實際情況並不會這樣。我們來看一個實際的例子，分別是一個變數，加上了相似的噪音：

size = 10000np.random.seed(seed=10)X_seed = np.random.normal(0, 1, size)X0 = X_seed + np.random.normal(0, .1, size)X1 = X_seed + np.random.normal(0, .1, size)X2 = X_seed + np.random.normal(0, .1, size)X = np.array([X0, X1, X2]).TY = X0 + X1 + X2 rf = RandomForestRegressor(n_estimators=20, max_features=2)rf.fit(X, Y);print "Scores for X0, X1, X2:", map(lambda x:round (x,3), rf.feature_importances_)Scores for X0, X1, X2: [0.278, 0.66, 0.062]

我們可以清楚的看到X1與X2的變數重要性相差10倍左右，但實際上二者其實是很相似的。

另外一個trick是隨機森林中類別數較多的變數會傾向於有較高的變數重要性，這個問題可以從dummy化去考慮，由於類別較多的變數橫向dummy化的變數較多，其被選進m特徵的概率會比其他變數更高。

所以變數重要性要慎用。

5、隨機森林可以處理相關性較強的變數嗎

這個問題是接著上一個問的，答案是在一定程度可以，但建議剔除相關性較強的變數，降低這種影響。

我們首先來看，為什麼相關性較強的一些變數會影響隨機森林。在隨機森林的步驟中，有一步是要求每次分裂都從隨機的m個特徵中選擇一特徵作為分裂特徵，這種隨機性就是為了使得樹與樹之間的相關性變低，或者說變得不一樣。如果變數集裡面出現了兩個完全一致（相關性的極端）的變數，那該變數被選到m個變數的機會就會變高，那麼構造出來的樹就會變得越像，樹與樹之間的相關性就會變高，那麼隨機森林的泛化的能力就會變差。換句話說，這些相似的變數擠佔了帶有其他信息的變數入模的機會，從而使得模型變差。

6、有些變數dummy化，有些變數不dummy會對模型有影響嗎

當變數中有缺失值時，我們通常會將變數dummy化，尤其當這個變數是連續變數時，會先簡單離散，再dummy化。那如果某一連續變數沒有缺失值，我們知道cart樹是可以處理缺失值的，這種情況下可以不離散dummy化嗎。

我的答案是不能，因為其他變數dummy化後，意味著其他變數的橫向維度變多了，那麼會影響隨機森林分裂時隨機選取m變數的概率，即沒有dummy化的變數，被選到的可能性會變低，從而影響樹的結構。

引用文章如下：

決策樹演算法原理(上) - 劉建平Pinard - 博客園

使用sklearn進行集成學習--理論 - jasonfreak - 博客園

說說隨機森林

為什麼說bagging是減少variance，而boosting是減少bias?

Selecting good features - Part III: random forests

Bias in random forest variable importance measures: Illustrations, sources and a solution

推薦閱讀：