admin 管理员组文章数量: 887021
决策树
文章目录
- 一、什么事信息增益?
- 二、决策树的构造
- 引入
- 1.信息增益
- 2.划分数据集
- 3.递归构建决策树
- 三、在python中使用Matplotlib注解绘制树形图
- 引入
- 1.Matplotlib注解
- 2.构造注解树
- 四.测试与储存分类器
- 1.使用决策树执行分类
- 2.决策树的存储
一、什么事信息增益?
划分数据集的之前之后信息发生的变化称为信息增益,知道如何计算信息增益,就可以计算每个特征值划分数据集获得的信息增益,获取信息增益最高的特征就是最好的选择。
通俗来说就是信息选择的特征。
信息熵:表示随机变量的不确定性。
条件熵:在一个条件下,随机变量的不确定性。
信息增益:熵 - 条件熵。表示在一个条件下,信息不确定性减少的程度。
举例:
X(明天下雨)是一个随机变量,X的熵1
Y(明天阴天)也是随机变量,在阴天情况下下雨的信息熵假设为0.3(此处需要知道其联合概率分布或是通过数据估计)即是条件熵。
信息增益=X的熵-Y条件下X的熵=0.7。
在获得阴天这个信息后,下雨信息不确定性减少了0.7,不确定减少了很多,所以信息增益大。也就是说,阴天(即特征)这个信息对明天下午这一推断来说非常重要。
熵定义为信息的期望值,即计算所有类别所有可能包含的信息期望值,通过以下公式得到。其中n是分类的数目。p(i)为该分类的概率
这次实验采取的样本(共100条,这只是一部分)
二、决策树的构造
代码都写入trees.py
引入
# 决策树
# 数据可视化
import matplotlib.lines as mlines
import matplotlib.pyplot as plt
import matplotlib as mpl
from numpy import *
import operator
from math import log
# 代码功能:计算香农熵
#我们要用到对数函数,所以我们需要引入math模块中定义好的log函数(对数函数)
import trees
import treePlotter
1.信息增益
计算给定数据集的香农熵
def calcShannonEnt(dataSet):#传入数据集
# 在这里dataSet是一个链表形式的的数据集countDataSet = len(dataSet) #我们计算出这个数据集中的数据个数labelCounts={} #构建字典,用键值对的关系我们表示出 我们数据集中的类别还有对应的关系for featVec in dataSet: #通过for循环,我们每次取出一个数据集,如featVec=[1,1,'yes']currentLabel=featVec[-1] #取出最后一列 也就是类别的那一类,比如说‘yes’或者是‘no’if currentLabel not in labelCounts.keys(): #若不在字典中labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1shannonEnt = 0.0 #计算香农熵, 根据公式for key in labelCounts:prob = float(labelCounts[key])/countDataSet #类别标签的频率=概率shannonEnt -= prob * log(prob,2) #公式得熵return shannonEntdef createDataSet(): #恐怖片数据dataSet=[[1,1,'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 1, 'no'],[0, 1, 'no'],[1, 1, 'yes'], [1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 1, 'no'],[0, 1, 'no'],[1, 1, 'yes'], [1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 1, 'no'],[0, 1, 'no'],[1, 1, 'yes'], [1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes']]labels = ['movie','bloody']return dataSet,labelsif __name__ == '__main__':myDat, labels = trees.createDataSet()print(myDat)print(calcShannonEnt(myDat))# 熵越大,混合数据越多myDat[0][-1] = 'maybe'print(myDat)print(calcShannonEnt(myDat))
结果
2.划分数据集
(1)按照给定特征划分数据集
def splitDataSet(dataSet, axis, value): #axis是dataSet数据集下要进行特征划分的列号例如outlook是0列,value是该列下某个特征值,0列中的sunnyretDataSet = [] #创建新的list对象for featVec in dataSet: #遍历数据集,并抽取按axis的当前value特征进划分的数据集(不包括axis列的值)if featVec[axis] == value:reducedFeatVec = featVec[:axis]reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)return retDataSetif __name__ == '__main__':myDat, labels = trees.createDataSet()# 给定特征划分数据集print(splitDataSet(myDat, 0, 0))print(splitDataSet(myDat, 0, 1))
结果
(2)①选择最好的数据集划分(信息增益)
def chooseBestFeatureToSplit(dataSet):numFeatures = len(dataSet[0]) - 1 #获取当前数据集的特征个数,最后一列是分类标签baseEntropy = calcShannonEnt(dataSet) #计算当前数据集的信息熵bestInfoGain = 0.0; bestFeature = -1 #初始化最优信息增益和最优的特征for i in range(numFeatures): #遍历每个特征iterate over all the featuresfeatList = [example[i] for example in dataSet]#获取数据集中当前特征下的所有值uniqueVals = set(featList) #获取当前特征值newEntropy = 0.0for 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 = ireturn bestFeature #返回特征下标if __name__ == '__main__':# 选择最好数据集特征划分myDat, labels = trees.createDataSet()print(chooseBestFeatureToSplit(myDat))
结果
②选择最好的数据集划分(基尼指数)
#基尼指数
def chooseBestFeatureToSplit(dataSet):numFeatures = len(dataSet[0]) - 1 #获取当前数据集的特征个数,最后一列是分类标签bestGini = 999999.0bestFeature = -1for i in range(numFeatures):featList = [example[i] for example in dataSet]uniqueVals = set(featList)gini = 0.0for value in uniqueVals:subDataSet = splitDataSet(dataSet, i, value)prob = len(subDataSet) / float(len(dataSet))subProb = len(splitDataSet(subDataSet, -1, 'N')) / float(len(subDataSet))gini += prob * (1.0 - pow(subProb, 2) - pow(1 - subProb, 2))if (gini < bestGini):bestGini = ginibestFeature = ireturn bestFeature #返回特征下标if __name__ == '__main__':# 选择最好数据集特征划分myDat,labels=trees.createDataSet()print(chooseBestFeatureToSplit(myDat))
结果
说明含否决定的因素最大,即不是电影就决对不是恐怖电影,没有血腥场景也决对不是恐怖电影。
3.递归构建决策树
def majorityCnt(classList):classCount={}for vote in classList:if vote not in classCount.keys(): classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), 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] #当类别完全相同时则停止继续划分,直接返回该类的标签if len(dataSet[0]) == 1: #遍历完所有的特征时,仍然不能将数据集划分成仅包含唯一类别的分组 dataSetreturn majorityCnt(classList) #由于无法简单的返回唯一的类标签,这里就返回出现次数最多的类别作为返回值bestFeat = chooseBestFeatureToSplit(dataSet) #获取最好的分类特征索引bestFeatLabel = labels[bestFeat] #获取该特征的名字# 这里直接使用字典变量来存储树信息,这对于绘制树形图很重要。myTree = {bestFeatLabel:{}} #当前数据集选取最好的特征存储在bestFeat中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 myTreeif __name__ == '__main__':# 创建树myDat, labels = trees.createDataSet()myTree = createTree(myDat, labels)print(myTree)
结果
三、在python中使用Matplotlib注解绘制树形图
函数写入treePlotter.py。主函数写在trees.py
引入
import matplotlib.pyplot as plt
import pickle
1.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 createPlot():fig=plt.figure(1,facecolor='white') #创建一个新图形,白色fig.clf() #清空绘图区createPlot.ax1=plt.subplot(111,frameon=False) #一行一列共一个图此时在绘制第一个图,不绘制边缘plotNode('a decision node',(0.5,0.1),(0.1,0.5),decisionNode)plotNode('a leaf node',(0.8,0.1),(0.3,0.8),leafNode)plt.show()
2.构造注解树
(1)获取叶节点的数目和树的层数
#获取叶子节点个数
def getNumLeafs(myTree): #获取叶节点数目numLeafs = 0 #叶节点数初始化为0# firstStr = myTree.keys()[0] #python3.6以上版本这么改firstSides = list(myTree.keys())firstStr = firstSides[0]secondDict = myTree[firstStr] #第一个key对应的value为其子树for key in secondDict.keys(): #对子树的每个孩子节点if type(secondDict[key]).__name__=='dict': #测试节点是否为字典,如果不是,则为叶节点numLeafs += getNumLeafs(secondDict[key]) #对该子节点递归调用此函数else: #否则说明是叶节点numLeafs +=1return numLeafs#获取树的深度
def getTreeDepth(myTree): #获取树高maxDepth = 0 #最大树高初始化为0# firstStr = myTree.keys()[0] #第一个节点为树的第一个键值 #需要转化为列表才能按下标访问firstSides = list(myTree.keys())firstStr = firstSides[0]secondDict = myTree[firstStr] #第一个key对应的value为其子树for key in secondDict.keys(): #对子树的每个孩子节点if type(secondDict[key]).__name__ =='dict': #如果当前子节点仍有子树thisDepth = 1+ getTreeDepth(secondDict[key])else: #否则说明是叶节点thisDepth = 1 #当前树高为1if thisDepth > maxDepth : maxDepth = thisDepth #如果当前树高大于最大树高则更新最大树高return maxDepthdef retrieveTree(i):listodfTrees=[{'no movie':{0:'no',1:{'bloody':{0:'no',1:'yes'}}}},{'no movie':{0:'no',1:{'bloody':{0:{'head':{0:'no',1:'yes'}},1:'no'}}}}]return listodfTrees[i]
main函数在trees.py执行
if __name__ == '__main__':treePlotter.retrieveTree(1)myTree = treePlotter.retrieveTree(0)print(treePlotter.getNumLeafs(myTree))print(treePlotter.getTreeDepth(myTree))
结果
(2)plotTree函数
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]plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD#减少y偏移for key in secondDict.keys(): #对当前树的每个子树if type(secondDict[key])==dict: #如果其仍有子树plotTree(secondDict[key], cntrPt, str(key)) #递归调用此函数else: #否则为叶节点,直接输出plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalWplotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalDdef 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.0plotTree(inTree, (0.5,1.0), '')plt.show()
main函数在trees.py执行
if __name__ == '__main__':# 打印树myTree = treePlotter.retrieveTree(0)print(treePlotter.createPlot(myTree))
结果
main函数在trees.py执行
if __name__ == '__main__':#打印树myTree = treePlotter.retrieveTree(0)myTree['no movie'][3]='maybe'myTree{'no movie':{0:'no',1:{'bloody':{0:'no',1:'yes'}},3:'maybe'}}print(treePlotter.createPlot(myTree))
结果
四.测试与储存分类器
1.使用决策树执行分类
使用决策树的分类函数
def classify(inputTree, featLabels, testVec): #递归函数,从决策树根节点起不断向下在输入向量中找到对应特征,直到得出结果firstStr = list(inputTree.keys())[0] #当前树的根节点标签字符secondDict = inputTree[firstStr] #根节点的子树#将标签字符串转换为索引featIndex = featLabels.index(firstStr) #当前判断的特征在特征向量中的下标for key in secondDict.keys(): #对此特征下对应的各个分类方向if testVec[featIndex]==key: #找到测试向量对应的那个方向if type(secondDict[key])==dict: #如果下面还有分类classLabel = classify(secondDict[key], featLabels, testVec) #对其之后对应的分类继续递归调用此函数else:classLabel = secondDict[key] #若已到叶节点则判断结束,classLabel返回给上层调用return classLabel
main函数在trees.py执行
if __name__ == '__main__':#测试# 测试myDat,labels=trees.createDataSet()myTree = createTree(myDat, labels)# treePlotter.createPlot(myTree)myDat, labels = trees.createDataSet()print("[1,0]", treePlotter.classify(myTree, labels, [1, 0]))print("[1,1]", treePlotter.classify(myTree, labels, [1, 1]))print("[0,1]", treePlotter.classify(myTree, labels, [0, 1]))print("[0,0]", treePlotter.classify(myTree, labels, [0, 0]))
结果
2.决策树的存储
使用pickle模块存储决策树
# 决策树的存储
def storeTree(inputTree, filename):# 这里二进制写入# fw=open(filename,'w')fw = open(filename, 'wb')# dump函数将决策树写入文件中pickle.dump(inputTree, fw)# 写完成后关闭文件fw.close()# 取决策树
def grabTree(filename):import pickle# 采用二进制读取# fr=open(filename)fr = open(filename, 'rb')return pickle.load(fr)
main函数在trees.py执行
if __name__ == '__main__':
myDat, labels = trees.createDataSet()myTree = createTree(myDat, labels)treePlotter.storeTree(myTree, 'movie.txt')treePlotter.grabTree('movie.txt'){'no movie': {0: 'no', 1: {'bloody': {0: 'no', 1: 'yes'}}}}
结果(自己会在目录下生成一个.txt文件,至于为什么是乱码,我也没整明白,试了百度的方法也没用,要是有小可爱知道滴我一声哈)
本文标签: 决策树
版权声明:本文标题:决策树 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1693777591h242302.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论