python实现C4.5决策树算法
作者:杨柳岸晓风 发布时间:2021-10-05 19:35:29
标签:python,C4.5,决策树
C4.5算法使用信息增益率来代替ID3的信息增益进行特征的选择,克服了信息增益选择特征时偏向于特征值个数较多的不足。信息增益率的定义如下:
# -*- coding: utf-8 -*-
from numpy import *
import math
import copy
import cPickle as pickle
class C45DTree(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, featValueList= self.getBestFeat(dataSet) # 返回数据集的最优特征轴
bestFeatLabel = lables[bestFeat]
tree = {bestFeatLabel: {}}
del (lables[bestFeat])
for value in featValueList: # 决策树递归生长
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):
Num_Feats = len(dataSet[0][:-1])
totality = len(dataSet)
BaseEntropy = self.computeEntropy(dataSet)
ConditionEntropy = [] # 初始化条件熵
slpitInfo = [] # for C4.5,caculate gain ratio
allFeatVList = []
for f in xrange(Num_Feats):
featList = [example[f] for example in dataSet]
[splitI, featureValueList] = self.computeSplitInfo(featList)
allFeatVList.append(featureValueList)
slpitInfo.append(splitI)
resultGain = 0.0
for value in featureValueList:
subSet = self.splitDataSet(dataSet, f, value)
appearNum = float(len(subSet))
subEntropy = self.computeEntropy(subSet)
resultGain += (appearNum/totality)*subEntropy
ConditionEntropy.append(resultGain) # 总条件熵
infoGainArray = BaseEntropy*ones(Num_Feats)-array(ConditionEntropy)
infoGainRatio = infoGainArray/array(slpitInfo) # C4.5信息增益的计算
bestFeatureIndex = argsort(-infoGainRatio)[0]
return bestFeatureIndex, allFeatVList[bestFeatureIndex]
# 计算划分信息
def computeSplitInfo(self, featureVList):
numEntries = len(featureVList)
featureVauleSetList = list(set(featureVList))
valueCounts = [featureVList.count(featVec) for featVec in featureVauleSetList]
pList = [float(item)/numEntries for item in valueCounts]
lList = [item*math.log(item, 2) for item in pList]
splitInfo = -sum(lList)
return splitInfo, featureVauleSetList
# 计算信息熵
# @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 C45DTree import *
dtree = C45DTree()
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/71272968
0
投稿
猜你喜欢
- 本文实例讲述了PHP实现根据数组某个键值大小进行排序的方法。分享给大家供大家参考,具体如下:问题:针对给定数组的某个键的键值进行排序解决方法
- Python实现12306火车票抢票系统效果图如下所示:具体代码如下所示:import urllib.request as request
- Cookie简介首先,我们对Cookie做一个简单的介绍,说明如何利用ASP来维护cookie。Cookie是存储在客户端计算机中的一个小文
- 在学习与运用ASP中,response对象涉及到的方面也比较多,想全部都掌握也并非一两天的事,我也是最近才发现response对象中居然有这
- 如何显示随机信息?使用了asp的randomize来创造随机数,select case来显示自定义信息。具体代码如下:<html>
- 这里先解释一下几个概念 - 位置参数:按位置设置的参数,隐式用元组保存对应形参.平时我们用的大多数是按位置传参.比如有函数def func(
- 前言本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理。闲来无事听听歌,听
- 本文实例讲述了Python矩阵常见运算操作。分享给大家供大家参考,具体如下:python的numpy库提供矩阵运算的功能,因此我们在需要矩阵
- 从PJBlog 2.7开始,验证码的功能就很好很强大了,但是同时也给手工输入带来了不小的麻烦——经常输错。之前我写了一个《自己写的一个PJB
- 位置参数这是一个求等差数列和的函数,使用必需要传入一个参数n,这就是位置参数def sum(n): sum=0 &
- 爬取过程:你好,李焕英 短评的URL:https://movie.douban.com/subject/34841067/comments?
- 虽然说表单验证在客户端使用javascript来验证已经可以了,但是我们为了防止访客绕过客户端验证也为了数据安全最好还是在服务器端加上必要的
- python实现银行管理系统,供大家参考,具体内容如下有的地方用的方法的比较复杂,主要是为回顾更多的知识test1用来存类和函数#test1
- PDO::quotePDO::quote — 为SQL语句中的字符串添加引号。(PHP 5 >= 5.1.0, PECL pdo &g
- 在日常的工作中,保护数据免受未授权用户的侵犯是系统管理员特别关心的问题。如果你目前用的是MySQL,就可以使用一些方便的功能来保护系统,来大
- Python 面向对象编程的三大特性之继承一、继承继承也是面向对象编程三大特性之一继承是类与类的一种关系定义一个新的 class
- 本文实例讲述了Python3.5内置模块之shelve模块、xml模块、configparser模块、hashlib、hmac模块用法。分享
- 什么是协程协程是python种一种实现多任务的方式,他是一种比线程更加小的单元,占用更小的执行单元(资源),为啥说他是一个执行单元,因为他自
- 昨天在做一道CTF题的时候碰到了一个图片异或的问题,操作大概如下:将一个图片读入,然后每字节进行异或操作,核心代码可简化为以下:#codin
- 参考:1.Basemap绘制中国地图2.Basemap生成的图中绘制轨迹使用CMA热带气旋最佳路径数据集,对我国周边的台风进行绘制impor