Classification and Regression Trees

1. Prediction Trees

线性回归和多项式回归都是global model，然而数据的每个维度之间存在非线性的复杂的关系，如果假设它是一个简单的global model的话，是不合理的。一些非参数的滤波器尝试局部地拟合模型，然后将它们组合在一起，但是这样很难解释。

另一个非线性回归的思路是，将空间分为小的区域，这些小区域里的特征之间的相互影响更可控。递归地，更小的区域也是一样。直到得到一些小块的空间，我们能用简单的模型去拟合（模型树）。

以上递归划分的过程可以用二叉树的结构表示，每个叶子节点表示一个划分块，这个划分块有一个简单的模型（simple local model）。对于经典的回归树而言，小块的模型是一个常数值。预测值就是块中各个数据的label的均值：$\hat y = {1 \over c} {\sum_{i=1}^c y_i}$，这样做由以下几点好处：

• 计算速度快
• 很容易知道那个变量更重要
• 当有些维度的数据丢失时，我们依然可以通过平均子树的label来做预测，而不需要从上到下走到叶子节点。
• 模型能给一个锯齿状的响应（The model gives a jagged response, so it can work when the true regression surface is not smooth. If it is smooth, though, the piecewise-constant surface can approximate it arbitrarily closely (with enough leaves)）
• 有可行、快速的算法去求解

A last analogy before we go into some of the mechanics. One of the most comprehensible non-parametric methods is k-nearest-neighbors: find the points which are most similar to you, and do what, on average, they do. There are two big drawbacks to it: first, you’re defining “similar” entirely in terms of the inputs, not the response; second, k is constant everywhere, when some points just might have more very-similar neighbors than others. Trees get around both problems: leaves correspond to regions of the input space (a neighborhood), but one where the responses are similar, as well as the inputs being nearby; and their size can vary arbitrarily. Prediction trees are adaptive nearest-neighbor methods.

2. Regression Trees

在聚类中，我们希望最大化$I[C;X]$，特征关于聚类的信息。在回归树中，我们希望最大化$I[C;Y]$，Y表示响应(label)，C表示叶子节点。同样地，我们无法直接最大化，只能贪婪搜索。我们从二分问题开始，将根节点分为两部分，然后递归地进行划分。

停止准则(stopping criterion)。什么时候停止划分？显然，只有一个点的结点不可划分，但是这样不具有推广性。一个更典型的准则是：(1)当一个结点具有少于5个数据点时，停止划分；(2)如果划分增加的信息量低于某个阈值时，停止划分。

用最小二乘误差来衡量树的信息量：

其中$m_c = {1\over n_c}\sum_{i \in c}y_i$，叶节点c的预测值。

基本的树生长算法如下：

1. 从所有根节点开始，计算$m_c$和$S$；
2. 如果该结点中的所有点都一样，则停止。否则，遍历所有可能的二元化分，找到使得$S$降低最多的那种划分。如果该划分同时不满足停止准则，则应用该划分，得到两个新的节点。
3. 对于一个新的结点，返回第一步。

为了树过拟合，可以采用剪枝策略（后剪枝）:

基于交叉验证的剪枝：对于一对叶子节点，计算$S$，然后计算合并这对叶子结点后的$S$。如果$S$减小，则剪枝，合并这对叶子节点。

将数据分为50%的训练集和50%的测试集，然后交替进行生长和剪枝。用第一部分来生长树，第二部分进行剪枝；然后利用第二部分来生生长树，第一部分来剪枝；......交替进行，直到树的大小不变。

3. Classification Trees

分类树的生长和剪枝与回归树一样。不同的是，分类树输出的是数据的类别。

分类时，一个样本$X$进来，从树根开始，从上到下，落到$k$个不相交的区块($A_1,A_2,...,A_k$)中的一个。如果$X$落到在$A_j$中，则$Y$的类别为$j$。如下图所示，一个数据[-6,6]落到了左上角的一块区域，则分为第2左上角那一块的类别。而这一块中有4个样本属于第2类，有1个样本属于第1类，则最终[-6,6]属于第2类，并且概率为0.80。

不同的是：

• 怎么度量信息
• 树给出的预测是什么样的
• 怎么度量预测误差

3.1 度量信息

响应变量$Y$是一个“类别”，我们可以用信息论来度量我们能从一个离散变量$A$中知道多少信息：

其中，$I[Y;A=a] = H[Y] - H[Y|A=a]$，$H[Y]$为熵，$H[Y|A=a]$为条件熵。

$H[Y;A=a]$表示知道$A=a$之后，$Y$的不确定性减少了多少。

$I[Y;A]$表示知道$A$的值之后，$Y$的不确定性减少了多少。

对于分类树而言，$A$不是一个预测器，而是需要预测的值，一般是二值，

3.2如何做出预测

预测包括两部分：（1）输出其属于哪一类；（2）属于这一类的概率。

3.3度量误差

有三种方法来度量误差：错误率、期望损失(expected loss)和normalized negative log-likelihood，如交叉熵。

3.3.1错误率(Misclassification Rate)

不解释。

3.3.2平均损失(Average Loss)

3.3.3似然和交叉熵(Likelihood and Cross-Entropy)

3.3.4Neyman-Pearson Approach