決策樹模型組合之随機森林（Random Forest）

在機器學習中，随機森林由許多的決策樹組成，因為這些決策樹的形成采用了随機的方法，是以叫做随機森林。随機森林中的決策樹之間是沒有關聯的，當測試資料進入随機森林時，其實就是讓每一顆決策樹進行分類看看這個樣本應該屬于哪一類，最後取所有決策樹中分類結果最多的那類為最終的結果（每棵樹的權重要考慮進來）。所有的樹訓練都是使用同樣的參數，但是訓練集是不同的，分類器的錯誤估計采用的是oob（out of bag）的辦法。是以随機森林是一個包含多個決策樹的分類器，并且其輸出的類别是由個别樹輸出的類别的衆數而定。随機森林可以既可以處理屬性為離散值的量，如ID3算法，也可以處理屬性為連續值的量，比如C4.5算法。另外，随機森林還可以用來進行無監督學習聚類和異常點檢測。

随機森林的建立

基本就是兩個步驟：随機采樣與完全分裂。

（1）随機采樣

首先是兩個随機采樣的過程，random forest對輸入的資料要進行行、列的采樣。

對于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重複的樣本。假設輸入樣本為N個，那麼采樣的樣本也為N個，這選擇好了的N個樣本用來訓練一個決策樹，作為決策樹根節點處的樣本，同時使得在訓練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現over-fitting。

對于列采樣，從M個feature中，選擇m個(m << M)，即：當每個樣本有M個屬性時，在決策樹的每個節點需要分裂時，随機從這M個屬性中選取出m個屬性，滿足條件m << M。

（2）完全分裂

對采樣之後的資料使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節點要麼是無法繼續分裂的，要麼裡面的所有樣本的都是指向的同一個分類。分裂的辦法是：采用上面說的列采樣的過程從這m個屬性中采用某種政策（比如說資訊增益）來選擇1個屬性作為該節點的分裂屬性。

決策樹形成過程中每個節點都要按完全分裂的方式來分裂，一直到不能夠再分裂為止（如果下一次該節點選出來的那一個屬性是剛剛其父節點分裂時用過的屬性，則該節點已經達到了葉子節點，無須繼續分裂了）。

我們用LearnUnprunedTree(X,Y)表示生成一棵未剪枝的決策樹的過程，以下簡寫LUT (X,Y)：

随機森林的優點

總結如下：

（1）比較适合做多分類問題，訓練和預測速度快，在資料集上表現良好；

（2）對訓練資料的容錯能力強，是一種有效地估計缺失資料的一種方法，當資料集中有大比例的資料缺失時仍然可以保持精度不變和能夠有效地處理大的資料集；

（3）能夠處理很高次元的資料，并且不用做特征選擇，即：可以處理沒有删減的成千上萬的變量；

（4）能夠在分類的過程中可以生成一個泛化誤差的内部無偏估計；

（5）能夠在訓練過程中檢測到特征之間的互相影響以及特征的重要性程度；

（6）不會出現過度拟合；

（7）實作簡單并且容易實作并行化。

C/C++基本文法學習

STL

C++ primer