K-近邻算法

k近邻算法例子。测试样本（绿色圆形）应归入要么是第一类的蓝色方形或是第二类的红色三角形。如果k=3（实线圆圈）它被分配给第二类，因为有2个三角形和只有1个正方形在内侧圆圈之内。如果k=5（虚线圆圈）它被分配到第一类（3个正方形与2个三角形在外侧圆圈之内）。

训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。

在分类阶段，k是一个用户定义的常数。一个没有类别标签的向量（查询或测试点）将被归类为最接近该点的k个样本点中最频繁使用的一类。

一般情况下，将欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种离散变量情况下，另一个度量——重叠度量（或海明距离）可以用来作为度量。例如对于基因表达微阵列数据，k-NN也与Pearson和Spearman相关系数结合起来使用。[4]通常情况下，如果运用一些特殊的算法来计算度量的话，k近邻分类精度可显著提高，如运用大间隔最近邻居或者邻里成分分析法。

“多数表决”分类会在类别分布偏斜时出现缺陷。也就是说，出现频率较多的样本将会主导测试点的预测结果，因为他们比较大可能出现在测试点的K邻域而测试点的属性又是通过k邻域内的样本计算出来的。[5]解决这个缺点的方法之一是在进行分类时将样本到k个近邻点的距离考虑进去。k近邻点中每一个的分类（对于回归问题来说，是数值）都乘以与测试点之间距离的成反比的权重。另一种克服偏斜的方式是通过数据表示形式的抽象。例如，在自组织映射（SOM）中，每个节点是相似的点的一个集群的代表（中心），而与它们在原始训练数据的密度无关。K-NN可以应用到SOM中。

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，[6] 但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术（见超参数优化）来获取。

噪声和非相关性特征的存在，或特徵尺度与它们的重要性不一致会使K近邻算法的准确性严重降低。对于选取和缩放特征来改善分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展[7]，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

在二元（两类）分类问题中，选取k为奇数有助于避免两个分类平票的情形。在此问题下，选取最佳经验k值的方法是自助法。[8]

k- 最近邻分类器可以被视为为 k最近邻居分配权重${\displaystyle 1/k}$以及为所有其他邻居分配 0权重。这可以推广到加权最近邻分类器。也就是说，第 i近的邻居被赋予权重${\displaystyle w_{ni}}$，其中${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$。关于加权最近邻分类器的强一致性的类似结果也成立。[9]

设${\displaystyle C_{n}^{wnn}}$表示权重为${\displaystyle \{w_{ni}\}_{i=1}^{n}}$的加权最近邻分类器。根据类别分布的规律性条件，超额风险具有以下渐近展开[10]

${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$

对常数 ${\displaystyle B_{1}}$ and ${\displaystyle B_{2}}$ 当 ${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$ 并且 ${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\{i^{1+2/d}-(i-1)^{1+2/d}\}}$。

最佳加权方案${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$用于平衡上面显示中的两个项，如下所示：令 ${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$，

${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$ 对 ${\displaystyle i=1,2,\dots ,k^{*}}$ 并且

${\displaystyle w_{ni}^{*}=0}$ 对 ${\displaystyle i=k^{*}+1,\dots ,n}$.

利用最优权重，超额风险的渐近展开中的主项是${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$。当使用bagged 最近邻分类器时，类似的结果也是如此。

原始朴素的算法通过计算测试点到存储样本点的距离是比较容易实现的，但它属于计算密集型的，特别是当训练样本集变大时，计算量也会跟着增大。多年来，许多用来减少不必要距离评价的近邻搜索算法已经被提出来。使用一种合适的近邻搜索算法能使K近邻算法的计算变得简单许多。

近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍[11]。对于一些K值，K近邻保证错误率不会超过贝叶斯的。

近邻算法能用一种有效的方式隐含的计算决策边界。另外，它也可以显式的计算决策边界，以及有效率的这样做计算，使得计算复杂度是边界复杂度的函数。[12]

K近邻算法也适用于连续变量估计，比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有：

1. 从目标区域抽样计算欧式或马氏距离；
2. 在交叉验证后的RMSE基础上选择启发式最优的K邻域；
3. 计算多元k-最近邻居的距离倒数加权平均。

然而k最近鄰居法因為計算量相當的大，所以相當的耗時，Ko與Seo提出一演算法TCFP（text categorization using feature projection），嘗試利用特徵投影法來降低與分類無關的特徵對於系統的影響，並藉此提昇系統效能，其實驗結果顯示其分類效果與k最近鄰居法相近，但其運算所需時間僅需k最近鄰居法運算時間的五十分之一。

除了針對文件分類的效率，尚有研究針對如何促進k最近鄰居法在文件分類方面的效果，如Han等人於2002年嘗試利用貪心法，針對文件分類實做可調整權重的k最近鄰居法WAkNN（weighted adjusted k nearest neighbor），以促進分類效果；而Li等人於2004年提出由於不同分類的文件本身有數量上有差異，因此也應該依照訓練集合中各種分類的文件數量，選取不同數目的最近鄰居，來參與分類。

• When Is "Nearest Neighbor" Meaningful?页面存档备份，存于
• Belur V. Dasarathy (编). . 1991. ISBN 0-8186-8930-7.
• Shakhnarovish, Darrell, and Indyk (编). . MIT Press. 2005. ISBN 0-262-19547-X.
• Mäkelä H Pekkarinen A. . Forest Ecology and Management. 2004-07-26, 196 (2–3): 245–255. doi:10.1016/j.foreco.2004.02.049.
• Fast k nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
• Scholarpedia article on k-NN 页面存档备份，存于
• google-all-pairs-similarity-search 页面存档备份，存于