筆者介紹
曾擔任零售企業項目負責人，負責企業數據化轉型，數據化管理；曾服務中國移動，負責客服部門產品推薦模型組組長；現於某金融投資公司大數據中心，負責風控數據建設，風控建模工作。在除工作外，也喜歡在DC、DF、天池、Kaggle參加一些比賽。機器學習方面，有一定經驗，願與各位分享我的所見所聞所想，與各位共同進步。
什麼是決策樹？
決策樹，是一種基於特徵的模型，常用的決策樹有ID3、C4.5、CART，可以用來做分類也可以用來做迴歸，和之前將的嶺迴歸，Lasso迴歸，邏輯迴歸不同的是，決策樹是基於特徵的。怎麼理解呢？
迴歸是通過一定的方法（最小二乘法，梯度下降法等），變量需要是連續型，通過擬合變量權重求解。
決策樹是基於離散分類節點，進行決策判斷構建的，所以做決策樹之前就需要把連續變量離散化。也是基於此決策樹不用擬合變量權重，也不用考慮多重共線性。
決策樹
決策樹怎麼構建？
當我們構建決策樹模型時，只需要考慮三個步驟：
1.特徵處理；因為決策樹是基於離散變量的，所以通常情況下需要將連續變量進行離散化，離散化的操作可以考慮分箱的方法，如等頻分箱，等寬分箱，卡方分箱等；（分箱既分類，比如年齡，0-18：少年，18-30：青年，30-50：中年，>50：老年，關於分箱後續也會有專題分享）
2.特徵選擇；將特徵分好類之後，需要選擇特徵，到底哪些特徵應該優先決策，比如醫生想確定這個人的症狀，需要先問哪裡痛？絞痛還是陣痛？特徵選擇一般有信息熵、信息增益、Gini係數。這些都是貪婪算法，貪婪是指他們會找當前選擇下的最佳決策點，無法考慮這個決策點對於整體來說是不是最佳的決策點。
所以決策樹的結果，可能是相對好的結果，但是可能不是最佳結果。
3.決策生成；基於之前的決策點生成決策樹；
4.決策剪枝；如果特徵足夠多，決策樹可能會無限衍生下去，但是當決策枝葉太長，可能會導致過擬合的情況，所以需要進行剪枝來修正結果。包括：
①.預剪枝，通過提前停止樹的構建而對樹剪枝，一旦停止，節點就是樹葉，該樹葉持有子集元祖最頻繁的類。
停止決策樹生長最簡單的方法有：
a.定義一個高度，當決策樹達到該高度時就停止決策樹的生長
b.達到某個節點的實例具有相同的特徵向量，即使這些實例不屬於同一類，也可以停止決策樹的生長。這個方法對於處理數據衝突問題比較有效。
c.定義一個閾值，當達到某個節點的實例個數小於閾值時就可以停止決策樹的生長
d.定義一個閾值，當達到某個節點的實例佔比小於閾值時，就可以停止決策樹的生長
e.定義一個閾值，通過計算每次擴張對系統性能的增益，並比較增益值與該閾值大小來決定是否停止決策樹的生長。
②.後剪枝方法，它首先構造完整的決策樹，允許樹過度擬合訓練數據，然後對那些置信度不夠的結點子樹用葉子結點來代替，該葉子的類標號用該結點子樹中最頻繁的類標記。相比於先剪枝，這種方法更常用，正是因為在先剪枝方法中精確地估計何時停止樹增長很困難。
決策樹的優缺點？
優點：
決策樹易於理解和解釋.人們在通過解釋後都有能力去理解決策樹所表達的意義。
對於決策樹，數據的準備往往是簡單或者是不必要的。 其他的技術往往要求先把數據一般化，比如去掉多餘的或者空白的屬性。
能夠同時處理數據型和常規型屬性。其他的技術往往要求數據屬性的單一
決策樹是一個白盒模型。如果給定一個觀察的模型，那麼根據所產生的決策樹很容易推出相應的邏輯表達式。
易於通過靜態測試來對模型進行評測。表示有可能測量該模型的可信度。
在相對短的時間內能夠對大型數據源做出可行且效果良好的結果。
可以對有許多屬性的數據集構造決策樹。
決策樹可很好地擴展到大型數據庫中，同時它的大小獨立於數據庫的大小。
缺點：
對於那些各類別樣本數量不一致的數據，在決策樹當中,
信息增益的結果偏向於那些具有更多數值的特徵。決策樹處理缺失數據時的困難。
過度擬合問題的出現。
忽略數據集中屬性之間的相關性。
特徵選擇？
決策樹的特徵選擇主要有信息增益、信息增益比、基尼指數。
信息增益（ ID3算法 ）
定義：以某特徵劃分數據集前後的熵的差值
在熵的理解那部分提到了，熵可以表示樣本集合的不確定性，熵越大，樣本的不確定性就越大。因此可以使用劃分前後集合熵的差值來衡量使用當前特徵對於樣本集合D劃分效果的好壞 。
劃分前樣本集合D的熵是一定的 ，entroy(前)，使用某個特徵A劃分數據集D，計算劃分後的數據子集的熵 entroy(後)
信息增益 = entroy(前) - entroy(後)
公式:
做法：計算使用所有特徵劃分數據集D，得到多個特徵劃分數據集D的信息增益，從這些信息增益中選擇最大的，因而當前結點的劃分特徵便是使信息增益最大的劃分所使用的特徵。
信息增益的理解：
對於待劃分的數據集D，其 entroy(前)是一定的，但是劃分之後的熵 entroy(後)是不定的，entroy(後)越小說明使用此特徵劃分得到的子集的不確定性越小（也就是純度越高），因此 entroy(前) - entroy(後)差異越大，說明使用當前特徵劃分數據集D的話，其純度上升的更快。而我們在構建最優的決策樹的時候總希望能更快速到達純度更高的集合，這一點可以參考優化算法中的梯度下降算法，每一步沿著負梯度方法最小化損失函數的原因就是負梯度方向是函數值減小最快的方向。同理：在決策樹構建的過程中我們總是希望集合往最快到達純度更高的子集合方向發展，因此我們總是選擇使得信息增益最大的特徵來劃分當前數據集D。
缺點：信息增益偏向取值較多的特徵
原因：當特徵的取值較多時，根據此特徵劃分更容易得到純度更高的子集，因此劃分之後的熵更低，由於劃分前的熵是一定的，因此信息增益更大，因此信息增益比較 偏向取值較多的特徵。
解決方法 : 信息增益比（ C4.5算法 ）
信息增益比 = 懲罰參數 * 信息增益
公式：
注意：其中的HA(D)，對於樣本集合D，將當前特徵A作為隨機變量（取值是特徵A的各個特徵值），求得的經驗熵。（之前是把集合類別作為隨機變量，現在把某個特徵作為隨機變量，按照此特徵的特徵取值對集合D進行劃分，計算熵HA(D)）
信息增益比本質： 是在信息增益的基礎之上乘上一個懲罰參數。特徵個數較多時，懲罰參數較小；特徵個數較少時，懲罰參數較大。
懲罰參數：數據集D以特徵A作為隨機變量的熵的倒數，即：將特徵A取值相同的樣本劃分到同一個子集中（之前所說數據集的熵是依據類別進行劃分的）
缺點：信息增益比偏向取值較少的特徵
原因： 當特徵取值較少時HA(D)的值較小，因此其倒數較大，因而信息增益比較大。因而偏向取值較少的特徵。
使用信息增益比：基於以上缺點，並不是直接選擇信息增益率最大的特徵，而是現在候選特徵中找出信息增益高於平均水平的特徵，然後在這些特徵中再選擇信息增益率最高的特徵。
基尼指數（ CART算法 ---分類樹）
定義：基尼指數（基尼不純度）：表示在樣本集合中一個隨機選中的樣本被分錯的概率。
注意： Gini指數越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高，反之，集合越不純。
即
基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率公式：
說明:
1. pk表示選中的樣本屬於k類別的概率，則這個樣本被分錯的概率是(1-p
k)2. 樣本集合中有K個類別，一個隨機選中的樣本可以屬於這k個類別中的任意一個，因而對類別就加和
3. 當為二分類是，Gini(P) = 2p(1-p)
樣本集合D的Gini指數 ： 假設集合中有K個類別，則：
基於特徵A劃分樣本集合D之後的基尼指數：
需要說明的是CART是個二叉樹，也就是當使用某個特徵劃分樣本集合只有兩個集合：1. 等於給定的特徵值 的樣本集合D1 ， 2 不等於給定的特徵值 的樣本集合D2
實際上是對擁有多個取值的特徵的二值處理。
舉個例子：
假設現在有特徵 “學歷”，此特徵有三個特徵取值： “本科”，“碩士”， “博士”，當使用“學歷”這個特徵對樣本集合D進行劃分時，劃分值分別有三個，因而有三種劃分的可能集合，劃分後的子集如下：
劃分點： “本科”，劃分後的子集合 ： {本科}，{碩士，博士} 劃分點： “碩士”，劃分後的子集合 ： {碩士}，{本科，博士} 劃分點： “碩士”，劃分後的子集合 ： {博士}，{本科，碩士}對於上述的每一種劃分，都可以計算出基於
劃分特徵= 某個特徵值 將樣本集合D劃分為兩個子集的純度：
因而對於一個具有多個取值（超過2個）的特徵，需要計算以每一個取值作為劃分點，對樣本D劃分之後子集的純度Gini(D,Ai)，(其中Ai 表示特徵A的可能取值)然後從所有的可能劃分的Gini(D,A i)中找出Gini指數最小的劃分，這個劃分的劃分點，便是使用特徵A對樣本集合D進行劃分的最佳劃分點。
信息增益部分借鑑了：https://www.cnblogs.com/muzixi/p/6566803.html
閱讀更多 Ai機器學習 的文章
