機器學習_學習筆記系列(39)：極限隨機樹回歸(Extremely Randomized Trees Regressor)
上一篇我們介紹了一個和Random Forest非常相似的演算法Extra Tree，然後我們用其來解決平面二元分類上的問題。而今天我們就要來講Extra Tree如何解決回歸問題。
Extremely Randomized Trees Regressor
回顧上一次我們介紹的Extra Tree Classifier，其和Random Forest一樣以Decision Tree作為Base Learner，然後最後再用Majority Voting結合所有的models。
而Extra Tree和Random Forest不同之處就在於，Random Forest丟進去訓練的資料是隨機抽樣的，所以有可能取到相同的資料，另外在找分割線的時候，他是每種可能性都確認過，然後找一個最佳的結果。而Extra Tree丟進去的訓練資料和原始資料相同，並沒有進行隨機抽樣，但是在找分割線的時候，是隨機產生K種候選值，然後再從這K個裡面選最好的一個。
所以同樣的邏輯搬到解決回歸問題上，我們輸入給Extra Tree Regressor的訓練資料也是和我們的原始資料相同，而在找最佳的回歸切割點的時候，我們一樣也是隨機產生K個候選值，然後根據這K個選項，找出錯誤率最小的值。
對於完整流程，假設我們的資料集D，輸入資料為x，輸出資料為y，總共有N筆，M個特徵。然後我們會在一開始設定我們跑的迴圈次數T，也就是產生T個Base Leaner。
接著我們丟進去Decision Tree進行訓練後，Decision Tree會先呼叫Decision Stump，然後Decision Stump會隨機產生K種組合，如果第一個隨機產生的組合，特徵標記為1，我們就會從x的第一個特徵裡面，從最小值到最大值間隨機產生一個數字。如果第二個隨機產生的組合，特徵標記為3，我們就會從x的第三個特徵裡面，從最小值到最大值間隨機產生一個數字。接下來我們根據這K個組合，找出一個最佳組合，讓其回歸出來的錯誤率最小。
找到最佳組合後Decision Stump就會回傳我們是選擇第幾個特徵作為分割線，然後其數值多少。接下來我們就會根據這個特徵和數值，把當前的資料x和y，拆成兩部分，然後以相同的方式分別將左右兩部分的資料再帶入Decision Tree裡面。而這樣的步驟會直到，我們的樹已達我們設定的最大深度或是左右兩邊的資料都已經達到完美回歸，也就是MSE=0。
對於此我們來比較一下Decision Tree、Random Forest、Extra Tree三種model的效能。
Decision Tree
Random Forest
Extra Tree
接著我們來看三者的MSE
我們可以看到三者雖然在訓練集的表現差不多，但是在測試集的表現Extra Tree的表現明顯的比Decision Tree來得好。
Python Sample Code:
Github:
Reference:
[1] Geurts, P., Ernst, D., & Wehenkel, L. (2006). Extremely randomized trees. Machine learning, 63(1), 3–42.
