基于局部分布的k-最近鄰分類方法

葉建龍

（隴南師范高等?？茖W(xué)校數(shù)信學(xué)院，甘肅成縣 742500）

基于局部分布的k-最近鄰分類方法

葉建龍

（隴南師范高等專科學(xué)校數(shù)信學(xué)院，甘肅成縣 742500）

k-最近鄰分類算法通過對待測樣本的鄰近樣本進(jìn)行分析來預(yù)測待測樣本的類標(biāo)號，是一種簡單有效的分類方法.傳統(tǒng)的k-最近鄰算法通常使用鄰近樣本的多數(shù)投票規(guī)則來確定類標(biāo)號.本文提出一種改進(jìn)的k-最近鄰算法，從鄰域的局部分布來分析待測樣本的類別.我們分析了局部分布特征對分類的影響，通過局部分布特征估計(jì)樣本對每個(gè)類的隸屬度，待測樣本被分到最大的隸屬度的類中.實(shí)驗(yàn)結(jié)果表明改進(jìn)的方法能一定程度上提高分類準(zhǔn)確率.

近鄰分類；數(shù)據(jù)挖掘；算法

1 引言

分類問題是數(shù)據(jù)挖掘領(lǐng)域一個(gè)重要的研究方向，而近鄰分類算法是研究分類問題的一個(gè)重要并廣泛使用的方法.近鄰分類算法的基本思想是根據(jù)待測樣本在訓(xùn)練集中的近鄰樣本對該待測樣本進(jìn)行分類.k-最近鄰算法（kNN）最初是由Cover和Hart［1］提出的，他們先從訓(xùn)練樣本集中找到與待測樣本最近的k個(gè)樣本，稱為待測樣本的k個(gè)最近鄰，然后將待測樣本分到其k個(gè)最近鄰所代表的多數(shù)類中.近幾十年來，k-最近鄰分類方法以其算法簡單有效而廣泛應(yīng)用于模式識別和數(shù)據(jù)挖掘的各個(gè)領(lǐng)域［2，3，4］，并被評為數(shù)據(jù)挖掘領(lǐng)域影響最大的十種算法之一［5］.

如果一個(gè)數(shù)據(jù)集中同類的樣本點(diǎn)近似度比不同類的樣本點(diǎn)高，這個(gè)樣本點(diǎn)的鄰近樣本就較遠(yuǎn)的樣本比更能表現(xiàn)這個(gè)樣本的性質(zhì)，k最近鄰算法在這種情況下就非常有效.實(shí)際上，被分為同類的樣本通常會有某些相似性，因此，如果給定的特征足夠，kNN算法通常能表現(xiàn)良好的分類效果.

傳統(tǒng)的kNN算法是以待測樣本的k個(gè)最近鄰?fù)镀钡男问酱_定類標(biāo)號的，這種投票方法的缺點(diǎn)是沒有考慮k個(gè)最近鄰之間的差異，把這k個(gè)最近鄰等同對待.雖然當(dāng)鄰域很小時(shí)，這種差異可以忽略不計(jì)，但是實(shí)際上由于數(shù)據(jù)集的不同，我們并不能保證所有樣本的k個(gè)最近鄰都在很小的區(qū)域內(nèi).因此，傳統(tǒng)的kNN算法對某些樣本的分類會出現(xiàn)誤分情況.

文獻(xiàn)中針對這個(gè)問題對kNN的改進(jìn)方法主要有兩類，第一類是通過對k個(gè)最近鄰進(jìn)行加權(quán)的方法來區(qū)分對待測樣本分類的貢獻(xiàn)，這種方法稱為加權(quán)k最近鄰方法（Weighted-kNN，WkNN）［6，7，8］.第二類方法是將這k個(gè)近鄰按類別規(guī)約為幾個(gè)局部中心，根據(jù)中心到待測樣本的距離來確定類標(biāo)號，這類方法有類平均模式（Categorical Average Patterns，CAP）［9］和局部概率中心（Local Probabilistic Center，LPC）［10］等.

本文從局部分布的角度來研究分類問題并提出基于局部分布的k最近鄰分類方法（Local Distribution based kNN，LD-kNN）.一個(gè)樣本的類標(biāo)號與它周圍樣本的分布是密切相關(guān)的，我們可以根據(jù)待測樣本的k個(gè)最近鄰的分布特征計(jì)算出該樣本對各個(gè)類的隸屬度，然后將待測樣本分到最高隸屬度的類中.在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明該方法的有效性.

2 相關(guān)算法

給定一個(gè)樣本X和它在訓(xùn)練集中的的k個(gè)最近鄰，第i個(gè)最近鄰記為（xi，Li），xi為特征描述，Li為類標(biāo)號，其到X的距離記為di.K最近鄰算法的任務(wù)就是組織這些信息對待測樣本X進(jìn)行分類.常用的方法有投票方法（V-kNN），距離加權(quán)方法（DW-kNN）和局部中心方法（LC-kNN）.

2.1 V-kNN

V-kNN是最基礎(chǔ)的k最近鄰分類方法，它是從k個(gè)最近鄰的投票來產(chǎn)生分類結(jié)果，V-kNN分類可以表示成如下公式

I（c）是指示函數(shù)，當(dāng)條件c為真時(shí)返回1，否則返回0.Nc表示k個(gè)最近鄰中類標(biāo)號是C類的個(gè)數(shù).

2.2 DW-kNN

DW-kNN是對傳統(tǒng)V-kNN的一種改進(jìn)，它通過對k個(gè)最近鄰樣本進(jìn)行加權(quán)來區(qū)分不同近鄰樣本對分類的貢獻(xiàn)，距離較近的樣本更能反映待測樣本的特征，因此DW-kNN會給較近的樣本一個(gè)較大的權(quán)重進(jìn)行投票.如果給第i個(gè)樣本的權(quán)重是，DW-kNN可以表示為

權(quán)重wi和該近鄰到待測樣本的距離di是密切相關(guān)，距離越大，該近鄰對待測樣本的影響越小，權(quán)重就越小.很多文獻(xiàn)［6，7，8］都提出了不同的加權(quán)方法.最典型的就是Dudani［6］提出的加權(quán)方法，表示如下

2.3 LC-kNN

LC-kNN提取待測樣本周圍每個(gè)類的局部中心信息，然后將待測樣本分到局部中心最近的類中.這種方法將待測樣本的k個(gè)最近鄰按類標(biāo)號分組整體考慮，有效降低了k個(gè)最近鄰中噪聲點(diǎn)的影響.LC-kNN可以表示如下

其中d（）表示兩個(gè)樣本點(diǎn)的距離.XC表示C類的局部中心.通常估計(jì)如下

由于每個(gè)類選取不同數(shù)據(jù)的近鄰會對局部中心的估算造成偏差，CAP方法通過對每個(gè)類選擇相等數(shù)量的最近鄰來優(yōu)化LC-kNN.假設(shè)對每個(gè)類都選k個(gè)最近鄰，表示C類的第i個(gè)最近鄰，CAP的局部中心就可以表示為

LPC方法對訓(xùn)練集的每個(gè)樣本計(jì)算一個(gè)概率p表示它真正屬于指定類的概率，即pi表示Xi屬于Li的概率.通過這個(gè)概率來對訓(xùn)練集的噪聲樣本進(jìn)行處理.這樣，LPC的局部概率中心就表示為

3 本文的算法

我們通過每個(gè)類在待測樣本周圍的局部分布信息來估計(jì)待測樣本對各個(gè)類的隸屬度.本文用到的局部分布信息包括分布的中心和分布的離散程度兩個(gè)指標(biāo).對單變量來說，變量的均值是其中心，標(biāo)準(zhǔn)差代表了其離散程度.對分類問題來說，一個(gè)樣本通常是有多個(gè)變量表示，變量的分布就是多為分布.因此需要將均值和標(biāo)準(zhǔn)差擴(kuò)展到多變量.n個(gè)樣本X1，……Xn的中心和離散程度可以表示如下：

對于給定訓(xùn)練集T和待測樣本q，LD-kNN的分類過程如下：

1.從訓(xùn)練集T中找出樣本q的k個(gè)最近鄰組成近鄰集合Nk（q）.即

Nk（q）={x|d（x；q）≤d（Xk；q）；x∈T}

其中Xk表示第k個(gè)最近鄰，d（）為距離函數(shù)，表示兩個(gè)樣本之間的距離，本文選用歐氏距離.

2.根據(jù)類標(biāo)號將k最近鄰集合Nk（q）劃分為Nc個(gè)小集合Si（i=1，……，Nc），使得每個(gè)集合中所有樣本都屬于同一個(gè)類，而不同集合中的樣本屬于不同的類.即

其中NC代表k個(gè)最近鄰中類的總個(gè)數(shù)，Nj表示第j個(gè)類中包含在k個(gè)最近鄰中的樣本數(shù).

4.根據(jù)中心和離散程度來估計(jì)該樣本對該類的隸屬度MDi（q）.直觀來看，類的局部分布對隸屬度的影響如下：1.類的離散程度相同的情況下，樣本到類中心的距離越近，該樣本對該類的隸屬度越大.2.類的離散程度越大，即類越分散，它覆蓋一個(gè)樣本的可能性就越大，換句話說，一個(gè)樣本到幾個(gè)類中心距離相等時(shí)，該樣本更可能屬于離散程度較大的類.另外，3.由于Ni/k代表了待測樣本q周圍第i類分布的先驗(yàn)概率，Ni越大，q對第i類的隸屬度就越大.因此，我們假設(shè)有如下關(guān)系：

表1 搖實(shí)驗(yàn)數(shù)據(jù)集

4 實(shí)驗(yàn)結(jié)果及分析

5.將待測樣本q分到MDi（q）最大的類中，即

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文用UCI的4個(gè)學(xué)習(xí)文算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證［11］，選用的數(shù)據(jù)集信息如表1.

4.2 實(shí)驗(yàn)設(shè)置

對每個(gè)數(shù)據(jù)集我們進(jìn)行如下實(shí)驗(yàn)設(shè)置：

1.交叉驗(yàn)證：我們使用5折交叉驗(yàn)證進(jìn)行測試.對每個(gè)數(shù)據(jù)集均勻劃分成5份，其中4份作為訓(xùn)練集，剩余一份作為測試集，分類精度為所有測試集中正確分類的樣本數(shù)除以總的測試樣本數(shù).由于訓(xùn)練集和測試集是獨(dú)立的，交叉驗(yàn)證能有效避免過擬合的問題.

2.規(guī)范化：對數(shù)據(jù)集的每個(gè)特征，我們使用z-score規(guī)范化將訓(xùn)練集中的特征轉(zhuǎn)換為均值為0，標(biāo)準(zhǔn)差為1，測試集用相同的均值和標(biāo)準(zhǔn)差進(jìn)行變化.變換公式如下：

3.評價(jià)指標(biāo)：我們執(zhí)行10次5折交叉驗(yàn)證，每次的劃分是隨機(jī)劃分的，我們將10次5折交叉驗(yàn)證的平均分類精度作為評價(jià)指標(biāo).平均分類精度越高，分類效果越好.

4.參數(shù)選擇：kNN分類器中的參數(shù)k表示搜索的近鄰的個(gè)數(shù).在我們的實(shí)驗(yàn)中，我們搜索近鄰的個(gè)數(shù)為k*NC，NC為類的數(shù)目，即在待測樣本周圍平均每個(gè)類有k個(gè)近鄰.我們將k從1到30變化，得出最高的分類精度作為該分類器在該數(shù)據(jù)集上的評價(jià)指標(biāo).

4.3 實(shí)驗(yàn)結(jié)果及分析

在實(shí)驗(yàn)數(shù)據(jù)集上不同kNN分類方法的比較結(jié)果如下表所示

表2 搖不同分類方法在不同數(shù)據(jù)集上的分類精度

從表2可以看出，在這四個(gè)數(shù)據(jù)集上，LD-kNN的分類精度都要高于其他方法，驗(yàn)證了LD-kNN的有效性.

參數(shù)k是一個(gè)能影響LD-kNN分類器分類效果的重要因素.如果k選擇太小，對局部分布特征的估計(jì)會不很穩(wěn)定，當(dāng)k=1時(shí)，LD-kNN就變成了傳統(tǒng)的最近鄰分類方法.如果k的選擇過大，那么有的近鄰樣本就會離待測樣本較遠(yuǎn)，無法反映待測樣本特性，反而對分類有負(fù)影響.因此，針對不同數(shù)據(jù)集要選擇合適的參數(shù)k以提高分類精度.

5 結(jié)語

基于局部分布的思想，我們提出以一種新的k最近鄰分類方法.這種方法將待測樣本周圍的樣本按類別整體考慮，計(jì)算各類的局部分布特征，然后根據(jù)局部分布特征計(jì)算待測樣本對于各個(gè)類的隸屬度，樣本被分到具有最大隸屬度的類中.由于對局部近鄰的整體考慮，該方法表現(xiàn)出比傳統(tǒng)kNN方法更好的分類效果.

［1］T.Cover and P.Hart,“Nearest neighbor pattern classification,”Information Theory,IEEE Transactions on,vol.13, no.1,pp.21-27,1967.

［2］D.Hand,H.Mannila,and P.Smyth,Principles of data mining.MIT press,2001.

［3］Y.Zhou,Y.Li,and S.Xia,“An improved knn text classification algorithm based on clustering,”Journal of computers, vol.4,no.3,pp.230-237,2009.

［4］J.Bromley and E.Sackinger,“Neural-network and k-nearest-neighbor classifiers,”Rapport technique,pp.11 359-910 819,1991.

［5］X.Wu,V.Kumar,J.R.Quinlan,J.Ghosh,Q.Yang,H. Motoda,G.J.McLachlan,A.Ng,B.Liu,S.Y.Philip et al.,“Top 10 algorithms in data mining,”Knowledge and Information Systems,vol.14,no.1,pp.1-37,2008.

［6］S.Dudani,“The distance-weighted k-nearest-neighbor rule,”Systems,Man and Cybernetics,IEEE Transactions on, no.4,pp.325-327,1976.

［責(zé)任編輯：王曉軍］

O 176.3

A

1672-402X（2016）11-0013-04

2016-08-10

葉建龍（1981-），男，甘肅西和人，隴南師范高等?？茖W(xué)校講師，研究方向：數(shù)據(jù)挖掘、算法.