信息熵在决策树分类中的简单应用

（一） 信息熵
信息熵是信息的期望值，描述信息的不确定度。熵越大，表明集合信息的混乱程度越高，换句话说，集合信息混沌，其包含信息价值少。
信息熵计算公式：

信息熵公式
（二）信息增益
信息增益是对信息前后变化量的描述。
计算公式：

infoGain = baseEntropy - EntropyAfter

当infoGain > 0 ,表明集合信息熵减小，包含的信息更纯更有序，价值得到提高。
当infoGain < 0，信息变得混沌。
infoGain = 0，信息量没有变化，但不表明信息没有变化。
我们要依据样本特征来分割数据集以使数据变得更加有序的过程就是要求一个使得infoGain> 0的分类特征，而且是在所有的特征中使得infoGain值最大的特征。
在决策树分类中，数据集包含的分类特征不止一个，那么，在第一次划分数据集时如何从整个特征集中抽出一个特征？第二次呢。信息增益便是对这种划分数据集前后信息是更有序了，还是更混乱的度量。
选出取得信息增益最大的特征，以该特征对数据集分类，如果该特征共有n个特征值，那么划分数据集后会生成n个节点。这些n个节点再计算信息增益，并选出最大的特征，以此往复，直到最终节点仅包含同一类数据为止。
（三）Python代码实现
1，划分数据
splitDataSet方法接收待分类的数据集、预选中的分类特征featIndex及特征的值featValue。如果样本预特征featIndex的值与featValue值相等，则归集该样本且移除该分类特征。返回的retDataSet即为移除分类特征的子数据集。

def splitDataSet(dataSet, featIndex, featValue):
    retDataSet = []
    for singleData in dataSet:
        if singleData[featIndex] == featValue:
            reducedFeatVect = singleData[:featIndex]
            reducedFeatVect.extend(single[featIndex + 1:])
            retDataSet.append(reducedFeatVect)
    return retDataSet

2，选出最佳分类特征
试探性选出最佳分类特征的过程是：
第一步，先从数据集的第一列作为分割数据的特征，接着第二列，第三列直到最后一列。取出第一列的所有值，并存入集合以去重复。
第二步，遍历集合中的分类特征的值，把每一个值传入splitDataSet方法来判断该样本是否应该化为该特征的值代表的同质集，换句话说，与该特征的值相等的归集到一类。
第三步，对同一个分类特征而言，可能具有不同的值。特征的值有多少个，对应节点分支有多少支。因此，在对一个分类特征计算信息熵大小时，必须把各个特征的值的信息熵相加，这才代表该分类特征所具有的信息熵。
第四步，原信息熵baseEntropy与分类后的信息熵newEntropy相减即求得信息增益。该次迭代求出的信息增益与上次相比较，若大于上次的信息增益，说明集合信息变得更纯些（熵减），则把此次信息增益赋给变量bestInfoFain 并把该特征所在列表索引赋给变量bestFeature ，最后返回最佳的分类特征

def chooseBestFeature(dataSet):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShonnonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [ds[i] for ds in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = float(len(subDataSet)) / len(dataSet)
            newEntropy += prob * calcShannonEnt(subDataSet)
            infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

3，计算信息熵

def calcShanonnEnt(dataSet):
    numberEnt = len(dataSet)
    labelCounts = {}
    for feat in dataSet:
        currentLabel = feat[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numberEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt