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

Question

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

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

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

Answer 1

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

学习类型：
- ID3作为“迭代二分法”，仅用于二元分类
- CART，或“分类和回归树”，是一系列算法（包括但不限于二分类树学习）。使用rpart()，您可以指定method='class'或method='anova'，但rpart可以从因变量的类型（即因子或数字）推断出这一点。
用于分割选择的损失函数。
- 正如其他评论所提到的，ID3 根据信息增益选择其分裂，这是父节点和子节点（的加权总和）之间熵的减少。
- CART，当用于分类时，选择它的分裂来实现最小化基尼杂质的子集

有趣的是，作为一名从业者，我几乎从未听说过使用 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

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