python实现ID3决策树算法
作者:杨柳岸晓风 时间:2023-04-13 09:35:28
ID3决策树是以信息增益作为决策标准的一种贪心决策树算法
# -*- coding: utf-8 -*-
from numpy import *
import math
import copy
import cPickle as pickle
class ID3DTree(object):
def __init__(self): # 构造方法
self.tree = {} # 生成树
self.dataSet = [] # 数据集
self.labels = [] # 标签集
# 数据导入函数
def loadDataSet(self, path, labels):
recordList = []
fp = open(path, "rb") # 读取文件内容
content = fp.read()
fp.close()
rowList = content.splitlines() # 按行转换为一维表
recordList = [row.split("\t") for row in rowList if row.strip()] # strip()函数删除空格、Tab等
self.dataSet = recordList
self.labels = labels
# 执行决策树函数
def train(self):
labels = copy.deepcopy(self.labels)
self.tree = self.buildTree(self.dataSet, labels)
# 构件决策树:穿件决策树主程序
def buildTree(self, dataSet, lables):
cateList = [data[-1] for data in dataSet] # 抽取源数据集中的决策标签列
# 程序终止条件1:如果classList只有一种决策标签,停止划分,返回这个决策标签
if cateList.count(cateList[0]) == len(cateList):
return cateList[0]
# 程序终止条件2:如果数据集的第一个决策标签只有一个,返回这个标签
if len(dataSet[0]) == 1:
return self.maxCate(cateList)
# 核心部分
bestFeat = self.getBestFeat(dataSet) # 返回数据集的最优特征轴
bestFeatLabel = lables[bestFeat]
tree = {bestFeatLabel: {}}
del (lables[bestFeat])
# 抽取最优特征轴的列向量
uniqueVals = set([data[bestFeat] for data in dataSet]) # 去重
for value in uniqueVals: # 决策树递归生长
subLables = lables[:] # 将删除后的特征类别集建立子类别集
# 按最优特征列和值分隔数据集
splitDataset = self.splitDataSet(dataSet, bestFeat, value)
subTree = self.buildTree(splitDataset, subLables) # 构建子树
tree[bestFeatLabel][value] = subTree
return tree
# 计算出现次数最多的类别标签
def maxCate(self, cateList):
items = dict([(cateList.count(i), i) for i in cateList])
return items[max(items.keys())]
# 计算最优特征
def getBestFeat(self, dataSet):
# 计算特征向量维,其中最后一列用于类别标签
numFeatures = len(dataSet[0]) - 1 # 特征向量维数=行向量维数-1
baseEntropy = self.computeEntropy(dataSet) # 基础熵
bestInfoGain = 0.0 # 初始化最优的信息增益
bestFeature = -1 # 初始化最优的特征轴
# 外循环:遍历数据集各列,计算最优特征轴
# i为数据集列索引:取值范围0~(numFeatures-1)
for i in xrange(numFeatures):
uniqueVals = set([data[i] for data in dataSet]) # 去重
newEntropy = 0.0
for value in uniqueVals:
subDataSet = self.splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * self.computeEntropy(subDataSet)
infoGain = baseEntropy - newEntropy
if (infoGain > bestInfoGain): # 信息增益大于0
bestInfoGain = infoGain # 用当前信息增益值替代之前的最优增益值
bestFeature = i # 重置最优特征为当前列
return bestFeature
# 计算信息熵
# @staticmethod
def computeEntropy(self, dataSet):
dataLen = float(len(dataSet))
cateList = [data[-1] for data in dataSet] # 从数据集中得到类别标签
# 得到类别为key、 出现次数value的字典
items = dict([(i, cateList.count(i)) for i in cateList])
infoEntropy = 0.0
for key in items: # 香农熵: = -p*log2(p) --infoEntropy = -prob * log(prob, 2)
prob = float(items[key]) / dataLen
infoEntropy -= prob * math.log(prob, 2)
return infoEntropy
# 划分数据集: 分割数据集; 删除特征轴所在的数据列,返回剩余的数据集
# dataSet : 数据集; axis: 特征轴; value: 特征轴的取值
def splitDataSet(self, dataSet, axis, value):
rtnList = []
for featVec in dataSet:
if featVec[axis] == value:
rFeatVec = featVec[:axis] # list操作:提取0~(axis-1)的元素
rFeatVec.extend(featVec[axis + 1:])
rtnList.append(rFeatVec)
return rtnList
# 存取树到文件
def storetree(self, inputTree, filename):
fw = open(filename,'w')
pickle.dump(inputTree, fw)
fw.close()
# 从文件抓取树
def grabTree(self, filename):
fr = open(filename)
return pickle.load(fr)
调用代码
# -*- coding: utf-8 -*-
from numpy import *
from ID3DTree import *
dtree = ID3DTree()
# ["age", "revenue", "student", "credit"]对应年龄、收入、学生、信誉4个特征
dtree.loadDataSet("dataset.dat", ["age", "revenue", "student", "credit"])
dtree.train()
dtree.storetree(dtree.tree, "data.tree")
mytree = dtree.grabTree("data.tree")
print mytree
来源:https://blog.csdn.net/yjIvan/article/details/71194383
标签:python,ID3,决策树
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
使用python创建生成动态链接库dll的方法
2021-02-13 22:18:21
js实现axios限制请求队列
2024-05-10 13:59:31
python魔法方法-自定义序列详解
2022-10-08 08:56:12
![](https://img.aspxhome.com/file/2023/8/75348_0s.png)
基于Go语言实现插入排序算法及优化
2024-05-22 10:18:05
![](https://img.aspxhome.com/file/2023/8/123898_0s.png)
js+html5操作sqlite数据库的方法
2024-01-23 18:31:05
mybatis连接MySQL8出现的问题解决方法
2024-01-22 08:27:59
Python opencv应用实现图片切分操作示例
2021-12-25 03:45:39
![](https://img.aspxhome.com/file/2023/6/72876_0s.png)
python 使用elasticsearch 实现翻页的三种方式
2021-03-09 17:39:57
![](https://img.aspxhome.com/file/2023/1/95271_0s.jpg)
python中时间模块的基本使用教程
2021-05-15 21:24:43
如何利用pyinstaller打包Python程序为exe可执行文件
2023-11-08 08:01:39
![](https://img.aspxhome.com/file/2023/2/64652_0s.png)
pandas to_excel 添加颜色操作
2021-07-19 19:49:57
Python之列表推导式最全汇总(中篇)
2022-05-25 20:56:59
![](https://img.aspxhome.com/file/2023/2/99272_0s.jpg)
如何建设一个多语言版的ASP网站?
2009-11-26 20:36:00
一文吃透Go的内置RPC原理
2024-02-03 08:45:53
![](https://img.aspxhome.com/file/2023/6/103736_0s.png)
Python+logging输出到屏幕将log日志写入文件
2023-07-19 05:29:21
![](https://img.aspxhome.com/file/2023/5/59295_0s.png)
mac PyCharm添加Python解释器及添加package路径的方法
2023-06-04 23:58:22
![](https://img.aspxhome.com/file/2023/7/90427_0s.jpg)
asp实现本周的一周时间列表的代码
2011-04-06 10:45:00
python (logging) 日志按日期、大小回滚的操作
2023-10-03 02:42:21
MySQL查询优化之查询慢原因和解决技巧
2024-01-23 13:36:09
Ubuntu 18.04下mysql 8.0 安装配置方法图文教程
2024-01-25 18:05:41
![](https://img.aspxhome.com/file/2023/5/118475_0s.png)