引入
我們回顧一下之前學習的兩個算法连霉，Bagging算法中榴芳，通過bootstrapping得到不一樣的數據，通過這些數據送到一個基本算法之后跺撼，得到不同的g窟感，最后對這些g取平均得到G；決策樹算法中歉井，通過遞歸方式建立子樹柿祈，最終得到一棵完整的樹。
這兩種算法都有其鮮明的特點哩至，決策樹對于不同的數據相對會敏感一些躏嚎，即其算法的variance很大，而Bagging的特點是通過投票和平均的方式來降低variance的效果菩貌。如果將這兩種方法結合起來卢佣，就是該文要介紹的隨機森林，random forest菜谣。
1. 隨機森林算法
隨機森立算法中的“隨機”一詞是指通過Bagging中的bootstrapping得到不同的數據珠漂，進而體現出來的隨機性，而得到這筆數據用來送進CART算法訓練得到一棵樹尾膊，最后將所得的樹做平均得到最終結果媳危。
并行計算的可能性：隨機森林算法從Bagging過程中可以分配到不同的計算機中進行計算，每臺計算機可以獨立學習一棵樹冈敛，不同的樹之間沒有任何依賴關系待笑。這使得Bagging過程很容易實現并行化。
2. 特征投影(Feature Projection)
在Bagging算法中抓谴，通過bootstrap在原來的數據中進行抽樣暮蹂，來得到不同的數據集，從而產生不同的g癌压。
在隨機森林的算法中仰泻，除了在數據集中做抽取之外，還可以在特征這一角度進行抽取滩届。舉個例子集侯，如果事先我們有100個特征，現在我們可以抽取10個特征來訓練一棵樹，這樣的方式我們也可以得到很不一樣的樹棠枉，其對于分類的標準顯然也很不一樣浓体。
這種特征抽取的方式相當于在原來特征的100個維度中，隨機選取10個維度辈讶，這等效于一個特征轉換命浴，這個過程中，從100維度到10個維度的轉換中贱除，相當于作了低維度的投影(Projection)生闲。
得到的特征實際上是原始特征的隨機子集，這使得生成模型過程中的效率也大大提高了勘伺。
3. 特征擴展(Feature Expansion)
上面介紹的特征投影等效于對原來的特征向量左乘一個投影矩陣Φ(x) = P·x跪腹，得到的特征抽樣是隨機選取的原始特征。現在我們可以嘗試更加復雜飞醉、有能力的投影方式冲茸。
更加有能力的特征投影就是不再單一選取單一維度的特征，而是將多個維度的特征進行組合缅帘，得到新的一維的特征轴术，這稱為特征擴展。
4. Out-Of-Bag Estimate
在bootstrapping的過程中钦无，有些數據可能沒有被選擇逗栽，這些數據稱為out-of-bag(OOB) examples，對于訓練每一個gt失暂，其中用“”標注的數據即是gt的OOB examples彼宠。
下面的公式是經過N'次選擇之后沒有被選擇的數據，大約有(1/e)N多的數據沒有被選擇到弟塞，即大約有三分之一的數據沒有被選擇凭峡，這些數據由于沒有用來訓練模型，故可以用于模型的驗證决记。
在隨機森林的算法中摧冀，我們不太需要使用OOB數據來驗證每個g的性能，因為即使g的能力很差系宫，最終進行平均得到的G的性能也可能會很好索昂。但這些OOB數據可以用來驗證G的性能。
上圖中扩借，(xN,yN)這一個數據由于沒有用于g2椒惨，g3，gT的訓練數據潮罪，故可以用來作為它們的驗證數據框产。所以(xN,yN)可以作為G-的驗證數據凄杯，其中
G-(x)=average(g2, g3, gT)。下面給出了OOB Error（Eoob）的公式秉宿，G的OOB Error的估算是通過不同的G-來平均得到的，所以屯碴，在bootstrap的過程就可以自己去驗證模型的性能好壞描睦，不需要單獨劃分一塊數據作為專門的驗證數據。
下面是隨機森林算法中使用OOB Error進行驗證的方法：
5. 特征選擇(Feature Selection)
接下來要介紹的特征選擇导而，其目的主要是使用程序來自動選擇需要的特征忱叭，而將冗余的、不相關的特征忽略掉今艺。
優(yōu)點：特征選擇由于舍去了不必要的特征韵丑，使得模型復雜度大大降低，可以簡化假設虚缎，縮短預測時間撵彻；同時，舍去了特征的噪聲实牡，可以提高模型的泛化能力陌僵，使得模型不容易對噪聲過擬合；最后创坞，由于選擇出來的特征具有很好的物理意義碗短，其結果可以作很好的解釋。
缺點：特征的選擇計算量大题涨；如果選出來的特征是噪聲的話偎谁，可能會導致過擬合；如果選擇了噪聲特征纲堵，得到的解釋可能只是數據之中的關聯性巡雨，而非因果性。
5.1 Permutation Test
上面說的特征選擇是如何選擇特征的組合方式的問題婉支，為了解決這個問題鸯隅，我們暫不考慮特征之間的相關關系，而是為每個特征打一個分數向挖，表示特征的重要性蝌以，然后按照重要性進行排序，選擇最重要的前K個特征作為選取出來的特征何之。
由于隨機森林算法是一個非線性的模型跟畅，我們不能單純以線性模型中的權重作為衡量特征重要性的標準，所以下面要介紹的稱為Permutation Test的方法來判別特征的權重溶推。
Permutation Test的方法是通過將第i個維度特征的所有數據重新的隨機調整位置徊件，然后比較一下原始數據和調整之后的數據表現的差距奸攻，來評價這個維度的特征是有多么重要。
5.2 在Out-Of-Bag Estimate過程中做Permutation Test
在隨機森林中可以用OOB代替驗證的過程虱痕，為了簡化Permutation Test帶來的重新進行訓練的代價睹耐，我們在使用OOB Example（bootstrap過程中沒有選取的數據）進行驗證的過程中做一些修改，即在驗證的時候去進行Permutation Test部翘，而非訓練時進行硝训。
在求Eoob(G)時，我們通過G-(xn)來計算新思，我們在這里將x(n)修改成x(n,i)窖梁，就可以不用對G進行修改了。
在實際應用中夹囚，面對非線性的問題時纵刘，可以通過隨機森林的方法來進行初步的特征選擇。
參考資料
機器學習技法課程荸哟，林軒田假哎，臺灣大學
轉載請注明作者Jason Ding及其出處
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
Github博客主頁(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進入我的博客主頁
