3.機器學習之決策樹詳解

本篇博客主要介紹機器學習中的決策樹模型，決策樹演算法在機器學習中算是很經典的一個演算法系列，它既可以作為分類演算法，也可以作為回歸演算法，同時也特別適合集成學習比如隨機森林，決策樹模型是一類演算法的集合，在資料挖掘十大演算法中，具體的決策樹演算法占有兩席位置，即C4.5和CART演算法，

決策樹分類的思想類似于找物件，現想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

女兒：多大年紀了？
母親：26，
女兒：長的帥不帥？
母親：挺帥的，
女兒：收入高不？
母親：不算很高，中等情況，
女兒：是公務員不？
母親：是，在稅務局上班呢，
女兒：那好，我去見見，

這個女孩的決策程序就是典型的分類樹決策，相當于通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見，假設這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務員，那么這個可以用下圖表示女孩的決策邏輯：　

決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹），其每個非葉節點表示一個特征屬性上的測驗，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節點存放一個類別，使用決策樹進行決策的程序就是從根節點開始，測驗待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果，

決策樹是在已知各種情況發生概率((各個樣本資料出現中，不同特征出現的概率))的基礎上,通過構建決策樹來進行分析的一種方式，常用演算法有ID3、C4.5、CART，

目前決策樹已經成功運用于醫學、制造產業、天文學、分支生物學以及商業等諸多領域，之前介紹的K-近鄰演算法可以完成很多分類任務，但是它最大的缺點就是無法給出資料的內在含義，決策樹的主要優勢就在于資料形式非常容易理解，決策樹演算法能夠讀取資料集合，構建類似于上面的決策樹，決策樹很多任務都是為了資料中所蘊含的知識資訊，因此決策樹可以使用不熟悉的資料集合，并從中提取出一系列規則，機器學習演算法最終將使用這些機器從資料集中創造的規則，專家系統中經常使用決策樹，而且決策樹給出結果往往可以匹敵在當前領域具有幾十年作業經驗的人類專家，

決策樹的構造演算法：

分類解決離散問題，回歸解決連續問題，1.分類樹是基于概率來構建的,采用資訊增益、資訊增益率、基尼系數來作為樹的評價指標，2.回歸數是基于平均值來構建的,采用均方差作為樹的評價指標，決策樹：資訊論；邏輯回歸、貝葉斯：概率論，不同于邏輯斯蒂回歸和貝葉斯演算法，決策樹的構造程序不依賴領域知識，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性，所謂決策樹的構造就是進行屬性選擇度量確定各個特征屬性之間的拓撲結構，決策樹對空資料，例外值都不敏感，任何型別的資料都支持，不需要特征處理，不用做特征工程，

構造決策樹的關鍵步驟是分裂屬性，所謂分裂屬性就是在某個節點處按照某一特征屬性的不同劃分構造不同的分支，其目標是讓各個分裂子集盡可能地“純”，盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別，分裂屬性分為三種不同的情況：

  1、屬性是離散值且不要求生成二叉決策樹，此時用屬性的每一個劃分作為一個分支，

  2、屬性是離散值且要求生成二叉決策樹，此時使用屬性劃分的一個子集進行測驗，按照“屬于此子集”和“不屬于此子集”分成兩個分支，

  3、屬性是連續值，此時確定一個值作為分裂點split_point，按照>split_point和<=split_point生成兩個分支，

構造決策樹的關鍵性內容是進行屬性選擇度量，屬性選擇度量是一種選擇分裂準則，它決定了拓撲結構及分裂點split_point的選擇，屬性選擇度量演算法有很多，如ID3，C4.5等，一般使用自頂向下遞回分治法，并采用不回溯的貪心策略（只考慮當前資料特征的最好分割方式,不能回溯操作，只能從上往下分割)，

決策樹構建程序（步驟）：

1.將所有的特征看成一個一個的節點；

2.遍歷所有特征,遍歷到其中某一個特征時:遍歷當前特征的所有分割方式，找到最好的分割點,將資料劃分為不同的子節點,計算劃分后子節點的純度資訊；

3.在遍歷的所有特征中,比較尋找最優的特征以及最優特征的最優劃分方式,純度越高,則對當前資料集進行分割操作；

4.對新的子節點繼續執行2-3步,直到每個最終的子節點都足夠純，

決策樹演算法構建的停止條件：

1.當子節點中只有一種型別的時候停止構建(會導致過擬合)

2.當前節點種樣本數小于某個值，同時迭代次數達到指定值，停止構建，此時使用該節點中出現最多的類別樣本資料作為對應值(比較常用)

決策樹三大演算法

 1). ID3演算法：

 決策樹ID3演算法的資訊論基礎：機器學習演算法其實很古老，我們代碼中經常使用的 if, else其實就已經在用到決策樹的思想了，只是你有沒有想過，有這么多條件，用哪個條件特征先做if，哪個條件特征后做if比較優呢？怎么準確的定量選擇這個標準就是決策樹機器學習演算法的關鍵了，1970年代，一個叫昆蘭的大牛找到了用資訊論中的熵來度量決策樹的決策選擇程序，方法一出，它的簡潔和高效就引起了轟動，昆蘭把這個演算法叫做ID3，在看ID3演算法是怎么選擇特征之前，首先需要知道一些資訊論中的基本概念：

資訊：這個是熵和資訊增益的基礎概念，是對一個抽象事物的命名，無論用不用‘資訊’來命名這種抽象事物，或者用其他名稱來命名這種抽象事物，這種抽象事物是客觀存在的，資訊論是量化處理資訊的分支科學，我們可以在劃分資料之前使用資訊論量化度量資訊的內容，集合資訊的度量方式稱為香農熵或者簡稱為熵，這個名字來源于資訊論之父克勞德?香農，熵定義為資訊的期望值，在明晰這個概念之前，我們必須知道資訊的定義，如果帶分類的事物集合可以劃分為多個類別當中，則某個類（xi）的資訊（量）定義如下：

 I(x)用來表示隨機變數的資訊，p(xi)指是當xi發生時的概率，當事件xi發生的概率p(xi)很小，但是它卻發生了，那這個資訊量相當大，比如買彩票中獎了，那么這個資訊量肯定是很大的，相反，對于大概率事件，人們習以為常，那么這個事件的資訊量就很小，這就體現在上述公式中，

再熟悉資訊論中熵：熵度量了事物的不確定性，越不確定的事物，它的熵就越大，具體的，隨機變數X的熵的運算式如下：

其中n代表X的n種不同的離散取值，而pi代表了X取值為i的概率，log為以2或者e為底的對數，舉個例子，比如X有2個可能的取值，而這兩個取值各為1/2時X的熵最大，此時X具有最大的不確定性，對應熵值為：

如果一個值概率大于1/2，另一個值概率小于1/2，則不確定性減少，對應的熵也會減少，比如一個概率1/3，一個概率2/3，則對應熵為：

熟悉了一個變數X的熵，很容易推廣到多個個變數的聯合熵，這里給出兩個變數X和Y的聯合熵運算式：

有了聯合熵，又可以得到條件熵的運算式H(X|Y)，條件熵類似于條件概率,它度量了我們的X在知道Y以后剩下的不確定性，運算式如下：

剛才提到H(X)度量了X的不確定性，條件熵H(X|Y)度量了我們在知道Y以后X剩下的不確定性，那么H(X)-H(X|Y)呢？從上面的描述大家可以看出，它度量了X在知道Y以后不確定性減少程度，這個度量我們在資訊論中稱為互資訊，記為I(X,Y)，在決策樹ID3演算法中叫做資訊增益，ID3演算法就是用資訊增益來判斷當前節點應該用什么特征來構建決策樹，資訊增益大，則越適合用來分類，原則：每次需要分裂時，計算每個屬性的增益率，然后選擇資訊增益率最大的屬性進行分裂，

左邊的橢圓代表H(X),右邊的橢圓代表H(Y),中間重合的部分就是我們的互資訊或者資訊增益I(X,Y), 左邊的橢圓去掉重合部分就是H(X|Y),右邊的橢圓去掉重合部分就是H(Y|X)，兩個橢圓的并就是H(X,Y)，

資訊熵：是度量樣本純度(不確定度)最常用的一種指標，所謂樣本純度，相反而言之就是凌亂程度，如一個資料集U中的樣本都屬于同一類，那么這時樣本純度最高而凌亂程度最低，如果當前樣本集合 D 中第 k 類樣本所占的比例為 pk ，則 D 的資訊熵定義為：

其中D表示樣本集合，|y|樣本中類別的數目， pk表示第k種分類占集合的比例，Ent(D)的值越小，D的純度越高，熵度量了事物的不確定性，越不確定的事物，它的熵就越大，

資訊增益：指的是使用某一個屬性a進行劃分后，所帶來的純度提高的大小（百話了解就是在劃分資料集之前和之后資訊發生的變化），一般而言，資訊增益越大，意味著使用屬性a來進行劃分所獲得的“純度提升”越大，用屬性 a 對樣本集 D 進行劃分所獲得的資訊增益：

資訊增益 = 根節點的資訊熵 - 所有分支節點的資訊熵的加權和，或者說資訊增益 = 資訊熵 - 條件熵，(資訊熵是代表隨機變數的復雜度（不確定度），條件熵代表在某一個條件下，隨機變數的復雜度（不確定度），

上圖的描述是使用屬性a對樣本集合D進行劃分，因為a有V個取值{a1,a2,…,aV}，因此決策樹會有V個分支，劃分后每一個節點中樣本的數量為屬性a=ak的樣本的數量，樣本集合中，屬性 a 上取值為 av 的樣本集合，記為 Dv，權值為劃分后屬性a=ak節點中樣本的數量與劃分前節點中的樣本數量的比值，即概率，概率確保了權重的和為1，

資訊增益表示得知屬性 a 的資訊而使得樣本集合不確定度減少的程度，在決策樹演算法中，我們的關鍵就是每次選擇一個特征，特征有多個，那么到底按照什么標準來選擇哪一個特征，這個問題就可以用資訊增益來度量，如果選擇一個特征后，資訊增益最大（資訊不確定性減少的程度最大），那么我們就選取這個特征，

決策樹ID3演算法的思路：上面提到ID3演算法就是用資訊增益大小來判斷當前節點應該用什么特征來構建決策樹，用計算出的資訊增益最大的特征來建立決策樹的當前節點，這里我們舉一個資訊增益計算的具體的例子，比如我們有15個樣本D，輸出為0或者1，其中有9個輸出為1， 6個輸出為0， 樣本中有個特征A，取值為A1，A2和A3，在取值為A1的樣本的輸出中，有3個輸出為1， 2個輸出為0，取值為A2的樣本輸出中,2個輸出為1,3個輸出為0， 在取值為A3的樣本中，4個輸出為1，1個輸出為0，

 對應的資訊增益為 ：

 如果沒明白，再看一個更加具體的例子（必懂）：

 正例(好瓜)占 8/17，反例占 9/17 ，根結點的資訊熵為：

計算當前屬性集合{色澤，根蒂，敲聲，紋理，臍部，觸感}中每個屬性的資訊增益，色澤有3個可能的取值：{青綠，烏黑，淺白}：

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 個分支結點的資訊熵（條件熵）：

 那么可以知道屬性色澤的資訊增益是：

同理，我們可以求出其它屬性的資訊增益，分別如下：

 于是我們找到了資訊增益最大的屬性紋理，它的Gain(D，紋理) = 0.381最大，于是我們選擇的劃分屬性為紋理，如下：

 因為 "紋理" 有3個取值，因此決策樹會有3個分支，于是，我們可以得到了三個子結點，對于這三個子節點，我們可以遞回的使用剛剛找資訊增益最大的方法進行選擇特征屬性，比如：D1(紋理=清晰) = {1, 2, 3, 4, 5, 6, 8, 10, 15}，第一個分支結點可用屬性集合{色澤、根蒂、敲聲、臍部、觸感}，基于 D1各屬性的資訊增益，分別求的如下：

于是我們可以選擇特征屬性為根蒂，臍部，觸感三個特征屬性中任選一個（因為他們三個相等并最大），其它倆個子結點同理，然后得到新一層的結點，再遞回的由資訊增益進行構建樹即可，

到這里為止，我們已經知道了構建樹的演算法，但是資訊增益準則其實是對可取值數目較多的屬性有所偏好！現在假如我們把資料集中的“編號”也作為一個候選劃分屬性，我們可以算出“編號”的資訊增益是0.998，因為每一個樣本的編號都是不同的（由于編號獨特唯一，條件熵為0了，每一個結點中只有一類，純度非常高啊），也就是說，來了一個預測樣本，你只要告訴我編號，其它特征就沒有用了，這樣生成的決策樹顯然不具有泛化能力，ID3演算法雖然提出了新思路，但是還是有很多值得改進的地方，

決策樹ID3演算法的不足：

(1). ID3沒有考慮連續特征，比如長度，密度都是連續值，無法在ID3運用，這大大限制了ID3的用途，

(2). ID3采用資訊增益大的特征優先建立決策樹的節點，就是上面說的資訊增益準則其實是對可取值數目較多的屬性有所偏好！在相同條件下，取值比較多的特征比取值少的特征資訊增益大，比如一個變數有2個值，各為1/2，另一個變數為3個值，各為1/3，其實他們都是完全不確定的變數，但是取3個值的比取2個值的資訊增益大，

(3). ID3演算法對于缺失值的情況沒有做考慮

(4). 沒有考慮過擬合的問題，

ID3 演算法的作者昆蘭基于上述不足，對ID3演算法做了改進，這就是C4.5演算法，也許你會問，為什么不叫ID4，ID5之類的名字呢?那是因為決策樹太火爆，他的ID3一出來，別人二次創新，很快 就占了ID4， ID5，所以他另辟蹊徑，取名C4.0演算法，后來的進化版為C4.5演算法，下面我們就來聊下C4.5演算法，

2). C4.5演算法：

區別：分裂屬性選擇的評判標準是決策樹演算法之間的根本區別，區別于ID3演算法通過資訊增益選擇分裂屬性，C4.5演算法通過資訊增益率選擇分裂屬性， 

C4.5演算法對ID3演算法主要做了一下幾點改進：

（1）能夠處理離散型和連續型的屬性型別，即將連續型的屬性進行離散化處理；

（2）通過資訊增益率選擇分裂屬性，克服了ID3演算法中通過資訊增益傾向于選擇擁有多個屬性值的屬性作為分裂屬性的不足；

（3）構造決策樹之后進行剪枝操作；

（4）能夠處理具有缺失屬性值的訓練資料，

 對于第一個問題，不能處理連續特征， C4.5的思路是將連續的特征離散化，比如m個樣本的連續特征A有m個，從小到大排列為a1,a2,...,am，a1,a2,...,am,則C4.5取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點Ti表示Ti表示為：Ti = [ ai+ ( a i+1）] / 2，對于這m-1個點，分別計算以該點作為二元分類點時的資訊增益，選擇資訊增益最大的點作為該連續特征的二元離散分類點，比如取到的增益最大的點為at,則小于at的值為類別1，大于at的值為類別2，這樣我們就做到了連續特征的離散化，要注意的是，與離散屬性不同的是，如果當前節點為連續屬性，則該屬性后面還可以參與子節點的產生選擇程序，

對于第二個問題，資訊增益作為標準容易偏向于取值較多的特征的問題，我們引入一個資訊增益比的變數IR(X,Y)，它是資訊增益和特征熵的比值  運算式如下：

 其中D為樣本特征輸出的集合，A為樣本特征；對于于特征熵HA(D)HA(D), 運算式如下：

 其中n為特征A的類別數， Di為特征A的第i個取值對應的樣本個數，|D|為樣本個數，特征數越多的特征對應的特征熵越大，它作為分母，可以校正資訊增益容易偏向于取值較多的特征的問題，

從而演變得到C4.5演算法中資訊增益率的公式（其實和上面一個意思）：

期中IV(a)即為屬性a的固有值：

由上面的計算例子：

可以看出IV(a)其實能夠反映出，當選取該屬性，分成的V類別數越大，IV(a)就越大，如果僅僅只用資訊增益來選擇屬性的話，那么我們偏向于選擇分成子節點類別大的那個特征，但是在前面分析了，并不是很好，所以我們需要除以一個屬性的固定值，這個值要求隨著分成的類別數越大而越小，于是讓它做了分母，這樣可以避免資訊增益的缺點，那么資訊增益率就是完美無瑕的嗎？當然不是，有了這個分母之后，我們可以看到增益率準則其實對可取類別數目較少的特征有所偏好！畢竟分母越小，整體越大，于是C4.5演算法不直接選擇增益率最大的候選劃分屬性，候選劃分屬性中找出資訊增益高于平均水平的屬性（這樣保證了大部分好的的特征），再從中選擇增益率最高的（又保證了不會出現編號特征這種極端的情況），

資訊增益對可取值較多的屬性有所偏好；資訊增益率偏向于可能取值減少的屬性，

 對于第三個問題：缺失值處理的問題，主要需要解決的是兩個問題，一是在樣本某些特征缺失的情況下選擇劃分的屬性；二是選定了劃分屬性，對于在該屬性上缺失特征的樣本的處理，

對于第一個子問題，對于某一個有缺失特征值的特征A，C4.5的思路是將資料分成兩部分，對每個樣本設定一個權重（初始可以都為1），然后劃分資料，一部分是有特征值A的資料D1，另一部分是沒有特征A的資料D2. 然后對于沒有缺失特征A的資料集D1來和對應的A特征的各個特征值一起計算加權重后的資訊增益比，最后乘上一個系數，這個系數是無特征A缺失的樣本加權后所占加權總樣本的比例，

對于第二個子問題，可以將缺失特征的樣本同時劃分入所有的子節點，不過將該樣本的權重按各個子節點樣本的數量比例來分配，比如缺失特征A的樣本a之前權重為1，特征A有3個特征值A1,A2,A3， 3個特征值對應的無缺失A特征的樣本個數為2,3,4.則a同時劃分入A1，A2，A3，對應權重調節為2/9,3/9, 4/9，

 對于第四個問題：C4.5引入了正則化系數進行初步的剪枝，

除了上面的4點，C4.5和ID的思路區別不大，C4.5雖然改進或者改善了ID3演算法的幾個主要的問題，仍然有優化的空間，

決策樹C4.5演算法的不足：

(1). 由于決策樹演算法非常容易過擬合，因此對于生成的決策樹必須要進行剪枝，剪枝的演算法有非常多，C4.5的剪枝方法有優化的空間，思路主要是兩種，一種是預剪枝，即在生成決策樹的時候就決定是否剪枝，另一個是后剪枝，即先生成決策樹，再通過交叉驗證來剪枝，后面講CART樹的時候會專門講決策樹的減枝思路，主要采用的是后剪枝加上交叉驗證選擇最合適的決策樹，

(2). C4.5生成的是多叉樹，即一個父節點可以有多個節點，很多時候，在計算機中二叉樹模型會比多叉樹運算效率高，如果采用二叉樹，可以提高效率，

(3). C4.5只能用于分類，如果能將決策樹用于回歸的話可以擴大它的使用范圍，

(4). C4.5由于使用了熵模型，里面有大量的耗時的對數運算,如果是連續值還有大量的排序運算，如果能夠加以模型簡化可以減少運算強度但又不犧牲太多準確性的話，那就更好了，

這4個問題在CART樹里面部分加以了改進，所以目前如果不考慮集成學習話，在普通的決策樹演算法里，CART演算法算是比較優的演算法了，scikit-learn的決策樹使用的也是CART演算法，

3). CART演算法：

 CART演算法對于C4.5演算法的大部分不足做了改進，比如模型是用較為復雜的熵來度量，使用了相對較為復雜的多叉樹，只能處理分類不能處理回歸等，CART是一棵二叉樹，既可以做回歸，也可以做分類，首先，我們要明白，什么是回歸樹，什么是分類樹，兩者的區別在于樣本輸出，如果樣本輸出是離散值，那么這是一顆分類樹，如果果樣本輸出是連續值，那么那么這是一顆回歸樹，當CART是分類樹時，采用GINI值作為節點分裂的依據；當CART是回歸樹時，采用樣本的最小方差作為節點分裂的依據，分類樹的作用是通過一個物件的特征來預測該物件所屬的類別，而回歸樹的目的是根據一個物件的資訊預測該物件的屬性，并以數值表示，

CART分類樹演算法的最優特征選擇方法：

在ID3演算法中我們使用了資訊增益來選擇特征，資訊增益大的優先選擇，在C4.5演算法中，采用了資訊增益比來選擇特征，以減少資訊增益容易選擇特征值多的特征的問題，但是無論是ID3還是C4.5,都是基于資訊論的熵模型的，這里面會涉及大量的對數運算，能不能簡化模型同時也不至于完全丟失熵模型的優點呢？有！CART分類樹演算法使用基尼系數來代替資訊增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特征越好，這和資訊增益(比)是相反的，

什么是基尼值：
基尼值 Gini(D) 反映了從資料集中隨機抽取兩個樣本，其類別標記不一致的概率，當資料集的純度越高，每次抽到不同類別標記的概率越小，打個比方，在一個袋子里裝100個乒乓球，其中有99個白球，1個黃球，那么當我們隨機抽取兩個球的時候，很大概率是抽到兩個白球，所以資料集D的純度可以用基尼值來度量，其定義如下：

基尼值越小，資料集D純度越高，

什么是基尼指數：

基尼指數是針對于屬性定義的，其反映的是，使用屬性a進行劃分后，所有分支中（使用基尼值度量的）純度的加權和，屬性a的基尼指數定義如下：

具體的，在分類問題中，假設有K個類別，第k個類別的概率為pk, 則基尼系數的運算式為：

如果是二類分類問題，計算就更加簡單了，如果屬于第一個樣本輸出的概率是p，則基尼系數的運算式為：

 對于個給定的樣本D,假設有K個類別, 第k個類別的數量為Ck,則樣本D的基尼系數運算式為：

 特別的，對于樣本D,如果根據特征A的某個值a,把D分成D1和D2兩部分，則在特征A的條件下，D的基尼系數運算式為：

 大家可以比較下基尼系數運算式和熵模型的運算式，二次運算是不是比對數簡單很多？尤其是二類分類的計算，更加簡單，但是簡單歸簡單，和熵模型的度量方式比，基尼系數對應的誤差有多大呢？二分類模型中，熵、Gini系數、分類誤差的比較情況（左下圖）；二類分類，基尼系數和熵之半（二分之一熵）的曲線如下（右下圖）：

從上圖可以看出，基尼系數和熵之半的曲線非常接近，僅僅在45度角附近誤差稍大，因此，基尼系數可以做為熵模型的一個近似替代，而CART分類樹演算法就是使用的基尼系數來選擇決策樹的特征，同時，為了進一步簡化，CART分類樹演算法每次僅僅對某個特征的值進行二分，而不是多分，這樣CART分類樹演算法建立起來的是二叉樹，而不是多叉樹，這樣一可以進一步簡化基尼系數的計算，二可以建立一個更加優雅的二叉樹模型，

CART回歸樹演算法的最優特征選擇方法：

回歸樹，采用樣本方差衡量節點純度， 方差越大，節點越不純，表示該節點的資料越分散，預測的效果就越差，所以方差越小，則不純度越低，特征越好，如果一個節點的所有資料都相同，那么方差就為0，此時可以很肯定得認為該節點的輸出值；如果節點的資料相差很大，那么輸出的值有很大的可能與實際值相差較大，

回歸方差計算公式：

 因此，無論是分類樹還是回歸樹，CART都要選擇使子節點的GINI值或者回歸方差最小的屬性作為分裂的方案，即最小化：

分類樹：

 回歸樹：

CART樹演算法對于連續特征和離散特征處理的改進：

CART如何分裂成一棵二叉樹？節點的分裂分為兩種情況，連續型的資料和離散型的資料，CART對連續型屬性的處理與C4.5差不多，CART分類樹演算法通過最小化分裂后的GINI值，CART回歸樹演算法樣本方差尋找最優分割點，將節點一分為二，

首先對于CART分類樹連續值的處理問題（注意事特征，不是輸出），其思想和C4.5是相同的，都是將連續的特征離散化，唯一的區別在于在選擇劃分點時的度量方式不同，C4.5使用的是資訊增益比，則CART分類樹使用的是基尼系數，具體的思路如下，比如m個樣本的連續特征A有m個，從小到大排列為a1,a2,...,am,則CART演算法取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點Ti表示為：

對于這m-1個點，分別計算以該點作為二元分類點時的基尼系數，選擇基尼系數最小的點作為該連續特征的二元離散分類點，比如取到的基尼系數最小的點為at,則小于at的值為類別1，大于at的值為類別2，這樣我們就做到了連續特征的離散化，要注意的是，與ID3或者C4.5處理離散屬性不同的是，如果當前節點為連續屬性，則該屬性后面還可以參與子節點的產生選擇程序，

 對于CART回歸樹連續值的處理問題（注意事特征，不是輸出），我們知道CART分類樹采用的是用基尼系數的大小來度量特征的各個劃分點的優劣情況，這比較適合分類模型，但是對于回歸模型，我們使用了常見的和方差的度量方式，CART回歸樹的度量目標是，對于任意劃分特征A，對應的任意劃分點s兩邊劃分成的資料集D1和D2，求出使D1和D2各自集合的均方差最小，同時D1和D2的均方差之和最小所對應的特征和特征值劃分點，運算式為：

 其中，c1為D1資料集的樣本輸出均值，c2為D2資料集的樣本輸出均值，

【補充】除了概念的不同，CART回歸樹和CART分類樹的建立和預測的區別主要有下面兩點：1)連續值的處理方法不同；2）對于決策樹建立后做預測的方式，CART分類樹采用葉子節點里概率最大的類別作為當前節點的預測類別；而回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數來預測輸出結果，除了上面提到了以外，CART回歸樹和CART分類樹的建立演算法和預測沒有什么區別，

 對于CART離散值的處理問題（注意事特征，不是輸出），采用的思路是不停的二分離散特征，當CART是分類樹時，采用GINI值作為節點分裂的依據；當CART是回歸樹時，采用樣本的最小方差作為節點分裂的依據，

示例：對于離散型屬性，理論上有多少個離散值就應該分裂成多少個節點，回憶下ID3或者C4.5，如果某個特征A被選取建立決策樹節點，如果它有A1,A2,A3三種類別，我們會在決策樹上一下建立一個三叉的節點，這樣導致決策樹是多叉樹，但是CART分類樹使用的方法不同，CART是一棵二叉樹，他采用的是不停的二分，每一次分裂只會產生兩個節點，還是這個例子，CART分類樹會考慮把A分成{A1}和{A2,A3}，{A2}和{A1,A3}，{A3}和{A1,A2}三種情況，找到基尼系數最小的組合，比如{A2}和{A1,A3}，然后建立二叉樹節點，一個節點是A2對應的樣本，另一個節點是{A1,A3}對應的節點，同時，由于這次沒有把特征A的取值完全分開，后面我們還有機會在子節點繼續選擇到特征A來劃分A1和A3，這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征只會參與一次節點的建立，

 如果沒懂，再來看一個超具體的案例（針對離散型屬性的分類和回歸CART二叉樹）：

針對上面的資料，以屬性“職業”為例，一共有三個離散值，“學生”、“老師”、“上班族”，該屬性有三種劃分的方案，分別為{“學生”}、{“老師”、“上班族”}，{“老師”}、{“學生”、“上班族”}，{“上班族”}、{“學生”、“老師”}，分別計算三種劃分方案的子節點GINI值或者樣本方差，選擇最優的劃分方法，如下圖所示：

第一種劃分方法：{“學生”}、{“老師”、“上班族”}：

 預測是否已婚（分類）：

 預測年齡（回歸）：

 第二種劃分方法：{“老師”}、{“學生”、“上班族”}：

 預測是否已婚（分類）：

預測年齡（回歸）：

第三種劃分方法：{“上班族”}、{“學生”、“老師”}：

  預測是否已婚（分類）：

預測年齡（回歸）：

綜上，如果想預測是否已婚，則選擇{“上班族”}、{“學生”、“老師”}的劃分方法，如果想預測年齡，則選擇{“老師”}、{“學生”、“上班族”}的劃分方法，

CART總結：

1). CART是一棵二叉樹，每一次分裂會產生兩個子節點，對于連續性的資料，直接采用與C4.5相似的處理方法，對于離散型資料，選擇最優的兩種離散值組合方法，

2). CART既能是分類數，又能是二叉樹，如果是分類樹，將選擇能夠最小化分裂后節點GINI值的分裂屬性；如果是回歸樹，選擇能夠最小化兩個節點樣本方差的分裂屬性，

3). CART跟C4.5一樣，需要進行剪枝，采用CCP（代價復雜度的剪枝方法），

決策樹CART演算法的不足：

1）無論是ID3, C4.5還是CART,在做特征選擇的時候都是選擇最優的一個特征來做分類決策，但是大多數，分類決策不應該是由某一個特征決定的，而是應該由一組特征決定的，這樣決策得到的決策樹更加準確，這個決策樹叫做多變數決策樹(multi-variate decision tree)，在選擇最優特征的時候，多變數決策樹不是選擇某一個最優特征，而是選擇最優的一個特征線性組合來做決策，這個演算法的代表是OC1，

2）如果樣本發生一點點的改動，就會導致樹結構的劇烈改變，這個可以通過集成學習里面的隨機森林之類的方法解決，　　　

決策樹的剪枝：

由于決策時演算法很容易對訓練集過擬合，而導致泛化能力差，（如果我們用這個決策樹來對訓練集進行分類的話，那么這顆樹的表現非常好，但是在測驗集上的表現就遠沒有在訓練集上的表現好，這就是過擬合問題，）為了解決這個問題，我們需要對CART樹進行剪枝，即類似于線性回歸的正則化，來增加決策樹的泛化能力，

樹的剪枝就是剪掉樹的一些枝葉，考慮大決策樹的枝代表著邏輯判斷，也代表著分類后的子集，決策樹的剪枝就是刪掉一些不必要的邏輯判斷，并且將子集合并，這樣確實會造成在訓練集上子集不純的現象，但是因為我們最終目標是模型在測驗集上的效果，所以犧牲在訓練集上的效果換取解決測驗集的過擬合問題這樣的做法也是值得的，決策樹剪枝可以分為兩類，預剪枝(Pre-Pruning)和后剪枝(Post-Pruning)，

PrePrune：預剪枝，及早的停止樹增長；PostPrune：后剪枝，在已生成過擬合決策樹上進行剪枝，可以得到簡化版的剪枝決策樹，

預剪枝：就是在生成決策樹的同時進行剪枝，正常決策樹的生成是只要有資訊增益就要進行分支，換句話可以說所有決策樹的構建方法，都是在無法進一步降低熵的情況下才會停止創建分支的程序，為了避免過擬合，可以設定一個閾值，熵減小的數量小于這個閾值，即使還可以繼續降低熵，也停止繼續創建分支，預剪枝就是設定一個閾值，比如只有在資訊增益大于這個閾值的時候（也即是在分類后的資訊混亂程度減小程度大于一定標準的時候）才進行分類，如果在資訊增益過小的情況下，即使存在資訊增益的現象，也不會對其進行分支，預剪枝的思想比較簡單，但在實際應用中，預剪枝的表現并不是很好，所以，目前我們基本都是使用后剪枝方法，

預剪枝依據：

• 作為葉結點或作為根結點需要含的最少樣本個數
• 決策樹的層數
• 結點的經驗熵小于某個閾值才停止

后剪枝：就是在決策樹構造完成后進行剪枝，剪枝的程序是對擁有相同父節點的一組節點進行檢查，如果將其合并，熵增小于某一閾值，那么這一組節點可以合并一個節點，如果將其合并后熵增大于這個閾值，那么說明將其分枝是合理的，后剪枝就是洗掉一些子樹，然后用其葉節點代替，這個葉節點代表的子集不一定都是“純”的，那么，這個葉子節點所標識的類別通過大多數原則確定，大多數原則就是指這個葉節點所代表的子集中大多數的類別來表示這個葉節點，剪枝的程序是對擁有同樣父節點的一組節點進行檢查，判斷如果將其合并，熵的增加量是否小于某一閾值，如果確實小，則這一組節點可以合并一個節點，其中包含了所有可能的結果，后剪枝是目前最普遍的做法，

常用的后剪枝演算法有五種，REP、PEP、MEP、CCP演算法和后規則修剪方法，如果訓練資料較少，PEP演算法表現出良好的預測精度，隨著資料規模的增大，使用REP和CCP剪枝方法得到的決策樹的分類性能和預測精度明顯提高，詳解以下常用的三種：

1). Reduced-Error Pruning(REP,錯誤率降低剪枝）：

這個思路很直接，完全的決策樹不是過度擬合么，我再搞一個測驗資料集來糾正它，REP方法是通過一個新的驗證集來糾正樹的過擬合問題，對于完全域策樹中的每一個非葉子節點的子樹，我們將它替換成一個葉子節點，該葉子節點的類別我們用子樹所覆寫訓練樣本中存在最多的那個類來代替(大多數原則來確定)，這樣就產生了一個新的相對簡化決策樹，然后比較這兩個決策樹在驗證集中的表，如果新的決策樹在驗證集中的正確率較高(測驗資料集中的錯誤比較少)，那么該子樹就可以替換成葉子節點，從而達到決策樹剪枝的目的，該演算法是從下往上依次遍歷所有的子樹，直至沒有任何子樹可以替換使得在驗證集上的表現得以改進時，演算法就可以終止，

假設上圖是我們生成的決策樹，我們要對其進行剪枝，使用REP演算法，

1). 將節點4刪掉替換成8和9，測驗在驗證集上的表現，若表現更好，則將節點4刪掉并替換成8和9的并集，若表現不好則保留原樹的形狀

2). 將節點2刪掉替換成8、9和5，測驗在驗證集上的表現

3). 將節點3刪掉替換成6和7，測驗在驗證集上的表現

REP剪枝方法決定是否修剪這個結點步驟如下：

1：洗掉以此結點為根的子樹

2：使其成為葉子結點

3：賦予該結點關聯的訓練資料的最常見分類

4：當修剪后的樹對于驗證集合的性能不會比原來的樹差時，才真正洗掉該結點

REP是最簡單的后剪枝方法之一，不過在資料量比較少的情況下，REP方法趨于過擬合而較少使用，這是因為訓練資料集合中的特性在剪枝程序中被忽略，所以在驗證資料集合比訓練資料集合小的多時，要注意這個問題，由于驗證集合沒有參與決策樹的創建，所以用REP剪枝后的決策樹對于測驗樣例的偏差要好很多，能夠解決一定程度的過擬合問題，

2). Pessimistic Error Pruning(PEP，悲觀剪枝）：

上文的REP方法思想簡單且易于使用，不過最大的問題在于它需要一個新的驗證集來修正我們的決策樹，PEP方法也是根據剪枝前后的錯誤率來決定是否剪枝，和REP不同之處在于：PEP不需要新的驗證集，而是完全使用訓練資料來生成決策樹，又用這些訓練資料來完成剪枝，并且PEP是自上而下剪枝的，將該結點的某子節點不需要被剪枝時被剪掉；另外PEP方法會有剪枝失敗的情況出現，由于我們還是用生成決策樹時相同的訓練樣本，那么對于每個節點剪枝后的錯分率一定是會上升的，因此在計算錯分率時需要加一個懲罰因子0.5，PEP后剪枝技術是由大師Quinlan提出的，它不需要像REP(錯誤率降低修剪)樣，需要用部分樣本作為測驗資料，，決策樹生成和剪枝都使用訓練集, 所以會產生錯分，

PEP剪枝演算法是在C4.5決策樹演算法中提出的， 把一顆子樹（具有多個葉子節點）用一個葉子節點來替代，比起REP剪枝法，它不需要一個單獨的測驗資料集，PEP演算法是唯一使用Top-Down剪枝策略，這種策略會導致與先剪枝出現同樣的問題，雖然PEP方法存在一些局限性，但是在實際應用中表現出了較高的精度,，兩外PEP方法不需要分離訓練集合和驗證機和，對于資料量比較少的情況比較有利，再者其剪枝策略比其它方法相比效率更高，速度更快，因為在剪枝程序中，樹中的每顆子樹最多需要訪問一次，在最壞的情況下，它的計算時間復雜度也只和非剪枝樹的非葉子節點數目成線性關系，

 # 詳細原理待總結，

3). Cost-Complexity Pruning(CCP、代價復雜度)：

代價復雜度選擇節點表面誤差率增益值最小的非葉子節點，洗掉該非葉子節點的左右子節點，若有多個非葉子節點的表面誤差率增益值相同小，則選擇非葉子節點中子節點數最多的非葉子節點進行剪枝，CART就是采用CCP（代價復雜度）剪枝方法，CART剪枝分為剪枝成子樹序列，并通過交叉驗證選取最優子樹，也就是說，CART樹的剪枝演算法可以概括為兩步，第一步是從原始決策樹生成各種剪枝效果的決策樹，第二步是用交叉驗證來檢驗剪枝后的預測能力，選擇泛化預測能力最好的剪枝后的數作為最終的CART樹，

CCP演算法為子樹Tt定義了代價和復雜度，以及一個衡量代價與復雜度之間關系的引數α，代價指的是在剪枝程序中因子樹Tt被葉節點替代而增加的錯分樣本，復雜度表示剪枝后子樹Tt減少的葉結點數，α則表示剪枝后樹的復雜度降低程度與代價間的關系，表面誤差率增益值定義為：

其中，R(t)表示節點t的錯誤代價，R(t)=r(t)?p(t)；r(t)表示節點t的錯分樣本率，p(t)表示節點t中樣本占全部樣本的比例，|N|表示子樹T?t中的葉節點數，

從原始決策樹生成各種剪枝效果的決策樹的具體步驟：

1). 令決策樹的非葉子節點為{T1，T2，T3，......，Tn}

2). 計算所有非葉子節點的表面誤差率增益值α={α1，α2，α3，......，αn}

3). 選擇表面誤差率增益值αi最小的非葉子節點Ti（若多個非葉子節點具有相同小的表面誤差率增益值，選擇節點數最多的非葉子節點）

4). 對Ti進行剪枝

實體：

假設資料有100條，從下往上，首先計算T5：

 同理，T6? 的α為0.03，由于0 < 0.03，此時將T5? 剪枝而得到一顆新樹，

CCP演算法的實作步驟：

1）按照上述公式從下到上計算每一個非葉節點的α值，然后每一次都剪掉具有最小α值的子樹，從而得到一個集合{T0，T1，T2，......，TM}，其中，T0? 表示完整的決策樹，TM? 表示根節點

2）根據真實的錯誤率在集合{T0,T1,T2,...,TM}選出一個最好的決策樹（交叉驗證）

剪枝程序特別重要，所以在最優決策樹生成程序中占有重要地位，有研究表明，剪枝程序的重要性要比樹生成程序更為重要，對于不同的劃分標準生成的最大樹(Maximum Tree)，在剪枝之后都能夠保留最重要的屬性劃分，差別不大，反而是剪枝方法對于最優樹的生成更為關鍵，C4.5使用了PEP剪枝方法，本文的CART使用了CCP的剪枝方法，

決策樹演算法總結：

決策樹學習的關鍵就是如何選擇最優劃分屬性，三種演算法主要區別:CART構建的一定是二叉樹,ID3,C4.5構建的不一定是二叉樹，分類樹是基于概率來構建的,采用資訊增益、資訊增益率、基尼系數來作為樹的評價指標，回歸數是基于平均值來構建的,采用均方差作為樹的評價指標，

決策樹優化策略:

1.決策樹欠擬合：沒有將不同的資料類別劃分開，原因：決策樹深度太淺導致，解決方案：1.增加樹的深度，2.使用集成演算法，Boosting演算法(GBDT)

2.決策樹過擬合：學習能力太強，將噪音資料特征也學習到資料分割中了，原因:決策樹深度太深導致，解決方案:1.剪枝（調整API中的引數）2.使用集成演算法：Bagging演算法(隨機森林)

決策樹演算法的優點：

1）簡單直觀，易于理解和解釋，可以可視化分析，容易提取出規則

2）基本不需要預處理，不需要提前歸一化，處理缺失值

3）既可以處理離散值也可以處理連續值，很多演算法只是專注于離散值或者連續值

4）能夠處理不相關的特征

5）可以處理多維度輸出的分類問題，

7）可以交叉驗證的剪枝來選擇模型，從而提高泛化能力，

8） 對于例外點的容錯能力好，健壯性高，

9）測驗資料集時，運行速度比較快，在相對短的時間內能夠對大型資料源做出可行且效果良好的結果，

決策樹演算法的缺點：

1）決策樹演算法非常容易過擬合，導致泛化能力不強，可以通過設定節點最少樣本數量和限制決策樹深度來改進，

2）決策樹會因為樣本發生一點點的改動，就會導致樹結構的劇烈改變，這個可以通過集成學習之類的方法解決，

3）尋找最優的決策樹是一個NP難的問題，我們一般是通過啟發式方法，容易陷入區域最優，可以通過集成學習之類的方法來改善

4）如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征，這個可以通過調節樣本權重來改善，

 5）決策樹容易忽略資料集中屬性的相互關聯

參考文章：

1. https://www.cnblogs.com/pinard/p/6050306.html 

2. https://www.cnblogs.com/pinard/p/6053344.html

3. https://www.cnblogs.com/feiyumo/p/9284490.html

4. https://blog.csdn.net/weixin_43216017/article/details/87534496

標籤：Python

上一篇：Python新手爬蟲三：爬取PPT模板

下一篇：Python3.7+Robot Framework+RIDE1.7.4.1安裝使用教程