前言：人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容，請(qǐng)參見公眾號(hào)“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機(jī)器學(xué)習(xí)主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點(diǎn)探討一下C4．5算法。
上篇文章介紹Quinlan（悉尼大學(xué)）提出了ID3算法［參見人工智能（41）］，但是由于ID3算法在實(shí)際應(yīng)用中存在一些問題，于是Quinlan又提出了ID3的改進(jìn)算法－C4．5算法。
C4．5算法是由Quinlan提出并開發(fā)的用于產(chǎn)生決策樹［參見人工智能（23）］的算法。該算法是對(duì)Quinlan之前開發(fā)的ID3算法的一個(gè)擴(kuò)展。C4．5算法產(chǎn)生的決策樹可以被用作分類目的，因此該算法也可以用于統(tǒng)計(jì)分類。
C4．5算法與ID3算法一樣使用了信息熵的概念，并和ID3一樣通過學(xué)習(xí)數(shù)據(jù)來建立決策樹。ID3算法使用的是信息熵的變化值，而C4．5算法使用的是信息增益率。在決策樹構(gòu)造過程中進(jìn)行剪枝，因?yàn)槟承┚哂泻苌僭氐慕Y(jié)點(diǎn)可能會(huì)使構(gòu)造的決策樹過適應(yīng)（Overfitting），如果不考慮這些結(jié)點(diǎn)可能會(huì)更好。對(duì)非離散數(shù)據(jù)能處理，并對(duì)不完整數(shù)據(jù)進(jìn)行處理。
C4．5算法概念：
C4．5算法由Quinlan在ID3算法基礎(chǔ)上提出的，用來構(gòu)造決策樹。C4．5算法是用于生成決策樹的一種經(jīng)典算法。它是一系列用在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘分類問題中的算法。它的目標(biāo)是監(jiān)督學(xué)習(xí)：給定一個(gè)數(shù)據(jù)集，其中的每一個(gè)元組都能用一組屬性值來描述，每一個(gè)元組屬于一個(gè)互斥的類別中的某一類。通過學(xué)習(xí)，找到一個(gè)從屬性值到類別的映射關(guān)系，并且這個(gè)映射能用于對(duì)新的類別未知的實(shí)體進(jìn)行分類。
C4．5算法改進(jìn)：
C4．5算法是ID3算法的一種延伸和優(yōu)化，C4．5算法對(duì)ID3算法主要做的改進(jìn)是：1）通過信息增益率選擇分裂屬性，克服了ID3算法中分裂屬性的不足；2）通過將連續(xù)型的屬性進(jìn)行離散化處理，克服ID3算法不能處理連續(xù)型數(shù)據(jù)缺陷；3）構(gòu)造決策樹之后進(jìn)行剪枝操作，解決ID3算法中可能會(huì)出現(xiàn)的過擬合問題；4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)。
C4．5算法本質(zhì)：
ID3采用的信息增益度量。它優(yōu)先選擇有較多屬性值的Feature，因?yàn)閷傩灾刀嗟腇eature會(huì)有相對(duì)較大的信息增益。信息增益反映的給定一個(gè)條件以后不確定性減少的程度，分得越細(xì)的數(shù)據(jù)集確定性更高，也就是條件熵越小，信息增益越大。避免這個(gè)不足的一個(gè)度量就是不用信息增益來選擇Feature，而是用信息增益比率（gain ratio）。
增益比率通過引入一個(gè)被稱作分裂信息（Split information）的項(xiàng)來懲罰取值較多的Feature，分裂信息用來衡量Feature分裂數(shù)據(jù)的廣度和均勻性（有點(diǎn)像煎餅中均勻攤雞蛋的感覺＾＿＾）。
分裂信息公式：
信息增益比率公式：
但是當(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)子樹）按照連續(xù)變量的大小從小到大進(jìn)行排序；
2）假設(shè)該屬性對(duì)應(yīng)的不同的屬性值一共有N個(gè)，那么總共有N？1可能的候選分割閾值點(diǎn)，每個(gè)候選的分割閾值點(diǎn)的值為上述排序后的屬性值中兩兩前后連續(xù)元素的中點(diǎn)，根據(jù)這個(gè)分割點(diǎn)把原來連續(xù)的屬性分成離散屬性（比如BooL屬性）；
3）用信息增益比率選擇最佳劃分。
另外，C4．5算法還能對(duì)缺失值進(jìn)行處理：
1）賦上該屬性最常見的值；
2）根據(jù)節(jié)點(diǎn)的樣例上該屬性值出現(xiàn)的情況賦一個(gè)概率；
3）丟棄有缺失值的樣本。
C4．5算法采用PEP（Pessimistic Error Pruning）剪枝法。PEP剪枝法由Quinlan提出，是一種自上而下的剪枝法，根據(jù)剪枝前后的錯(cuò)誤率來判定是否進(jìn)行子樹的修剪，因此不需要單獨(dú)的剪枝數(shù)據(jù)集。
C4．5優(yōu)點(diǎn)：
1）通過信息增益率選擇分裂屬性，克服了ID3算法中通過信息增益傾向于選擇擁有多個(gè)屬性值的屬性作為分裂屬性的不足；
2）通過將連續(xù)型的屬性進(jìn)行離散化處理，克服ID3算法不能處理連續(xù)型數(shù)據(jù)缺陷，C4．5算法能夠處理離散型和連續(xù)型的2種屬性類型；
3）構(gòu)造決策樹之后進(jìn)行剪枝（PEP）操作（ID3算法中沒有），解決ID3算法中可能會(huì)出現(xiàn)的過擬合問題；
4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)；
5）產(chǎn)生的分類規(guī)則易于理解且準(zhǔn)確率較高。
C4．5缺點(diǎn)：
1） 在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效；
2） 針對(duì)含有連續(xù)屬性值的訓(xùn)練樣本時(shí)，算法計(jì)算效率較低；
3） 算法在選擇分裂屬性時(shí)沒有考慮到條件屬性間的相關(guān)性，只計(jì)算數(shù)據(jù)集中每一個(gè)條件屬性與決策屬性之間的期望信息，有可能影響到屬性選擇的正確性；
4） 算法只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。
C4．5應(yīng)用場景：
C4．5算法具有條理清晰，能處理連續(xù)型屬性，防止過擬合，準(zhǔn)確率較高和適用范圍廣等優(yōu)點(diǎn)，是一個(gè)很有實(shí)用價(jià)值的決策樹算法，可以用來分類，也可以用來回歸。C4．5算法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)、金融分析、遙感影像分類、生產(chǎn)制造、分子生物學(xué)和數(shù)據(jù)挖掘等領(lǐng)域得到廣泛應(yīng)用。
結(jié)語：
C4．5算法是由Quinlan在ID3算法基礎(chǔ)上提出的。C4．5算法是ID3算法的一種延伸，對(duì)ID3算法做了一些改進(jìn)和優(yōu)化。它是一系列用在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的分類問題中的算法。C4．5算法不是一個(gè)算法，而是一組算法。C4．5算法目標(biāo)是通過學(xué)習(xí)，找到一個(gè)從屬性值到類別的映射關(guān)系，并且這個(gè)映射能用于對(duì)新的類別未知的實(shí)體進(jìn)行分類。C4．5算法在世界上廣為流傳，得到極大的關(guān)注。C4．5算法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)、金融分析、遙感影像分類、生產(chǎn)制造、分子生物學(xué)和數(shù)據(jù)挖掘等領(lǐng)域得到廣泛應(yīng)用。
－－－－－－以往文章推薦－－－－－－
機(jī)器學(xué)習(xí)
深度學(xué)習(xí)
人工神經(jīng)網(wǎng)絡(luò)
決策樹
隨機(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ò)
長短時(shí)記憶神經(jīng)網(wǎng)絡(luò)
Adaboost算法
ID3算法
