非參數(shù)判別分類方法.ppt

1、2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)1,3.6 近鄰法,自動分類的基本方法有兩大類,近鄰法則在原理上屬于模板匹配,（1）將特征空間劃分成決策域 （2）模板匹配,近鄰法的缺點：計算量大，存儲量大,近鄰法的優(yōu)點：在模板數(shù)量很大時其錯誤率指標(biāo)還是相當(dāng)不錯的。,近鄰法的改進(jìn)方法,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)2,重點,弄清楚近鄰法的定義(包括k近鄰法)，與基本做法,弄清“近鄰法性能好”是在什么意義上講的。知道漸進(jìn)平均錯誤率的定義,快速搜索方法是使用怎樣的原理？,剪輯近鄰法的原理是什么? 而壓縮近鄰法與剪輯近鄰法有什么不同之處？,2020/1

2、2/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)3,3.6.1 近鄰法原理及其決策規(guī)則,近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一。這一節(jié)將討論其基本原理，錯誤率分析及若干改進(jìn)方法。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)4,將與測試樣本最近鄰樣本的類別作為決策的方法稱為最近鄰法。對一個C類別問題，每類有Ni個樣本，i1,C, 則第i類i的判別函數(shù),最近鄰法決策規(guī)劃,其中Xik表示是i類的第k個樣本。,如果,則決策Xj,決策規(guī)則為：,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)

3、5,基本規(guī)則是，在所有N個樣本中找到與測試樣本的k個最近鄰者，其中各類別所占個數(shù)表示成ki,i1,c，則決策規(guī)劃是：,k近鄰法決策規(guī)劃,如果,則決策Xj,k近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)6,計算錯誤的偶然性：因為訓(xùn)練樣本集的數(shù)量總是有限的，有時多一個少一個訓(xùn)練樣本對測試樣本分類的結(jié)果影響很大。,利用訓(xùn)練樣本數(shù)量增至極大，來對其性能進(jìn)行評價。,漸近平均錯誤率,3.6.2 近鄰法錯誤率分析,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)7,如果所用訓(xùn)練樣本集的樣本數(shù)量N極大，即

4、N時，可以想像X將趨向于X，或者說處于以X為中心的極小鄰域內(nèi)，此時分析錯誤率問題就簡化為在X樣本條件下X與一個X(X的極限條件)分屬不同類別的問題。如果樣本X的兩類別后驗概率分別為P(1|X)與P(2|X)，那么對X值，在N條件下，發(fā)生錯誤決策的概率為：,最近鄰法錯誤率分析,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)8,(3.6-1),2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)9,漸近平均錯誤率，是PN(e)在N的極限。,與基于最小錯誤率的貝葉斯決策方法對比,其中,而,則,(3.6-2),(3.6-3),2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與

5、技術(shù)學(xué)院,(39)10,由,可得,上式減去,從式(3.6-5)可見在一般情況下P是大于零的值， 只要P(1|X)P(2|X)0。 有以下兩種例外情況P0， 這兩種情況是P(1|X)1或P(1|X)P(2|X)1/2。,(3.6-4),(3.6-5),2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)11,思考,什么情況下P(1|X)1或P(2|X)=1? P(1|X)= P(2|X)會出現(xiàn)什么什么情況？,答：一般來說，在某一類樣本分布密集區(qū)，某一類的后驗概率接近或等于1。此時，基于最小錯誤率貝葉斯決策基本沒錯，而近鄰法出錯可能也很小。而后驗概率近似相等一般出現(xiàn)在兩類分布的交界處，

6、此時分類沒有依據(jù)，因此基于最小錯誤率的貝葉斯決策也無能為力了，近鄰法也就與貝葉斯決策平起平坐了。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)12,當(dāng)N時，最近鄰法的漸近平均錯誤率的下界是貝葉斯錯誤率，這發(fā)生在樣本對某類別后驗概率處處為1的情況或各類后驗概率相等的情況。,在其它條件下，最近鄰法的錯誤率要高于貝葉斯錯誤率，可以證明以下關(guān)系式成立。,一般情況下P*很小,最近鄰法錯誤率上下界與貝葉斯錯誤率的關(guān)系,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)13,k近鄰法錯誤率分析,對于兩類別問題,k-鄰域的情況，則錯誤出現(xiàn)在k個鄰域樣本中，正確的類別所占樣本未

7、過半數(shù)，得到,(3.6-6),2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)14,將(3.6-7)與(3.6-6)相比較，(3.6-6)相當(dāng)于(3.6-7)中k1的情況，而在(3.6-7)中當(dāng)k增大時PkN(e|X)是單調(diào)遞減的。因此可以得出結(jié)論，在N的條件下，k-近鄰法的錯誤率要低于最近鄰法，從圖中也可看出，無論是最近鄰法，還是k-近鄰法，其錯誤率的上下界都是在一倍到兩倍貝葉斯決策方法的錯誤率范圍內(nèi)。,K-近鄰法錯誤率上下界與貝葉斯錯誤率的關(guān)系,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)15,3.6.3 改進(jìn)的近鄰法,近鄰法的嚴(yán)重弱點與問題：需要存儲全

8、部訓(xùn)練樣本，以及繁重的距離計算量。,改進(jìn)的方法大致分為兩種原理：,（1）對樣本集進(jìn)行組織與整理，分群分層，盡可能將計算壓縮到在接近測試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個樣本進(jìn)行距離計算。,（2）在原有樣本集中挑選出對分類計算有效的樣本，使樣本總數(shù)合理地減少，以同時達(dá)到既減少計算量，又減少存儲量的雙重效果。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)16,3.6.3.1 快速搜索近鄰法,這種方法著眼于只解決減少計算量，但沒有達(dá)到減少存儲量的要求。其基本思想是將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，

9、即組又分子組，因而待識別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點所代表的組，確定其相鄰關(guān)系。為了簡單先從最近鄰法討論起。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)17,首先將整個樣本分成l個子集，每個子集又分為它的l個子集。分成子集的原則是該子集內(nèi)的樣本盡可能聚成堆，這可用聚類方法實現(xiàn)。,一、樣本集分級分解,結(jié)點參數(shù)： 樹形結(jié)構(gòu)，每個結(jié)點表示一樣本子集，描述該子集的參數(shù)如下。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)18,樹形結(jié)構(gòu)樣本集,樣本集分解舉例,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)

10、19,要實現(xiàn)快速搜索近鄰，需要有方法快速判斷某個樣本子集是否是該待識樣本的可能近鄰樣本集，從而可將無關(guān)的樣本子集盡快排除。另一方面在某樣本子集內(nèi)尋找哪個樣本是近鄰時，需快速排除不可能為近鄰的樣本。這兩個快速判別算法可用以下兩個規(guī)則表示：,二、快速搜索算法,規(guī)則1：,則Xip不可能是X的近鄰。其中B是待識別樣本在搜索近鄰過程中的當(dāng)前近鄰距離，B在搜索過程中不斷改變與縮小。算法開始可將B設(shè)為無窮大。D(X,Mp)表示待識樣本X到結(jié)點p的均值點距離。,如果存在B+rp D(X,Mp),2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)20,這個規(guī)則的證明是顯而易見的，下圖表示一待識樣本

11、及其當(dāng)前近鄰與一樣本子集的關(guān)系。,判斷某子集是否可能為最近鄰,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)21,規(guī)則2：,則Xi不可能是X的近鄰。,規(guī)則2的證明同規(guī)則1，不再贅述。由此可見，只要將每個樣本子集p中的每個樣本Xi到其均值Mp的距離D(Xi,Mp)存入存儲器中，就可利用上式將許多不可能成為測試樣本近鄰的訓(xùn)練樣本排除。,如果B+D(Xi,Mp) D(X,Mp), 其中Xip,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)22,當(dāng)搜索樹形樣本集結(jié)構(gòu)由高層次向低層次深入時，對同一層次的所有結(jié)點，可以利用規(guī)則1排除掉一些不可能包含待識別樣本的近鄰的結(jié)點

12、(樣本子集)。但是這往往不能做到只留下唯一的待搜索結(jié)點，因此必須選擇其中某一結(jié)點先深入搜索，以類似于深度優(yōu)先的方法確定搜索路徑直至葉結(jié)點。然而在該葉結(jié)點中找到的近鄰并不能保證確實是全樣本集中的最近鄰者，所找到的該近鄰樣本需要在那些有可能包含最近鄰的樣本子集中核對與修正，直至找到真正的最近鄰樣本為止。,搜索算法的大體過程,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)23,步驟1：初始化置B，L1(當(dāng)前層次)，p0(確定當(dāng)前結(jié)點)。,步驟2：設(shè)置后選待搜索結(jié)點把當(dāng)前結(jié)點的所有直接后繼結(jié)點放入層的一目錄表中，并對這些結(jié)點計算D(X，Mp)。,步驟3：排除無關(guān)結(jié)點對層目錄表中的每個

13、結(jié)點P，用規(guī)則1將與近鄰無緣的結(jié)點從目錄表中清除。,步驟4：路徑選擇如該層次目錄表中有不止一個結(jié)點，選其中D(X，Mp)最小者，將該結(jié)點從目錄表中刪除，如該結(jié)點是葉結(jié)點轉(zhuǎn)步驟5，如不是葉結(jié)點，則LL+1，轉(zhuǎn)步驟2；如該層次目錄表中無結(jié)點待搜索，則LL-1，如L0則停止，否則轉(zhuǎn)步驟3。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)24,步驟5：近鄰樣本搜索對現(xiàn)在執(zhí)行結(jié)點p中的每個樣本Xi，利用規(guī)則2作如下檢驗： 如果D(X，Mp)D(Xi,Mp)+B則Xi不是X的最近鄰，否則計算D(X，Xi)，若D(X，Xi)B，置NNi和BD(X,Xi)。對當(dāng)前執(zhí)行結(jié)點中所有Xi被檢驗后，

14、轉(zhuǎn)步驟3。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)25,k-近鄰法快速計算是搜索待測樣本的k個最近鄰，以做到最后在這k個最近鄰中計算占多數(shù)的訓(xùn)練樣本類別。因此只要發(fā)現(xiàn)有一個訓(xùn)練樣本比當(dāng)前第k個近鄰的距離要小，就把當(dāng)前第k個近鄰剔除出當(dāng)前k近鄰組。,k近鄰法的快速搜索算法,k-近鄰法的快速計算法與上述過程大體相同，只是B值修改為當(dāng)前第k個近鄰的距離值。然后在步驟5中，對所計算的距離要與該k個當(dāng)前的近鄰比較，若比其中某個距離小，則刪除最大者。除了以上兩點修正外，其它算法與最近鄰快速算法一樣。,以上是快速算法的原理與計算過程。至于樹結(jié)構(gòu)的層次與葉結(jié)點內(nèi)樣本個數(shù)的選擇在設(shè)計時

15、根據(jù)中間結(jié)點計算與葉結(jié)點計算的綜合平衡考慮。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)26,3.6.3.2 剪輯近鄰法,剪輯近鄰法著眼于如何減少模板樣本數(shù)目，從而可同時減少分類時的計算量及模板樣本的存儲量，同時還能進(jìn)一步改進(jìn)分類器的性能，如降低錯誤率等要求。,剪輯近鄰法除了在樣本數(shù)量上有一定程度的減少外，更主要的優(yōu)點是錯誤率的降低。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)27,當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯誤率主要來自處于交迭區(qū)中的樣本。當(dāng)我們得到一個作為識別用的參考樣本集時，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用

16、近鄰法分類出錯。因此如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實現(xiàn)既減少樣本數(shù)又提高正確識別率的雙重目的。為此可以利用現(xiàn)有樣本集對其自身進(jìn)行剪輯。下面以兩類別問題為例說明這種方法的原理。,剪輯近鄰法的基本思想,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)28,假設(shè)現(xiàn)有一個樣本集N，樣本數(shù)量為N。將此樣本集分成兩個互相獨立的樣本子集。一個被當(dāng)作考試集NT，另一個作為參考集NR，數(shù)量分別為NT與NR，NT+NRN。將NT中的樣本表示成Xi,(i=1,2, NT)，而在NR中的樣本表示為Yj,(j=1,2, NR)。,剪輯近鄰法,一個樣本集分成兩個相互獨立的樣本子集是指，分

17、完以后的兩個子集具有相同的分布，例如將一個樣本集分成兩個相互獨立的對等子集，則在每個特征空間的子區(qū)域，兩個子集都有相同的比例，或說各類數(shù)量近似相等。要注意指出的是每個子區(qū)域(從大空間到小空間)實際做時要用從總的集合中隨機(jī)抽取的方式進(jìn)行。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)29,首先對NT中每一個Xi在NR中找到其最近鄰的樣本Yi(Xi)，用Yi(Xi)表示Yi是Xi的最近鄰參考樣本。如果Yi與Xi不屬于同一類別，則將Xi從NT中刪除，最后從NT中得到一個經(jīng)過剪輯的樣本集，稱為剪輯樣本集NTE。 NTE可用來取代原樣本集N，作為參考樣本集對待識別樣本進(jìn)行分類。,剪輯

18、的過程,NT經(jīng)過剪輯后，要作為新的訓(xùn)練樣本集，則NR是對其性能進(jìn)行測試的樣本，如發(fā)現(xiàn)NT中的某個訓(xùn)練樣本對分類不利，就要把它剪輯掉。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)30,剪輯樣本的過程也可以用k-近鄰法進(jìn)行。,剪輯近鄰法也可用到多類別情況。,剪輯過程也可不止一次，重復(fù)多次的稱為重復(fù)剪輯近鄰法。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)31,1. 將樣本集N隨機(jī)劃分為S個子集，即,重復(fù)剪輯法步驟,N=1, 2, S, S=3,2. 用最近鄰法，以j,j=(i+1)mod S為參考集，對i中的樣本進(jìn)行分類，其中i1,S。,3. 去掉步驟2中

19、被錯分類的樣本。,4. 用所有留下的全部樣本的構(gòu)成新的樣本集NE 。,5. 如該次剪輯過程中沒有樣本被刪除，則停止，否則轉(zhuǎn)步驟1。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)32,從圖1到圖4可以看出,剩下的樣本集形成了兩個很好的聚類,并且在每個聚類中的樣本都屬于同一類.,MULTIEDIT算法實驗,圖1 原始樣本集,圖2 經(jīng)一次迭代的結(jié)果,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)33,圖3 經(jīng)三次迭代的結(jié)果,圖4 算法終止時留下的樣本,動畫演示,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)34,1. 利用最近鄰法剪輯后得到的樣

20、本集進(jìn)行分類，其錯誤率總小于原樣本集，如用P1E(e)表示其錯誤率，則有,剪輯近鄰法錯誤率的分析,其中P(e)表示用原樣本的漸近平均錯誤率。,由于近鄰法錯誤率上界為2P*(兩倍貝葉斯錯誤率)，因而,在P(e)很小，如P(e)0.1情況下可有,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)35,2. 利用k-近鄰法進(jìn)行剪輯得到的樣本集進(jìn)行分類，則在N及k，且K/N0的條件下有,該式表明k很大時，剪輯樣本法的錯誤率可收斂于最優(yōu)情況P*。當(dāng)然實際上k值不能取得太大。,3.多類情況，剪輯效果更好。,2020/12/5,中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,(39)36,3.6.3.3 壓縮近鄰法,剪輯近鄰法所得到的剪輯樣本集在樣本數(shù)量的壓縮方面并不十分明顯，它的作用在于將原樣本集中處于邊界處的樣本刪除掉，但靠近兩類中心的大部分樣本仍被保留下來。,然而按近鄰規(guī)則來看，這些樣本