基于Python实现的ID3决策树功能示例
作者:leeliyang 发布时间:2021-10-24 07:57:24
标签:Python,ID3,决策树
本文实例讲述了基于Python实现的ID3决策树功能。分享给大家供大家参考,具体如下:
ID3算法是决策树的一种,它是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事。ID3算法,即Iterative Dichotomiser 3,迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法。
如下示例是一个判断海洋生物数据是否是鱼类而构建的基于ID3思想的决策树
# 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'],
[0,0,'maybe']]
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()
运行结果如下:
{'no surfaceing': {0: {'flippers': {0: 'maybe', 1: 'no'}}, 1: {'flippers': {0: 'no', 1: 'yes'}}}}
execute for 0.0103958394532
最后我们测试一下这个脚本即可,如果想把这个生成的决策树用图像画出来,也只是在需要在脚本里面定义一个plottree的函数即可。
希望本文所述对大家Python程序设计有所帮助。
来源:http://blog.csdn.net/gentelyang/article/details/75195630


猜你喜欢
- SQL*DBA命令的安全性: 如果您没有SQL*PLUS应用程序,您也可以使用SQL*DBA作SQL查权限相关的命令只能分配给Oracle软
- 下面就来说说解决方案吧~import osimport syscurPath = os.path.abspath(os.path.dirna
- Xml_javascript分页实例:<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.
- 1、什么是双向数据绑定Vue.js是一个MV VM框架, 即数据双向绑定, 即当数据发生变化的时候, 视图也就发生变化, 当视图发生变化的时
- 现有问题当前的项目中包括一个6200万行、500多列的表。其中的数据来自SQL Server以外,它们到达的表中有一个标识主键,所有剩下的列
- 说在前面突发奇想,想了解一下mysql order by排序是以什么规则进行的? 好了,话不多说,直接进入正题吧。MySql order b
- 这篇文章主要介绍了微信小程序 云开发模糊查询实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友
- 一、生成日期数据import pandas as pdpd.date_range( )同生成随机数的思想类似,使用pandas库中的函数pd
- Create a Simple API Using Django REST Framework in PythonWHAT IS AN AP
- 这两天在看webpack,今天卡在webpack-dev-server上了,折腾了一下午,一直无法正常运行,每次服务器也提示正常启动了,但是
- python tkinter按钮Button的使用创建和设置窗口from tkinter import *#创建窗口对象root = Tk(
- 初步介绍 当然,我知道现在有成千上万个关于 用CSS处理圆角 的教程,但不管怎么说,我仍然想把这篇文章展示给您。也希望您会发现这篇文章会非常
- 总结大家都知道,在开发中提供用户登录以及维护用户的登录状态,是一个拥有用户系统的软件应用普遍需要做的事情。像微信这样的一个社交平台,如果做一
- 译注:这是一篇在Stack overflow上很热的帖子。提问者自称已经掌握了有关Python OOP编程中的各种概念,但始终觉得元类(me
- 下面通过三种方法给大家介绍Pycharm2020.1安装中文语言插件的方法,大家可以参考下:方法一(在搜索不到插件):1.安装好Pychar
- 本篇文章主要是由于计划使用django写一个计划任务出来,可以定时的轮换值班人员名称或者定时执行脚本等功能,百度无数坑之后,终于可以凑合把这
- 引言python中的模块、库、包有什么区别?module:一个 .py 文件就是个 modulelib:抽象概念,和另外两个不是一类,只要你
- 当数据库服务器变得十分繁忙导致性能下降时,你会怎么办?购买更多的硬件升级你的服务器,还是重新考虑数据库服务器设计使得数据库平台具备良好的可升
- 如下所示:daffodil = int(input('请输入一个三位数:'))if daffodil == pow(daff
- 首先要做的就是去豆瓣网找对应的接口,这里就不赘述了,谷歌浏览器抓包即可,然后要做的就是分析返回的json数据的结构:https://movi