Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

C4.5决策树算法

C4.5算法是由Ross Quinlan开发的用于产生决策树的算法。该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法产生的决策树可以被用作分类目的,因此该算法也可以用于统计分类。 C4.5算法与ID3算法一样使用了信息熵的概念,并和ID3一样通过学习数据来建立决策树

来源:维基百科
简介

C4.5是一种生成决策树的算法,它由Ross Quinlan发布。C4.5是Ross Quinlan早期发布的ID3算法的延伸。由C4.5生成的决策树可以被用于分类,由此,C4.5也被称为统计分类器。Weka机器学习软件的开发者描述C4.5算法为“具有里程碑意义的决策树程序,也可能是机器学习中训练数据的主力”。

C4.5算法是数据挖掘十大算法之一,它是对ID3算法的改进,相对于ID3算法主要有以下几个改进

(1)用信息增益比来选择属性

(2)在决策树的构造过程中对树进行剪枝

(3)对非离散数据也能处理

(4)能够对不完整数据进行处理

C4.5使用信息熵的概念,以与ID3相同的方式从一组训练数据构建决策树。训练数据是一组数据(S=s_{1},s_{2},...)已经分类的样本。每个样品s_{i}由一个p维矢量组成(x_{1,i},x_{2,i},...,x_{p,i}),x_{j}代表样本的属性值或特征,以及其中的类s_{i}下降。

在树的每个节点上,C4.5选择最有效地将其样本集分成富集于一个类或另一个类的子集的数据属性。分裂标准是标准化的信息增益(熵的差异)。选择具有最高标准化信息增益的属性作出决定。C4.5算法然后在较小的子列表上重复出现。

这个算法有几个基本情况。

1.列表中的所有样本属于同一类。发生这种情况时,它只是为决策树创建一个叶节点来说明选择该类。

2.没有任何功能提供任何信息获取。在这种情况下,C4.5使用类的期望值在树上创建一个决策节点。

3.遇到以前看不见的类的实例。同样,C4.5使用期望值在树上创建一个决策节

来源:

wikipediahttps://en.wikipedia.org/wiki/C4.5_algorithm

例子:

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

从ID3算法中衍生出了C4.5和CART两种算法,这两种算法在数据挖掘中都非常重要。下图就是一棵典型的C4.5算法对数据集产生的决策树。数据集如下图所示,它表示的是天气情况与去不去打高尔夫球之间的关系。


A

B

C

D

E

F

1

Day

Outlook

Temperature

Humidity

Windy

Play Golf?

2

1

Sunny

85

85

FALSE

No

3

2

Sunny

80

90

TRUE

No

4

3

Overcast

83

78

FALSE

Yes

5

4

Rainy

70

96

FALSE

Yes

6

5

Rainy

68

80

FALSE

Yes

7

6

Rainy

65

70

TRUE

No

8

7

Overcast

64

65

TRUE

Yes

9

8

Sunny

72

95

FALSE

No

10

9

Sunny

69

70

FALSE

Yes

11

10

Rainy

75

80

FALSE

Yes

12

11

Sunny

75

70

TRUE

Yes

13

12

Overcast

72

90

TRUE

Yes

14

13

Overcast

81

75

FALSE

Yes

15

14

Rainy

71

80

TRUE

No

在数据集上通过C4.5生成的决策树,如下图所示:

算法描述:C4.5并不一个算法,而是一组算法—C4.5,非剪枝C4.5和C4.5规则。下图中的算法将给出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中的元组分类所需的期望信息为下式:

Info(D)=-\sum_{i=1}^{m}p_{i}log_{2}(p_{i}) 式(1)

Info(D)又称为熵。

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

Info_{A}(D)=-\sum_{j=1}^{v}\frac{\left |D_{j} \right |}{\left |D \right |}*Info(D_{j}) 式(2)

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

Gain(A)=Info(D)-Info_{A}(D) 式(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),定义如下:

SplitInfo_{A}(D)=-\sum_{j=1}^{v}\frac{\left | D_{j} \right |}{\left | D \right |}*log_{2}(\frac{\left | D_{j} \right |}{\left | D \right |})

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

GainRatio(A)=\frac{Gain(A)}{SplitInfo(A)}

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

(3)Gini指标

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

Gini(D)=1-\sum_{i=1}^{m}p_{i}^{2}

其他特征

树剪枝

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

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

先剪枝方法中通过提前停止树的构造(比如决定在某个节点不再分裂或划分训练元组的子集)而对树剪枝。一旦停止,这个节点就变成树叶,该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法,比如:

(1)当决策树达到一定的高度就停止决策树的生长;

(2)到达此节点的实例具有相同的特征向量,而不必一定属于同一类,也可以停止生长

(3)到达此节点的实例个数小于某个阈值的时候也可以停止树的生长,不足之处是不能处理那些数据量比较小的特殊情况

(4)计算每次扩展对系统性能的增益,如果小于某个阈值就可以让它停止生长。先剪枝有个缺点就是视野效果问题,也就是说在相同的标准下,也许当前扩展不能满足要求,但更进一步扩展又能满足要求。这样会过早停止决策树的生长。

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

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

悲观剪枝法的基本思路是:设训练集生成的决策树是T,用T来分类训练集中的N的元组,设K为到达某个叶子节点的元组个数,其中分类错误地个数为J。由于树T是由训练集生成的,是适合训练集的,因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树,其叶节点个数为L(s),\sum K为到达此子树的叶节点的元组个数总和,\sum J为此子树中被错误分类的元组个数之和。在分类新的元组时,则其错误分类个数为\sum J+\frac{L(S)}{2},其标准错误表示为:se(E)=\sqrt{\frac{E*(N-E)}{N}}。当用此树分类训练集时,设E为分类错误个数,当下面的式子成立时,则删掉子树S,用叶节点代替,且S的子树不必再计算。

E+\frac{1}{2}< (\sum J+\frac{L(S)}{2})+se(\sum J+\frac{L(S)}{2})

发展历史

描述

最早的决策树算法是由Hunt等人于1966年提出的CLS。当前最有影响的决策树算法是由Quinlan于1986年提出的ID3和1993年提出的C4.5.其他早期算法还包括CART,FACT,CHAID算法。后期的算法主要有SLIQ, SPRINT, PUBLIC等。

传统的决策树分类算法主要是针对小数据集的,大都要求训练集常驻内存,这使得在处理数据挖掘任务时,传统决策树算法在可伸展性,精度和效率方面受到了很大的限制。而在实际的数据挖掘应用中我们面临的数据集往往是容量巨大的数据库或者数据仓库,在构造决策树时需要将庞大的数据在主存和缓存中不停地导入导出,使得运算效率大大降低。针对以上问题,许多学者提出了处理大型数据集的决策树算法。

主要事件


A

B

C

1

年份

事件

相关论文

2

1993

Ross Quinlan对ID3算法扩展,发明了C4.5算法

C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers.ISBN1-55860-238-0

3

2002

讲解了离散类数据挖掘的标杆属性选择技术,其中讲解了C4.5在大数据挖掘的应用。

Hall M A, Holmes G. Benchmarking Attribute Selection Techniques for Discrete Class Data Mining[J]. IEEE Transactions on Knowledge & Data Engineering, 2002, 15(6):1437-1447.

4




发展分析

瓶颈

C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

未来发展方向

NA

Contributor: JiangPeng

简介