查看“︁C4.5算法”︁的源代码

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

C4.5算法与ID3算法一样使用了[[信息熵]]的概念，并和ID3一样通过学习数据来建立决策树。<ref>Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.</ref>

在Springer LNCS于2008年发表的优秀论文中，该算法在前10大数据挖掘算法中排名第一，之后使得它变得非常受欢迎。<ref>{{Cite web |url=http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf |title=Umd.edu - Top 10 Algorithms in Data Mining |accessdate=2019-02-16 |archive-date=2018-11-23 |archive-url=https://web.archive.org/web/20181123174345/http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf |dead-url=no }}</ref>
== 算法 ==

C4.5跟ID3一样，使用信息熵从训练数据集中构建决策树。训练数据是已经分类的样本集合<math>S = {s_1, s_2, ...}</math>。每个样本<math> s_i</math>由p维向量<math>(x_{1,i}, x_{2,i}, ...,x_{p,i}) </math>组成，其中<math> x_j </math>表示样本的属性值或者叫特征，当然也包括样本 <math> s_i </math> 的类别。

在树的每个节点上，C4.5选择数据的属性，该属性最有效地将其样本集划分为集中在一个类或另一个类中的子集。划分准则是归一化的信息增益，即熵的差。选择信息增益最大的属性进行决策，然后对划分后的子集进行递归处理。

该算法有几个基本情况：

* 若一个样本集合的样本都属于同一个类别，则直接创建一个叶节点，表示选择该类别；
* 若所有特征都没有提供任何信息增益，C4.5使用类的期望值在树的上层创建一个决策节点；
* 若遇到了以前未见过的样本，C4.5使用期望值在树的上层创建一个决策节点。

== 伪代码 ==

构建决策树的一般算法是：<ref>S.B. Kotsiantis, "Supervised Machine Learning: A Review of Classification Techniques", ''Informatica'' 31(2007) 249-268, 2007</ref>

# 检查上述基本情况
# 对于每个特征''a''，计算划分''a''的信息增益
# 记''a_best''为最高信息增益的特征
# 创建一个在''a_best''上划分的决策节点
# 使用划分后的样本创建作为当前决策节点的子节点，并在这些子节点上递归地处理

==参考==
{{reflist}}

{{Compsci-stub}}

{{DEFAULTSORT:C4.5 Algorithm}}
[[Category:分類演算法]]
[[Category:决策树]]