Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (21): 1-7.DOI: 10.3778/j.issn.1002-8331.1707-0202

Previous Articles     Next Articles

Survey on theory and application of k-Nearest-Neighbors algorithm

WU Xueyan, WANG Shuihua, ZHANG Yudong   

  1. School of Computer Science and Technology, Nanjing Normal University, Nanjing 210023, China
  • Online:2017-11-01 Published:2017-11-15

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

毋雪雁,王水花,张煜东   

  1. 南京师范大学 计算机科学与技术学院,南京 210023

Abstract: 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.

Key words: k-Nearest-Neighbors(kNN) algorithm, face recognition, text recognition, medical image processing

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

关键词: k最近邻算法(kNN), 人脸识别, 文字识别, 医学图像处理