C4.5

由於ID3算法在實際應用中存在一些問題，於是Quinlan提出了C4.5算法

C4.5算法繼承了ID3算法的優點，並在以下幾方面對ID3算法進行了改進：

1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；

2) 在樹構造過程中進行剪枝；

3) 能夠完成對連續屬性的離散化處理；

4) 能夠對不完整數據進行處理。

C4.5算法有如下優點：產生的分類規則易於理解，準確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。此外，C4.5只適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時程序無法運行。

具體算法步驟如下；

1創建節點N

2如果訓練集為空，在返回節點N標記為Failure

3如果訓練集中的所有記錄都屬於同一個類別，則以該類別標記節點N

4如果候選屬性為空，則返回N作為葉節點，標記為訓練集中最普通的類；

5for each 候選屬性 attribute_list

6if 候選屬性是連續的then

7對該屬性進行離散化

8選擇候選屬性attribute_list中具有最高信息增益率的屬性D

9標記節點N為屬性D

10for each 屬性D的一致值d

11由節點N長出一個條件為D=d的分支

12設s是訓練集中D=d的訓練樣本的集合

13if s為空

14加上一個樹葉，標記為訓練集中最普通的類

15else加上一個有C4.5（R - {D},C，s）返回的點