Machine learning -- C4.5算法详解及Python实现

程序实现部分转自 Wsine的博客小站

地址:http://www.cnblogs.com/wsine/p/5180315.html

C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习,找到一个从属性值到类别的映射关系,并且这个映射能用于对新的类别未知的实体进行分类。

C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构,其中每个内部节点(非树叶节点)表示在一个属性上的测试,每个分枝代表一个测试输出,而每个树叶节点存放一个类标号。一旦建立好了决策树,对于一个未给定类标号的元组,跟踪一条有根节点到叶节点的路径,该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置,适合于探测性的知识发现。

从ID3算法中衍生出了C4.5和CART两种算法,这两种算法在数据挖掘中都非常重要。下图就是一棵典型的C4.5算法对数据集产生的决策树。

数据集如图1所示,它表示的是天气情况与去不去打高尔夫球之间的关系。

图1 数据集

图2 在数据集上通过C4.5生成的决策树

算法描述

C4.5并不一个算法,而是一组算法—C4.5,非剪枝C4.5和C4.5规则。下图中的算法将给出C4.5的基本工作流程:

图3 C4.5算法流程

我们可能有疑问,一个元组本身有很多属性,我们怎么知道首先要对哪个属性进行判断,接下来要对哪个属性进行判断?换句话说,在图2中,我们怎么知道第一个要测试的属性是Outlook,而不是Windy?其实,能回答这些问题的一个概念就是属性选择度量。

属性选择度量

属性选择度量又称分裂规则,因为它们决定给定节点上的元组如何分裂。属性选择度量提供了每个属性描述给定训练元组的秩评定,具有最好度量得分的属性被选作给定元组的分裂属性。目前比较流行的属性选择度量有--信息增益、增益率和Gini指标。

先做一些假设,设D是类标记元组训练集,类标号属性具有m个不同值,m个不同类Ci(i=1,2,…,m),CiD是D中Ci类的元组的集合,|D|和|CiD|分别是D和CiD中的元组个数。

(1)信息增益

信息增益实际上是ID3算法中用来进行属性选择度量的。它选择具有最高信息增益的属性来作为节点N的分裂属性。该属性使结果划分中的元组分类所需信息量最小。对D中的元组分类所需的期望信息为下式:

(1)

Info(D)又称为熵。

现在假定按照属性A划分D中的元组,且属性A将D划分成v个不同的类。在该划分之后,为了得到准确的分类还需要的信息由下面的式子度量:

(2)

信息增益定义为原来的信息需求(即仅基于类比例)与新需求(即对A划分之后得到的)之间的差,即

(3)

我想很多人看到这个地方都觉得不是很好理解,所以我自己的研究了文献中关于这一块的描述,也对比了上面的三个公式,下面说说我自己的理解。

一般说来,对于一个具有多个属性的元组,用一个属性就将它们完全分开几乎不可能,否则的话,决策树的深度就只能是2了。从这里可以看出,一旦我们选择一个属性A,假设将元组分成了两个部分A1和A2,由于A1和A2还可以用其它属性接着再分,所以又引出一个新的问题:接下来我们要选择哪个属性来分类?对D中元组分类所需的期望信息是Info(D) ,那么同理,当我们通过A将D划分成v个子集Dj(j=1,2,…,v)之后,我们要对Dj的元组进行分类,需要的期望信息就是Info(Dj),而一共有v个类,所以对v个集合再分类,需要的信息就是公式(2)了。由此可知,如果公式(2)越小,是不是意味着我们接下来对A分出来的几个集合再进行分类所需要的信息就越小?而对于给定的训练集,实际上Info(D)已经固定了,所以选择信息增益最大的属性作为分裂点。

但是,使用信息增益的话其实是有一个缺点,那就是它偏向于具有大量值的属性。什么意思呢?就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性。例如一个训练集中有10个元组,对于某一个属相A,它分别取1-10这十个数,如果对A进行分裂将会分成10个类,那么对于每一个类Info(Dj)=0,从而式(2)为0,该属性划分所得到的信息增益(3)最大,但是很显然,这种划分没有意义。

(2)信息增益率

正是基于此,ID3后面的C4.5采用了信息增益率这样一个概念。信息增益率使用“分裂信息”值将信息增益规范化。分类信息类似于Info(D),定义如下:

(4)

这个值表示通过将训练数据集D划分成对应于属性A测试的v个输出的v个划分产生的信息。信息增益率定义:

(5)

选择具有最大增益率的属性作为分裂属性。

(3)Gini指标

Gini指标在CART中使用。Gini指标度量数据划分或训练元组集D的不纯度,定义为:

(6)

其它特征

树剪枝

在决策树的创建时,由于数据中的噪声和离群点,许多分枝反映的是训练数据中的异常。剪枝方法是用来处理这种过分拟合数据的问题。通常剪枝方法都是使用统计度量,剪去最不可靠的分枝。

剪枝一般分两种方法:先剪枝和后剪枝。

先剪枝方法中通过提前停止树的构造(比如决定在某个节点不再分裂或划分训练元组的子集)而对树剪枝。一旦停止,这个节点就变成树叶,该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法,比如(1)当决策树达到一定的高度就停止决策树的生长;(2)到达此节点的实例具有相同的特征向量,而不必一定属于同一类,也可以停止生长(3)到达此节点的实例个数小于某个阈值的时候也可以停止树的生长,不足之处是不能处理那些数据量比较小的特殊情况(4)计算每次扩展对系统性能的增益,如果小于某个阈值就可以让它停止生长。先剪枝有个缺点就是视野效果问题,也就是说在相同的标准下,也许当前扩展不能满足要求,但更进一步扩展又能满足要求。这样会过早停止决策树的生长。

另一种更常用的方法是后剪枝,它由完全成长的树剪去子树而形成。通过删除节点的分枝并用树叶来替换它。树叶一般用子树中最频繁的类别来标记。

C4.5采用悲观剪枝法,它使用训练集生成决策树又用它来进行剪枝,不需要独立的剪枝集。

悲观剪枝法的基本思路是:设训练集生成的决策树是T,用T来分类训练集中的N的元组,设K为到达某个叶子节点的元组个数,其中分类错误地个数为J。由于树T是由训练集生成的,是适合训练集的,因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树,其叶节点个数为L(s),

为到达此子树的叶节点的元组个数总和,

为此子树中被错误分类的元组个数之和。在分类新的元组时,则其错误分类个数为

,其标准错误表示为:

。当用此树分类训练集时,设E为分类错误个数,当下面的式子成立时,则删掉子树S,用叶节点代替,且S的子树不必再计算。

Python实现部分

  • 运行环境:Pyhton3,需要第三方库treePlotter模块(画图所需,不画图可不必)和matplotlib(如果使用上面的模块必须)的支持,请注意安装`!!!!!!安装的教程在请看之前的文章或者去python社区或者参考其他博文。

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学习(guodongwei1991)

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

原始发表时间:2016-06-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏积累沉淀

数据挖掘算法之深入朴素贝叶斯分类

写在前面的话:   我现在大四,毕业设计是做一个基于大数据的用户画像研究分析。所以开始学习数据挖掘的相关技术。这是我学习的一个新技术领域,学习难度比我以往学过的...

37780
来自专栏梦里茶室

CVPR2018: Unsupervised Cross-dataset Person Re-identification by Transfer Learning of Spatio-tempora

CVPR2018: Unsupervised Cross-dataset Person Re-identification by Transfer Learni...

84570
来自专栏数说工作室

金融数据挖掘之决策树(ID3)

数说工作室提供策略编写、数据分析服务和量化支持。

420110
来自专栏IT派

2017年大数据领域薪资有多高?

IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 互联网在经历前几年的繁荣之后,现在开始进入寒冬,资本家不再像以前那样大胆地投资,纷纷攥紧自己...

68340
来自专栏数说工作室

金融数据挖掘之朴素贝叶斯

你和我之前的人生, 就像是来自同一个分布族的共轭曲线, 即使有各自的参数空间, 也注定要相识相念。 你和我之后的人生, 是我们相扶相持下不离不弃的最大似然, 用...

398100
来自专栏IT派

干货 | 面试官是如何看出你机器学习水平的?

面试官如何判断面试者的机器学习水平? 首先这个问题问的很广。做机器学习方向很多,有些公司更偏重于数据挖掘,而有些更倾向于深度学习。同理,相对应的岗位有些偏重理...

50660
来自专栏IT派

常见面试之机器学习算法思想简单梳理

导语:今天小编从别的地方推送一篇更广泛的文章供你们学习参考,总结的常见机器学习算法(主要是一些常规分类器)大概流程和主要思想,希望对大家找机器学习岗位时有点帮助...

39070
来自专栏积累沉淀

数据挖掘算法之贝叶斯网络

贝叶斯网络 序 上上周末写完上篇朴素贝叶斯分类后,连着上了七天班,而且有四天都是晚上九点下班,一直没有多少时间学习贝叶斯网络,所以更新慢了点,利用清明节两天假期...

1.3K100
来自专栏AI研习社

对创业公司的忠告:这么玩数据才不会死

编者注:本文作者 Matthew Coffman,是专注于企业云的风投基金 High Alpha 产品经理。他具有丰富的大数据行业经验,也参与和见证了许多数据公...

34560
来自专栏IT派

一文助你解决数据不平衡的疑惑

导语:这几年来,机器学习和数据挖掘非常火热,它们逐渐为世界带来实际价值。与此同时,越来越多的机器学习算法从学术界走向工业界,而在这个过程中会有很多困难。数据不平...

38180

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励