专栏首页机器学习算法与Python学习机器学习(11)之C4.5详解与Python实现(从解决ID3不足的视角)

机器学习(11)之C4.5详解与Python实现(从解决ID3不足的视角)

关键字全网搜索最新排名

【机器学习算法】:排名第一

【机器学习】:排名第二

【Python】:排名第三

【算法】:排名第四

前言

上一篇(机器学习(9)之ID3算法详解及python实现)我们讲到ID3算法有四个主要的不足,一是不能处理连续特征,第二个就是用信息增益作为标准容易偏向于取值较多的特征,最后两个是缺失值处理的问和过拟合问题。昆兰在C4.5算法中改进了上述4个问题。

针对于问题1

对于第一个问题,不能处理连续特征, C4.5的思路是将连续的特征离散化。比如 m 个样本的连续特征 A 有 m个,从小到大排列为a1,a2,...,am, 则C4.5取相邻两样本值的中位数,一共取得m-1个划分点,其中第i个划分点表示Ti表示为:Ti=ai+ai+12。对于这m-1个点,分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at,则小于at的值为类别1,大于at的值为类别2,这样我们就做到了连续特征的离散化。要注意的是,与离散属性不同的是,如果当前节点为连续属性,则该属性后面还可以参与子节点的产生选择过程。

针对于问题2

对于第二个问题,信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量IR(X,Y),它是信息增益和特征熵的比值。表达式如下:

其中D为样本特征输出的集合,A为样本特征,对于特征熵HA(D), 表达式如下:

其中n为特征A的类别数, Di为特征A的第i个取值对应的样本个数,D为样本个数。特征数越多的特征对应的特征熵越大,它作为分母,可以校正信息增益容易偏向于取值较多的特征的问题。

针对于问题3

对于第三个缺失值处理的问题,主要需要解决的是两个问题,一是在样本某些特征缺失的情况下选择划分的属性,二是选定了划分属性,对于在该属性上缺失特征的样本的处理。

对于第一个子问题,对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分,对每个样本设置一个权重(初始可以都为1),然后划分数据,一部分是有特征值A的数据D1,另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比,最后乘上一个系数,这个系数是无特征A缺失的样本加权后所占加权总样本的比例。

对于第二个子问题,可以将缺失特征的样本同时划分入所有的子节点,不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1,特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1,A2,A3。对应权重调节为2/9,3/9, 4/9。

对于第4个问题,C4.5引入了正则化系数进行初步的剪枝。具体方法这里不讨论。之后会在讲CART的时候会详细讨论剪枝的思路。除了上面的4点,C4.5和ID的思路区别不大。

C4.5的不足与思考

C4.5虽然改进或者改善了ID3算法的几个主要的问题,仍然有优化的空间。

  1)由于决策树算法非常容易过拟合,因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多,C4.5的剪枝方法有优化的空间。思路主要是两种,一种是预剪枝,即在生成决策树的时候就决定是否剪枝。另一个是后剪枝,即先生成决策树,再通过交叉验证来剪枝。后面在讲CART树的时候我们会专门讲决策树的减枝思路,主要采用的是后剪枝加上交叉验证选择最合适的决策树。

 2)C4.5生成的是多叉树,即一个父节点可以有多个节点。很多时候,在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树,可以提高效率。

 3)C4.5只能用于分类,如果能将决策树用于回归的话可以扩大它的使用范围。

 4)C4.5由于使用了熵模型,里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话,那就更好了。

python实现

在算法实现上,C4.5算法只是修改了信息增益计算的函数calcShannonEntOfFeature和最优特征选择函数chooseBestFeatureToSplit。calcShannonEntOfFeature在ID3的calcShannonEnt函数上加了个参数feat,ID3中该函数只用计算类别变量的熵,而calcShannonEntOfFeature可以计算指定特征或者类别变量的熵。chooseBestFeatureToSplit函数在计算好信息增益后,同时计算了当前特征的熵IV,然后相除得到信息增益比,以最大信息增益比作为最优特征。

#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()

参考:

1. 周志华《机器学习》

2. http://www.cnblogs.com/pinard/p/6050306.html

3. 李航 《统计学习方法》

4. http://www.cnblogs.com/vincent-vg/p/6745275.html

本文分享自微信公众号 - 机器学习算法与Python学习(guodongwei1991),作者:昱良

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-08-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器学习(9)之ID3算法详解及python实现

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 前言 决策树算法在机器学习中算是很经...

    昱良
  • 我的八年博士生涯——CMU王赟写在入职Facebook之前

    下周一我就要开始在 Facebook 上班了。趁入职之前,我想写一写我博士生涯的感悟;再不写就要凉啦。

    昱良
  • 1 行Python代码能干哪些事,这 13个你知道吗?

    来源:http://www.techug.com/post/what-can-a-line-of-python-code-do.html

    昱良
  • 干货 | 证件全文本OCR技术,了解一下

    携程技术
  • Python 运算符

    本章节主要说明Python的运算符。举个简单的例子 4 +5 = 9 。 例子中,4和5被称为操作数,"+"号为运算符。

    想偷懒的程序员
  • RTSP/ONVIF互联网直播服务器录像回看接口调用时查询到超出指定时间段录像文件

    优秀便捷的流媒体服务器都支持二次开发调用API对接,同时支持选取指定时间段录像播放及下载(MP4合成播放下载)进行调用,在日常使用中录像接口调用用的是比较频繁的...

    EasyNVR
  • WPF效果第一百一十九篇之自定义Window

    在去年我就吐槽过同事牛逼哄哄的自定义无边窗体效果;本来是几个属性就搞定的事情;这不最近又要去摸索他了,原来都是直接通过属性控制自定义窗口,但是这么玩每加一个窗体...

    WPF程序员
  • 《2019自由行用户旅行偏好数据报告》:九成人宁愿超支剁手| 每周文旅资讯精选(10.21-10.27)

    ? ? 故宫博物院与北大、敦煌研究院签署协议 共同开展文物保护与研究 10月20日,故宫博物院与北京大学、敦煌研究院20日在故宫博物院建福宫花园敬胜斋召开战略...

    腾讯文旅
  • php实现的支付宝网页支付功能示例【基于TP5框架】

    更多关于thinkPHP相关内容感兴趣的读者可查看本站专题:《ThinkPHP入门教程》、《thinkPHP模板操作技巧总结》、《ThinkPHP常用方法总结》...

    砸漏
  • ASP.NET MVC 微信JS-SDK认证

    李国宝

扫码关注云+社区

领取腾讯云代金券