决策树（Decision Tree）

决策树的定义:

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型: 内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。

用决策树对需要测试的实例进行分类: 从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。

每次寻找最优的特征列，那么该如何找到呢，使用的是香农熵：

$H(x)=-\sum_{i=1}^{n}p(x_{i})log(p(x_{i}))$

$p(x_{i})$ 代表随机事件x的概率

信息量是对信息的度量，就跟时间的度量是秒一样，当我们考虑一个离散的随机变量 x 的时候，当我们观察到的这个变量的一个具体值的时候，我们接收到了多少信息呢？

多少信息用信息量来衡量，我们接受到的信息量跟具体发生的事件有关。

信息的大小跟随机事件的概率有关。越小概率的事情发生了产生的信息量越大，如湖南产生的地震了；越大概率的事情发生了产生的信息量越小，如太阳从东边升起来了（肯定发生嘛，没什么信息量）。因此一个具体事件的信息量应该是随着其发生概率而递减的，且不能为负。

假如有两个不相关事件，x和y，两个事件同时发生时获得的信息应该等于观察到的事件各自发生时获得的信息之和，即：h(x,y)=h(x)+h(y)

而两个事件同时发生的概率为p(x,y)=p(x)*p(y)

这里就可以看出h(x,y)和p(x,y)的关系为对数关系

h(x,y)=log(p(x,y))=log(p(x))+log(p(y))

所以 $h(x)=-\log (p(x))$ （log是以2为底）

前面加个负号是因为信息量为正数

信息熵下面正式引出信息熵：信息量度量的是一个具体事件发生了所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望。即

$H(x)=-\sum_{i=1}^{n}p(x_{i})log(p(x_{i}))$

信息熵还可以作为一个系统复杂程度的度量，如果系统越复杂，出现不同情况的种类越多，那么他的信息熵是比较大的。如果一个系统越简单，出现情况种类很少（极端情况为 1 种情况，那么对应概率为 1，那么对应的信息熵为 0），此时的信息熵较小。

例子：

数据集：

1.5 50 thin
1.5 60 fat
1.6 40 thin
1.6 60 fat
1.7 60 thin
1.7 80 fat
1.8 60 thin
1.8 90 fat
1.9 70 thin
1.9 80 thin

第一列身高，第二列体重，第三列label

首先，对两列特征值分别进行计算，从第一列开始，以1.5为特征值划分数据集为

50 thin

60 fat

计算香农熵：

$\frac{2}{10}\left ( -\frac{1}{2}log(\frac{1}{2}) -\frac{1}{2}log(\frac{1}{2}) \right)$

然后再以1.6划分：

。。。。

第一列划分完再把这一列香农熵加起来，再划分第二列，同第一列步骤一致，加起来后和第一列比较，找到香农熵最小的feature列分类。

下一层树再以同样的方式进行分类。

from  numpy import *
from __future__ import print_function
import operator
from os import listdir
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt
import mathdef createDataSet():dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels=['no surfacing','flippers']return dataSet,labels#计算香农熵函数
def calcShannonEnt(dataSet):"""calcShannonEnt(calculate Shannon entropy 计算给定数据集的香农熵)Args:dataSet 数据集Returns:返回 每一组feature下的某个分类下，香农熵的信息期望"""# -----------计算香农熵的第一种实现方式start--------------------------------------------------------------------------------# 求list的长度，表示计算参与训练的数据量numEntries = len(dataSet)# 下面输出我们测试的数据集的一些信息# 例如: <type 'list'> numEntries:  5 是下面的代码的输出# print type(dataSet), 'numEntries: ', numEntries# 计算分类标签label出现的次数labelCounts = {}# the the number of unique elements and their occurancefor featVec in dataSet:# 将当前实例的标签存储，即每一行数据的最后一个数据代表的是标签currentLabel = featVec[-1]# 为所有可能的分类创建字典，如果当前的键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1# print '-----', featVec, labelCounts# 对于label标签的占比，求出label标签的香农熵shannonEnt = 0.0for key in labelCounts:# 使用所有类标签的发生频率计算类别出现的概率。prob = float(labelCounts[key])/numEntries# log base 2 # 计算香农熵，以 2 为底求对数shannonEnt -= prob * math.log(prob, 2)# print '---', prob, prob * log(prob, 2), shannonEnt# -----------计算香农熵的第一种实现方式end--------------------------------------------------------------------------------# # -----------计算香农熵的第二种实现方式start--------------------------------------------------------------------------------# # 统计标签出现的次数# label_count = Counter(data[-1] for data in dataSet)# # 计算概率# probs = [p[1] / len(dataSet) for p in label_count.items()]# # 计算香农熵# shannonEnt = sum([-p * log(p, 2) for p in probs])# # -----------计算香农熵的第二种实现方式end--------------------------------------------------------------------------------return shannonEnt
def splitDataSet(dataSet,index,value):retDataSet=[]for featVec in dataSet:if featVec[index]==value:reducedFeatVec=featVec[:index]'''请百度查询一下:  extend和append的区别music_media.append(object) 向列表中添加一个对象objectmusic_media.extend(sequence) 把一个序列seq的内容添加到列表中 (跟 += 在list运用类似， music_media += sequence)1、使用append的时候，是将object看作一个对象，整体打包添加到music_media对象中。2、使用extend的时候，是将sequence看作一个序列，将这个序列和music_media序列合并，并放在其后面。music_media = []music_media.extend([1,2,3])print music_media#结果: #[1, 2, 3]music_media.append([4,5,6])print music_media#结果: #[1, 2, 3, [4, 5, 6]]music_media.extend([7,8,9])print music_media#结果: #[1, 2, 3, [4, 5, 6], 7, 8, 9]'''reducedFeatVec.extend(featVec[index+1:])retDataSet.append(reducedFeatVec)return retDataSet
'''
这块是选择最好的特征列
选取最大的信息熵
gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值
信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。
'''
def chooseBestFeatureToSplit(dataSet):"""chooseBestFeatureToSplit(选择最好的特征)Args:dataSet 数据集Returns:bestFeature 最优的特征列"""# -----------选择最优特征的第一种方式 start------------------------------------# 求第一行有多少列的 Feature, 最后一列是label列嘛numFeatures = len(dataSet[0]) - 1# label的信息熵baseEntropy = calcShannonEnt(dataSet)# 最优的信息增益值, 和最优的Featurn编号bestInfoGain, bestFeature = 0.0, -1# iterate over all the featuresfor i in range(numFeatures):featList=[example[i] for example in dataSet]'''a=[[1,1,1],[2,1,0]]a1=[a2[1] for a2 in a]print(a1)打印集合列'''#对列元素去重uniqueVals=set(featList)#创建临时的信息熵newEntropy=0.0#遍历某一列的value集合，计算该列的信息熵#遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和for value in uniqueVals:subDataSet=splitDataSet(dataSet,i,value)prob=len(subDataSet)/float(len(dataSet))newEntropy+=prob*calcShannonEnt(subDataSet)infoGain=baseEntropy-newEntropyprint('infoGain=',infoGain,'bestFeature=',i,baseEntropy,newEntropy)if(infoGain>bestInfoGain):bestInfoGain=infoGainbestFeature=ireturn bestFeaturedef majorityCnt(classList):classCount={}for vote in classList:if vote not in classCount.keys():classCount[vote]=0;classCount[vote]+=1;# 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)return sortedClassCount[0][0]
def createTree(dataSet,labels):classList=[example[-1] for example in dataSet]# 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行# 第一个停止条件: 所有的类标签完全相同，则直接返回该类标签。# count() 函数是统计括号中的值在list中出现的次数if classList.count(classList[0])==len(classList):return classList[0]if len(dataSet[0])==1:return majorityCnt(classList)# 选择最优的列，得到最优列对应的label含义bestFeat=chooseBestFeatureToSplit(dataSet)bestFeatLabel=labels[bestFeat]#初始化myTree'''a=[[1,1,1],[2,1,0]]a1= ['age', 'prescript', 'astigmatic', 'tearRate']a3=a1[0]a2={a3:{}}a2[a3][1]='1'a2[a3]['2']='1'print(a2)输出{'age': {1: '1', '2': '1'}}'''myTree={bestFeatLabel:{}}# 注: labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改# 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in listdel(labels[bestFeat])# 取出最优列，然后它的branch做分类featValues=[example[bestFeat]for example in dataSet]uniqueVals=set(featValues)for value in uniqueVals:# 求出剩余的标签labelsubLabels=labels[:]# 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)return myTree
def classify(inputTree,featLabels,testVec):"""classify(给输入的节点，进行分类)Args:inputTree  决策树模型featLabels Feature标签对应的名称testVec    测试输入的数据Returns:classLabel 分类的结果值，需要映射label才能知道名称"""# 获取tree的根节点对于的key值firstStr=inputTree.keys()[0]# 通过key得到根节点对应的valuesecondDict=inputTree[firstStr]# 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类featIndex=featLabels.index(firstStr)# 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类key=testVec[featIndex]valueOfFeat=secondDict[key]print('+++',firstStr,'xxx',secondDict,'---',key,'>>>',valueOfFeat)# 判断分枝是否结束: 判断valueOfFeat是否是dict类型if isinstance(valueOfFeat,dict):classLabel=classify(valueOfFeat,featLabels,testVec)else:classLabel=valueOfFeat#因为最后一列是label列，所以直接返回就行return classLabel
def storeTree(inputTree,filename):import pickle# -------------- 第一种方法 start --------------#fw=open(filename,'wb')#pickle.dump(inputTree,fw)#fw.close()# -------------- 第一种方法 end --------------# -------------- 第二种方法 start --------------with open(filename,'wb') as fw:pickle.dump(inputTree,fw)# -------------- 第二种方法 start --------------   
def grabTree(filename):import picklefr=open(filename,'rb')return pickle.load(fr)
def fishTest():# 1.创建数据和结果标签myDat,labels=createDataSet()# print myDat, labels# 计算label分类标签的香农熵# calcShannonEnt(myDat)# # 求第0列 为 1/0的列的数据集【排除第0列】# print '1---', splitDataSet(myDat, 0, 1)# print '0---', splitDataSet(myDat, 0, 0)# # 计算最好的信息增益的列# print chooseBestFeatureToSplit(myDat)import copymyTree=createTree(myDat,copy.deepcopy(labels))print(myTree)#[i,j]表示要取的分支上的节点位置，对应的结果值print(classify(myTree,labels,[1,1]))# 获得树的高度print(get_tree_height(myTree))print(myTree.keys()[0])#画图可视化展现createPlot(myTree)
def get_tree_height(tree):"""Desc:递归获得决策树的高度Args:treeReturns:树高"""if not isinstance(tree, dict):return 1child_trees = tree.values()[0].values()# 遍历子树, 获得子树的最大高度max_height = 0for child_tree in child_trees:child_tree_height = get_tree_height(child_tree)if child_tree_height > max_height:max_height = child_tree_heightreturn max_height + 1
#decisionTreePlot画图类
# 定义文本框 和 箭头格式 【 sawtooth 波浪方框, round4 矩形方框 , fc表示字体颜色的深浅 0.1~0.9 依次变浅，没错是变浅】
decisionNode=dict(boxstyle="sawtooth",fc="0.8")
leafNode=dict(boxstyle="round4",fc="0.8")
arrow_args=dict(arrowstyle="<-")def getNumLeafs(myTree):numLeafs=0firstStr=myTree.keys()[0]secondDict=myTree[firstStr]#根节点开始遍历for key in secondDict.keys():# 判断子节点是否为dict, 不是+1if type(secondDict[key]) is dict:numLeafs+=getNumLeafs(secondDict[key])else:numLeafs+=1return numLeafs
def getTreeDepth(myTree):maxDepth=0firstStr=myTree.keys()[0]secondDict=myTree[firstStr]#根节点开始遍历for key in secondDict.keys():# 判断子节点是不是dict, 求分枝的深度if type(secondDict[key]) is dict:thisDepth=1+getTreeDepth(secondDict[key])else:thisDepth=1#记录最大的分支深度if thisDepth>maxDepth:maxDepth=thisDepthreturn maxDepth
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 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)
'''
说明
函数.变量
如plotTree.xoff
表示plotTree的静态变量
def k():k.i=0
def k1():k.i=1
k1()
print(k.i)
输出为1
'''
def plotTree(myTree,parentPt,nodeTxt):#获取叶子节点的数量numLeafs=getNumLeafs(myTree)# 获取树的深度# depth = getTreeDepth(myTree)# 找出第1个中心点的位置，然后与 parentPt定点进行划线# x坐标为 (numLeafs-1.)/plotTree.totalW/2+1./plotTree.totalW，化简如下cntrPt=(plotTree.xoff+(1.0+float(numLeafs))/2.0/plotTree.totalW,plotTree.yoff)# print cntrPt# 并打印输入对应的文字plotMidText(cntrPt,parentPt,nodeTxt)firstStr=myTree.keys()[0]# 可视化Node分支点；第一次调用plotTree时，cntrPt与parentPt相同plotNode(firstStr,cntrPt,parentPt,decisionNode)#根节点的值secondDict=myTree[firstStr]# y值 = 最高点-层数的高度[第二个节点位置]；1.0相当于树的高度plotTree.yoff = plotTree.yoff - 1.0 / plotTree.totalDfor key in secondDict.keys():# 判断该节点是否是Node节点if type(secondDict[key]) is dict:# 如果是就递归调用[recursion]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):# 创建一个figure的模版fig=plt.figure(1,facecolor='green')fig.clf()axprops=dict(xticks=[],yticks=[])# 表示创建一个1行，1列的图，createPlot.ax1 为第 1 个子图，createPlot.ax1=plt.subplot(111,frameon=False,**axprops)plotTree.totalW=float(getNumLeafs(inTree))plotTree.totalD=float(getTreeDepth(inTree))print(plotTree.totalD)# 半个节点的长度；xOff表示当前plotTree未遍历到的最左的叶节点的左边一个叶节点的x坐标# 所有叶节点中，最左的叶节点的x坐标是0.5/plotTree.totalW（因为totalW个叶节点在x轴方向是平均分布在[0, 1]区间上的）# 因此，xOff的初始值应该是 0.5/plotTree.totalW-相邻两个叶节点的x轴方向距离plotTree.xoff=-0.5/plotTree.totalW# 根节点的y坐标为1.0，树的最低点y坐标为0plotTree.yoff=1.0# 第二个参数是根节点的坐标plotTree(inTree,(0.5,1.0),'')plt.show()
fishTest()
ef ContactLensesTest():"""Desc:预测隐形眼镜的测试代码Args:noneReturns:none"""# 加载隐形眼镜相关的 文本文件 数据fr=open('3.DecisionTree/lenses.txt')# 解析数据，获得 features 数据lenses=[inst.strip().split('\t') for inst in fr.readlines()]# 得到数据的对应的 LabelslensesLabels=['age','prescript','astigmatic','tearRate']# 使用上面的创建决策树的代码，构造预测隐形眼镜的决策树lensesTree=createTree(lenses,lensesLabels)print(lensesTree)#画图可视化展现createPlot(lensesTree)storeTree(lensesTree, "lensenTree")
ContactLensesTest()