不同决策树算法的复杂度和性能比较

Question

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

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

• 性能
• 复杂性
• 决策失误
• 还有更多。

Answer 1

决策树的实现主要是沿着这些轴进行的：

• 分裂准则(即如何计算“方差”)
• 它是否为classification (离散变量，例如类标签)建立了回归(连续变量，例如分数)的模型
• 消除/减少over-fitting的技术
• 是否能够处理不完全数据

主要的决策树实现是：

• ID3 (迭代词典)是Ross开发的三个决策树实现中的第一个( Quinlan，J.R.1986)。决策树的归纳马赫。学习。1，1(1986年3月)，81-106.
• CART，或分类和回归树通常用作决策树一词的通用缩略词，尽管它显然有一个更具体的含义。总之，CART实现非常类似于C4.5；一个显著的区别是CART基于递归地应用于数据的数值分裂准则构造树，而C4.5包含构建_rule set_s的中间步骤。
• C4.5，昆兰的下一次迭代。新的特征(相对于ID3)是：(i)接受连续和离散的特征；(ii)处理不完全的数据点；(iii)通过(非常聪明的)自下而上的技术(通常称为“剪枝”)解决过度拟合问题；(iv)不同的权重可以应用于构成训练数据的特征。其中，前三个是非常重要的--我建议你选择的任何DT实现都有三个。第四项(差别加权)则不那么重要。
• C5.0，最近的Quinlan迭代。这种实现是由专利覆盖的，因此很可能很少实现(商业软件包之外)。我本人从未编写过C5.0实现(我甚至从未见过源代码)，因此我无法提供C5.0与C4.5之间的明达比较。我一直怀疑它的发明者(罗斯·昆兰)声称的改进--例如，他声称它比C4.5快几个数量级“。其他声明也同样广泛(“显着地提高了内存效率”)等等。我将向您指出研究，它报告了两种技术的比较结果，您可以自己决定。
• CHAID (卡方自动交互检测器)实际上比最初的ID3实现早了六年(1980年发表在戈登·卡斯的博士论文中)。我知道这个technique.The R平台有一个名为查德的包，其中包含了优秀的文档
• MARS (多元自适应回归样条)实际上是由火星的最初发明者萨尔福德系统注册的一个术语。因此，Salford没有出售的图书馆中的MARS克隆被命名为火星以外的东西--例如，在R中，相关函数是多样条库中的polymars。Matlab和Statistica也有火星功能的实现。

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

C4.5是在桔黄色的中实现的决策树风格；CART是雪橇中的风格--这两种都是优秀的ML库中的优秀实现。

C4.5是ID3之外的一个重要步骤--在范围方面(C4.5具有更广泛的用例谱，因为它可以处理培训数据中的连续变量)和模型质量。

也许C5.0相对于C4.5最重要的改进是对增强的trees的支持。对DTs的集成支持--增强树和随机森林--已经包含在Orange的DT实现中；这里，集成支持被添加到C4.5算法中。滑雪板还具有一系列随机森林和增强方法。