AI机器学习-决策树-python实现C4.5算法

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

之所以这样做是因为信息增益倾向于选择取值比较多的特征(特征越多,条件熵(特征划分后的类别变量的熵)越小,信息增益就越大),详细区别可查看之前的文章。

下面我们举例来说明一下,还是以上节的例子,我们加一列,叫名字:

名字,长相,有没有钱,见不见

张三,帅, 有钱, 见

李四,帅, 有钱, 见

王五,帅, 没钱, 不见

赵六,不帅, 有钱, 不见

马七,不帅, 有钱, 不见

按ID3算法,重新运行程序,可以得出下面的决策树结构:

可以发现,名字这个属性的信息增益很大,但是并没有什么实际的意义。这种情况下我们可以用C4.5算法,通过信息增益率来进行条件选择。

根据C4.5算法的定义,某属性的信息增益率等于此属性的信息增益/此属性的信息熵

gainRate(A)=

只需要修改一下条件选择函数,即可实现,新建一个方法chooseBestFeatureToSplit2,内容如下:

#通过递归调用创建决策树,method是指的算法,默认为ID3

defcreateTree(dataSet, labels, method='ID3'):

#获取数据集结果列的数据组成列表

resultList = [example[-1]forexampleindataSet]

ifresultList.count(resultList[0]) == len(resultList): # 列表中的结果集的值相同则直接返回结果值

returnresultList[0]

iflen(dataSet[0]) == 1: #遍历完所有的特征时,仍然不能将数据集划分成仅包含唯一类别的分组 dataSet

returnmajorityCnt(resultList) #由于无法简单的返回唯一的类标签,这里就返回出现次数最多的类别作为返回值

bestFeatColumnIndex=-1

ifmethod =="ID3":

bestFeatColumnIndex = chooseBestFeatureToSplit(dataSet) #ID3算法获取最佳分支属性列索引

ifmethod =="C4.5":

bestFeatColumnIndex = chooseBestFeatureToSplit2(dataSet) # C4.5算法获取最佳分支属性列索引

ifbestFeatColumnIndex == -1: #如果没找出最好的结果,选第一列

bestFeatColumnIndex = 0

bestFeatLabel = labels[bestFeatColumnIndex] #获取最佳分支属性列名称

myTree = }

del(labels[bestFeatColumnIndex]) #把已分配的列名称删除,因为递归调用createTree的时候splitDataSet方法会把当前列去除

featValues = [example[bestFeatColumnIndex]forexampleindataSet] #取出最佳分支列整列的数据组成一个列表

uniqueVals = set(featValues) #把列数据去重,得到此属性的所有可能的不重复取值

forbestFeatColumnUniqueValinuniqueVals:

subLabels = labels[:] # 为了不改变原始列表的内容复制了一下

#递归调用构建决策树

treeResult = createTree(splitDataSet(dataSet,bestFeatColumnIndex, bestFeatColumnUniqueVal), subLabels, method)

myTree[bestFeatLabel][bestFeatColumnUniqueVal] = treeResult

returnmyTree

然后在修改调用方法

myTree = createTree(data, label,"C4.5") 运行后的结果如下图,虽然看上去还是不怎么准确,不过相对来说靠谱了不少。(注,预想应该是长相->是不是有钱,因为是不是有钱这个的增益率和名字的增益率相同,在算法中如果增益率相同,默认取第一个)

关注微信公众号“挨踢学霸”,获取更多技术文章

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180506A04VMP00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券