Brett Lantz在R中使用C5.0算法实现决策树

Brett Lantz在R中使用C5.0算法实现决策树

• 来源 | 愿码(ChainDesk.CN) 内容编辑
• 愿码Slogan | 连接每个 程序员 的故事
• 网站 | http://chaindesk.cn
• 愿码愿景 | 打造全学科IT系统免费课程，助力小白用户、初级工程师0成本免费系统学习、低成本进阶，帮助BAT一线资深工程师成长并利用自身优势创造睡后收入。
• 官方公众号 | 愿码 | 愿码服务号 | 区块链部落
• 免费加入愿码全思维工程师社群 | 任一公众号回复“愿码”两个字获取入群二维码

本文阅读时长：9min

决策树学习者是强大的分类器，它利用树结构来模拟特征和潜在结果之间的关系。这种结构之所以得名，是因为它反映了文字树在宽阔的树干上开始的方式，并且当它向上延伸时分裂成更窄的树枝。以同样的方式，决策树分类器使用分支决策的结构，其将示例引导到最终预测的类值。

决策树有很多实现，但最著名的是 C5.0算法 。该算法由计算机科学家J. Ross Quinlan开发，作为其先前算法 C4.5 的改进版本（C4.5本身是对其 迭代二分法3（ID3） 算法的改进）。虽然Quinlan向商业客户销售C5.0，但该算法的单线程版本的源代码已公开，因此已被纳入诸如R等程序中。

C5.0决策树算法

C5.0算法已经成为生成决策树的行业标准，因为它可以直接开箱即用地解决大多数类型的问题。与其他高级机器学习模型相比 ，C5.0构建的决策树通常表现得差不多但更容易理解和部署。此外，如下表所示，算法的弱点相对较小，可以在很大程度上避免。

优势

• 一种通用分类器，可以很好地解决许多类型的问题。
• 高度自动化的学习过程，可以处理数字或名义特征，以及缺少数据。
• 不包括不重要的功能。
• 可以在小型和大型数据集上使用。
• 在没有数学背景的情况下可以解释的模型中的结果（对于相对较小的树）。
• 比其他复杂模型更有效。

弱点

• 决策树模型通常偏向于具有大量级别的特征的分裂。
• 很容易过度装配或不适合模型。
• 由于依赖于轴并行分割，可能无法对某些关系建模。
• 训练数据的微小变化可能导致决策逻辑发生很大变化。
• 大树很难解释，他们做出的决定似乎违反直觉。

为了简单起见，我们早期的决策树示例忽略了机器如何采用分而治之策略所涉及的数学问题。让我们更详细地探讨这一点，以研究这种启发式方法在实践中如何运作。

选择最佳分割

决策树将面临的第一个挑战是确定要拆分的特征。在前面的示例中，我们寻找一种分割数据的方法，使得生成的分区包含主要包含单个类的示例。示例子集仅包含单个类的程度称为 纯度 ，而仅由单个类组成的任何子集称为 纯 。

可以使用各种纯度测量来识别最佳决策树分裂候选者。C5.0使用 熵 ，这是一种借鉴信息理论的概念，用于量化一组类值中的随机性或无序性。具有高熵的集合非常多样化，并且提供关于可能也属于集合的其他项目的很少信息，因为没有明显的共性。决策树希望找到减少熵的分裂，最终增加组内的同质性。

通常，熵以 比特 来度量。如果只有两个可能的类，则熵值的范围可以从0到1.对于n个类，熵范围从0到log 2 （n）。在每种情况下，最小值表示样本是完全同质的，而最大值表示数据尽可能多样化，并且没有组具有甚至小的多个。

在数学概念中，熵被指定为：

在该公式中，对于给定的数据段（S），术语c指的是类级别的数量，并且p i  指的是落入级别级别i的值的比例。例如，假设我们有两个类的数据分区：红色（60％）和白色（40％）。我们可以将熵计算为：

> -0.60 * log2(0.60) - 0.40 * log2(0.40)

[1] 0.9709506

我们可以想象所有可能的两级安排的熵。如果我们知道一个类中的例子的比例是x，那么另一个类中的比例是（1-x）。使用curve（）函数，我们可以绘制x的所有可能值的熵：

> curve(-x * log2(x) - (1 - x) * log2(1 - x),

    col = "red", xlab = "x", ylab = "Entropy", lwd = 4)

如下图：

如在x = 0.50处的熵峰值所示，50-50分裂导致最大熵。随着一个类越来越主导另一个类，熵减少到零。

为了使用熵来确定要分割的最佳特征，该算法计算由于对每个可能特征的分割而导致的同质性变化，该度量被称为 信息增益 。特征F的信息增益被计算为分割（S 1）之前的片段中的熵与分割（S 2）产生的分区之间的差异：

一个复杂的问题是，在拆分之后，数据被分成多个分区。因此，计算熵（S 2 ）的函数需要考虑所有分区的总熵。它通过根据落入该分区的所有记录的比例对每个分区的熵进行加权来实现此目的。这可以在公式中说明如下：

简单来说，由分割产生的总熵是n个分区中的每一个的熵的总和，其由落入分区（w i）中的示例的比例加权。

信息增益越高，在对该特征进行拆分后创建同类组的功能就越好。如果信息增益为零，则不会减少用于分割此特征的熵。另一方面，最大信息增益等于分割之前的熵。这意味着拆分后的熵为零，这意味着拆分产生完全同质的组。

以前的公式假设名义特征，但决策树也使用信息增益来分割数字特征。为此，通常的做法是测试将值划分为大于或小于阈值的组的各种拆分。这会将数字特征缩减为两级分类功能，以便像往常一样计算信息增益。为分割选择产生最大信息增益的数字切割点。

注意：尽管它被C5.0使用，但信息增益并不是可用于构建决策树的唯一分裂标准。其他常用标准是基尼指数，卡方统计量和增益比。

修剪决策树

如前所述，决策树可以继续无限增长，选择拆分功能并划分为更小和更小的分区，直到每个示例完全分类或算法耗尽要分离的功能。但是，如果树长得过大，那么它做出的许多决定将过于具体，模型将过度拟合到训练数据中。 修剪 决策树的过程涉及减小其大小，以便更好地概括为看不见的数据。

该问题的一个解决方案是在树达到一定数量的决策时或当决策节点仅包含少量示例时阻止树增长。这称为 提前停止 或 预先 确定决策树。由于树避免做不必要的工作，这是一个吸引人的策略。然而，这种方法的一个缺点是，无法知道树是否会错过细微但重要的模式，如果它变得更大，它将会学到它。

另一种称为 后修剪的方法 涉及种植有意过大的树并修剪叶节点以将树的大小减小到更合适的水平。这通常是比预执行更有效的方法，因为在不首先增加决策树的情况下确定决策树的最佳深度是相当困难的。稍后修剪树允许算法确定发现了所有重要的数据结构。

C5.0算法的一个好处是，它是关于修剪的看法 - 它使用相当合理的默认值自动处理许多决策。它的总体策略是对树进行后修剪。它首先会生成一个超级训练数据的大树。之后，删除对分类错误影响很小的节点和分支。在某些情况下，整个分支在树上向上移动或由更简单的决策取代。这些移植分支的过程分别称为 子树提升 和 子树替换 。

在过度拟合和欠拟合之间取得适当的平衡是一件艺术，但如果模型准确性至关重要，那么可能需要花一些时间使用各种修剪选项来查看它是否能提高测试数据集的性能。

总而言之，决策树由于其高准确性和用简单语言制定统计模型的能力而被广泛使用。在这里，我们研究了一种非常流行且易于配置的决策树算法C5.0。与其他决策树实现相比，C5.0算法的主要优势在于可以非常轻松地调整训练选项。