葉建龍
(隴南師范高等??茖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ù)挖掘;算法
分類問題是數(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é)果表明該方法的有效性.
給定一個(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的局部概率中心就表示為
我們通過每個(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ù)集
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以提高分類精度.
基于局部分布的思想,我們提出以一種新的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ù)挖掘、算法.