葉建龍

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

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

葉建龍

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

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

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

1 引言

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

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

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

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

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

2 相關算法

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

2.1 V-kNN

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

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

2.2 DW-kNN

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

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

2.3 LC-kNN

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

其中d（）表示兩個樣本點的距離.XC表示C類的局部中心.通常估計如下

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

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

3 本文的算法

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

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

1.從訓練集T中找出樣本q的k個最近鄰組成近鄰集合Nk（q）.即

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

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

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

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

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

表1 搖實驗數(shù)據(jù)集

4 實驗結果及分析

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

4.1 實驗數(shù)據(jù)

本文用UCI的4個學習文算法進行了實驗驗證［11］，選用的數(shù)據(jù)集信息如表1.

4.2 實驗設置

對每個數(shù)據(jù)集我們進行如下實驗設置：

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

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

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

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

4.3 實驗結果及分析

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

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

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

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

5 結語

基于局部分布的思想，我們提出以一種新的k最近鄰分類方法.這種方法將待測樣本周圍的樣本按類別整體考慮，計算各類的局部分布特征，然后根據(jù)局部分布特征計算待測樣本對于各個類的隸屬度，樣本被分到具有最大隸屬度的類中.由于對局部近鄰的整體考慮，該方法表現(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.

［責任編輯：王曉軍］

O 176.3

A

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

2016-08-10

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