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

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

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

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

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

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

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

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