一、決策樹
決策樹（decision tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點(diǎn)開始，測(cè)試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果。
如下圖就是一個(gè)典型的決策樹，我們可以通過紋理（清晰/模糊）、觸感（硬滑/軟粘）、根蒂（蜷縮/稍蜷/硬挺）、色澤（青綠/烏黑/淺白）判斷一個(gè)西瓜是好瓜還是壞瓜。例如一個(gè)紋理清晰根蒂稍蜷色澤烏黑觸感硬滑的瓜，從根節(jié)點(diǎn)開始，遍歷到葉子結(jié)點(diǎn)，就知道這是一個(gè)好瓜。
模型的核心部分是結(jié)點(diǎn)和有向邊，其中結(jié)點(diǎn)分為葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)（葉節(jié)點(diǎn)表示一個(gè)類，非葉節(jié)點(diǎn)表示一個(gè)特征），有向邊表示特征屬性的判斷和分裂。決策樹代表實(shí)例屬性值約束的合取的折取，從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合?。础桑?，樹本身對(duì)應(yīng)這些合取的折?。础龋?。所以決策樹的判斷過程就相當(dāng)于從根節(jié)點(diǎn)到某一葉節(jié)點(diǎn)的遍歷，每一步如何遍歷是由數(shù)據(jù)各個(gè)特征的具體特征屬性決定。
不同于貝葉斯算法，決策樹的構(gòu)造過程不依賴領(lǐng)域知識(shí)，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性。所謂決策樹的構(gòu)造就是進(jìn)行屬性選擇度量確定各個(gè)特征屬性之間的拓?fù)浣Y(jié)構(gòu)。
構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性。即在某個(gè)節(jié)點(diǎn)處按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個(gè)分裂子集盡可能地“純”。
分裂屬性有三種情況：
1、屬性是離散值且不要求生成二叉決策樹，此時(shí)用屬性的每一個(gè)劃分作為一個(gè)分支；
2、屬性是離散值且要求生成二叉決策樹，此時(shí)使用屬性劃分的一個(gè)子集進(jìn)行測(cè)試，按照“屬于此子集”和“不屬于此子集”分成兩個(gè)分支；
3、屬性是連續(xù)值，此時(shí)確定一個(gè)值作為分裂點(diǎn)split_point，按照>split_point和<=split_point生成兩個(gè)分支。
盡可能“純”就是盡量讓一個(gè)分裂子集中待分類項(xiàng)屬于同一類別。由此衍生出來多種決策樹算法，ID3、C4.5、CART等基礎(chǔ)算法，以及隨機(jī)森林、GBDT、XGboost、lightGBM等集成算法，接下來將說明其中的基礎(chǔ)算法部分，并簡(jiǎn)單介紹一下集成算法。
二、信息
在介紹ID3、C4.5算法和CART算法之前需要先說明一些基礎(chǔ)知識(shí)。
1、信息量
在日常生活中，極少發(fā)生的事件一旦發(fā)生就容易引起人們的關(guān)注，而司空見慣的事情就不會(huì)引起注意，也就是說極少見的事件所帶來的的信息量多。
例如我們說北京明天要地震、北京明天是個(gè)晴天、明天的太陽(yáng)從東邊升起，這三件事情，由于明天地震發(fā)生的可能性是極小的，一旦發(fā)生，那么這句話的信息量是將是巨大的，而太陽(yáng)從東邊升起是亙古不變的，所以我們認(rèn)為這句話的信息量幾乎為0。
如果用統(tǒng)計(jì)學(xué)的術(shù)語描述，就是越小概率事件發(fā)生了產(chǎn)生的信息量越大。因此，我們可以得出兩條結(jié)論：
（1）一個(gè)具體事件的信息量應(yīng)該是隨著其發(fā)生概率而遞減的，且不能為負(fù)，即info(x) = 1/P(x)；
（2）如果兩個(gè)不相關(guān)的事件x和y，那么兩個(gè)事件同時(shí)發(fā)生時(shí)獲得的信息應(yīng)該等于兩個(gè)事件各自發(fā)生時(shí)獲得的信息之和，即info(x,y)=info(x)+info(y)，且有P(x,y)=P(x)*P(y)。
可以看出，info(x)一定與P(x)的對(duì)數(shù)有關(guān)系（因?yàn)閘og(a) + log(b) = log(a*b)），則info(x) = -logP(x)。（負(fù)號(hào)是保證信息一定是正數(shù)或者是0，底數(shù)遵從普遍傳統(tǒng)可以定義為2，但只需要信息量滿足低概率事件x對(duì)應(yīng)于高的信息量即可。）
2、信息熵
在我們知道了信息量的度量之后，由于他是一個(gè)具體事件發(fā)生了所帶來的信息，那么在事前，因?yàn)槭录目赡芨怕屎涂赡芙Y(jié)果是不確定的，又如何準(zhǔn)確的計(jì)算信息量的多少？
這里我們需要引入熵的概念：熵是在事件結(jié)果出來之前對(duì)可能產(chǎn)生的信息量的期望，則信息熵：所有可能發(fā)生事件所帶來的信息量的期望（隨機(jī)變量的所有可能取值）。
香農(nóng)在1948年的《通信的數(shù)學(xué)理論》正式提出了信息的度量問題，成為信息論誕生的里程碑。他在進(jìn)行信息的定量計(jì)算時(shí)，明確地把信息量定義為隨機(jī)不定性程度的減少。這表明他對(duì)信息的理解是：信息是用來減少隨機(jī)不定性的東西，則其逆定義：信息是確定性的增加。
香農(nóng)提出了著名的信息熵H公式：
? ?
其中，如果對(duì)數(shù)log的底為2，則計(jì)算出來的信息熵就以比特（bit）為單位。并且我們擴(kuò)展至多概率事件時(shí)可以得到 ：
?
其中P(xi)代表隨機(jī)事件X為xi的概率。
（題外話：信息熵還可以作為一個(gè)系統(tǒng)復(fù)雜程度的度量，如果系統(tǒng)越復(fù)雜，出現(xiàn)不同情況的種類越多，那么它的信息熵就越大，如果系統(tǒng)越簡(jiǎn)單，出現(xiàn)不同情況的種類越少，那么信息熵就越小。）
3、條件熵
信息熵是衡量某一單獨(dú)事件，或者多個(gè)相互獨(dú)立事件的信息量多少，那么如果是多事件且事件之間并不相互獨(dú)立，或者某一以另一事件的發(fā)生為前提，我們應(yīng)該怎么計(jì)算其信息的熵呢，這里我們引入條件熵的概念：在給定事件X的條件下，事件Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望。
先給出公式：
H（Y|X）表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。
注意：
1、這里是在給定某個(gè)數(shù)（即某個(gè)變量的某個(gè)值）的情況下，另一變量的熵是多少，變量的不確定性是多少；
2、這里條件熵中的X也是一個(gè)變量，即在一個(gè)變量X的條件下，另一變量Y的熵對(duì)X的期望；
3、在X的每一個(gè)值下，計(jì)算一個(gè)熵，然后每一個(gè)熵乘以各個(gè)值的概率，然后相加；
其原理：用另一變量對(duì)原變量分類后，原變量的不確定性就會(huì)減少，因?yàn)樵黾恿薠的信息，不確定程度減少了多少就是信息的增益。
三、ID3算法
ID3算法是建立在奧卡姆剃刀（如無必要，勿增實(shí)體）的基礎(chǔ)上：越是小型的決策樹越優(yōu)于大的決策樹。
ID3算法最早由羅斯昆（J. Ross Quinlan）于1975年在悉尼大學(xué)提出的一種分類預(yù)測(cè)算法，算法的核心是“信息熵”。它是一種貪心算法，以信息熵的下降速度為選取測(cè)試屬性的標(biāo)準(zhǔn)，即在每個(gè)節(jié)點(diǎn)選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標(biāo)準(zhǔn)，然后繼續(xù)這個(gè)過程，直到生成的決策樹能完美分類訓(xùn)練樣例。
ID3算法計(jì)算每個(gè)屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測(cè)試屬性，對(duì)被選取的測(cè)試屬性創(chuàng)建一個(gè)節(jié)點(diǎn)，并以改節(jié)點(diǎn)的屬性標(biāo)記，對(duì)該屬性的每個(gè)值創(chuàng)建一個(gè)分支據(jù)此劃分樣本。
信息增益 = 信息熵 - 條件熵
如果將X和Y定義為某一個(gè)屬性a和樣本集合D，則有
信息增益表示得知屬性a的信息而使得樣本集合D不確定程度的減少。在ID3算法中，以信息增益度量決策樹中的分裂特征選擇，信息增益越大（信息不確定性減少的程度越大），那么我們就選取這個(gè)特征。
還是以西瓜為例：
好瓜占8/17，壞瓜占9/17，首先計(jì)算根節(jié)點(diǎn)的信息熵為：
接著計(jì)算當(dāng)前屬性集合{色澤、根蒂、敲聲、紋理、臍部、觸感}中各屬性的信息增益：
如色澤有3個(gè)可能的取值：{青綠、烏黑、淺白}
D1(色澤=青綠) = {1, 4, 6, 10, 13, 17}，正例 3/6，反例 3/6
D2(色澤=烏黑) = {2, 3, 7, 8, 9, 15}，正例 4/6，反例 2/6
D3(色澤=淺白) = {5, 11, 12, 14, 16}，正例 1/5，反例 4/5
則3個(gè)分支節(jié)點(diǎn)的信息熵：
那么我們可以計(jì)算出屬性的信息增益：
我們找到信息增益最大的屬性：紋理，他的Gain(D，紋理)=0.3814最大。
于是我們選擇的劃分屬性為“紋理”，如下：
我們得到了三個(gè)子節(jié)點(diǎn)，對(duì)這三個(gè)子節(jié)點(diǎn)，我們通過遞歸使用剛剛的方法進(jìn)行特征屬性的選擇，比如：D1(紋理=清晰) = {1, 2, 3, 4, 5, 6, 8, 10, 15}，第一個(gè)分支結(jié)點(diǎn)可用屬性集合{色澤、根蒂、敲聲、臍部、觸感}，基于 D1各屬性的信息增益，分別求的如下：
于是我們可以選擇特征屬性為根蒂，臍部，觸感三個(gè)特征屬性中任選一個(gè)（因?yàn)樗麄內(nèi)齻€(gè)相等并最大），其它倆個(gè)子結(jié)點(diǎn)同理，然后得到新一層的結(jié)點(diǎn)，再遞歸的由信息增益進(jìn)行構(gòu)建樹即可。我們最終的決策樹如最開始的西瓜樹所示。
由此，我們基于信息增益理論，構(gòu)建了ID3算法的西瓜決策樹模型，但是通過上面的計(jì)算過程我們可以看出，信息增益準(zhǔn)則其實(shí)對(duì)可取數(shù)目較多的屬性有所偏好。
加入我們把“編號(hào)”也作為一個(gè)候選劃分屬性，且編號(hào)唯一，那么我們可以算出編號(hào)的信息增益為0.998，因?yàn)闂l件熵為0了，每個(gè)結(jié)點(diǎn)中只有一類，純度非常高。也就是說，如果來了一個(gè)預(yù)測(cè)樣本，只要告訴我編號(hào)，那么其他特征就沒用了，這樣生成的決策樹顯然不具有泛化能力。
于是我們引入信息增益率來選擇決策樹的最優(yōu)劃分屬性。
四、C4.5算法
C4.5算法是由Ross Quinlan開發(fā)的用于產(chǎn)生決策樹的算法，是對(duì)ID3算法的一個(gè)擴(kuò)展。它的目標(biāo)是監(jiān)督學(xué)習(xí)：給定一個(gè)數(shù)據(jù)集，其中的每一個(gè)元組都能用一組屬性值來描述，每一個(gè)元組屬于一個(gè)互斥的類別中的某一類。C4.5的目標(biāo)是通過學(xué)習(xí)，找到一個(gè)從屬性值到類別的映射關(guān)系，并且這個(gè)映射能用于對(duì)新的類別未知的實(shí)體進(jìn)行分類。
它對(duì)ID3算法進(jìn)行了如下改進(jìn)：
(1)、用信息增益率來選擇屬性，克服了信息增益選擇屬性時(shí)對(duì)較多數(shù)目屬性的偏好；
(2)、在樹構(gòu)建過程中進(jìn)行剪枝；
(3)、能夠完成對(duì)連續(xù)屬性的離散化處理；
(4)、能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理；
1、信息增益率：
信息增益率 = 信息增益 / IV(a)，即信息增益率是信息增益除以一個(gè)屬性a的固有值得來的。
這里的IV(a)屬性固有值的計(jì)算公式：
從公式中可以看出，當(dāng)選取該屬性時(shí)，分成的V類別數(shù)越大，IV(A)就越大，所以讓他作為分母，避免了信息增益的缺點(diǎn)。
還是西瓜樹的例子，可以計(jì)算得到：
IV(觸感) = 0.874 ( V = 2 )
IV(色澤) = 1.580 ( V = 3 )
IV(編號(hào)) = 4.088 ( V = 17)
當(dāng)然，C4.5算法也并不直接選取信息增益率最大的候選劃分屬性（因?yàn)槠鋵?duì)可取類別數(shù)目較少的特征有所偏好：分母越大，整體越小），而是在候選劃分屬性中找出信息增益高于平均水平的屬性（保證大部分好的特征），再?gòu)闹羞x擇信息增益率最高的（保證不會(huì)出現(xiàn)唯一編號(hào)特征這樣的極端情況）。
其他計(jì)算過程與ID3算法無異。
2、連續(xù)屬性的處理
（1）對(duì)特征的取值進(jìn)行升序排序；
（2）兩個(gè)特征取值之間的中點(diǎn)作為可能的分裂點(diǎn)，將數(shù)據(jù)集分成兩部分，計(jì)算每個(gè)可能的分裂點(diǎn)的信息增益（InforGain）。優(yōu)化算法就是只計(jì)算分類屬性發(fā)生改變的那些特征取值；
（3）選擇修正后信息增益(InforGain)最大的分裂點(diǎn)作為該特征的最佳分裂點(diǎn)；
（4）計(jì)算最佳分裂點(diǎn)的信息增益率（Gain Ratio）作為特征的Gain Ratio。注意，此處需對(duì)最佳分裂點(diǎn)的信息增益進(jìn)行修正：減去log2(N-1)/|D|（N是連續(xù)特征的取值個(gè)數(shù)，D是訓(xùn)練數(shù)據(jù)數(shù)目，此修正的原因在于：當(dāng)離散屬性和連續(xù)屬性并存時(shí)，C4.5算法傾向于選擇連續(xù)特征做最佳樹分裂點(diǎn)）
3、剪枝
在決策樹的創(chuàng)建時(shí)，由于數(shù)據(jù)中的噪聲和離群點(diǎn)，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝方法是用來處理這種過分?jǐn)M合數(shù)據(jù)的問題。通常剪枝方法都是使用統(tǒng)計(jì)度量，剪去最不可靠的分枝。
剪枝一般分兩種方法：先剪枝和后剪枝。
先剪枝方法中通過提前停止樹的構(gòu)造（比如決定在某個(gè)節(jié)點(diǎn)不再分裂或劃分訓(xùn)練元組的子集）而對(duì)樹剪枝。一旦停止，這個(gè)節(jié)點(diǎn)就變成樹葉，該樹葉可能取它持有的子集最頻繁的類作為自己的類。先剪枝有很多方法，比如
（1）當(dāng)決策樹達(dá)到一定的高度就停止決策樹的生長(zhǎng)；
（2）到達(dá)此節(jié)點(diǎn)的實(shí)例具有相同的特征向量，而不必一定屬于同一類，也可以停止生長(zhǎng)；
（3）到達(dá)此節(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某個(gè)閾值的時(shí)候也可以停止樹的生長(zhǎng)，不足之處是不能處理那些數(shù)據(jù)量比較小的特殊情況；
（4）計(jì)算每次擴(kuò)展對(duì)系統(tǒng)性能的增益，如果小于某個(gè)閾值就可以讓它停止生長(zhǎng)。
先剪枝有個(gè)缺點(diǎn)就是視野效果問題，也就是說在相同的標(biāo)準(zhǔn)下，也許當(dāng)前擴(kuò)展不能滿足要求，但更進(jìn)一步擴(kuò)展又能滿足要求。這樣會(huì)過早停止決策樹的生長(zhǎng)。
另一種更常用的方法是后剪枝，它由完全成長(zhǎng)的樹剪去子樹而形成。通過刪除節(jié)點(diǎn)的分枝并用樹葉來替換它。樹葉一般用子樹中最頻繁的類別來標(biāo)記。
第一種方法，也是最簡(jiǎn)單的方法，稱之為基于誤判的剪枝。這個(gè)思路很直接，完全的決策樹過度擬合，那我們就再搞一個(gè)測(cè)試數(shù)據(jù)集來糾正它。對(duì)于完全決策樹中的每一個(gè)非葉子節(jié)點(diǎn)的子樹，我們嘗試著把它替換成一個(gè)葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)的類別我們用子樹所覆蓋訓(xùn)練樣本中存在最多的那個(gè)類來代替，這樣就產(chǎn)生了一個(gè)簡(jiǎn)化決策樹，然后比較這兩個(gè)決策樹在測(cè)試數(shù)據(jù)集中的表現(xiàn)，如果簡(jiǎn)化決策樹在測(cè)試數(shù)據(jù)集中的錯(cuò)誤比較少，并且該子樹里面沒有包含另外一個(gè)具有類似特性的子樹（所謂類似的特性，指的就是把子樹替換成葉子節(jié)點(diǎn)后，其測(cè)試數(shù)據(jù)集誤判率降低的特性），那么該子樹就可以替換成葉子節(jié)點(diǎn)。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測(cè)試數(shù)據(jù)集的表現(xiàn)得以改進(jìn)時(shí)，算法就可以終止。
第一種方法很直接，但是需要一個(gè)額外的測(cè)試數(shù)據(jù)集，能不能不要這個(gè)額外的數(shù)據(jù)集呢？為了解決這個(gè)問題，于是就提出了悲觀剪枝。悲觀剪枝就是遞歸得估算每個(gè)內(nèi)部節(jié)點(diǎn)所覆蓋樣本節(jié)點(diǎn)的誤判率。剪枝后該內(nèi)部節(jié)點(diǎn)會(huì)變成一個(gè)葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)的類別為原內(nèi)部節(jié)點(diǎn)的最優(yōu)葉子節(jié)點(diǎn)所決定。然后比較剪枝前后該節(jié)點(diǎn)的錯(cuò)誤率來決定是否進(jìn)行剪枝。該方法和前面提到的第一種方法思路是一致的，不同之處在于如何估計(jì)剪枝前分類樹內(nèi)部節(jié)點(diǎn)的錯(cuò)誤率。
五、CART算法
無論是ID3算法的信息增益，還是C4.5算法的信息增益率，都是基于信息論的熵模型，會(huì)涉及到大量的對(duì)數(shù)運(yùn)算，那么能不能簡(jiǎn)化模型的同事也不至于完全丟失熵模型的優(yōu)點(diǎn)呢？
CART算法應(yīng)運(yùn)而生，其決策樹分類算法使用基尼系數(shù)來代替信息增益，基尼系數(shù)代表了模型的不純度，基尼系數(shù)越小，則不純度越低，特征越好，這與信息增益恰好相反。并且為了進(jìn)一步的簡(jiǎn)化，CART分類每次僅僅對(duì)某一特征的值進(jìn)行二分，而不是多分，構(gòu)建的是二叉樹而不是多叉樹。
其中k代表類別。
基尼系數(shù)反映了數(shù)據(jù)集中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率。因此基尼指數(shù)越小，則數(shù)據(jù)集純度越高?；嶂笖?shù)偏向于特征值較多的特征，類似信息增益?；嶂笖?shù)可以用來度量任何不均勻分布，是介于 0~1 之間的數(shù)，0 是完全相等，1 是完全不相等。
此外，當(dāng) CART 為二分類，其表達(dá)式為：
我們可以看到在平方運(yùn)算和二分類的情況下，其運(yùn)算更加簡(jiǎn)單。當(dāng)然其性能也與熵模型非常接近。
那么，基尼指數(shù)與熵模型性能接近，但到底與熵模型的差距有多大呢？
我們由泰勒展開式：
可以得到：
則有：
基尼指數(shù)可以理解為熵模型的一階泰勒展開。則有一張經(jīng)典圖：
CART樹的剪枝策略是一種“基于代價(jià)復(fù)雜度的剪枝”方法進(jìn)行后剪枝。這種方法會(huì)生成一系列樹，每個(gè)樹都是通過將前面的樹的某個(gè)或某些子樹替換成一個(gè)葉節(jié)點(diǎn)而得到的，這一系列樹中的最后一棵樹僅含一個(gè)用來預(yù)測(cè)類別的葉節(jié)點(diǎn)。然后用一種成本復(fù)雜度的度量準(zhǔn)則來判斷哪棵子樹應(yīng)該被一個(gè)預(yù)測(cè)類別值的葉節(jié)點(diǎn)所代替。這種方法需要使用一個(gè)單獨(dú)的測(cè)試數(shù)據(jù)集來評(píng)估所有的樹，根據(jù)它們?cè)跍y(cè)試數(shù)據(jù)集熵的分類性能選出最佳的樹。
六、總結(jié)
我們對(duì)比一下ID3、C4.5、CART三者之間的差異
劃分標(biāo)準(zhǔn)的差異：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺點(diǎn)，偏向于特征值小的特征，CART 使用基尼指數(shù)克服 C4.5 需要求 log 的巨大計(jì)算量，偏向于特征值較多的特征。
使用場(chǎng)景的差異：ID3 和 C4.5 都只能用于分類問題，CART 可以用于分類和回歸問題；ID3 和 C4.5 是多叉樹，速度較慢，CART 是二叉樹，計(jì)算速度很快；
樣本數(shù)據(jù)的差異：ID3 只能處理離散數(shù)據(jù)且缺失值敏感，C4.5 和 CART 可以處理連續(xù)性數(shù)據(jù)且有多種方式處理缺失值；從樣本量考慮的話，小樣本建議 C4.5、大樣本建議 CART。C4.5 處理過程中需對(duì)數(shù)據(jù)集進(jìn)行多次掃描排序，處理成本耗時(shí)較高，而 CART 本身是一種大樣本的統(tǒng)計(jì)方法，小樣本處理下泛化誤差較大 ；
樣本特征的差異：ID3 和 C4.5 層級(jí)之間只使用一次特征，CART 可多次重復(fù)使用特征；
剪枝策略的差異：ID3 沒有剪枝策略，C4.5 是通過悲觀剪枝策略來修正樹的準(zhǔn)確性，而 CART 是通過代價(jià)復(fù)雜度剪枝。
七、參考資料
https://zhuanlan.zhihu.com/p/34729077
https://www.cnblogs.com/onemorepoint/p/6762134.html
https://blog.csdn.net/leaf_zizi/article/details/83380081
