十大经典数据挖掘算法之C4.5算法

      C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习&＃xff1a;给定一个数据集&＃xff0c;其中的每一个元组都能用一组属性值来描述&＃xff0c;每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习&＃xff0c;找到一个从属性值到类别的映射关系&＃xff0c;并且这个映射能用于对新的类别未知的实体进行分类。C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构&＃xff0c;其中每个内部节点&＃xff08;非树叶节点&＃xff09;表示在一个属性上的测试&＃xff0c;每个分枝代表一个测试输出&＃xff0c;而每个树叶节点存放一个类标号。一旦建立好了决策树&＃xff0c;对于一个未给定类标号的元组&＃xff0c;跟踪一条有根节点到叶节点的路径&＃xff0c;该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置&＃xff0c;适合于探测性的知识发现。

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

                                                                                 图1  数据集

        下图2所示&＃xff0c;就是一棵由C4.5算法对上面数据集产生的决策树

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

           通过上图可以看到&＃xff0c;通过四个属性重要性的不同&＃xff0c;就可以划分出不同的分支&＃xff0c;我们可能有疑问&＃xff0c;一个元组本身有很多属性&＃xff0c;我们怎么知道首先要对哪个属性进行判断&＃xff0c;接下来要对哪个属性进行判断&＃xff1f;换句话说&＃xff0c;在图2中&＃xff0c;我们怎么知道第一个要测试的属性是Outlook&＃xff0c;而不是Windy&＃xff1f;其实&＃xff0c;能回答这些问题的一个概念就是属性选择度量。

       属性选择度量

    属性选择度量又称分裂规则&＃xff0c;因为它们决定给定节点上的元组如何分裂。属性选择度量提供了每个属性描述给定训练元组的秩评定&＃xff0c;具有最好度量得分的属性被选作给定元组的分裂属性。目前比较流行的属性选择度量有--信息增益、增益率和Gini指标。C4.5使用信息增益或者信息增益率作为属性选择度量。&＃xff08;离散属性值使用信息增益&＃xff0c;连续属性值使用信息增益率&＃xff0c;实际应用中通常对连续属性值进行离散化&＃xff09;

    下面分别介绍每种属性选择度量的定义&＃xff0c;先做一些假设&＃xff0c;设D是类标记元组训练集&＃xff0c;类标号属性具有m个不同值&＃xff0c;m个不同类Ci(i&＃61;1,2,…&＃xff0c;m)&＃xff0c;CiD是D中Ci类的元组的集合&＃xff0c;|D|和|CiD|分别是D和CiD中的元组个数。

    &＃xff08;1&＃xff09;信息增益

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

        &＃xff08;1&＃xff09;

Info(D)又称为熵。

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

               &＃xff08;2&＃xff09;

    信息增益定义为原来的信息需求&＃xff08;即仅基于类比例&＃xff09;与新需求&＃xff08;即对A划分之后得到的&＃xff09;之间的差&＃xff0c;即

               &＃xff08;3&＃xff09;

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

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

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

  &＃xff08;2&＃xff09;信息增益率

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

            &＃xff08;4&＃xff09;

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

                 &＃xff08;5&＃xff09;

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

    &＃xff08;3&＃xff09;Gini指标

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

                 &＃xff08;6&＃xff09;

        下面以C4.5的信息增益和信息增益率为例&＃xff0c;介绍决策树生成过程&＃xff0c;上面的训练集有4个属性&＃xff0c;即属性集合A&＃61;{OUTLOOK, TEMPERATURE, HUMIDITY, WINDY}&＃xff1b;而类标签有2个&＃xff0c;即类标签集合C&＃61;{Yes, No}&＃xff0c;分别表示适合打高尔夫球和不适合打高尔夫球&＃xff0c;其实是一个二分类问题。

        我们计算信息增益&＃xff0c;这里直接列出来&＃xff0c;如下所示&＃xff1a;数据集D包含14个训练样本&＃xff0c;其中属于类别“Yes”的有9个&＃xff0c;属于类别“No”的有5个&＃xff0c;则计算其信息熵&＃xff1a;    

下面对属性集中每个属性分别计算信息熵&＃xff0c;如下所示&＃xff1a;

根据上面的数据&＃xff0c;我们可以计算选择第一个根结点所依赖的信息增益值&＃xff0c;计算如下所示&＃xff1a;

接下来&＃xff0c;我们计算分裂信息度量H(V)&＃xff1a;

• OUTLOOK属性

属性OUTLOOK有3个取值&＃xff0c;其中Sunny有5个样本、Rainy有5个样本、Overcast有4个样本&＃xff0c;则

• TEMPERATURE属性

属性TEMPERATURE有3个取值&＃xff0c;其中Hot有4个样本、Mild有6个样本、Cool有4个样本&＃xff0c;则

• HUMIDITY属性

属性HUMIDITY有2个取值&＃xff0c;其中Normal有7个样本、High有7个样本&＃xff0c;则

• WINDY属性

属性WINDY有2个取值&＃xff0c;其中True有6个样本、False有8个样本&＃xff0c;则

根据上面计算结果&＃xff0c;我们可以计算信息增益率&＃xff0c;如下所示&＃xff1a;

      根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点&＃xff0c;对该结点进行分裂。

C4.5算法的优点是&＃xff1a;产生的分类规则易于理解&＃xff0c;准确率较高。
C4.5算法的缺点是&＃xff1a;在构造树的过程中&＃xff0c;需要对数据集进行多次的顺序扫描和排序&＃xff0c;因而导致算法的低效。