python机器学习理论与实战(二)决策树

决策树也是有监督机器学习方法。 电影《无耻混蛋》里有一幕游戏,在德军小酒馆里有几个人在玩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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

您可能感兴趣的文章:

  • 决策树的python实现方法
  • python实现决策树C4.5算法详解(在ID3基础上改进)
  • 基于ID3决策树算法的实现(Python版)
  • 机器学习python实战之决策树
  • Python机器学习之决策树算法实例详解
  • python决策树之CART分类回归树详解
  • python利用sklearn包编写决策树源代码
  • python编写分类决策树的代码
  • python决策树之C4.5算法详解
  • python机器学习之决策树分类详解
(0)

相关推荐

  • 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利用sklearn包编写决策树源代码

    本文实例为大家分享了python编写决策树源代码,供大家参考,具体内容如下 因为最近实习的需要,所以用python里的sklearn包重新写了一次决策树. 工具:sklearn,将dot文件转化为pdf格式(是为了将形成的决策树可视化)graphviz-2.38,下载解压之后将其中的bin文件的目录添加进环境变量 源代码如下: from sklearn.feature_extraction import DictVectorizer import csv from sklearn import

  • 决策树的python实现方法

    本文实例讲述了决策树的python实现方法.分享给大家供大家参考.具体实现方法如下: 决策树算法优缺点: 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据 缺点:可能会产生过度匹配的问题 适用数据类型:数值型和标称型 算法思想: 1.决策树构造的整体思想: 决策树说白了就好像是if-else结构一样,它的结果就是你要生成这个一个可以从根开始不断判断选择到叶子节点的树,但是呢这里的if-else必然不会是让我们认为去设置的,我们要做的是提供一种方法,计算机可以根

  • python决策树之CART分类回归树详解

    决策树之CART(分类回归树)详解,具体内容如下 1.CART分类回归树简介   CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量.如果待预测分类是离散型数据,则CART生成分类决策树:如果待预测分类是连续型数据,则CART生成回归决策树.数据对象的条件属性为离散型或连续型,并不是区别分类树与回归树的标准,例如表1中,数据对象xi的属性A.B为离散型或连续型,并是不区别分类树与回归树的标准. 表1 2.CART分类回归树分裂属性的选择   2.1 CART分类树--待预测

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

    本文实例讲述了Python机器学习之决策树算法.分享给大家供大家参考,具体如下: 决策树学习是应用最广泛的归纳推理算法之一,是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树.决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,机器学习算法最终将使用这些从数据集中创造的规则.决策树的优点为:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据.缺点为:可能产生过度匹配的问题.决策树适于处理离散型和连续型的数据. 在决策树中最重要的就是如何选取

  • 机器学习python实战之决策树

    决策树原理:从数据集中找出决定性的特征对数据集进行迭代划分,直到某个分支下的数据都属于同一类型,或者已经遍历了所有划分数据集的特征,停止决策树算法. 每次划分数据集的特征都有很多,那么我们怎么来选择到底根据哪一个特征划分数据集呢?这里我们需要引入信息增益和信息熵的概念. 一.信息增益 划分数据集的原则是:将无序的数据变的有序.在划分数据集之前之后信息发生的变化称为信息增益.知道如何计算信息增益,我们就可以计算根据每个特征划分数据集获得的信息增益,选择信息增益最高的特征就是最好的选择.首先我们先来

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

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

  • python编写分类决策树的代码

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

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

随机推荐