[原]【機器學習基礎】隨機森林算法

在Bagging算法中，通過bootstrap在原來的數據中進行抽樣，來得到不同的數據集，從而產生不同的g。

在隨機森林的算法中，除了在數據集中做抽取之外，還可以在特征這一角度進行抽取。舉個例子，如果事先我們有100個特征，現在我們可以抽取10個特征來訓練一棵樹，這樣的方式我們也可以得到很不一樣的樹，其對于分類的標準顯然也很不一樣。

這種特征抽取的方式相當于在原來特征的100個維度中，隨機選取10個維度，這等效于一個特征轉換，這個過程中，從100維度到10個維度的轉換中，相當于作了低維度的投影(Projection)。

得到的特征實際上是原始特征的隨機子集，這使得生成模型過程中的效率也大大提高了。

上面介紹的特征投影等效于對原來的特征向量左乘一個投影矩陣Φ(x) = P·x，得到的特征抽樣是隨機選取的原始特征。現在我們可以嘗試更加復雜、有能力的投影方式。

更加有能力的特征投影就是不再單一選取單一維度的特征，而是將多個維度的特征進行組合，得到新的一維的特征，這稱為特征擴展。

在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進行驗證的方法：

接下來要介紹的特征選擇，其目的主要是使用程序來自動選擇需要的特征，而將冗余的、不相關的特征忽略掉。

優點：特征選擇由于舍去了不必要的特征，使得模型復雜度大大降低，可以簡化假設，縮短預測時間；同時，舍去了特征的噪聲，可以提高模型的泛化能力，使得模型不容易對噪聲過擬合；最后，由于選擇出來的特征具有很好的物理意義，其結果可以作很好的解釋。

缺點：特征的選擇計算量大；如果選出來的特征是噪聲的話，可能會導致過擬合；如果選擇了噪聲特征，得到的解釋可能只是數據之中的關聯性，而非因果性。

Permutation Test的方法是通過將第i個維度特征的所有數據重新的隨機調整位置，然后比較一下原始數據和調整之后的數據表現的差距，來評價這個維度的特征是有多么重要。

在隨機森林中可以用OOB代替驗證的過程，為了簡化Permutation Test帶來的重新進行訓練的代價，我們在使用OOB Example（bootstrap過程中沒有選取的數據）進行驗證的過程中做一些修改，即在驗證的時候去進行Permutation Test，而非訓練時進行。

在求Eoob(G)時，我們通過G-(xn)來計算，我們在這里將x(n)修改成x(n,i)，就可以不用對G進行修改了。

在實際應用中，面對非線性的問題時，可以通過隨機森林的方法來進行初步的特征選擇。