C4.5算法是什么以及它是如何工作的？

引言

传统的C4.5技术用于构建决策树，主要用于数据挖掘和机器学习应用中需要分类的任务。它由Doug Quinlan设计，通过修复其前身ID3的缺陷并增加一些新功能来改进ID3。

根本上，C4.5使用分治策略，根据属性值递归地将特征空间划分为更小的子集。该方法旨在通过在每个阶段选择最佳属性来分割数据，从而最大化信息增益，即类别标签的模糊性减少量。

C4.5能够处理离散和连续属性，这使其适用于各种数据集，这是其值得注意的特性之一。为了选择连续属性的适当阈值，它使用了启发式方法。

为了避免过拟合，C4.5还包含剪枝策略，这包括移除对假设数据上的预测准确性没有显著提高的决策树组件。此外，它使用子树替换等技术来处理缺失的属性值。

决策树：C4.5的基础

决策树是C4.5算法的基本构建块，为它的分类过程提供了框架。这些树描绘了一种类似流程图的层级结构，其中每个内部节点表示一个属性测试，每个分支表示测试的结果，每个叶节点表示一个类别名称。

C4.5中的决策树是迭代构建的，在每个阶段基于最佳属性分割数据集。基于像数据增益或增益率这样的度量——它们衡量属性在多大程度上降低了类别标签的混淆——选择最佳属性。直到训练数据被树完全分类或满足某个停止条件，这个过程才会停止。

在C4.5的更大背景下，决策树提供了许多好处。它们为用户提供了一个清晰易懂的模型，使得决策过程可以被理解。决策树是灵活的，可以处理分类数据和数值数据，因为它们能够处理各种数据集类型。

然而，决策树容易过拟合，即模型将训练数据中的模式错误地识别为噪声。C4.5使用剪枝方法来提高树在未见过数据上的泛化效率，并减轻此问题的影响。

信息增益：C4.5的核心主题

信息增益是C4.5算法的核心概念，它在构建决策树时充当选择属性的指导原则。它衡量了一个属性在多大程度上分离了数据，并减少了类别标签的模糊性。

信息增益的基本原理是找到一个属性，当用于分割数据集时，它能提供最大的不确定性或杂质减少量。更少的信息熵意味着类在子集中的标签更加同质。信息熵衡量数据中的不确定性或混乱程度。

C4.5通过比较分割前后数据集的信息熵来计算每个属性的信息增益。在每个决策树节点，选择信息增益最大的属性作为分割标准。

C4.5剪枝技术

• 错误率降低剪枝

使用此方法，从底向上递归遍历决策树，并评估在验证数据集上移除每个子树的效果。如果移除子树会导致性能更好或性能没有显著下降，则将该子树剪枝（替换为单个叶节点）。

• 事后规则剪枝

C4.5构建决策树，然后将这些树转换为一组规则，而不是直接剪枝子树。然后，根据验证数据集的预测准确性，对这些规则进行简化。剪枝是为了移除导致过拟合或不提高分类性能的规则。

• 最小描述长度（MDL）原则

在确定何时停止开发决策树时，C4.5将MDL概念作为指导。该原则在模型的复杂度和其数据拟合程度之间取得平衡。决策树会不断扩展，直到其描述长度（衡量模型复杂度的指标）在没有进一步划分的情况下得到显著减少。

• 子树替换

如果子树的错误率与叶节点的错误率没有显著差异，C4.5会用单个叶节点替换整个子树。这样做可以保持决策树的简单性和预测准确性。

C4.5算法如何工作

• 起点

该方法从完整数据集开始，将其视为决策树的根节点。
集合中的每个实例都是带有相关类别标签和特征（或属性）的信息片段。

• 属性选择

在每个决策树节点，C4.5决定哪个属性最适合将数据集划分为。
对于每个属性，它会计算一个度量，通常是信息增益和增益率。这些度量表明一个属性在多大程度上减少了关于类别标签的模糊性。
对于当前节点，分割标准是通过选择具有最大数据增益或增益率的属性来确定的。

• 分割数据集

在属性选择之后，数据集根据属性的可能值被划分为子集。
分类属性的每个子集对应一个唯一的属性值。
C4.5为连续属性设置一个适当的阈值来分离数据到子集中。

• 递归构建树

该方法会递归地分割数据集，并在上一步生成的每个子集上执行属性选择。
此过程一直持续到满足以下任一条件：
当子集中的所有实例都属于同一类别时，将生成一个叶节点。
没有更多的属性可以用于划分。
树已达到预定的深度。
子集中的实例数量达到某个阈值。

• 还原

一旦树生长成熟，就会进行剪枝，以减少过拟合。
剪枝包括移除不显著提高预测准确性的节点或分支，从而简化树。
常见的剪枝方法包括错误率降低剪枝、事后规则剪枝和子树替换。

• 结果

生成的决策树代表了一组分类规则。
树结构中的每个叶节点对应一个类别标签，树中的每个内部节点表示对一个属性的响应所做的决策。
从根节点到叶节点的路径表示对一个实例进行分类所需的条件。

• Grouping

为了对新实例进行分类，根据该实例的属性值，它会沿着决策树通过根节点移动到叶节点。
算法在每个内部节点评估属性条件，并沿着相应的分支向下移动，直到到达一个叶节点。
实例被分配到遍历过程中到达的叶节点所对应的类别标签。

分割标准

• 信息增益

信息增益量化了一个属性在多大程度上减少了关于类别标签的模糊性。
它通过比较根据属性分割前后数据集的信息熵（也称为杂质）来计算。
数据集的无序和不确定程度由信息熵衡量。类在子集中的标签越同质，信息熵就越低。
信息增益的计算公式如下：
分割前的信息熵 - 分割后信息熵的加权平均值 = 信息增益。
对于当前节点，通过选择具有最大信息增益的属性来确定分割标准。

• 增益率

尽管信息增益很有用，但它倾向于具有许多值的属性。
增益率是信息增益的一种修改，它通过惩罚具有许多不同值的属性来解决对具有更多值的属性的偏见。
它是通过将信息增益（衡量属性的内在信息）除以分裂信息来计算的。
可以使用此公式计算增益率：
信息增益/分裂信息 = 增益率
对于属性值，分裂信息是通过该属性值的熵或其他不纯度指标来确定的。

总结

总而言之，C4.5算法是一种用于分类应用的决策树构建的有效方法。它使用像数据增益或增益率这样的分割标准，选择能够最大化类别标签模糊性减少的属性。通过使用剪枝策略来避免过拟合和递归数据集分割，C4.5能够生成可解释的决策树，并能有效地对实例进行分类。尽管其有效性，C4.5可能受到诸如有偏见的树构建和对嘈杂数据敏感性等问题的影响。尽管如此，它仍然是机器学习领域中的一项基本算法，有助于理解和开发更复杂的分类方法。