本文為大家分享了決策樹之C4.5算法，供大家參考，具體內(nèi)容如下

1. C4.5算法簡介

  C4.5算法是用于生成決策樹的一種經(jīng)典算法，是ID3算法的一種延伸和優(yōu)化。C4.5算法對ID3算法主要做了一下幾點改進：

  （1）通過信息增益率選擇分裂屬性，克服了ID3算法中通過信息增益傾向于選擇擁有多個屬性值的屬性作為分裂屬性的不足；
  （2）能夠處理離散型和連續(xù)型的屬性類型，即將連續(xù)型的屬性進行離散化處理；
  （3）構(gòu)造決策樹之后進行剪枝操作；
  （4）能夠處理具有缺失屬性值的訓練數(shù)據(jù)。

2. 分裂屬性的選擇——信息增益率

  分裂屬性選擇的評判標準是決策樹算法之間的根本區(qū)別。區(qū)別于ID3算法通過信息增益選擇分裂屬性，C4.5算法通過信息增益率選擇分裂屬性。

  屬性A的“分裂信息”(split information)：

其中，訓練數(shù)據(jù)集S通過屬性A的屬性值劃分為m個子數(shù)據(jù)集，|Sj|表示第j個子數(shù)據(jù)集中樣本數(shù)量，|S|表示劃分之前數(shù)據(jù)集中樣本總數(shù)量。

  通過屬性A分裂之后樣本集的信息增益：

信息增益的詳細計算方法，可以參考博客“決策樹之ID3算法及其Python實現(xiàn)”中信息增益的計算。

  通過屬性A分裂之后樣本集的信息增益率：

  通過C4.5算法構(gòu)造決策樹時，信息增益率最大的屬性即為當前節(jié)點的分裂屬性，隨著遞歸計算，被計算的屬性的信息增益率會變得越來越小，到后期則選擇相對比較大的信息增益率的屬性作為分裂屬性。

3. 連續(xù)型屬性的離散化處理

  當屬性類型為離散型，無須對數(shù)據(jù)進行離散化處理；當屬性類型為連續(xù)型，則需要對數(shù)據(jù)進行離散化處理。C4.5算法針對連續(xù)屬性的離散化處理，核心思想：將屬性A的N個屬性值按照升序排列；通過二分法將屬性A的所有屬性值分成兩部分（共有N-1種劃分方法，二分的閾值為相鄰兩個屬性值的中間值）；計算每種劃分方法對應的信息增益，選取信息增益最大的劃分方法的閾值作為屬性A二分的閾值。詳細流程如下：
（1）將節(jié)點Node上的所有數(shù)據(jù)樣本按照連續(xù)型屬性A的具體取值，由小到大進行排列，得到屬性A的屬性值取值序列(xA1,...,xAN)。
（2）在序列(xA1,...,xAN)中共有N-1種二分方法，即共產(chǎn)生N-1個分隔閾值。對于第i種二分方法，其二分閾值θi=xAi+xAi+12。它將該節(jié)點上的數(shù)據(jù)集劃分為2個子數(shù)據(jù)集(xA1,...,xAi)(xAi+1,...,xAN)。計算此種二分結(jié)果下的信息增益。
（3）分別計算N-1種二分結(jié)果下的信息增益，選取信息增益最大的二分結(jié)果作為對屬性A的劃分結(jié)果，并記錄此時的二分閾值。

4. 剪枝——PEP(Pessimistic Error Pruning)剪枝法

  由于決策樹的建立完全是依賴于訓練樣本，因此該決策樹對訓練樣本能夠產(chǎn)生完美的擬合效果。但這樣的決策樹對于測試樣本來說過于龐大而復雜，可能產(chǎn)生較高的分類錯誤率。這種現(xiàn)象就稱為過擬合。因此需要將復雜的決策樹進行簡化，即去掉一些節(jié)點解決過擬合問題，這個過程稱為剪枝。
  剪枝方法分為預剪枝和后剪枝兩大類。預剪枝是在構(gòu)建決策樹的過程中，提前終止決策樹的生長，從而避免過多的節(jié)點產(chǎn)生。預剪枝方法雖然簡單但實用性不強，因為很難精確的判斷何時終止樹的生長。后剪枝是在決策樹構(gòu)建完成之后，對那些置信度不達標的節(jié)點子樹用葉子結(jié)點代替，該葉子結(jié)點的類標號用該節(jié)點子樹中頻率最高的類標記。后剪枝方法又分為兩種，一類是把訓練數(shù)據(jù)集分成樹的生長集和剪枝集；另一類算法則是使用同一數(shù)據(jù)集進行決策樹生長和剪枝。常見的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。
  C4.5算法采用PEP(Pessimistic Error Pruning)剪枝法。PEP剪枝法由Quinlan提出，是一種自上而下的剪枝法，根據(jù)剪枝前后的錯誤率來判定是否進行子樹的修剪，因此不需要單獨的剪枝數(shù)據(jù)集。接下來詳細介紹PEP(Pessimistic Error Pruning)剪枝法。
  對于一個葉子節(jié)點，它覆蓋了n個樣本，其中有e個錯誤，那么該葉子節(jié)點的錯誤率為(e+0.5)/n，其中0.5為懲罰因子（懲罰因子一般取值為0.5）。
  對于一棵子樹，它有L個葉子節(jié)點，那么該子樹的誤判率為：

其中，ei表示子樹第i個葉子節(jié)點錯誤分類的樣本數(shù)量，ni表示表示子樹第i個葉子節(jié)點中樣本的總數(shù)量。

  假設一棵子樹錯誤分類一個樣本取值為1，正確分類一個樣本取值為0，那么子樹的誤判次數(shù)可以認為是一個伯努利分布，因此可以得到該子樹誤判次數(shù)的均值和標準差：

把子樹替換成葉子節(jié)點后，該葉子節(jié)點的誤判率為：

其中，e′=∑Li=1ei，n′=∑Li=1ni。

同時，該葉子結(jié)點的誤判次數(shù)也是一個伯努利分布，因此該葉子節(jié)點誤判次數(shù)的均值為：

剪枝的條件為：

滿足剪枝條件時，則將所得葉子節(jié)點替換該子樹，即為剪枝操作。

5. 缺失屬性值的處理

  訓練樣本集中有可能會出現(xiàn)一些樣本缺失了一些屬性值，待分類樣本中也會出現(xiàn)這樣的情況。當遇到這樣的樣本集時該如何處理呢？含有缺失屬性的樣本集會一般會導致三個問題：

  （１）在構(gòu)建決策樹時，每一個分裂屬性的選取是由訓練樣本集中所有屬性的信息増益率來決定的。而在此階段，如果訓練樣本集中有些樣本缺少一部分屬性，此時該如何計算該屬性的信息増益率；

  （２）當已經(jīng)選擇某屬性作為分裂屬性時，樣本集應該根據(jù)該屬性的值來進行分支，但對于那些該屬性的值為未知的樣本，應該將它分支到哪一棵子樹上；

  （３）在決策樹已經(jīng)構(gòu)建完成后，如果待分類樣本中有些屬性值缺失，則該樣本的分類過程如何進行。

  針對上述因缺失屬性值引起的三個問題，C4.5算法有多種解決方案。
  面對問題一，在計算各屬性的信息増益率時，若某些樣本的屬性值未知，那么可以這樣處理：計算某屬性的信息増益率時忽略掉缺失了此屬性的樣本；或者通過此屬性的樣本中出現(xiàn)頻率最高的屬性值，賦值給缺失了此屬性的樣本。
  面對問題二，假設屬性Ａ已被選擇作為決策樹中的一個分支節(jié)點，在對樣本集進行分支的時候，對于那些屬性Ａ的值未知的樣本，可以送樣處理：不處理那些屬性Ａ未知的樣本，即簡單的忽略它們；或者根據(jù)屬性Ａ的其他樣本的取值，來對未知樣本進行賦值；或者為缺失屬性Ａ的樣本單獨創(chuàng)建一個分支，不過這種方式得到的決策樹模型結(jié)點數(shù)顯然要増加，使模型更加復雜了。
  面對問題三，根據(jù)己經(jīng)生成的決策樹模型，對一個待分類的樣本進行分類時，若此樣本的屬性Ａ的值未知，可以這樣處理：待分類樣本在到達屬性Ａ的分支結(jié)點時即可結(jié)束分類過程，此樣本所屬類別為屬性Ａ的子樹中概率最大的類別；或者把待分類樣本的屬性Ａ賦予一個最常見的值，然后繼續(xù)分類過程。

6. C4.5算法流程

7. C4.5算法優(yōu)缺點分析

優(yōu)點：

（1）通過信息增益率選擇分裂屬性，克服了ID3算法中通過信息增益傾向于選擇擁有多個屬性值的屬性作為分裂屬性的不足；
（2）能夠處理離散型和連續(xù)型的屬性類型，即將連續(xù)型的屬性進行離散化處理；
（3）構(gòu)造決策樹之后進行剪枝操作；
（4）能夠處理具有缺失屬性值的訓練數(shù)據(jù)。

缺點：
（1）算法的計算效率較低，特別是針對含有連續(xù)屬性值的訓練樣本時表現(xiàn)的尤為突出。
（2）算法在選擇分裂屬性時沒有考慮到條件屬性間的相關性，只計算數(shù)據(jù)集中每一個條件屬性與決策屬性之間的期望信息，有可能影響到屬性選擇的正確性。

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論