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

Question

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

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

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

Answer 1

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

学习类型:

ID3 ，作为“迭代二分法”，适用于 仅二进制分类

CART 或“分类 和 回归树”是一系列算法(包括但不限于二分类树学习)。与 rpart() ，您可以指定 method='class'或 method='anova' ，但是 rpart可以从因变量的类型(即因子或数字)推断出这一点。

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

ID3，正如其他评论所提到的，根据信息增益选择它的 split ，这是entropy 的减少。在父节点和(加权和)子节点之间。

CART，当用于分类时，选择它的 split 来实现最小化Gini impurity的子集。

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

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

1 Quinlan, J. R. 1986。决策树的归纳。马赫。学习。 1, 1 (1986 年 3 月), 81–106

2 布雷曼，利奥；弗里德曼，J.H.；奥尔申，R.A.；斯通，C. J. (1984)。分类和回归树。加利福尼亚州蒙特雷:Wadsworth & Brooks/Cole Advanced Books & Software。