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

上篇文章介紹Quinlan（悉尼大學）提出了ID3算法［參見人工智能（41）］，但是由于ID3算法在實際應用中存在一些問題，于是Quinlan又提出了ID3的改進算法－C4．5算法。

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

C4．5算法與ID3算法一樣使用了信息熵的概念，并和ID3一樣通過學習數(shù)據(jù)來建立決策樹。ID3算法使用的是信息熵的變化值，而C4．5算法使用的是信息增益率。在決策樹構(gòu)造過程中進行剪枝，因為某些具有很少元素的結(jié)點可能會使構(gòu)造的決策樹過適應（Overfitting），如果不考慮這些結(jié)點可能會更好。對非離散數(shù)據(jù)能處理，并對不完整數(shù)據(jù)進行處理。

C4．5算法概念：

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

C4．5算法改進：

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

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

ID3采用的信息增益度量。它優(yōu)先選擇有較多屬性值的Feature，因為屬性值多的Feature會有相對較大的信息增益。信息增益反映的給定一個條件以后不確定性減少的程度，分得越細的數(shù)據(jù)集確定性更高，也就是條件熵越小，信息增益越大。避免這個不足的一個度量就是不用信息增益來選擇Feature，而是用信息增益比率（gain ratio）。

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

分裂信息公式：

信息增益比率公式：

但是當某個Di的大小跟D的大小接近時，則

SplitInformation（D，A）→0

GainRatio（D，A）→∞

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

C4．5算法流程：

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

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

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

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

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

另外，C4．5算法還能對缺失值進行處理：

1）賦上該屬性最常見的值；

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

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

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

C4．5優(yōu)點：

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

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

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

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

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

C4．5缺點：

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

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

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

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

C4．5應用場景：

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

結(jié)語：

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

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

機器學習

深度學習

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

決策樹

隨機森林

強化學習

遷移學習

遺傳算法

樸素貝葉斯

支持向量機

蒙特卡羅方法

馬爾科夫模型

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

回歸模型

K鄰近算法

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

受限玻爾茲曼機

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

長短時記憶神經(jīng)網(wǎng)絡

Adaboost算法

ID3算法