廣義近鄰模式分類研究.pdf

1、模式識別，以其明確的問題定義、嚴(yán)格的數(shù)學(xué)基礎(chǔ)、堅(jiān)實(shí)的理論框架和廣泛的應(yīng)用價(jià)值，已得到越來越多的重視，并且也成為其他幾門學(xué)科如人工智能、計(jì)算機(jī)視覺、機(jī)器學(xué)習(xí)、心理生物學(xué)和認(rèn)知科學(xué)等的中心研究內(nèi)容之一。在模式識別領(lǐng)域里，在概率密度形式未知和概率密度形式很少符合實(shí)際情況的場合里，非參數(shù)技術(shù)是一種有效的分類方法。近鄰分類方法作為一種經(jīng)典的非參數(shù)分類方法，以其簡單性及較高的分類精度，在信息檢索、時間序列預(yù)測、筆跡和手勢識別、地學(xué)分析、字符識別、計(jì)

2、算機(jī)輔助診斷等諸多領(lǐng)域得到了廣泛應(yīng)用。理論已經(jīng)證明，在樣本數(shù)趨于無窮的情況下，近鄰規(guī)則的分類誤差不會超過最優(yōu)貝葉斯分類器分類誤差的兩倍。
　　 近鄰分類在模式識別鄰域得到了大量應(yīng)用，然而近鄰分類也存在著下面的一些問題:(1)當(dāng)可得的訓(xùn)練樣本數(shù)與數(shù)據(jù)的內(nèi)在維數(shù)之比較大時，近鄰分類通常能取得較高的分類精度。然而，在大多數(shù)情形下，可得的訓(xùn)練樣本數(shù)通常較小，這就導(dǎo)致近鄰分類的分類精度顯著降低。(2)近鄰分類器基于局部信息進(jìn)行預(yù)測。正是因

3、為這樣的局部分類決策，近鄰分類對噪聲非常敏感，作為非參數(shù)分類方法的一種，近鄰分類的分類性能通常由于離群點(diǎn)的存在而受到嚴(yán)重削弱。(3)近鄰分類可以生成任意形狀的決策邊界，其決策邊界具有很高的可變性，近鄰個數(shù)的確定直接影響到近鄰分類器決策邊界的形成。(4)近鄰分類是一種消極的學(xué)習(xí)方法，它需要較高的存儲要求和較高的計(jì)算代價(jià)，具有較高的計(jì)算復(fù)雜度。(5)除非采用適當(dāng)?shù)木嚯x度量，否則近鄰分類器可能做出錯誤的預(yù)測。
　　 在近鄰分類存在的這

4、些問題中，本文主要圍繞近鄰分類的三大問題:如何提高近鄰分類的分類性能;如何選擇一個適當(dāng)?shù)木嚯x度量;如何降低近鄰分類的計(jì)算復(fù)雜度，以減少存儲要求，加快搜索速度等展開深入細(xì)致的研究和探討。
　　 具體地，本文的主要創(chuàng)新點(diǎn)可歸納如下:
　　 1、提出了基于類間樣本之間相似性的偽最近鄰分類方法。模式分類能夠順利進(jìn)行，關(guān)鍵就在于來自同一類別的不同樣本的特征值非常相似，而來自不同類別的樣本的特征值有較大的差異。偽最近鄰分類規(guī)則就充分

5、利用了模式分類的這一本質(zhì)。在偽最近鄰分類方法里，考慮了測試樣本與同類訓(xùn)練樣本集里的多個近鄰樣本之間不同距離對分類結(jié)果的影響，距離愈小，分配給相應(yīng)近鄰的權(quán)值就愈大，對分類結(jié)果的影響就愈大。理論分析證明了提出的偽最近鄰分類的漸近分類誤差率小于或等于傳統(tǒng)的最近鄰分類的分類誤差率。偽最近鄰分類規(guī)則特別適合在大樣本情形下對近鄰分類的性能進(jìn)行改進(jìn)。
　　 2、針對訓(xùn)練樣本集里的離群點(diǎn)樣本的影響，提出了基于類均值的擴(kuò)展最近鄰分類。非參數(shù)分類，

6、尤其是近鄰分類的分類性能，由于離群點(diǎn)的存在，從而導(dǎo)致分類性能的急劇降低?；陬惥档臄U(kuò)展最近鄰分類，由于引入了類均值這一表征樣本數(shù)據(jù)類整體知識的信息，可極大地克服離群點(diǎn)對分類性能的影響，并能避免對訓(xùn)練數(shù)據(jù)的過擬合，從而改善近鄰分類的分類性能。該方法在樣本數(shù)據(jù)類均值差異較大的情形下，對近鄰分類性能的改進(jìn)較為明顯。
　　 3、近鄰分類在小樣本情形下，分類性能將急劇降低。為了提高近鄰分類在小樣本情形下的分類性能，提出了基于局部均值與類

7、統(tǒng)計(jì)量的擴(kuò)展最近鄰分類。該分類方法不僅能克服離群點(diǎn)對近鄰分類性能的影響，還能避免對訓(xùn)練數(shù)據(jù)的過擬合，并能顯著改善近鄰分類在小樣本情形下的分類性能。
　　 4、影響近鄰分類方法大量使用的一個主要障礙就是它的計(jì)算復(fù)雜度。為了降低近鄰分類的計(jì)算復(fù)雜度，提出了基于半監(jiān)督學(xué)習(xí)的近鄰剪輯方法。該方法不但剔除了那些帶有錯誤類別號的樣本，而且去除了大量的邊界疊加樣本，從而減少訓(xùn)練樣本集合里的樣本數(shù)量。更為重要的是，該方法能顯著改善近鄰分類器的分