K最近邻算法理论与应用综述

毋雪雁，王水花，张煜东

南京师范大学 计算机科学与技术学院，南京 210023

◎热点与综述◎

K最近邻算法理论与应用综述

毋雪雁，王水花，张煜东

南京师范大学 计算机科学与技术学院，南京 210023

k最近邻算法（kNN）是一个十分简单的分类算法，该算法包括两个步骤：（1）在给定的搜索训练集上按一定距离度量，寻找一个k的值。（2）在这个kNN算法当中，根据大多数分为一致的类来进行分类。kNN算法具有的非参数性质使其非常易于实现，并且它的分类误差受到贝叶斯误差的两倍的限制，因此，kNN算法仍然是模式分类的最受欢迎的选择。通过总结多篇使用了基于kNN算法的文献，详细阐述了每篇文献所使用的改进方法，并对其实验结果进行了分析；通过分析kNN算法在人脸识别、文字识别、医学图像处理等应用中取得的良好分类效果，对kNN算法的发展前景无比期待。

k最近邻算法（kNN）；人脸识别；文字识别；医学图像处理

1 引言

在模式识别这个领域中，k最近邻算法（kNN）是一种主要用于分类以及回归的非参数统计方法[1]。kNN算法是所有机器学习算法中最为简单的算法之一，这种基于实例的算法本身非常的简单有效，是一种惰性学习的算法。

目前，涌现出了越来越多的改进kNN算法的方法，许多的研究人员对其进行了不同方面的改进，使其在性能上有一定的提升，在作用范围上更加宽广。例如，加权最近邻算法[2]是k最近邻算法的一个变体，它根据它们的距离来分配同一个权重的邻居，权重随着距离变化而变化，距离越近，权重越大，反之，距离越远，权重越小；引用最近邻搜索算法[3]也是k最近邻算法的一个变体，该算法考虑了局部距离特征和局部稀疏特征，该算法具有较强的竞争性、分类精度与适应性；终于人脸识别问题研究，一种新的快速近邻搜索算法[4]在最近被提出，它具有较高的维度，搜索更加快速准确，目标数据库的维护率很低，是一个精度更高的方法。对于上述提到的对于k最近邻算法的改进方式，在下文中会给出其更为具体的解释说明，并且对这些改进方法的特点和性能分别进行分析和比较。

kNN算法在人脸识别、文字识别、医学图像处理等领域被人们广为应用。例如，AHP对kNN改进的算法[5]来进行人脸识别和文字识别，该算法取得了良好的效果并且被广泛的运用。kNN算法在医学图像处理领域应用更加广泛，对于乳腺癌的检测、脑部图像分类与检测以及脑卒中检测有着很好的分类效果。kNN算法是取得一个良好分类结果的重要影响因素之一。

本文介绍了kNN算法的基本原理与在实际当中的一些应用，期望读者在读完本文之后能够了解现有kNN算法的发展，将来可以在提高kNN算法性能的同时把kNN算法应用至许多未知的新领域中。

2 kNN算法的基本介绍

kNN算法的基本思路是：假若一个特征空间中大多数的样本属于某一个类别，则在这个特征空间中，k个最相似的样本也属于这个类别。

该算法由两个步骤组成：（1）对于一个给定的搜索训练集按一定距离度量，来找到一个k的值。（2）在这个kNN当中，根据大多数分为一致的类来进行分类。

2.1 数学模型

kNN算法是一个“消极”算法，y=f(x1,x2,…xp,x)。其中x1,x2,…,xp是训练数据，x是待分类或回归查询实例，y是分类或回归结果。它根据kNN算法中大多数的类来对查询进行分类。

2.2 算法流程

假设一个训练集{(xi,yi)}ni=1∈D，xi是一个v维的矢量，yi是一个类的标签，对于查询xj在训练集(xj,yj)当中，该算法以这些方式获得其未知的yj：

（1）计算训练集当中xj到每一个xi的距离。

（2）将计算出的距离按顺序排列。

（3）选择训练集中最接近xj的k个样本。

（4）根据大多数点的分布可以在 xj的最近邻居得出其类标签。

kNN算法的流程如图1所示，其中，k为算法的初始类别参数，m为初始的最近邻元组的个数，L为训练元组与测试元组之间的距离，Lmax为之前存入优先级队列中的最大距离。

图1 kNN算法流程图

2.3 算法实现

Matlab代码对于kNN分类算法的实现如表1所述。表1也显示了：（1）先对数据进行分类处理。（2）计算各个向量之间的欧氏距离。（3）将距离进行升序排序，并且获取原索引值。（4）统计各个类别的数量。（5）获取最大数量的类别。

表1 kNN算法的Matlab实现

3 kNN算法应用

在实际应用当中，kNN算法在人脸识别、文字识别、医学图像处理等领域可以取得良好的分类效果。

3.1 人脸识别

随着QQ、微信以及Instagram等在线社交网络的出现，人们上传到网络中的图像数量正在迅速增加。大量的图像数据导致了对人们图像分析研究的需求变大。Sun[6]等提供了一个完整的解决方案，在云环境中使用Hadoop和kNN算法实现人脸图像的标签和分类。实验结果表明，这个系统在性能上有了很大的改进。此外，通过比较分类准确度和处理时间，证明了该系统十分有效。

Unnikrishnan[7]等利用人的面部属性，自动对图片中面部的性别和年龄进行估计，提出了一个新且广泛的数据集和年龄和性别估计研究的基准和分类流程。该分类流程包括图像检测、图像对齐、图像分割、图像纹理特征添加和识别这几个步骤。对于人的年龄和性别进行的分类，利用了深度学习知识中的kNN算法和SVM算法来实现。

Nagar[8]等提出可以使用稀疏流形聚类与嵌入算法来寻找人体面部的流行子空间，考虑具有不同姿态角度，照明和面部表情的不同个体的面部图像时，现有的多种技术不能给出准确的结果。kNN算法用于对脸部图像进行分类，将所提出的方法与使用用于不同面部表情，照明和姿势的标准面部数据集的基准进行比较。使用一次性交叉验证测试策略来验证结果。

Qian[9]等做出了两个贡献，（1）引入了一种基于局部自适应回归内核描述符（HWLD）的图像特征提取的视觉词直方图的新方法。（2）提出了k近邻的稀疏表示（kNN-SR），用于分配视觉词汇。实验结果证明了，该方法比一些最先进的特征提取方法的更加有效，准确率更高。

人脸识别的难点之一是方向或姿态的差异、光照变化、面部表情的改变等。Ameur[10]提出了一种在无控制环境下，运用Gabor小波和LBP来进行特征提取，降维之后运用kNN算法和SRC分类器来进行人脸识别，在时间消耗和识别率方面取得了很好的结果。同时，还证明了系统的效率取决于通过降维技术获得的缩减向量的大小。很明显，方法的融合比单独使用方法有更好分类效果。

杨淑平[11]等提出一个新的概念——分块小波，在此基础上他们使用kNN和SVM分类器相融合，得到了一个人脸识别的新算法。该算法既考虑了局部特征和组合特征，又克服小样本问题，再综合kNN的快速分类能力及SVM在少数类别分类上的优势，把二者进行融合，分类识别组合特征向量。实验结果证明：该方法识别率高，识别速度快，实验结果良好，实用性很高。

针对人脸表情识别，王小虎[12]等介绍了一种FSVM+kNN组合的人脸表情识别新方法，这个方法用PCA来提取人脸表情的特征，在不同的待分类区域中划分不同的区域类型，并结合这两种算法自身特点来分类。实验结果表明，这个方法既可以保证精确分类，又可以缩减计算时间，简化计算复杂度。

Wang[13]等提出了基于FSVM和kNN的人脸表情识别的一个新方法。首先，对人脸表情特征提取的主成分分析（PCA），然后，该算法将得到的区域划分为不同类型，并结合FSVM和kNN的特性，不同的分类方法针对不同类型。实验结果表明，该算法识别精度较为准确，同时简化了计算时间复杂度。

Zhou[14]等提出了一种基于改进的Gabor小波特征的主动外观模型（AAM），来提取面部特征点。混合AAM和它们的邻居的特征点被认为是一个分类问题，以得到进一步完善的结果。即：提取特征点附近的Gabor特征，通过线性判别分析（LDA）进行训练，并用kNN算法进行分类，得到特征点的精确位置。实验结果表明，该方法的准确率较高，可以准确地定位面部的特征。

Kamarol[15]等提出了一种基于kNN和加权方案的低复杂度的面部情绪识别和强度估计的新框架。该算法构造了一种面部特征表示方法，并利用Hidden Markov模型将输入视频分类为六种基本表达形式之一，即愤怒、厌恶、恐惧、幸福、悲伤和惊奇。然后用变点检测器获得表达式的时间段、中性点、起始点和顶点。

表2 kNN算法对于人脸识别的应用分析

3.2 文字识别

杨丽华[16]等详细地介绍文本的自动分类，文本分类在实际生活中有着十分广泛的应用，这对于人们获取信息有着极大的帮助。该文系统地介绍了kNN算法用于文本分类的原理，归纳了各种kNN算法的改进思路及算法，使得文本分类的实验结果更为准确。

为了使kNN算法在文本分类中能够更好地使用，周庆平[17]等提出一种基于聚类的改进kNN算法。在对文本进行第一步——特征提取之后，根据聚类算法把文本分成几类，再用改进的kNN算法对这几个类进行分类。实验最后证明了，这个方法对于文本分类有着很好的结果。

对于kNN算法没有办法同时满足分类速度和分类精度都很好的这一不足之处，樊存佳[18]等提出使用改进的K-Medoids聚类算法剔除对kNN算法分类没有什么贡献的训练样本，以至于得以减少计算kNN相似度的时间和精力，对于k个最近邻文本，定义代表度函数使其可以被有差别地处理。实验结果证明了，经过改进的kNN算法对于分类的准确度和减少时间复杂度均有着明显提高。

Pang[19]等结合kNN和Rocchio提出了一个广义的聚类基于质心的文本分类器，基本思路为两点：（1）使用聚类算法来加强Rocchio模型的表现力，并构建一个集群分类模型；（2）采用改进的Rocchio模型加快kNN分类速度。实验证明文本分类器的效果良好。

针对于伊朗车牌字符的识别，Tabrizi[20]等提供了一种新的方法，提高了车牌识别系统的识别精度，降低了识别系统的识别成本。在这方面，进行了kNN算法和多类支持向量机（kNN-SVM）模型的开发研究，SVM模型提高了在相似字符识别kNN性能，该模型克服了车牌字符相似性问题的混淆。

Jiang[21]等提出了一种改进的kNN文本分类算法，将约束单向聚类算法与kNN文本分类相结合，建立了一个分类模型。对三个基准语料库的实证结果证明，该算法能有效地减少对于文本相似度的计算量，并且优于当前最先进的kNN、朴素贝叶斯算法和SVM算法。此外，该算法构造的分类模型可以进行增量式更新，在许多实际应用中具有很大的可扩展性。

Jindal[22]等提出了一种新的生物医学领域文本分类的方法——LKNN算法，其中L用来代表医疗文件。这些标记用于将摘要与指定医学主题标题为网格的关键字的标准列表进行匹配，它自动将医学领域的期刊文章分为特定的类别。实验结果最终证明，LKNN算法在诸多方面均好于传统的kNN算法。

Du[23]提出一种基于聚类中心文本序列的并行MKNN算法来对文本进行分类。首先，基于聚类中心实现了算法相似度计算量的有效降维；其次，MapReduce并行框架的作用是：用来满足大规模文本分类和计算结合文本分类特征的实时需求；最后，该算法的分类速度可以保证足够的精度，比同类单线程算法的文本分类精度和算法效率都有提高。

Tan[24]对于因特网上文档的指数增长的问题，引入了多种监督学习算法来处理文本分类问题。其中，kNN算法的特性是简单、高效，在文本分类领域的应用较广。作者提出了一种新的优化策略，称之为对kNN分类器推拉。通过三基准评价集的实验可以得出，推拉kNN分类器在性能方面取得显著改进，好于传统的kNN分类器。

Trstenjak[25]等介绍了使用KNN算法和TF-IDF方法相结合构造文本分类框架的可能性。框架能够根据不同的参数来分类，测量和分析得出的结果。框架的评价主要集中在分类的速度和质量上。测试结果显示了算法的优缺点，为类似框架的进一步发展提供了指导。

Jo[26]提出了一个特定版本的kNN，其特征向量间的相似性考虑属性或特征之间的相似性计算和其中的价值。在这项研究中，定义了考虑属性和属性值的相似性，将kNN修改为基于属性相似性的版本，并使用修改后的版本作为文本摘要的方法，目的是实现更简洁、更可靠的表示数据项的文本摘要算法。

表3 kNN算法对于文字识别的应用分析

3.3 医学图像处理

为了使医生的负担得以减轻，加快医学发展的脚步，王清[27]等对于kNN算法进行了改进，并将其用在医学领域，他们使用速度较快的k均值聚类来获取训练样本，之后再用kNN算法对于未分类的像素进行分类。实验结果表明该算法可以较好地识别出MRI图相当中的脑白质、脊髓、灰质三个部分的图像。

孟志伟[28]等利用受限玻尔兹曼机（RBM）和kNN分类器相结合的方法，主要思路是：（1）构造可视层二值对于隐层二值的RBM，训练RBM得到特征提取器；（2）用该特征提取器来提取图像的特征；（3）用kNN算法来分类得到的特征。实验结果证明，该方法性能良好，且在分类准确率和分类效率方面都有着较为明显的提升。

当前，纹理分析法是人们对于假指纹检测使用的主要方法，然而这并不包括假指纹与人体指纹的差异所造成的噪声分析。张永良[29]等针对于假指纹检测，提出了一种SVM-kNN的分类算法，该算法利用曲波系数特征及曲波重构图像纹理特征来实现。实验结果证明该算法比LBP、SSCA等算法性能更优。

糖尿病视网膜病变是导致病人失去光明的新病例病因之一。在得病的早期，能够准确检测微动脉瘤（MAs）来诊断糖尿病视网膜病变的分级是有着非常重大意义的。Wu[30]等介绍了一个自动检测眼底图像中多智能体的方法。该方法包括四个主要步骤：预处理、候选提取、特征提取和分类。提取了局部特征和轮廓特征，用kNN分类器区分真假MAs。实验结果表明，该方法非常高效，对临床诊断具有很大的帮助。

Jung[31]等对于开发心律失常检测技术做出了很大的努力，通过主成分分析（PCA）方法来提取系数和线性判别分析（LDA）方法加强原始信号的典型特征，采用加权kNN的加权值来控制降低灵敏度，这取决于算法中k的大小，之后再应用适应度规则来提高心律失常分类准确率。

Sudharani[32]评估了对于脑卒中图像k-最近邻分类器（kNN）和最小平均距离分类器（MMD）的相对性能，是一种完全自动化的方法来识别和分类脑卒中的不规则（出血），当大脑供血停止时，脑卒中就发生了。实验证明，kNN方法的识别率大于MMD的识别率，并且这两种方法的识别率都高于欧几里德和曼哈顿度量的求和。

Rajini[33]等提出了一种基于磁共振图像分类的自动诊断方法。该方法分为特征提取和分类两个阶段。在第一阶段中，利用离散小波变换（DWT）获得与MRI图像相关的特征，之后利用主成分分析（PCA）对磁共振图像的小波变换特征进行了提取，得到了更为重要的特征；在分类阶段有两个分类器：第一个分类器是前馈BP人工神经网络（FP-ANN）、第二分类器是kNN算法。根据这些特征，能够训练出一个基于神经网络的二值分类器，它能自动判断图像是正常脑或病脑，以及是否患有脑损伤。

Machhale[34]等提出了一种识别正常和异常脑MRI图像的智能分类系统。在本文实验中，采用了各种技术对脑癌进行分类。在此基础上，成功地完成了脑肿瘤的图像预处理、图像特征提取和分类检测。对比了SVM、kNN以及SVM-kNN这些机器学习技术，其中SVM-kNN表现出最高的分类准确率。

Zhong[35]等提出了一种基于kNN的MRI数据CT图像的预测方法。在该方法中，在约束空间范围内搜索每个MR图像补丁的最近邻，为了提高准确性和预测效率，作者建议使用基于低秩逼近和流形正则化优化的有监督的描述符来优化一个MR局部描述符和降维。结果表明，该方法能有效地预测CT数据，优于两种最新的CT预测方法。

对于同一个数据集，de Bresser[36]等将最近流行的几个方法：SIENA，US以及kNN进行了对比，得出了以下结论：US和kNN对脑容量测量有很好的精确性、准确性和可比性，对于体积变化的测量，SIENA显示出最好的性能。总之，在其他大脑结构的体积变化测量是必需的情况下，kNN是最佳选择。

表4 kNN算法对于医学图像处理的应用分析

4 kNN算法改进

虽然kNN算法优点非常明显，但其仍有不可忽视的缺点，比如：当数据集非常庞大的时候，计算会非常耗时，其时间和空间复杂度都很高。针对这一缺点，许多的专家学者都提出了改进的算法，比如Fuzzy-kNN算法[37]，该方法适用于数据量非常庞大的数据集。它可以正确界定分类问题的实例和类关系表现的几种机制，是基于Fuzzy-kNN两个关键参数的多项选择表示：一个应用于隶属函数的定义，另一种用于分类规则，该算法提高了分类的准确性，减少了分类时间，优于传统的kNN算法。

kNN算法在一些问题的处理和分类上，无法为不可见的实例确定标签集。针对于这一缺点的改进主要有多标签学习kNN算法[38]。对于每个看不见的实例，它在训练集中的k最近的邻居都是第一个被识别的，在此之后，根据这些相邻实例的标签集获得的统计信息，即每个可能类的相邻实例的数量，最大限度地利用后面的（MAP）原则来确定未被发现的实例的标签集。该算法在一些已建立的多标签学习算法中取得了十分优异的性能。

kNN算法基于VSM模型，利用欧氏距离或余弦距离来度量样本的距离，但权重不变，这与实际情况不符。针对于这一缺点的改进主要有加权kNN算法[39]。它根据样本点之间的距离来分配一个权重，权重的大小随距离的减小而增大。与标准kNN相比，权重的引入提高了分类性能，原因是训练样本更接近对象，因此它们更可能被分类在同一类中。因此，加权kNN的分类准确度通常情况下比传统的kNN算法要好很多。

传统的kNN算法在相似度测量上以及亲和力方面仍有着许多不足之处，针对于这一点的改进主要有亲和力为基础的新的局部距离函数和相似性度量的改进kNN算法[40]。设计了一种基于新的亲和距离函数的相似度测量函数，提出kNN算法实现附近水平学习而构建的功能即：接近的距离和相似度函数，它也可以被归类为一个局部自适应的kNN算法。上述修改对算法性能的影响很大，实验结果表明，该方法优于kNN算法的一些知名的变体。

在移动的计算环境中，所有的移动用户在网络中的一个指定时间持续监控kNN的结果是一种空间查询，这就带来了一个问题：一个节点的单个运动可能导致几个用户不得不重新计算他们的kNN结果。针对于这一点，桶点区域的移动用户使用四叉树索引来对kNN算法进行了改进[41]，一种新的Reverse-kNN技术被提出以维护开销，这有助于快速确定这些节点中的每一个合适的搜索半径，便于查询结果的连续监测。

此外，针对不同的实际问题，还有许多kNN算法与其他算法相融合的改进，这些改进都提高了传统的kNN算法的性能，降低了其时间和空间复杂度，为各种分类问题提供了思路和解决方法，值得学习和研究。

5 kNN算法与SVM算法的对比与分析

kNN算法是一种取决于统计的懒惰学习算法，它读取一组标记训练集，然后用它对未标记的测试集进行分类；然而，它有一个选择k的最佳值的问题，这可以通过做实验来测试k的不同值并选择性能最好的值来实现。SVM算法是从一组标记的训练数据生成函数的方法，该函数可以是一个分类函数，也可以是一般的回归函数；在分类方面，SVM算法是在可能的输入空间找到一个超曲面，但是这就使得分类的正确率接近测试数据但是与训练数据并不一致。针对不同的数据集，两种算法有着不同的表现，在微型精密值方面，kNN算法较为优异；当特征数量很高时，SVM表现出更好的性能；但是kNN算法的计算简单，效率很高，复杂度方面优于SVM算法[42]。

6 总结与展望

本文详细地介绍了kNN算法的基本原理，以及国内外学者对于其在不同领域的应用，并且对比分析了kNN算法与其他分类算法。目前，kNN算法已被广泛应用于人脸识别、文字识别和医学图像处理等领域中，并且取得了一定的成果，对人类生活有着很大的帮助。总之，kNN算法是一个功能很强大的分类算法，在今后的研究中，需要对其进行改进以使其可以针对不同的问题都有一个良好的分类结果，如何利用kNN算法在新兴领域等方面做进一步的改进依然是一个研究热点。

[1]Altman N S.An introduction to kernel and nearest-neighbor nonparametric regression[J].The American Statistician，1992，46（3）：175-185.

[2]Bicego M，Loog M.Weighted K-nearest neighbor revisited[C]//International Conference on Pattern Recognition（ICPR），2016：1642-1647.

[3]Ding J，Cheng H D，Xian M，et al.Local-weighted citation-kNN algorithm for breast ultrasound image classification[J].Optik-International Journal for Light and Electron Optics，2015，126（24）：5188-5193.

[4]Ishii M，Imaoka H，Sato A.Fast k-nearest neighbor search for face identification using bounds of residual score[C]//IEEE International Conference on Automatic Faceamp;Gesture Recognition，2017，194-199.

[5]Bhattacharya G，Ghosh K，Chowdhury A S.Granger causality driven AHP for feature weighted kNN[J].Pattern Recognition，2017，66：425-436.

[6]Sun K，Kang H，Park H H.Tagging and classifying facial images in cloud environments based on KNN using MapReduce[J].Optik-International Journal for Light and Electron Optics，2015，126（21）：3227-3233.

[7]Unnikrishnan A，Ajesh F，Kizhakkethottam J J.Texturebased estimation of age and gender from wild conditions[J].Procedia Technology，2016，24：1349-1357.

[8]Nagar R K，Manazhy R，Sankaran P.Sparse manifold discriminant embedding for face recognition[J].Procedia Computer Science，2016，89：743-748.

[9]Qian J，Yang J，Zhang N，et al.Histogram of visual words based on locally adaptive regression kernels descriptors for image feature extraction[J].Neurocomputing，2014，129：516-527.

[10]Ameur B，Masmoudi S，Derbel A G，et al.Fusing Gabor and LBP feature sets for KNN and SRC-based face recognition[C]//InternationalConference on Advanced Technologies for Signalamp;Image Processing，2016：453-458.

[11]杨淑平，易国栋，袁修贵，等.一种基于分块小波的人脸识别算法[J].中南大学学报：自然科学版，2013，44（5）：1902-1909.

[12]王小虎，黄银珍，张石清.结合FSVM和KNN的人脸表情识别[J].微电子学与计算机，2013（10）：38-41.

[13]Wang X H，Liu A，Zhang S Q.New facial expression recognition based on FSVM and KNN[J].Optik-International Journal for Light and Electron Optics，2015，126（21）：3132-3134.

[14]Zhou Y，Li Y，Wu Z，et al.Robust facial feature points extraction in color images[J].Engineering Applications of Artificial Intelligence，2011，24（1）：195-200.

[15]Kamarol S K A，Jaward M H，Kälviäinen H，et al.Joint facial expression recognition and intensity estimation based on weighted votes of image sequences[J].Pattern Recognition Letters，2017，92：25-32.

[16]杨丽华，戴齐，郭艳军.kNN文本分类算法研究[J].微计算机信息，2006，22（21）：269-270.

[17]周庆平，谭长庚，王宏君，等.基于聚类改进的KNN文本分类算法[J].计算机应用研究，2016，33（11）：3374-3377.

[18]樊存佳，汪友生，边航.一种改进的KNN文本分类算法[J].国外电子测量技术，2015（12）：39-43.

[19]Pang G，Jiang S.A generalized cluster centroid based classifier for text categorization[J].Information Processingamp;Management，2013，49（2）：576-586.

[20]Tabrizi S S，Cavus N.A hybrid KNN-SVM model for iranian license plate recognition[J].Procedia Computer Science，2016，102：588-594.

[21]Jiang S，Pang G，Wu M，et al.An improved K-nearestneighbor algorithm for text categorization[J].Expert Systems with Applications，2012，39（1）：1503-1509.

[22]Jindal R，Taneja S.A lexical approach for text categorization of medical documents[J].Procedia Computer Science，2015，46：314-320.

[23]Du J H.Automatic text classification algorithm based on Gauss improved convolutional neural network[J].Journal of Computational Science，2017：709-714.

[24]Tan S.An effective refinement strategy for KNN text classifier[J].Expert Systems with Applications，2006，30（2）：290-298.

[25]Trstenjak B，Mikac S，Donko D.KNN with TF-IDF based framework for text categorization[J].Procedia Engineering，2014，69：1356-1364.

[26]Jo T.K nearest neighbor for text summarization using feature similarity[C]//International Conference on Communication，Control，Computing and Electronics Engineering（ICCCCEE），2017：371-375.

[27]王清，马华，孙静，等.改进的KNN算法及其在医学图像处理中的应用[J].泰山医学院学报，2006，27（6）：564-566.

[28]孟志伟，刘惠义，陈霜霜.基于RBM_KNN的脑部磁共振图像分类[J].信息技术，2017（4）：169-173.

[29]张永良，刘超凡，肖刚，等.基于曲波纹理分析和SVM_KNN分类的假指纹检测算法[J].计算机科学，2014，41（12）：303-308.

[30]Wu B，Zhu W，Shi F，et al.Automatic detection of microaneurysms in retinal fundus images[J].Computerized Medical Imaging and Graphics：the Official Journal of the Computerized Medical Imaging Society，2017，55：106-112.

[31]Jung W H，Lee S G.An arrhythmia classification method in utilizing the weighted KNN and the fitness rule[J].IRBM，2017，38（3）：138-148.

[32]Sudharani K，Sarma T C，Prasad K S.Brain stroke detection using K-nearest neighbor and minimum mean distance technique[C]//InternationalConference on Control，2016：770-776.

[33]Rajini N H，Bhavani R.Classification of MRI brain images using k-nearest neighbor and artificial neural network[C]//International Conference on Recent Trends in Information Technology，2011：563-568.

[34]Machhale K，Nandpurn H B，Kapur V，et al.MRI brain cancer classification using hybrid classifier（SVM-KNN）[C]//InternationalConference on IndustrialInstrumentation and Control（ICIC），2015：60-65.

[35]Zhong Liming，Lin Liyan，Lu Zhentai，et al.Predict CT image from MRI dATA using kNN-regeression with learned local descriptors[C]//IEEE International Symposium on Biomedical Imaging，2016：743-746.

[36]De B J，Portegies M P，Leemans A，et al.A comparison ofMR based segmentation methodsformeasuring brain atrophy progression[J].NeuroImage，2011，54（2）：760-768.

[37]Derrac J，Chiclana F，Garc A S，et al.Evolutionary fuzzy k-nearest neighbors algorithm using interval-valued fuzzy sets[J].Information Sciences，2016，329：144-163.

[38]Zhang M L，Zhou Z H.ML-KNN：A lazy learning approach to multi-label learning[J].Pattern Recognition，2007，40（7）：2038-2048.

[39]Gao Y，Gao F.Edited adaboost by weighted kNN[J].Neurocomputing，2010，73（16/18）：3079-3088.

[40]Bhattacharya G，Ghosh K，Chowdhury A S.An affinitybased new local distance function and similarity measure for kNN algorithm[J].Pattern Recognition Letters，2012，33（3）：356-363.

[41]Yang K T，Chiu G M.Monitoring continuous all k-nearest neighbor query in mobile network environments[J].Pervasive and Mobile Computing，2017，39：231-248.

[42]Hmeidi I，Hawashin B，El-qawasmeh E.Performance of KNN and SVM classifiers on full word Arabic articles[J].Advanced Engineering Informatics，2008，22（1）：106-111.

WU Xueyan,WANG Shuihua,ZHANG Yudong

School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China

Survey on theory and application of k-Nearest-Neighbors algorithm.Computer Engineering and Applications,2017,53（21）：1-7.

K nearest neighbor（kNN）algorithm is a simple classification algorithm,the algorithm consists of two steps：（1）Find out a set of k on a given search training set measure at a distance.（2）The classification is according to the most consistent classes in this kNN algorithm.The non-parametric property of kNN algorithm makes it very easy to implement,and its classification error is restricted by two times of the Bayes error.Therefore,the kNN algorithm is still the most popular choice for pattern classification.This paper summarizes many literatures by using kNN algorithm,expounding the improvement methods used in each document,and analyzing the experimental results.By analyzing the kNN algorithm in face recognition,text recognition,medical image-processing and other applications achieved good classification results,this paper is very promising for the development of kNN algorithm.

k-Nearest-Neighbors（kNN）algorithm;face recognition;text recognition;medical image processing

A

TP301.6

10.3778/j.issn.1002-8331.1707-0202

国家自然科学基金（No.61602250，No.61503188）；江苏省自然科学基金（No.BK20150983，No.BK20150982）；江苏省高校自然科学研究面上项目（No.16KJB520025，No.15KJB470010）。

毋雪雁（1993—），女，硕士生，研究方向：模式识别；王水花（1985—），女，讲师，研究方向：模式识别；张煜东（1985—），男，教授，博导，研究方向：人工智能与医学图像处理，E-mail：yudongzhang@ieee.org。

2017-07-13

2017-09-18

1002-8331（2017）21-0001-07