K-最近邻

K-最近邻（KNN）是一种非参数监督式分类模型。它可以根据计算k个训练样本到查询点（query point）的距离（主要是欧几里德距离和马哈拉诺比斯距离）来分配标签（单独为每个点计算）。它在协同过滤推荐系统中有广泛的应用。

基本思想

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

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

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

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

假设

(x_1,y_1),(x_2,y_2),...(x_n,y_n),

Y是X的类标签。那么P就是X在可能类别Y上的概率分布。

在分类设置中，K最近邻算法本质上归结为在K个最相似的实例与给定的“unseen”的观察之间进行多数投票。相似性是根据两个数据点之间的距离度量来定义的。一个经典的方法是欧氏距离。

计算其他举例的方式：Manhattan, Chebyshev and Hamming distance.

更正式地，给定一个正整数K，一个看不见的观察x和一个相似度度量d, KNN分类器执行以下两个步骤:

• 集计算整个数据x和每个训练观察之间的d距离。在训练数据中，我们将K点称为最接近x的集合A。注意，K通常是奇数，以防止平局情况。
• 然后它估计每个类的条件概率，也就是说，给定类标签的点的分数。(注意，I(x)是指标函数，当参数x为真时，它的值为1，反之则为0)

最后，输入x被分配给具有最大概率的类。

KNN代码实例:

Iris Flower Dataset使用该数据集进行分类

# loading librariesimport pandas as pd# define column namesnames = ['sepal_length', 'sepal_width', 'petal_length', 'petal_width', 'class']# loading training datadf = pd.read_csv('path/iris.data.txt',header=None,names=names)df.head()

# ============================== R code ==============================#loading packageslibrary(ggplot2)library(magrittr)# sepal width vs. sepal lengthiris %>%ggplot(aes(x=Sepal.Length,y=Sepal.Width,color=Species))+geom_point()# petal width vs. petal lengthiris %>%ggplot(aes(x=Petal.Length,y=Petal.Width,color=Species)) +geom_point()# =====================================================================

# loading librariesimport numpy as npfrom sklearn.cross_validationimporttrain_test_split# create design matrix X and target vectoryX = np.array(df.ix[:, 0:4]) # end index is exclusivey = np.array(df['class']) # another way of indexing a pandas df# split into train and testX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33,random_state=42)

# loading libraryfrom sklearn.neighborsimport KNeighborsClassifier# instantiate learning model (k = 3)knn = KNeighborsClassifier(n_neighbors=3)# fitting the modelknn.fit(X_train,y_train)# predict the responsepred = knn.predict(X_test)# evaluate accuracyprint accuracy_score(y_test, pred)

发展历史

描述

大约50年前被发现以来，K-最近邻方法已经发展了很长时间。现在它主要被用于文本挖掘和预测问题，并且在农业、金融和医疗等行业领域得到了应用。

1951年，Fix和Hodges设想了最近邻规则，这也是KNN的最早设想之一。随后，1962年，Sebestyen将这样KNN称作邻近算法（proximity algorithm）。1965年，KNN当时被Nilsson称作最小距离分类器（minimum distance classifier）。1967年，Cover和Hart在论文《Nearest neighbor pattern classification》中正式介绍了KNN，也是KNN的首次正式的提出。

kNN算法因其提出时间较早，随着其他技术的不断更新和完善，kNN算法的诸多不足之处也逐渐显露，因此许多kNN算法的改进算法也应运而生。针对以上算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面。

分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。KNN算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分，如2006年，Zhang, H., Berg, A. C., Maire, M., & Malik, J. j.基于SVM和KNN区分最近邻分类的视觉类别。在2007年，Zhang, M. L., & Zhou, Z. H.在有限的数据中设计了对多标签数据的KNNs算法《ML-KNN: A lazy learning approach to multi-label learning》。2009年，《Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection》利用两种divide and conquer方法来近似KNN的计算。

分类效果：Stanfill和Waltz采用价值距离指标（Value Distance Metric/VDM）；采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2001年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。2005,NCA(Neighbourhood components analysis)是将马氏距离应用于KNN算法来实现降维的效果，它主要目的是通过找到一个线性变化矩阵，来最大化leave-one-out (LOO)分类精确度。算法的关键点在于可以通过可微的目标函数f(A)来找出线性变化矩阵A，比如说使用共轭梯度法。因此，NCA被普遍应用于模型的选择，降维，结构预测，异常分析，强化学习的神经网络中。

主要事件

发展分析

瓶颈

• 为了得到良好的表现，需要选择合适的k值，但k的选择仍然不容易控制。
• 模型在高维空间中可能效果不佳，而且当数据规模增长时，模型的扩展性能也不好。
• 计算负载重，需要使用很多内存。
• 其对不相关特征的敏感性可能会导致结果不准确。
• 难以确定使用哪种距离计算方法更好。

未来发展方向

• 未来会更多地研究和实验使用深度学习技术来学习K-NN可以执行的有用表征。为了将其应用到更多问题中，未来的一大研究方向是寻找能够克服树的表征能力上限的解决方案。

Contributor: Ruiying Cai