模式識別-第8講-近鄰法課件

模式識別

授課教師薛耀紅xueyh@模式識別 授課教師薛耀紅第8講近鄰法第8講近鄰法本節(jié)課主要內(nèi)容1最近鄰法2k－近鄰法3改進(jìn)的近鄰法3.1快速搜索近鄰法3.2剪輯近鄰法3.3壓縮近鄰法4最佳距離度量近鄰法本節(jié)課主要內(nèi)容1最近鄰法回顧最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為類別代表點，考查新樣本到各代表點的距離并將它分到最近的代表點所代表的類。極端情況，將所有樣本都作為代表點－－－－近鄰法回顧最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心1最近鄰法問題描述:

特征向量類別X=(0.1,0.1)?特征向量類別(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W21最近鄰法問題描述:特征向量1最近鄰法最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，并在每個子類中確定代表點，一般用子類的質(zhì)心或鄰近質(zhì)心的某一樣本為代表點。測試樣本的類別則以其與這些代表點距離最近作決策。該法的缺點是所選擇的代表點并不一定能很好地代表各類，其后果將使錯誤率增加。最近鄰法的基本思想：以全部訓(xùn)練樣本作為“代表點”，計算測試樣本與這些“代表點”，即所有樣本的距離，并以最近鄰者的類別作為決策。近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。1最近鄰法最小距離分類器：將各類訓(xùn)練樣本劃分成若干子類，1最近鄰法將與測試樣本最近鄰樣本的類別作為決策的方法稱為最近鄰法。1最近鄰法將與測試樣本最近鄰樣本的類別作為決策的方法稱為1最近鄰法1最近鄰法1最近鄰法在二維情況下，最近鄰規(guī)則算法使得二維空間被分割成了許多Voronoi網(wǎng)格，每一個網(wǎng)格代表的類別就是它所包含的訓(xùn)練樣本點所屬的類別。1最近鄰法在二維情況下，最近鄰規(guī)則算法使得二維空間被分割最近鄰法的錯誤率

最近鄰法的錯誤率是比較難計算的，這是因為訓(xùn)練樣本集的數(shù)量總是有限的，有時多一個少一個訓(xùn)練樣本對測試樣本分類的結(jié)果影響很大。紅點表示A類訓(xùn)練樣本，藍(lán)點表示B類訓(xùn)練樣本，而綠點O表示待測樣本。假設(shè)以歐氏距離來衡量，O的最近鄰是A3，其次是B1，因此O應(yīng)該屬于A類；但若A3被拿開，O就會被判為B類。最近鄰法的錯誤率最近鄰法的錯誤率是比較難計算的，這是因為訓(xùn)最近鄰法的錯誤率這說明計算最近鄰法的錯誤率會有偶然性，也就是指與具體的訓(xùn)練樣本集有關(guān)。同時還可看到，計算錯誤率的偶然性會因訓(xùn)練樣本數(shù)量的增大而減小。因此我們就利用訓(xùn)練樣本數(shù)量增至極大，來對其性能進(jìn)行評價。這要使用漸近概念，以下都是在漸近概念下來分析錯誤率的。

最近鄰法的錯誤率最近鄰法的錯誤率當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時，其錯誤率是帶有偶然性的。

下圖所示為一個在一維特征空間的兩類別情況：

X表示一待測試樣本，而X'是所用訓(xùn)練樣本集中X的最鄰近者，則錯誤是由X與X'分屬不同的類別所引起的。最近鄰法的錯誤率當(dāng)最近鄰法所使用的訓(xùn)練樣本數(shù)量N不是很大時，最近鄰法的錯誤率由于X’與所用訓(xùn)練樣本集有關(guān)，因此錯誤率有較大偶然性。但是如果所用訓(xùn)練樣本集的樣本數(shù)量N極大，即N→∞時，可以想像X’將趨向于X，或者說處于以X為中心的極小鄰域內(nèi)，此時分析錯誤率問題就簡化為在X樣本條件下X與一個X(X’的極限條件)分屬不同類別的問題。如果樣本X的兩類別后驗概率分別為P(ω1|X)與P(ω2|X)，那么對X值，在N→∞條件下，發(fā)生錯誤決策的概率為：最近鄰法的錯誤率由于X’與所用訓(xùn)練樣本集有關(guān)，因此錯誤率有較最近鄰法的錯誤率而在這條件下的平均錯誤率

P稱為漸近平均錯誤率，是PN(e)在N→∞的極限。為了與基于最小錯誤率的貝葉斯決策方法對比，下面寫出貝葉斯錯誤率的計算式：

其中最近鄰法的錯誤率而在這條件下的平均錯誤率最近鄰法的錯誤率

若是兩類問題，則

貝葉斯錯誤率：最近鄰法錯誤率：可見在一般情況下△P是大于零的值，只要P(ω1|X)＞P(ω2|X)＞0。最近鄰法的錯誤率若是兩類問題，則最近鄰法的錯誤率有以下兩種例外情況△P＝0：P(ω1|X)＝1P(ω1|X)＝P(ω2|X)＝1/2。最近鄰法的錯誤率有以下兩種例外情況△P＝0：最近鄰法的錯誤率請想一下，什么情況下P(ω1|X)＝1或P(ω2|X)=1?P(ω1|X)=P(ω2|X)會出現(xiàn)什么什么情況？

一般來說，在某一類樣本分布密集區(qū)，某一類的后驗概率接近或等于1。此時，基于最小錯誤率貝葉斯決策基本沒錯，而近鄰法出錯可能也很小。而后驗概率近似相等一般出現(xiàn)在兩類分布的交界處，此時分類沒有依據(jù)，因此基于最小錯誤率的貝葉斯決策也無能為力了，近鄰法也就與貝葉斯決策平起平坐了。從以上討論可以看出，當(dāng)N→∞時，最近鄰法的漸近平均錯誤率的下界是貝葉斯錯誤率，這發(fā)生在樣本對某類別后驗概率處處為1的情況或各類后驗概率相等的情況。

最近鄰法的錯誤率請想一下，什么情況下P(ω1|X)＝1或P(最近鄰法的錯誤率最近鄰法的錯誤率最近鄰法的錯誤率最近鄰法的錯誤率高于貝葉斯錯誤率，可以證明以下關(guān)系式成立：由于一般情況下P*很小，因此又可粗略表示成：可粗略說最近鄰法的漸近平均錯誤率在貝葉斯錯誤率的兩倍之內(nèi)。

最近鄰法的錯誤率最近鄰法的錯誤率高于貝葉斯錯誤率，可以證明以小結(jié)模式識別（機器自動分類）的基本方法有兩大類：一類是將特征空間劃分成決策域，這就要確定判別函數(shù)或確定分界面方程。另一種方法則稱為模板匹配，即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個模板匹配度更好些，從而確定待測試樣本的分類。前面討論的方法可以說都是將特征空間劃分為決策域，并用判別函數(shù)或決策面方程表示決策域的方法。近鄰法則在原理上屬于模板匹配。它將訓(xùn)練樣本集中的每個樣本都作為模板，用測試樣本與每個模板做比較，看與哪個模板最相似(即為近鄰)，就按最近似的模板的類別作為自己的類別。小結(jié)模式識別（機器自動分類）的基本方法有兩大類：前面討論的方作業(yè)：1、什么是模式與模式識別？2、一個典型的模式識別系統(tǒng)主要由哪幾個部分組成？3、什么是后驗概率？4、描述貝葉斯公式及其主要作用。5、請詳細(xì)寫出感知器訓(xùn)練算法步驟。6、請詳細(xì)寫出Fisher算法實現(xiàn)步驟。作業(yè)：1、什么是模式與模式識別？2k－近鄰法k-近鄰法:

最近鄰法的擴展，其基本規(guī)則是，在所有N個樣本中找到與測試樣本的k個最近鄰者，其中各類別所占個數(shù)表示成ki,i＝1，…，c。判別函數(shù)為：

gi(x)=ki,i=1,2,…,c。

決策規(guī)則為：

k-近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。2k－近鄰法k-近鄰法:最近鄰法的擴展，其基本規(guī)則是，2k－近鄰法

從樣本點x開始生長，不斷擴大區(qū)域，直到包含進(jìn)k個訓(xùn)練樣本點為止，并且把測試樣本點x的類別歸為這最近的k個訓(xùn)練樣本點中出現(xiàn)頻率最大的類別。2k－近鄰法從樣本點x開始生長，不斷擴大區(qū)域，直K近鄰法的錯誤率對于最近鄰法PN(e|x,x’)＝P(ω1|x)P(ω2|x’)+P(ω2|x)P(ω1|x’)當(dāng)N->∞時，P(ωi|x’)近似等于P(ωi|x)PN->∞(e|x,x’)＝P(ω1|x)P(ω2|x)+P(ω2|x)P(ω1|x)對于K近鄰法

K近鄰法的錯誤率對于最近鄰法K近鄰法的錯誤率對所有的x，有：

PN->∞k(e|x)≤Ck[P*(e|x)](Ck[P*(e|x)]為貝葉斯條件錯誤率的函數(shù))根據(jù)Jensen不等式,P=E[PNk(e|x)]≤E{Ck[P*(e|x)]}≤CkE{[P*(e|x)]}=Ck(P*)不等式關(guān)系P*≤P≤Ck(P*)≤Ck-1(P*)≤…≤C1(P*)≤2P*(1-P*)

K近鄰法的錯誤率對所有的x，有：k－近鄰法的錯誤率最近鄰法和k-近鄰法的錯誤率上下界都是在一倍到兩倍貝葉斯決策方法的錯誤率范圍內(nèi)。在k→∞的條件下，k-近鄰法的錯誤率要低于最近鄰法。在k→∞的條件下，k-近鄰法的錯誤率等于貝葉斯誤差率。k－近鄰法的錯誤率最近鄰法和k-近鄰法的錯誤率上下界都是在一3改進(jìn)的近鄰法

盡管近鄰法有其優(yōu)良品質(zhì)，但是它的一個嚴(yán)重弱點與問題是需要存儲全部訓(xùn)練樣本，以及繁重的距離計算量。

但以簡單的方式降低樣本數(shù)量，只能使其性能降低，這也是不希望的。為此要研究既能減少近鄰法計算量與存儲量，同時又不明顯降低其性能的一些改進(jìn)算法。改進(jìn)的方法大致分為兩種原理。一種是對樣本集進(jìn)行組織與整理，分群分層，盡可能將計算壓縮到在接近測試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個樣本進(jìn)行距離計算。另一種原理則是在原有樣本集中挑選出對分類計算有效的樣本，使樣本總數(shù)合理地減少，以同時達(dá)到既減少計算量，又減少存儲量的雙重效果。3改進(jìn)的近鄰法盡管近鄰法有其優(yōu)良品質(zhì)，但是它的一個嚴(yán)重3.1改進(jìn)的近鄰法-快速搜索近鄰法這種方法著眼于只解決減少計算量，但沒有達(dá)到減少存儲量的要求。

基本思想：將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，即組又分子組。因而待識別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點所代表的組，確定其相鄰關(guān)系。3.1改進(jìn)的近鄰法-快速搜索近鄰法這種方法著眼于只解決減少快速搜索近鄰法（1）樣本集的分級分解首先將整個樣本分成l個子集，每個子集又分為它的l個子集，如此進(jìn)行若干次就能建立起一個樣本集的樹形結(jié)構(gòu)。分成子集的原則是該子集內(nèi)的樣本盡可能聚成堆，這可用聚類方法實現(xiàn)。

結(jié)點參數(shù)：樹形結(jié)構(gòu)，每個結(jié)點表示一樣本子集，描述該子集的參數(shù)是：

快速搜索近鄰法（1）樣本集的分級分解快速搜索近鄰法用樹結(jié)構(gòu)表示樣本分級:p:樹中的一個結(jié)點，對應(yīng)一個樣本子集KpNp:Kp中的樣本數(shù)Mp:Kp中的樣本均值rp:從Kp中任一樣本到Mp的最大距離快速搜索近鄰法用樹結(jié)構(gòu)表示樣本分級:快速搜索近鄰法（2）快速搜索算法

要實現(xiàn)快速搜索近鄰，需要有方法快速判斷某個樣本子集是否是該待識樣本的可能近鄰樣本集，從而可將無關(guān)的樣本子集盡快排除;另一方面在某樣本子集內(nèi)尋找哪個樣本是近鄰時，需快速排除不可能為近鄰的樣本。

這兩個快速判別算法可用以下兩個規(guī)則表示?？焖偎阉鹘彿ǎ?）快速搜索算法快速搜索近鄰法

規(guī)則1：如果存在則不可能是X的近鄰。其中B是待識別樣本在搜索近鄰過程中的當(dāng)前近鄰距離，B在搜索過程中不斷改變與縮小。算法開始可將B設(shè)為無窮大。表示待識樣本X到結(jié)點的均值點距離。

快速搜索近鄰法快速搜索近鄰法

規(guī)則2：如果其中Xi∈，則Xi不可能是X的近鄰。由此可見，只要將每個樣本子集中的每個樣本Xi到其均值Mp的距離D(Xi,Mp)存入存儲器中，就可利用上式將許多不可能成為測試樣本近鄰的訓(xùn)練樣本排除。

快速搜索近鄰法快速搜索近鄰法（3）搜索算法

搜索算法的大體過程是這樣的：當(dāng)搜索樹形樣本集結(jié)構(gòu)由高層次向低層次深入時，對同一層次的所有結(jié)點，可以利用規(guī)則1排除掉一些不可能包含待識別樣本的近鄰的結(jié)點(樣本子集)。但是這往往不能做到只留下唯一的待搜索結(jié)點，因此必須選擇其中某一結(jié)點先深入搜索，以類似于深度優(yōu)先的方法確定搜索路徑直至葉結(jié)點。然而在該葉結(jié)點中找到的近鄰并不能保證確實是全樣本集中的最近鄰者，所找到的該近鄰樣本需要在那些有可能包含最近鄰的樣本子集中核對與修正，直至找到真正的最近鄰樣本為止?？焖偎阉鹘彿ǎ?）搜索算法樹搜索算法置B=∞，L=0，p=0將當(dāng)前結(jié)點的所有直接后繼結(jié)點放入一個目錄表中，并對這些結(jié)點計算D(x,Mp)根據(jù)規(guī)則1從目錄表中去掉step2中的某些結(jié)點如果目錄表已無結(jié)點則置L=L-1，如果L=0則停止，否則轉(zhuǎn)Step3。如果目錄表有一個以上的結(jié)點，則轉(zhuǎn)step5在目錄表中選出最近結(jié)點p’為當(dāng)前執(zhí)行結(jié)點。如果當(dāng)前的水平L是最終水平，則轉(zhuǎn)Step6，否則置L=L+1，轉(zhuǎn)Step2對當(dāng)前執(zhí)行結(jié)點p’中的每個xi，根據(jù)規(guī)則2決定是否計算D(x,xi)。若D(x,xi)<B，則置NN=i和B=D(x,xi)，處理完當(dāng)前執(zhí)行結(jié)點中的每個xi后轉(zhuǎn)Step3當(dāng)算法結(jié)束時，輸出x的最近鄰xNN和x與xNN的距離B樹搜索算法置B=∞，L=0，p=03.2改進(jìn)的近鄰法-剪輯近鄰法目的：去掉靠近兩類中心的樣本？基本思想：當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯誤率主要來自處于交迭區(qū)中的樣本。當(dāng)我們得到一個作為識別用的參考樣本集時，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實現(xiàn)既減少樣本數(shù)又提高正確識別率的雙重目的。為此可以利用現(xiàn)有樣本集對其自身進(jìn)行剪輯。3.2改進(jìn)的近鄰法-剪輯近鄰法目的：去掉靠近兩類中心的樣本3.2改進(jìn)的近鄰法-剪輯近鄰法剪輯的過程是：將樣本集KN分成兩個互相獨立的子集：考試（test）集KT和參考（reference）集KR。首先對KT中每一個Xi在參考集KR中找到其最近鄰的樣本Yi(Xi)

。如果Yi與Xi不屬于同一類別，則將Xi從考試集KT中刪除，最后得到一個剪輯的樣本集KTE（剪輯樣本集），以取代原樣本集，對待識別樣本進(jìn)行分類。剪輯的結(jié)果是去掉兩類邊界附近的樣本。3.2改進(jìn)的近鄰法-剪輯近鄰法剪輯的過程是：將樣本集KN分MULTIEDIT算法MULTIEDIT算法正太分布樣本集合正太分布樣本集合正太分布樣本集合正太分布樣本集合正太分布樣本集合正太分布樣本集合正太分布樣本集合正太分布樣本集合非正太分布樣本集合非正太分布樣本集合非正太分布樣本集合非正太分布樣本集合非正太分布樣本集合非正太分布樣本集合3.3改進(jìn)的近鄰法-壓縮近鄰法壓縮近鄰法：利用現(xiàn)有樣本集，逐漸生成一個新的樣本集，使該樣本集在保留最少量樣本的條件下，仍能對原有樣本的全部用最近鄰法正確分類，那么該樣本集也就能對待識別樣本進(jìn)行分類，并保持正常識別率。3.3改進(jìn)的近鄰法-壓縮近鄰法壓縮近鄰法：利用現(xiàn)有樣本集，3.3改進(jìn)的近鄰法-壓縮近鄰法定義兩個存儲器，一個用來存放即將生成的樣本集，稱為Store；另一存儲器則存放原樣本集，稱為Grabbag。其算法是：初始化。Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個樣本。樣本集生成。在Grabbag中取出第i個樣本用Store中的當(dāng)前樣本集按最近鄰法分類。若分類錯誤，則將該樣本從Grabbag轉(zhuǎn)入Store中，若分類正確，則將該樣本放回Grabbag中。結(jié)束過程。若Grabbag中所有樣本在執(zhí)行第二步時沒有發(fā)生轉(zhuǎn)入Store的現(xiàn)象，或Grabbag已成空集，則算法終止，否則轉(zhuǎn)入第二步。3.3改進(jìn)的近鄰法-壓縮近鄰法定義兩個存儲器，一個用來存放模式識別-第8講-近鄰法ppt課件4.最佳距離度量近鄰法在x的局部臨近區(qū)域中，定義新的距離函數(shù)

其中xl為x的局部鄰域中的樣本,可以證明，

x的最近鄰x’必有滿足：

按照上面定義的新距離，在x的局部鄰域中選擇x的最近鄰x’,則可使有限樣本與無限樣本的錯誤率之差在均方意義下達(dá)到最小。

需要說明：上述距離度量使通過對P(wi|x’)在x的局部鄰域區(qū)域中做線性近似得到的，因此，它只適合于KN中與x較為接近的那些樣本。4.最佳距離度量近鄰法在x的局部臨近區(qū)域中，定義新的距離函

距離度量

的計算（兩類情況）令A(yù)表示以x為中心的一個局部鄰近區(qū)域，A中有NA個樣本xl，其中個屬于wi類，局部樣本均值的估計為則有距離度量的計算（兩類情況）令A(yù)表示以x4.最佳距離度量近鄰法根據(jù)

尋找x最近鄰的程序步驟(兩類情況)

(1)計算||x-x1||,…,||x-xN||(2)找出與x距離是最短的NA個近鄰xl，l=1,2,…,lNA

(3)利用xl計算M1-M0(4)計算|(M1-M0)T(x-xl1)|,…,|(M1-M0)T(x-xlNA)選出其中最小者，若為xlk,則xlk為x的按照距離度量的最近鄰，即xlk

＝x’

4.最佳距離度量近鄰法根據(jù)5.模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)別

從參數(shù)判別方法看，它的前提是對特征空間中的各類樣本的分布清楚，因此一旦要測試分類樣本的特征向量值X已知，就可以確定X對各類的后驗概率，也就可按相應(yīng)的準(zhǔn)則計算與分類。如果這種分布可以用正態(tài)分布等描述，那么決策域的判別函數(shù)與分界面方程就可用函數(shù)的形式確定下來。所以判別函數(shù)等的確定取決于樣本統(tǒng)計分布的有關(guān)知識。因此參數(shù)分類判別方法一般只能用在有統(tǒng)計知識的場合，或能利用訓(xùn)練樣本估計出參數(shù)的場合。5.模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)別非參數(shù)分類判別方法則著眼于直接利用訓(xùn)練樣本集，省去參數(shù)估計這一環(huán)節(jié)，這樣一來，從保證最小錯誤率的原則出發(fā)計算確定判別函數(shù)的方法就不適用了。因此非參數(shù)分類判別方法只能根據(jù)一些其它準(zhǔn)則來設(shè)計分類器。分類器的效果好壞，常指分類的錯誤率，一般在理論上很難說明，主要靠實踐來檢驗。所選擇的判別函數(shù)型式，所使用的訓(xùn)練樣本集，以及所用的算法對結(jié)果都會有影響。模式分類方法總結(jié)一、參數(shù)判別分類方法與非參數(shù)判別分類方法的區(qū)模式分類方法總結(jié)二、非參數(shù)分類判別方法的基本做法

使用非參數(shù)分類判別方法進(jìn)行分類器設(shè)