9.3 PRIM（耐心规则归纳方法）：凸块搜索

树结构模型（在回归问题中）将特征空间分割成块状的区域（下称为“方块”），并使不同方块中输出变量的平均值差异尽可能大。定义了区域的分割规则彼此之间构成了二叉树的结构，因而易于理解预测的规则。

耐心规则归纳方法（The patient rule induction method，PRIM） 同样是在特征空间中查找方块，但寻找的是输出变量的平均值最高的方块。因此它是寻找目标函数的最大值区域，这种操作称为 凸块搜索（bump hunting）。（如果需要寻找最小值而不是最大值，可以简单地将输出变量加上负号。）

PRIM 与树结构分割方法的另一个不同是方块的定义无法用二叉树表示。这样会更难以解释一组分割规则；然而去除了二叉树的约束后，个体的规则通常会更简单。

PRIM 中主要的方块构建是自上而下的，从一个包含所有数据的方块开始。将方块沿着某个表面的方向进行少量的收缩，然后去除落在收缩后的方块外的观测样本。收缩所选的表面，是沿其收缩后得到的方块内平均值最大的一个表面。然后重复这个过程，直到当前的方块包含了某个最小数量的样本点。

**图 9.7**：PRIM 算法的演示。其中有两个类别，被表示为蓝色（类别 0）和红色（类别 1）的点。过程从一个包含了所有数据的长方形开始（黑色虚线），然后沿着某个边以一个预设的程度压缩区域并剥离数据，而使留在方块中点的平均值最大。从左上图开始，展示了依次剥离过程的序列，直到最后在右下图中分离出了全为红色点的区域。每个图的上方标记了循环的过程序号。

图 9.7 展示了这个过程。这里有均匀分布在单位正方形区域上的 200 个数据点。红色的点代表了在 $0.5<X_1<0.8$ 和 $0.4<X_2<0.6$ 上输出变量 $Y$ 取值为 1 的样本；蓝色的点代表了其他区域输出为 0 的样本。一系列散点图展示了自上而下的剥离过程依次产生的方块，在每一步骤剥离掉现有数据点的一个固定比例 $\alpha=0.1$。

图 9.8 展示了随着方块的逐步压缩，其中的输出变量的平均值。

在自上而下地计算了方块序列后，PRIM 反向进行这个过程，沿这任意可以增加方块内的均值的表面方向扩展。这被称为 贴入（pasting）。由于自上而下的过程是在每一步的贪心算法，所以通常可能存在这种扩展。

经过这些步骤后得到了一序列的方块，每个块中都有不同数量的样本。然后通过交叉验证以及分析人员的判断，选择最优的方块大小。

将步骤 1 中找到的方块中的样本集合记为 $B_1$。然后 PRIM 过程从训练集中排除 $B_1$ 中的观测样本，并对剩余的数据集重复进行两步骤过程——自上而下的剥离样本，然后自下而上的贴入样本。重复这个过程若干次，得到一个方块的序列：$B_1$， $B_2$，……，$B_k$。每个方块由一组与部分自变量相关的规则所定义，比如：

$$\begin{align} & (a_1 \leq X_1 \leq b_1) \\ & (b_1 \leq X_3 \leq b_2) \end{align}$$

算法 9.3 概括了 PRIM 过程。

算法 9.3： PRIM（耐心规则归纳方法）

自所有的训练数据以及包含所有数据的方块开始。
将这个方块在某个平面上压缩，从而剥离掉某个自变量 $X_j$ 取值最大或最小的 $\alpha$ 比例的样本。选择其中使剩余在方块中的样本均值最大的剥离方向。（通常 $\alpha=0.05$ 或 $0.10$。）
重复步骤 2，直到方块中只剩某个很少数量的样本（比如 10 个）。
将得到的方块沿着任意可增加方块内样本均值的方向扩展。
步骤 1-4 给出一个方块的序列，每个方块中有不同数量的样本。用交叉验证来选择序列中的某一个，记为方块 $B_1$。
从数据集中排除方块 $B_1$ 中的数据，并重复步骤 2-5 来获得第二个方块，然后持续进行这个过程，得到期望个数的方块。

与 CART 一样，对分类自变量 PRIM 可以考虑其取值的所有分割方式。对缺失值的处理方式也与 CART 类似。PRIM 适用于（量化输出变量）回归问题；也可简单地通过编码 0 和 1 的方式处理二分类的输出变量。但并没有 $k>2$ 个类别的简单处理方法：一种方法是为每个类别对一个基准类型分别应用 PRIM 过程。

PRIM 对 CART 的一个优势是它的耐心（patience）。由于其二叉分割，CART 会很快地将数据碎片化。假设进行等大小的二叉分割，那么 $N$ 个观测样本只能经受 $\log_2(N)-1$ 次分割而若 PRIM 在每一步剥离 $\alpha$ 比例的训练样本点，那么它在耗尽数据前可进行大约 $-\log(N)/\log(1-\alpha)$ 次剥离。例如，若有 $N=128$ 和 $\alpha=0.10$，则 $\log_2(N)-6=6$ 而 $-\log(N)/\log(1-\alpha)=46$。考虑到每个阶段中的样本个数必须为整数，PRIM 实际上只能剥离 29 次。在任意的场景中，PRIM 更耐心的特性可能有助于自上而下的贪心算法找到更好的解。

9.3.1 垃圾邮件例子（续）

在“垃圾邮件”数据上应用 PRIM 方法，其中的输出变量取值“垃圾邮件”编码为 1，“正常邮件”编码为 0。

PRIM 找到的前连个方块列举如下：

规则 1	全局均值	方块均值	方块支撑
训练集	0.3931	0.9607	0.1413
测试集	0.3958	1.0000	0.1536

$$\text{规则 1} \begin{cases} \text{ch!} &> 0.029 \\ \text{CAPAVE} &> 2.331 \\ \text{your} &> 0.705 \\ \text{1999} &< 0.040 \\ \text{CAPTOT} &> 79.50 \\ \text{edu} &< 0.070 \\ \text{re} &< 0.535 \\ \text{ch;} &< 0.030 \end{cases}$$

规则 2	剩余样本均值	方块均值	方块支撑
训练集	0.2998	0.9560	0.1043
测试集	0.2862	0.9264	0.1061

$$\text{规则 2} \begin{cases} \text{remove} &> 0.010 \\ \text{george} &< 0.110 \end{cases}$$

方块支撑为方块包含的观测样本比例。第一个方块包含了 15% 的测试样本，并且全都是垃圾邮件。第二个方块包含了 10.6% 的测试样本，其中的 92.6% 为垃圾邮件。两个方块共同包含了 26% 的数据，并且其中的大约 97% 为垃圾邮件。接下来的几个方块（没有列出）比较小，只包含了大约 3% 的数据。

列出的自变量按重要性排序。有趣的是 CART 树模型中顶层的几个分割变量（见图 9.5）并没有出现在 PRIM 的第一个方块规则中。