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

1. C4.5算法簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

剪枝的條件為：

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

5. 缺失屬性值的處理

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

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

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

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

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

6. C4.5算法流程

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

優(yōu)點(diǎn)：

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

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

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

最新評論