统计学习方法（第2版）最新章节_李航著

3.2 k 近邻模型

k 近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、 k 值的选择和分类决策规则决定。

3.2.1　模型

k 近邻法中，当训练集、距离度量（如欧氏距离）、 k 值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。这一事实从最近邻算法中可以看得很清楚。

特征空间中，对每个训练实例点 x _i ，距离该点比其他点更近的所有点组成一个区域，叫作单元（cell）。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。最近邻法将实例 x _i 的类 y _i 作为其单元中所有点的类标记（class label）。这样，每个单元的实例点的类别是确定的。图3.1是二维特征空间划分的一个例子。

3.2.2　距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。 k 近邻模型的特征空间一般是 n 维实数向量空间 R ⁿ 。使用的距离是欧氏距离，但也可以是其他距离，如更一般的 L _p 距离（ L _p distance）或Minkowski距离（Minkowski distance）。

设特征空间 X 是 n 维实数向量空间 R ⁿ ， x _i , x _j ∈ X ，，， x _i , x _j 的 L _p 距离定义为

图3.1 k 近邻法的模型对应特征空间的一个划分

这里 p ≥1。当 p =2时，称为欧氏距离（Euclidean distance），即

当 p =1时，称为曼哈顿距离（Manhattan distance），即

当 p = ∞ 时，它是各个坐标距离的最大值，即

图3.2给出了二维空间中 p 取不同值时，与原点的 L _p 距离为1（ L _p =1）的点的图形。

图3.2 L _p 距离间的关系

下面的例子说明，由不同的距离度量所确定的最近邻点是不同的。

例3.1 已知二维空间的3个点 x ₁ =（1,1） ^T ， x ₂ =（5,1） ^T ， x ₃ =（4,4） ^T ，试求在 p 取不同值时， L _p 距离下 x ₁ 的最近邻点。

解因为 x ₁ 和 x ₂ 只有第一维的值不同，所以 p 为任何值时， L _p （ x ₁ , x ₂ ）=4。而

于是得到： p 等于1或2时， x ₂ 是 x ₁ 的最近邻点； p 大于等于3时， x ₃ 是 x ₁ 的最近邻点。

3.2.3 k 值的选择

k 值的选择会对 k 近邻法的结果产生重大影响。

如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感 ^[2] 。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说， k 值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的 k 值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。

如果 k = N ，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。

在应用中， k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。