r - 有人可以解释一下 ID3 和 CART 算法之间的区别吗？

Question

我必须使用 R 软件和 rpart 包创建决策树。在我的论文中，我应该首先定义 ID3 算法，然后实现各种决策树。

我发现 rpart 包不适用于 ID3 算法。它使用 CART 算法。我想了解其中的差异，并可能在我的论文中解释差异，但我没有找到任何比较双方的文献。

你能帮助我吗？你知道一篇比较两者的论文吗，或者你能向我解释一下区别吗？

Answer 1

我无法访问原始文本^1,2但使用一些辅助资源，这些递归（“贪婪”）分区（“树”）算法之间的主要区别似乎是：

1. 学习类型：

   • ID3，作为“迭代二分法”，仅用于二元分类
   • CART 或“分类和回归树”是一系列算法（包括但不限于二分类树学习）。使用rpart()，您可以指定method='class'或method='anova'，但rpart可以从因变量的类型（即因子或数值）推断出这一点。

2. 用于分割选择的损失函数。

   • 正如其他评论所提到的，ID3 根据信息增益选择其拆分，这是父节点和子节点（加权和）之间熵的减少。
   • CART 用于分类时，选择其拆分以实现最小化Gini 杂质的子集

有趣的是，作为一名从业者，我几乎从没听说过使用 ID3 一词，而 CART 经常被用作决策树的一个包罗万象的术语。CART 在 R 的rpart包中有一个非常流行的实现。 ?rpart注意到“在大多数细节上，它非常接近 Breiman 等人 (1984)。”

但是，您可以通过rpart(..., parms=list(split='information'))覆盖默认行为并拆分信息增益。

¹ Quinlan, JR 1986。决策树的归纳。马赫 学。1, 1 (1986 年 3 月), 81–106

²布雷曼，里奥；弗里德曼，JH；奥尔森，RA；斯通，CJ（1984 年）。分类和回归树。加利福尼亚州蒙特雷：Wadsworth & Brooks/Cole Advanced Books & Software。

Answer 2

http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf

阅读本文的1 C4.5 及以上内容，它将澄清您的所有疑问，帮助我解决我的问题。不要被标题气馁，它是关于不同树算法的差异。无论如何都是一篇值得阅读的好论文