CART算法(分类和回归树)问题

Question

1. 采用CART算法对给定深度k的完全分类树模型D3进行拟合，并通过查找E(k, \alpha) = min_{T\subset Tk} Err(T) + \alpha |T|对树进行剪枝。这里，Err(T)是树T对训练数据的训练误差，|T|是T中的叶数，\alpha是给定的参数。下面哪个是sometimes false？

\color{blue}{(a) E(k+ 1,0) \geq E (k,0)}

(b) E(k+ 1,0) \leq E(k,0)

(c) E(k+ \alpha+1) \geq E(k,\alpha)

(d)上述三种说法都是正确的

\color{blue}{Explanation:}通过提供深度k和k + 1，Cart算法将返回给我们一个深度k, T,树和一个深度k + 1, \widetilde {T}树。需要注意的是，T和\widetilde {T}共享相同的第一个k - 1 级别。

现在，剪枝开始了，T的任何可能的剪枝都可以通过剪枝\widetilde {T}来实现，反之亦然。因此，E(k, \alpha) \geq E(k + 1, \alpha)中的任何$\alpha \in R_+.$$参见第7课。

这是我刚做过的一次考试。我想知道是否有类似于图像中的实例，CART算法可以使用负alpha从而鼓励更大的树？还是算法声明alpha在任何时候都必须是非负整数？

Answer 1

进行额外的分割总是会减少Err (直到达到纯叶子)，因此任何负\alpha都会与\alpha=0一样最小化T。所以我们还是用\alpha\geq0吧。(但不要求\alpha是整数。)

Erm，除非您实现了这样的东西，即使是一个纯节点也可以被分割，在这种情况下，负的\alpha会使树甚至被分割，直到每一片叶子都由一个样本(及其副本)组成，或者达到最大深度。

Answer 2

还是算法声明alpha在任何时候都必须是非负整数？

据我所知，实际情况如下：

在第308页的“统计学习要素”(1)中，作者写道：

调优参数\alpha \geq 0控制树大小与其适合数据的优度之间的权衡。

此外，科学知识-学习文档说：

最小成本-复杂度剪枝是一种用于修剪树以避免过度拟合的算法，在第三章中对此进行了描述。该算法被称为复杂性参数的\alpha \geq 0参数化。

这两个来源都以“分类和回归树”(2)为原始来源。

(1)“统计学习的要素”；Hastie等人；第二版；2008年

(2)“分类和回归树”；Breiman，等人；1984年

Answer 3

是一个用于正则化的参数，它控制树不被过度匹配，这是CART算法的一个固有问题。负面影响会导致一棵更大的树，这可能会加剧过度适应的问题。