毋雪雁，王水花，張煜東

南京師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210023

◎熱點(diǎn)與綜述◎

K最近鄰算法理論與應(yīng)用綜述

毋雪雁，王水花，張煜東

南京師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210023

k最近鄰算法（kNN）是一個(gè)十分簡(jiǎn)單的分類(lèi)算法，該算法包括兩個(gè)步驟：（1）在給定的搜索訓(xùn)練集上按一定距離度量，尋找一個(gè)k的值。（2）在這個(gè)kNN算法當(dāng)中，根據(jù)大多數(shù)分為一致的類(lèi)來(lái)進(jìn)行分類(lèi)。kNN算法具有的非參數(shù)性質(zhì)使其非常易于實(shí)現(xiàn)，并且它的分類(lèi)誤差受到貝葉斯誤差的兩倍的限制，因此，kNN算法仍然是模式分類(lèi)的最受歡迎的選擇。通過(guò)總結(jié)多篇使用了基于kNN算法的文獻(xiàn)，詳細(xì)闡述了每篇文獻(xiàn)所使用的改進(jìn)方法，并對(duì)其實(shí)驗(yàn)結(jié)果進(jìn)行了分析；通過(guò)分析kNN算法在人臉識(shí)別、文字識(shí)別、醫(yī)學(xué)圖像處理等應(yīng)用中取得的良好分類(lèi)效果，對(duì)kNN算法的發(fā)展前景無(wú)比期待。

k最近鄰算法（kNN）；人臉識(shí)別；文字識(shí)別；醫(yī)學(xué)圖像處理

1 引言

在模式識(shí)別這個(gè)領(lǐng)域中，k最近鄰算法（kNN）是一種主要用于分類(lèi)以及回歸的非參數(shù)統(tǒng)計(jì)方法[1]。kNN算法是所有機(jī)器學(xué)習(xí)算法中最為簡(jiǎn)單的算法之一，這種基于實(shí)例的算法本身非常的簡(jiǎn)單有效，是一種惰性學(xué)習(xí)的算法。

目前，涌現(xiàn)出了越來(lái)越多的改進(jìn)kNN算法的方法，許多的研究人員對(duì)其進(jìn)行了不同方面的改進(jìn)，使其在性能上有一定的提升，在作用范圍上更加寬廣。例如，加權(quán)最近鄰算法[2]是k最近鄰算法的一個(gè)變體，它根據(jù)它們的距離來(lái)分配同一個(gè)權(quán)重的鄰居，權(quán)重隨著距離變化而變化，距離越近，權(quán)重越大，反之，距離越遠(yuǎn)，權(quán)重越??；引用最近鄰搜索算法[3]也是k最近鄰算法的一個(gè)變體，該算法考慮了局部距離特征和局部稀疏特征，該算法具有較強(qiáng)的競(jìng)爭(zhēng)性、分類(lèi)精度與適應(yīng)性；終于人臉識(shí)別問(wèn)題研究，一種新的快速近鄰搜索算法[4]在最近被提出，它具有較高的維度，搜索更加快速準(zhǔn)確，目標(biāo)數(shù)據(jù)庫(kù)的維護(hù)率很低，是一個(gè)精度更高的方法。對(duì)于上述提到的對(duì)于k最近鄰算法的改進(jìn)方式，在下文中會(huì)給出其更為具體的解釋說(shuō)明，并且對(duì)這些改進(jìn)方法的特點(diǎn)和性能分別進(jìn)行分析和比較。

kNN算法在人臉識(shí)別、文字識(shí)別、醫(yī)學(xué)圖像處理等領(lǐng)域被人們廣為應(yīng)用。例如，AHP對(duì)kNN改進(jìn)的算法[5]來(lái)進(jìn)行人臉識(shí)別和文字識(shí)別，該算法取得了良好的效果并且被廣泛的運(yùn)用。kNN算法在醫(yī)學(xué)圖像處理領(lǐng)域應(yīng)用更加廣泛，對(duì)于乳腺癌的檢測(cè)、腦部圖像分類(lèi)與檢測(cè)以及腦卒中檢測(cè)有著很好的分類(lèi)效果。kNN算法是取得一個(gè)良好分類(lèi)結(jié)果的重要影響因素之一。

本文介紹了kNN算法的基本原理與在實(shí)際當(dāng)中的一些應(yīng)用，期望讀者在讀完本文之后能夠了解現(xiàn)有kNN算法的發(fā)展，將來(lái)可以在提高kNN算法性能的同時(shí)把kNN算法應(yīng)用至許多未知的新領(lǐng)域中。

2 kNN算法的基本介紹

kNN算法的基本思路是：假若一個(gè)特征空間中大多數(shù)的樣本屬于某一個(gè)類(lèi)別，則在這個(gè)特征空間中，k個(gè)最相似的樣本也屬于這個(gè)類(lèi)別。

該算法由兩個(gè)步驟組成：（1）對(duì)于一個(gè)給定的搜索訓(xùn)練集按一定距離度量，來(lái)找到一個(gè)k的值。（2）在這個(gè)kNN當(dāng)中，根據(jù)大多數(shù)分為一致的類(lèi)來(lái)進(jìn)行分類(lèi)。

2.1 數(shù)學(xué)模型

kNN算法是一個(gè)“消極”算法，y=f(x1,x2,…xp,x)。其中x1,x2,…,xp是訓(xùn)練數(shù)據(jù)，x是待分類(lèi)或回歸查詢實(shí)例，y是分類(lèi)或回歸結(jié)果。它根據(jù)kNN算法中大多數(shù)的類(lèi)來(lái)對(duì)查詢進(jìn)行分類(lèi)。

2.2 算法流程

假設(shè)一個(gè)訓(xùn)練集{(xi,yi)}ni=1∈D，xi是一個(gè)v維的矢量，yi是一個(gè)類(lèi)的標(biāo)簽，對(duì)于查詢xj在訓(xùn)練集(xj,yj)當(dāng)中，該算法以這些方式獲得其未知的yj：

（1）計(jì)算訓(xùn)練集當(dāng)中xj到每一個(gè)xi的距離。

（2）將計(jì)算出的距離按順序排列。

（3）選擇訓(xùn)練集中最接近xj的k個(gè)樣本。

（4）根據(jù)大多數(shù)點(diǎn)的分布可以在 xj的最近鄰居得出其類(lèi)標(biāo)簽。

kNN算法的流程如圖1所示，其中，k為算法的初始類(lèi)別參數(shù)，m為初始的最近鄰元組的個(gè)數(shù)，L為訓(xùn)練元組與測(cè)試元組之間的距離，Lmax為之前存入優(yōu)先級(jí)隊(duì)列中的最大距離。

圖1 kNN算法流程圖

2.3 算法實(shí)現(xiàn)

Matlab代碼對(duì)于kNN分類(lèi)算法的實(shí)現(xiàn)如表1所述。表1也顯示了：（1）先對(duì)數(shù)據(jù)進(jìn)行分類(lèi)處理。（2）計(jì)算各個(gè)向量之間的歐氏距離。（3）將距離進(jìn)行升序排序，并且獲取原索引值。（4）統(tǒng)計(jì)各個(gè)類(lèi)別的數(shù)量。（5）獲取最大數(shù)量的類(lèi)別。

表1 kNN算法的Matlab實(shí)現(xiàn)

3 kNN算法應(yīng)用

在實(shí)際應(yīng)用當(dāng)中，kNN算法在人臉識(shí)別、文字識(shí)別、醫(yī)學(xué)圖像處理等領(lǐng)域可以取得良好的分類(lèi)效果。

3.1 人臉識(shí)別

隨著QQ、微信以及Instagram等在線社交網(wǎng)絡(luò)的出現(xiàn)，人們上傳到網(wǎng)絡(luò)中的圖像數(shù)量正在迅速增加。大量的圖像數(shù)據(jù)導(dǎo)致了對(duì)人們圖像分析研究的需求變大。Sun[6]等提供了一個(gè)完整的解決方案，在云環(huán)境中使用Hadoop和kNN算法實(shí)現(xiàn)人臉圖像的標(biāo)簽和分類(lèi)。實(shí)驗(yàn)結(jié)果表明，這個(gè)系統(tǒng)在性能上有了很大的改進(jìn)。此外，通過(guò)比較分類(lèi)準(zhǔn)確度和處理時(shí)間，證明了該系統(tǒng)十分有效。

Unnikrishnan[7]等利用人的面部屬性，自動(dòng)對(duì)圖片中面部的性別和年齡進(jìn)行估計(jì)，提出了一個(gè)新且廣泛的數(shù)據(jù)集和年齡和性別估計(jì)研究的基準(zhǔn)和分類(lèi)流程。該分類(lèi)流程包括圖像檢測(cè)、圖像對(duì)齊、圖像分割、圖像紋理特征添加和識(shí)別這幾個(gè)步驟。對(duì)于人的年齡和性別進(jìn)行的分類(lèi)，利用了深度學(xué)習(xí)知識(shí)中的kNN算法和SVM算法來(lái)實(shí)現(xiàn)。

Nagar[8]等提出可以使用稀疏流形聚類(lèi)與嵌入算法來(lái)尋找人體面部的流行子空間，考慮具有不同姿態(tài)角度，照明和面部表情的不同個(gè)體的面部圖像時(shí)，現(xiàn)有的多種技術(shù)不能給出準(zhǔn)確的結(jié)果。kNN算法用于對(duì)臉部圖像進(jìn)行分類(lèi)，將所提出的方法與使用用于不同面部表情，照明和姿勢(shì)的標(biāo)準(zhǔn)面部數(shù)據(jù)集的基準(zhǔn)進(jìn)行比較。使用一次性交叉驗(yàn)證測(cè)試策略來(lái)驗(yàn)證結(jié)果。

Qian[9]等做出了兩個(gè)貢獻(xiàn)，（1）引入了一種基于局部自適應(yīng)回歸內(nèi)核描述符（HWLD）的圖像特征提取的視覺(jué)詞直方圖的新方法。（2）提出了k近鄰的稀疏表示（kNN-SR），用于分配視覺(jué)詞匯。實(shí)驗(yàn)結(jié)果證明了，該方法比一些最先進(jìn)的特征提取方法的更加有效，準(zhǔn)確率更高。

人臉識(shí)別的難點(diǎn)之一是方向或姿態(tài)的差異、光照變化、面部表情的改變等。Ameur[10]提出了一種在無(wú)控制環(huán)境下，運(yùn)用Gabor小波和LBP來(lái)進(jìn)行特征提取，降維之后運(yùn)用kNN算法和SRC分類(lèi)器來(lái)進(jìn)行人臉識(shí)別，在時(shí)間消耗和識(shí)別率方面取得了很好的結(jié)果。同時(shí)，還證明了系統(tǒng)的效率取決于通過(guò)降維技術(shù)獲得的縮減向量的大小。很明顯，方法的融合比單獨(dú)使用方法有更好分類(lèi)效果。

楊淑平[11]等提出一個(gè)新的概念——分塊小波，在此基礎(chǔ)上他們使用kNN和SVM分類(lèi)器相融合，得到了一個(gè)人臉識(shí)別的新算法。該算法既考慮了局部特征和組合特征，又克服小樣本問(wèn)題，再綜合kNN的快速分類(lèi)能力及SVM在少數(shù)類(lèi)別分類(lèi)上的優(yōu)勢(shì)，把二者進(jìn)行融合，分類(lèi)識(shí)別組合特征向量。實(shí)驗(yàn)結(jié)果證明：該方法識(shí)別率高，識(shí)別速度快，實(shí)驗(yàn)結(jié)果良好，實(shí)用性很高。

針對(duì)人臉表情識(shí)別，王小虎[12]等介紹了一種FSVM+kNN組合的人臉表情識(shí)別新方法，這個(gè)方法用PCA來(lái)提取人臉表情的特征，在不同的待分類(lèi)區(qū)域中劃分不同的區(qū)域類(lèi)型，并結(jié)合這兩種算法自身特點(diǎn)來(lái)分類(lèi)。實(shí)驗(yàn)結(jié)果表明，這個(gè)方法既可以保證精確分類(lèi)，又可以縮減計(jì)算時(shí)間，簡(jiǎn)化計(jì)算復(fù)雜度。

Wang[13]等提出了基于FSVM和kNN的人臉表情識(shí)別的一個(gè)新方法。首先，對(duì)人臉表情特征提取的主成分分析（PCA），然后，該算法將得到的區(qū)域劃分為不同類(lèi)型，并結(jié)合FSVM和kNN的特性，不同的分類(lèi)方法針對(duì)不同類(lèi)型。實(shí)驗(yàn)結(jié)果表明，該算法識(shí)別精度較為準(zhǔn)確，同時(shí)簡(jiǎn)化了計(jì)算時(shí)間復(fù)雜度。

Zhou[14]等提出了一種基于改進(jìn)的Gabor小波特征的主動(dòng)外觀模型（AAM），來(lái)提取面部特征點(diǎn)?；旌螦AM和它們的鄰居的特征點(diǎn)被認(rèn)為是一個(gè)分類(lèi)問(wèn)題，以得到進(jìn)一步完善的結(jié)果。即：提取特征點(diǎn)附近的Gabor特征，通過(guò)線性判別分析（LDA）進(jìn)行訓(xùn)練，并用kNN算法進(jìn)行分類(lèi)，得到特征點(diǎn)的精確位置。實(shí)驗(yàn)結(jié)果表明，該方法的準(zhǔn)確率較高，可以準(zhǔn)確地定位面部的特征。

Kamarol[15]等提出了一種基于kNN和加權(quán)方案的低復(fù)雜度的面部情緒識(shí)別和強(qiáng)度估計(jì)的新框架。該算法構(gòu)造了一種面部特征表示方法，并利用Hidden Markov模型將輸入視頻分類(lèi)為六種基本表達(dá)形式之一，即憤怒、厭惡、恐懼、幸福、悲傷和驚奇。然后用變點(diǎn)檢測(cè)器獲得表達(dá)式的時(shí)間段、中性點(diǎn)、起始點(diǎn)和頂點(diǎn)。

表2 kNN算法對(duì)于人臉識(shí)別的應(yīng)用分析

3.2 文字識(shí)別

楊麗華[16]等詳細(xì)地介紹文本的自動(dòng)分類(lèi)，文本分類(lèi)在實(shí)際生活中有著十分廣泛的應(yīng)用，這對(duì)于人們獲取信息有著極大的幫助。該文系統(tǒng)地介紹了kNN算法用于文本分類(lèi)的原理，歸納了各種kNN算法的改進(jìn)思路及算法，使得文本分類(lèi)的實(shí)驗(yàn)結(jié)果更為準(zhǔn)確。

為了使kNN算法在文本分類(lèi)中能夠更好地使用，周慶平[17]等提出一種基于聚類(lèi)的改進(jìn)kNN算法。在對(duì)文本進(jìn)行第一步——特征提取之后，根據(jù)聚類(lèi)算法把文本分成幾類(lèi)，再用改進(jìn)的kNN算法對(duì)這幾個(gè)類(lèi)進(jìn)行分類(lèi)。實(shí)驗(yàn)最后證明了，這個(gè)方法對(duì)于文本分類(lèi)有著很好的結(jié)果。

對(duì)于kNN算法沒(méi)有辦法同時(shí)滿足分類(lèi)速度和分類(lèi)精度都很好的這一不足之處，樊存佳[18]等提出使用改進(jìn)的K-Medoids聚類(lèi)算法剔除對(duì)kNN算法分類(lèi)沒(méi)有什么貢獻(xiàn)的訓(xùn)練樣本，以至于得以減少計(jì)算kNN相似度的時(shí)間和精力，對(duì)于k個(gè)最近鄰文本，定義代表度函數(shù)使其可以被有差別地處理。實(shí)驗(yàn)結(jié)果證明了，經(jīng)過(guò)改進(jìn)的kNN算法對(duì)于分類(lèi)的準(zhǔn)確度和減少時(shí)間復(fù)雜度均有著明顯提高。

Pang[19]等結(jié)合kNN和Rocchio提出了一個(gè)廣義的聚類(lèi)基于質(zhì)心的文本分類(lèi)器，基本思路為兩點(diǎn)：（1）使用聚類(lèi)算法來(lái)加強(qiáng)Rocchio模型的表現(xiàn)力，并構(gòu)建一個(gè)集群分類(lèi)模型；（2）采用改進(jìn)的Rocchio模型加快kNN分類(lèi)速度。實(shí)驗(yàn)證明文本分類(lèi)器的效果良好。

針對(duì)于伊朗車(chē)牌字符的識(shí)別，Tabrizi[20]等提供了一種新的方法，提高了車(chē)牌識(shí)別系統(tǒng)的識(shí)別精度，降低了識(shí)別系統(tǒng)的識(shí)別成本。在這方面，進(jìn)行了kNN算法和多類(lèi)支持向量機(jī)（kNN-SVM）模型的開(kāi)發(fā)研究，SVM模型提高了在相似字符識(shí)別kNN性能，該模型克服了車(chē)牌字符相似性問(wèn)題的混淆。

Jiang[21]等提出了一種改進(jìn)的kNN文本分類(lèi)算法，將約束單向聚類(lèi)算法與kNN文本分類(lèi)相結(jié)合，建立了一個(gè)分類(lèi)模型。對(duì)三個(gè)基準(zhǔn)語(yǔ)料庫(kù)的實(shí)證結(jié)果證明，該算法能有效地減少對(duì)于文本相似度的計(jì)算量，并且優(yōu)于當(dāng)前最先進(jìn)的kNN、樸素貝葉斯算法和SVM算法。此外，該算法構(gòu)造的分類(lèi)模型可以進(jìn)行增量式更新，在許多實(shí)際應(yīng)用中具有很大的可擴(kuò)展性。

Jindal[22]等提出了一種新的生物醫(yī)學(xué)領(lǐng)域文本分類(lèi)的方法——LKNN算法，其中L用來(lái)代表醫(yī)療文件。這些標(biāo)記用于將摘要與指定醫(yī)學(xué)主題標(biāo)題為網(wǎng)格的關(guān)鍵字的標(biāo)準(zhǔn)列表進(jìn)行匹配，它自動(dòng)將醫(yī)學(xué)領(lǐng)域的期刊文章分為特定的類(lèi)別。實(shí)驗(yàn)結(jié)果最終證明，LKNN算法在諸多方面均好于傳統(tǒng)的kNN算法。

Du[23]提出一種基于聚類(lèi)中心文本序列的并行MKNN算法來(lái)對(duì)文本進(jìn)行分類(lèi)。首先，基于聚類(lèi)中心實(shí)現(xiàn)了算法相似度計(jì)算量的有效降維；其次，MapReduce并行框架的作用是：用來(lái)滿足大規(guī)模文本分類(lèi)和計(jì)算結(jié)合文本分類(lèi)特征的實(shí)時(shí)需求；最后，該算法的分類(lèi)速度可以保證足夠的精度，比同類(lèi)單線程算法的文本分類(lèi)精度和算法效率都有提高。

Tan[24]對(duì)于因特網(wǎng)上文檔的指數(shù)增長(zhǎng)的問(wèn)題，引入了多種監(jiān)督學(xué)習(xí)算法來(lái)處理文本分類(lèi)問(wèn)題。其中，kNN算法的特性是簡(jiǎn)單、高效，在文本分類(lèi)領(lǐng)域的應(yīng)用較廣。作者提出了一種新的優(yōu)化策略，稱之為對(duì)kNN分類(lèi)器推拉。通過(guò)三基準(zhǔn)評(píng)價(jià)集的實(shí)驗(yàn)可以得出，推拉kNN分類(lèi)器在性能方面取得顯著改進(jìn)，好于傳統(tǒng)的kNN分類(lèi)器。

Trstenjak[25]等介紹了使用KNN算法和TF-IDF方法相結(jié)合構(gòu)造文本分類(lèi)框架的可能性?？蚣苣軌蚋鶕?jù)不同的參數(shù)來(lái)分類(lèi)，測(cè)量和分析得出的結(jié)果?？蚣艿脑u(píng)價(jià)主要集中在分類(lèi)的速度和質(zhì)量上。測(cè)試結(jié)果顯示了算法的優(yōu)缺點(diǎn)，為類(lèi)似框架的進(jìn)一步發(fā)展提供了指導(dǎo)。

Jo[26]提出了一個(gè)特定版本的kNN，其特征向量間的相似性考慮屬性或特征之間的相似性計(jì)算和其中的價(jià)值。在這項(xiàng)研究中，定義了考慮屬性和屬性值的相似性，將kNN修改為基于屬性相似性的版本，并使用修改后的版本作為文本摘要的方法，目的是實(shí)現(xiàn)更簡(jiǎn)潔、更可靠的表示數(shù)據(jù)項(xiàng)的文本摘要算法。

表3 kNN算法對(duì)于文字識(shí)別的應(yīng)用分析

3.3 醫(yī)學(xué)圖像處理

為了使醫(yī)生的負(fù)擔(dān)得以減輕，加快醫(yī)學(xué)發(fā)展的腳步，王清[27]等對(duì)于kNN算法進(jìn)行了改進(jìn)，并將其用在醫(yī)學(xué)領(lǐng)域，他們使用速度較快的k均值聚類(lèi)來(lái)獲取訓(xùn)練樣本，之后再用kNN算法對(duì)于未分類(lèi)的像素進(jìn)行分類(lèi)。實(shí)驗(yàn)結(jié)果表明該算法可以較好地識(shí)別出MRI圖相當(dāng)中的腦白質(zhì)、脊髓、灰質(zhì)三個(gè)部分的圖像。

孟志偉[28]等利用受限玻爾茲曼機(jī)（RBM）和kNN分類(lèi)器相結(jié)合的方法，主要思路是：（1）構(gòu)造可視層二值對(duì)于隱層二值的RBM，訓(xùn)練RBM得到特征提取器；（2）用該特征提取器來(lái)提取圖像的特征；（3）用kNN算法來(lái)分類(lèi)得到的特征。實(shí)驗(yàn)結(jié)果證明，該方法性能良好，且在分類(lèi)準(zhǔn)確率和分類(lèi)效率方面都有著較為明顯的提升。

當(dāng)前，紋理分析法是人們對(duì)于假指紋檢測(cè)使用的主要方法，然而這并不包括假指紋與人體指紋的差異所造成的噪聲分析。張永良[29]等針對(duì)于假指紋檢測(cè)，提出了一種SVM-kNN的分類(lèi)算法，該算法利用曲波系數(shù)特征及曲波重構(gòu)圖像紋理特征來(lái)實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果證明該算法比LBP、SSCA等算法性能更優(yōu)。

糖尿病視網(wǎng)膜病變是導(dǎo)致病人失去光明的新病例病因之一。在得病的早期，能夠準(zhǔn)確檢測(cè)微動(dòng)脈瘤（MAs）來(lái)診斷糖尿病視網(wǎng)膜病變的分級(jí)是有著非常重大意義的。Wu[30]等介紹了一個(gè)自動(dòng)檢測(cè)眼底圖像中多智能體的方法。該方法包括四個(gè)主要步驟：預(yù)處理、候選提取、特征提取和分類(lèi)。提取了局部特征和輪廓特征，用kNN分類(lèi)器區(qū)分真假M(fèi)As。實(shí)驗(yàn)結(jié)果表明，該方法非常高效，對(duì)臨床診斷具有很大的幫助。

Jung[31]等對(duì)于開(kāi)發(fā)心律失常檢測(cè)技術(shù)做出了很大的努力，通過(guò)主成分分析（PCA）方法來(lái)提取系數(shù)和線性判別分析（LDA）方法加強(qiáng)原始信號(hào)的典型特征，采用加權(quán)kNN的加權(quán)值來(lái)控制降低靈敏度，這取決于算法中k的大小，之后再應(yīng)用適應(yīng)度規(guī)則來(lái)提高心律失常分類(lèi)準(zhǔn)確率。

Sudharani[32]評(píng)估了對(duì)于腦卒中圖像k-最近鄰分類(lèi)器（kNN）和最小平均距離分類(lèi)器（MMD）的相對(duì)性能，是一種完全自動(dòng)化的方法來(lái)識(shí)別和分類(lèi)腦卒中的不規(guī)則（出血），當(dāng)大腦供血停止時(shí)，腦卒中就發(fā)生了。實(shí)驗(yàn)證明，kNN方法的識(shí)別率大于MMD的識(shí)別率，并且這兩種方法的識(shí)別率都高于歐幾里德和曼哈頓度量的求和。

Rajini[33]等提出了一種基于磁共振圖像分類(lèi)的自動(dòng)診斷方法。該方法分為特征提取和分類(lèi)兩個(gè)階段。在第一階段中，利用離散小波變換（DWT）獲得與MRI圖像相關(guān)的特征，之后利用主成分分析（PCA）對(duì)磁共振圖像的小波變換特征進(jìn)行了提取，得到了更為重要的特征；在分類(lèi)階段有兩個(gè)分類(lèi)器：第一個(gè)分類(lèi)器是前饋BP人工神經(jīng)網(wǎng)絡(luò)（FP-ANN）、第二分類(lèi)器是kNN算法。根據(jù)這些特征，能夠訓(xùn)練出一個(gè)基于神經(jīng)網(wǎng)絡(luò)的二值分類(lèi)器，它能自動(dòng)判斷圖像是正常腦或病腦，以及是否患有腦損傷。

Machhale[34]等提出了一種識(shí)別正常和異常腦MRI圖像的智能分類(lèi)系統(tǒng)。在本文實(shí)驗(yàn)中，采用了各種技術(shù)對(duì)腦癌進(jìn)行分類(lèi)。在此基礎(chǔ)上，成功地完成了腦腫瘤的圖像預(yù)處理、圖像特征提取和分類(lèi)檢測(cè)。對(duì)比了SVM、kNN以及SVM-kNN這些機(jī)器學(xué)習(xí)技術(shù)，其中SVM-kNN表現(xiàn)出最高的分類(lèi)準(zhǔn)確率。

Zhong[35]等提出了一種基于kNN的MRI數(shù)據(jù)CT圖像的預(yù)測(cè)方法。在該方法中，在約束空間范圍內(nèi)搜索每個(gè)MR圖像補(bǔ)丁的最近鄰，為了提高準(zhǔn)確性和預(yù)測(cè)效率，作者建議使用基于低秩逼近和流形正則化優(yōu)化的有監(jiān)督的描述符來(lái)優(yōu)化一個(gè)MR局部描述符和降維。結(jié)果表明，該方法能有效地預(yù)測(cè)CT數(shù)據(jù)，優(yōu)于兩種最新的CT預(yù)測(cè)方法。

對(duì)于同一個(gè)數(shù)據(jù)集，de Bresser[36]等將最近流行的幾個(gè)方法：SIENA，US以及kNN進(jìn)行了對(duì)比，得出了以下結(jié)論：US和kNN對(duì)腦容量測(cè)量有很好的精確性、準(zhǔn)確性和可比性，對(duì)于體積變化的測(cè)量，SIENA顯示出最好的性能?？傊?，在其他大腦結(jié)構(gòu)的體積變化測(cè)量是必需的情況下，kNN是最佳選擇。

表4 kNN算法對(duì)于醫(yī)學(xué)圖像處理的應(yīng)用分析

4 kNN算法改進(jìn)

雖然kNN算法優(yōu)點(diǎn)非常明顯，但其仍有不可忽視的缺點(diǎn)，比如：當(dāng)數(shù)據(jù)集非常龐大的時(shí)候，計(jì)算會(huì)非常耗時(shí)，其時(shí)間和空間復(fù)雜度都很高。針對(duì)這一缺點(diǎn)，許多的專家學(xué)者都提出了改進(jìn)的算法，比如Fuzzy-kNN算法[37]，該方法適用于數(shù)據(jù)量非常龐大的數(shù)據(jù)集。它可以正確界定分類(lèi)問(wèn)題的實(shí)例和類(lèi)關(guān)系表現(xiàn)的幾種機(jī)制，是基于Fuzzy-kNN兩個(gè)關(guān)鍵參數(shù)的多項(xiàng)選擇表示：一個(gè)應(yīng)用于隸屬函數(shù)的定義，另一種用于分類(lèi)規(guī)則，該算法提高了分類(lèi)的準(zhǔn)確性，減少了分類(lèi)時(shí)間，優(yōu)于傳統(tǒng)的kNN算法。

kNN算法在一些問(wèn)題的處理和分類(lèi)上，無(wú)法為不可見(jiàn)的實(shí)例確定標(biāo)簽集。針對(duì)于這一缺點(diǎn)的改進(jìn)主要有多標(biāo)簽學(xué)習(xí)kNN算法[38]。對(duì)于每個(gè)看不見(jiàn)的實(shí)例，它在訓(xùn)練集中的k最近的鄰居都是第一個(gè)被識(shí)別的，在此之后，根據(jù)這些相鄰實(shí)例的標(biāo)簽集獲得的統(tǒng)計(jì)信息，即每個(gè)可能類(lèi)的相鄰實(shí)例的數(shù)量，最大限度地利用后面的（MAP）原則來(lái)確定未被發(fā)現(xiàn)的實(shí)例的標(biāo)簽集。該算法在一些已建立的多標(biāo)簽學(xué)習(xí)算法中取得了十分優(yōu)異的性能。

kNN算法基于VSM模型，利用歐氏距離或余弦距離來(lái)度量樣本的距離，但權(quán)重不變，這與實(shí)際情況不符。針對(duì)于這一缺點(diǎn)的改進(jìn)主要有加權(quán)kNN算法[39]。它根據(jù)樣本點(diǎn)之間的距離來(lái)分配一個(gè)權(quán)重，權(quán)重的大小隨距離的減小而增大。與標(biāo)準(zhǔn)kNN相比，權(quán)重的引入提高了分類(lèi)性能，原因是訓(xùn)練樣本更接近對(duì)象，因此它們更可能被分類(lèi)在同一類(lèi)中。因此，加權(quán)kNN的分類(lèi)準(zhǔn)確度通常情況下比傳統(tǒng)的kNN算法要好很多。

傳統(tǒng)的kNN算法在相似度測(cè)量上以及親和力方面仍有著許多不足之處，針對(duì)于這一點(diǎn)的改進(jìn)主要有親和力為基礎(chǔ)的新的局部距離函數(shù)和相似性度量的改進(jìn)kNN算法[40]。設(shè)計(jì)了一種基于新的親和距離函數(shù)的相似度測(cè)量函數(shù)，提出kNN算法實(shí)現(xiàn)附近水平學(xué)習(xí)而構(gòu)建的功能即：接近的距離和相似度函數(shù)，它也可以被歸類(lèi)為一個(gè)局部自適應(yīng)的kNN算法。上述修改對(duì)算法性能的影響很大，實(shí)驗(yàn)結(jié)果表明，該方法優(yōu)于kNN算法的一些知名的變體。

在移動(dòng)的計(jì)算環(huán)境中，所有的移動(dòng)用戶在網(wǎng)絡(luò)中的一個(gè)指定時(shí)間持續(xù)監(jiān)控kNN的結(jié)果是一種空間查詢，這就帶來(lái)了一個(gè)問(wèn)題：一個(gè)節(jié)點(diǎn)的單個(gè)運(yùn)動(dòng)可能導(dǎo)致幾個(gè)用戶不得不重新計(jì)算他們的kNN結(jié)果。針對(duì)于這一點(diǎn)，桶點(diǎn)區(qū)域的移動(dòng)用戶使用四叉樹(shù)索引來(lái)對(duì)kNN算法進(jìn)行了改進(jìn)[41]，一種新的Reverse-kNN技術(shù)被提出以維護(hù)開(kāi)銷(xiāo)，這有助于快速確定這些節(jié)點(diǎn)中的每一個(gè)合適的搜索半徑，便于查詢結(jié)果的連續(xù)監(jiān)測(cè)。

此外，針對(duì)不同的實(shí)際問(wèn)題，還有許多kNN算法與其他算法相融合的改進(jìn)，這些改進(jìn)都提高了傳統(tǒng)的kNN算法的性能，降低了其時(shí)間和空間復(fù)雜度，為各種分類(lèi)問(wèn)題提供了思路和解決方法，值得學(xué)習(xí)和研究。

5 kNN算法與SVM算法的對(duì)比與分析

kNN算法是一種取決于統(tǒng)計(jì)的懶惰學(xué)習(xí)算法，它讀取一組標(biāo)記訓(xùn)練集，然后用它對(duì)未標(biāo)記的測(cè)試集進(jìn)行分類(lèi)；然而，它有一個(gè)選擇k的最佳值的問(wèn)題，這可以通過(guò)做實(shí)驗(yàn)來(lái)測(cè)試k的不同值并選擇性能最好的值來(lái)實(shí)現(xiàn)。SVM算法是從一組標(biāo)記的訓(xùn)練數(shù)據(jù)生成函數(shù)的方法，該函數(shù)可以是一個(gè)分類(lèi)函數(shù)，也可以是一般的回歸函數(shù)；在分類(lèi)方面，SVM算法是在可能的輸入空間找到一個(gè)超曲面，但是這就使得分類(lèi)的正確率接近測(cè)試數(shù)據(jù)但是與訓(xùn)練數(shù)據(jù)并不一致。針對(duì)不同的數(shù)據(jù)集，兩種算法有著不同的表現(xiàn)，在微型精密值方面，kNN算法較為優(yōu)異；當(dāng)特征數(shù)量很高時(shí)，SVM表現(xiàn)出更好的性能；但是kNN算法的計(jì)算簡(jiǎn)單，效率很高，復(fù)雜度方面優(yōu)于SVM算法[42]。

6 總結(jié)與展望

本文詳細(xì)地介紹了kNN算法的基本原理，以及國(guó)內(nèi)外學(xué)者對(duì)于其在不同領(lǐng)域的應(yīng)用，并且對(duì)比分析了kNN算法與其他分類(lèi)算法。目前，kNN算法已被廣泛應(yīng)用于人臉識(shí)別、文字識(shí)別和醫(yī)學(xué)圖像處理等領(lǐng)域中，并且取得了一定的成果，對(duì)人類(lèi)生活有著很大的幫助?？傊?，kNN算法是一個(gè)功能很強(qiáng)大的分類(lèi)算法，在今后的研究中，需要對(duì)其進(jìn)行改進(jìn)以使其可以針對(duì)不同的問(wèn)題都有一個(gè)良好的分類(lèi)結(jié)果，如何利用kNN算法在新興領(lǐng)域等方面做進(jìn)一步的改進(jìn)依然是一個(gè)研究熱點(diǎn)。

[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]楊淑平，易國(guó)棟，袁修貴，等.一種基于分塊小波的人臉識(shí)別算法[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，44（5）：1902-1909.

[12]王小虎，黃銀珍，張石清.結(jié)合FSVM和KNN的人臉表情識(shí)別[J].微電子學(xué)與計(jì)算機(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文本分類(lèi)算法研究[J].微計(jì)算機(jī)信息，2006，22（21）：269-270.

[17]周慶平，譚長(zhǎng)庚，王宏君，等.基于聚類(lèi)改進(jìn)的KNN文本分類(lèi)算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（11）：3374-3377.

[18]樊存佳，汪友生，邊航.一種改進(jìn)的KNN文本分類(lèi)算法[J].國(guó)外電子測(cè)量技術(shù)，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]王清，馬華，孫靜，等.改進(jìn)的KNN算法及其在醫(yī)學(xué)圖像處理中的應(yīng)用[J].泰山醫(yī)學(xué)院學(xué)報(bào)，2006，27（6）：564-566.

[28]孟志偉，劉惠義，陳霜霜.基于RBM_KNN的腦部磁共振圖像分類(lèi)[J].信息技術(shù)，2017（4）：169-173.

[29]張永良，劉超凡，肖剛，等.基于曲波紋理分析和SVM_KNN分類(lèi)的假指紋檢測(cè)算法[J].計(jì)算機(jī)科學(xué)，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

國(guó)家自然科學(xué)基金（No.61602250，No.61503188）；江蘇省自然科學(xué)基金（No.BK20150983，No.BK20150982）；江蘇省高校自然科學(xué)研究面上項(xiàng)目（No.16KJB520025，No.15KJB470010）。

毋雪雁（1993—），女，碩士生，研究方向：模式識(shí)別；王水花（1985—），女，講師，研究方向：模式識(shí)別；張煜東（1985—），男，教授，博導(dǎo)，研究方向：人工智能與醫(yī)學(xué)圖像處理，E-mail：yudongzhang@ieee.org。

2017-07-13

2017-09-18

1002-8331（2017）21-0001-07