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

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

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

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

C4．5算法概念：

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

C4．5算法改進：

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

C4．5算法本質：

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

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

分裂信息公式：

信息增益比率公式：

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

SplitInformation（D，A）→0

GainRatio（D，A）→∞

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

C4．5算法流程：

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

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

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

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

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

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

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

2）根據節點的樣例上該屬性值出現的情況賦一個概率；

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

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

C4．5優點：

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

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

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

4）能夠處理具有缺失屬性值的訓練數據；

5）產生的分類規則易于理解且準確率較高。

C4．5缺點：

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

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

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

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

C4．5應用場景：

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

結語：

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

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

機器學習

深度學習

人工神經網絡

決策樹

隨機森林

強化學習

遷移學習

遺傳算法

樸素貝葉斯

支持向量機

蒙特卡羅方法

馬爾科夫模型

Hopfield神經網絡

回歸模型

K鄰近算法

卷積神經網絡

受限玻爾茲曼機

循環神經網絡

長短時記憶神經網絡

Adaboost算法

ID3算法