第十講：Random Forest
1、Random Forest Algorithm
Bagging：通過平均來降低變化量。 Decision Tree：對不同的資料敏感，變化量大。 aggregation of aggregation ：用bagging的方式把一堆decision tree結合起來。
RF = bagging + CART 1、并行化、高效 2、繼承CART的優點 3、消除完全生長CART的overfit缺點
得到有差異性的g： 随機抽取dataset（bagging） 随機抽取feature（低維投影，特征子空間） RF = bagging + 随機特征CART
特征 = 投影矩陣*原始特征 投影到原始方向：特征随機抽取 投影到任意方向：特征結合後随機抽取，more powerful。 原始的RF考慮在 CART每一次分支時 将特征結合起來後低維投影。 RF = bagging + 随機結合特征CART
課後習題： perceptron，特征權重後切分 decision stump，單個特征切分，相當于水準或垂直切分 random-combination，特征結合後 投影， 不隻是垂直、水準，還可能斜的切分
2、Out-Of-Bag Estimate
out-of-bag（OOB） example：沒有被bagging過程選中的資料
有多少OOB Example：N*(1/e)
OOB資料可以用來交叉驗證G bagging的過程可以實作自我交叉驗證：OOB Error
OOB Error做模型選擇 不需要切分訓練集和驗證集，不需要做兩次訓練
3、Feature Selection
有時候想去除： 備援的特征、 無關的特征 特征選擇（事物的雙面性，好處壞處相對應，關鍵是特征選擇的好壞） 好處：高效、更一般化、更具有解釋性 壞處：選取特征的計算量大、過拟合、錯誤的解釋 decision tree自帶特征選擇。
根據重要性選取特征：取Top importance 線性模型的importance：w向量（這時x應該要歸一化才能衡量吧！）
RF的特征選擇：置換檢驗 random test：如果是重要的特征，那麼增加random values，表現會下降 random values： 1、插入均勻分布、高斯分布等資料。缺陷：改變原有特征的資料分布，表現差距=噪音影響+分布影響（不要） 2、boostrap（在原有資料上抽樣）， 置換檢驗（ 在原有資料上 重新随機排列）。分布接近一緻，資料亂掉了。
特征 i 的重要性 = 原始資料的表現 - 特征 i 資料置換後的表現
原始RF特征重要性衡量 一種方法： (1)原始資料，訓練G，在G上用OOB Error衡量表現performance(D)
(2) 原始資料上置換 特征 i的 資料 ，重新訓練G(p) ， 在G (p) 上用 OOB Error衡量表現？performance(D (p) ) (3)importance(i) = performance(D) - performance(D (p) ) 更簡單的方法： (1)原始資料，訓練G， 在G上用OOB Error衡量表現 Eoob(G) (2) OOB example上置換 特征 i的 OOB 資料， 在G上用 OOB Error衡量表現E(p) oob (G) (3)importance(i) = E oob(G) - E(p) oob (G)
3、Random Forest Action
随機特征結合 CART 樹（左圖） bagging的一棵 随機特征結合 CART 樹（中圖，bagging選取中的點比較大） t棵樹的RF（bagging + 随機特征結合 CART 樹）（右圖）
簡單的資料集
樹變多，邊界 變得更加平滑、 更大。
複雜的資料集
很容易就得到了還不錯的非線性模型
有噪音的資料集
樹多了後通過投票把噪音消除，得到穩定的結果
樹越多，表現越好 KDDCup例子：RF的随機性使得表現不穩定，通過增加樹的棵樹來使得它更穩定 RF的缺點：RF是一個随機性的模型，如果随機的過程還沒有到達相對穩定的狀态，或者是對結果的一點點變化很敏感，那麼會受随機過程的影響。 實物上使用RF，要看G是否達到穩定，進而決定是否需要更多的樹。