Python机器学习之决策树算法实例详解

本文实例讲述了Python机器学习之决策树算法。分享给大家供大家参考,具体如下:

决策树学习是应用最广泛的归纳推理算法之一,是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树。决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,机器学习算法最终将使用这些从数据集中创造的规则。决策树的优点为:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。缺点为:可能产生过度匹配的问题。决策树适于处理离散型和连续型的数据。

在决策树中最重要的就是如何选取用于划分的特征

在算法中一般选用ID3,D3算法的核心问题是选取在树的每个节点要测试的特征或者属性,希望选择的是最有助于分类实例的属性。如何定量地衡量一个属性的价值呢?这里需要引入熵和信息增益的概念。熵是信息论中广泛使用的一个度量标准,刻画了任意样本集的纯度。

假设有10个训练样本,其中6个的分类标签为yes,4个的分类标签为no,那熵是多少呢?在该例子中,分类的数目为2(yes,no),yes的概率为0.6,no的概率为0.4,则熵为 :

其中value(A)是属性A所有可能值的集合,是S中属性A的值为v的子集,即。上述公式的第一项为原集合S的熵,第二项是用A分类S后熵的期望值,该项描述的期望熵就是每个子集的熵的加权和,权值为属于的样本占原始样本S的比例。所以Gain(S, A)是由于知道属性A的值而导致的期望熵减少。

完整的代码:

# -*- coding: cp936 -*-
from numpy import *
import operator
from math import log
import operator
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
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {} # a dictionary for feature
  for featVec in dataSet:
    currentLabel = featVec[-1]
    if currentLabel not in labelCounts.keys():
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  for key in labelCounts:
    #print(key)
    #print(labelCounts[key])
    prob = float(labelCounts[key])/numEntries
    #print(prob)
    shannonEnt -= prob * log(prob,2)
  return shannonEnt
#按照给定的特征划分数据集
#根据axis等于value的特征将数据提出
def splitDataSet(dataSet, axis, value):
  retDataSet = []
  for featVec in dataSet:
    if featVec[axis] == value:
      reducedFeatVec = featVec[:axis]
      reducedFeatVec.extend(featVec[axis+1:])
      retDataSet.append(reducedFeatVec)
  return retDataSet
#选取特征,划分数据集,计算得出最好的划分数据集的特征
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1 #剩下的是特征的个数
  baseEntropy = calcShannonEnt(dataSet)#计算数据集的熵,放到baseEntropy中
  bestInfoGain = 0.0;bestFeature = -1 #初始化熵增益
  for i in range(numFeatures):
    featList = [example[i] for example in dataSet] #featList存储对应特征所有可能得取值
    uniqueVals = set(featList)
    newEntropy = 0.0
    for value in uniqueVals:#下面是计算每种划分方式的信息熵,特征i个,每个特征value个值
      subDataSet = splitDataSet(dataSet, i ,value)
      prob = len(subDataSet)/float(len(dataSet)) #特征样本在总样本中的权重
      newEntropy = prob * calcShannonEnt(subDataSet)
    infoGain = baseEntropy - newEntropy #计算i个特征的信息熵
    #print(i)
    #print(infoGain)
    if(infoGain > bestInfoGain):
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
#如上面是决策树所有的功能模块
#得到原始数据集之后基于最好的属性值进行划分,每一次划分之后传递到树分支的下一个节点
#递归结束的条件是程序遍历完成所有的数据集属性,或者是每一个分支下的所有实例都具有相同的分类
#如果所有实例具有相同的分类,则得到一个叶子节点或者终止快
#如果所有属性都已经被处理,但是类标签依然不是确定的,那么采用多数投票的方式
#返回出现次数最多的分类名称
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]#将最后一行的数据放到classList中,所有的类别的值
  if classList.count(classList[0]) == len(classList): #类别完全相同不需要再划分
    return classList[0]
  if len(dataSet[0]) == 1:#这里为什么是1呢?就是说特征数为1的时候
    return majorityCnt(classList)#就返回这个特征就行了,因为就这一个特征
  bestFeat = chooseBestFeatureToSplit(dataSet)
  print('the bestFeatue in creating is :')
  print(bestFeat)
  bestFeatLabel = labels[bestFeat]#运行结果'no surfacing'
  myTree = {bestFeatLabel:{}}#嵌套字典,目前value是一个空字典
  del(labels[bestFeat])
  featValues = [example[bestFeat] for example in dataSet]#第0个特征对应的取值
  uniqueVals = set(featValues)
  for value in uniqueVals: #根据当前特征值的取值进行下一级的划分
    subLabels = labels[:]
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
  return myTree
#对上面简单的数据进行小测试
def testTree1():
  myDat,labels=createDataSet()
  val = calcShannonEnt(myDat)
  print 'The classify accuracy is: %.2f%%' % val
  retDataSet1 = splitDataSet(myDat,0,1)
  print (myDat)
  print(retDataSet1)
  retDataSet0 = splitDataSet(myDat,0,0)
  print (myDat)
  print(retDataSet0)
  bestfeature = chooseBestFeatureToSplit(myDat)
  print('the bestFeatue is :')
  print(bestfeature)
  tree = createTree(myDat,labels)
  print(tree)

对应的结果是:

>>> import TREE
>>> TREE.testTree1()
The classify accuracy is: 0.97%
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no']]
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
[[1, 'no'], [1, 'no']]
the bestFeatue is :
0
the bestFeatue in creating is :
0
the bestFeatue in creating is :
0
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

最好再增加使用决策树的分类函数

同时因为构建决策树是非常耗时间的,因为最好是将构建好的树通过 python 的 pickle 序列化对象,将对象保存在磁盘上,等到需要用的时候再读出

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)

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

时间: 2017-12-06

python决策树之C4.5算法详解

本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下 1. C4.5算法简介   C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化.C4.5算法对ID3算法主要做了一下几点改进:   (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足:   (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理:   (3)构造决策树之后进行剪枝操作:   (4)能够处理具有缺失属性值的训练数据. 2

python代码实现ID3决策树算法

本文实例为大家分享了python实现ID3决策树算法的具体代码,供大家参考,具体内容如下 ''''' Created on Jan 30, 2015 @author: 史帅 ''' from math import log import operator import re def fileToDataSet(fileName): ''''' 此方法功能是:从文件中读取样本集数据,样本数据的格式为:数据以空白字符分割,最后一列为类标签 参数: fileName:存放样本集数据的文件路径 返回值:

python实现决策树分类算法

本文实例为大家分享了python实现决策树分类算法的具体代码,供大家参考,具体内容如下 1.概述 决策树(decision tree)--是一种被广泛使用的分类算法. 相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置 在实际应用中,对于探测式的知识发现,决策树更加适用. 2.算法思想 通俗来说,决策树分类的思想类似于找对象.现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话: 女儿:多大年纪了? 母亲:26. 女儿:长的帅不帅? 母亲:挺帅的. 女儿:收入高不?

Python机器学习之决策树算法

一.决策树原理 决策树是用样本的属性作为结点,用属性的取值作为分支的树结构. 决策树的根结点是所有样本中信息量最大的属性.树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性.决策树的叶结点是样本的类别值.决策树是一种知识表示形式,它是对所有样本数据的高度概括决策树能准确地识别所有样本的类别,也能有效地识别新样本的类别. 决策树算法ID3的基本思想: 首先找出最有判别力的属性,把样例分成多个子集,每个子集又选择最有判别力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止.最后

解读python如何实现决策树算法

数据描述 每条数据项储存在列表中,最后一列储存结果 多条数据项形成数据集 data=[[d1,d2,d3...dn,result], [d1,d2,d3...dn,result], . . [d1,d2,d3...dn,result]] 决策树数据结构 class DecisionNode: '''决策树节点 ''' def __init__(self,col=-1,value=None,results=None,tb=None,fb=None): '''初始化决策树节点 args: col -

基于ID3决策树算法的实现(Python版)

实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

python实现C4.5决策树算法

C4.5算法使用信息增益率来代替ID3的信息增益进行特征的选择,克服了信息增益选择特征时偏向于特征值个数较多的不足.信息增益率的定义如下: # -*- coding: utf-8 -*- from numpy import * import math import copy import cPickle as pickle class C45DTree(object): def __init__(self): # 构造方法 self.tree = {} # 生成树 self.dataSet =

Python决策树和随机森林算法实例详解

本文实例讲述了Python决策树和随机森林算法.分享给大家供大家参考,具体如下: 决策树和随机森林都是常用的分类算法,它们的判断逻辑和人的思维方式非常类似,人们常常在遇到多个条件组合问题的时候,也通常可以画出一颗决策树来帮助决策判断.本文简要介绍了决策树和随机森林的算法以及实现,并使用随机森林算法和决策树算法来检测FTP暴力破解和POP3暴力破解,详细代码可以参考: https://github.com/traviszeng/MLWithWebSecurity 决策树算法 决策树表现了对象属性和

Python实现决策树C4.5算法的示例

为什么要改进成C4.5算法 原理 C4.5算法是在ID3算法上的一种改进,它与ID3算法最大的区别就是特征选择上有所不同,一个是基于信息增益比,一个是基于信息增益. 之所以这样做是因为信息增益倾向于选择取值比较多的特征(特征越多,条件熵(特征划分后的类别变量的熵)越小,信息增益就越大):因此在信息增益下面加一个分母,该分母是当前所选特征的熵,注意:这里而不是类别变量的熵了. 这样就构成了新的特征选择准则,叫做信息增益比.为什么加了这样一个分母就会消除ID3算法倾向于选择取值较多的特征呢? 因为特

python实现决策树C4.5算法详解(在ID3基础上改进)

一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

python实现决策树ID3算法的示例代码

在周志华的西瓜书和李航的统计机器学习中对决策树ID3算法都有很详细的解释,如何实现呢?核心点有如下几个步骤 step1:计算香农熵 from math import log import operator # 计算香农熵 def calculate_entropy(data): label_counts = {} for feature_data in data: laber = feature_data[-1] # 最后一行是laber if laber not in label_counts

python实现ID3决策树算法

ID3决策树是以信息增益作为决策标准的一种贪心决策树算法 # -*- coding: utf-8 -*- from numpy import * import math import copy import cPickle as pickle class ID3DTree(object): def __init__(self): # 构造方法 self.tree = {} # 生成树 self.dataSet = [] # 数据集 self.labels = [] # 标签集 # 数据导入函数

Python决策树分类算法学习

从这一章开始进入正式的算法学习. 首先我们学习经典而有效的分类算法:决策树分类算法. 1.决策树算法 决策树用树形结构对样本的属性进行分类,是最直观的分类算法,而且也可以用于回归.不过对于一些特殊的逻辑分类会有困难.典型的如异或(XOR)逻辑,决策树并不擅长解决此类问题. 决策树的构建不是唯一的,遗憾的是最优决策树的构建属于NP问题.因此如何构建一棵好的决策树是研究的重点. J. Ross Quinlan在1975提出将信息熵的概念引入决策树的构建,这就是鼎鼎大名的ID3算法.后续的C4.5,

Python KNN分类算法学习

本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距

python sklearn常用分类算法模型的调用

本文实例为大家分享了python sklearn分类算法模型调用的具体代码,供大家参考,具体内容如下 实现对'NB', 'KNN', 'LR', 'RF', 'DT', 'SVM','SVMCV', 'GBDT'模型的简单调用. # coding=gbk import time from sklearn import metrics import pickle as pickle import pandas as pd # Multinomial Naive Bayes Classifier d

python实现决策树分类(2)

在上一篇文章中,我们已经构建了决策树,接下来可以使用它用于实际的数据分类.在执行数据分类时,需要决策时以及标签向量.程序比较测试数据和决策树上的数值,递归执行直到进入叶子节点. 这篇文章主要使用决策树分类器就行分类,数据集采用UCI数据库中的红酒,白酒数据,主要特征包括12个,主要有非挥发性酸,挥发性酸度, 柠檬酸, 残糖含量,氯化物, 游离二氧化硫, 总二氧化硫,密度, pH,硫酸盐,酒精, 质量等特征. 下面是具体代码的实现: #coding :utf-8 ''' 2017.6.26 aut

用Python实现KNN分类算法

本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 KNN分类算法应该算得上是机器学习中最简单的分类算法了,所谓KNN即为K-NearestNeighbor(K个最邻近样本节点).在进行分类之前KNN分类器会读取较多数量带有分类标签的样本数据作为分类的参照数据,当它对类别未知的样本进行分类时,会计算当前样本与所有参照样本的差异大小:该差异大小是通过数据点在样本特征的多维度空间中的距离来进行衡量的,也就是说,如果两个样本点在在其特征数据多维度空间中的距离越近,则这

python机器学习之决策树分类详解

决策树分类与上一篇博客k近邻分类的最大的区别就在于,k近邻是没有训练过程的,而决策树是通过对训练数据进行分析,从而构造决策树,通过决策树来对测试数据进行分类,同样是属于监督学习的范畴.决策树的结果类似如下图: 图中方形方框代表叶节点,带圆边的方框代表决策节点,决策节点与叶节点的不同之处就是决策节点还需要通过判断该节点的状态来进一步分类. 那么如何通过训练数据来得到这样的决策树呢? 这里涉及要信息论中一个很重要的信息度量方式,香农熵.通过香农熵可以计算信息增益. 香农熵的计算公式如下: p(xi)

python实现决策树分类

上一篇博客主要介绍了决策树的原理,这篇主要介绍他的实现,代码环境python 3.4,实现的是ID3算法,首先为了后面matplotlib的绘图方便,我把原来的中文数据集变成了英文. 原始数据集: 变化后的数据集在程序代码中体现,这就不截图了 构建决策树的代码如下: #coding :utf-8 ''' 2017.6.25 author :Erin function: "decesion tree" ID3 ''' import numpy as np import pandas as

python编写分类决策树的代码

决策树通常在机器学习中用于分类. 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关特征数据. 缺点:可能会产生过度匹配问题. 适用数据类型:数值型和标称型. 1.信息增益 划分数据集的目的是:将无序的数据变得更加有序.组织杂乱无章数据的一种方法就是使用信息论度量信息.通常采用信息增益,信息增益是指数据划分前后信息熵的减少值.信息越无序信息熵越大,获得信息增益最高的特征就是最好的选择. 熵定义为信息的期望,符号xi的信息定义为: 其中p(xi)为该分类的概率. 熵,即信息