关键词：
C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点：
1）用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度 度量准则），也就是熵的变化值，ID3算法以信息增益作为划分训练数据集的特征，有一个致命的缺点：选择取值比较多的特征往往会具有较大的信息增益，所以ID3偏向于选择取值较多的特征。
2）在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。
3）对非离散数据也能处理。
4）能够对不完整数据进行处理。
如何计算信息增益率？
熟悉了ID3算法后，已经知道如何计算信息增益，计算公式如下所示（来自Wikipedia）：
或者，用另一个更加直观容易理解的公式计算：
- 按照类标签对训练数据集D的属性集A进行划分，得到信息熵：
- 按照属性集A中每个属性进行划分，得到一组信息熵：
- 计算信息增益
然后计算信息增益，即前者对后者做差，得到属性集合A一组信息增益：
这样，信息增益就计算出来了。
- 计算信息增益率
下面看，计算信息增益率的公式，如下所示（来自Wikipedia）：
其中，IG表示信息增益，按照前面我们描述的过程来计算。而IV是我们现在需要计算的，它是一个用来考虑分裂信息的度量，分裂信息用来衡量属性分 裂数据的广度和均匀程序，计算公式如下所示（来自Wikipedia）：
简化一下，看下面这个公式更加直观：
其中，V表示属性集合A中的一个属性的全部取值。
举例分析
我们以一个很典型被引用过多次的训练数据集D为例，来说明C4.5算法如何计算信息增益并选择决策结点。
上面的训练集有4个属性，即属性集合A={OUTLOOK, TEMPERATURE, HUMIDITY, WINDY}；而类标签有2个，即类标签集合C={Yes, No}，分别表示适合户外运动和不适合户外运动，其实是一个二分类问题。
我们已经计算过信息增益，这里直接列出来，如下所示：
数据集D包含14个训练样本，其中属于类别“Yes”的有9个，属于类别“No”的有5个，则计算其信息熵：
1 |
Info(D) = -9/14 * log2(9/14) - 5/14 * log2(5/14) = 0.940 |
下面对属性集中每个属性分别计算信息熵，如下所示：
1 |
Info(OUTLOOK) = 5/14 * [- 2/5 * log2(2/5) – 3/5 * log2(3/5)] + 4/14 * [ - 4/4 * log2(4/4) - 0/4 * log2(0/4)] + 5/14 * [ - 3/5 * log2(3/5) – 2/5 * log2(2/5)] = 0.694 |
2 |
Info(TEMPERATURE) = 4/14 * [- 2/4 * log2(2/4) – 2/4 * log2(2/4)] + 6/14 * [ - 4/6 * log2(4/6) - 2/6 * log2(2/6)] + 4/14 * [ - 3/4 * log2(3/4) – 1/4 * log2(1/4)] = 0.911 |
3 |
Info(HUMIDITY) = 7/14 * [- 3/7 * log2(3/7) – 4/7 * log2(4/7)] + 7/14 * [ - 6/7 * log2(6/7) - 1/7 * log2(1/7)] = 0.789 |
4 |
Info(WINDY) = 6/14 * [- 3/6 * log2(3/6) – 3/6 * log2(3/6)] + 8/14 * [ - 6/8 * log2(6/8) - 2/8 * log2(2/8)] = 0.892 |
根据上面的数据，我们可以计算选择第一个根结点所依赖的信息增益值，计算如下所示：
1 |
Gain(OUTLOOK) = Info(D) - Info(OUTLOOK) = 0.940 - 0.694 = 0.246 |
2 |
Gain(TEMPERATURE) = Info(D) - Info(TEMPERATURE) = 0.940 - 0.911 = 0.029 |
3 |
Gain(HUMIDITY) = Info(D) - Info(HUMIDITY) = 0.940 - 0.789 = 0.151 |
4 |
Gain(WINDY) = Info(D) - Info(WINDY) = 0.940 - 0.892 = 0.048 |
接下来，我们计算分裂信息度量H(V)：
- OUTLOOK属性
属性OUTLOOK有3个取值，其中Sunny有5个样本、Rainy有5个样本、Overcast有4个样本，则
1 |
H(OUTLOOK) = - 5/14 * log2(5/14) - 5/14 * log2(5/14) - 4/14 * log2(4/14) = 1.577406282852345 |
- TEMPERATURE属性
属性TEMPERATURE有3个取值，其中Hot有4个样本、Mild有6个样本、Cool有4个样本，则
1 |
H(TEMPERATURE) = - 4/14 * log2(4/14) - 6/14 * log2(6/14) - 4/14 * log2(4/14) = 1.5566567074628228 |
- HUMIDITY属性
属性HUMIDITY有2个取值，其中Normal有7个样本、High有7个样本，则
1 |
H(HUMIDITY) = - 7/14 * log2(7/14) - 7/14 * log2(7/14) = 1.0 |
- WINDY属性
属性WINDY有2个取值，其中True有6个样本、False有8个样本，则
1 |
H(WINDY) = - 6/14 * log2(6/14) - 8/14 * log2(8/14) = 0.9852281360342516 |
根据上面计算结果，我们可以计算信息增益率，如下所示：
1 |
IGR(OUTLOOK) = Gain(OUTLOOK) / H(OUTLOOK) = 0.246/1.577406282852345 = 0.15595221261270145 |
2 |
IGR(TEMPERATURE) = Gain(TEMPERATURE) / H(TEMPERATURE) = 0.029 / 1.5566567074628228 = 0.018629669509642094 |
3 |
IGR(HUMIDITY) = Gain(HUMIDITY) / H(HUMIDITY) = 0.151/1.0 = 0.151 |
4 |
IGR(WINDY) = Gain(WINDY) / H(WINDY) = 0.048/0.9852281360342516 = 0.048719680492692784 |
根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点进行分裂。
总结
C4.5算法的优点是：产生的分类规则易于理解，准确率较高。
C4.5算法的缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
机器学习总结决策树id3，c4.5算法，cart算法
...点，并对比了各种算法的不同点。决策树：是一种基本的分类和回归方法。在分类问题中，是基于特征对实例进行分类。既可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。决策树模型：... 查看详情
决策树--c4.5算法
C4.5是另一个分类决策树算法，是基于ID3算法的改进，改进点如下：1、分离信息 解释：数据集通过条件属性A的分离信息，其实和ID3中的熵； 2、信息增益率 解释：Gain(A)为获的A的信息增益，C4.5中选择具有最大增益率... 查看详情
大数据经典算法解析（1）一c4.5算法
...牛正文】：决策树模型：决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边与三类节点：根节点（rootnode），表示第一个特征属性，只有出边没有入边；内部节点（internalnode），表示特征属性，有一条... 查看详情
c4.5算法
参考技术AC4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习：给定一个数据集，其中的每一个元组都能用一组属性值来描述，每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习，找... 查看详情
决策树算法
...杂的熵来度量，使用了相对较为复杂的多叉树，只能处理分类不能处理回归等。对于这些问题，CART算法大部分做了改进。CART算法也就是我们下面的重点了。由于CART算法可以做回归，也可以做分类，我们分别加以介绍，先从CART... 查看详情
C4.5 决策树：分类概率分布？
】C4.5决策树：分类概率分布？【英文标题】：C4.5decisiontree:classificationprobabilitydistribution?【发布时间】：2012-08-0423:37:09【问题描述】：我正在使用Weka的J48(C4.5)决策树分类器。一般来说，对于决策树，一旦碰到叶子就可以确定分类... 查看详情
决策树算法cart和c4.5决策树有啥区别？各用于啥领域？
...策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。3、... 查看详情
机器学习决策树分类原理(代码片段)
决策树分类原理1.熵1.1概念1.2案例2.决策树的划分依据2.1信息增益2.1.1概念2.1.2案例2.2信息增益率2.2.1概念2.2.2案例案例一案例二2.2.3为什么使用C4.5要好?2.3基尼值和基尼指数2.3.1概念2.3.2案例3.小结3.1常见决策树的启发函数比较3.1.1ID3... 查看详情
决策树分类算法小结
引言 本文主要是对分类型决策树的一个总结。在分类问题中，决策树可以被看做是if-then规则的结合，也可以认为是在特定特征空间与类空间上的条件概率分布。决策树学习主要分为三个步骤：特征选择、决策树的生成与剪... 查看详情
02-24决策树总结
...法树结构支持模型特征选择连续值处理缺失值处理剪枝ID3分类多叉树信息增益不支持不支持不支持C4.5分类多叉树信息增益比支持支持支持CART分类、回归二叉树基尼指数、均方差支持支持支持二、决策树优缺点2.1优点简单明了，... 查看详情
决策树与迭代决策树(转)
....RandomForest5.GBDT6.参考内容 今天我们来谈一谈机器学习算法中的各种树形算法，包括ID3、C4.5、CART以及基于集成思想的树模型RandomForest和GBDT。本 查看详情
id3决策树分析
1简述1.1 id3是一种基于决策树的分类算法，由J.RossQuinlan在1986年开发。id3根据信息增益，运用自顶向下的贪心策略建立决策树。信息增益用于度量某个属性对样本集合分类的好坏程度。由于采用了信息增益，id3算... 查看详情
C4.5 决策树算法没有提高准确性
】C4.5决策树算法没有提高准确性【英文标题】：C4.5DecisionTreeAlgorithmdoesn\'timprovetheaccuracy【发布时间】：2017-06-2202:24:49【问题描述】：我在Weka中使用10倍交叉验证运行了C4.5剪枝算法。我注意到未修剪的树比修剪的树具有更高的测... 查看详情
机器学习决策树算法和分类原理(代码片段)
目录1决策树算法简介2决策树分类原理2.1熵2.1.1概念2.1.2案例2.2划分依据一：信息增益2.2.1概念2.2.2案例2.3划分依据二：信息增益率2.3.1概念2.3.2案例2.3.2.1案例一2.3.2.2案例二2.3.3为什么使用C4.5要好2.4划分依据三：基尼值... 查看详情
十大经典算法
...的十大经典算法：一、C4.5C4.5，是机器学习算法中的一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法，ID3的改进算法，所以基本上了解了一半决策树构造方法就能... 查看详情
决策树系列算法总结（id3,c4.5,cart,randomforest,gbdt）
...们不完全是线性的）的逻辑一般是求每个特征对最终分类结果的贡献权重。但是，这种线性组合并不总是有意义的。在这种情况下，如果不想使用多层的神经网络做分类的话，用决策树系列的算法就是不错的选择... 查看详情
统计学习方法五决策树分类
决策树分类1，概念 2，决策树算法2.1，特征选择： 熵：值越大，不确定性因素越大；条件熵：条件对结果的影响不确定性；信息增益；信息增益比 2.2... 查看详情
c4.5算法详解（非常仔细）(代码片段)
首先，C4.5是决策树算法的一种。决策树算法作为一种分类算法，目标就是将具有p维特征的n个样本分到c个类别中去。相当于做一个投影，c=f(n)，将样本经过一种变换赋予一种类别标签。决策树为了达到这一目... 查看详情