C4.5算法

ID3算法的一个扩展

C4.5算法是由Ross Quinlan开发的用于产生决策树的算法。该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法产生的决策树可以被用作分类目的，因此该算法也可以用于统计分类。

产品介绍

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

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

从ID3算法中衍生出了C4.5和CART两种算法，这两种算法在数据挖掘中都非常重要。

改进表现

用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（entropy，熵是一种不纯度度量准则），也就是熵的变化值，而C4.5用的是信息增益率。

在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。

对非离散数据也能处理。

能够对不完整数据进行处理。

优缺点

C4.5算法优点：产生的分类规则易于理解，准确率较高。

缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

算法描述

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

Input:an attibute-valued dataset D

1:Tree={}

3: terminate

4: end if

5:for all attribute a∈ D do

6: Compute inforation-theoretic criteria if we split on a

7:end for

8:a(best)=Best attribute according to above computed criteria

9: Tree=Create a decision node that tests a(best) in the root

10:D(v)=Induced sub-datasets from D based on a(best)

11:for all D(v) do

12: Tree(v)=C4.5(D(v))

13: Attach Tree(v) to the corresponding branch of Tredd

14:end for

15:return Tree

属性选择度量

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

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

（1）信息增益

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

Info(D)又称为熵。

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

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

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

一般说来，对于一个具有多个属性的元组，用一个属性就将它们完全分开几乎不可能，否则的话，决策树的深度就只能是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)，定义如下：

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

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

（3）Gini指标

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

其它特征

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

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

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

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省