上一节(ID3原理及代码实现)讲到的ID3算法存在不足,用信息增益作为特征选择标准会偏向取值较多的特征,因为特征的取值越多(该特征数据分的更细)即纯度更高,不确定性(条件熵越小(H(D|A)))更低,由于(H(D))是一定的,因此信息增益更大,所以偏向取值更多的特征。使用信息增益比可以矫正这一问题,信息增益比就是特征选择的另一准则——C4.5。
1 C4.5原理
信息增益比表达式:
其中(D)是训练数据集,(A)是样本特征,({H_{A}(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)
<module 'mytrees' from 'D:\Python\Mechine_learning\Tree\mytrees.py'>
>>> import treePlotter
>>> myTree = treePlotter.retrieveTree(0)
>>> treePlotter.createPlot(myTree)
3 C4.5小结
缺点:信息增益比偏向取值较少的特征
原因: 当特征取值较少时,({H_{A}(D)})的值较小,因此其倒数较大,因而信息增益比较大。因而偏向取值较少的特征。
使用信息增益比:基于以上缺点,并不是直接选择信息增益率最大的特征,而是先在候选特征中找出信息增益高于平均水平的特征,然后在这些特征中再选择信息增益率最高的特征。