k近邻法（二）|距离变量+k值选择+分类决策规则| 《统计学习方法》学习笔记（十三）

k近邻模型

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

1. 模型

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

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

2. 距离变量

特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间$\bold R^n$Rn。使用的距离是欧式距离，但也可以是其他距离，如更一般的$L_p$Lp​距离（$L_p\space distance$Lp​ distance）或Minkowski距离。

设特征空间$\chi$χ是n维实数向量空间$\bold R^n$Rn，$x_i,x_j\in \chi, \quad x_l=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T，x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T$xi​,xj​∈χ,xl​=(xi(1)​,xi(2)​,...,xi(n)​)T，xj​=(xj(1)​,xj(2)​,...,xj(n)​)T，$x_i,x_j$xi​,xj​的$L_p$Lp​距离定义为
$L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$Lp​(xi​,xj​)=(l=1∑n​∣xi(l)​−xj(l)​∣p)p1​
这里$p\geq 1$p≥1。当$p=2$p=2时，称为欧氏距离(Euclidean distance)，即
$L_2(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2}}$L2​(xi​,xj​)=(l=1∑n​∣xi(l)​−xj(l)​∣2)21​
当$p=1$p=1时，称为曼哈顿距离（Manhattan distance），即
$L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|$L1​(xi​,xj​)=l=1∑n​∣xi(l)​−xj(l)​∣
当$p=\infty$p=∞时，它是各个坐标距离的最大值，即
$L_{\infty}(x_i,x_j)=max_{l}|x_i^{(l)}-x_j^{(l)}|$L∞​(xi​,xj​)=maxl​∣xi(l)​−xj(l)​∣
下图是二维空间p取不同值时，与原点的$L_p$Lp​距离为1($L_p=1$Lp​=1)的图形。

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

已知二维空间的3个点$x_1=(1,1)^T,x_2=(5,1)^T,x_3=(4,4)^T$x1​=(1,1)T,x2​=(5,1)T,x3​=(4,4)T，试求在p取不同值时，$L_p$Lp​距离下$x_1$x1​的最近邻点。

解：因为$x_1$x1​和$x_2$x2​只有第二维上值不同，所以p为任何值时，$L_p(x_1,x_2)=4$Lp​(x1​,x2​)=4。而$L_1(x_1,x_3)=6,L_2(x_1,x_3)=4.24,L_3(x_1,x_3)=3.78,L_4(x_1,x_3)=3.57$L1​(x1​,x3​)=6,L2​(x1​,x3​)=4.24,L3​(x1​,x3​)=3.78,L4​(x1​,x3​)=3.57

所以当p等于1或2时，$x_2$x2​是$x_1$x1​的最近邻点；p大于等于3时，$x_3$x3​是$x_1$x1​的最近邻点。

3. k值的选择

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

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

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

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

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

4. 分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则（major voting rule）有如下解释：如果分类的损失函数为0-1损失函数，分类函数为
$f:\bold R^n \to {c_1,c_2,...,c_k}$f:Rn→c1​,c2​,...,ck​
那么误分类的概率是
$P(Y \neq f(X))=1-P(Y=f(X))$P(Y​=f(X))=1−P(Y=f(X))
对给定的实例$x\in \chi$x∈χ，其最近邻的k个训练实例点构成集合$N_k(x)$Nk​(x)。如果涵盖$N_k(x)$Nk​(x)的区域类别是$c_j$cj​，那么误分类率是
$\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i\neq c_j)=1-k\sum_{x_i\in N_k(x)}I(y_i=c_j)$k1​xi​∈Nk​(x)∑​I(yi​​=cj​)=1−kxi​∈Nk​(x)∑​I(yi​=cj​)
要使误分类率最小即经验风险最小，就要使$\sum_{x_i\in N_k(x)}I(y_i=c_j)$∑xi​∈Nk​(x)​I(yi​=cj​)最大，所以多数表决规则等价于经验风险最小化。