Regression Tree (VS Linear Regression)

Regression Tree 模型相比 Linear Regression 模型有何优势呢？

Linear Regression 是最经典的回归模型，可用下式表示：

$Y = β_0 + β^T X + ε$

然而 Linear Regression 的假设很强，即各特征（ $X_1,X_2,\dots$ ）是独立的，而实际中各特征是相互影响的，我们可以通过加入高次项来考虑这些特征间的相互作用，如：

$Y = β_0 + β^T X + γXX^T + ε$

可以看到，即使只考虑特征俩俩之间的交互，模型参数的数量都会随特征数量的增加而快速增加，这将大大增加模型训练的难度。

归根结底，Linear Regression 无法很好的处理特征之间的相互影响的原因在于它是一个全局模型（global model），用一个单一的预测公式适用于整个数据空间。当数据具有许多以复杂的、非线性的方式交互的特性时，建立一个单一的全局模型可能会非常困难。

一种处理非线性回归的方法是将特征空间细分或划分为更小的区域，在这些区域中，特征间的相互作用更易于管理。然后我们再次划分这些子分区——这称为递归分区——直到最后我们得到一系列小的空间块，这些块中的样本可以用简单模型拟合。因此，我们的算法分为两部分：一部分是递归分区，另一部分是建立各分区中的简单模型。

Prediction Tree 使用树来表示递归分区。树的每个终端节点或叶节点表示分区的一个单元，并附加一个简单的模型，该模型仅适用于该单元。如果 $x$ 落在分区的相应单元中，则点 $x$ 属于叶结点。为了确定我们在哪个单元中，我们从树的根节点开始，并询问一系列关于特征的问题。

经典的 Regression Tree 算法中，每个单元中的模型只是一个常数估计，即属于当前单元（结点）的样本的 $y$ 的均值。因此这相当于一个分段常数模型。这样做有几个好处：

预测很快(不需要复杂的计算，只需查找树中的常数即可)
很容易理解哪些特征在进行预测时很重要
如果一些数据丢失了，我们可能无法一直向下到达树的叶子，但我们仍然可以通过平均我们已到达结点的子树中的所有叶子来进行预测
模型给出了一个锯齿状的响应，所以它可以在真实的回归曲面不光滑时仍能较好拟合。如果真实模型是光滑的，则分段常数曲面可以任意接近它(只要有足够的叶节点)
有快速、可靠的算法来学习这些树

Regression Tree 运行后产生的结果大致长这样：

可以看到，一旦分区确定，各分区上的模型也就确定了（只是简单取平均），因此关键的部分在于如何建立一棵树来产生好的分区。

关于如何建树，我们可以定义损失函数为平方损失：

$S=\sum_{c \in \text { leaves }(T)} \sum_{i \in C}\left(y_{i}-m_{c}\right)^{2}$

其中 $m_c=\frac{1}{n_c}\sum_{i\in C}y_i$ 。

然后按如下步骤建树：

（1）从包含所有点的单个节点开始。计算 $m_c$ 和 $S$ 。
（2）如果结点中的所有样本的 $y$ 都相等，则停止。否则，在所有特征的二分中搜索一个能尽可能减少 $S$ 的。如果最大的减少量小于某个阈值 $δ$ ，或产生的结点将包含一个小于 $q$ 个样本点，停止。否则，使用该拆分，创建两个新节点。
（3）在每个新结点中，重复上述步骤。

这个简单算法的一个问题是，它可能过早地停止。有些变量本身并不能提供很多信息，但却导致了信息丰富的后续拆分。

寻找回归树的一个更成功的方法是使用交叉验证思想。我们将数据随机分为一个训练集和一个验证集，然后我们将基本树算法应用于训练集，并设定 $q = 1$ 和 $δ=0$ ——也就是说，我们生成最大的树。这通常会导致过拟合。然后我们使用交叉验证来剪枝。在每一对具有共同父节点的叶节点上，我们对验证集的误差进行评估，看看去除这两个节点并使它们的父节点成为叶节点是否会使平方损失更小。重复此操作，直到剪枝不再改善验证集上的表现。

Reference：
CMU Data Mining

最后编辑于：2019.11.12 15:15:04