原理

k近邻法（k-nearest neighbor，k-NN）是一种基本的分类与回归方法。此处只讨论分类问题中的k-NN算法。k-NN算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别。可以取多类。k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对于新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方法进行预测。因此，k近邻法不具有显示的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。k近邻法1968年由Cover和Hart提出。

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

算法：k近邻法

输入：训练数据集

\[T = {(x_1, y_1), (x_2, y_2),...,(x_N, y_N)}\]

其中，\(x_i \in X \subseteq R^n\)为实例的特征向量，\(y_i \in Y = {c_1, c_2,...,c_K}\)为实例的类别，i=1,2,…,N；实例特征向量x；

输出：实例x所属的类y

(1) 根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖着k个点的x的邻域记作\(N_k(x)\)；

(2) 在$$N_k(x)中根据分类决策规则（如多数表决）决定x的类别y：

\[y = arg max_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_i), i=1,2,...,N; j=1,2,...,K\]

上式中，I为指示函数，即当\(y_i = c_i\)时，I为1，否则I为0.

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

k近邻算法没有显式的学习过程。

k近邻模型

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

模型

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

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

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是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^{(1)}, x_i^{(2)},...,x_i^{(n)})^T, x_j = (x_j^{(1)}, x_j^{(2)},...,x_j^{(n)})^T\)，\(x_i, x_j\)的\(L_p\)距离定义为

\[L_p(x_i, x_j) = (\sum_{l=1}^n \mid x_i^{(l)} - x_j^{(l)} \mid^p)^{\frac{1}{p}}\]

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

\[L_2(x_i, x_j) = (\sum_{l=1}^n \mid x_i^{(l)} - x_j^{(l)} \mid^2)^{\frac{1}{2}}\]

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

\[L_1(x_i, x_j) = \sum_{l=1}^n \mid x_i^{(l)} - x_j^{(l)} \mid\]

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

\[L_\infty(x_i, x_j) = \max_l \mid x_i^{(l)} - x_j^{(l)} \mid\]

k值的选择

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

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

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

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

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

分类决策规则

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

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

\[f: R^n \to {c_1, c_2,...,c_K}\]

那么误分类的概率是

\[P(Y \neq f(X)) = 1 - P(Y=f(X))\]

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

\[\frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i \neq c_j) = 1- \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i = c_j)\]

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

k近邻法的实现：kd树

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

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

为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。例如kd树。

构造kd树

kd树是对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

构造kd树的方法如下：构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对k维空间进行切分，生成子结点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当期超矩形区域切分成左右两个子区域（子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例为止（终止时的结点为叶结点）。在此过程中，将实例保持在相应的结点上。

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数（median）为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时效率未必是最优的。

算法：构造平衡kd树

输入：k维空间数据集\(T={x_1, x_2,...,x_N}\)，其中\(x_i = (x_i^{(1)}, x_i^{(2)}, ... x_i^{(l)})^T, i=1,2,...,N\)

输出：kd树

(1) 开始：构造根结点，根结点对应于包含T的k维空间的超矩形区域。

选择\(x^{(1)}\)为坐标轴，以T中所有实例\(x^{(1)}\)坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴\(x^{(1)}\)垂直的超平面实现。

由根结点生成深度为1的左右子结点：左子结点对应坐标\(x^{(1)}\)小于切分点的子区域，右子结点对应于坐标\(x^{(1)}\)大于切分点的子区域。

将落在切分超平面上的实例点保存在根结点。

(2) 重复：对深度为j的结点，选择\(x^{(l)}\)为切分的坐标轴，\(l=j(mod k)+1\)，以该结点的区域中所有实例\(x^{(l)}\)坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴\(x^{(l)}\)垂直的超平面实现。

由该结点生成深度为j+1的左右子结点：做子结点对应于坐标\(x^{(l)}\)小于切分点的子区域，右子结点对应坐标\(x^{(l)}\)大于切分点的子区域。

将落在切分超平面上的实例点保存在该结点。

(3) 直到两个子区域没有实例点存在时停止。从而形成kd树的区域划分。

搜索kd树

算法： 用kd树的最近邻搜索

输入：已构造的kd树；目标点x；

输出：x的最近邻。

(1) 在kd树中找出包含目标点x的叶结点。

(2) 以此叶结点为“当前最近点”

(3) 递归地向上回退，在每个结点进行以下操作：

(a) 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”

(b) 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标为球心，以目标点与“当前最近点”间的距离为半径的超球体相交。

如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；

如果不相交，向上回退。

(4) 当回退到根结点时，搜索结束，最后的“当前最近点”即为x的最近邻点。

如果实例点是随机分布的，kd树搜索的平均计算复杂度是O(log N)，这里N是训练实例数。kd树更适合用于训练实例数远大于空间维数时的k近邻搜索。当空间维树接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

参考文献

  • 统计学习方法 李航 第3章