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

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

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

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.