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

1、第3章 非參數(shù)判別分類方法,非參數(shù)判別分類法,貝葉斯決策具有理論： 要設(shè)法獲取樣本統(tǒng)計(jì)分布的資料,要知道先驗(yàn)概率，類分布概率密度函數(shù)等。在樣本數(shù)不足條件下獲取準(zhǔn)確的統(tǒng)計(jì)分布是困難的另一條道路：即根據(jù)訓(xùn)練樣本集提供的信息，直接進(jìn)行分類器設(shè)計(jì)。 這種方法繞過(guò)統(tǒng)計(jì)分布狀況的分析，繞過(guò)參數(shù)估計(jì)這一環(huán)，而企圖對(duì)特征空間實(shí)行劃分，稱為非參數(shù)判別分類法，即不依賴統(tǒng)計(jì)參數(shù)的分類法。,學(xué)習(xí)指南,了解非參數(shù)判別分

2、類方法在模式識(shí)別技術(shù)中所處的地位。是當(dāng)前模式識(shí)別中主要使用的方法。非參數(shù)判別分類方法的核心是由訓(xùn)練樣本集提供的信息直接確定決策域的劃分方法。最重要的概念是分類器設(shè)計(jì)用一種訓(xùn)練與學(xué)習(xí)的過(guò)程來(lái)實(shí)現(xiàn)。要進(jìn)一步體會(huì)模式識(shí)別中以確定準(zhǔn)則函數(shù)并實(shí)現(xiàn)優(yōu)化的計(jì)算框架。,學(xué)習(xí)目的,掌握非參數(shù)判別分類法的原理掌握機(jī)器自學(xué)習(xí)的原理。學(xué)習(xí)線性分類器的幾種典型算法用近鄰法進(jìn)行分類通過(guò)相應(yīng)數(shù)學(xué)工具的運(yùn)用進(jìn)一步提高運(yùn)用數(shù)學(xué)的本領(lǐng),重點(diǎn),非參數(shù)判別分類

3、器的基本原理，與參數(shù)判別分類方法的比較線性分類器的幾種典型方法—— 以Fisher準(zhǔn)則為代表的傳統(tǒng)模式識(shí)別方法 以感知準(zhǔn)則函數(shù)為代表的機(jī)器自學(xué)習(xí)方法近鄰法的工作原理及其改進(jìn)線性分類器擴(kuò)展到非線性分類器兩類別分類方法與多類別分類方法,難點(diǎn),Fisher準(zhǔn)則函數(shù)，其中用到向量點(diǎn)積，帶約束條件的拉格朗日乘子法以及矩陣的特征值、特征向量等數(shù)學(xué)工具。要求對(duì)這些數(shù)學(xué)工具較深理解。 感知器準(zhǔn)則函數(shù)提出利用錯(cuò)誤提供信息實(shí)現(xiàn)

4、疊代修正的學(xué)習(xí)原理近鄰法的改進(jìn),§3.1引言,貝葉斯決策理論設(shè)計(jì)分類器的步驟非參數(shù)判別分類,非參數(shù)判別分類方法兩個(gè)過(guò)程,使用什么典型的分類決策方法利用訓(xùn)練樣本集提供的信息確定這些函數(shù)中的參數(shù)。,§3.2 線性分類器,3.2.1 線性判別函數(shù)的基本概念 兩類別問(wèn)題中線性判別函數(shù)的一般形式,ω0是一個(gè)常數(shù)，稱為閾值權(quán),決策規(guī)則,g(X)＝0就是相應(yīng)的決策面方程，在線性判別函數(shù)條件下它對(duì)應(yīng)d維空間的一個(gè)

5、超平面,向量W的意義,設(shè)在該決策平面上有兩個(gè)特征向量X1與X2，則 W與該平面上任兩點(diǎn)組成的向量(X1-X2)正交W是該超平面的法線向量,g(X)也就是d維空間中任一點(diǎn)X到該決策面H的距離的代數(shù)度量 w0體現(xiàn)該決策面在特征空間中的位置w0=0時(shí)，該決策面過(guò)特征空間坐標(biāo)系原點(diǎn)，否則， 表示坐標(biāo)原點(diǎn)到該決策面的距離,,,g(X) / ||W||,,,,R0=w0 / ||W||,X,Xp,R1: g>0,R2:

6、 g<0,正側(cè),負(fù)側(cè),H: g=0,3.2.2　廣義線性判別函數(shù),欲設(shè)計(jì)這樣一個(gè)一維樣本的分類器，使其性能為：線性判別函數(shù)：無(wú)能為力設(shè)計(jì)判別函數(shù)　　g(x)＝(x-a)(x-b)　 決策規(guī)則　　 　　　若：g(x)>0, 決策：X∈w1　 g(x)<0, 決策：X∈w2,,采用映射x→Y判別函數(shù)g(x)又可表示成,g(x)被稱為廣義線性判別函數(shù)， a 稱為廣義權(quán)向量,推廣

7、----線性判別函數(shù)的齊次簡(jiǎn)化,將g(x)中的W向量與w0統(tǒng)一表示成,稱為增廣樣本向量,a:稱為增廣權(quán)向量 (廣義權(quán)向量),它使特征空間增加了一維，但保持了樣本間的歐氏距離不變，對(duì)于分類效果也與原決策面相同，只是在Y空間中決策面是通過(guò)坐標(biāo)原點(diǎn)的，這在分析某些問(wèn)題時(shí)具有優(yōu)點(diǎn)，因此經(jīng)常用到。,例如：一個(gè)一維特征空間的分類器，其決策面方程為： X-c=0　在一維空間中為一個(gè)點(diǎn)。經(jīng)齊次簡(jiǎn)化后得：,,3.2.3　線性分類器設(shè)計(jì)步驟,線性分類

8、器設(shè)計(jì)任務(wù) 在給定樣本集XX={X1,X2,…,XN}條件下， 確定線性判別函數(shù)的各項(xiàng)系數(shù),w1,w2,…,wd ，以期對(duì)待測(cè)樣本進(jìn)行分類時(shí)，能滿足相應(yīng)的準(zhǔn)則函數(shù)J為最優(yōu)的要求。關(guān)鍵問(wèn)題: 確定所需的準(zhǔn)則函數(shù)，然后用最優(yōu)化技術(shù)確定準(zhǔn)則函數(shù)的極值解w*及w0*，或增廣權(quán)向量 a*,具體過(guò)程,1 、按需要確定一準(zhǔn)則函數(shù)J?！　? 、確定準(zhǔn)則函數(shù)J達(dá)到極值時(shí)w*及w0*的具體數(shù)值，從而確定判別函數(shù)，完成分類

9、器設(shè)計(jì)。 設(shè)計(jì)線性分類器，是指所用的判別函數(shù)、分界面方程的類型已選定為線性類型，因此主要的設(shè)計(jì)任務(wù)是確定線性方程的兩個(gè)參數(shù)，一個(gè)是權(quán)向量W，另一個(gè)是閾值w0。,3.3　Fisher線性判別函數(shù),Fisher線性判別函數(shù)是研究這類判別函數(shù)中最有影響的方法之一。對(duì)線性判別函數(shù)的研究就是從R.A.Fisher在1936年發(fā)表的論文開始的。,3.3.1 Fisher準(zhǔn)則函數(shù),Fisher準(zhǔn)則基本原理,如果在二維空間中一條

10、直線能將兩類樣本分開，或者錯(cuò)分類很少，則同一類別樣本數(shù)據(jù)在該直線的單位法向量上的投影的絕大多數(shù)都應(yīng)該超過(guò)某一值。而另一類數(shù)據(jù)的投影都應(yīng)該小于(或絕大多數(shù)都小于)該值，則這條直線就有可能將兩類分開。 準(zhǔn)則：向量W的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些，而使類內(nèi)樣本的離散程度盡可能小。這就是Fisher準(zhǔn)則函數(shù)的基本思路。 y=WTX,樣本在d維特征空間的一些描述量,(1) 各類樣本均值向量mi(2) 樣本類內(nèi)離散度矩陣Si

11、與總類內(nèi)離散度矩陣Sw(3) 樣本類間離散度矩陣Sb,2 在一維Y空間,(1) 各類樣本均值 　　　 　　　　(2) 樣本類內(nèi)離散度 和總類內(nèi)離散度,Fisher準(zhǔn)則的函數(shù)形式,Fisher選擇投影方向W的原則： y=WTX 類間分布盡可能分開， 類內(nèi)樣本投影盡可能密集的要求評(píng)價(jià)投影方向W的函數(shù),進(jìn)一步化為W的顯函數(shù),分子,分母,分母：,3.3.2　最佳W值的確定,最佳W值的確定: 求取使JF達(dá)極大值時(shí)的

12、 w*設(shè)計(jì)一拉格朗日函數(shù),對(duì)向量的求導(dǎo)(或偏導(dǎo))的定義是,由于Sw非奇異，兩邊乘以Sw-1得,,,最佳法線向量,使Fisher準(zhǔn)則函數(shù)JF達(dá)極大值的解，也就是按Fisher準(zhǔn)則將d維X空間投影到一維Y空間的最佳投影方向。,是在兩類正態(tài)分布但具有相同的協(xié)方差矩陣Σ時(shí)，按最小錯(cuò)誤率的貝葉斯決策得到的結(jié)果。BAYES: 如果P(ωi)=P(ωj)，則最佳分界線就是兩類概率密度函數(shù)值相等的點(diǎn)的集合。兩類樣本的離散矩陣相近，也就是說(shuō)兩類分

13、布的形式很相近，按Fisher準(zhǔn)則，錯(cuò)分率就應(yīng)比較小，F(xiàn)isher準(zhǔn)則的合理性可以在這里體現(xiàn),3.3.3　判別函數(shù)的確定,w0確定,當(dāng)     與     已知時(shí),（P(W1)、P(W2)已知時(shí)）實(shí)驗(yàn)確定,分類規(guī)則,3.4　感知準(zhǔn)則函數(shù),感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，企圖將其用于腦模型感知器，因此被稱為感

14、知準(zhǔn)則函數(shù)。特點(diǎn)是隨意確定的判別函數(shù)初始值，在對(duì)樣本分類訓(xùn)練過(guò)程中逐步修正直至最終確定。,線性可分性,設(shè)已知樣本集{y1,y2,…,yN}， yn是d維增廣樣本向量。分屬于ω1 和ω2類。若存在權(quán)向量a,使任何y∈ω1 ,都有：aTy>0 y∈ω2 ,都有：aTy<0 則稱這組樣本集線性可分?；颍喝魳颖炯蔷€性可分的，則必存在一個(gè)權(quán)向量a，可使每個(gè)樣本正確分類。,樣

15、本規(guī)范化,感知準(zhǔn)則函數(shù)使用增廣樣本向量與增廣權(quán)向量在線性可分條件下，廣義權(quán)向量a應(yīng)有：　　若 Y∈ω1 ,則：aTY>0 Y∈ω2 ,則：aTY0.,解區(qū)與解向量,滿足aTY’>0的權(quán)向量a稱為解向量。解向量存在無(wú)窮多個(gè)，是一區(qū)域，稱為解區(qū),對(duì)解區(qū)的限制,目的：使解向量更可靠越靠近解區(qū)中間的解向量越好解區(qū)邊界上的解向量不好引入余量b，解向量應(yīng)滿足： aTY’&g

16、t;b.,,,,,,,,,aTY’>b.,aTY’>0.,感知準(zhǔn)則函數(shù)方法的思路,隨意找一個(gè)初始向量 a(0)用訓(xùn)練樣本集中的每個(gè)樣本Y來(lái)計(jì)算。 若Y’使aTY’<0，則a不適合，需進(jìn)一步修正。 設(shè)當(dāng)前經(jīng)k次疊代修正的廣義權(quán)向量為a(k)，修正為 理論證明，只要訓(xùn)練樣本集線性可分，無(wú)論a(0)的初值是什么，經(jīng)過(guò)有限次疊代，都可找到合適的a。,感知準(zhǔn)則函數(shù),感知準(zhǔn)則函數(shù)方法是一種利用錯(cuò)分類對(duì)

17、現(xiàn)決策權(quán)向量進(jìn)行修正直至收斂的方法。這種方法只對(duì)線性可分情況適用。對(duì)于任何一個(gè)增廣權(quán)向量a 若該向量能將樣本集正確分類，則 aTY>0 令被錯(cuò)分類的規(guī)范化增廣樣本集為yk 定義一準(zhǔn)則函數(shù),感知準(zhǔn)則函數(shù)的極小值,常用的方法是梯度下降算法 即對(duì)第k次迭代值，求其梯度向量，并令迭代向量沿此負(fù)梯度向量方向修正迭代公式,感知準(zhǔn)則函數(shù)利用梯度下降算法,可簡(jiǎn)單敘述為： 任意給定一向量初始值a

18、(1)，第k+1次迭代時(shí)的權(quán)向量a(k+1)等于第k次的權(quán)向量a(k)加上被錯(cuò)分類的所有樣本之和與ρk 的乘積。 可以證明，對(duì)于線性可分的樣本集，經(jīng)過(guò)有限次修正，一定可以找到一個(gè)解向量 ，即算法能在有限步內(nèi)收斂。 其收斂速度的快慢取決于初始權(quán)向量a(k) 和系數(shù)ρk 。,例：三個(gè)樣本,,,,感知準(zhǔn)則函數(shù)方法只對(duì)線性可分樣本集有效對(duì)線性不可分的樣本集，該算法不能收斂。其它方法，如最小錯(cuò)分樣本數(shù)準(zhǔn)則等。這

19、一節(jié)對(duì)感知準(zhǔn)則函數(shù)的討論，只是很初步的，并且只討論了線性可分的情況。但這種利用錯(cuò)誤提供的信息，進(jìn)行自修正的思想意義是十分深遠(yuǎn)的。 這種只解決線性分類的感知器稱為單層感知器，由它基礎(chǔ)上發(fā)展起來(lái)的多層感知器在原理上能解決非線性分類、多類劃分，以及非線性擬和非線性映射等多種功能，是人工神經(jīng)元網(wǎng)絡(luò)的基礎(chǔ)。,3.5 最小錯(cuò)分樣本數(shù)準(zhǔn)則,若樣本集線性不可分，則對(duì)于任何a，均有某些樣本被錯(cuò)分類。尋找使最多數(shù)目樣本滿足正確分類的

20、a，即滿足aTyn>0的不等式數(shù)目最多。,,用矩陣形式重寫不等式組： Ya>0其中：為使解更可靠，引入余量b>0,則 Ya>b’>0,準(zhǔn)則,最小平方誤差準(zhǔn)則,不等式組寫為： aTyn=bn>0方程組：Ya=b,,實(shí)際上無(wú)精確解，設(shè)a是一個(gè)解，則有誤差誤差向量：e=Ya-b平方誤差準(zhǔn)則（MSE----Minim

21、um Square Error）,3.6　多類問(wèn)題,兩類別問(wèn)題中使用的線性判別函數(shù)方法可以推廣到多類別問(wèn)題中 將C類別問(wèn)題化為(C-1)個(gè)兩類問(wèn)題，即將第i類與所有非i類樣本，按兩類問(wèn)題確定其判別函數(shù)與決策面方程。因此對(duì)于C類，則總共有(C-1)個(gè)兩類別問(wèn)題，,兩個(gè)問(wèn)題,可能會(huì)出現(xiàn)一些不定區(qū)域，如圖中陰影所示，在這些區(qū)域中的樣本無(wú)法確定其類別。另一方面用線性判別函數(shù)對(duì)i類及所有非i類進(jìn)行劃分并不能保證獲得性能良好的劃分，硬性使用線性

22、分類器可能會(huì)產(chǎn)生很不好的效果。,另一種做法,將C類中的每?jī)深悇e單獨(dú)設(shè)計(jì)其線性判別函數(shù)，總共有C(C-1)/2個(gè)線性判別函數(shù)。這種方法由于每個(gè)判別函數(shù)針對(duì)每?jī)深悇e樣本設(shè)計(jì)，預(yù)期可有好效果，但仍有不定區(qū)域，在該區(qū)域內(nèi)樣本類別無(wú)法確定。,線性機(jī)器,將特征空間確實(shí)劃分為C個(gè)決策域，共有C個(gè)判別函數(shù)每個(gè)決策域Ri按以下規(guī)則劃分,決策樹,,,,,,,,,,,,1,n2,n3,n4,n5,T1 t2

23、t3 t4 t5 t6 t7,二叉樹,,,,,,,,,t1,t2,t3,t4,t5,n1,n2,n3,3.7 非線性判別函數(shù),對(duì)實(shí)際的模式識(shí)別問(wèn)題來(lái)說(shuō)，各類在特征空間中的分布往往比較復(fù)雜，因此無(wú)法用線性分類函數(shù)得到好的效果。傳統(tǒng)的模式識(shí)別技術(shù)，則側(cè)重于使用分段線性判別函數(shù)，因此基本上是沿用了線性判別函數(shù)的方法。人工神經(jīng)元網(wǎng)絡(luò)如多層感知器等網(wǎng)絡(luò)能夠?qū)嵱?/p>

24、非常復(fù)雜的非線性分類，以及非線性函數(shù)擬合，非線性映射等。支持向量機(jī)提出了一種基于特征映射的方法，也就是使用某種映射，使本來(lái)在原特征空間必須使用非線性分類技術(shù)才能解決的問(wèn)題,映射到一個(gè)新的空間以后, 使線性分類技術(shù)能繼續(xù)使用。,3.7.1 非線性判別函數(shù)與分段線性判別函數(shù),,分段線性判別函數(shù),分段線性判別函數(shù)的分段段數(shù)問(wèn)題 過(guò)少：效果差 過(guò)多：計(jì)算量大同一類樣本可以用若干個(gè)子類來(lái)描述，子類的數(shù)目就可作為確定分段段數(shù)的依據(jù)

25、。 樣本分布及子類劃分已定的情況下，設(shè)計(jì)分段線性判別函數(shù)的問(wèn)題，著重討論幾種典型的設(shè)計(jì)原理 樣本分布及合適子類劃分并不知道，則采用聚類的方法,分段線性判別函數(shù)的一般形式,分段線性判別函數(shù)的一般形式可定義為 表示第i類第l段線性判別函數(shù)，li為i類所具有的判別函數(shù)個(gè)數(shù) 分別是第l段的權(quán)向量與閾值權(quán),判別規(guī)則,若：其中： 稱為第i類的判別函數(shù) 決策：,決策面方程,取決于相鄰

26、的決策域，如第i類的第n個(gè)子類與第j類的第m個(gè)子類相鄰，則,3.7.2基于距離的分段線性判別函數(shù),,決策規(guī)則,如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或者說(shuō)把屬于ωi的決策域Ri分成li個(gè)子域，即 每個(gè)子區(qū)域R il均值用m il表示，作為該子區(qū)域的代表點(diǎn)判別函數(shù)定義為：　　 　　　　　判別規(guī)則是：　　如果,,對(duì)樣本進(jìn)行子類的合適劃分是分段線性距離分類器性能好壞的一個(gè)關(guān)鍵問(wèn)題,3.7.3 錯(cuò)誤修正

27、算法,aiTy， ajTy相比較的含義 aiTy是ai向量與y向量的點(diǎn)積，一般來(lái)說(shuō)點(diǎn)積值比較大則表示這兩個(gè)向量在方向上比較一致，換句話說(shuō)向量間的夾角較小。 如果某一類樣本比較分散，但是能用若干個(gè)增廣權(quán)向量表示。 同一類規(guī)范化增廣樣本向量：與代表自己一類的增廣權(quán)向量的點(diǎn)積的最大值比與其它類增廣權(quán)向量的點(diǎn)積值要大。 可以做到正確分類 這種算法就是要用錯(cuò)誤提供的信息進(jìn)行疊代修正。,,對(duì)每類樣

28、本集進(jìn)行具體劃分，希望能知道每類所需的增廣權(quán)向量數(shù)目。該數(shù)目可以在計(jì)算過(guò)程中按分類效果調(diào)整。,當(dāng)每類的子類數(shù)目已知時(shí),可以采用假設(shè)初始權(quán)向量，然后由樣本提供的錯(cuò)誤率信息進(jìn)行迭代修正，直至收斂。該算法的基本要點(diǎn)：對(duì)每個(gè)類別的子類賦予一初始增廣權(quán)向量 對(duì)每次迭代所得增廣權(quán)向量用樣本去檢測(cè)，如發(fā)生錯(cuò)誤分類，則利用錯(cuò)誤分類的信息進(jìn)行修正。其做法是：,先將某一j類的增廣樣本向量yj，與該類所有增廣權(quán)向量求內(nèi)積，找到其中的最大值

29、將該yj與其它類(如i類)的權(quán)向量求內(nèi)積，并作比較表明這些權(quán)向量都不再需要修改。,果存在某個(gè)或幾個(gè)子類不滿足上述條件，譬如某個(gè)子類 的現(xiàn)有權(quán)向量 使得這表明yj將錯(cuò)分類，有關(guān)權(quán)向量需要修正 首先找到導(dǎo)致yj錯(cuò)分類的所有權(quán)向量中具有與yj內(nèi)積最大值的權(quán)向量,接著對(duì) 作相應(yīng)修正然后利用權(quán)向量的新值重復(fù)以上過(guò)程，直到收斂或迫使其收斂。

30、這種算法在樣本確實(shí)能被分段線性判別函數(shù)正確劃分的條件下是收斂的。當(dāng)該條件不滿足時(shí)，則需逐步減小ρk的數(shù)值，迫使其“收斂”，顯然會(huì)有相應(yīng)的錯(cuò)誤率存在。,3.7.4 局部訓(xùn)練法,它的出發(fā)點(diǎn)是類間的分界面必然處在兩類樣本的交界處，因此只需找出這些交界處的樣本，然后對(duì)這些鄰近的不同類樣本,按需要確定分界面即可。,幾個(gè)問(wèn)題,參加訓(xùn)練的局部樣本集由兩類樣本組成。這些區(qū)域稱之為“交遇區(qū)”，局部訓(xùn)練法就是基于交遇區(qū)內(nèi)的樣本進(jìn)行設(shè)計(jì)的。(1) 如何

31、從樣本集中找到“交遇區(qū)”；(2)如何利用“交遇區(qū)”中樣本設(shè)計(jì)線性分類器(3)如何進(jìn)行分類決策。,緊互對(duì)原型與交遇區(qū),尋找“交遇區(qū)”是先在每類樣本集內(nèi)進(jìn)行分片劃分，所使用的方法是聚類方法 找到處在本類樣本占領(lǐng)區(qū)域邊界上的小片原型。若分屬兩類的兩個(gè)原型互為最近鄰，那么這兩個(gè)原型就被認(rèn)定為處在兩類樣本決策域的交界處，它們所在區(qū)域就成為交遇區(qū)。,找到兩類樣本的交遇區(qū),首先對(duì)這兩類樣本進(jìn)行聚類分析，找出它們各自的一些相對(duì)密集的子區(qū)域（“原

32、型區(qū)”） 在每個(gè)原型區(qū)中找到一個(gè)質(zhì)心或距質(zhì)心很近的樣本作為各原型區(qū)的代表點(diǎn)，稱為“原型”。 找出各原型在對(duì)方類型中相距最近的原型對(duì) 找到互為最小距離的原型對(duì)組成“緊互對(duì)原型對(duì)”。緊互對(duì)原型對(duì)的集合組成“交遇區(qū)”,局部訓(xùn)練法,如何利用“交遇區(qū)”來(lái)設(shè)計(jì)分界面的問(wèn)題。 基本思想： 邊界由若干個(gè)交遇區(qū)確定，在每個(gè)交遇區(qū)中只有兩種不同類型的樣本。由這些樣本產(chǎn)生一個(gè)合適的分界面，一般使用分段線性分界面。具體做法：

33、 利用處于最緊貼邊界的緊互對(duì)原型對(duì)產(chǎn)生一初始分界面，然后利用交遇區(qū)進(jìn)行調(diào)整，這種調(diào)整屬于局部性的調(diào)整。,分段線性判別函數(shù)產(chǎn)生,步驟一： 產(chǎn)生初始超平面　　首先由緊互對(duì)原型對(duì)集合中最近的一對(duì)， 產(chǎn)生一個(gè)初始決策面的方程。例如可由這兩個(gè)原型的垂直平分平面作為初始界面，表示成H1 步驟二： 初始決策面最佳化 確定H1能正確分類的所有緊互對(duì)原型對(duì)，并由這些原型對(duì)中的樣本組成局部訓(xùn)練的樣本集

34、，按所使用的準(zhǔn)則設(shè)計(jì)出線性決策面H1*，該決策面對(duì)現(xiàn)有局部樣本集來(lái)說(shuō)是最佳的。對(duì)該H1決策面又可找出它能正確分類的所有緊互對(duì)原型對(duì)。如果H1* 與H1’的分類效果相同，則H1* 不需再調(diào)整，否則由H1*作為初始決策面重復(fù)上述過(guò)程，直到所包羅的局部訓(xùn)練樣本集不再發(fā)生變化為止。,,步驟三： 新決策面的產(chǎn)生與最佳化　　在找到一個(gè)最佳的決策面段后，將相應(yīng)的局部訓(xùn)練樣本從原緊互對(duì)原型對(duì)集合中撤走，然后在剩下的緊互對(duì)原型對(duì)集合重復(fù)上述步驟，產(chǎn)生另

35、一個(gè)超平面分界面，如此重復(fù)下去直到所有緊互對(duì)原型對(duì)都被處理完畢，得到一系列超平面，組成分段線性分類器。,分段線性分類器檢驗(yàn)一個(gè)決策規(guī)則的確定,在使用上述方法得到一組超平面作為分段線性分類器的分界面后，需要使用全體樣本對(duì)其進(jìn)行性能檢驗(yàn)，觀察其能否對(duì)全體樣本作出合理的劃分。,使用全體樣本進(jìn)行檢驗(yàn)及改進(jìn),如果現(xiàn)有的決策界面為每一個(gè)樣本yj處在哪個(gè)區(qū)域，可用它們與這些增廣權(quán)向量 的內(nèi)積符號(hào)表示 內(nèi)積符號(hào)的總效果：定義一個(gè)由樣本Xj(用

36、增廣樣本向量yj表示)決策的m維向量,處在同一區(qū)域的所有樣本都有同樣的向量值 全體樣本將被劃分若干子集，最大可能的子集數(shù)為2m個(gè) 每個(gè)子集都可能包含兩個(gè)類別的訓(xùn)練樣本，但在每個(gè)子集中兩類樣本分布的不同，將作為劃分與改進(jìn)決策域的依據(jù),用 表示在第k個(gè)子集中第l類訓(xùn)練樣本的個(gè)數(shù)，k＝1，…，2m,l＝1，2比值函數(shù) 表示每個(gè)子集中ω1類樣本所占比例根據(jù)L值及N1(Z

37、K)與N2(ZK)這三個(gè)數(shù)據(jù)，可對(duì)各個(gè)區(qū)域作相應(yīng)決定：,,如果L>>1/2，則ZK區(qū)域?yàn)棣?的決策域；如果L<<1/2，則ZK區(qū)域?yàn)棣?的決策域；如果L≈1/2，以及N1(ZK)、N2(ZK)很小，則對(duì)ZK內(nèi)樣本可作拒絕決策；如果L≈1/2，但N1(ZK)與N2(ZK)數(shù)量不可忽略，則對(duì)此區(qū)域，用該子集的樣本再次進(jìn)行局部訓(xùn)練法訓(xùn)練，以獲得其進(jìn)一步劃分。重復(fù)上述過(guò)程，直至對(duì)所有區(qū)域都能合理地確定為哪一類的決

38、策域，或拒識(shí)區(qū)域?yàn)橹埂?圖中的樣本采用上述方法后，決策平面由兩個(gè)(H1、H2)增至三個(gè)，即H、H2與H3組成。至于對(duì)每類樣本的決策規(guī)劃，可用上面提到的m維向量作決策。例如圖 (b)中Z向量為(1，1，1)、(1，1，0)以及(0，1，0)的區(qū)域?yàn)棣?的決策域，而(0，1，1)(0，0，0)及(0，0，1)區(qū)域則為ω1的決策域。,§3.8 近鄰法,自動(dòng)分類的基本方法有兩大類一類是將特征空間劃分成決策域，這就要確定判別函數(shù)或確

39、定分界面方程。另一種方法則稱為模板匹配，即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個(gè)模板匹配度更好些，從而確定待測(cè)試樣本的分類。,,近鄰法是由Cover和Hart于1968年提出的，隨后得到理論上深入的分析與研究，是非參數(shù)法中最重要的方法之一 近鄰法則在原理上屬于模板匹配 近鄰法的缺點(diǎn)：計(jì)算量大，存儲(chǔ)量大近鄰法的優(yōu)點(diǎn)：在模板數(shù)量很大時(shí)其錯(cuò)誤率指標(biāo)還是相當(dāng)不錯(cuò)的 改進(jìn)的辦法：剪輯近鄰法與壓縮近鄰法,3.8.1 近鄰法原理及其決策規(guī)

40、則,最小距離分類器。將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)。測(cè)試樣本的類別則以其與這些代表點(diǎn)距離最近作決策。該法的缺點(diǎn)：所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測(cè)試樣本與這些“代表點(diǎn)”，即所有樣本的距離，并以最近鄰者的類別作為決策。------近鄰法的基本思想,3.8.1.1 最近鄰法決策規(guī)劃,將與測(cè)試樣本最近鄰樣本的類別作為決策的方法稱為最近鄰法。對(duì)一個(gè)C類

41、別問(wèn)題，每類有Ni個(gè)樣本，i＝1，…，C，則第i類ωi的判別函數(shù)Xik表示是ωi類的第k個(gè)樣本,判別函數(shù)的決策規(guī)則,若：則：X∈ωj,3.8.1.2 k-近鄰法決策規(guī)則,基本規(guī)則 在所有N個(gè)樣本中找到與測(cè)試樣本的k個(gè)最近鄰者，其中各類別所占個(gè)數(shù)表示成ki,i＝1，…，co 則決策規(guī)劃是：　　如果 則：X∈ωj,3.8.2 近鄰法錯(cuò)誤率分析,近鄰法的錯(cuò)誤率是比較難算的，因?yàn)橛?xùn)

42、練樣本集的數(shù)量總是有限的，有時(shí)多一個(gè)少一個(gè)訓(xùn)練樣本對(duì)測(cè)試樣本分類的結(jié)果影響很大 利用訓(xùn)練樣本數(shù)量增至極大，來(lái)對(duì)其性能進(jìn)行評(píng)價(jià)。這要使用漸近概念，是在漸近概念下來(lái)分析錯(cuò)誤率的,一維特征空間的兩類別情況X表示一待測(cè)試樣本，X‘是X的最鄰近者錯(cuò)誤是由X與X'分屬不同的類別所引起的。由于X'與所用訓(xùn)練樣本集有關(guān)，因此錯(cuò)誤率有較大偶然性。,3.8.2.1 最近鄰法錯(cuò)誤率分析,N→∞時(shí)，X'將趨向于X此時(shí)分析錯(cuò)誤率問(wèn)

43、題就簡(jiǎn)化為在X樣本條件下X與一個(gè)X(X‘的極限條件)分屬不同類別的問(wèn)題。如果樣本X的兩類別后驗(yàn)概率分別為P(ω1|X)與P(ω2|X)，那么對(duì)X值，在N→∞條件下，發(fā)生錯(cuò)誤決策的概率為：,,漸近平均錯(cuò)誤率 基于最小錯(cuò)誤率的貝葉斯決策方法,可見在一般情況下△P是大于零的值，只要P(ω1|X)＞P(ω2|X)＞0。有以下兩種例外情況△P＝0，這兩種情況是P(ω1|X)＝1的情況或P(ω1|X)＝P(ω2|X)＝1/2。,,當(dāng)N→

44、∞時(shí)，最近鄰法的漸近平均錯(cuò)誤率的下界是貝葉斯錯(cuò)誤率，這發(fā)生在樣本對(duì)某類別后驗(yàn)概率處處為1的情況或各類后驗(yàn)概率相等的情況?！　≡谄渌鼦l件下，最近鄰法的錯(cuò)誤率要高于貝葉斯錯(cuò)誤率，可以證明以下關(guān)系式成立,,一般情況下P*很小 則：P*<P<2P*,3.8.2.2 k-近鄰法錯(cuò)誤率分析,對(duì)于兩類別問(wèn)題， 推廣到k-鄰域的情況，則錯(cuò)誤出現(xiàn)在k個(gè)鄰域樣本中，正確的類別所占樣本未過(guò)半數(shù)，得到,,當(dāng)k增大時(shí) 是

45、單調(diào)遞減的。因此,在N→∞的條件下，k-近鄰法的錯(cuò)誤率要低于最近鄰法。,不同k值時(shí)的錯(cuò)誤率,0 0.25 0.5,0.50.250,P*<P<2P*,3.8.3 改進(jìn)的近鄰法,近鄰法的弱點(diǎn)與問(wèn)題：需要存儲(chǔ)全部訓(xùn)練樣本，以及繁重的距離計(jì)算量。在所有情況下，對(duì)未知樣本都能進(jìn)行決策，但當(dāng)錯(cuò)誤代價(jià)太大時(shí)，會(huì)產(chǎn)生較大風(fēng)險(xiǎn)。上述分析是漸近的，要求N →∞,無(wú)法實(shí)現(xiàn)。

46、 以簡(jiǎn)單的方式降低樣本數(shù)量，只能使其性能降低，這也是不希望的。,改進(jìn)的思路,要研究既能減少近鄰法計(jì)算量與存儲(chǔ)量，同時(shí)又不明顯降低其性能的一些改進(jìn)算法。改進(jìn)的方法大致分為兩種原理。一種是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測(cè)試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。另一種原理則是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重

47、效果。下面就一些典型算法進(jìn)行討論。,3.8.3.1 近鄰法的快速算法,這種方法著眼于只解決減少計(jì)算量，但沒(méi)有達(dá)到減少存儲(chǔ)量的要求。其基本思想是將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，即組又分子組，因而待識(shí)別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點(diǎn)所代表的組，確定其相鄰關(guān)系。為了簡(jiǎn)單先從最近鄰法討論起。,一、樣本集分級(jí)分解,首先將整個(gè)樣本分成

48、l個(gè)子集，每個(gè)子集又分為它的l個(gè)子集，如此進(jìn)行若干次就能建立起一個(gè)樣本集的樹形結(jié)構(gòu)。分成子集的原則是該子集內(nèi)的樣本盡可能聚成堆，這可用聚類方法實(shí)現(xiàn)。,結(jié)點(diǎn)參數(shù),結(jié)點(diǎn)參數(shù)： 樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)表示一樣本子集，描述該子集的參數(shù)是：,例：一個(gè)樹形結(jié)構(gòu)樣本集，分支數(shù)l＝3,二、快速搜索算法,要實(shí)現(xiàn)快速搜索近鄰，需要有方法快速判斷某個(gè)樣本子集是否是該待識(shí)樣本的可能近鄰樣本集，從而可將無(wú)關(guān)的樣本子集盡快排除。另一方面在某樣本子集內(nèi)尋找哪個(gè)樣本是

49、近鄰時(shí)，需快速排除不可能為近鄰的樣本。 這兩個(gè)快速判別算法可用以下兩個(gè)規(guī)則表示：,規(guī)則1：,如果存在則 不可能是X的近鄰。其中B是待識(shí)別樣本在搜索近鄰過(guò)程中的當(dāng)前近鄰距離，B在搜索過(guò)程中不斷改變與縮小。算法開始可將B設(shè)為無(wú)窮大。 表示待識(shí)樣本X到結(jié)點(diǎn) 的均值點(diǎn)距離。,例：一待識(shí)樣本及其當(dāng)前近鄰與一樣本子集的關(guān)系,,規(guī)則2：,如果　　 　　　　 　　其中Xi∈ ，則Xi不可能是

50、X的近鄰。規(guī)則2的證明同規(guī)則1，不再贅述?？梢姡灰獙⒚總€(gè)樣本子集 中的每個(gè)樣本Xi到其均值Mp的距離D(Xi,Mp)存入存儲(chǔ)器中，就可利用上式將許多不可能成為測(cè)試樣本近鄰的訓(xùn)練樣本排除。,搜索算法的大體過(guò)程,當(dāng)搜索樹形樣本集結(jié)構(gòu)由高層次向低層次深入時(shí)，對(duì)同一層次的所有結(jié)點(diǎn)，可以利用規(guī)則1排除掉一些不可能包含待識(shí)別樣本的近鄰的結(jié)點(diǎn)(樣本子集)。但是這往往不能做到只留下唯一的待搜索結(jié)點(diǎn)，因此必須選擇其中某一結(jié)點(diǎn)先深入搜索，以類似于深

51、度優(yōu)先的方法確定搜索路徑直至葉結(jié)點(diǎn)。然而在該葉結(jié)點(diǎn)中找到的近鄰并不能保證確實(shí)是全樣本集中的最近鄰者，所找到的該近鄰樣本需要在那些有可能包含最近鄰的樣本子集中核對(duì)與修正，直至找到真正的最近鄰樣本為止。,搜索步驟,步驟1： [初始化]置B＝∞，L＝1(當(dāng)前層次)，p＝0(確定當(dāng)前結(jié)點(diǎn))。步驟2： [置后選待搜索結(jié)點(diǎn)]把當(dāng)前結(jié)點(diǎn)的所有直接后繼結(jié)點(diǎn)放入層的一目錄表中，并對(duì)這些結(jié)點(diǎn)計(jì)算D(X，Mp)。步驟3： [排除無(wú)關(guān)結(jié)點(diǎn)]對(duì)層目錄表中的

52、每個(gè)結(jié)點(diǎn)P，用規(guī)則1將與近鄰無(wú)緣的結(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)，則L＝L+1，轉(zhuǎn)步驟2；如該層次目錄表中無(wú)結(jié)點(diǎn)待搜索，則L＝L-1，如L＝0則停止，否則轉(zhuǎn)步驟3。,步驟5： [近鄰樣本搜索]對(duì)現(xiàn)在執(zhí)行結(jié)點(diǎn)p中的每個(gè)樣本Xi，利用規(guī)則2作如下檢驗(yàn)： 如果D(X，Mp)＞D(Xi,Mp)+B則Xi不是

53、X的最近鄰，否則計(jì)算D(X，Xi)，若D(X，Xi)＜B，置NN＝i和B＝D(X,Xi)。對(duì)當(dāng)前執(zhí)行結(jié)點(diǎn)中所有Xi被檢驗(yàn)后，轉(zhuǎn)步驟3。在算法結(jié)束時(shí)，輸出X的最近鄰XNN及兩者間距離,k-近鄰法的快速計(jì)算,-近鄰法快速計(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-近鄰法的快速計(jì)算法與上述過(guò)程大體相同，只

54、是B值修改為當(dāng)前第k個(gè)近鄰的距離值。然后在步驟5中，對(duì)所計(jì)算的距離要與該k個(gè)當(dāng)前的近鄰比較，若比其中某個(gè)距離小，則刪除最大者。除了以上兩點(diǎn)修正外，其它算法與最近鄰快速算法一樣。以上是快速算法的原理與計(jì)算過(guò)程。至于樹結(jié)構(gòu)的層次與葉結(jié)點(diǎn)內(nèi)樣本個(gè)數(shù)的選擇在設(shè)計(jì)時(shí)根據(jù)中間結(jié)點(diǎn)計(jì)算與葉結(jié)點(diǎn)計(jì)算的綜合平衡考慮。,3.8.3.2 剪輯近鄰法,以上討論的快速算法只是研究如何減少計(jì)算量的問(wèn)題，而不考慮存儲(chǔ)量的壓縮。實(shí)際上由于對(duì)樣本進(jìn)行分層次分組，并附

55、有一些參數(shù)，實(shí)際的存儲(chǔ)量還有可能增加。本節(jié)討論的算法著眼于如何減少模板樣本數(shù)目，從而可同時(shí)減少分類時(shí)的計(jì)算量及模板樣本的存儲(chǔ)量，同時(shí)還能進(jìn)一步改進(jìn)分類器的性能，如降低錯(cuò)誤率等要求。,剪輯近鄰法的基本思想,當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯(cuò)誤率主要來(lái)自處于交迭區(qū)中的樣本。當(dāng)我們得到一個(gè)作為識(shí)別用的參考樣本集時(shí)，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可

56、以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。,例,假設(shè)現(xiàn)有一個(gè)樣本集N，樣本數(shù)量為N。我們將此樣本集分成兩個(gè)互相獨(dú)立的樣本子集。一個(gè)被當(dāng)作考試集 ，另一個(gè)作為參考集 ，數(shù)量分別為NT與NR，NT+NR＝N。將 中的樣本表示成 ， 而在 中的樣本表示為,,將一個(gè)樣本集分成兩個(gè)相互獨(dú)立的樣本子集是指，分完

57、以后的兩個(gè)子集具有相同的分布例如將一個(gè)樣本集分成兩個(gè)相互獨(dú)立的對(duì)等子集，則在每個(gè)特征空間的子區(qū)域，兩個(gè)子集都有相同的比例，或說(shuō)各類數(shù)量近似相等。要注意指出的是每個(gè)子區(qū)域(從大空間到小空間)實(shí)際做時(shí)要用從總的集合中隨機(jī)抽取的方式進(jìn)行。,剪輯的過(guò)程,首先對(duì) æNT 中每一個(gè)Xi在æNR中找到其最近鄰的樣本Yi(Xi)，用Yi(Xi)表示Yi是Xi的最近鄰參考樣本。如果Yi與Xi不屬于同一類別，則將Xi從 æN

58、T 中刪除。最后從æNT中得到一個(gè)經(jīng)過(guò)剪輯的樣本集，稱為剪輯樣本集æNTE ?？捎脕?lái)取代原樣本集æN ，作為參考樣本集對(duì)待識(shí)別樣本進(jìn)行分類。,æNT經(jīng)過(guò)剪輯后，要作為新的訓(xùn)練樣本集，則æNR 是對(duì)其性能進(jìn)行測(cè)試的樣本，如發(fā)現(xiàn) æNT中的某個(gè)訓(xùn)練樣本對(duì)分類不利，就要把它剪輯掉。剪輯樣本的過(guò)程也可以用k-近鄰法進(jìn)行，即對(duì) 中的每個(gè)樣本Xi，找到在 中的k個(gè)近鄰，用k-近鄰法判斷

59、Xi是否被錯(cuò)分類。剪輯近鄰法也可用到多類別情況。剪輯過(guò)程也可不止一次。重復(fù)多次的稱為重復(fù)剪輯近鄰法。,重復(fù)剪輯算法步驟,將樣本集æN 隨機(jī)劃分為S個(gè)子集，即　　 æN={æ1,æ2,…,æs}, s≥3用最近鄰法，以 æj，j=(i+1)mod(s)為參考集，對(duì) æj中的樣本進(jìn)行分類，其中i＝1，…，s。去掉步驟2中被錯(cuò)分類的樣本。用所有留下的全部

60、樣本的構(gòu)成新的樣本集æN 。如該次剪輯過(guò)程中沒(méi)有樣本被刪除，則停止，否則轉(zhuǎn)步驟1。,例：兩類正態(tài)分布樣本的重復(fù)剪輯,原始樣本集 一次迭代的結(jié)果，,,三次迭代留下的樣本 算法終止時(shí)留下的樣本,剪輯近鄰法錯(cuò)誤率的分析,利用最近鄰法剪輯后得到的樣本集進(jìn)行分類，其錯(cuò)誤率P1E(e)總小于原樣本集　　 　 P1E(e) ≤P(e)　　　　其中P(e)表示用原樣本的漸近平

61、均錯(cuò)誤率。在P(e)很小，如P(e)<0.1情況下可有　　 　　 P1E(e) ≤P(e)/2由于近鄰法錯(cuò)誤率上界為2P*(兩倍貝葉斯錯(cuò)誤率)，因而　　 　　 P1E(e) ≤P*,,利用k-近鄰法進(jìn)行剪輯得到的樣本集進(jìn)行分類，則在N→∞及k→∞，且K/N→0的條件下有 P1E(e) ≤P*該式表明k很大時(shí)，剪輯樣本法的錯(cuò)誤率可收斂于最優(yōu)情況P*。當(dāng)然實(shí)際上k值不能取得太大?！《囝惽闆r，剪輯效果更好。,3.8.3.3

62、 壓縮近鄰法,剪輯近鄰法所得到的剪輯樣本集在樣本數(shù)量的壓縮方面并不十分明顯，它的作用在于將原樣本集中處于邊界處的樣本刪除掉，但靠近兩類中心的大部分樣本仍被保留下來(lái)。然而按近鄰規(guī)則來(lái)看，這些樣本中的大多數(shù)對(duì)分類決策沒(méi)什么用處，如能在剪輯的基礎(chǔ)上再去掉一部分這樣的樣本，將有助于進(jìn)一步縮短計(jì)算時(shí)間與壓縮存儲(chǔ)量，這種方法稱為壓縮近鄰法。,壓縮近鄰法壓縮樣本的思想,利用現(xiàn)有樣本集，逐漸生成一個(gè)新的樣本集。使該樣本集在保留最少量樣本的條件下, 仍

63、能對(duì)原有樣本的全部用最近鄰法正確分類，那末該樣本集也就能對(duì)待識(shí)別樣本進(jìn)行分類, 并保持正常識(shí)別率。該算法的作法也十分簡(jiǎn)單，它定義兩個(gè)存儲(chǔ)器，一個(gè)用來(lái)存放即將生成的樣本集，稱為Store；另一存儲(chǔ)器則存放原樣本集，稱為Grabbag。,算法,初始化］Store是空集，原樣本集存入Grabbag；從Grabbag中任意選擇一樣本放入Store中作為新樣本集的第一個(gè)樣本。[樣本集生成］在Grabbag中取出第i個(gè)樣本用Store中的當(dāng)前樣