前言：人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容，請(qǐng)參見(jiàn)公眾號(hào)“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機(jī)器學(xué)習(xí)主要有三大類(lèi)：1）分類(lèi)；2）回歸；3）聚類(lèi)。今天我們重點(diǎn)探討一下C4．5算法。 

上篇文章介紹Quinlan（悉尼大學(xué)）提出了ID3算法［參見(jiàn)人工智能（41）］，但是由于ID3算法在實(shí)際應(yīng)用中存在一些問(wèn)題，于是Quinlan又提出了ID3的改進(jìn)算法－C4．5算法。

C4．5算法是由Quinlan提出并開(kāi)發(fā)的用于產(chǎn)生決策樹(shù)［參見(jiàn)人工智能（23）］的算法。該算法是對(duì)Quinlan之前開(kāi)發(fā)的ID3算法的一個(gè)擴(kuò)展。C4．5算法產(chǎn)生的決策樹(shù)可以被用作分類(lèi)目的，因此該算法也可以用于統(tǒng)計(jì)分類(lèi)。

C4．5算法與ID3算法一樣使用了信息熵的概念，并和ID3一樣通過(guò)學(xué)習(xí)數(shù)據(jù)來(lái)建立決策樹(shù)。ID3算法使用的是信息熵的變化值，而C4．5算法使用的是信息增益率。在決策樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝，因?yàn)槟承┚哂泻苌僭氐慕Y(jié)點(diǎn)可能會(huì)使構(gòu)造的決策樹(shù)過(guò)適應(yīng)（Overfitting），如果不考慮這些結(jié)點(diǎn)可能會(huì)更好。對(duì)非離散數(shù)據(jù)能處理，并對(duì)不完整數(shù)據(jù)進(jìn)行處理。

C4．5算法概念：

C4．5算法由Quinlan在ID3算法基礎(chǔ)上提出的，用來(lái)構(gòu)造決策樹(shù)。C4．5算法是用于生成決策樹(shù)的一種經(jīng)典算法。它是一系列用在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘分類(lèi)問(wèn)題中的算法。它的目標(biāo)是監(jiān)督學(xué)習(xí)：給定一個(gè)數(shù)據(jù)集，其中的每一個(gè)元組都能用一組屬性值來(lái)描述，每一個(gè)元組屬于一個(gè)互斥的類(lèi)別中的某一類(lèi)。通過(guò)學(xué)習(xí)，找到一個(gè)從屬性值到類(lèi)別的映射關(guān)系，并且這個(gè)映射能用于對(duì)新的類(lèi)別未知的實(shí)體進(jìn)行分類(lèi)。

C4．5算法改進(jìn)：

C4．5算法是ID3算法的一種延伸和優(yōu)化，C4．5算法對(duì)ID3算法主要做的改進(jìn)是：1）通過(guò)信息增益率選擇分裂屬性，克服了ID3算法中分裂屬性的不足；2）通過(guò)將連續(xù)型的屬性進(jìn)行離散化處理，克服ID3算法不能處理連續(xù)型數(shù)據(jù)缺陷；3）構(gòu)造決策樹(shù)之后進(jìn)行剪枝操作，解決ID3算法中可能會(huì)出現(xiàn)的過(guò)擬合問(wèn)題；4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)。

C4．5算法本質(zhì)：

ID3采用的信息增益度量。它優(yōu)先選擇有較多屬性值的Feature，因?yàn)閷傩灾刀嗟腇eature會(huì)有相對(duì)較大的信息增益。信息增益反映的給定一個(gè)條件以后不確定性減少的程度，分得越細(xì)的數(shù)據(jù)集確定性更高，也就是條件熵越小，信息增益越大。避免這個(gè)不足的一個(gè)度量就是不用信息增益來(lái)選擇Feature，而是用信息增益比率（gain ratio）。

增益比率通過(guò)引入一個(gè)被稱作分裂信息（Split information）的項(xiàng)來(lái)懲罰取值較多的Feature，分裂信息用來(lái)衡量Feature分裂數(shù)據(jù)的廣度和均勻性（有點(diǎn)像煎餅中均勻攤雞蛋的感覺(jué)＾＿＾）。

分裂信息公式：

信息增益比率公式：

但是當(dāng)某個(gè)Di的大小跟D的大小接近時(shí)，則

SplitInformation（D，A）→0

GainRatio（D，A）→∞

為了避免這樣的屬性，采用啟發(fā)式思路，只對(duì)那些信息增益比較高的屬性才用信息增益比率。

C4．5算法流程：

C4．5算法并不是一個(gè)算法，而是一組算法。C4．5算法包括非剪枝C4．5和C4．5規(guī)則。

C4．5能處理連續(xù)屬性值，具體步驟為：

1）把需要處理的樣本（對(duì)應(yīng)根節(jié)點(diǎn)）或樣本子集（對(duì)應(yīng)子樹(shù)）按照連續(xù)變量的大小從小到大進(jìn)行排序；

2）假設(shè)該屬性對(duì)應(yīng)的不同的屬性值一共有N個(gè)，那么總共有N？1可能的候選分割閾值點(diǎn)，每個(gè)候選的分割閾值點(diǎn)的值為上述排序后的屬性值中兩兩前后連續(xù)元素的中點(diǎn)，根據(jù)這個(gè)分割點(diǎn)把原來(lái)連續(xù)的屬性分成離散屬性（比如BooL屬性）；

3）用信息增益比率選擇最佳劃分。

另外，C4．5算法還能對(duì)缺失值進(jìn)行處理：

1）賦上該屬性最常見(jiàn)的值；

2）根據(jù)節(jié)點(diǎn)的樣例上該屬性值出現(xiàn)的情況賦一個(gè)概率；

3）丟棄有缺失值的樣本。

C4．5算法采用PEP（Pessimistic Error Pruning）剪枝法。PEP剪枝法由Quinlan提出，是一種自上而下的剪枝法，根據(jù)剪枝前后的錯(cuò)誤率來(lái)判定是否進(jìn)行子樹(shù)的修剪，因此不需要單獨(dú)的剪枝數(shù)據(jù)集。

C4．5優(yōu)點(diǎn)：

1）通過(guò)信息增益率選擇分裂屬性，克服了ID3算法中通過(guò)信息增益傾向于選擇擁有多個(gè)屬性值的屬性作為分裂屬性的不足；

2）通過(guò)將連續(xù)型的屬性進(jìn)行離散化處理，克服ID3算法不能處理連續(xù)型數(shù)據(jù)缺陷，C4．5算法能夠處理離散型和連續(xù)型的2種屬性類(lèi)型；

3）構(gòu)造決策樹(shù)之后進(jìn)行剪枝（PEP）操作（ID3算法中沒(méi)有），解決ID3算法中可能會(huì)出現(xiàn)的過(guò)擬合問(wèn)題；

4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)；

5）產(chǎn)生的分類(lèi)規(guī)則易于理解且準(zhǔn)確率較高。

C4．5缺點(diǎn)：

1）  在構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效；

2）  針對(duì)含有連續(xù)屬性值的訓(xùn)練樣本時(shí)，算法計(jì)算效率較低；

3）  算法在選擇分裂屬性時(shí)沒(méi)有考慮到條件屬性間的相關(guān)性，只計(jì)算數(shù)據(jù)集中每一個(gè)條件屬性與決策屬性之間的期望信息，有可能影響到屬性選擇的正確性；

4） 算法只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。

C4．5應(yīng)用場(chǎng)景：

C4．5算法具有條理清晰，能處理連續(xù)型屬性，防止過(guò)擬合，準(zhǔn)確率較高和適用范圍廣等優(yōu)點(diǎn)，是一個(gè)很有實(shí)用價(jià)值的決策樹(shù)算法，可以用來(lái)分類(lèi)，也可以用來(lái)回歸。C4．5算法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)、金融分析、遙感影像分類(lèi)、生產(chǎn)制造、分子生物學(xué)和數(shù)據(jù)挖掘等領(lǐng)域得到廣泛應(yīng)用。

結(jié)語(yǔ)：

C4．5算法是由Quinlan在ID3算法基礎(chǔ)上提出的。C4．5算法是ID3算法的一種延伸，對(duì)ID3算法做了一些改進(jìn)和優(yōu)化。它是一系列用在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的分類(lèi)問(wèn)題中的算法。C4．5算法不是一個(gè)算法，而是一組算法。C4．5算法目標(biāo)是通過(guò)學(xué)習(xí)，找到一個(gè)從屬性值到類(lèi)別的映射關(guān)系，并且這個(gè)映射能用于對(duì)新的類(lèi)別未知的實(shí)體進(jìn)行分類(lèi)。C4．5算法在世界上廣為流傳，得到極大的關(guān)注。C4．5算法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)、金融分析、遙感影像分類(lèi)、生產(chǎn)制造、分子生物學(xué)和數(shù)據(jù)挖掘等領(lǐng)域得到廣泛應(yīng)用。

－－－－－－以往文章推薦－－－－－－

機(jī)器學(xué)習(xí)

深度學(xué)習(xí)

人工神經(jīng)網(wǎng)絡(luò)

決策樹(shù)

隨機(jī)森林

強(qiáng)化學(xué)習(xí)

遷移學(xué)習(xí)

遺傳算法

樸素貝葉斯

支持向量機(jī)

蒙特卡羅方法

馬爾科夫模型

Hopfield神經(jīng)網(wǎng)絡(luò)

回歸模型

K鄰近算法

卷積神經(jīng)網(wǎng)絡(luò)

受限玻爾茲曼機(jī)

循環(huán)神經(jīng)網(wǎng)絡(luò)

長(zhǎng)短時(shí)記憶神經(jīng)網(wǎng)絡(luò)

Adaboost算法

ID3算法