上一節(ID3原理及代碼實作)講到的ID3算法存在不足，用資訊增益作為特征選擇标準會偏向取值較多的特征，因為特征的取值越多(該特征資料分的更細)即純度更高，不确定性(條件熵越小$H(D|A)$)更低，由于$H(D)$是一定的，是以資訊增益更大，是以偏向取值更多的特征。使用資訊增益比可以矯正這一問題，資訊增益比就是特征選擇的另一準則——C4.5。
1 C4.5原理
資訊增益比表達式： $$g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}$$ 其中$D$是訓練資料集，$A$是樣本特征，${H_{A}(D)}$是特征熵，表達式為： $${H_{A}(D)}=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}$$ $n$表示特征$A$的類别個數，$D_{i}$表示樣本子集，$|D_{i}|$ 表示$D_{i}$樣本子集的個數。資訊增益比本質是在資訊增益的基礎上乘一個懲罰參數。特征個數較多時，懲罰參數較小；特征個數較少時，懲罰參數較大。 懲罰參數：資料集$D$以特征$A$作為随機變量的熵的倒數，即：将特征A取值相同的樣本劃分到同一個子集中。
C4.5算法對ID3算法進行了改進，用資訊增益比來選擇特征。 決策樹C4.5算法
輸入: 訓練資料集$D$，特征集$A$，門檻值$\varepsilon $；
輸出: 決策樹$T$
step1 若$D$中所有執行個體屬于同一類$C_{k}$，則$T$為單結點樹，并将類$C_{k}$作為該結點的類标記，傳回$T$；
step2 若$A=\Phi$，則$T$為單結點樹，并将$D$中執行個體數最大的類$C_{k}$作為該結點的類标記，傳回$T$；
step3 否則計算特征集$A$中各特征對$D$的資訊增益比，選擇資訊增益最大的特征$A_{g}$；
step4 如果$A_{g}$的資訊增益小于門檻值$\varepsilon$，則置$T$為單結點樹，并将$D$中執行個體數最大的類$C_{k}$作為該結點的類标記，傳回$T$；
step5 否則，對$A_{g}$的每一個取值$A_{gi}$将對應的樣本輸出$D$分成不同的類别$D_{i}$，每個類别産生一個子節點，對應特征值是$A_{gi}$，傳回增加了結點的樹；
step6 對所有的子結點，以$D_{i}$為訓練集，以$A-{A_{g}}$為特征集，遞歸調用(1)-(5)，得到子樹$T_{i}$，傳回$T_{i}$.
2 代碼實作
這裡隻給出資訊增益比特征選擇部分，其他代碼與ID3原理及代碼實作一緻。
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 # the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGainRatio = 0.0;
bestFeature = -1
for i in range(numFeatures): # iterate over all the features
featList = [example[i] for example in dataSet] # create a list of all the examples of this feature
uniqueVals = set(featList) # get a set of unique values
newEntropy = 0.0
splitInfo = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
splitInfo += -prob * log(prob, 2)
infoGain = baseEntropy - newEntropy # calculate the info gain; ie reduction in entropy
if (infoGain == 0): #fix the overflow bug
continue
infoGainRatio = infoGain / splitInfo
if (infoGainRatio > bestInfoGainRatio): # compare this to the best gain so far
bestInfoGainRatio = infoGainRatio # if better than current best, set to best
bestFeature = i
return bestFeature # returns an integer
控制台運作效果：
>>> import mytrees
>>> imp.reload(mytrees)
>>> import treePlotter
>>> myTree = treePlotter.retrieveTree(0)
>>> treePlotter.createPlot(myTree)
3 C4.5小結
缺點：資訊增益比偏向取值較少的特征
原因： 當特征取值較少時，${H_{A}(D)}$的值較小，是以其倒數較大，因而資訊增益比較大。因而偏向取值較少的特征。 使用資訊增益比：基于以上缺點，并不是直接選擇資訊增益率最大的特征，而是先在候選特征中找出資訊增益高于平均水準的特征，然後在這些特征中再選擇資訊增益率最高的特征。