C4.5是ID3的一個改進算法。
基本介紹
- 外文名：C4.5
- 性質：算法
- 本質：是ID3的一個改進算法
- 改進：詳見正文
簡介,算法,
簡介
由於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）返回的點
