Id3

它根據信息增益(Information gain)來選取Feature作為決策樹分裂的節點.特徵A對訓練數據集D的信息增益定義為集合D的經驗熵(所謂經驗熵,指的是熵是有某個數據集合估計得到的)H(D)與特徵A給定條件下D的經驗條件熵 H(D∣A)之差,記為 g(D,A)

算法過程大概是怎麼樣的。

　　　　輸入的是m個樣本，樣本輸出集合為D，每個樣本有n個離散特徵，特徵集合即為A，輸出為決策樹T。

　　　　算法的過程為：

　　　　1)初始化信息增益的閾值ϵ

　　　　2）判斷樣本是否為同一類輸出Di，如果是則返回單節點樹T。標記類別為Di

　　　　3) 判斷特徵是否為空，如果是則返回單節點樹T，標記類別為樣本中輸出類別D實例數最多的類別。

　　　　4）計算A中的各個特徵（一共n個）對輸出D的信息增益，選擇信息增益最大的特徵Ag

　　　　5) 如果Ag的信息增益小於閾值ϵ，則返回單節點樹T，標記類別為樣本中輸出類別D實例數最多的類別。

　　　　6）否則，按特徵Ag的不同取值Agi將對應的樣本輸出D分成不同的類別Di。每個類別產生一個子節點。對應特徵值為Agi。返回增加了節點的數T。

　　　　7）對於所有的子節點，令D=Di, A=A−{Ag}遞歸調用2-6步，得到子樹Ti並返回。

決策樹ID3算法的不足

　　　　ID3算法雖然提出了新思路，但是還是有很多值得改進的地方。　　

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

　　　　b)ID3採用信息增益大的特徵優先建立決策樹的節點。很快就被人發現，在相同條件下，取值比較多的特徵比取值少的特徵信息增益大。比如一個變量有2個值，各為1/2，另一個變量為3個值，各為1/3，其實他們都是完全不確定的變量，但是取3個值的比取2個值的信息增益大。如果校正這個問題呢？

　　　　c) ID3算法對於缺失值的情況沒有做考慮

　　　　d) 沒有考慮過擬合的問題

c4.5信息增益率

計算屬性分裂信息度量:用分裂信息度量來考慮某種屬性進行分裂時分支的數量信息和尺寸信息，我們把這些信息稱為屬性的內在信息。信息增益率用信息增益 / 內在信息表示，信息增益率會導致屬性的重要性隨著內在信息的增大而減小（也就是說，如果這個屬性本身不確定性就很大，那我就越不傾向於選取它），這樣算是對單純用信息增益有所補償。

改變：

1）連續值的處理

C4.5的思路是將連續的特徵離散化。比如m個樣本的連續特徵A有m個，從小到大排列為a1,a2,...,am，則C4.5取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點Ti表示為：Ti=ai+ai+1/2。對於這m-1個點，分別計算以該點作為二元分類點時的信息增益。選擇信息增益最大的點作為該連續特徵的二元離散分類點。比如取到的增益最大的點為at,則小於at的值為類別1，大於at的值為類別2，這樣我們就做到了連續特徵的離散化。

2)缺失值處理的問題，

主要需要解決的是兩個問題，一是在樣本某些特徵缺失的情況下選擇劃分的屬性，二是選定了劃分屬性，對於在該屬性上缺失特徵的樣本的處理。

對於第一個子問題，對於某一個有缺失特徵值的特徵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幾個主要的問題，仍然有優化的空間。

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

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

　　　　3)C4.5只能用於分類，如果能將決策樹用於迴歸的話可以擴大它的使用範圍。

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

Cart樹

CART分類樹算法使用基尼係數來代替信息增益比，基尼係數代表了模型的不純度，基尼係數越小，則不純度越低，特徵越好。這和信息熵是類似的。與信息增益（比）是相反的。選取gini (d,a)基尼係數最小的最為劃分屬性。

分類與迴歸樹的英文是Classfication And Regression Tree，縮寫為CART。CART算法採用二分遞歸分割的技術將當前樣本集分為兩個子樣本集，使得生成的每個非葉子節點都有兩個分支。非葉子節點的特徵取值為True和False，左分支取值為True，右分支取值為False，因此CART算法生成的決策樹是結構簡潔的二叉樹。CART可以處理連續型變量和離散型變量，利用訓練數據遞歸的劃分特徵空間進行建樹，用驗證數據進行剪枝。

如果待預測分類是離散型數據，則CART生成分類決策樹。

如果待預測分類是連續性數據，則CART生成迴歸決策樹。

CART分類樹預測分類離散型數據，採用基尼指數選擇最優特徵，同時決定該特徵的最優二值切分點。分類過程中，假設有K個類，樣本點屬於第k個類的概率為Pk，則概率分佈的基尼指數定義為

根據基尼指數定義，可以得到樣本集合D的基尼指數，其中Ck表示數據集D中屬於第k類的樣本子集。

如果數據集D根據特徵A在某一取值a上進行分割，得到D1,D2兩部分後，那麼在特徵A下集合D的基尼係數如下所示。其中基尼係數Gini(D)表示集合D的不確定性，基尼係數Gini(D,A)表示A=a分割後集合D的不確定性。基尼指數越大，樣本集合的不確定性越大。

對於屬性A，分別計算任意屬性值將數據集劃分為兩部分之後的Gain_Gini，選取其中的最小值，作為屬性A得到的最優二分方案。然後對於訓練集S，計算所有屬性的最優二分方案，選取其中的最小值，作為樣本及S的最優二分方案。

算法輸入是訓練集D，基尼係數的閾值，樣本個數閾值。

　　　　輸出是決策樹T。

　　　　我們的算法從根節點開始，用訓練集遞歸的建立CART樹。

　　　　1) 對於當前節點的數據集為D，如果樣本個數小於閾值或者沒有特徵，則返回決策子樹，當前節點停止遞歸。

　　　　2) 計算樣本集D的基尼係數，如果基尼係數小於閾值，則返回決策樹子樹，當前節點停止遞歸。

　　　　3) 計算當前節點現有的各個特徵的各個特徵值對數據集D的基尼係數，對於離散值和連續值的處理方法和基尼係數的計算見第二節。缺失值的處理方法和C4.5算法裡描述的相同。

　　　　4) 在計算出來的各個特徵的各個特徵值對數據集D的基尼係數中，選擇基尼係數最小的特徵A和對應的特徵值a。根據這個最優特徵和最優特徵值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2.

　　　　5) 對左右的子節點遞歸的調用1-4步，生成決策樹。

　　　　對於生成的決策樹做預測的時候，假如測試集裡的樣本A落到了某個葉子節點，而節點裡有多個訓練樣本。則對於A的類別預測採用的是這個葉子節點裡概率最大的類別。

3.CART迴歸樹

3.1算法詳解

CART迴歸樹預測迴歸連續型數據，假設X與Y分別是輸入和輸出變量，並且Y是連續變量。在訓練數據集所在的輸入空間中，遞歸的將每個區域劃分為兩個子區域並決定每個子區域上的輸出值，構建二叉決策樹。

迴歸樹的建立大致與分類樹相同。

CART樹算法的剪枝

　　　　CART迴歸樹和CART分類樹的剪枝策略除了在度量損失的時候一個使用均方差，一個使用基尼係數，算法基本完全一樣，這裡我們一起來講。

　　　　由於決策時算法很容易對訓練集過擬合，而導致泛化能力差，為了解決這個問題，我們需要對CART樹進行剪枝，即類似於線性迴歸的正則化，來增加決策樹的泛化能力。但是，有很多的剪枝方法，我們應該這麼選擇呢？CART採用的辦法是後剪枝法，即先生成決策樹，然後產生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝策略。

　　　　也就是說，CART樹的剪枝算法可以概括為兩步，第一步是從原始決策樹生成各種剪枝效果的決策樹，第二部是用交叉驗證來檢驗剪枝後的預測能力，選擇泛化預測能力最好的剪枝後的數作為最終的CART樹。

　　　　首先我們看看剪枝的損失函數度量，在剪枝的過程中，對於任意的一刻子樹T,其損失函數為：

其中，α為正則化參數，這和線性迴歸的正則化一樣。C(T)為訓練數據的預測誤差，分類樹是用基尼係數度量，迴歸樹是均方差度量。|T|是子樹T的葉子節點的數量。

　　　　當α=0時，即沒有正則化，原始的生成的CART樹即為最優子樹。當α=∞時，即正則化強度達到最大，此時由原始的生成的CART樹的根節點組成的單節點樹為最優子樹。當然，這是兩種極端情況。一般來說，α越大，則剪枝剪的越厲害，生成的最優子樹相比原生決策樹就越偏小。對於固定的α，一定存在使損失函數Cα(T)最小的唯一子樹。

　　　　看過剪枝的損失函數度量後，我們再來看看剪枝的思路，對於位於節點t的任意一顆子樹Tt，如果沒有剪枝，它的損失是

Cα(Tt)=C(Tt)+α|Tt|

　如果將其剪掉，僅僅保留根節點，則損失是

Cα(T)=C(T)+α

　　　　當α=0或者α很小時，Cα(Tt)

。當α繼續增大時不等式反向，也就是說，如果滿足下式：

α=C(T)−C(Tt)/|Tt|−1

Tt和T有相同的損失函數，但是T節點更少，因此可以對子樹Tt進行剪枝，也就是將它的子節點全部剪掉，變為一個葉子節點T。

　　　　最後我們看看CART樹的交叉驗證策略。上面我們講到，可以計算出每個子樹是否剪枝的閾值α，如果我們把所有的節點是否剪枝的值α都計算出來，然後分別針對不同的α所對應的剪枝後的最優子樹做交叉驗證。這樣就可以選擇一個最好的α，有了這個α，我們就可以用對應的最優子樹作為最終結果。

　　　　好了，有了上面的思路，我們現在來看看CART樹的剪枝算法。

　　　　輸入是CART樹建立算法得到的原始決策樹T。

　　　　輸出是最優決策子樹Tα。

　　　　算法過程如下：

　　　　1）初始化αmin=∞， 最優子樹集合ω={T}。

　　　　2）從葉子節點開始自下而上計算各內部節點t的訓練誤差損失函數Cα(Tt)（迴歸樹為均方差，分類樹為基尼係數）, 葉子節點數|Tt|，以及正則化閾值

α=min{C(T)−C(Tt)/|Tt|−1,αmin}

更新αmin=α

　　　　3) 得到所有節點的α值的集合M。

　　　　4）從M中選擇最大的值αk，自上而下的訪問子樹t的內部節點，如果

C(T)−C(Tt)|/t|−1≤αk

時，進行剪枝。並決定葉節點t的值。如果是分類樹，則是概率最高的類別，如果是迴歸樹，則是所有樣本輸出的均值。這樣得到αk對應的最優子樹Tk

　　　　5）最優子樹集合ω=ω∪Tk， M=M−{αk}

　　　　6) 如果M不為空，則回到步驟4。否則就已經得到了所有的可選最優子樹集合ω.

　　　　7) 採用交叉驗證在ω選擇最優子樹Tα

當α很小的時候，T0 是這樣的最優子樹.

當α很大的時候，單獨一個根節點就是最優子樹。

儘管α的取值無限多，但是T0的子樹是有限個。Tn是最後剩下的根結點，子樹生成是根據前一個子樹Ti，剪掉某個內部節點後，生成Ti+1。然後對這樣的子樹序列分別用測試集進行交叉驗證，找到最優的那個子樹作為我們的決策樹。子樹序列如下

T0>T1>T2>T3>...>Tn

因此CART剪枝分為兩部分，分別是生成子樹序列和交叉驗證

決策樹算法的優點：

　　　　1）簡單直觀，生成的決策樹很直觀。

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

　　　　3）使用決策樹預測的代價是O(log2m)。 m為樣本數。

　　　　4）既可以處理離散值也可以處理連續值。很多算法只是專注於離散值或者連續值。

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

　　　　6）相比於神經網絡之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋

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

　　　　8） 對於異常點的容錯能力好，健壯性高。

　　　　我們再看看決策樹算法的缺點:

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

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

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

　　　　4）有些比較複雜的關係，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關係可以換神經網絡分類方法來解決。

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

參考：

1】博客園 劉建平 決策樹

2】https://weizhixiaoyi.com/2018/04/22/機器學習之分類與迴歸樹-CART/

ID3

C4.5

CART

根據基尼指數定義，可以得到樣本集合D的基尼指數，其中Ck表示數據集D中屬於第k類的樣本子集。

如果數據集D根據特徵A在某一取值a上進行分割，得到D1,D2兩部分後，那麼在特徵A下集合D的基尼係數如下所示。其中基尼係數Gini(D)表示集合D的不確定性，基尼係數Gini(D,A)表示A=a分割後集合D的不確定性。基尼指數越大，樣本集合的不確定性越大。

閱讀更多 洛鴻0920 的文章

關鍵字: 算法 決策樹 集合