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


猜你喜欢
- 今天用到BeautifulSoup解析爬下来的网页数据首先导入包from bs4 import BeautifulSoup然后可以利用url
- 目的两年前曾为了租房做过一个找房机器人 「爬取豆瓣租房并定时推送到微信」,维护一段时间后就荒废了。当时因为代码比较简单一直没开源,现在想想说
- 一般情况下,网站的图片代码是这样的。<img src="./images/test.jpg"
- Jinja2需要Python2.4以上的版本。 安装 按照Jinja有多种方式,你可以根据需要选择不同的按照方式。 使用easy_insta
- Mac安装软件时提示已损坏的解决方法从网上下载的SecureCRT、Principle等设计软件,以及输入法等常用软件,安装时可能会提示&a
- 在for i in iterator结构中,循环器每次返回的对象将赋予给i,直到循环结束。使用iter()内置函数,我们可以将诸如表、字典等
- 这是我在网上看到的一篇不错的mysql数据库优化文章,内容说的很全! 1、使用索引来更快地遍历表 缺省情况下建立的索引是非群集索引,但有时它
- 如下所示:result = os.popen('ps aux') res = result.read()
- 本文实例为大家分享了python3判断url链接是否为404的具体代码,供大家参考,具体内容如下import pymysqlimport t
- 运行环境由于这是一个Python语言的软件包,因此需要你的机器上首先安装好Python语言的环境。关于这一点,请自行在网络上搜索获取方法。关
- 科讯5.0 标签和之前版本变化不大,如果用老版本的科讯,可以参考这个标签使用。相关文章:新云4.0 模板通用标签说明 标签清单:======
- Request Payload 和 Form Data 请求头上的参数差别在于:Content-TypeForm DataPost表单请求代
- 解决了ACCESS数据库路径的问题!采用DBType=0或DBType=1来区分AC库还是MSSQL库具体采用AC库时应注意的事项,请看程序
- JSP 注释的详解及简单实例一 三种格式二 举例 <body> <h1>大家好</h1
- 当发现目录时出错如下:\windows\tensorflow\core\framework\op_kernel.cc:993] Not fo
- time库是python中处理时间的标准库。计算机时间的表达:time()、ctime()、gmtime();提供获取系统时间并格式化输出功
- ORM 查询管理器对于 ORM 定义: 对象关系映射, Object Relational Mapping, ORM, 是一种程序设计技术,
- function getTableDataByXML(inTable, inWindow) { var
- 如下所示:<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional
- 在 pandas 中提供了利用映射关系来实现某些操作的函数,具体如下:replace() 函数:替换元素;map() 函数:新建一列;ren