一、决策树简介
1.什么是决策树
分类决策树模型是一种描述对实例进行分类的树形结构。 决策树由结点和有向边组成。结点有两种类型：内部结点和叶 节点。内部结点表示一个特征或属性，叶节点表示一个类
2.基本原理介绍
下图所示流程图就是一个决策树，正方形代表判断模块，椭圆代表终止模块，表示已经得出了结论，可以终止运行。从判断模块引出的左右箭头叫做分支，它可以到达另一个判断模块或者终止模块。下图构造的是一个假想的邮件分类系统， 首先它检测发送邮件域名地址：
如果地址为myEmployer.com，则将其放在分类“无聊时需要阅读的邮件”中。
如果邮件不是来自这个域名，则检查邮件内容里是否包含单词曲棍球。
如果包含则将邮件归类到“需要及时处理的朋友邮件”。
如果不包含则将邮件归类到“无需阅读的垃圾邮件”。
3.决策树的优缺点
优点
计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点
可能会产生过度匹配问题。
二、决策树的构造
1.决策树构造的一般流程
（1）收集数据：可以使用任何方法
（2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
（3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
（4）训练算法：构造树的数据结构
（5）测试算法：使用经验树计算错误率
（6）使用算法：此步骤可以使用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义
2.三种划分方法
2.1信息增益：ID3
2.1.1信息熵定义与计算方法
“信息熵”是度量样本集合纯度最常用的一种指标，假定 当前样本集合D中第k类样本所占的比例为 pk (K=1, 2, …, |y|) ，则D的信息熵定义为：
Ent(D)的值越小，则D的纯度越高
? 计算信息熵时约定：若p = 0，则plog2p=0
? Ent(D)的最小值为0，最大值为log2|y|
2.1.2信息增益定义与计算方法
离散属性a有V个可能的取值{a1, a2, …, aV}，用a来进行划分，则会产 生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为 av的样本，记为Dv。则可计算出用属性a对样本集D进行划分所获得的 “信息增益”：
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的 “纯度提升”越大
2.1.3存在的问题
信息增益对可取值数目较多的属性有所偏好
2.2增益率：C4.5
2.2.1增益率定义与计算方法
其中
称为属性a的“固有值” [Quinlan, 1993]，属性a的可能取值数 目越多（即V越大），则IV(a)的值通常就越大
2.2.2存在问题
增益率准则对可取值数目较少的属性有所偏好
2.3基尼指数：CART
2.3.1基尼指数的定义与计算方法
三、 代码实现决策树的构造（信息增益）
1.计算信息熵（代码实现）
def calcShannonEnt(dataSet):
# 返回数据集的行数
numEntries = len(dataSet)
# 保存每个标签(Label)出现次数的字典
labelCounts = {}
# 对每组特征向量进行统计
for featVec in dataSet:
# 提取标签(Label)信息
currentLabel = featVec[-1]
# 如果标签(Label)没有放入统计次数的字典，添加进去
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
# Label计数
labelCounts[currentLabel] += 1
# 香农熵
shannonEnt = 0.0
# 计算香农熵
for key in labelCounts:
# 选择该标签(Label)的概率
prob = float(labelCounts[key])/numEntries
# 利用公式计算香农熵
shannonEnt -= prob * log(prob, 2)
# 返回香农熵
return shannonEnt
def createDataSet():
# 数据集
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
# 分类属性
labels = ['no surfacing', 'flippers']
# 返回数据集和分类属性
return dataSet, labels
2.划分数据集（代码实现）
def splitDataSet(dataSet, axis, value):
# 创建返回的数据集列表
retDataSet = []
# 遍历数据集
for featVec in dataSet:
if featVec[axis] == value:
# 去掉axis特征
reducedFeatVec = featVec[:axis]
# 将符合条件的添加到返回的数据集
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
# 返回划分后的数据集
return retDataSet
3.递归构造决策树（代码实现）
工作原理：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。
#多数表决
def majorityCnt(classList):
classCount = {}
# 统计classList中每个元素出现的次数
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)
# 返回classList中出现次数最多的元素
return sortedClassCount[0][0]
#创建决策树
def createTree(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
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
4.在Python中使用matplotlib注解绘制决策树（代码实现）
#获得叶节点的数目
def getNumLeafs(myTree):
# 初始化叶子
numLeafs = 0
#python3中myTree.keys()返回的是dict_keys,不在是list,
#所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
firstStr = next(iter(myTree))
# 获取下一组字典
secondDict = myTree[firstStr]
for key in secondDict.keys():
# 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
if type(secondDict[key]).__name__=='dict':
numLeafs += getNumLeafs(secondDict[key])
else: numLeafs +=1
return numLeafs
#获得决策树深度
def getTreeDepth(myTree):
# 初始化决策树深度
maxDepth = 0
#python3中myTree.keys()返回的是dict_keys,不在是list,
#所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
firstStr = next(iter(myTree))
# 获取下一个字典
secondDict = myTree[firstStr]
for key in secondDict.keys():
#测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
if type(secondDict[key]).__name__=='dict':
thisDepth = 1 + getTreeDepth(secondDict[key])
else: thisDepth = 1
# 更新层数
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth
#输出预先存储的树信息
def retrieveTree(i):
"""
用于测试的预定义的树结构
"""
listOfTrees = [{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},
{'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
]
return listOfTrees[i]
//标注有向边属性值
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]#计算标注位置
yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
#绘制决策树
def plotTree(myTree, parentPt, nodeTxt):
# 设置结点格式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
# 设置叶结点格式
leafNode = dict(boxstyle="round4", fc="0.8")
# 获取决策树叶结点数目，决定了树的宽度
numLeafs = getNumLeafs(myTree)
# 获取决策树层数
depth = getTreeDepth(myTree)
# 下个字典
firstStr = next(iter(myTree))
# 中心位置
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
# 标注有向边属性值
plotMidText(cntrPt, parentPt, nodeTxt)
# 绘制结点
plotNode(firstStr, cntrPt, parentPt, decisionNode)
# 下一个字典，也就是继续绘制子结点
secondDict = myTree[firstStr]
# y偏移
plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
for key in secondDict.keys():
# 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点不是叶结点，递归调用继续绘制
if type(secondDict[key]).__name__=='dict':
plotTree(secondDict[key],cntrPt,str(key))
# 如果是叶结点，绘制叶结点，并标注有向边属性值
else:
plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
#创建绘制面板:
def createPlot(inTree):
# 创建fig
fig = plt.figure(1, facecolor='white')
# 清空fig
fig.clf()
axprops = dict(xticks=[], yticks=[])
# 去掉x、y轴
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
# 获取决策树叶结点数目
plotTree.totalW = float(getNumLeafs(inTree))
# 获取决策树层数
plotTree.totalD = float(getTreeDepth(inTree))
# x偏移
plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
# 绘制决策树
plotTree(inTree, (0.5,1.0), '')
# 显示绘制结果
plt.show()
#main
if __name__ == '__main__':
myTree = retrieveTree(0)
createPlot(myTree)
运行截图：
5.使用决策树执行分类（代码实现）
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子节点；最后将测试数据定义为叶子节点所属的类型。
代码如下：
"""
Parameters:
inputTree - 已经生成的决策树
featLabels - 存储选择的最优特征标签
testVec - 测试数据列表，顺序对应最优特征标签
Returns:
classLabel - 分类结果
"""
def classify(inputTree, featLabels, testVec):
# 获取决策树结点
firstStr = next(iter(inputTree))
# 下一个字典
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key], featLabels, testVec)
else: classLabel = secondDict[key]
return classLabel
6.决策树的存储（代码实现）
构造决策树是很耗时的任务，即使处理很小的数据集，如前面的样本数据，也要花费几秒的时间，如果数据集很大，将会耗费很多计算时间。然而用创建好的决策树解决分类问题，则可以很快完成。因此，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树
代码如下：
def storeTree(inputTree, filename):
with open(filename, 'wb') as fw:
pickle.dump(inputTree, fw)
def grabTree(filename):
fr = open(filename, 'rb')
return pickle.load(fr)
四、 实例：预测车辆状况
车辆的状况分为四类:
unacc (Unacceptable 状况很差)
acc (Acceptable 状况一般)
good (Good 状况好)
vgood (Very good 状况非常好)
通过一下分类属性来判断车辆的状况：
buying (购买价: vhigh, high, med, low)
maint (维护价: vhigh, high, med, low)
doors (几个门: 2, 3, 4, 5more)
persons (载人量: 2, 4, more)
lug_boot (贮存空间: small, med, big)
safety (安全性: low, med, high)
数据样本：
代码实现：
if __name__ == '__main__':
fr = open('carTrain.txt')
cars = [inst.strip().split('\t') for inst in fr.readlines()]
carLabels = ['buying', 'maint', 'doors', 'persons', 'lub_boot', 'safety']
carsTree = createTree(cars, carLabels)
print(carsTree)
createPlot(carsTree)
测试结果
>>>
{'safety': {'low': 'unacc', 'med': {'persons': {'2': 'unacc', '4': {'buying': {'low': {'maint': {'low': 'acc', 'med': 'good', 'high': 'acc', 'vhigh': 'acc'}}, 'med': {'maint': {'low': 'acc', 'med': 'acc', 'high': 'unacc', 'vhigh': 'acc'}}, 'high': {'maint': {'low': 'unacc', 'med': 'acc', 'high': 'unacc', 'vhigh': 'unacc'}}, 'vhigh': {'maint': {'low': 'unacc', 'med': 'acc', 'high': 'unacc', 'vhigh': 'unacc'}}}}, 'more': {'buying': {'low': {'maint': {'med': {'doors': {'2': 'good', '3': 'good', '4': 'acc'}}, 'vhigh': {'doors': {'2': 'acc', '3': 'acc', '4': 'unacc'}}}}, 'med': {'doors': {'2': 'acc', '3': 'acc', '4': {'maint': {'med': 'acc', 'vhigh': 'unacc'}}}}, 'high': {'maint': {'med': {'doors': {'2': 'acc', '3': 'acc', '4': 'unacc'}}, 'vhigh': 'unacc'}}, 'vhigh': {'maint': {'med': {'doors': {'2': 'acc', '3': 'acc', '4': 'unacc'}}, 'vhigh': 'unacc'}}}}}}, 'high': {'persons': {'4': {'buying': {'low': {'maint': {'med': {'doors': {'2': 'vgood', '3': 'good', '4': 'good'}}, 'vhigh': 'acc'}}, 'med': {'doors': {'2': {'maint': {'med': 'vgood', 'vhigh': 'acc'}}, '3': 'acc', '4': 'acc'}}, 'high': {'maint': {'med': 'acc', 'vhigh': 'unacc'}}, 'vhigh': {'maint': {'med': 'acc', 'vhigh': 'unacc'}}}}, '2': 'unacc', 'more': {'buying': {'low': {'doors': {'4': 'vgood', '3': 'vgood', '5more': {'maint': {'low': 'good', 'high': 'acc'}}}}, 'med': {'maint': {'low': {'doors': {'4': 'vgood', '3': 'vgood', '5more': 'good'}}, 'high': 'acc'}}, 'high': 'acc', 'vhigh': {'maint': {'low': 'acc', 'high': 'unacc'}}}}}}}}
五、 总结
1.三者比较
2.何时停止决策树的分裂
决策树不可能不限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩下一个数据点时自动结束分裂，但这种情况下树过于复杂，而且预测的经度不高。一般情况下为了降低决策树复杂度和提高预测的经度，会适当提前终止节点的分裂。
以下是决策树节点停止分裂的一般性条件：
（1）最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
（2）熵或者基尼值小于阀值。
? 由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。
（3）决策树的深度达到指定的条件
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
（4）所有特征已经使用完毕，不能继续进行分裂。
? 被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。