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

1. C4.5算法簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

  當(dāng)屬性類(lèi)型為離散型，無(wú)須對(duì)數(shù)據(jù)進(jìn)行離散化處理；當(dāng)屬性類(lèi)型為連續(xù)型，則需要對(duì)數(shù)據(jù)進(jìn)行離散化處理。C4.5算法針對(duì)連續(xù)屬性的離散化處理，核心思想：將屬性A的N個(gè)屬性值按照升序排列；通過(guò)二分法將屬性A的所有屬性值分成兩部分（共有N-1種劃分方法，二分的閾值為相鄰兩個(gè)屬性值的中間值）；計(jì)算每種劃分方法對(duì)應(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è)分隔閾值。對(duì)于第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é)果作為對(duì)屬性A的劃分結(jié)果，并記錄此時(shí)的二分閾值。

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

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

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

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

把子樹(shù)替換成葉子節(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)替換該子樹(shù)，即為剪枝操作。

5. 缺失屬性值的處理

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

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

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

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

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

6. C4.5算法流程

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

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

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

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

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