在前面ML经典算法：决策树（1）中描述了什么是决策树算法，以及介绍了三种不同的属性划分方法。不仅要知道理论，还要实践，下面对这信息增益划分方法进行python实现。
先来复习一下信息增益：
信息增益越大，则意味着使用属性 α 来进行划分所获得的"纯度提升"越大。
假定离散属性 α 有 V 个可能的取值 {α1 ， α2. …， αv}，若使用 α 来对样本集D 进行划分，则会产生 V 个分支结点，其中第 u 个分支结点包含了 D 中所有在属性 α 上取值为 α" 的样本记为 Du. 先计算出 Du的信息熵（下面会介绍），再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 IDuI / IDI ，即样本数越多的分支结点的影响越大，于是可计算出用属性 α 对样本集 D 进行划分所获得的"信息增益"，公式如下：
其中Ent(D)为"信息熵" (information entropy)，信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合 D 中第 k 类样本所占的比例为 Pk (k = 1,2,. . . , IYI) ， D的信息熵定义为:Ent(D)
1. 计算信息熵
首先计算信息熵：
# 计算信息熵
def calcShannonEnt(dataSet):
# 样本数
numEntries = len(dataSet)
labelCounts = {}
# 遍历每个样本
for featVec in dataSet:
# 获取当前样本的类别
currentLabel = featVec[-1]
# 标签为键，样本为值 生成类别字典
# 计数每一标签的样本数
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
# 计算信息熵
for key in labelCounts:
# 获得每一类占总样本数的概率
prob = float(labelCounts[key]) / numEntries
shannonEnt = shannonEnt - prob * log(prob, 2)
return shannonEnt
2. 求信息增益
首先为求信息增益中第axis个属性值为value的样本子集（即在属性 α 上取值为 α" 的样本 Du）：
# 划分数据集，axis:按第几个属性划分，value:要返回的子集对应的属性值
# 获得数据集中，第axis个属性值为value的其他属性和标签的样本子集
def splitDataSet(dataSet, axis, value):
retDataSet = []
featVec = []
for featVec in dataSet:
if featVec[axis] == value:
# 获得第axis个属性之前的几个属性
reducedFeatVec = featVec[:axis]
# 获得第axis个属性之后的几个属性
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet
然后求Du的信息熵和权重 IDuI / IDI ，最后求得信息增益，获得增益最大的那个属性：
# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
# 获得属性的个数，-1是去掉标签
numFeatures = len(dataSet[0]) - 1
# 获得信息熵Ent（D）
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
# 对每个属性技术信息增益
for k in range(numFeatures):
# 获得所有样本的第i个属性值
featList = [example[k] for example in dataSet]
# 该属性的取值集合
uniqueVals = set(featList)
newEntropy = 0.0
# 对每一种取值计算信息增益
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, k, value)
# 样本集合中第 k 类样本所占的比例：权重 IDuI / IDI
prob = len(subDataSet) / float(len(dataSet))
# 获得获得第k类属性值为value的信息熵：calcShannonEnt(subDataSet)
newEntropy += prob * calcShannonEnt(subDataSet)
# 获得信息增益
infoGain = baseEntropy - newEntropy
# 选择信息增益最大的属性
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = k
return bestFeature