淺談C5.0與CART演算法的比較--理論理解

作者：劉順祥 公眾號：每天進步一點點2015 (微信ID：lsxxx2011)

配套教程：手把手教你做文本挖掘 https://edu.hellobi.com/course/181

一、決策樹的發展

決策樹是目前比較流行的一種分類演算法，實質上是一種自上而下的歸納學習演算法。該演算法最早由Quinlan在1986年提出，當時稱為ID3演算法，該演算法是基於信息增益進行節點變數的選擇，但該選擇方法會傾向於屬性值比較多的那些變數（如省份欄位有31個水平，性別有2個水平，信息增益首選會考慮選擇省份作為特徵節點）；而且該演算法在構造樹的時候不能很好的處理連續的自變數，導致該演算法的擴展性比較弱；隨後的1993年，Quinlan又提出了C4.5演算法，改進了ID3的缺點，即使用信息增益率進行特徵節點的選擇，避免了偏袒的可能性，而且該演算法對自變數不作任何的限制，但是最大的缺點是該演算法的運行效率比較低；為了解決效率的問題，基於C4.5提出了商業版的C5.0，可惜的是C5.0並沒有公布演算法的更多細節，但其主要核心部分還是和C4.5一致的。與此同時，1984年Brieman等人提出了CART演算法，該演算法擁有一個非常完整的體系，包括樹的生長過程（採用基尼指數選擇樹的節點）、剪枝過程等，而且該演算法還可以解決回歸問題。接下來就針對C5.0和CART演算法做一個簡要的對比。

二、C5.0與CART的比較

C5.0演算法

1、C5.0是一種多叉樹（即如果根節點或中間節點存在連續型的自變數，則該變數會一分為二的展開兩個分支；如果根節點或中間節點存在離散的自變數，則該變數會根據離散變數的水平數分開多個分支），就會導致某個變數一旦被使用，後面的節點將不會再啟用該變數。

2、C5.0決策樹的生長過程採用的是最大信息增益率原則進行節點選擇和分裂點的選擇，具體可從下方的理論中理解：

信息熵反應的是信息雜亂程度，信息越雜亂（越不純），則信息熵越大；反之，信息熵越小。其數學公式為：

其中-log2(pj)反應的是信息量，即某隨機事件發生的概率越小，則信息量越大；反之概率越大，則信息量越小。所以信息熵就是指事件發生的概率（pj）乘以其對應的信息量（-log2(pj)），然後再加總。

信息增益的計算為：

其中，Info為Y變數的信息熵，InfoA為自變數A對Y變數分割的信息熵，

接下來舉個例子，也許你就能夠明白。

Y變數為是否相親，不妨我們計算學歷這個變數對Y變數的分割信息增益值。

Y變數的信息熵：

學歷對Y變數的分割信息熵：

學歷對Y變數的分割信息增益：

在非葉節點的特徵選擇時，我們要求信息增益最大化，但考慮信息增益最大化會帶來一個問題，就是特徵的選擇會傾向於那些離散水平多的變數。例如兩種極端情況：一種是ID變數（當作離散變數處理），該變數對Y變數的分割信息增益就等於Y變數的信息熵，達到最大；另一種是單一值變數，如國籍，該變數對Y變數的分割信息增益就等於0，達到最小，所以節點變數很可能會選擇ID變數。但這樣做其實是對那些水平比較少的離散變數的一種不公平處理。於是就提出了信息增益率的概念，即：

SI為分割信息，說白了就是計算自變數A的信息熵；信息增益率就是在信息增益的基礎上除以自變數A的信息熵。仍然接著上面的學歷例子：

學歷變數的信息熵：

學歷對Y變數的分割信息增益率：

通過這樣的一個變換就可以解決信息增益存在的偏袒弊端。

3、剪枝採用「減少-誤差」法和「減少-損失」法技術

「減少-誤差」法：其核心思想是對比剪枝前後的誤差率，如果剪枝後的誤差率比剪枝前的誤差率要低，則剪枝，否則不剪枝。關於誤差率的計算：如果第i個節點中包含N個樣本，其中預測錯誤的樣本量為M，則該節點的錯誤率為f=M/N，根據正態分布假設，該觀測錯誤率的置信區間為：

所以得到悲觀的真實錯誤率為：

該剪枝方法所設定的默認alpha值為0.25，所以，alpha（置信水平）越小，則1-alpha（置信度）就越大，就越可能執行剪枝，使得真實錯誤率越小，模型的泛化能力越大。

「減少-損失」法：該方法結合損失矩陣對樹進行剪枝，核心思想是比較剪枝前後損失量，如果剪枝後的損失要小於剪枝前的損失，則剪枝，否則不剪枝。有關損失的計算如下：

其中，k為待剪子樹中葉節點的個數，pi為第i個葉節點所含樣本量占子樹所含樣本量的比例，ei為第i個葉節點的估計誤差，oi為第i個葉節點的錯判損失，e為父節點的估計誤差，o為父節點的錯判損失。

4、C5.0演算法只能解決分類問題。

CART演算法

1、是一個二叉樹，即每一個非葉節點只能引伸出兩個分支，所以當某個非葉節點是多水平(2個以上)的離散變數時，該變數就有可能被多次使用。舉個例子也許能夠明白：如果年齡段可分為{青年，中年，老年}，則其子集可以是{青年，中年，老年}、{青年，中年}、{青年，老年}、{中年，老年}、{青年}、{中年}、{老年}、{}。其中{青年，中年，老年}和空集{}為無意義的分割，所以最終有2^3-2=6種組合，形成3對對立的組合，如{青年，中年}與{老年}可以分出兩個分支。

2、CART決策樹的生長過程採用的是最大基尼增益指數原則進行節點選擇和分裂點的選擇，具體可從下方的理論中理解：

對於分類問題

Y變數的基尼指數：

自變數A對Y變數的分割基尼增益指數：

我們仍然拿上面的相親數據為例，計算學歷的各個水平對Y變數的分割基尼增益指數：

Y變數的基尼指數：

{大專}與{本科、碩士}二叉樹的基尼指數：

所以，大專與非大專的分割基尼增益指數為0.486-0.483=0.003。

{本科}與{大專、碩士}二叉樹的基尼指數：

所以，本科與非本科的分割基尼增益指數為0.486-0.438=0.048。

{碩士}與{大專、本科}二叉樹的基尼指數：

所以，碩士與非碩士的分割基尼增益指數為0.486-0.419=0.067。

對於回歸問題

非葉結點的特徵選擇及分割點選擇使用最小二乘偏差：

Y變數的最小二乘偏差：

其中，yi為實際的連續值，ri為預測的連續值；ri的是由某個葉節點中樣本均值來衡量。

自變數A對Y變數的分割最小二乘偏差增益：

其中，beta為連續變數的某個分割點，基於這個分割點可以將數據分成兩組。

3、剪枝採用「最小代價複雜度」法和「損失矩陣」法技術

最小代價複雜度說白了就是某個中間節點中往葉節點發展的過程中，其大錯誤率是否下降的明顯，如果不明顯，則剪枝，否則不減枝。具體數學公式如下：

舉個例子也許你就明白了：

上圖反應了一個簡單的樹，根節點有100個樣本，兩個中間節點T1，T2和4個葉節點。則中間節點T1，T2誤差率增益值α分別為：

可通過設置一個閾值，當誤差率增益值α低於閾值時可以考慮剪枝。

損失矩陣的思想與C5.0的類似，這裡就不在贅述。

4、CART演算法既可以解決分類問題（Y變數為離散變數），也能夠很好的處理預測問題（Y變數為連續變數）。

關於兩個演算法的理論比較我們今天就講到這裡，主要是從演算法的幾叉樹？如何選擇節點特徵、分割點？樹的剪枝技術？和各自解決的問題做了梳理。在下一期我們將針對這兩個演算法如何通過R語言實現落地，並通過案例完成兩個演算法的較量。

推薦閱讀：