performance - 不同决策树算法的复杂度或性能比较

Question

我正在研究数据挖掘，更准确地说，是决策树。

我想知道是否有多种算法来构建决策树(还是只有一种？)，基于以下标准，哪个更好？

业绩

复杂性

决策失误

和更多。

Answer 1

决策树的实现主要在这些轴上有所不同:

split 准则 (即，如何计算“方差”)

是否为建模型回归 (连续变量，例如，a
得分)以及 分类 (离散变量，例如一个类
标签)

消除/减少技术过拟合

是否可以处理数据不完整

主要的决策树实现是:

ID3 ，或迭代二分器，是三个决策树中的第一个
由 Ross Quinlan 开发的实现 (Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81-106.)

购物车 ，或分类和回归树通常用作通用
术语决策树的首字母缩写词，尽管它显然具有更具体的含义。总之，CART 实现与 C4.5 非常相似；一个显着的区别是 CART 基于递归应用于数据的数值分割标准来构建树，而 C4.5 包括构建规则集的中间步骤。

C4.5 ，昆兰的下一次迭代。新功能(相对于 ID3)是:
(i) 接受连续和离散特征； (ii) 处理
不完整的数据点； (iii) 通过(非常
聪明)自下而上的技术，通常被称为“修剪”； (iv)
可以应用不同的权重组成的特征
训练数据。其中，前三个非常重要——我建议您选择的任何 DT 实现都具有这三个。第四个(不同的权重)不太重要

C5.0 ，最近的 Quinlan 迭代。这个实现是
受专利保护，因此可能很少实现
(商业软件包之外)。我从未编码过 C5.0
自己实现(我什至从未见过源代码)所以我无法提供 C5.0 与 C4.5 的明智比较。我一直
对其发明者声称的改进持怀疑态度 (Ross
Quinlan)——例如，他声称这是“几个数量级”
比 C4.5 快。其他声明也同样广泛(“显着提高了内存效率”)等等。我会告诉你studies
其中报告了两种技术的比较结果，您可以自己决定。

柴德 (卡方自动交互检测器)实际上早于
将最初的 ID3 实现提前了大约 6 年(发布于
博士Gordon Kass 于 1980 年发表的论文)。我对这种技术一无所知。R 平台有一个名为 CHAID 的包。哪一个
包括优秀的文档

火星 (多自适应回归样条)实际上是 MARS 的原始发明者 Salford Systems 注册的一个术语。作为一个
结果，Salford 未出售的库中的 MARS 克隆被命名为 MARS 以外的名称——例如，在 R 中，相关函数是 poly-spline 库中的 polymars。 Matlab 和 Statistica 也有
具有 MARS 功能的实现

我会推荐 CART 或 C4.5(虽然我对 C5.0 或 CHAID 没有直接经验，但我熟悉它们的功能集)。

C4.5 是在 Orange 中实现的决策树风格; CART 是 sklearn 中的味道-- 优秀的机器学习库中的优秀实现。

C4.5 是超越 ID3 的重要一步——无论是在范围(C4.5 具有更广泛的用例范围，因为它可以处理训练数据中的连续变量)和模型质量方面。

也许 C5.0 与 C4.5 相比最显着的改进是对 的支持。提升树 .对 DT 的集成支持——增强树和随机森林——已包含在 Orange 的 DT 实现中；在这里，集成支持被添加到 C4.5 算法中。 sklearn 还具有一系列随机森林和增强方法。