機器學習_學習筆記系列(38)：極限隨機樹分類(Extremely Randomized Trees Classifier)
前兩篇我們介紹了Random Forest Classifier & Regressor，其是用Decision Tree做為Base Learner用Bagging的方式訓練出來的。而在這邊我們要來介紹一個和Random Forest很相似的演算法「Extremely Randomized Trees」。
Extremely Randomized Trees
對於Extremely Randomized Trees，我們通常又會簡稱為Extra Tree，其是2006年，由三位電腦科學家Pierre Geurts、Damien Ernst、Louis Wehenkel所提出，其論文[1]名稱就叫做：
Extremely randomized trees
對於Extra Tree的演算法核心概念，其實和Random Forest很像，他們都會用迴圈產生T個Decision Tree然後再把這T個Base Leaner結合起來。對於他們的差別在於
1. Random Forest中訓練每個Decision Tree的時候，訓練資料是隨機挑選且資料可重複的，而Extra Tree訓練每個Decision Tree的時候，訓練資料和原始資料相同。
2. Random Forest中的Decision Tree在找最適當的切割線的時候，是從當前的Node底下找出一個impurity值最低的解，而Extra Tree中的Decision Tree在找最適當的切割線的時候，是隨機產生K個切割線然後從K條線中選出一個impurity值最低的解。
所以說我們可以從第二個差別看到，假使我們今天有N筆資料，每筆資料有M個特徵，如果今天用Random Forest的方法，如果要找到最佳切割線，總共要計算M(N-1)次，如果是Extra Tree的方法，我們只要做K次。
想像一下如果我們今天的資料量非常龐大，有一百萬筆，然後每筆又有十個特徵，如果用Random Forest的方法，那不是在第一回找分割點的時候，就要做9999990次運算嗎。所以如果運用Extra Tree我們可以大大的把建立一個Node所需的運算次數降到K次。
接下來我們用Python實現演算法，在這裡我們一樣以平面二元分類為例子，然後Base Learner設為9個。
Random Forest
Extra Tree
我們可以看到雖然Extra Tree產生分割線的方式是隨機的，但是整體來講，其還是可以大致上抓到趨勢。再來我們來看其總體表現
我們可以看到運用Ensemble Learning的方式，其訓練集和測試集的表現都比使用單一個Decision Tree來得好。而我們可以特別注意Extra Tree的執行時間，因為其式隨機挑選分割線，所以其執行時間比Random Forest的一半還要少。
Python Sample Code:
Github:
Reference:
[1] Geurts, P., Ernst, D., & Wehenkel, L. (2006). Extremely randomized trees. Machine learning, 63(1), 3–42.
