引子：決策樹模型（Decision Trees，DTs）是一種非參監(jiān)督式學習模型。它既可以應用于分類問題，也可以應用于回歸問題。它的目標是基于數據屬性找到決定性規(guī)則（decision rules），預測目標值。

概括

優(yōu)點：

－ 模型解釋性好；

－ 訓練需要的數據量??；

－ 既可以處理數值變量（numerical var），也可以處理分類變量（categorical var）；

－ 可以解決多目標問題（multi-output）

如果說大部分機器學習都是黑盒子（black box），那么決策樹絕對是少有的white box model。

缺點：

在bias-variance tradeoff中，它偏向于低bias，高variance，因此模型容易過度擬合（overfitting），并且不穩(wěn)定（unstable）。很大一部分原因，在于它的學習過程采用的幾乎都是貪婪算法（greedy algorithms）。然而這也是不得不的選擇。有證明，尋找最優(yōu)決策樹是一個NP-complete問題（用科普的話說，您的計算能力不足以解決這類問題~），因而，我們找到的也只能是局部最優(yōu)而非全局最優(yōu)。（但我個人的理解，要是數據取樣好，good class balance，或者是big data，比如GB，TB級別，就不怕局部最優(yōu)算法的困擾）

不過，機器學習發(fā)展至今，過度擬合問題已經可以得到很好的解決。比如與boosting 結合的boost tree（ada boost 等）和ensemble learning 模型 random forest，都可以攻克以上的缺點。因此，決策樹及其家族在工業(yè)界和學術界都廣受推崇，并且有很大的貢獻。

下面介紹幾種在決策樹學習過程中廣泛采用的算法。

ID3

全稱Iterative Dichotomiser 3的ID3可謂最流行也最古老的算法，其創(chuàng)始人Ross Quinlan在發(fā)明了ID3后又擴展出了C4.5，C5.0。深入了解ID3之前，需要先引入一個定義：熵（Entropy）

給定一組數據集群set S，并標記label，即它們可分組到class 1,class 2,......class n。定義pi為class i所占的比例。定義entropy為：

在熱力學里，熵越大意味著混亂程度越大；而在統(tǒng)計學里，entropy越大，意味著不確定性uncertainty越大。因此我們希望一個集群S的熵越小越好。而其原理也很簡單，看下圖fun(p): -p*log(p)就可以解釋

如果給定一個規(guī)則A，在規(guī)則A下，數據點都集中在兩個極端，即p->0或者p->1，那么我們就越確定A是一個可信任的規(guī)則，而如果數據是spread out evenly的，則我們這個規(guī)則很可能是錯誤的。

ID3的訓練原理也就如此順其自然的得到了：我們根據attributes依次尋找分割條件使得分割后的各個Partition set si的熵的總和是最小的，即最小化：

其中qi是si的權重（proportion weight）。下面是一棵已經生成的樹：

之所以level這個attribute會被放在第一層layer 1，是因為基于level后將所有數據進行第一次分割后得到的熵是最小的。緊接著基于上個分割后再進行分割，但顯然這是一個貪婪算法，因為這樣的順序下，有一定可能錯過一些更優(yōu)的path。

注：比較多的地方使用的不是minimize entropy而是maximize information gain。而這兩者是一回事，因為information gain = entropy_before _split - entropy_after_split。而entropy_before_split是在沒有該attribute參與前的分類，對每個attribute而言都是一樣的。

C4.5/C5.0

C4.5是對ID3的一些改進，主要在于能處理連續(xù)數值和不完整數據，并且通過引入pruning防止overfitting。同時，它引入了一個information gain ratio的概念，是一種類似歸一化處理。

其中H(Y)就是上文的entropy before split，H(Y|X)就是上文的entropy after split based on attribute X。而H(X)是僅根據attribute X而不考慮label Y進行分割后的entropy。而其對連續(xù)變量的處理，是按照連續(xù)變量的大小從小到大進行排序，假設一共有N個，那么總共有N-1個可能的候選分割閾值點，每個候選的分割閾值點的值為上述排序后的屬性值鏈表中兩兩前后連續(xù)元素的中點。這樣感覺有點暴力搜索。但是也可以做一些優(yōu)化，比如前后兩個值的lable如果是一樣的，就可以不再考慮他們的中點

而C5.0在內存上做了一些優(yōu)化。

CART

CART采用的優(yōu)化方法略有不同。它計算的不是information entropy，而是gini impurity。

廣泛使用的python scikit-learn包采用的就是基于CART算法的決策樹。

Random Forest

在RF之前想提一下的是bagging(bootstrap aggregating的簡稱)。bootstrap是一種常用的方法，其原理也十分簡單，就是有放回的隨機抽樣用于訓練。

所謂隨機森林，顧名思義，就是一群樹。大概有一段時間很流行ensemble learning或者majority voting，從某種程度上可以解決overfitting的問題。隨機森林就是拿一群弱學習器（DTs）進行投票。之所以這里的DTs稱為弱學習器，是因為往往我們只取部分attributes作為input進行學習。

關于隨機森林是不是一種容易過擬合的模型，眾說紛紜；但是一致同意的是，從DT到RF，white box已經被洗黑了(black box).

Boosting

boosting 可謂是決策樹家族發(fā)展最成功的一支。同樣，它也有ensemble learning和majority voting的理念。但是和隨機森林不同的是，它的子樹存在“進化”（evolve）的思想，而且在進化中適應訓練數據，這算是它的核心。

Adaboost是boosting類模型中最為有名的。它的訓練步驟如下：

假如有N個數據值observation，那么一開始，他們用于評價模型error（步驟b）的weights都是1/N，但是在訓練過程中，假如有的數據點（xi，yi）訓練不好，對應的wi就會變大（步驟d)，那么它在下一個子樹Gm會得到更多重視。最后的投票也不是簡單的平均投票，而是根據每個子樹的Alpha值權衡。

XGBoost

如果你混跡Kaggle，那么你就不可能沒聽說過大名鼎鼎的XGBoost。它絕對是幫你上Kaggle排行榜的利器。XGBoost是一個模型，也是一個工具包。它既是boosting算法中比較出類拔萃的，同時工具包提供分布并行計算，可以幫助你加速訓練，所以備受歡迎。我在這里提的是該算法的一些核心思想。至于具體工具包的使用，請參照文末的參考鏈接。

如上所述，boosting的訓練是樹的“進化”，那么進化的方向就可以有很多，xgboost是其中較為巧妙的。假如第一棵樹的訓練目標是原始的（x, y)，那么下一棵樹就可以用于對上一棵樹的修正（x, y-y')，其中y’是上一棵樹的預測值，依次類推，相當于每次都在修正“殘差”。如果你關注deep learning領域的最新研究結果，也能看到一些類似訓練殘差的神經網絡模型。

理想情況下，模型會收斂，即殘差會趨向于零。將每棵樹的結果相加，就是對最原始的目標值y的預測。當然這只是基本的訓練參數。如果你調整一些參數，比如eta，可以給殘差一個權重。同樣，類似于其他的決策樹，你可以選擇什么時候stop（子節(jié)點的數據量小于多少threshold）。

參考鏈接

http://scikit-learn.org/stable/

https://xgboost.readthedocs.io/en/latest/

“Data Science from Scratch”

“The Elements of Statistical Learning”