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

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

2、kiX)N,1,2,.(k min)(ikikiXXXg 對(duì)應(yīng)的決策規(guī)則為：對(duì)應(yīng)的決策規(guī)則為： 如果如果 則決策則決策 即只要將待分樣本X與全部與全部N( )個(gè)已知類(lèi)別的樣本進(jìn)行歐氏距離歐氏距離之間的比較，然后將X歸到離它最近的類(lèi)別中歸到離它最近的類(lèi)別中。 由于這種方法只根據(jù)離待分樣本X最近的一個(gè)樣本的類(lèi)別而決定其類(lèi)別，所以通常稱(chēng)為1-最近鄰法最近鄰法(亦稱(chēng)1-NN方法方法)iXciiN1c),1,2,.(j )(gmin)(jXXgji三三. 最近鄰法的錯(cuò)誤率問(wèn)題最近鄰法的錯(cuò)誤率問(wèn)題最近鄰法是一種次優(yōu)次優(yōu)方法，它的錯(cuò)誤率錯(cuò)誤率比最小錯(cuò)誤概率最小錯(cuò)誤概率的的Bayes決策規(guī)則決策規(guī)則下的錯(cuò)誤率

3、要大要大，但是，當(dāng)樣本數(shù)目無(wú)限無(wú)限時(shí)，它的錯(cuò)誤率不會(huì)超過(guò)Bayes錯(cuò)誤率的一倍一倍。定性分析：定性分析： 若將X的最近鄰Xj的類(lèi)別看成是一個(gè)隨機(jī)變量隨機(jī)變量 ，于是 的概率就是后驗(yàn)概率 .當(dāng)樣本數(shù)目很多樣本數(shù)目很多時(shí)，可以認(rèn)為X的最近鄰Xj 離它很近離它很近，從而近似的近似的認(rèn)為j)(jjXPjj)()(XPXPjjj這時(shí)最近鄰法可看成是如下的隨機(jī)化決策如下的隨機(jī)化決策：按照概率按照概率 來(lái)決定來(lái)決定X的類(lèi)別的類(lèi)別。故最近鄰法可看成是用后驗(yàn)概率后驗(yàn)概率來(lái)對(duì)X進(jìn)行分類(lèi)的。再進(jìn)一步說(shuō)，就是如果有下式成立如果有下式成立：則依Bayes決策，應(yīng)取 作為X的類(lèi)別。而在最近鄰法最近鄰法中，最近鄰的類(lèi)別為

4、的概率為 ，所以X分到分到 類(lèi)去的概率為 ，而不分到不分到 類(lèi)去的概率為：)(XPi)(XPj)(max)(XPXPjjiii)(XPii)(1XPii這也就是說(shuō)：這也就是說(shuō)： 按Bayes決策決策的話(huà)：以概率為1，而得決策 按最近鄰法決策最近鄰法決策的話(huà)：以概率為，而得決策 顯然，當(dāng)接近于當(dāng)接近于1時(shí)，最近鄰法與最小錯(cuò)誤率下的Bayes法的結(jié)果結(jié)果就幾乎相同幾乎相同了。也就是說(shuō)，當(dāng)最小錯(cuò)誤概率較小時(shí)，最近鄰法的錯(cuò)誤概率也是較小的，這兩種方法同樣同樣“好好”。而當(dāng)各類(lèi)的都接近于當(dāng)各類(lèi)的都接近于 時(shí)時(shí)(即所有類(lèi)別是等可能的)，最近鄰法與Bayes法的結(jié)果就不一樣了。這時(shí)兩者的錯(cuò)兩者的錯(cuò)誤率都接近

5、于誤率都接近于iX)(XPiiX)(XPi)(XPic1c11 定量描述：定量描述：式中：p為最近鄰法的漸近平均錯(cuò)誤率 為 Bayes錯(cuò)誤率 c 為類(lèi)別數(shù) 一般較小 )12(PccPPPPP PPP2 6.2 k-近鄰法近鄰法(k-NN法法)為了克服單個(gè)樣本類(lèi)別的偶然性偶然性以增加分類(lèi)的可靠性可靠性，可將最近鄰法則最近鄰法則進(jìn)行改進(jìn)，一個(gè)簡(jiǎn)單的方法就是k-近鄰法近鄰法。此法就是考察待分樣本考察待分樣本X的的k個(gè)最近鄰樣本個(gè)最近鄰樣本，這這k個(gè)最近鄰個(gè)最近鄰元素中元素中哪一類(lèi)哪一類(lèi)的樣本最多的樣本最多，就將X判屬哪一類(lèi)。或者說(shuō)，就是在在N個(gè)已知類(lèi)別個(gè)已知類(lèi)別的樣本中，找出的樣本中，找出X的的k個(gè)

6、近鄰個(gè)近鄰，這，這k個(gè)近鄰中個(gè)近鄰中多多數(shù)屬于的那一類(lèi)數(shù)屬于的那一類(lèi) ，就是 。具體就是：具體就是：設(shè)k1,k2,.,kc分別為X的的k個(gè)最近鄰樣本個(gè)最近鄰樣本中屬于屬于 類(lèi)的樣本數(shù)類(lèi)的樣本數(shù)，iiXc,.,21則定義定義 類(lèi)的判別函數(shù)為：類(lèi)的判別函數(shù)為： 決策規(guī)則為：決策規(guī)則為： 如果如果 則判則判最近鄰法和k-近鄰法的共同優(yōu)點(diǎn)是簡(jiǎn)單簡(jiǎn)單，而且結(jié)果是比較好結(jié)果是比較好的的，但是它們也存在下述問(wèn)題存在下述問(wèn)題： 需要將全部樣本全部樣本存入機(jī)器中，每次決策都要計(jì)算X與全部樣本間的距離并進(jìn)行比較。所以要求的存儲(chǔ)容量存儲(chǔ)容量和和計(jì)算量都很大計(jì)算量都很大。 沒(méi)有考慮到?jīng)Q策的沒(méi)有考慮到?jīng)Q策的風(fēng)險(xiǎn)風(fēng)險(xiǎn)，所

7、以如果決策的錯(cuò)誤代價(jià)很大時(shí)，會(huì)產(chǎn)生很大的風(fēng)險(xiǎn)。上述分析是建立在樣本數(shù)建立在樣本數(shù) 的假定上的的假定上的，這在實(shí)際實(shí)際應(yīng)用中是無(wú)法實(shí)現(xiàn)的無(wú)法實(shí)現(xiàn)的。),.,2 , 1(ciiiikXg)()(max)(XgXgiijjXN6.3 近鄰法的改進(jìn)算法近鄰法的改進(jìn)算法共同特點(diǎn)是如何盡快地找出盡快地找出最近鄰可能存在的小的空間，減少搜索的范圍減少搜索的范圍，從而達(dá)到減少減少近鄰法中的計(jì)算量計(jì)算量和存儲(chǔ)量存儲(chǔ)量的問(wèn)題。一一. 快速近鄰算法快速近鄰算法該算法對(duì)最近鄰法對(duì)最近鄰法和k-近鄰法近鄰法都適用都適用。下面以最近鄰法為例來(lái)討論。1. 基本思想基本思想將全部已知樣本按級(jí)分成全部已知樣本按級(jí)分成一些不相交

8、的子集不相交的子集，并在子集的基礎(chǔ)上進(jìn)行搜索。也就是說(shuō)，該算法由兩個(gè)階段組成：第一階段：第一階段：將樣本集按級(jí)分解按級(jí)分解，形成樹(shù)狀結(jié)構(gòu)。第二階段：第二階段：用搜索算法搜索算法找出待識(shí)樣本的最近鄰。2. 涉及的規(guī)則涉及的規(guī)則設(shè)=X1,X2,XN表示全部樣本集全部樣本集；P表示節(jié)點(diǎn)P對(duì)應(yīng)的樣本子集樣本子集，即P；NP表示P中的樣本數(shù)中的樣本數(shù)；MP表示P中的樣本均值中的樣本均值(即“類(lèi)心類(lèi)心”)；rP ：表示從從MP到到Xi p 的最大距離的最大距離；B表示除除p中的樣本之外的樣本中的樣本之外的樣本到待分樣本X的最近距離最近距離。B的初值設(shè)為，以后再不斷修正不斷修正。規(guī)則規(guī)則1如果存在如果存在

9、則Xi p不可不可能是能是X的最近鄰的最近鄰。),(ppMXDrB),(maxpiXMXDpi證明：證明：對(duì)任意 ，據(jù)三角不等式有 而據(jù) rp定義有 由上兩式可得 即得則則 不可能是不可能是X的最近鄰的最近鄰。piX),(),(),(pPiiMXDMXDXXDppirMXD),(BrMXDXXDpPi),(),(),(ppMXDrBpiX的近鄰iMp rP規(guī)則規(guī)則2.如果存在則 不可能是X的最近鄰。證明：證明：比較規(guī)則比較規(guī)則1與規(guī)則與規(guī)則2，并參圖，可知 故得證。),(),(ppiMXDMXDBpiXppirMXD),(3. 快速近鄰算法快速近鄰算法第一階段：第一階段：將樣本集樣本集按級(jí)分解

10、按級(jí)分解。首先將將分為l個(gè)子集個(gè)子集，每個(gè)子集再分成每個(gè)子集再分成l個(gè)子子集個(gè)子子集，依次分下去，圖圖6.3為l=3的情況。這時(shí)每個(gè)節(jié)點(diǎn)上對(duì)應(yīng)一群樣本。第二階段：第二階段：搜索搜索樹(shù)搜索算法：step1：設(shè)置設(shè)置B=，L=0，P=0.(L是當(dāng)前水平，P是當(dāng)前節(jié)點(diǎn))。step2：將當(dāng)前節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)P的所有直接后繼節(jié)點(diǎn)所有直接后繼節(jié)點(diǎn)(即子節(jié)點(diǎn))放入一個(gè)目錄表中，并對(duì)這些節(jié)點(diǎn)節(jié)點(diǎn)X計(jì)算計(jì)算),(pMXD二二. 剪輯近鄰法剪輯近鄰法此類(lèi)方法的基本思想是基本思想是：剪掉剪掉(清理)兩類(lèi)間的邊界兩類(lèi)間的邊界，取掉類(lèi)別混雜的樣本混雜的樣本，使兩類(lèi)邊界更清晰。1. 兩分剪輯近鄰法兩分剪輯近鄰法(亦稱(chēng)剪輯最近

11、鄰法剪輯最近鄰法)基本過(guò)程為：基本過(guò)程為：設(shè)N個(gè)樣本分成c類(lèi) = , , (N1+N2+,+Nc= N)step1：剪輯。剪輯。利用已知樣本集 中的樣本進(jìn)行預(yù)分預(yù)分 類(lèi)，類(lèi)，并剪輯掉被錯(cuò)分類(lèi)的樣本剪輯掉被錯(cuò)分類(lèi)的樣本，留下的樣本構(gòu)成 剪輯樣本集剪輯樣本集step2：分類(lèi)。分類(lèi)。利用 和近鄰規(guī)則對(duì)未知樣本X進(jìn)行 分類(lèi)。NN11N22NccNENNE下面以?xún)深?lèi)情況以?xún)深?lèi)情況進(jìn)行具體介紹：設(shè)將已知類(lèi)別的樣本集N分成測(cè)試集測(cè)試集NT和參照集參照集NR兩個(gè)獨(dú)立的獨(dú)立的部分(即這兩部分沒(méi)有公共元素沒(méi)有公共元素)，它們的樣本數(shù)各為NR和NT，且NR+NT=N。剪輯步：剪輯步：利用參照集參照集NR中的樣本 對(duì)測(cè)試集對(duì)測(cè)試集NT 中的每個(gè)樣本每個(gè)樣本采用最