- 一 决策树简介
- 二 决策树的构造
- 1.决策树的优缺点
- 2.决策树的一般流程
- 3.信息增益
- 4 划分数据集
- 5 递归构建决策树
- 三 绘制树形图
- 1 代码实现
- 2 运行结果
- 四 测试和存储分类器
- 1.使用决策树执行分类
- 2.决策树的存储
- 五 实战：预测隐形眼镜类型
- 1.代码实现
- 2.运行结果
你是否玩过二十个问题的游戏，游戏的规则很简单：参与游戏的一方在脑海里想某个事物，其他参与者向他提问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围。或者是酒桌上的猜数游戏，游戏规则有点类似，参与游戏的一方在脑海里想一个固定的数值，需要在固定的范围内，其他参与者进行猜测，他会先给出猜测的正确与否，如果正确直接喝酒，如果错误，就在下一个参与者开始之前给出新的猜数范围，逐步缩小待猜测事物的范围。
决策树的工作原理与上面两个游戏类似，用户输入一系列数据，然后给出游戏的答案。我们经常使用决策树处理分类问题，近来的调查表明决策树也是最经常使用的数据挖掘算法。它之所以如此流行，一个很重要的原因就是不需要了解机器学习的知识，就能搞明白决策树是如何工作的。
如果以前没有接触过决策树，也完全不用担心，它的概念非常简单。通过简单的图形就可以了解其工作原理，图3-1所示的流程图就是一个决策树，长方形代表 判断模块（decision block），椭圆形代表 终止模块（terminating block），表示已经得出结论，可以终止运行。从 判断模块 引出的左右箭头称作 分支（branch），它可以到达另一个判断模块或者终止模块。
上面构造的是一个假想的邮件分类系统， 首先它检测发送邮件域名地址：
如果地址为myEmployer.com，则将其放在分类“无聊时需要阅读的邮件”中。
如果邮件不是来自这个域名，则检查邮件内容里是否包含单词曲棍球。
如果包含则将邮件归类到“需要及时处理的朋友邮件”。
如果不包含则将邮件归类到“无需阅读的垃圾邮件”。
第二章介绍的k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，在这些机器根据数据集创建规则时，就是 机器学习 的过程。
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。
(1) 收集数据：可以使用任何方法。
(2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
(3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
(4) 训练算法：构造树的数据结构。
(5) 测试算法：使用经验树计算错误率。
(6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
划分数据集的大原则是：将无序的数据变得更加有序
在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择 。
在可以评测哪种数据划分方式就是最好的数据划分之前，必须学习如何计算信息增益。集合信息的度量方式称为香农熵 或者简称为熵 。
代码实现
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
4 划分数据集
分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以便判断当前是否正确地划分了数据集。对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。
代码实现
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
5 递归构建决策树
工作原理：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。
代码实现
#多数表决
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
三 绘制树形图
1 代码实现
#获得叶节点的数目
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)
2 运行结果
四 测试和存储分类器
1.使用决策树执行分类
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子节点；最后将测试数据定义为叶子节点所属的类型。
代码实现
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
2.决策树的存储
构造决策树是很耗时的任务，即使处理很小的数据集，如前面的样本数据，也要花费几秒的时间，如果数据集很大，将会耗费很多计算时间。然而用创建好的决策树解决分类问题，则可以很快完成。因此，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。
代码实现
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)
五 实战：预测隐形眼镜类型
1.代码实现
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import LabelEncoder, oneHotEncoder
from sklearn.externals.six import StringIO
from sklearn import tree
if __name__ == '__main__':
with open('lenses.txt', 'r') as fr: #加载文件
lenses = [inst.strip().split('t') for inst in fr.readlines()]#处理文件
lenses_target = [] #提取每组数据的类别，保存在列表里
for each in lenses:
lenses_target.append(each[-1])
print(lenses_target)
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate'] #特征标签
lenses_list = [] #保存lenses数据的临时列表
lenses_dict = {} #保存lenses数据的字典，用于生成pandas
for each_label in lensesLabels: #提取信息，生成字典
for each in lenses:
lenses_list.append(each[lensesLabels.index(each_label)])
lenses_dict[each_label] = lenses_list
lenses_list = []
# print(lenses_dict) #打印字典信息
lenses_pd = pd.Dataframe(lenses_dict) #生成pandas.Dataframe
# print(lenses_pd) #打印pandas.Dataframe
le = LabelEncoder() #创建LabelEncoder()对象，用于序列化
for col in lenses_pd.columns: #序列化
lenses_pd[col] = le.fit_transform(lenses_pd[col])
# print(lenses_pd) #打印编码信息
clf = tree.DecisionTreeClassifier(max_depth = 4) #创建DecisionTreeClassifier()类
# clf = clf.fit(lenses_pd.values.tolist(), lenses_target) #使用数据，构建决策树
tree.plot_tree(clf.fit(lenses_pd.values.tolist(), lenses_target), filled=True)
plt.show()
2.运行结果
