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

 更新时间:2018年05月30日 09:22:04   作者:WOTGL   我要评论
本篇文章主要介绍了Python实现决策树C4.5算法的示例,详解的介绍了决策树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()

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持澳门金沙网上娱乐。

相关文章

  • 详解字典树Trie结构及其Python代码实现

    详解字典树Trie结构及其Python代码实现

    Trie多被用来查找和字符串,利用公共前缀来减少搜索时间,下面我们就来详解字典树Trie结构及其Python代码实现
    2016-06-06
  • python实现换位加密算法的示例

    python实现换位加密算法的示例

    今天小编就为大家分享一篇python实现换位加密算法的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-10-10
  • django 微信网页授权认证api的步骤详解

    django 微信网页授权认证api的步骤详解

    这篇文章主要介绍了django 微信网页授权认证api的步骤详解,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
    2019-07-07
  • [机器视觉]使用python自动识别验证码详解

    [机器视觉]使用python自动识别验证码详解

    这篇文章主要介绍了python自动识别验证码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2019-05-05
  • 基于Python的文件类型和字符串详解

    基于Python的文件类型和字符串详解

    下面小编就为大家分享一篇基于Python的文件类型和字符串详解,具有很的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2017-12-12
  • python实现事件驱动

    python实现事件驱动

    这篇文章主要为大家详细介绍了python实现事件驱动的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2018-11-11
  • Python WSGI的深入理解

    Python WSGI的深入理解

    这篇文章主要给大家介绍了关于Python WSGI的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2018-08-08
  • 17个Python小技巧分享

    17个Python小技巧分享

    这篇文章主要给大家分享了17个Python小技巧,都是些基础的非常常用也非常实用的小技巧,这里推荐给大家。
    2015-01-01
  • Python时间戳使用和相互转换详解

    Python时间戳使用和相互转换详解

    这篇文章主要为大家详细介绍了Python时间戳使用和相互转换的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-12-12
  • Python hexstring-list-str之间的转换方法

    Python hexstring-list-str之间的转换方法

    今天小编就为大家分享一篇Python hexstring-list-str之间的转换方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-06-06

最新评论