决策树 (Decision Tree）是一种十分常用的分类方法，作为一个预测模型，决策树表示对象属性与对象值之间的一种映射关系。
1. 信息熵和信息增益
1.1 信息熵
公式表示为： 其中 S 表示样本集，c 表示样本集合中类别个数，Pi 表示第 i 个类别的概率。
- 信息熵的意思就是一个变量 i（就是这里的类别）可能的变化越多（只和值的种类多少以及发生概率有关），它携带的信息量就越大（因为是相加累计），即类别变量 i 的信息熵越大。
- 二分类问题中，当 X 的概率 P(X) 为 0.5 时，表示变量的不确定性最大，此时的熵达到最大值 1。
- 信息熵反映系统的确定程度：信息熵越低，系统越确定；信息熵越高，系统越不确定
1.2 条件熵
公式表示为： 其中 ti 表示属性 T 的取值。条件熵的直观理解：假设单独计算明天下雨的信息熵：H(Y)=2，而在已知今天阴天情况下计算明天下雨的条件熵：H(Y|X)=0.5（熵变小，确定性变大，明天下雨的概率变大，信息量减少），这样相减后为 1.5，在获得阴天这个信息后，下雨信息不确定性减少了 1.5，信息增益很大，所以今天是否时阴天这个特征信息 X 对明天下雨这个随机变量 Y 的来说是很重要的。
1.3 信息增益
公式表示为：
信息增益考察某个特征对整个系统的贡献。
2. 算法实现
2.0 数据集描述
通过“不浮出水面能否生存 no surfacing”和“是否有脚蹼 flippers”来判断 5 种海洋生物是否属于鱼类。
2.1 计算信息熵
from math import log
def calcInforEnt(dataSet):
num = len(dataSet)
labelCount = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCount.keys():
labelCount[currentLabel] = 0
labelCount[currentLabel] += 1 # 统计类别数目，labelCount = {'yes': 2, 'no': 3}
inforEnt = 0.0
for key in labelCount:
prob = float(labelCount[key]) / num
inforEnt -= prob * log(prob, 2)
return inforEnt测试：
dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
calcInforEnt(dataSet) # 0.97095059445466862.2 划分数据集
按照给定特征值划分数据集
def splitDataSet(dateSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet测试：
dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
splitDataSet(dataSet, 0, 1) # [[1, 'yes'], [1, 'yes'], [0, 'no']]
splitDataSet(dataSet, 0, 0) # [[1, 'no'], [1, 'no']]2.3 选择最好的特征划分数据集
遍历整个数据集，循环计算信息熵和 splitDataSet() 函数，找到最好的特征划分方式。
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 # 数据集的最后一列表示类标签
baseEntropy = calcInforEnt(dataSet)
bestInforGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet] # 取出每个属性的所有值，组成一个数组
uniqueVals = set(featList) # 去重
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * calcInforEnt(subDataSet)
inforGain = bestInforGain - newEntropy
if inforGain > bestInforGain:
bestInforGain = inforGain
bestFeature = i
return bestFeature测试：
dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
chooseBestFeatureToSplit(dataSet) # 02.4 递归构建决策树
工作原理：得到原始数据集，基于最佳的属性划分数据集，由于属性存在两个或以上属性值，因此存在两个或以上的数据分支。第一次划分结束后，数据向下传递到树分支中，每个分支按照条件继续分叉。
递归结束条件：程序遍历完所有划分数据集的属性，或者每一个分支下的实例属于相同分类
import operator
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
# 创建树
def ctrateTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
if classList.count(classList[0] == len(classList)):
return classList[0] # 类型相同，停止划分
if len(dataSet[0]) == 1:
return majorityCnt(classList) # 遍历结束，返回出现频率最高的特征
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel: {}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = ctrateTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree 测试：
dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
labels = ['no surfacing', 'flippers']
ctrateTree(dataSet, labels) # {'no surfacing': {0: 'no', 1: {'flippers'：{0: 'no', 1: 'yes'}}}}3. 评价
以上决策树的 ID3 的实现方式，没有剪枝的步骤，容易发生过度拟合，导致决策树过高。C4.5 决策树的改进策略：
- 用信息增益率来选择属性，克服了用信息增益选择属性偏向选择多值属性的不足
- 在构造树的过程中进行剪枝，参考剪枝算法
- 对连续属性进行离散化
- 能够对不完整的数据进行处理
4. 参考
- 《机器学习实战》
- 信息熵与信息增益