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

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

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

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

4、N時(shí)，可以想像X將趨向于X，或者說處于以X為中心的極小鄰域內(nèi)，此時(shí)分析錯(cuò)誤率問題就簡(jiǎn)化為在X樣本條件下X與一個(gè)X(X的極限條件)分屬不同類別的問題。如果樣本X的兩類別后驗(yàn)概率分別為P(1|X)與P(2|X)，那么對(duì)X值，在N條件下，發(fā)生錯(cuò)誤決策的概率為：,最近鄰法錯(cuò)誤率分析,2020/12/5,中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,(39)8,(3.6-1),2020/12/5,中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,(39)9,漸近平均錯(cuò)誤率，是PN(e)在N的極限。,與基于最小錯(cuò)誤率的貝葉斯決策方法對(duì)比,其中,而,則,(3.6-2),(3.6-3),2020/12/5,中國(guó)礦業(yè)大學(xué) 計(jì)算機(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,中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,(39)11,思考,什么情況下P(1|X)1或P(2|X)=1? P(1|X)= P(2|X)會(huì)出現(xiàn)什么什么情況？,答：一般來說，在某一類樣本分布密集區(qū)，某一類的后驗(yàn)概率接近或等于1。此時(shí)，基于最小錯(cuò)誤率貝葉斯決策基本沒錯(cuò)，而近鄰法出錯(cuò)可能也很小。而后驗(yàn)概率近似相等一般出現(xiàn)在兩類分布的交界處，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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