模式識(shí)別課件(第六章-NO1)(最近鄰法)

1、第六章 近鄰法6.1 最近鄰法一. 最近鄰法的基本思想此法是一種根據(jù)全部樣本提供的信息，繞開概率的估計(jì)而直接決策的方法，所以它是非參數(shù)決策方法的一種。其基本思想是：設(shè)有一組N個(gè)樣本 = X1,X2,XN其中每個(gè)樣本都已標(biāo)以類別標(biāo)志。如果在這N個(gè)樣本中與待分樣本X相距最近的一個(gè)樣本為Xi，則把X分到Xi所在的類別中去。 二. 最近鄰法的決策規(guī)則設(shè)有c類模式樣本， 1, 2, c每類有Ni個(gè)樣本(i=1,2,c)，則最近鄰法的(i類)判別函數(shù)為:式中 表示i類中的第k個(gè)樣本。 對(duì)應(yīng)的決策規(guī)則為： 如果 則決策 即只要將待分樣本X與全部N( )個(gè)已知類別的樣本進(jìn)行歐氏距離之間的比較，然后將X歸到離它

2、最近的類別中。 由于這種方法只根據(jù)離待分樣本X最近的一個(gè)樣本的類別而決定其類別，所以通常稱為1-最近鄰法(亦稱1-NN方法)三. 最近鄰法的錯(cuò)誤率問題最近鄰法是一種次優(yōu)方法，它的錯(cuò)誤率比最小錯(cuò)誤概率的Bayes決策規(guī)則下的錯(cuò)誤率要大，但是，當(dāng)樣本數(shù)目無(wú)限時(shí)，它的錯(cuò)誤率不會(huì)超過Bayes錯(cuò)誤率的一倍。定性分析： 若將X的最近鄰Xj的類別看成是一個(gè)隨機(jī)變量 ，于是 的概率就是后驗(yàn)概率 .當(dāng)樣本數(shù)目很多時(shí)，可以認(rèn)為X的最近鄰Xj 離它很近，從而近似的認(rèn)為這時(shí)最近鄰法可看成是如下的隨機(jī)化決策：按照概率 來(lái)決定X的類別。故最近鄰法可看成是用后驗(yàn)概率來(lái)對(duì)X進(jìn)行分類的。再進(jìn)一步說(shuō)，就是如果有下式成立：則依B

3、ayes決策，應(yīng)取 作為X的類別。而在最近鄰法中，最近鄰的類別為 的概率為 ，所以X分到 類去的概率為 ，而不分到 類去的概率為：這也就是說(shuō)： 按Bayes決策的話：以概率為1，而得決策 按最近鄰法決策的話：以概率為，而得決策 顯然，當(dāng)接近于1時(shí)，最近鄰法與最小錯(cuò)誤率下的Bayes法的結(jié)果就幾乎相同了。也就是說(shuō)，當(dāng)最小錯(cuò)誤概率較小時(shí)，最近鄰法的錯(cuò)誤概率也是較小的，這兩種方法同樣“好”。而當(dāng)各類的都接近于 時(shí)(即所有類別是等可能的)，最近鄰法與Bayes法的結(jié)果就不一樣了。這時(shí)兩者的錯(cuò)誤率都接近于 定量描述：式中：p為最近鄰法的漸近平均錯(cuò)誤率 為 Bayes錯(cuò)誤率 c 為類別數(shù) 一般較小 6.2

4、 k-近鄰法(k-NN法)為了克服單個(gè)樣本類別的偶然性以增加分類的可靠性，可將最近鄰法則進(jìn)行改進(jìn)，一個(gè)簡(jiǎn)單的方法就是k-近鄰法。此法就是考察待分樣本X的k個(gè)最近鄰樣本，這k個(gè)最近鄰元素中哪一類的樣本最多，就將X判屬哪一類?；蛘哒f(shuō)，就是在N個(gè)已知類別的樣本中，找出X的k個(gè)近鄰，這k個(gè)近鄰中多數(shù)屬于的那一類 ，就是 。具體就是：設(shè)k1,k2,.,kc分別為X的k個(gè)最近鄰樣本中屬于 類的樣本數(shù)，則定義 類的判別函數(shù)為： 決策規(guī)則為： 如果 則判最近鄰法和k-近鄰法的共同優(yōu)點(diǎn)是簡(jiǎn)單，而且結(jié)果是比較好的，但是它們也存在下述問題： 需要將全部樣本存入機(jī)器中，每次決策都要計(jì)算X與全部樣本間的距離并進(jìn)行比較。

5、所以要求的存儲(chǔ)容量和計(jì)算量都很大。 沒有考慮到?jīng)Q策的風(fēng)險(xiǎn)，所以如果決策的錯(cuò)誤代價(jià)很大時(shí)，會(huì)產(chǎn)生很大的風(fēng)險(xiǎn)。上述分析是建立在樣本數(shù) 的假定上的，這在實(shí)際應(yīng)用中是無(wú)法實(shí)現(xiàn)的。6.3 近鄰法的改進(jìn)算法共同特點(diǎn)是如何盡快地找出最近鄰可能存在的小的空間，減少搜索的范圍，從而達(dá)到減少近鄰法中的計(jì)算量和存儲(chǔ)量的問題。一. 快速近鄰算法該算法對(duì)最近鄰法和k-近鄰法都適用。下面以最近鄰法為例來(lái)討論。1. 基本思想將全部已知樣本按級(jí)分成一些不相交的子集，并在子集的基礎(chǔ)上進(jìn)行搜索。也就是說(shuō)，該算法由兩個(gè)階段組成：第一階段：將樣本集按級(jí)分解，形成樹狀結(jié)構(gòu)。第二階段：用搜索算法找出待識(shí)樣本的最近鄰。2. 涉及的規(guī)則設(shè)=

6、X1,X2,XN表示全部樣本集；P表示節(jié)點(diǎn)P對(duì)應(yīng)的樣本子集，即P；NP表示P中的樣本數(shù)；MP表示P中的樣本均值(即“類心”)；rP ：表示從MP到Xip 的最大距離；B表示除p中的樣本之外的樣本到待分樣本X的最近距離。B的初值設(shè)為，以后再不斷修正。規(guī)則1如果存在 則Xip不可能是X的最近鄰。證明：對(duì)任意 ，據(jù)三角不等式有 而據(jù) rp定義有 由上兩式可得 即得則 不可能是X的最近鄰。的近鄰iMp rP規(guī)則2.如果存在則 不可能是X的最近鄰。證明：比較規(guī)則1與規(guī)則2，并參圖，可知 故得證。3. 快速近鄰算法第一階段：將樣本集按級(jí)分解。首先將分為l個(gè)子集，每個(gè)子集再分成l個(gè)子子集，依次分下去，圖6.

7、3為l=3的情況。這時(shí)每個(gè)節(jié)點(diǎn)上對(duì)應(yīng)一群樣本。第二階段：搜索樹搜索算法：step1：設(shè)置B=，L=0，P=0.(L是當(dāng)前水平，P是當(dāng)前節(jié)點(diǎn))。step2：將當(dāng)前節(jié)點(diǎn)P的所有直接后繼節(jié)點(diǎn)(即子節(jié)點(diǎn))放入一個(gè)目錄表中，并對(duì)這些節(jié)點(diǎn)X計(jì)算二. 剪輯近鄰法此類方法的基本思想是：剪掉(清理)兩類間的邊界，取掉類別混雜的樣本，使兩類邊界更清晰。1. 兩分剪輯近鄰法(亦稱剪輯最近鄰法)基本過程為：設(shè)N個(gè)樣本分成c類 = , , (N1+N2+,+Nc= N)step1：剪輯。利用已知樣本集 中的樣本進(jìn)行預(yù)分 類，并剪輯掉被錯(cuò)分類的樣本，留下的樣本構(gòu)成 剪輯樣本集step2：分類。利用 和近鄰規(guī)則對(duì)未知樣本X進(jìn)行 分類。下面以兩類情況進(jìn)行具體介紹：設(shè)將已知類別的樣本集N分成測(cè)試集NT和參照集NR兩個(gè)獨(dú)立的部分(即這兩部分沒有公共元素)，它們的樣本數(shù)各為NR和NT，且NR+NT=N。剪輯步：利用參照集NR中的樣本 對(duì)測(cè)試集NT 中的每