基于Python实现的ID3决策树功能示例
作者:leeliyang 时间:2021-10-24 07:57:24
本文实例讲述了基于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
标签:Python,ID3,决策树
0
投稿
猜你喜欢
mysql+mybatis下全文搜索的使用方法
2024-01-21 22:07:09
Python可变参数会自动填充前面的默认同名参数实例
2022-05-24 05:00:43
python 将对象设置为可迭代的两种实现方法
2023-08-24 18:01:39
重新认识CSS的权重
2011-05-24 17:06:00
go mod 使用私有gitlab群组的解决方案
2024-05-22 10:29:28
python实现控制电脑鼠标和键盘,登录QQ的方法示例
2023-11-19 12:10:26
opencv读取视频并保存图像的方法
2023-02-21 17:30:16
ES5学习教程之Array对象
2024-04-17 10:09:17
手机验证设计感悟
2011-01-20 19:55:00
Python的互斥锁与信号量详解
2021-12-24 15:29:34
php计算两个整数的最大公约数常用算法小结
2023-11-20 00:29:01
SpringBoot项目application.yml文件数据库配置密码加密的方法
2024-01-18 02:12:40
Oracle 数据库 临时数据的处理方法
2009-07-02 11:48:00
五种方法解决 Web2.0设计中的匹配度
2007-09-22 10:58:00
yahoo 页面的标签效果
2024-04-10 10:38:14
Django + Uwsgi + Nginx 实现生产环境部署的方法
2023-01-01 06:02:49
JavaScript性能优化小技巧,创建文档碎片
2010-03-31 18:27:00
微信小程序分包操作实战指南
2024-04-16 08:47:57
python处理大日志文件
2021-11-09 22:21:14
VSCODE配置Markdown及Markdown基础语法详解
2021-10-02 10:21:20