当在一个高维的特征空间上应用最近邻分类模型，某个点的最近邻可能非常远，导致偏差较大而且分类规则的效果变差。
为了进一步说明这个问题，假设 $N$ 个数据典均匀分布在单位立方体 $[-\frac{1}{2},\frac{1}{2}]^p$ 之中。令 $R$ 为原点的 1 最近邻的半径范围。那么：
$$\operatorname{median}(R) = v_p^{-1/p} \left( 1-\frac{1}{2}^{1/N} \right)^{1/p} \tag{13.7}$$$v_pr^p$ 即为半径为 $r$ 的 $p$ 维球体的体积。图 13.12 展示了不同训练样本量和维度下的半径中位数。可见半径中位数快速地靠近 0.5，也就是距离立方体边缘的距离。
那么要如何应对这个问题？比如在如图 13.13 中二分类的场景中，这里有两个特征变量，图中圆形区域为某个待分类点的一个最近邻域。在最近邻分类方法中隐含的假设是在一个邻域中类别的概率大致是固定的，因此简单取平均就给出很好的估计。然而在这个例子里，类别的概率只在水平方向才有变动。若已知这个信息，我们可以在垂直方向拉伸这个邻域，就如图中的细长的长方形区域。这将会降低估计的偏差而保持方差不变。
一般来说，这就需要调整最近邻分类方法中使用的距离测度，从而使得到的邻域在类别概率变化不大的方向上尽可能拉长。在高维特征空间中，类别概率可能只会在一个低维子空间上变动，所以调整距离测度可能带来相当大的好处。
Friedman (1994a) 提出了一个方法，通过将一个包含着样本的“盒体”中逐步地切除边角而自适应地获得正方体邻域。本节我们将介绍 Hastie and Tibshirani (1996a) 提出的 判别自适应最近邻（discriminant adaptive nearest-neighbor，DANN） 规则。在之前，Short and Fukunaga (1981) 和 Myles and Hand (1990) 也提出过类似的方法。
在每个待分类点处，构建一个邻域，比如取 50 个点，然后根据这些点上类别的分布来决定如何重塑邻域，也就是要调整距离测度。然后使用这个调整后的距离测度在这个点应用最近邻。所以对于不同的待分类点，使用的距离测度可能并不相同。
图 13.13 中可见，应将邻域沿着与类别中心点连接线正交（垂直）的方向进行拉伸。这个方向与线性判别边界是一致的，并且这是类别概率变动最小的方向。一般来说，这个变动最小方向并不一定是与类别中心点连接线正交的方向（参考图 4.9）。不过可假设这是一个局部判别模型，决定邻域最优形状只需要用到局部类别内部和类别之间的协方差矩阵所携带的信息。
某个待分类点 $x_0$ 处的 判别自适应最近邻（DANN） 距离度量定义为：
$$D(x, x_0) = (x - x_0)^T \mathbf{\Sigma} (x - x_0) \tag{13.8}$$其中的：
$$\begin{align} \mathbf{\Sigma} &= \mathbf{W}^{-1/2} [\mathbf{W}^{-1/2}\mathbf{B}\mathbf{W}^{-1/2} + \epsilon\mathbf{I}] \mathbf{W}^{-1/2} \\ &= \mathbf{W}^{-1/2} [\mathbf{B}^* + \epsilon\mathbf{I}] \mathbf{W}^{-1/2} \tag{13.9}\end{align}$$这里的 $\mathbf{W}$ 为类别内部混合（pooled）协方差矩阵 $\sum_{k=1}^K\pi_k\mathbf{W}_k$，而 $\mathbf{B}$ 为类别之间协方差矩阵 $\sum_{k=1}^K(\bar{x}_k-\bar{x})(\bar{x}_k-\bar{x})^T$，在 $\mathbf{W}$ 和 $\mathbf{B}$ 的计算中只用到了 $x_0$ 的 50 个最近邻点。计算出距离测度后，在用这个测度对 $x_0$ 使用最近邻规则。
实际上这个复杂的公式在操作中却非常简单。首先基于 $\mathbf{W}$ 矩阵获取圆形区域的样本，然后向 $\mathbf{B}^*$（原型区域样本的类别之间协方差矩阵）零特征值方向拉伸这个区域。之所以这样做，是因为从局部看在这些方向上移动类别的平均比例没有变化。参数 $\epsilon$ 将这个邻域从一个无限长的带状限制为一个椭圆，从而避免使用到距离待分类点非常远的样本。一般令 $\epsilon=1$ 就可以有很好的效果。
图 13.14 展示了两个同心圆形状的类别中得到的一些邻域。注意到当邻域中同时存在两个类别时，邻域向判别边界的方向产生了拉伸。在只有一个类别的区域，邻域仍然是正圆形；在这些邻域中，类别间协方差矩阵 $\mathbf{B}=0$，式 13.8 中的 $\mathbf{\Sigma}$ 为单位矩阵。
13.4.1 示例
与图 13.14 中的二维例子类似地，我们在十维空间生成了两个类别的数据。类别 1 的所有十个自变量是独立的标准正态分布，概率条件为总的半径平方大于 22.4 并小于 40；而类别 2 的自变量也是独立的标准正态分布，不过没有任何约束条件。每个类别有 250 个观测样本。因此，在十维的空间上第一个类别几乎总是包围着第二个类别。
最近邻中的子集选择规则可以去除无作用的纯干扰变量，但在这个例子中并不存在这样的干扰变量。在特征空间上的任意点处，只在一个方向上存在类别的区分。但是特征空间不同位置上的这个方向都不相同，所以所有的特征变量都会在空间中的某个位置会对模型起作用。
图 13.15 展示了十次实现测试误差率的箱线图，包括了普通的 5 最近邻、学习向量量化（LVQ）、判别自适应 5 最近邻。我们在 LVQ 中每个类别使用了 50 个原型，使它与 5 近邻有可比性（因为 $250/5=50$）。与 LVQ 和普通最近邻相比，自适应的距离测度显著地降低了错误率。
13.4.2 最近邻的全局降维
判别自适应最近邻方法是在局部进行降维，即在在每个待分类点处分别进行降维。在一些问题中，我们也可以进行全局降维，即原特征空间中的某个最佳子空间上使用最近邻方法。例如假设在一个四维的特征空间上有两个呈嵌套球形的类别，并且另外有六个噪声特征变量，它们的分布与类别不相关。那么我们希望能够发现这个有价值的四维子空间，然后在降维的子空间中使用最近邻分类模型。Hastie and Tibshirani (1996a) 介绍了一些解决这个问题的判别自适应最近邻方法。在每个训练样本点 $x_i$ 处，j，计算（局部邻域上的）类别之间平方和矩阵1 $\mathbf{B}_i$，然后在所有训练集上对这些矩阵做平均：
$$\bar{\mathbf{B}} = \frac{1}{N} \sum_{i=1}^N \mathbf{B}_i \tag{13.10}$$令 $e_1,e_2,\dots,e_p$ 为矩阵 $\mathbf{B}$ 的特征向量，按特征值 $\theta_k$ 从大到小排列。那么这些特征向量就张成（span）了全局降维后的最优子空间。这个结论的推导是基于：$\bar{\mathbf{B}}$ 的最优秩 L 近似 $\bar{\mathbf{B}}_{[L]}=\sum_{\ell=1}^L\theta_\ell e_\ell e_\ell^T$，是下面这个最小二乘问题的解：
$$\min_{\operatorname{rank}(\mathbf{M})=L} \sum_{i=1}^N \operatorname{trace}[(\mathbf{B}_i - \mathbf{M})^2] \tag{13.11}$$每个 $\mathbf{B}_i$ 包含了局部判别子空间和在这个子空间上判别强度的信息，所以式 13.11 可理解为是用加权最小二乘法为一系列 $N$ 维子空间寻找 $L$ 维度的最优近似子空间（练习 13.5）。
在上面介绍的 Hastie and Tibshirani (1996a) 中讨论的四维球形例子中，有四个较大的特征值 $\theta_\ell$（相应的特征向量就基本张成了原来的核心子空间），而其他六个特征值接近于零。在实际操作中，我们将数据投射到前四个特征向量的四维子空间上，然后使用最近邻分类方法。在[第 13.3.2 节]中的卫星图片分类示例中，图 13.8 中标记为“DANN”的方法就是在全局降维空间上的 5 最近邻。这个方法也与 Duan and Li (1991) 提出的 切片逆回归（sliced inverse regression） 方法有一些关联。他们在回归问题中应用了相似的思路，但不是在局部而是在全局进行计算。他们利用了特征变量分布的球形对称性假设来估计这个子空间。
本节练习
练习 13.2
推导 1 最近邻的半径中位数公式 13.7。
练习 13.5
-
原文中矩阵的描述为“the between-centroids sum of squares matrix”，可参考 R 中
fpc::ncoord函数代码。 ↩︎