黑松山资源网 Design By www.paidiu.com
一、概论
C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点。而C4.5引入了新概念“信息增益率”,C4.5是选择信息增益率最大的属性作为树节点。
二、信息增益
以上公式是求信息增益率(ID3的知识点)
三、信息增益率
四、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
以上这篇python实现决策树C4.5算法详解(在ID3基础上改进)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- 【原神】V5.0攻略 | 林尼攻略一图流
- 李翊君.1993-相思的烈酒【上华】【WAV+CUE】
- 古巨基.1998-LEO.KU(国)【千禧年代】【WAV+CUE】
- 郭子.2001-原来你什么都不想要创作集丫滚石】【WAV+CUE】
- 《使命召唤:黑色行动6》新预告公布!10月25日发售
- Atlus《暗喻幻想》媒体评分汇总:高分好评如潮!
- 2024金摇杆奖提名揭晓 《黑神话》角逐最佳视觉设计!
- 群星《新说唱2024 第3期 (上)》[320K/MP3][32.76MB]
- 群星《新说唱2024 第3期 (上)》[FLAC/分轨][95.38MB]
- 群星《新说唱2024 第3期 (下)》[320K/MP3][31.36MB]
- 幻兽帕鲁手游什么时候正式上线 最新消息一览
- 西普大陆BOSS位置盘点 解锁天启纪元玩法
- 西普大陆精灵进阶培养攻略 精灵养成指南
- dnf手游法控法系职业哪个强 dnf手游法控法系职业强度排行
- 魔兽世界血藤护目镜图纸在哪买 wlk血藤护目镜图纸购买位置介绍