3.1决策树的构造
第二章介绍的k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。
优点：计算复杂度不高，输出结果易于理解，对中间值缺失不敏感，可以处理不相关特征数据
缺点：可能会产生过度匹配问题
适用数据类型：数值型和标称型
决策树经常用于解决处理分类问题，它的一个重要任务是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集并从中提取出一系列规则，这些机器根据数据集创建规则的过程，就是机器学习的过程。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌人类专家。
决策树的一般流程：
1、收集数据：可以使用任何方法
2、准备数据：树构造的算法只适用于标称型数据，因此数值型数据必须离散化
3、分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
4、训练算法：构造树的数据结构
5、测试算法：使用经验树计算错误率
6、使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好的理解数据的内在含义
3.1.1信息增益
划分数据集的最大原则：将无序的数据变得有序。组织杂乱无章数据的一种方式就是使用信息论度量信息，量信息是量化处理信息的分支科学。我们可以在划分数据之前或之后使用信息量化度量信息的内容。
划分数据之前之后信息发生的变化称之为信息增益，知道如何计算信息增益，就可以计算每一个特征值划分数据集获得信息增益，获得信息增益最高的特征就是最好的选择。
集合信息的度量方式是香农熵或简称熵。熵定义信息的期望值，若待分类的事务可能划分在多个分类之中，则符号$x_{i}$的信息定义为：
$$ I(x_{i})=-log_{2}p(x_{i}) $$
其中$p(x_{i})$是选择该分类的概率。
为了计算熵，需要计算所有类别所有可能包含的信息期望，通过下面公式得到：
$$ H=-\sum _{i=1}^{n}p(x_{i})log_{2}p(x_{i}) $$
熵越高，混合的数据也就越多。得到熵之后，可以按照获取最大信息增益的方法划分数据集。
使用Python计算给定数据集的香农熵：
代码：
trees.py:
'''
功能：计算给定数据集的香农熵
'''
from math import log
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 -= 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, labelsmain.py:
import trees
myDat, labels = trees.createDataSet()
print(trees.calcShannonEnt(myDat))
'''
熵越高，则混合的数据也越多
在数据集中添加更多的分类，观察熵是如何变化的。
'''
myDat[0][-1] = 'maybe'
print(trees.calcShannonEnt(myDat))结果：
3.1.2划分数据集
在trees.py中添加下列代码：
#按照给定特征划分数据集
def splitDataSet(dataSet, axis, value): #参数分别为：待划分的数据集，划分数据集的特征，特征返回值
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
'''
遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。
熵计算将会告诉我们如何划分数据集是最好的数据组织方式。
'''
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 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
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy
if (infoGain > bestInfoGain): #compare this to the best gain so far
bestInfoGain = infoGain #if better than current best, set to best
bestFeature = i
return bestFeature #returns an integer在main.py中添加下列代码：
#测试splitDataSet()函数
print(trees.splitDataSet(myDat,0,1))
print(trees.splitDataSet(myDat,0,0))
#测试chooseBestFeatureToSplit()函数
print(trees.chooseBestFeatureToSplit(myDat))
print(myDat)结果：
分析：
通过结果可得出结论：第0个特征是最好的用于划分数据集的特征。
3.1.3递归构建决策树
工作原理：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。
在trees.py中添加下列代码：
import operator
'''
该函数使用分类名称的列表，然后创建键值为classList中唯一值的数据字典。
字典对象存储了classList中每个类标签出现的频率。
最后利用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 createTree(dataSet,labels): #参数：数据集和标签列表
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList):
return classList[0]#stop splitting when all of the classes are equal
if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}} #字典myTree存储了树的所有信息
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
#遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
for value in uniqueVals:
subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree在main.py中添加下列代码：
#测试createTree()函数
myTree = trees.createTree(myDat,labels)
print(myTree)结果：
分析：
第一个关键字 no surfacing 是第一个划分数据集的特征名称，该关键字的值也是另一个数据字典。第二个关键字是 no surfacing 特征划分的数据集，这些关键字的值是no surfacing节点的子节点。这些值可能是类标签，也可能是另一个数据字典。如果值是类标签，则该子节点是叶子节点；如果值是另一个数据字典，则子节点是一个判断节点。这种格式结构不断重复就构成了整棵树。
3.2在Python中使用Matplotlib注解绘制树形图
3.2.1Matplotlib注解
使用Matplotlib的注解功能绘制树形图，它可以对文字着色并提供多种形状以供选择，而且我们还可以反转箭头，将它指向文本框而不是数据点。
3.2.2构造注解树
绘制一颗完整的树需要一些技巧。我们虽然有x、y坐标，但是如何放置所有的树节点却是个问题。我们必须知道有多少个叶节点，以便可以正确确定x轴的长度；我们还需要知道树有多少层，以便可以正确确定y轴的高度。
创建名为treePlotter.py的新文件，然后输入代码：
import matplotlib.pyplot as plt
from trees import createTree
# 使用matplotlib的注释功能绘制树形图
# 用文本注解绘制树节点
# 定义文本框和箭头格式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
# 绘制带箭头的注解
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
# 构造注解树
# 获取叶节点的数目
def getNumLeafs(myTree):
numLeafs = 0
firstStr = list(myTree.keys())[0]
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
firstStr = list(myTree.keys())[0]
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 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)
def plotTree(myTree, parentPt, nodeTxt):
# 计算宽和高
numLeafs = getNumLeafs(myTree)
depth = getTreeDepth(myTree)
firstStr = list(myTree.keys())[0]
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 = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW
plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show()
# 输出预先存储的树信息
def retrieveTree(i):
listOfTree = [{'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 listOfTree[i]测试代码：
if __name__ == "__main__":
print(retrieveTree(1))
# result:{'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', '1': 'yes'}}, 1: 'no'}}}}
myTree = retrieveTree(0)
print(getNumLeafs(myTree)) # 3
print(getTreeDepth(myTree)) # 2
createPlot(myTree)结果：
3.3测试和存储分类器
3.3.1测试算法：使用决策树执行分类
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进人叶子节点；最后将测试数据定义为叶子节点所属的类型。
在trees.py中添加下列代码：
#使用决策树的分类函数
def classify(inputTree,featLabels,testVec):
firstStr = list(inputTree)[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr) #将标签换为索引
key = testVec[featIndex]
valueOfFeat = secondDict[key]
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
else: classLabel = valueOfFeat
return classLabel在main.py中添加下列代码：
import trees
import treePlotter
#测试classify()函数
dataSet,labels=trees.createDataSet()
myTree=treePlotter.retrieveTree(0)
print(trees.classify(myTree,labels,[1,0]))
print(trees.classify(myTree,labels,[1,1]))结果：
分析：
比较上述输出结果。第一节点名为 no surfacing ，它有两个子节点：一个是名字为0的叶子节点，类标签为no; 另一个是名为flippers的判断节点，此处进人递归调用，flippers节点有两个子节点。
3.3.2使用算法：决策树的存储
为了节省更多的计算时间，最好能够在每次执行分类时调用已经构建好的决策树，需要使用python模块pickle序列化对象。序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。
3.4示例：使用决策树预测隐形眼镜类型
代码：
from math import log
import operator
import matplotlib.pyplot as plt
# 程序清单3-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 -= prob * log(prob, 2)
return shannonEnt
# 程序清单3-2：按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet
# 程序清单3-3：选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 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 * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
# 统计classList中出现此处最多的元素（类标签）,即选择出现次数最多的结果
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
# 程序清单3-4：创建决策树
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 = labels[:]
mytree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return mytree
# 程序清单3-5：使用文本注解绘制树节点
# decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")
# leafNode = dict(boxstyle = "round4", fc = "0.8")
# arrow_args = dict(arrowstyle = "<-")
# 程序清单3-5：绘制带箭头的注解
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
arrow_args = dict(arrowstyle="<-")
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt,
textcoords='axes fraction', va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
# 程序清单3-5：创建绘图区，计算树形图的全局尺寸
def createPlot(inTree):
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW;
plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show()
# 程序清单3-6：获取叶节点的数目
def getNumLeafs(myTree):
numLeafs = 0 # 初始化叶子
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
# 程序清单3-6：获取树的层数
def getTreeDepth(myTree):
maxDepth = 0
firstStr = list(myTree.keys())[0]
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
# 程序清单3-7：标注有向边属性
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)
# 程序清单3-7：绘制决策函数
def plotTree(myTree, parentPt, nodeTxt):
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
numLeafs = getNumLeafs(myTree)
defth = getTreeDepth(myTree)
firstStr = list(myTree.keys())[0]
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt)
plotNode(firstStr, cntrPt, parentPt, decisionNode)
secondeDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
for key in secondeDict.keys():
if type(secondeDict[key]) is dict:
plotTree(secondeDict[key], cntrPt, str(key))
else:
plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
plotNode(secondeDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
if __name__ == '__main__':
fr = open('lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
print(lenses)
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
myTree_lenses = createTree(lenses, lensesLabels)
createPlot(myTree_lenses)