机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。
决策树，其结构和树非常相似，因此得其名决策树。决策树具有树形的结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
例如：
按照豆腐脑的冷热、甜咸和是否含有大蒜构建决策树，对其属性的测试，在最终的叶节点决定该豆腐脑吃还是不吃。
分类树（决策树）是一种十分常用的将决策树应用于分类的机器学习方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性（特征）和一个类别（分类信息/目标），这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。
其原理在于，每个决策树都表述了一种树型结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。
机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
目前常用的决策树算法有ID3算法、改进的C4.5算法和CART算法。
决策树的特点
1.多层次的决策树形式易于理解；
2.只适用于标称型数据，对连续性数据处理得不好；
2、ID3算法
ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法以信息论为基础，其核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。
信息熵（Entropy）:
,其中p(xi)是选择i的概率。
熵越高，表示混合的数据越多。信息增益（Information Gain）:
T是划分之后的分支集合，p(t)是该分支集合在原本的父集合中出现的概率，H(t)是该子集合的信息熵。
3.ID3算法与决策树的流程
（1）数据准备：需要对数值型数据进行离散化
（2）ID3算法构建决策树：
如果数据集类别完全相同，则停止划分
否则，继续划分决策树：
计算信息熵和信息增益来选择最好的数据集划分方法；
划分数据集
创建分支节点：
对每个分支进行判定是否类别相同，如果相同停止划分，不同按照上述方法进行划分。
二、Python算法实现
创建 trees.py文件，在其中创建构建决策树的函数。
首先构建一组测试数据：
0. 构造函数createDataSet：
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
在Python控制台测试构造函数
#测试下构造的数据Out[5]: ['no surfacing', 'flippers']
2.1 计算信息熵
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet) #nrows
#为所有的分类类目创建字典
labelCounts ={}
for featVec in dataSet:
currentLable=featVec[-1] #取得最后一列数据
if currentLable not in labelCounts.keys():
labelCounts[currentLable]=0
labelCounts[currentLable]+=1
#计算香农熵
shannonEnt=0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt
利用构造的数据测试calcShannonEnt：
#Python console
In [6]: trees.calcShannonEnt(myDat)
...:
Out[6]: 0.9709505944546686
2.2 按照最大信息增益划分数据集
#定义按照某个特征进行划分的函数splitDataSet在控制台中测试这两个函数：
#测试按照特征划分数据集的函数Out[14]: 0
2.3 创建决策树构造函数createTree
import operater以之前构造的测试数据为例，对决策树构造函数进行测试，在python控制台进行输入：
#决策树构造函数测试可以看到，最后生成的决策树myTree是一个多层嵌套的字典。
2.4 决策树运用于分类
#输入三个变量（决策树，属性特征标签，测试的数据）对决策树分类函数进行测试：
In [29]: reload(trees)Out[35]: 'yes'
2.5 决策树的存储
如果每次都需要训练样本集来构建决策树，费时费力，特别是数据很大的时候，每次重新构建决策树浪费时间。因此可以将已经创建的决策树（如字典形式）保存在硬盘上，需要使用的时候直接读取就好。
（1）存储函数
在工作目录下存在一个名为’classifierStorage.txt’的txt文档，该文档 保存了myTree的决策树信息，需要使用的时候直接调出使用。
三、使用Matplotlib绘制决策树
import matplotlib.pyplot as plt
from pylab import *
mpl.rcParams['font.sans-serif'] = ['SimHei'] #否则中文无法正常显示
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 createPlot():
fig=plt.figure(1,facecolor='white')
fig.clf()
createPlot.ax1=plt.subplot(111,frameon=False)
plotNode('决策节点',(0.5,0.1),(0.1,0.5),decisionNode)
plotNode('叶节点',(0.8,0.1),(0.3,0.8),leafNode)
plt.show()
#测试
#获取叶节点数量（广度）
def getNumLeafs(myTree):
numLeafs=0
firstStr=list(myTree.keys())[0]#'dict_keys' object does not support indexing
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 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+cntrPt[0]
yMid=(parentPt[1]-cntrPt[1])/2+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/plotTree.totalW,plotTree.yOff)
plotMidText(cntrPt,parentPt,nodeTxt)
plotNode(firstStr,cntrPt,parentPt,decisionNode)
secondDict=myTree[firstStr]
plotTree.yOff=plotTree.yOff -1/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/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()
对绘制决策树图的函数进行测试（控制台）：
In [26]: reload(treeplotter)
...:
Out[26]: <module 'treeplotter' from 'G:\\Workspaces\\MachineLearning\\treeplotter.py'>
In [27]: myTree=treeplotter.retrieveTree(0)
...:
In [28]: treeplotter.createPlot(myTree)
...:
得到决策树图：
隐形眼镜的数据集包含了患者的四个属性age，prescript，stigmatic，tearRate，利用这些数据构建决策树，并通过Matplotlib绘制出决策树的树状图。
附lenses.txt数据：
得到图
数据分析咨询请扫描二维码
