決策樹算法模型的歸類與整理（ID３＆C４.５＆CART＆線性二分類＆非線性二分類）
一、 總結摘要
決策樹模型在監督學習中非常常見，可用于分類（二分類、多分類）和回歸。雖然将多棵弱決策樹的Bagging、Random Forest、Boosting等tree ensembel 模型更為常見，但是“完全生長”決策樹因為其簡單直覺，具有很強的解釋性，也有廣泛的應用，而且決策樹是tree ensemble 的基礎。一般而言一棵“完全生長”的決策樹包含，特征選擇、決策樹建構、剪枝（包括預剪枝和後剪枝）三個過程，接下來我将簡要地梳理并比較ID3、C4.5、CART這3個算法。
例如上圖即為一棵簡單的決策樹模型，可以用來簡單判定并預測一位女孩是否要去見她的相親對象，這個過程與評判标準即可用上面的決策樹模型來加以輔助判定。
決策樹的優點與缺點
優點：
- 決策樹算法中簡單的決策規則建立決策樹模型的過程非常容易了解；
- 決策樹模型可以可視化，非常直覺；
- 應用範圍廣，可用于分類和回歸，而且非常容易做多類别的分類；
-
能夠處理數值型和連續的樣本特征。它比較适合分析離散型資料，若資料為連續型，則要先轉換成離散的資料再進行分析。
缺點：
- 很容易在訓練資料中生成複雜的樹結構，造成過拟合情況（overfitting）。剪枝可以緩解過拟合帶來的的負作用，常用方法是限制樹的高度、葉子節點中的最少樣本數量；
-
學習一棵最優的決策樹被認為是NP-Complete問題。實際中的決策樹是基于啟發式的貪心算法建立的，但這種算法不能保證建立全局最優的決策樹。Random Forest 引入随機能緩解這個問題。
時間複雜度與空間複雜度分析
時間複雜度O(NMD)：O(NMD), N是sample的大小，M是feature的數量，D是樹的深度。cart生長時，把所有feature内的值都作為分裂候選，并為其計算一個評價名額（資訊增益、增益比率、gini系數等），是以每層是O(NM)，D層的樹就是O(NM*D)。
空間複雜度o(N + M * Split * TreeNum )：N為樣本數量，M為特征數量，Split為平均每個特征的切分點數量，TreeNum為如果為随機森林，随機森林的數目數量。
70年代後期至80年代，Quinlan開發了ID3算法，後來，他将ID3算法進行改進，得到了C4.5算法，到1984年，由多位統計學家共同研究，又得出了CART算法。是以，ID３到C4.5再到CART算法，都是建立在決策樹模型的基礎之上的疊代和更新，通過算法内部的調整不斷對決策模型進行優化和改進。接下來，我将詳細介紹并比較這三種算法的用途及原理。
二、 ID3算法
ID3由Ross Quinlan在1986年提出。ID3決策樹可以有多個分支，但是不能處理特征值為連續的情況。決策樹是一種貪心算法，每次選取的分割資料的特征都是目前的最佳選擇，并不關心是否達到最優。在ID3中，每次根據“最大資訊熵增益”選取目前最佳的特征來分割資料，并按照該特征的所有取值來切分，也就是說如果一個特征有4種取值，資料将被切分4份，一旦按某特征切分後，該特征在之後的算法執行中，将不再起作用，是以有觀點認為這種切分方式過于迅速。
ID3算法十分簡單，核心是根據“最大資訊熵增益”原則選擇劃分目前資料集的最好特征，資訊熵是資訊論裡面的概念，是資訊的度量方式，不确定度越大或者說越混亂，熵就越大。在建立決策樹的過程中，根據特征屬性劃分資料，使得原本“混亂”的資料的熵(混亂度)減少，按照不同特征劃分資料熵減少的程度會不一樣。在ID3中選擇熵減少程度最大的特征來劃分資料，也就是“最大資訊熵增益”原則。
由于決策樹會根據最大資訊增益來對結點進行劃分，是以資訊增益的計算尤為重要，公式如下：
注明：p(i)為某種情況出現的機率值，Info(D)為整體的資訊熵，InfoA(D)表示在選取屬性A作為節點對整體進行劃分後資訊熵值，Gain(A)為屬性A的資訊增益大小。
接下來我們通過具體執行個體來說明ID3算法的運作過程
圖中表示的資料為年齡，收入，是否為學生與信用等級對買電腦這個動作的決策和影響，及通過表中的4個不同屬性對最終的行為進行判斷和預測，我們用ID3算法來進行描述。
根據我的觀察可以大緻畫出的決策樹模型如下，等下可以與python所畫出的進行比較，觀察人為建構與機器模組化的差異何在。
選擇age作為根節點後可以繼續向下畫圖，得出圖如下
到此處可見，該模型的決策樹已經大體成型，接下來通過python代碼來做機器模組化，繪制決策樹。
程式設計環境我選擇了Anaconda中的jupyter Notebook編譯器作為運作平台，好處是jupyter是一個線上編輯器，并且可以利用Anaconda中内置的多種資料包，包括了決策樹所需要的numpy、math、pandas等等，後續的C4.5和CART算法均使用此平台環境，後面将不再贅述。
代碼執行情況如下：
首先将上述表格的内容整理到excel中，标記好各個屬性和結果，以便後續的代碼調用。
開始建立樹模型并通過CSV包來讀取資料内容
讀入資料後建立字典來存儲資料内容，根據屬性來建立鍵值對，一一對應，将此部分運作即可得到圖中下方的一條條字典資料。
字典資料如下
将上述的字元資料轉換為1和0的表示，友善計算機的運算，轉換後的結果如下圖所示
可以将excel中的資料與上述1、0矩陣進行比較，确實是一一對應的關系，1和0都代表了不同屬性下面的不同狀态
準備工作完成後，開始建立決策樹模型并導出測試
測試結果如下，此處還沒有将決策樹圖形化展現出來，而是得出了數字化的結果，下面我會将圖形化的一同展現。
最後一步，導出決策樹，通過graphviz将決策樹模型具象化導出，同時儲存為PDF格式的圖檔，友善後續的使用和研究。
最終決策樹如下
由此圖可見，python所繪制的決策樹與我上圖中人為手繪的有所差别
python所建立的決策樹模型中左邊的子樹都是True,而右邊的子樹都是False，而且整棵樹是一個隻有二分支的二叉樹，并非是有多個分支的決策樹；
其次，最終圖并沒有按照先前分析的，選取最大增益的屬性進行節點的劃分，是以樹模型的整體結構看起來較為複雜，樹的深度和複雜度有所增加。但是最終的分析結果完全無誤，且運算過程遵循最大增益的判定規則。
經過分析，原因可能是ID3算法的提出距今已經有幾十年的時間，中間必定經曆過數次的更新和疊代，在不斷優化和探索中，是以python所繪制的ID3模型圖與人為構想的有些許差别，但是本質還是一樣的。
三、 C4.5算法
C4.5是Ross Quinlan在1993年在ID3的基礎上改進而提出的。ID3采用的資訊增益度量存在一個缺點，資訊增益的方法傾向于首先選擇因子數較多的變量，因為屬性值多的Feature會有相對較大的資訊增益(資訊增益反映的給定一個條件以後不确定性減少的程度,必然是分得越細的資料集确定性更高,也就是條件熵越小,資訊增益越大)。
為了避免這個不足，C4.5中将資訊增益作為節點劃分的标準摒棄，改為使用資訊增益率(gain ratio)來作為選擇分支的準則。資訊增益率通過引入一個被稱作分裂資訊(Split information)的項來懲罰取值較多的Feature。除此之外，C4.5還彌補了ID3中不能處理特征屬性值連續的問題。但是，對連續屬性值需要掃描排序，會使C4.5性能下降。
具體的算法公式如下：資訊增益率的計算也是建立在資訊增益的基礎上改進和使用的，C4.5算法即是将ID3算法中選擇特征的标準用資訊增益比代替。
具體的執行個體在此不再描述，改進後的C4.5在準确率方面有所提高，同時在ID３算法的基礎之上有４項改進：
第一就是用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的不足；
第二就是在樹構造過程中進行剪枝，有效抵抗了決策樹模型中過拟合問題帶來的準确率低下的問題；
第三就是能處理非離散的資料，減少了将連續資料轉換成離散資料處理的步驟，提高了算法效率；
第四就是能處理不完整的資料。
四、 CART算法
經過疊代和演化，決策樹模型已經從ID3改進到C4.5，後來，經過統計學家的共同研究，又提出了CART算法。
CART（Classification and Regression tree）分類回歸樹算法是由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出。ID3中根據屬性值分割資料，之後該特征不會再起作用，這種快速切割的方式會影響算法的準确率。而CART是一棵二叉樹，采用二進制切分法，每次把資料切成兩份，分别進入左子樹、右子樹。而且每個非葉子節點都有兩個孩子，是以CART的葉子節點比非葉子多1。
相比ID3和C4.5，CART應用要多一些，既可以用于分類也可以用于回歸。CART分類時，使用基尼指數（Gini）來選擇最好的資料分割的特征，gini描述的是純度，與資訊熵的含義相似。CART中每一次疊代都會降低GINI系數。下圖顯示資訊熵增益的一半，Gini指數，分類誤差率三種評價名額非常接近。回歸時使用均方差作為loss function。基尼系數的計算與資訊熵增益的方式非常類似，公式如下：
由此可知，CART決策樹的生成就是遞歸的建構二叉決策樹的過程，同時使用基尼系數最小化準則來進行特征選擇，生成二叉樹。
下面通過執行個體（通過人的不同屬性值來判定是否會拖欠貸款）來具體研究CART算法在時間中的應用。
表格資料如下圖所示：
首先要根據表格資料，分别計算不同屬性它們的Gini系數增益，取Gini系數增益最大的屬性來作為決策樹的根節點屬性。
若根據是否有房來進行劃分時，基尼指數的增益計算過程如下，二叉樹的左節點表示Yes,右節點表示No。
按照此方法即可依次計算其他各個屬性的Gini系數
由此比較可得，婚姻狀況與是否有房的Gini系數大小相同，故根節點采用這兩種屬性值來進行劃分均可，對後續無影響。根據年收入來劃分時，由于年收入的數字是連續型變量，是以在計算Gini系數時需要将其轉化為離散型變量來計算，過程如下：
将清單中相鄰兩個的年收入的平均值都計算出來，在依次以各個平均數作為劃分标準來進行Gini系數的計算，選擇其中最大的值所對應的年收入平均值來作為高低收入的分界限，這樣即解決了連續變量與離散變量的轉換問題。
由圖可知，将80和110作為高低收入的分界點是可行的。
選出根節點并按照該順序遞歸推導，最終得出的CART如下圖：
python建構CART的過程與上述ID３類似，在此不再進行贅述，jupyter notebook中的部分過程如截圖所示：
最終繪制的CART如下：
為了削減過拟合問題給最終的預測結果帶來的影響，我們可以對二叉樹進行剪枝的操作，剪枝分為兩種，分别是預剪枝和後剪枝，顧名思義，差別在于剪枝先後順序的不同。具體情況如下：
下面為兩棵二叉樹
預剪枝：根據日常經驗在衆多屬性值當中人為的去掉一些不太重要的屬性，即在建立決策樹之前去掉一些屬性；
例如在某項清單中共有20個屬性，在程式設計模組化之前通過觀察，可以人為去掉10個不重要的屬性，隻用剩下10個來進行判斷。
後剪枝：在建立決策樹之後根據二叉樹的資料觀察，去掉一部分支樹；
例如在上左圖中，經過A3的共100個資料，其中90個為No，10個為Yes，故A5裡有10個資料，再經過判斷，選擇Yes的有9個，No的有1個，綜上計算，經過A3後，99個資料為類B，隻有1個為類A，是以我們對其進行後剪枝得到了右圖。
去掉的部分隻有1個A類，屬于少數的特殊情況，實際上可能是由于過拟合造成的，也可以視為噪音或者幹擾所造成的。
以上即為決策樹中剪枝操作的叙述和舉例，在實際應用中，剪枝操作可以抵抗過拟合的情況，同時可以降低決策樹的複雜度。
五、 線性二分類與非線性二分類
在決策樹的實際應用中，可以進行預測和分類，是以二叉樹也分為回歸樹和分類樹，出上述三種算法外，決策樹還可以用于做線性二分類與非線性二分類。
下面将會通過點陣劃分來具體分析這兩種方法，程式設計環境依舊為Anaconda中的Jupyter Notebook編譯器。
點陣的劃分實際上也需要用到決策樹的判定過程，我們将随機點陣進行坐标化，給了每個點一個确切的定位，之後即可設定判定規則，根據坐标X和Y值的範圍來将不同顔色的點集劃分出來。結果如圖：
同樣為很複雜的決策樹，需要再次将其圖形化即可得到最終的劃分點集
最終結果如下圖：
上述過程中通過修改其中的部分參數值，比如決策樹的深度或者節點所需的最小樣本數等等參數會得到不同的劃分邊界，同時劃分的精準度也會有所不同，如果想要得到良好的劃分結果往往需要不斷的調整參數值，這裡存在一個試的過程。
非線性二分類的簡要示範
具體代碼部分與上述類似，在此我們不再贅述
以下為非線性二分類的點陣圖：
同理，我們需要将決策樹轉化為可視化的圖檔，具體操作過程與二分類中大同小異，代碼截圖見下方：
導出最終決策樹的劃分模型如下圖：
根據上下兩張圖劃分的對比，我們可以粗略看出，在對非線性二分類的劃分中，由于邊界情況較為複雜，劃分的效果不如線性劃分的結果好，運作剛才的代碼，我們可以看出數字化的結果。
由此結果可得，資料在訓練集中的準确率比在測試集當中的要高，原因是可能出現了過拟合的現象，由于非線性點集的劃分邊界較複雜，是以判定的決策樹的分支也會比較多，決策樹深度和複雜度都比較高，容易出現過拟合的現象，是以，若想提高最終劃分集合的準确率，我們需要對決策樹進行剪枝操作。
為此，我在這裡進行了預剪枝的操作，不斷調整和改進決策樹中Max Depth（最大樹深度）和Min Samples Split（内部節點再劃分所需的最小樣本數）這２個參數的值，最終得到了較好的分類結果。
六、 優缺點總結（第一部分也有，此處再次總結）
經過對上述幾種算法分類的探究實踐，可以得出決策樹模型的優缺點如下：
優點:
(1)速度快: 計算量相對較小,且容易轉化成分類規則，隻要沿着樹根向下一直走到葉子節點, 沿途的分裂條件就能夠唯一确定一條分類的謂詞；
(2)準确性高: 挖掘出來的分類規則準确性高,便于了解,決策樹可以清晰的顯示哪些字段比較重要,即可以生成可以了解的規則；
(3)可以處理連續和種類字段；
(4)不需要任何領域知識和參數假設；
(5)适合高維資料。
缺點:
(1)對于各類别樣本數量不一緻的資料, 資訊增益偏向于那些更多數值的特征；
(2)容易出現過拟合現象；
(3)會忽略掉屬性之間的相關性。