Python实现决策树C4.5算法的示例

为什么要改进成C4.5算法

原理

C4.5算法是在ID3算法上的一种改进,它与ID3算法最大的区别就是特征选择上有所不同,一个是基于信息增益比,一个是基于信息增益。

之所以这样做是因为信息增益倾向于选择取值比较多的特征(特征越多,条件熵(特征划分后的类别变量的熵)越小,信息增益就越大);因此在信息增益下面加一个分母,该分母是当前所选特征的熵,注意:这里而不是类别变量的熵了。

这样就构成了新的特征选择准则,叫做信息增益比。为什么加了这样一个分母就会消除ID3算法倾向于选择取值较多的特征呢?

因为特征取值越多,该特征的熵就越大,分母也就越大,所以信息增益比就会减小,而不是像信息增益那样增大了,一定程度消除了算法对特征取值范围的影响。

实现

在算法实现上,C4.5算法只是修改了信息增益计算的函数calcShannonEntOfFeature和最优特征选择函数chooseBestFeatureToSplit。

calcShannonEntOfFeature在ID3的calcShannonEnt函数上加了个参数feat,ID3中该函数只用计算类别变量的熵,而calcShannonEntOfFeature可以计算指定特征或者类别变量的熵。

chooseBestFeatureToSplit函数在计算好信息增益后,同时计算了当前特征的熵IV,然后相除得到信息增益比,以最大信息增益比作为最优特征。

在划分数据的时候,有可能出现特征取同一个值,那么该特征的熵为0,同时信息增益也为0(类别变量划分前后一样,因为特征只有一个取值),0/0没有意义,可以跳过该特征。

#coding=utf-8
import operator
from math import log
import time
import os, sys
import string

def createDataSet(trainDataFile):
 print trainDataFile
 dataSet = []
 try:
 fin = open(trainDataFile)
 for line in fin:
  line = line.strip()
  cols = line.split('\t')
  row = [cols[1], cols[2], cols[3], cols[4], cols[5], cols[6], cols[7], cols[8], cols[9], cols[10], cols[0]]
  dataSet.append(row)
  #print row
 except:
 print 'Usage xxx.py trainDataFilePath'
 sys.exit()
 labels = ['cip1', 'cip2', 'cip3', 'cip4', 'sip1', 'sip2', 'sip3', 'sip4', 'sport', 'domain']
 print 'dataSetlen', len(dataSet)
 return dataSet, labels

#calc shannon entropy of label or feature
def calcShannonEntOfFeature(dataSet, feat):
 numEntries = len(dataSet)
 labelCounts = {}
 for feaVec in dataSet:
 currentLabel = feaVec[feat]
 if currentLabel not in labelCounts:
  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:
 if featVec[axis] == value:
  reducedFeatVec = featVec[:axis]
  reducedFeatVec.extend(featVec[axis+1:])
  retDataSet.append(reducedFeatVec)
 return retDataSet

def chooseBestFeatureToSplit(dataSet):
 numFeatures = len(dataSet[0]) - 1 #last col is label
 baseEntropy = calcShannonEntOfFeature(dataSet, -1)
 bestInfoGainRate = 0.0
 bestFeature = -1
 for i in range(numFeatures):
 featList = [example[i] for example in dataSet]
 uniqueVals = set(featList)
 newEntropy = 0.0
 for value in uniqueVals:
  subDataSet = splitDataSet(dataSet, i, value)
  prob = len(subDataSet) / float(len(dataSet))
  newEntropy += prob *calcShannonEntOfFeature(subDataSet, -1) #calc conditional entropy
 infoGain = baseEntropy - newEntropy
    iv = calcShannonEntOfFeature(dataSet, i)
 if(iv == 0): #value of the feature is all same,infoGain and iv all equal 0, skip the feature
 continue
    infoGainRate = infoGain / iv
 if infoGainRate > bestInfoGainRate:
  bestInfoGainRate = infoGainRate
  bestFeature = i
 return bestFeature

#feature is exhaustive, reture what you want label
def majorityCnt(classList):
 classCount = {}
 for vote in classList:
 if vote not in classCount.keys():
  classCount[vote] = 0
 classCount[vote] += 1
 return max(classCount)  

def createTree(dataSet, labels):
 classList = [example[-1] for example in dataSet]
 if classList.count(classList[0]) ==len(classList): #all data is the same label
 return classList[0]
 if len(dataSet[0]) == 1: #all feature is exhaustive
 return majorityCnt(classList)
 bestFeat = chooseBestFeatureToSplit(dataSet)
 bestFeatLabel = labels[bestFeat]
 if(bestFeat == -1): #特征一样,但类别不一样,即类别与特征不相关,随机选第一个类别做分类结果
 return classList[0]
 myTree = {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 main():
 if(len(sys.argv) < 3):
 print 'Usage xxx.py trainSet outputTreeFile'
 sys.exit()
 data,label = createDataSet(sys.argv[1])
 t1 = time.clock()
 myTree = createTree(data,label)
 t2 = time.clock()
 fout = open(sys.argv[2], 'w')
 fout.write(str(myTree))
 fout.close()
 print 'execute for ',t2-t1
if __name__=='__main__':
 main()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python实现决策树并且使用Graphvize可视化的例子

    一.什么是决策树(decision tree)--机器学习中的一个重要的分类算法 决策树是一个类似于数据流程图的树结构:其中,每个内部节点表示一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或者类的分布,树的最顶层是根结点 根据天气情况决定出游与否的案例 二.决策树算法构建 2.1决策树的核心思路 特征选择:从训练数据的特征中选择一个特征作为当前节点的分裂标准(特征选择的标准不同产生了不同的特征决策树算法). 决策树生成:根据所选特征评估标准,从上至下递归地生成子节点,直到数据集

  • python实现决策树ID3算法的示例代码

    在周志华的西瓜书和李航的统计机器学习中对决策树ID3算法都有很详细的解释,如何实现呢?核心点有如下几个步骤 step1:计算香农熵 from math import log import operator # 计算香农熵 def calculate_entropy(data): label_counts = {} for feature_data in data: laber = feature_data[-1] # 最后一行是laber if laber not in label_counts

  • Python3.0 实现决策树算法的流程

    决策树的一般流程 检测数据集中的每个子项是否属于同一个分类 if so return 类标签 Else 寻找划分数据集的最好特征 划分数据集 创建分支 节点 from math import log import operator #生成样本数据集 def createDataSet(): dataSet = [[1,1,'yes'], [1,1,'yes'], [1,0,'no'], [0,1,'no'], [0,1,'no']] labels = ['no surfacing','flipp

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

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

  • 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 =

  • python使用sklearn实现决策树的方法示例

    1. 基本环境 安装 anaconda 环境, 由于国内登陆不了他的官网 https://www.continuum.io/downloads, 不过可以使用国内的镜像站点: https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 添加绘图工具 Graphviz http://www.graphviz.org/Download_windows.php 安装后, 将bin 目录内容添加到环境变量path 即可 参考blog : https://

  • python实现决策树、随机森林的简单原理

    本文申明:此文为学习记录过程,中间多处引用大师讲义和内容. 一.概念 决策树(Decision Tree)是一种简单但是广泛使用的分类器.通过训练数据构建决策树,可以高效的对未知的数据进行分类.决策数有两大优点:1)决策树模型可以读性好,具有描述性,有助于人工分析:2)效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度. 看了一遍概念后,我们先从一个简单的案例开始,如下图我们样本: 对于上面的样本数据,根据不同特征值我们最后是选择是否约会,我们先自定义的一个决策树

  • Python决策树和随机森林算法实例详解

    本文实例讲述了Python决策树和随机森林算法.分享给大家供大家参考,具体如下: 决策树和随机森林都是常用的分类算法,它们的判断逻辑和人的思维方式非常类似,人们常常在遇到多个条件组合问题的时候,也通常可以画出一颗决策树来帮助决策判断.本文简要介绍了决策树和随机森林的算法以及实现,并使用随机森林算法和决策树算法来检测FTP暴力破解和POP3暴力破解,详细代码可以参考: https://github.com/traviszeng/MLWithWebSecurity 决策树算法 决策树表现了对象属性和

  • python实现ID3决策树算法

    ID3决策树是以信息增益作为决策标准的一种贪心决策树算法 # -*- coding: utf-8 -*- from numpy import * import math import copy import cPickle as pickle class ID3DTree(object): def __init__(self): # 构造方法 self.tree = {} # 生成树 self.dataSet = [] # 数据集 self.labels = [] # 标签集 # 数据导入函数

  • Python机器学习算法库scikit-learn学习之决策树实现方法详解

    本文实例讲述了Python机器学习算法库scikit-learn学习之决策树实现方法.分享给大家供大家参考,具体如下: 决策树 决策树(DTs)是一种用于分类和回归的非参数监督学习方法.目标是创建一个模型,通过从数据特性中推导出简单的决策规则来预测目标变量的值. 例如,在下面的例子中,决策树通过一组if-then-else决策规则从数据中学习到近似正弦曲线的情况.树越深,决策规则越复杂,模型也越合适. 决策树的一些优势是: 便于说明和理解,树可以可视化表达: 需要很少的数据准备.其他技术通常需要

  • python基于ID3思想的决策树

    这是一个判断海洋生物数据是否是鱼类而构建的基于ID3思想的决策树,供大家参考,具体内容如下 # coding=utf-8 import operator from math import log import time def createDataSet(): dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no'], [0,0,'maybe']] labels = ['no surface

随机推荐