【学习】决策树的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()

PPV课其他精彩文章：

1、回复“干货”查看干货 数据分析师完整知识结构

2、回复“答案”查看大数据Hadoop面试笔试题及答案

3、回复“设计”查看这是我见过最逆天的设计，令人惊叹叫绝

4、回复“可视化”查看数据可视化专题-数据可视化案例与工具

5、回复“禅师”查看当禅师遇到一位理科生，后来禅师疯了！！知识无极限

6、回复“啤酒”查看数据挖掘关联注明案例-啤酒喝尿布

7、回复“栋察”查看大数据栋察——大数据时代的历史机遇连载

8、回复“数据咖”查看数据咖——PPV课数据爱好者俱乐部省分会会长招募

9、回复“每日一课”查看【每日一课】手机在线视频集锦

PPV课大数据ID: ppvke123 （长按可复制）

大数据人才的摇篮！专注大数据行业人才的培养。每日一课，大数据（EXCEL、SAS、SPSS、Hadoop、CDA）视频课程。大数据资讯，每日分享！数据咖—PPV课数据爱好者俱乐部！