不同的决策树算法,比较复杂性或性能

Question

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

我想知道是否有多种算法来构建决策树(或只有一个？),哪个更好,基于诸如

• 性能
• 复杂
• 决策失误
• 和更多.

Answer 1

决策树实现主要沿着这些轴不同:

• 在拆分标准(即如何"方差"的计算)

• 是否构建回归模型(连续变量,例如分数)以及分类(离散变量,例如类标签)

• 消除/减少过度拟合的技术

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

主要的决策树实现是:

• ID3或Iterative Dichotomizer是Ross Quinlan开发的三个决策树实现中的第一个(Quinlan,JR,1986.决策树的归纳.Mach.Learn.1,1(1986年3月),81-106.)

• CART或分类和回归树通常用作术语决策树的通用首字母缩略词,尽管它显然具有更具体的含义.总之,CART实现与C4.5非常相似; 一个值得注意的差异是CART基于递归地应用于数据的数值分裂标准构造树,而C4.5包括构造规则集的中间步骤.

• C4.5,Quinlan的下一次迭代.新功能(与ID3相比)是:(i)接受连续和离散功能; (ii)处理不完整的数据点; (iii)通过(非常聪明的)自下而上的技术解决过度拟合的问题,通常称为"修剪"; (iv)可以应用包括训练数据的特征的不同权重.其中,前三个非常重要 - 我建议你选择的任何DT实现都有三个.第四个(差分加权)不太重要

• C5.0,最新的Quinlan迭代.该实现由专利涵盖,因此可能很少实现(在商业软件包之外).我自己从未编写过C5.0实现(我从未见过源代码)所以我无法提供C5.0与C4.5的明智比较.我一直对其发明者(Ross Quinlan)声称的改进持怀疑态度 - 例如,他声称它比C4.5快了几个数量级.其他声明同样广泛("显着更高的存储效率")等等.我只想指出 哪些研究报告了这两种技术的比较结果,你可以自己决定.

• CHAID(卡方自动交互检测器)实际上比原始ID3实现早了大约六年(由Gordon Kass在1980年的博士论文中发表).我对这项技术知之甚少.R平台有一个名为CHAID的包,其中包含优秀的文档

• MARS(多自适应回归样条)实际上是由索尔福德系统公司MARS的原始发明人注册的一个术语.因此,Salford未出售的库中的MARS克隆被命名为MARS之外的其他东西 - 例如,在R中,相关函数是多样条库中的polymars.Matlab和Statistica也有MARS功能的实现

我会推荐CART或C4.5(虽然我没有使用C5.0或CHAID的直接经验,但我熟悉他们的功能集).

C4.5是Orange中实现的决策树风格; CART是sklearn的风格 - 在优秀的ML库中都有出色的实现.

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

也许最重要的声称C5.0与C4.5的改进是对增强树木的支持.DT的集合支持 - 提升树木和随机森林 - 已包含在Orange的DT实施中; 这里,集合支持被添加到C4.5算法中.sklearn还提供一系列随机森林和助推方法.