python实现决策树C4.5算法详解(在ID3基础上改进)
作者:jingxian 发布时间:2022-05-06 08:01:57
标签:c4.5,决策树算法,python
一、概论
C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点。而C4.5引入了新概念“信息增益率”,C4.5是选择信息增益率最大的属性作为树节点。
二、信息增益
以上公式是求信息增益率(ID3的知识点)
三、信息增益率
信息增益率是在求出信息增益值在除以。
例如下面公式为求属性为“outlook”的值:
四、C4.5的完整代码
from numpy import *
from scipy import *
from math import log
import operator
#计算给定数据的香浓熵:
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {} #类别字典(类别的名称为键,该类别的个数为值)
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys(): #还没添加到字典里的类型
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: #按dataSet矩阵中的第axis列的值等于value的分数据集
if featVec[axis] == value: #值等于value的,每一行为新的列表(去除第axis个数据)
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) #第i列属性的取值(不同值)数集合
newEntropy = 0.0
splitInfo = 0.0;
for value in uniqueVals: #求第i列属性每个不同值的熵*他们的概率
subDataSet = splitDataSet(dataSet, i , value)
prob = len(subDataSet)/float(len(dataSet)) #求出该值在i列属性中的概率
newEntropy += prob * calcShannonEnt(subDataSet) #求i列属性各值对于的熵求和
splitInfo -= prob * log(prob, 2);
infoGain = (baseEntropy - newEntropy) / splitInfo; #求出第i列属性的信息增益率
print infoGain;
if(infoGain > bestInfoGain): #保存信息增益率最大的信息增益率值以及所在的下表(列值i)
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
sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
#创建树
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]; #创建需要创建树的训练数据的结果列表(例如最外层的列表是[N, N, Y, Y, Y, N, Y])
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:{}} #以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 classify(inputTree, featLabels, testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key], featLabels, testVec)
else: classLabel = secondDict[key]
return classLabel
#读取数据文档中的训练数据(生成二维列表)
def createTrainData():
lines_set = open('../data/ID3/Dataset.txt').readlines()
labelLine = lines_set[2];
labels = labelLine.strip().split()
lines_set = lines_set[4:11]
dataSet = [];
for line in lines_set:
data = line.split();
dataSet.append(data);
return dataSet, labels
#读取数据文档中的测试数据(生成二维列表)
def createTestData():
lines_set = open('../data/ID3/Dataset.txt').readlines()
lines_set = lines_set[15:22]
dataSet = [];
for line in lines_set:
data = line.strip().split();
dataSet.append(data);
return dataSet
myDat, labels = createTrainData()
myTree = createTree(myDat,labels)
print myTree
bootList = ['outlook','temperature', 'humidity', 'windy'];
testList = createTestData();
for testData in testList:
dic = classify(myTree, bootList, testData)
print dic
五、C4.5与ID3的代码区别
如上图,C4.5主要在第52、53行代码与ID3不同(ID3求的是信息增益,C4.5求的是信息增益率)。
六、训练、测试数据集样例
训练集:
outlook temperature humidity windy
---------------------------------------------------------
sunny hot high false N
sunny hot high true N
overcast hot high false Y
rain mild high false Y
rain cool normal false Y
rain cool normal true N
overcast cool normal true Y
测试集
outlook temperature humidity windy
-----------------------------------------------
sunny mild high false
sunny cool normal false
rain mild normal false
sunny mild normal true
overcast mild high true
overcast hot normal false
rain mild high true


猜你喜欢
- 正常的页面跳转的api大家应该都清楚,但是涉及到多页面来回跳转以及返回到导航页的时候就需要一些技巧来进行处理,之前找了挺多文章也没有很详细的
- 一、什么是异常在python中,错误触发的异常如下二、异常的种类在python中不同的异常可以用不同的类型去标识,一个异常标识一种错误。1
- 一、协程介绍协程:英文名Coroutine,是单线程下的并发,又称微线程,纤程。协程是一种用户态的轻量级线程,即协程是由用户程序自己控制调度
- SQL Server与Oracle、DB2的优劣对比:1.开放性:SQL Server只能在Windows上运行,没有丝毫的开放性,操作系统
- 请问如何在ASP中使用ADO调用Oracle的存储过程?我们可以在下面的代码里使用微软Oracle 的OLE DB Provider ,包括
- 今天来分享一下图,这是一种比较复杂的非线性数据结构,之所以复杂是因为他们的数据元素之间的关系是任意的,而不像树那样 被几个性质定理框住了,元
- 1.cv2.threshold()参数说明cv2.threshold(src, thresh, maxval, type[, dst]) &
- 在目前的工作中需要解决复制整个SqlServer数据库的问题,复制的内容包括数据库大纲、数据库中的存储过程、函数、表结构、主外键关系以及表中
- 基本原理选好画板大小,设置好画笔颜色、粗细,定位好位置,依次画鼻子、头、耳朵、眼睛、腮、嘴、身体、手脚、尾巴,完事儿。都知道,T
- 如何避免磁盘临时表因为内存储引擎不支持TEXT和BLOB数据类型, 使用到BLOB和TEXT列的查询和使用隐式临时表的查询将不得不使用MyI
- 本文实例讲述了Python3.5实现的 * 菜单功能。分享给大家供大家参考,具体如下:程序: * 菜单要求:
- 折线图介绍折线图和柱状图一样是我们日常可视化最多的一个图例,当然它的优势和适用场景相信大家肯定不陌生,要想快速的得出趋势,抓住趋势二字,就会
- 概述本文主要介绍一种降维方法,PCA(Principal Component Analysis,主成分分析)。降维致力于解决三类问题。1.
- Python3中print函数的换行最近看了看Python的应用,从入门级的九九乘法表开始,结果发现Python3.x和Python2.x真
- 通过对 26 个字母的设定,设置自己要输出的字体。name = "RUNOOB"# 接收用户输入# name = inp
- 一、selenium截取验证码import jsonfrom io import BytesIOimport timefrom test.t
- PIL中设计的几个基本概念1.通道(bands):即使图像的波段数,RGB图像,灰度图像以RGB图像为例:>>>from
- %r用rper()方法处理对象%s用str()方法处理对象相同结果有些情况下,两者处理的结果是一样的,比如说处理int型对象。例:print
- 毫无疑问,JavaScript 是一种非常灵活的脚本语言,有时候它像一只难以驯服的野马——你受益于它的灵活性的同时,也要时刻提防它变得失去控
- 需求是小程序做头部做导航分类的效果顶部用 scroll-view 组件横向滚动,类似tab选项卡的效果,内容用类似模板方式引用,可重复利用&