KNN 介绍

$k$ 近邻法(k-nearest neighbor, k-NN) 1968 年由 Cover 和 Hart 提出。 KNN 是一种基本分类与回归方法。这里只讨论分类问题中的 KNN。 KNN 的输入为实例的特征向量，对应于特征空间的点；输出位实例的类别，可以取多类

KNN 假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其 $k$ 个最近邻的训练实例的类别， 通过多数表决等方法进行预测，因此，KNN 不具有显式的学习过程。KNN 实际上利用训练数据集对特征向量空间进行划分， 并作为其分类的“模型”

$k$ 值的选择、距离度量及分类决策规则是 KNN 的三个基本要素

KNN 算法

KNN 算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最近邻的 $k$ 个实例， 这 $k$ 个实例的多数属于某个类，就把该输入实例分为这个类

具体算法如下：

输入

训练数据集

$$T=\left\{\right(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N\left)\right\}$$

其中：

• $x_i\in X\subseteq R^n$ 为实例的特征向量， $y_i\in Y=\{c_1,c_2,\dots ,c_K\}$ 为实例的类别， $i=1,2,\dots ,N$
• 实例特征向量 $x$

输出

实例 $x$ 所属的类 $y$

1. 根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最近邻的 $k$ 个点， 盖这 $k$ 个点的 $x$ 的邻域记作 $N_k\left(x\right)$
2. 在 $N_k\left(x\right)$ 中根据分类决策规则（ 如多数表决）决定 $x$ 的类别 $y$

$$y=arg\underset{c_j}{max}\sum _{x_i\in N_k\left(x\right)}I(y_i=c_j),i=1,2,\dots ,N;j=1,2,\dots ,K$$

其中：

• $I$ 为指示函数，即当 $y_i=c_j$ 时 $I$ 为 1，否则 $I$ 为 0

KNN 的特殊情况是 $k=1$ 的情形，称为最近邻法。对于输入的实例点（特征向量）$x$， 最近邻法将训练数据集中与 $x$ 最邻点的类作为 $x$ 的类

KNN 没有显式的学习过程

KNN 模型

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

模型

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

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

距离度量

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

设特征空间 $X$ 是 $n$ 维实数向量空间 $R^n$， $x_i,x_j\in X$，$x_i=(x_i^{\left(1\right)},x_i^{\left(2\right)},\dots ,x_i^{\left(n\right)}{)}^T$， $x_j=(x_j^{\left(1\right)},x_j^{\left(2\right)},\dots ,x_j^{\left(n\right)}{)}^T$

$x_i$，$x_j$ 的 $L_p$ 距离定义为：

$$L_p(x_i,x_j)=(\sum _{l=1}^n|x_i^{\left(l\right)}-x_j^{\left(l\right)}{|}^p{)}^{\frac{1}{p}}，p\ge 1$$

当 $p=2$ 时，称为欧氏距离（Euclidean distance），即

$$L_2(x_i,x_j)=(\sum _{l=1}^n|x_i^{\left(l\right)}-x_j^{\left(l\right)}{|}^2{)}^{\frac{1}{2}}$$

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

$$L_1(x_i,x_j)=\sum _{l=1}^n|x_i^{\left(l\right)}-x_j^{\left(l\right)}|$$

当 $p=\infty$ 时，它是各个坐标距离的最大值，即：

$$L_{\infty }(x_i,x_j)=\underset{l}{max}|x_i^{\left(l\right)}-x_j^{\left(l\right)}|$$

k 值的选择

$k$ 值的选择会对 KNN 的结果产生重大影响

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

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

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

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

分类决策规则

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

多数表决规则（majority voting rule）有如下解释：如果分类的损失函数为 $0-1$ 损失函数，分类函数为

$$f:R^n\to \{c_1,c_2,\dots ,c_K\}$$

那么误分类的概率是

$$P(Y\ne f(X\left)\right)=1-P(Y=f(X\left)\right)$$

对给定的实例 $x\in X$，其最近邻的 $k$ 个训练实例点构成集合 $N_k\left(x\right)$。 如果涵盖 $N_k\left(x\right)$ 的区域的类别是 $c_j$，那么误分类率是

$$\frac{1}{k}\sum _{x_i\in N_k\left(x\right)}I(y_i\ne c_j)=1-\frac{1}{k}\sum _{x_i\in N_k\left(x\right)}I(y_i=c_j)$$

要使误分类率最小即经验风险最小，就要 $\sum _{x_i\in N_k\left(x\right)}I(y_i=c_j)$ 最大， 所以多数表决规则等价于经验风险最小化

KNN 的实现

kd 树

实现 KNN 时，主要考虑的问题是如何对训练数据进行快速 $k$ 近邻搜索。 这点在特征空间的维数大及训练数据容量大时尤其重要

KNN 最简单的实现方法是线性扫描（linear scan）。这时要计算输入实例与每一个训练实例的距离。 当训练集很大时，计算非常耗时，这种方法是不可行的

为了提高 KNN 搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。 具体方法很多，比如：kd 树（kd tree）方法

参考

• 统计学习方法-李航