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