1 Random Forest Algorithm
首先我們來複習一下之前介紹過的兩個機器學習模型：Bagging和Decision Tree。Bagging是通過bootstrap的方式，從原始的資料集D中得到新的D^；然後再使用一些base algorithm對每個D^都得到相應的gt；最後将所有的gt通過投票uniform的形式組合成一個G，G即為我們最終得到的模型。Decision Tree是通過遞歸形式，利用分支條件，将原始資料集D切割成一個個子樹結構，長成一棵完整的樹形結構。Decision Tree最終得到的G(x)是由相應的分支條件b(x)和分支樹Gc(x)遞歸組成。
Bagging和Decison Tree算法各自有一個很重要的特點。Bagging具有減少不同gt的方差variance的特點。這是因為Bagging采用投票的形式，将所有gt uniform結合起來，起到了求平均的作用，進而降低variance。而Decision Tree具有增大不同gt的方差variance的特點。這是因為Decision Tree每次切割的方式不同，而且分支包含的樣本數在逐漸減少，是以它對不同的資料D會比較敏感一些，進而不同的D會得到比較大的variance。
是以說，Bagging能減小variance，而Decision Tree能增大variance。如果把兩者結合起來，能否發揮各自的優勢，起到優勢互補的作用呢？這就是我們接下來将要讨論的aggregation of aggregation，即使用Bagging的方式把衆多的Decision Tree進行uniform結合起來。這種算法就叫做随機森林（Random Forest），它将完全長成的C&RT決策樹通過bagging的形式結合起來，最終得到一個龐大的決策模型。
2 Out-Of-Bag Estimate
上一部分我們已經介紹了Random Forest算法，而Random Forest算法重要的一點就是Bagging。接下來将繼續探讨bagging中的bootstrap機制到底蘊含了哪些可以為我們所用的東西。
通過bootstrap得到新的樣本集D’，再由D’訓練不同的gt。我們知道D’中包含了原樣本集D中的一些樣本，但也有些樣本沒有涵蓋進去。如下表所示，不同的gt下，紅色的表示沒有這些樣本。例如對g1來說，(x2,y2)和(x3,y4)沒有包含進去，對g2來說，(x1,y1)和(x2,y2)沒有包含進去，等等。每個gt中，紅色表示的樣本被稱為out-of-bag(OOB) example。
其中，e是自然對數，N是原樣本集的數量。由上述推導可得，每個gt中，OOB數目大約是N/e，即大約有三分之一的樣本沒有在bootstrap中被抽到。
然後，我們将OOB與之前介紹的Validation進行對比：
3 Feature Selection
如果樣本資料特征過多，假如有10000個特征，而我們隻想從中選取300個特征，這時候就需要舍棄部分特征。通常來說，需要移除的特征分為兩類：一類是備援特征，即特征出現重複，例如“年齡”和“生日”；另一類是不相關特征，例如疾病預測的時候引入的“保險狀況”。這種從d維特征到d’維特征的subset-transform Φ(x)稱為Feature Selection，最終使用這些d’維的特征進行模型訓練。
- 提高效率，特征越少，模型越簡單
- 正則化，防止特征過多出現過拟合
- 去除無關特征，保留相關性大的特征，解釋性強
同時，特征選擇的缺點是：
- 篩選特征的計算量較大
- 不同特征組合，也容易發生過拟合
- 容易選到無關特征，解釋性差
-
通俗解釋随機森林算法
值得一提的是，在decision tree中，我們使用的decision stump切割方式也是一種feature selection。
那麼，如何對許多元特征進行篩選呢？我們可以通過計算出每個特征的重要性（即權重），然後再根據重要性的排序進行選擇即可。
這種方法線上性模型中比較容易計算。因為線性模型的score是由每個特征經過權重求和而得到的，而權重系數的絕對值|wi|正好代表了對應特征xi的重要性為多少。|wi|越大，表示對應特征xi越重要，則該特征應該被選擇。w的值可以通過對已有的資料集(xi,yi)建立線性模型而得到。
然而，對于非線性模型來說，因為不同特征可能是非線性交叉在一起的，是以計算每個特征的重要性就變得比較複雜和困難。例如，Random Forest就是一個非線性模型，接下來，我們将讨論如何在RF下進行特征選擇。
RF中，特征選擇的核心思想是random test。random test的做法是對于某個特征，如果用另外一個随機值替代它之後的表現比之前更差，則表明該特征比較重要，所占的權重應該較大，不能用一個随機值替代。相反，如果随機值替代後的表現沒有太大差别，則表明該特征不那麼重要，可有可無。是以，通過比較某特征被随機值替代前後的表現，就能推斷出該特征的權重和重要性。
那麼random test中的随機值如何選擇呢？通常有兩種方法：一是使用uniform或者gaussian抽取随機值替換原特征；一是通過permutation的方式将原來的所有N個樣本的第i個特征值重新打亂分布（相當于重新洗牌）。比較而言，第二種方法更加科學，保證了特征替代值與原特征的分布是近似的（隻是重新洗牌而已）。這種方法叫做permutation test（随機排序測試），即在計算第i個特征的重要性的時候，将N個樣本的第i個特征重新洗牌，然後比較D和D(p)表現的差異性。如果差異很大，則表明第i個特征是重要的。
4 Random Forest in Action
最後，我們通過實際的例子來看一下RF的特點。首先，仍然是一個二進制分類的例子。如下圖所示，左邊是一個C&RT樹沒有使用bootstrap得到的模型分類效果，其中不同特征之間進行了随機組合，是以有斜線作為分類線；中間是由bootstrap（N’=N/2）後生成的一棵決策樹組成的随機森林，圖中加粗的點表示被bootstrap選中的點；右邊是将一棵決策樹進行bagging後的分類模型，效果與中間圖是一樣的，都是一棵樹。
當t=100，即選擇了100棵樹時，中間的模型是第100棵決策樹構成的，還是隻有一棵樹；右邊的模型是由100棵決策樹bagging起來的，如下圖所示：
随着樹木個數的增加，我們發現，分界線越來越光滑而且得到了large-margin-like boundary，類似于SVM一樣的效果。也就是說，樹木越多，分類器的置信區間越大。
然後，我們再來看一個比較複雜的例子，二維平面上分布着許多離散點，分界線形如sin函數。當隻有一棵樹的時候（t=1），下圖左邊表示單一樹組成的RF，右邊表示所有樹bagging組合起來構成的RF。因為隻有一棵樹，是以左右兩邊效果一緻。
可以看到，當RF由21棵樹構成的時候，分界線就比較平滑了，而且它的邊界比單一樹構成的RF要robust得多，更加平滑和穩定。
最後，基于上面的例子，再讓問題複雜一點：在平面上添加一些随機噪聲。當t=1時，如下圖所示：
從上圖中，我們發現21棵樹的時候，随機noise的影響基本上能夠修正和消除。這種bagging投票的機制能夠保證較好的降噪性，進而得到比較穩定的結果。
經過以上三個例子，我們發現RF中，樹的個數越多，模型越穩定越能表現得好。在實際應用中，應該盡可能選擇更多的樹。值得一提的是，RF的表現同時也與random seed有關，即随機的初始值也會影響RF的表現。
5 Summary
本文主要介紹了Random Forest算法模型。RF将bagging與decision tree結合起來，通過把衆多的決策樹組進行組合，構成森林的形式，利用投票機制讓G表現最佳，分類模型更穩定。其中為了讓decision tree的随機性更強一些，可以采用randomly projected subspaces操作，即将不同的features線性組合起來，進而進行各式各樣的切割。同時，我們也介紹了可以使用OOB樣本來進行self-validation，然後可以使用self-validation來對每個特征進行permutaion test，得到不同特征的重要性，進而進行feature selection。總的來說，RF算法能夠得到比較平滑的邊界，穩定性強，前提是有足夠多的樹。