基于局部保持的KNN算法

(西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039)

·計(jì)算機(jī)軟件理論、技術(shù)與應(yīng)用·

基于局部保持的KNN算法

曾俊杰，王曉明*，楊曉歡

(西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039)

距離度量對(duì)K近鄰(KNN)算法分類(lèi)精度起著重要的作用。傳統(tǒng)KNN算法通常采用歐氏距離，但該距離將所有特征的差別平等對(duì)待，忽略了數(shù)據(jù)的局部?jī)?nèi)在幾何結(jié)構(gòu)特征。針對(duì)此問(wèn)題，文章借鑒局部保持投影(LPP)的基本思想，在考慮數(shù)據(jù)的局部?jī)?nèi)在幾何結(jié)構(gòu)特征基礎(chǔ)上，依據(jù)類(lèi)內(nèi)局部保持散度矩陣構(gòu)造一種距離度量新方法，利用該距離度量提出一種局部保持K近鄰算法。實(shí)驗(yàn)結(jié)果表明，與采用歐氏距離和傳統(tǒng)馬氏距離的KNN相比，本算法能夠得到更好的分類(lèi)精度。

K-近鄰;局部保持投影;馬氏距離

分類(lèi)不僅在模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和人工智能等相關(guān)領(lǐng)域有廣泛的研究，而且在醫(yī)療診斷、信用評(píng)估、選擇購(gòu)物等生活實(shí)踐中也得到了廣泛的應(yīng)用。K近鄰(K-nearest neighbor，KNN)算法[1-2]具有直觀、簡(jiǎn)單、有效、易實(shí)現(xiàn)等特點(diǎn)，成為分類(lèi)算法中比較常用的算法之一。該算法由Cover和Hart在1967年提出，是一種基于向量空間模型的算法，通過(guò)計(jì)算向量之間的相似度來(lái)確定待分類(lèi)對(duì)象的類(lèi)別。與其他分類(lèi)算法不同，KNN算法不用提前設(shè)計(jì)出分類(lèi)器。同時(shí)，該方法對(duì)較復(fù)雜的問(wèn)題也有很好的分類(lèi)能力。

KNN中距離度量[3-4]的設(shè)計(jì)會(huì)直接影響該分類(lèi)算法的性能。傳統(tǒng)的KNN算法采用歐氏距離[5]，這種距離度量本質(zhì)上會(huì)賦予每個(gè)屬性相等的權(quán)值，這樣近鄰間的距離會(huì)被大量的不相關(guān)屬性所支配，分類(lèi)效果就會(huì)受到很大的影響。為了克服這個(gè)缺點(diǎn)，盧偉勝等[6]構(gòu)造了加權(quán)的歐氏距離，它既能消除冗余或無(wú)用屬性對(duì)分類(lèi)算法依賴的距離度量的影響，又能較好地消除鄰居中的噪聲點(diǎn)，從而提高算法的分類(lèi)效果；侯玉婷等[7]則提出了一種自適應(yīng)加權(quán)K-近鄰分類(lèi)方法，通過(guò)對(duì)不同特征分別進(jìn)行加權(quán)，可以有效提高自然圖像的分類(lèi)性能。馬氏距離[8-9]與歐氏距離相比較，它不受量綱的影響，并且可以反映樣本間的差別。Zhang等[10]提出一種基于傳統(tǒng)馬氏距離的KNN算法(MKNN)，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的優(yōu)越性，但是馬氏距離夸大了微小變量的作用。韓涵等[11]就此不足提出一種加權(quán)的馬氏距離改進(jìn)算法，并得到了較好的測(cè)試效果。此外，肖輝輝等[12]還定義2個(gè)樣本間的距離為屬性值的相關(guān)距離，以此距離來(lái)有效度量樣本間的相似度，從而提高了算法的分類(lèi)準(zhǔn)確性。上述文獻(xiàn)對(duì)KNN算法的距離度量做了各種改進(jìn)，使該算法的分類(lèi)效果得到一定程度的提高；但是它們考慮的是樣本的總體分布，忽略了數(shù)據(jù)的局部?jī)?nèi)在幾何結(jié)構(gòu)特征。

在2003年，一種叫作局部保持投影[13-14](locality preserving projections，LPP)的無(wú)監(jiān)督特征降維算法被提出。該算法備受關(guān)注，是一種特殊的線性流行學(xué)習(xí)方法，其顯著特點(diǎn)就是在維數(shù)壓縮的過(guò)程中充分利用數(shù)據(jù)的局部?jī)?nèi)在幾何結(jié)構(gòu)信息或流形結(jié)構(gòu)特征。

針對(duì)KNN的上述問(wèn)題，本文借鑒LPP的基本思想，提出了一種新穎的KNN算法。首先，根據(jù)類(lèi)內(nèi)局部保持散度矩陣構(gòu)造了一種新的距離度量方式，然后利用該方式提出了局部保持K近鄰算法(locality preservingK-nearest neighbor, LPKNN)。LPKNN采用新的距離度量方式，利用充分反映數(shù)據(jù)內(nèi)在幾何結(jié)構(gòu)特征的類(lèi)內(nèi)局部保持散度矩陣；因此，相對(duì)于KNN和MKNN算法，LPKNN算法最顯著的特點(diǎn)是充分考慮了每一類(lèi)數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)信息，并且該方法利用數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)特征，不同于原始的LPP。LPP屬于無(wú)監(jiān)督方法，沒(méi)有考慮數(shù)據(jù)的類(lèi)別信息，而本文定義的類(lèi)內(nèi)局部保持散度矩陣使用了數(shù)據(jù)的類(lèi)標(biāo)，屬于監(jiān)督方法。實(shí)驗(yàn)結(jié)果顯示，相對(duì)于KNN和MKNN，LPKNN表現(xiàn)出更好的分類(lèi)精度。

1 相關(guān)準(zhǔn)備工作

在本文內(nèi)容中，假定有由M個(gè)樣本組成的訓(xùn)練數(shù)據(jù)集X=[x1,…,xM]和N個(gè)樣本組成的測(cè)試數(shù)據(jù)集Y=[y1,…,yN]， ?xi,yj∈RP,X∈RP×M,Y∈RP×N。把訓(xùn)練數(shù)據(jù)集X劃分到C個(gè)不同的類(lèi)別，并用Xm表示第m(m=1,…,C)類(lèi)數(shù)據(jù)子集，共包含Nm個(gè)樣本。

1.1 KNN分類(lèi)算法

KNN是模式識(shí)別非參數(shù)分類(lèi)算法中最重要的方法之一。它的工作原理是首先找到待分類(lèi)對(duì)象在訓(xùn)練數(shù)據(jù)集中的K個(gè)最近的鄰居,然后根據(jù)這些鄰居的分類(lèi)屬性進(jìn)行投票,將得出的預(yù)測(cè)值賦給待分類(lèi)對(duì)象的分類(lèi)屬性。歐氏距離和馬氏距離是KNN算法中常見(jiàn)的距離度量。其計(jì)算公式為：

d(yi,xmj)2=(yi-xmj)T(yi-xmj)；

(1)

dM(yi,xmj)2=(yi-xmj)TS-1(yi-xmj)。

(2)

式中：S是訓(xùn)練數(shù)據(jù)集X的協(xié)方差矩陣；xmj表示的是第m(m=1,…,C)類(lèi)數(shù)據(jù)子集Xm的第j個(gè)數(shù)據(jù)。

式(1)的歐氏距離是衡量多維空間中各個(gè)點(diǎn)之間的絕對(duì)距離，是最常用的距離。使用歐氏距離的分類(lèi)算法大多只能發(fā)現(xiàn)低維空間中呈超球狀分布的數(shù)據(jù)，它的缺點(diǎn)是將樣品的不同屬性之間的差別等同看待。式(2)的馬氏距離與歐氏距離不同，它可以排除變量之間的相關(guān)性干擾，并且不受量綱的影響；但是它會(huì)夸大變化微小的變量的作用。

1.2局部保持投影

局部保持投影(LPP)算法是通過(guò)構(gòu)造數(shù)據(jù)集所對(duì)應(yīng)的k-近鄰圖來(lái)保持樣本的局部?jī)?nèi)在幾何結(jié)構(gòu)信息。該算法是通過(guò)提取最具有判別性的特征來(lái)進(jìn)行降維，因此在保留局部特征時(shí)具有明顯的優(yōu)勢(shì)。設(shè)w為權(quán)值矩陣，a為投影向量，LPP的目標(biāo)函數(shù)為

(3)

(4)

s.t.aTXDXTa=1。

(5)

其中D為對(duì)角矩陣，Dii=∑jWij(W為對(duì)稱(chēng)陣)，Dii越大，表示xi越重要。L=D-W,被稱(chēng)作拉普拉斯矩陣。約束式(5)是為了避免a=0這個(gè)解。投影矩陣a可以通過(guò)求解目標(biāo)函數(shù)最小化的廣義特征值問(wèn)題對(duì)應(yīng)的特征向量得到。

2 基于局部保持的KNN算法

2.1類(lèi)內(nèi)局部保持散度矩陣

本節(jié)給出了文獻(xiàn)[15]中引出的相關(guān)概念。本文后續(xù)部分將直接使用這些定義。

定義1 假定L是定義在數(shù)據(jù)集X上的拉普拉斯矩陣，則把矩陣Z=XLXT=X(D-W)XT叫作數(shù)據(jù)集X上的局部保持散度矩陣。

定義2 假定數(shù)據(jù)集X含有C類(lèi)數(shù)據(jù)集，則把矩陣

(6)

(7)

2.2基于局部保持的馬氏距離

結(jié)合LPP算法的思想,利用類(lèi)內(nèi)局部保持散度矩陣,構(gòu)造一個(gè)能夠反映數(shù)據(jù)內(nèi)在結(jié)構(gòu)特征的新距離度量公式，為

dLP(yi,xmj)2=(yi-xmj)TZw-1(yi-xmj)。

(8)

其中Zw是訓(xùn)練數(shù)據(jù)集X上的類(lèi)內(nèi)局部保持散度矩陣。

根據(jù)前面的描述，可以明顯的看出，歐氏距離、馬氏距離與基于類(lèi)內(nèi)局部保持散度矩陣的馬氏距離的不同。歐氏距離矩陣將所有特征間的差別平等對(duì)待，馬氏距離矩陣僅考慮數(shù)據(jù)的分布信息，它們都忽略了其內(nèi)部幾何結(jié)構(gòu)特征；而基于類(lèi)內(nèi)局部保持散度矩陣的馬氏距離是借鑒LPP算法的基本思想進(jìn)行定義的,相對(duì)于歐氏距離和傳統(tǒng)馬氏距離，它不僅保持了數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)特征還具有鑒別信息的作用。這也是它與LPP定義權(quán)值矩陣功能最大的不同。

2.3基于局部保持的KNN算法

式(8)定義的新距離度量能夠反映每一類(lèi)數(shù)據(jù)的局部?jī)?nèi)在幾何結(jié)構(gòu)特征，在本小節(jié)中,將該距離度量運(yùn)用到KNN算法中，便得到本文提出的局部保持K近鄰算法。

LPKNN算法的分類(lèi)決策過(guò)程如下：對(duì)于一個(gè)給定的測(cè)試數(shù)據(jù)yi，分別計(jì)算它與訓(xùn)練數(shù)據(jù)集X中每一個(gè)訓(xùn)練數(shù)據(jù)的距離，找到與之最近的K(K≥1)個(gè)訓(xùn)練數(shù)據(jù)，其中屬于第m類(lèi)的數(shù)據(jù)有Km個(gè)，判別函數(shù)為

(9)

其中dLP(yi,xmj)為測(cè)試數(shù)據(jù)yi與訓(xùn)練數(shù)據(jù)xmj之間的距離，如式(8)所示。按式(10)決策測(cè)試數(shù)據(jù)yi屬于第m類(lèi)。

fm(yi)=arg max(gm(yi))。

(10)

通過(guò)上述分析，算法步驟簡(jiǎn)單描述如下。

Step1：計(jì)算測(cè)試數(shù)據(jù)集Y中對(duì)象yi與訓(xùn)練數(shù)據(jù)集X中每個(gè)對(duì)象的距離，距離度量公式采用式(8)。

Step2：找出yi與X中距離最近的K個(gè)對(duì)象。

Step3：依次統(tǒng)計(jì)出這K個(gè)對(duì)象的所屬類(lèi)別，找出包含最多個(gè)數(shù)的類(lèi)。

Step4：將yi劃分到此類(lèi)中。

Step5：重復(fù)以上步驟，直到所有測(cè)試數(shù)據(jù)分類(lèi)結(jié)束。

Step6：輸出標(biāo)志后的測(cè)試集Y。

這里，可以清晰地看出KNN、MKNN和LPKNN3種算法的不同。KNN算法直接采用歐氏距離矩陣，沒(méi)有考慮數(shù)據(jù)的特征；MKNN算法采用基于數(shù)據(jù)協(xié)方差矩陣的馬氏距離來(lái)利用數(shù)據(jù)的分布特征； LPKNN算法借鑒MKNN利用數(shù)據(jù)分布特征的方式，采用了基于類(lèi)內(nèi)局部保持散度矩陣的馬氏距離，達(dá)到了充分考慮數(shù)據(jù)內(nèi)在幾何結(jié)構(gòu)特征的目的，而且在LPKNN算法采用的類(lèi)內(nèi)局部保持散度矩陣中，利用了數(shù)據(jù)的類(lèi)別信息。

2.4矩陣奇異問(wèn)題

LPKNN算法和MKNN算法一樣，最大的缺點(diǎn)就是會(huì)遇到一種所謂的小樣本問(wèn)題[16]，即樣本的維數(shù)大于樣本的個(gè)數(shù)。在運(yùn)行這2種算法時(shí)，基于類(lèi)內(nèi)局部保持散度矩陣的馬氏距離中的Zw和傳統(tǒng)馬氏距離中的協(xié)方差矩陣S都是P×P矩陣，都會(huì)出現(xiàn)奇異。除此之外，當(dāng)樣本維數(shù)小于樣本個(gè)數(shù)時(shí)也可能會(huì)出現(xiàn)奇異。

為了解決矩陣奇異這個(gè)問(wèn)題，可以采用以下幾種方法：求矩陣Zw和S的偽逆矩陣；將矩陣Zw和S正則化；用特征降維算法PCA[17]將樣本空間中的數(shù)據(jù)轉(zhuǎn)換到低維空間中。這樣矩陣Zw和S就不再是奇異的了。本文采用PCA特征降維算法來(lái)解決矩陣的奇異問(wèn)題。

3 實(shí)驗(yàn)研究

為了驗(yàn)證LPKNN算法的可行性及分類(lèi)效果，在實(shí)驗(yàn)中，將其與KNN和MKNN算法進(jìn)行了比較。實(shí)驗(yàn)分為3部分：第1部分實(shí)驗(yàn)采用人工擬合數(shù)據(jù)進(jìn)行測(cè)試；第2部分主要針對(duì)UCI(University of California，Irvine)[18]中的部分?jǐn)?shù)據(jù)集進(jìn)行測(cè)試；第3部分采用ORL人臉數(shù)據(jù)集進(jìn)行測(cè)試。

3.1擬合數(shù)據(jù)

人工擬合數(shù)據(jù)由two moons數(shù)據(jù)集和2個(gè)測(cè)試點(diǎn)組成，two moons數(shù)據(jù)集具有明顯非線性流行結(jié)構(gòu)，如圖1(a)所示。從理論上講，歐式空間是線性的黎曼流行空間，而非線性黎曼流行空間是典型的非歐式空間，所以蘊(yùn)含非線性流行結(jié)構(gòu)的two moons數(shù)據(jù)集是非歐式空間[19]；因此，通過(guò)測(cè)試2個(gè)數(shù)據(jù)點(diǎn)屬于two moons數(shù)據(jù)集的哪一類(lèi)來(lái)表明本文算法在處理數(shù)據(jù)內(nèi)在幾何結(jié)構(gòu)特征空間時(shí)的有效性。

圖1給出了原始擬合數(shù)據(jù)以及該數(shù)據(jù)在k為3到10的范圍內(nèi)變化時(shí)3種算法下的測(cè)試結(jié)果。此外，LPKNN算法中的k-近鄰參數(shù)為3，t-熱內(nèi)核參數(shù)為4。圖1(a)是擬合的two moons數(shù)據(jù)集及2個(gè)測(cè)試點(diǎn);圖1(b)是KNN算法的測(cè)試結(jié)果;圖1(c)是MKNN算法的測(cè)試結(jié)果;圖1(d)是LPKNN算法的測(cè)試結(jié)果。

不難發(fā)現(xiàn)，在使用歐氏距離和傳統(tǒng)馬氏距離的KNN算法時(shí)testpoint1被分類(lèi)給data1，testpoint2被分類(lèi)給data2，而采用LPKNN算法時(shí)testpoint1被分類(lèi)給data2，testpoint2被分類(lèi)給data1。由觀察數(shù)據(jù)可知，testpoint1被分類(lèi)給data2和testpoint2被分類(lèi)給data1是two moons數(shù)據(jù)集延伸的必然趨勢(shì)，故更具合理性。這也證明了采用歐氏距離的KNN算法反映的是2點(diǎn)之間的絕對(duì)距離，采用傳統(tǒng)馬氏距離的KNN算法考慮的是數(shù)據(jù)的分布信息，它們都忽略了LPKNN算法中具有的數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)特征。

(a) two moons數(shù)據(jù)集及測(cè)試點(diǎn)

(b) KNN分類(lèi)結(jié)果

(c) MKNN分類(lèi)結(jié)果

(d) LPKNN分類(lèi)結(jié)果

3.2 UCI數(shù)據(jù)

在這一部分的實(shí)驗(yàn)中，采用10個(gè)UCI數(shù)據(jù)來(lái)比較LPKNN與KNN和MKNN的分類(lèi)性能。表1描述了這些數(shù)據(jù)的基本信息。

設(shè)定3種算法都有的近鄰參數(shù)K=5。此外，在LPKNN算法中需要構(gòu)造權(quán)值矩陣Wm，其中的參數(shù)k、t的變化范圍分別為{3,4,5,6,7,8,9,10}和{0.25,0.5,1,2,4,8,16,32}。采用5重交叉測(cè)試[20](5-fold cross validation)來(lái)進(jìn)行參數(shù)選擇。5重交叉測(cè)試就是把所有的訓(xùn)練數(shù)據(jù)隨機(jī)地分成5個(gè)互不相交的子集，每個(gè)子集的大小大致相等，然后進(jìn)行5次訓(xùn)練測(cè)試，最后計(jì)算出這5次訓(xùn)練測(cè)試的平均精度,并將其作為參數(shù)選擇的評(píng)估準(zhǔn)則。

表1 實(shí)驗(yàn)中UCI數(shù)據(jù)集的基本信息

實(shí)驗(yàn)中，隨機(jī)選取數(shù)據(jù)的80%作為訓(xùn)練數(shù)據(jù)，剩下的作為測(cè)試數(shù)據(jù)。首先把訓(xùn)練數(shù)據(jù)的每一維特征處理成均值為0，方差為1，再根據(jù)同樣的規(guī)則處理測(cè)試數(shù)據(jù)；然后將訓(xùn)練數(shù)據(jù)進(jìn)行5重交叉測(cè)試；最后利用得到的參數(shù)對(duì)訓(xùn)練和測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。重復(fù)該過(guò)程20次,并把所得分類(lèi)精度的平均值作為算法的評(píng)價(jià)指標(biāo)。UCI數(shù)據(jù)集上20次測(cè)試的平均精度和標(biāo)準(zhǔn)偏差在表2中給出。

表2 UCI數(shù)據(jù)集上20次測(cè)試的平均精度和標(biāo)準(zhǔn)偏差 %

從這些實(shí)驗(yàn)結(jié)果可以看出，總體上LPKNN都表現(xiàn)出了比KNN和MKNN更好的分類(lèi)效果，這說(shuō)明當(dāng)充分利用了每一類(lèi)數(shù)據(jù)的局部?jī)?nèi)在幾何結(jié)構(gòu)信息時(shí)，有利于提高算法的分類(lèi)精度。盡管MKNN考慮了數(shù)據(jù)的分布信息，但是相對(duì)于KNN的實(shí)驗(yàn)結(jié)果，在大多數(shù)情況下的分類(lèi)精度都表現(xiàn)得更低。這可能是由于數(shù)據(jù)的分布特征造成的。

3.3人臉數(shù)據(jù)

為了測(cè)試在小樣本情況下LPKNN算法的分類(lèi)效果，在這一部分的實(shí)驗(yàn)中采用ORL人臉數(shù)據(jù)來(lái)進(jìn)行實(shí)驗(yàn)研究。ORL人臉數(shù)據(jù)包括40個(gè)人共400張灰度圖片，每人有10張分辨率為32×32的人臉圖像。ORL處理后的matlab數(shù)據(jù)可從http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html處下載。圖2為經(jīng)過(guò)預(yù)處理后的部分人臉圖像。測(cè)試之前所有的數(shù)據(jù)都被歸一化為0到1之間。

圖2 ORL預(yù)處理后的部分人臉圖像

由于是小樣本數(shù)據(jù)，MKNN算法和LPKNN算法都分別遭遇了協(xié)方差矩陣S和類(lèi)內(nèi)局部保持散度矩陣Zw的奇異性問(wèn)題，因此采用PCA降維算法來(lái)對(duì)數(shù)據(jù)進(jìn)行維數(shù)壓縮，在壓縮后的數(shù)據(jù)空間中運(yùn)行這2種算法。KNN算法則不存在這樣的問(wèn)題。

由于人臉數(shù)據(jù)每一類(lèi)的樣本個(gè)數(shù)較少，因此，設(shè)定3種算法都有的近鄰參數(shù)K=1。對(duì)于LPKNN中權(quán)值矩陣Wm的參數(shù)k、t的變化范圍分別是{3,4,5,6}和{5,10,20,30,40}。同樣采用5重交叉測(cè)試進(jìn)行參數(shù)選擇。實(shí)驗(yàn)中，首先隨機(jī)選取數(shù)據(jù)的80%作為訓(xùn)練數(shù)據(jù)，其余為測(cè)試數(shù)據(jù)；然后將訓(xùn)練數(shù)據(jù)進(jìn)行5重交叉測(cè)試；最后對(duì)訓(xùn)練和測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。此過(guò)程也重復(fù)20次，將分類(lèi)精度的平均值作為算法的評(píng)價(jià)指標(biāo)。表3給出了不同維數(shù)下ORL數(shù)據(jù)的測(cè)試結(jié)果，同時(shí)給出了采用KNN算法直接在樣本空間或特征空間中進(jìn)行測(cè)試的結(jié)果。

表3 ORL人臉數(shù)據(jù)上5重交叉測(cè)試的平均精度和標(biāo)準(zhǔn)偏差 %

從這些實(shí)驗(yàn)結(jié)果中可以看出： 1)在每一維上LPKNN算法比KNN和MKNN都體現(xiàn)出了更好的分類(lèi)精度且隨著維數(shù)增加分類(lèi)精度逐漸提高，這說(shuō)明考慮了數(shù)據(jù)內(nèi)在幾何結(jié)構(gòu)特征的算法改進(jìn)了實(shí)驗(yàn)的結(jié)果； 2)采用PCA降維后，算法的分類(lèi)精度有了一定程度的提高，這是由于PCA在進(jìn)行維數(shù)壓縮時(shí)可能會(huì)去掉數(shù)據(jù)特征中的噪聲,但是如果維數(shù)被壓縮得太低也會(huì)損失數(shù)據(jù)中有用的鑒別信息； 3)一般情況下當(dāng)把數(shù)據(jù)投影到(1/5)×d維(d為特征維數(shù))空間時(shí)3種算法都是可逆的，而此時(shí)LPKNN算法的分類(lèi)精度比降維和不降維的KNN算法都有大幅度的提高，這也說(shuō)明了充分利用每一類(lèi)數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)信息，有利于提高算法的分類(lèi)精度。

4 結(jié)束語(yǔ)

本文借鑒LPP算法的基本思想提出了一種局部保持K近鄰算法。不同于基于歐氏距離和傳統(tǒng)馬氏距離的KNN，LPKNN不僅考慮到了數(shù)據(jù)內(nèi)在幾何結(jié)構(gòu)特征還能夠鑒別數(shù)據(jù)信息，表現(xiàn)出了更好的分類(lèi)精度。針對(duì)LPKNN和MKNN都遭遇的小樣本問(wèn)題，本文采用PCA將原始空間的數(shù)據(jù)轉(zhuǎn)換到低維空間來(lái)解決。實(shí)驗(yàn)結(jié)果表明，該算法比基于歐氏距離和傳統(tǒng)馬氏距離的KNN算法的分類(lèi)精度都有所提高，說(shuō)明充分利用數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)信息有利于提高算法的分類(lèi)精度；但是在運(yùn)行LPKNN算法的時(shí)候由于進(jìn)行參數(shù)選擇會(huì)花費(fèi)較多的時(shí)間，因此如何提高算法的速度將是今后工作的研究方向。

[1]Cover T M, Hart P E. Nearest Neighbor Pattern Classification[J]. IEEE Transactions on Information Theory, 1967, 13(1):21-27.

[2]劉博,楊柳,袁方. 改進(jìn)的KNN方法及其在中文文本分類(lèi)中的應(yīng)用[J]. 西華大學(xué)學(xué)報(bào)：自然科學(xué)版,2008,27(2):33-36.

[3]沈媛媛, 嚴(yán)嚴(yán), 王菡子. 有監(jiān)督的距離度量學(xué)習(xí)算法研究進(jìn)展[J]. 自動(dòng)化學(xué)報(bào), 2014, 40(12):2673-2686.

[4]王駿, 王士同, 鄧趙紅. 聚類(lèi)分析研究中的若干問(wèn)題[J]. 控制與決策, 2012, 27(3):321-328.

[5]Jing Yinan, Hu Ling, Ku Wei-Shinn, et al. Authentication of k Nearest Neighbor Query on Road Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(6):1494-1506.

[6]盧偉勝, 郭躬德, 嚴(yán)宣輝，等. SMwKnn:基于類(lèi)別子空間距離加權(quán)的互k近鄰算法[J].計(jì)算機(jī)科學(xué), 2014, 41(2):166-169.

[7]侯玉婷, 彭進(jìn)業(yè), 郝露微，等. 基于KNN的特征自適應(yīng)加權(quán)自然圖像分類(lèi)研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(3):957-960.

[8]Shen Chunhua, Kim J, Wang Lei. Scalable Large-Margin Mahalanobis Distance Metric Learning[J]. IEEE Transactions on Neural Networks, 2010, 21(9):1524-1530.

[9]Washizawa Y, Hotta S. Mahalanobis Distance on Extended Grassmann Manifolds for Variational Pattern Analysis[J]. IEEE Transactions on Neural Networks and Learning Systems, 2014, 25(11):1980-1990.

[10]Zhang Suli, Pan Xin. A novel Text Classification Based on Mahalanobis distance[C]//Proceedings of the 2011 3rd International Conference on Computer Research and Development. China:IEEE, 2011:156-158.

[11]韓涵, 王厚軍, 龍兵，等. 基于改進(jìn)馬氏距離的模擬電路故障診斷方法[J]. 控制與決策, 2013, 28(11): 1713-1717.

[12]肖輝輝, 段艷明. 基于屬性值相關(guān)距離的KNN算法的改進(jìn)研究[J]. 計(jì)算機(jī)科學(xué), 2013, 40(11A):157-159.

[13]Kokiopoulou E, Saad Y. Orthogonal Neighborhood Preserving Projections: A Projection-Based Dimensionality Reduction Technique[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29 (12) :2143-2156.

[14]Silva E R, Cavalcanti G D C, Ren T I.Class-Dependent Locality Preserving Projections for Multimodal Scenarios[C]// Proceedings of the IEEE 24th International Conference on Tools with Artificial Intelligence. Greece:IEEE, 2012:982-987.

[15]Wang Xiaoming, Chung Fu-lai, Wang Shitong. On Minimum Class Locality Preserving Variance Support Vector Machine[J]．Pattern Recognition, 20l0, 43(8):2753-2762.

[16]Liu Jixin, Khemmar R, Ertaud J Y, et al. Compressed Sensing Face Recognition Method in Heterogeneous Database with Small Sample Size Problem[C]// Proceedings of the 2012 Eighth International Conference on Signal Image Technology and Internet Based Systems. Italy:IEEE, 2012:80-84.

[17]張學(xué)工. 模式識(shí)別[M]. 3版. 北京:清華大學(xué)出版社, 2010:163-165.

[18]Newman D J, Hettich S,Blake C L, et al.UCI Repository of Machine Learning Databases[EB/OL]. [2014-12-25]. http://www.ics.uci.edu/～mlearn/MLRepository.html.

[19]王玨, 周志華, 周傲英. 機(jī)器學(xué)習(xí)及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2006:135-164.

[20]Abril L G, Angulo C, Velasco F, et al. A Note on the Bias in SVM for Multiclassification[J]. IEEE Transanctions on Neural Netwoks, 2008, 19(4):723-725.

(編校：饒莉)

KNNAlgorithmBasedonLocalityPreserving

ZENG Jun-jie, WANG Xiao-ming*, YANG Xiao-huan

(SchoolofComputerandSoftwareEngineering,XihuaUniversity,Chengdu610039China)

The distance metric plays an important role inK-nearest neighbor(KNN) algorithm. The traditional KNN algorithm usually employs the Euclidean distance. However, this distance treats all features equally and ignores the local intrinsic geometric structural characteristics of data. In this paper, following the basic idea of locality preserving projection(LPP), we firstly used the locality preserving within-class scatter matrix to propose a novel distance metric, then we developed a modified version of KNN called locality preservingK-nearest neighbor(LPKNN). The proposed method takes the local intrinsic geometric structural characteristics of data into full consideration. The experimental results indicate that the proposed algorithm can obtain higher classification accuracy in contrast with the KNN algorithm based on the Euclidean distance and the traditional Mahalanobis distance.

K-nearest neighbor; locality preserving projection; Mahalanobis distance

2014-12-30

國(guó)家自然科學(xué)基金項(xiàng)目(61103168)；四川省教育廳自然科學(xué)重點(diǎn)項(xiàng)目(11ZA004)；西華大學(xué)研究生創(chuàng)新基金項(xiàng)目(ycjj2014032)。

：王曉明(1977—)，男，副教授，博士，主要研究方向?yàn)槟Ｊ阶R(shí)別、圖像處理。E-mail:392805710@qq.com

TP18；TP391.1

：A

：1673-159X(2015)06-0058-06

10.3969/j.issn.1673-159X.2015.06.012

*