决策树的python实现方法

 更新时间:2014年11月18日 14:47:13   投稿:shichen2014   我要评论

这篇文章主要介绍了决策树的python实现方法,详细分析了决策树的优缺点及算法思想并以完整实例形式讲述了Python实现决策树的方法,具有一定的借鉴价值,需要的朋友可以参考下

本文实例讲述了决策树的python实现方法。分享给大家供大家参考。具体实现方法如下:

决策树算法优缺点:

优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据

缺点:可能会产生过度匹配的问题

适用数据类型:数值型和标称型

算法思想:

1.决策树构造的整体思想:

决策树说白了就好像是if-else结构一样,它的结果就是你要生成这个一个可以从根开始不断判断选择到叶子节点的树,但是呢这里的if-else必然不会是让我们认为去设置的,我们要做的是提供一种方法,计算机可以根据这种方法得到我们所需要的决策树。这个方法的重点就在于如何从这么多的特征中选择出有价值的,并且按照最好的顺序由根到叶选择。完成了这个我们也就可以递归构造一个决策树了

2.信息增益

划分数据集的最大原则是将无序的数据变得更加有序。既然这又牵涉到信息的有序无序问题,自然要想到想弄的信息熵了。这里我们计算用的也是信息熵(另一种方法是基尼不纯度)。公式如下:

数据需要满足的要求:

① 数据必须是由列表元素组成的列表,而且所有的列白哦元素都要具有相同的数据长度
② 数据的最后一列或者每个实例的最后一个元素应是当前实例的类别标签

函数:

calcShannonEnt(dataSet)
计算数据集的香农熵,分两步,第一步计算频率,第二部根据公式计算香农熵

splitDataSet(dataSet, aixs, value)
划分数据集,将满足X[aixs]==value的值都划分到一起,返回一个划分好的集合(不包括用来划分的aixs属性,因为不需要)

chooseBestFeature(dataSet)
选择最好的属性进行划分,思路很简单就是对每个属性都划分下,看哪个好。这里使用到了一个set来选取列表中唯一的元素,这是一中很快的方法

majorityCnt(classList)
因为我们递归构建决策树是根据属性的消耗进行计算的,所以可能会存在最后属性用完了,但是分类还是没有算完,这时候就会采用多数表决的方式计算节点分类

createTree(dataSet, labels)
基于递归构建决策树。这里的label更多是对于分类特征的名字,为了更好看和后面的理解。

复制代码 代码如下:

#coding=utf-8
import operator
from math import log
import time

def createDataSet():
    dataSet=[[1,1,'yes'],
            [1,1,'yes'],
            [1,0,'no'],
            [0,1,'no'],
            [0,1,'no']]
    labels = ['no surfaceing','flippers']
    return dataSet, labels

#计算香农熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for feaVec in dataSet:
        currentLabel = feaVec[-1]
        if currentLabel not in labelCounts:
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

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)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        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
        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
    return max(classCount)        
   
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:#所有特征已经用完
        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[:]#为了不改变原始列表的内容复制了一下
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,
                                        bestFeat, value),subLabels)
    return myTree
   
def main():
    data,label = createDataSet()
    t1 = time.clock()
    myTree = createTree(data,label)
    t2 = time.clock()
    print myTree
    print 'execute for ',t2-t1
if __name__=='__main__':
    main()

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

相关文章

  • 使用python将请求的requests headers参数格式化方法

    使用python将请求的requests headers参数格式化方法

    今天小编就为大家分享一篇使用python将请求的requests headers参数格式化方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-01-01
  • Python进程间通信Queue实例解析

    Python进程间通信Queue实例解析

    这篇文章主要介绍了Python进程间通信Queue实例解析,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
    2018-01-01
  • Python中绑定与未绑定的类方法用法分析

    Python中绑定与未绑定的类方法用法分析

    这篇文章主要介绍了Python中绑定与未绑定的类方法用法,结合实例形式分析了未绑定的类方法与绑定的实例方法相关使用技巧,需要的朋友可以参考下
    2016-04-04
  • Python设置在shell脚本中自动补全功能的方法

    Python设置在shell脚本中自动补全功能的方法

    今天小编就为大家分享一篇Python设置在shell脚本中自动补全功能的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-06-06
  • python自定义解析简单xml格式文件的方法

    python自定义解析简单xml格式文件的方法

    这篇文章主要介绍了python自定义解析简单xml格式文件的方法,涉及Python解析XML文件的相关技巧,非常具有实用价值,需要的朋友可以参考下
    2015-05-05
  • Django进阶之CSRF的解决

    Django进阶之CSRF的解决

    这篇文章主要介绍了Django进阶之CSRF的解决,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2018-08-08
  • Python之文字转图片方法

    Python之文字转图片方法

    今天小编就为大家分享一篇Python之文字转图片方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-05-05
  • Python中eval带来的潜在风险代码分析

    Python中eval带来的潜在风险代码分析

    这篇文章主要介绍了Python中eval带来的潜在风险代码分析,具有一定借鉴价值,需要的朋友可以参考下。
    2017-12-12
  • python基础梳理(一)(推荐)

    python基础梳理(一)(推荐)

    这篇文章主要介绍了python基础梳理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2019-04-04
  • 使用Python的Twisted框架编写简单的网络客户端

    使用Python的Twisted框架编写简单的网络客户端

    这篇文章主要介绍了使用Python的Twisted框架编写简单的网络客户端,翻译自Twisted文档,包括一个简单的IRC客户端的实现,需要的朋友可以参考下
    2015-04-04

最新评论