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

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

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

性能

复杂度

决策错误

等。

最佳答案

决策树的实现主要在以下方面有所不同:

划分标准(即“方差”的计算方式)

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

消除/减少过度拟合

的技术

是否可以处理不完整的数据

决策树的主要实现是:

ID3 (或迭代二分器)是三个决策树中的第一个
罗斯·昆兰(Quinlan，J. R. 1986.决策树的归纳。马赫。学习。1，1(1986年3月)，第81-106页)开发的实现。

CART 或“分类和回归树”通常用作通用树
“决策树”一词的首字母缩写词，尽管它显然具有更具体的含义。总而言之，CART实现与C4.5非常相似。一个显着的差异是CART基于递归应用于数据的数值拆分准则构造树，而C4.5包括构造规则集的中间步骤。

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

C5.0 ，最新的Quinlan迭代。该实现是
包含在专利中，因此可能很少实现
(商业软件包之外)。我从未编码过C5.0
我自己实现(我什至从未见过源代码)，所以我无法提供C5.0与C4.5的知情比较。我一直
对其发明者声称的改进持怀疑态度(罗斯
昆兰)-例如，他声称这是“几个数量级”
比C4.5快。其他要求也同样广泛(“显着提高存储效率”)，依此类推。我只将您指向studies
报告两种技术的比较结果，您可以自己决定。

CHAID (卡方自动交互检测器)实际上早于
最初的ID3实现大约需要六年的时间(在
博士Gordon Kass在1980年撰写的论文)。我对此技术一无所知.R平台有一个名为CHAID的软件包
包括出色的文档

MARS (自适应回归样条曲线)实际上是MARS的原始发明者Salford Systems的商标。作为一个
结果，非Salford出售的库中的MARS克隆被命名为MARS以外的其他名称-例如，在R中，相关功能是poly-spline库中的polymars。 Matlab和Statistica也有
MARS功能

实现

我建议使用CART或C4.5(尽管我熟悉C5.0或CHAID的功能集，但我并没有直接的经验)。

C4.5是在Orange中实现的决策树风格； CART是sklearn中的特色-都是出色的ML库中的出色实现。

C4.5在范围(C4.5具有更广泛的用例范围，因为它可以处理训练数据中的连续变量)方面和模型质量方面都超越了ID3-。

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