python实现决策树C4.5算法详解(在ID3基础上改进)

一、概论

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  

以上这篇python实现决策树C4.5算法详解(在ID3基础上改进)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

时间: 2017-05-30

机器学习python实战之决策树

决策树原理:从数据集中找出决定性的特征对数据集进行迭代划分,直到某个分支下的数据都属于同一类型,或者已经遍历了所有划分数据集的特征,停止决策树算法. 每次划分数据集的特征都有很多,那么我们怎么来选择到底根据哪一个特征划分数据集呢?这里我们需要引入信息增益和信息熵的概念. 一.信息增益 划分数据集的原则是:将无序的数据变的有序.在划分数据集之前之后信息发生的变化称为信息增益.知道如何计算信息增益,我们就可以计算根据每个特征划分数据集获得的信息增益,选择信息增益最高的特征就是最好的选择.首先我们先来

基于ID3决策树算法的实现(Python版)

实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

决策树的python实现方法

本文实例讲述了决策树的python实现方法.分享给大家供大家参考.具体实现方法如下: 决策树算法优缺点: 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据 缺点:可能会产生过度匹配的问题 适用数据类型:数值型和标称型 算法思想: 1.决策树构造的整体思想: 决策树说白了就好像是if-else结构一样,它的结果就是你要生成这个一个可以从根开始不断判断选择到叶子节点的树,但是呢这里的if-else必然不会是让我们认为去设置的,我们要做的是提供一种方法,计算机可以根

决策树剪枝算法的python实现方法详解

本文实例讲述了决策树剪枝算法的python实现方法.分享给大家供大家参考,具体如下: 决策树是一种依托决策而建立起来的一种树.在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射关系,每一个节点代表某个对象,树中的每一个分叉路径代表某个可能的属性值,而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值.决策树仅有单一输出,如果有多个输出,可以分别建立独立的决策树以处理不同的输出. ID3算法:ID3算法是决策树的一种,是基于奥卡姆剃刀原理的,即用尽量用

机器学习之KNN算法原理及Python实现方法详解

本文实例讲述了机器学习之KNN算法原理及Python实现方法.分享给大家供大家参考,具体如下: 文中代码出自<机器学习实战>CH02,可参考本站: 机器学习实战 (Peter Harrington著) 中文版 机器学习实战 (Peter Harrington著) 英文原版 [附源代码] KNN算法介绍 KNN是一种监督学习算法,通过计算新数据与训练数据特征值之间的距离,然后选取K(K>=1)个距离最近的邻居进行分类判(投票法)或者回归.若K=1,新数据被简单分配给其近邻的类. KNN算法

linux下编译boost.python简单方法

最近项目使用c++操作Python脚本,选用boost.python库.在window下编译安装很顺利,但是在Linux下一直编译不通过,总是提示找不到头文件.linux版本为rhel5.7.后来询问同事,原来是同事将原来系统自带的python2.4删除掉了,然后手动编译安装了python3.3. 换到另外一台机器,重新下载boost,使用以下命令,顺利编译成功 ./bootstrap.sh --with-python=/usr/bin/python ./bjam --build-type=mi

Python绑定方法与非绑定方法详解

本文实例为大家分享了Python绑定方法与非绑定方法,供大家参考,具体内容如下 定义: 绑定方法(绑定给谁,谁来调用就自动将它本身当作第一个参数传入): 1. 绑定到类的方法:用classmethod装饰器装饰的方法. 为类量身定制 类.boud_method(),自动将类当作第一个参数传入 (其实对象也可调用,但仍将类当作第一个参数传入) 2. 绑定到对象的方法:没有被任何装饰器装饰的方法. 为对象量身定制 对象.boud_method(),自动将对象当作第一个参数传入 (属于类的函数,类可以

详解Python import方法引入模块的实例

详解Python import方法引入模块的实例 在Python用import或者from-import或者from-import-as-来导入相应的模块,作用和使用方法与C语言的include头文件类似.其实就是引入某些成熟的函数库和成熟的方法,避免重复造轮子,提高开发速度. python的import方法可以引入系统的模块,也可以引入我们自己写好的共用模块,这点和PHP非常相似,但是它们的具体细节还不是很一样.因为php是在引入的时候指明引入文件的具体路径,而python中不能够写文件路径进

Python专用方法与迭代机制实例分析

本文实例讲述了Python专用方法与迭代机制,分享给大家供大家参考之用.具体分析如下: 众所周知,Python 设计哲学是"优雅"."明确"."简单",对于一件事只用一种最好的方法来做,而这种优雅在于背后很自然的隐藏了很多细节.比如对一些对象直接用for 语句来迭代,一些全局函数可以作用于很多具有共同特征的对象,还有生成器装饰器自省等特性.其中很多实现都是借助 Python  内部专用方法,而对外则使用统一的全局函数来进行操作,在配合一些语法糖,

Python加密方法小结【md5,base64,sha1】

本文实例总结了python加密方法.分享给大家供大家参考,具体如下: MD5加密: def md5(str): import hashlib m = hashlib.md5() m.update(str) return m.hexdigest() base64加密: import base64 s = '我是字符串' a = base64.b64encode(s) print a print base64.b64decode(a) 输出结果: ztLKx9fWt/u0rg== 我是字符串 sha

python魔法方法-自定义序列详解

自定义序列的相关魔法方法允许我们自己创建的类拥有序列的特性,让其使用起来就像 python 的内置序列(dict,tuple,list,string等). 如果要实现这个功能,就要遵循 python 的相关的协议.所谓的协议就是一些约定内容.例如,如果要将一个类要实现迭代,就必须实现两个魔法方法:__iter__.next(python3.x中为__new__).__iter__应该返回一个对象,这个对象必须实现 next 方法,通常返回的是 self 本身.而 next 方法必须在每次调用的时

浅谈python字符串方法的简单使用

学习python字符串方法的使用,对书中列举的每种方法都做一个试用,将结果记录,方便以后查询. (1) s.capitalize() ;功能:返回字符串的的副本,并将首字母大写.使用如下: >>> s = 'wwwwww' >>> scap = s.capitalize() >>> scap 'Wwwwww' (2)s.center(width,char); 功能:返回将s字符串放在中间的一个长度为width的字符串,默认其他部分用空格填充,否则使用c