python机器学习理论与实战(二)决策树
作者:marvin521 发布时间:2021-09-24 06:20:33
决策树也是有监督机器学习方法。 电影《无耻混蛋》里有一幕游戏,在德军小酒馆里有几个人在玩20问题游戏,游戏规则是一个设迷者在纸牌中抽出一个目标(可以是人,也可以是物),而猜谜者可以提问题,设迷者只能回答是或者不是,在几个问题(最多二十个问题)之后,猜谜者通过逐步缩小范围就准确的找到了答案。这就类似于决策树的工作原理。(图一)是一个判断邮件类别的工作方式,可以看出判别方法很简单,基本都是阈值判断,关键是如何构建决策树,也就是如何训练一个决策树。
(图一)
构建决策树的伪代码如下:
Check if every item in the dataset is in the same class:
If so return the class label
Else
find the best feature to split the data
split the dataset
create a branch node
for each split
call create Branch and add the result to the branch node
return branch node
原则只有一个,尽量使得每个节点的样本标签尽可能少,注意上面伪代码中一句说:find the best feature to split the data,那么如何find thebest feature?一般有个准则就是尽量使得分支之后节点的类别纯一些,也就是分的准确一些。如(图二)中所示,从海洋中捞取的5个动物,我们要判断他们是否是鱼,先用哪个特征?
(图二)
为了提高识别精度,我们是先用“离开陆地能否存活”还是“是否有蹼”来判断?我们必须要有一个衡量准则,常用的有信息论、基尼纯度等,这里使用前者。我们的目标就是选择使得分割后数据集的标签信息增益最大的那个特征,信息增益就是原始数据集标签基熵减去分割后的数据集标签熵,换句话说,信息增益大就是熵变小,使得数据集更有序。熵的计算如(公式一)所示:
有了指导原则,那就进入代码实战阶段,先来看看熵的计算代码:
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #the the number of unique elements and their occurance
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) #log base 2 计算熵
return shannonEnt
有了熵的计算代码,接下来看依照信息增益变大的原则选择特征的代码:
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
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
从最后一个if可以看出,选择使得信息增益最大的特征作为分割特征,现在有了特征分割准则,继续进入一下个环节,如何构建决策树,其实就是依照最上面的伪代码写下去,采用递归的思想依次分割下去,直到执行完成就构建了决策树。代码如下:
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]
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:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
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
用图二的样本构建的决策树如(图三)所示:
(图三)
有了决策树,就可以用它做分类咯,分类代码如下:
def classify(inputTree,featLabels,testVec):
firstStr = inputTree.keys()[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
最后给出序列化决策树(把决策树模型保存在硬盘上)的代码:
def storeTree(inputTree,filename):
import pickle
fw = open(filename,'w')
pickle.dump(inputTree,fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename)
return pickle.load(fr)
优点:检测速度快
缺点:容易过拟合,可以采用修剪的方式来尽量避免
参考文献:machine learning in action
来源:http://blog.csdn.net/marvin521/article/details/9255977
猜你喜欢
- 我们主要讲解一下利用Python实现感知机算法。算法一首选,我们利用Python,按照上一节介绍的感知机算法基本思想,实现感知算法的原始形式
- 组建一个关于书籍、作者、出版社的例子:from django.db import modelsclass Publisher(models.
- 背景在小站点上,直接用git来部署php代码相当方便,你的远程站点以及本地版本库都有一个版本控制,追踪问题或者回滚是很轻松的事情。因为在小公
- 目录项目地址:1) 启动方法2) web查看方法3) 功能说明:4) 展示:代码项目地址:https://github.com/guodon
- python将字典内容写入json文件的方法:我们可以先使用json.dumps()函数将字典转换为字符串;然后再将内容写入json即可。j
- 代码如下:declare @Q_ID uniqueidentifier set @Q_ID = dbo.uf_GetParamValueBy
- Go语言的二进制(gob)格式是一个自描述的二进制序列。从其内部表示来看,Go语言的二进制格式由一个 0 块或者更多块的序列组成,其中的每一
- 有些朋友看到这个标题可能会有疑问,难道在视图中使用*符号还有何要注意的地方吗?对于这个问题,我们先不必回答,先看一下例子吧。 我这里,使用的
- 本文实例讲述了Python爬虫实现“盗取”微信好友信息的方法。分享给大家供大家参考,具体如下:刚起床,闲来无聊,找点事做,看了朋友圈一篇爬取
- 本篇文章适合css新手学习,对于已经掌握了css的朋友们也可以通过本片文章来复习知识。作者通过实践,认为在有些情况下css的代码是可以更加简
- 我们今天就来看一下PHP 7正式版的算法和 wordpress 应用在其上的性能表现。PHP7 的安装,真是非常地向下兼容,下载,解压,把之
- Python 提供了两个级别访问的网络服务。低级别的网络服务支持基本的 Socket,它提供了标准的 BSD Sockets API,可以访
- 技巧之一:提高使用Request集合的效率 访问一个ASP集合来提取一个值是费时的、占用计算资源的过程。因为这个操作包含了一系列对相关集合的
- 情况一:坐标上的内容是文字时如上图这样一个横向的柱状图,y坐标轴的内容太长后会导致显示不全。因为数据是由后端传过来的,有些会很长有些会比较短
- 简介集合对象 set 是由具有唯一性的可哈希对象组成的无序多项集,如 list 不能哈希因此,不能作为 set 的一项。set 的常见用途包
- python爬虫中使用urli库可以使用opener"发送多个请求,这些请求是能共享处理cookie的,小编之前也提过python
- 本文实例为大家分享了python3.6.1安装教程,供大家参考,具体内容如下1、安装编译环境所需包#yum install zlib-dev
- 1. 带默认值的参数在了解带星号(*)的参数之前,先看下带有默认值的参数,函数定义如下:>> def defaultValueA
- 问题怎样实现一个按优先级排序的队列? 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素解决方案下面的类利用 heapq 模块
- “In the latest release 10.2 Oracle changed these default values. The m