C4.5算法

C4.5算法是由Ross Quinlan開發的用於產生決策樹的算法。該算法是對Ross Quinlan之前開發的ID3算法的一個擴展。C4.5算法產生的決策樹可以被用作分類目的，因此該算法也可以用於統計分類。

C4.5算法與ID3算法一樣使用了信息熵的概念，並和ID3一樣通過學習數據來建立決策樹。

在Springer LNCS於2008年發表的優秀論文中，該算法在前10大數據挖掘算法中排名第一，之後使得它變得非常受歡迎。

算法

C4.5跟ID3一樣，使用信息熵從訓練數據集中構建決策樹。訓練數據是已經分類的樣本集合$S={s_{1},s_{2},...}$。每個樣本$s_{i}$由p維向量$(x_{1,i},x_{2,i},...,x_{p,i})$組成，其中$x_{j}$表示樣本的屬性值或者叫特徵，當然也包括樣本 $s_{i}$ 的類別。

在樹的每個節點上，C4.5選擇數據的屬性，該屬性最有效地將其樣本集劃分為集中在一個類或另一個類中的子集。劃分準則是歸一化的信息增益，即熵的差。選擇信息增益最大的屬性進行決策，然後對劃分後的子集進行遞歸處理。

該算法有幾個基本情況：

• 若一個樣本集合的樣本都屬於同一個類別，則直接創建一個葉節點，表示選擇該類別；
• 若所有特徵都沒有提供任何信息增益，C4.5使用類的期望值在樹的上層創建一個決策節點；
• 若遇到了以前未見過的樣本，C4.5使用期望值在樹的上層創建一個決策節點。

偽代碼

構建決策樹的一般算法是：

1. 檢查上述基本情況
2. 對於每個特徵a，計算劃分a的信息增益
3. 記a_best為最高信息增益的特徵
4. 創建一個在a_best上劃分的決策節點
5. 使用劃分後的樣本創建作為當前決策節點的子節點，並在這些子節點上遞歸地處理