RECAP:
在決策樹中，在一組數(shù)據(jù)中，根據(jù)每個(gè)特征的信息增益睬澡，決定應(yīng)該如何來進(jìn)行CRT的樹枝分叉。在是否貸款的case中眠蚂，以"是否有房"煞聪， "是否有工作" 作為第一輪和第二輪的特征，進(jìn)行分叉逝慧。而進(jìn)行到full decision tree的時(shí)候昔脯，發(fā)現(xiàn)“年齡”，“信貸情況”笛臣，并沒有用的上云稚，這兩個(gè)特征是冗余的特征。
那么沈堡，如何將bagging和decision tree進(jìn)行結(jié)合呢静陈？
Random Forest
Random Forest 就是將多個(gè)decision tree 進(jìn)行bagging的組合。需要解決2個(gè)問題：
1. 資料從哪來
2. 特征從哪來
第一個(gè)問題诞丽，之前已經(jīng)有bootstrapping鲸拥。采用抽取放回的方式進(jìn)行資料的抽取。在一組原始資料里率拒，有大約1/e崩泡，約1/3的資料取不到。
第二個(gè)問題猬膨，還是采用bootstrapping的方式，每次對特征進(jìn)行隨機(jī)選取。
這樣勃痴，每組資料和特征都不完全相同谒所，每組資料和特征都可以進(jìn)行decision tree的計(jì)算，這些decision tree都可以并行進(jìn)行沛申，提高了效率劣领。計(jì)算完成后，都可以得到一棵full decision tree铁材，然后按照bagging的方式尖淘，進(jìn)行uniform的結(jié)合，得到第一次迭代的Random Forest著觉。
OOB的方式進(jìn)行self-validation
由于在N筆資料中進(jìn)行bootstrapping村生，對于抽取到的資料，可以進(jìn)行training饼丘，未抽取到的資料（OOB）趁桃，進(jìn)行validation。在進(jìn)行validation的時(shí)候肄鸽，關(guān)心的是Gt而非gt卫病。因此需要用OOB的資料對Gt進(jìn)行Validation。怎么做典徘？
1. 找出每個(gè)Random Forest對應(yīng)的OOB資料
2. 計(jì)算一個(gè)decision tree的OOB蟀苛。例如（x1,y1）可以對g2進(jìn)行validation；（xn,yn）可以對g2,g3,gT進(jìn)行validation. 那么記做：
這種做法我們并不陌生逮诲，就像是我們之前介紹過的Leave-One-Out Cross Validation帜平，每次只對一個(gè)樣本進(jìn)行g(shù)?的驗(yàn)證一樣，只不過這里選擇的是每個(gè)樣本是哪些gt?的OOB汛骂，然后再分別進(jìn)行Gn??(x)的驗(yàn)證罕模。每個(gè)樣本都當(dāng)成驗(yàn)證資料一次（與留一法相同），最后計(jì)算所有樣本的平均表現(xiàn)：
Eoob?(G)估算的就是G的表現(xiàn)好壞帘瞭。我們把 Eoob?稱為bagging或者Random Forest的self-validation淑掌。 self-validation在調(diào)整隨機(jī)森林算法相關(guān)系數(shù)并得到最小的 Eoob?之后，就完成了整個(gè)模型的建立蝶念，無需重新訓(xùn)練模型抛腕。隨機(jī)森林算法中，self-validation在衡量G的表現(xiàn)上通常相當(dāng)準(zhǔn)確媒殉。
機(jī)器學(xué)習(xí)：隨機(jī)森林RF-OOB袋外錯(cuò)誤率
https://blog.csdn.net/wishchin/article/details/52515516?
Feature selection
例如decision tree的例子中担敌，“年齡”，“信貸情況”廷蓉，并沒有用的上全封，這兩個(gè)特征是冗余的特征。那么如何在d個(gè)特征中找出個(gè)特征呢？
1. 線性關(guān)系中刹悴，使用 |w|來表示特征的重要性行楞。重要性大的，w的絕對值就大
2. 在非線性關(guān)系土匀，例如random forest中子房，使用Permutation Test來衡量特征的重要性
RF中，特征選擇的核心思想是random test就轧。random test的做法是對于某個(gè)特征证杭，如果用另外一個(gè)隨機(jī)值替代它之后的表現(xiàn)比之前更差，則表明該特征比較重要妒御，所占的權(quán)重應(yīng)該較大解愤，不能用一個(gè)隨機(jī)值替代。相反携丁，如果隨機(jī)值替代后的表現(xiàn)沒有太大差別琢歇，則表明該特征不那么重要，可有可無梦鉴。所以李茫，通過比較某特征被隨機(jī)值替代前后的表現(xiàn)，就能推斷出該特征的權(quán)重和重要性肥橙。
那么random test中的隨機(jī)值如何選擇呢魄宏？通常有兩種方法：一是使用uniform或者Gaussian抽取隨機(jī)值替換原特征；一是通過permutation的方式將原來的所有N個(gè)樣本的第i個(gè)特征值重新打亂分布（相當(dāng)于重新洗牌）存筏。比較而言宠互，第二種方法更加科學(xué)，保證了特征替代值與原特征的分布是近似的（只是重新洗牌而已）椭坚。這種方法叫做permutation test（隨機(jī)排序測試）予跌，即在計(jì)算第i個(gè)特征的重要性的時(shí)候，將N個(gè)樣本的第i個(gè)特征重新洗牌善茎，然后比較D和D^{(p)}表現(xiàn)的差異性券册。如果差異很大，則表明第i個(gè)特征是重要的垂涯。
知道了permutation test的原理后烁焙，接下來要考慮的問題是如何衡量上圖中的performance，即替換前后的表現(xiàn)耕赘。顯然骄蝇，我們前面介紹過performance可以用Eoob?(G)來衡量。但是操骡，對于N個(gè)樣本的第i個(gè)特征值重新洗牌重置的D(p)九火，要對它進(jìn)行重新訓(xùn)練赚窃，而且每個(gè)特征都要重復(fù)訓(xùn)練，然后再與原D的表現(xiàn)進(jìn)行比較吃既，過程非常繁瑣考榨。為了簡化運(yùn)算跨细，RF的作者提出了一種方法鹦倚，就是把permutation的操作從原來的training上移到了OOB validation上去，記為
也就是說冀惭，在訓(xùn)練的時(shí)候仍然使用D震叙，但是在OOB驗(yàn)證的時(shí)候，將所有的OOB樣本的第i個(gè)特征重新洗牌散休，驗(yàn)證G的表現(xiàn)媒楼。這種做法大大簡化了計(jì)算復(fù)雜度，在RF的feature selection中應(yīng)用廣泛戚丸。
Permutation Test 置換檢驗(yàn)(轉(zhuǎn)）
