引子：決策樹模型（Decision Trees敬鬓，DTs）是一種非參監(jiān)督式學習模型。它既可以應用于分類問題笙各，也可以應用于回歸問題钉答。它的目標是基于數(shù)據(jù)屬性找到?jīng)Q定性規(guī)則（decision rules），預測目標值杈抢。
概括
優(yōu)點：
－ 模型解釋性好数尿；
－ 訓練需要的數(shù)據(jù)量小惶楼；
－ 既可以處理數(shù)值變量（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)筹陵。（但我個人的理解刽锤，要是數(shù)據(jù)取樣好镊尺，good class balance，或者是big data并思，比如GB庐氮，TB級別，就不怕局部最優(yōu)算法的困擾）
不過宋彼，機器學習發(fā)展至今弄砍，過度擬合問題已經(jīng)可以得到很好的解決。比如與boosting 結(jié)合的boost tree（ada boost 等）和ensemble learning 模型 random forest输涕，都可以攻克以上的缺點音婶。因此，決策樹及其家族在工業(yè)界和學術(shù)界都廣受推崇莱坎，并且有很大的貢獻衣式。
下面介紹幾種在決策樹學習過程中廣泛采用的算法。
ID3
全稱Iterative Dichotomiser 3的ID3可謂最流行也最古老的算法檐什，其創(chuàng)始人Ross Quinlan在發(fā)明了ID3后又擴展出了C4.5碴卧，C5.0。深入了解ID3之前乃正，需要先引入一個定義：熵（Entropy）
給定一組數(shù)據(jù)集群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下帅掘，數(shù)據(jù)點都集中在兩個極端，即p->0或者p->1堂油，那么我們就越確定A是一個可信任的規(guī)則修档，而如果數(shù)據(jù)是spread out evenly的，則我們這個規(guī)則很可能是錯誤的府框。
ID3的訓練原理也就如此順其自然的得到了：我們根據(jù)attributes依次尋找分割條件使得分割后的各個Partition set si的熵的總和是最小的吱窝，即最小化：
其中qi是si的權(quán)重（proportion weight）。下面是一棵已經(jīng)生成的樹：
之所以level這個attribute會被放在第一層layer 1，是因為基于level后將所有數(shù)據(jù)進行第一次分割后得到的熵是最小的院峡。緊接著基于上個分割后再進行分割兴使，但顯然這是一個貪婪算法，因為這樣的順序下照激，有一定可能錯過一些更優(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ù)數(shù)值和不完整數(shù)據(jù)，并且通過引入pruning防止overfitting啄清。同時六水，它引入了一個information gain ratio的概念，是一種類似歸一化處理辣卒。
其中H(Y)就是上文的entropy before split掷贾，H(Y|X)就是上文的entropy after split based on attribute X。而H(X)是僅根據(jù)attribute X而不考慮label Y進行分割后的entropy荣茫。而其對連續(xù)變量的處理想帅，是按照連續(xù)變量的大小從小到大進行排序，假設(shè)一共有N個啡莉，那么總共有N-1個可能的候選分割閾值點港准，每個候選的分割閾值點的值為上述排序后的屬性值鏈表中兩兩前后連續(xù)元素的中點。這樣感覺有點暴力搜索咧欣。但是也可以做一些優(yōu)化浅缸，比如前后兩個值的lable如果是一樣的，就可以不再考慮他們的中點
而C5.0在內(nèi)存上做了一些優(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進行學習腊尚。
關(guān)于隨機森林是不是一種容易過擬合的模型，眾說紛紜满哪；但是一致同意的是婿斥，從DT到RF，white box已經(jīng)被洗黑了(black box).
Boosting
boosting 可謂是決策樹家族發(fā)展最成功的一支哨鸭。同樣民宿，它也有ensemble learning和majority voting的理念。但是和隨機森林不同的是故慈，它的子樹存在“進化”（evolve）的思想顽照，而且在進化中適應訓練數(shù)據(jù)胁镐，這算是它的核心。
Adaboost是boosting類模型中最為有名的志群。它的訓練步驟如下：
假如有N個數(shù)據(jù)值observation，那么一開始蛔钙，他們用于評價模型error（步驟b）的weights都是1/N锌云，但是在訓練過程中，假如有的數(shù)據(jù)點（xi吁脱，yi）訓練不好桑涎，對應的wi就會變大（步驟d)，那么它在下一個子樹Gm會得到更多重視兼贡。最后的投票也不是簡單的平均投票石洗，而是根據(jù)每個子樹的Alpha值權(quán)衡。
XGBoost
如果你混跡Kaggle紧显，那么你就不可能沒聽說過大名鼎鼎的XGBoost讲衫。它絕對是幫你上Kaggle排行榜的利器。XGBoost是一個模型孵班，也是一個工具包涉兽。它既是boosting算法中比較出類拔萃的，同時工具包提供分布并行計算篙程，可以幫助你加速訓練枷畏，所以備受歡迎。我在這里提的是該算法的一些核心思想虱饿。至于具體工具包的使用拥诡，請參照文末的參考鏈接触趴。
如上所述，boosting的訓練是樹的“進化”渴肉，那么進化的方向就可以有很多冗懦，xgboost是其中較為巧妙的。假如第一棵樹的訓練目標是原始的（x, y)仇祭，那么下一棵樹就可以用于對上一棵樹的修正（x, y-y')披蕉，其中y’是上一棵樹的預測值，依次類推乌奇，相當于每次都在修正“殘差”没讲。如果你關(guān)注deep learning領(lǐng)域的最新研究結(jié)果，也能看到一些類似訓練殘差的神經(jīng)網(wǎng)絡(luò)模型礁苗。
理想情況下爬凑，模型會收斂，即殘差會趨向于零试伙。將每棵樹的結(jié)果相加贰谣，就是對最原始的目標值y的預測。當然這只是基本的訓練參數(shù)迁霎。如果你調(diào)整一些參數(shù)吱抚，比如eta，可以給殘差一個權(quán)重考廉。同樣秘豹，類似于其他的決策樹，你可以選擇什么時候stop（子節(jié)點的數(shù)據(jù)量小于多少threshold）昌粤。
參考鏈接
http://scikit-learn.org/stable/
https://xgboost.readthedocs.io/en/latest/
“Data Science from Scratch”
“The Elements of Statistical Learning”
