2.2非參數(shù)判別分類法貝葉斯決策理論：需要知道先驗(yàn)概率，類條件概率密度函數(shù)等。

類條件概率密度函數(shù)的確定是通過(guò)確定其函數(shù)形式p(x|ωi)并對(duì)其參數(shù)估計(jì)來(lái)完成的。因此，以貝葉斯決策方法為基礎(chǔ)的方法稱為參數(shù)判別方法問(wèn)題：1）類條件概率密度函數(shù)形式p(x|ωi)很難確定

2）在樣本數(shù)不足條件下獲取準(zhǔn)確的統(tǒng)計(jì)分布是困難的1非參數(shù)判別分類法解決辦法：根據(jù)訓(xùn)練樣本集直接進(jìn)行分類器設(shè)計(jì)。這種方法繞過(guò)統(tǒng)計(jì)分布狀況的分析，繞過(guò)參數(shù)估計(jì)這一環(huán)，而企圖對(duì)特征空間實(shí)行劃分，稱為非參數(shù)判別分類法，即不依賴統(tǒng)計(jì)參數(shù)的分類法。例如：采用判別函數(shù)的方法。依據(jù)判別函數(shù)的形式不同，有不同的方法：如：線性判別函數(shù)；分段線性判別函數(shù)；2非參數(shù)判別分類方法兩個(gè)過(guò)程1）確定使用什么典型的分類決策方法即決定判別函數(shù)類型（如線性判別函數(shù)）及優(yōu)化準(zhǔn)則（用于確定判別函數(shù)的參數(shù)）。2）利用訓(xùn)練樣本集提供的信息及優(yōu)化準(zhǔn)則（Fisher準(zhǔn)則、感知函數(shù)準(zhǔn)則、最小錯(cuò)分樣本數(shù)準(zhǔn)則等）確定這些函數(shù)中的參數(shù)（具體實(shí)現(xiàn)的算法）。相對(duì)最小錯(cuò)誤率及最小風(fēng)險(xiǎn)決策（最優(yōu)分類器）而言，非參數(shù)判別分類方法是次優(yōu)方法，但在所提準(zhǔn)則下，是最好的。32.2.1線性分類器判別函數(shù)是線性判別函數(shù)的分類器稱為線性分類器主要工作：用訓(xùn)練樣本去估計(jì)線性判別函數(shù)的參數(shù)1線性判別函數(shù)線性判別函數(shù)的一般形式

g(X)=WTX+w0w0是一個(gè)常數(shù)，稱為閾值權(quán)4兩類別線性判別函數(shù)的決策規(guī)則若：g(X)>0，則決策：X∈

ω1g(X)<0，則決策：X

∈ω2g(X)=0，可將其任意類或拒絕g(X)＝0就是相應(yīng)的決策面方程，在線性判別函數(shù)條件下它對(duì)應(yīng)d維空間的一個(gè)超平面HWTX+w0

=05設(shè)在該決策平面H上有兩個(gè)特征向量X1與X2，則

WTX1+w0

=WTX2+w0

=0

所以：

WT(X1-X2)=0即：W與該平面上任兩點(diǎn)組成的向量(X1-X2)正交W是該超平面的法線向量

1）g(x)>0,決策：X∈ω1

決策面的法向量指向ω1的決策域R1，R1在H的正側(cè)

2）g(x)<0,決策：X∈ω2，

ω2的決策域R2在H的負(fù)側(cè)向量W的意義6g(X)是d維空間任一點(diǎn)X到?jīng)Q策面H的距離的代數(shù)度量w0體現(xiàn)該決策面在特征空間中的位置1)w0=0時(shí)，該決策面過(guò)特征空間坐標(biāo)系原點(diǎn)2)否則，r0=w0/||W||表示坐標(biāo)原點(diǎn)到?jīng)Q策面的距離g(X)/||W||R0=w0/||W||XXpR1:g>0R2:g<0正側(cè)負(fù)側(cè)H:g=0g(X)、w0的意義r7g(X)的意義設(shè)Xp是X在H上的投影向量，r是x到H的垂直距離W/||W||是W方向的單位向量，則g(X)=WTx+w0=WT(Xp+rW/||W||)+w0

=(WTXp+w0)+rWTW/||W||

=r||W||r=g(X)/||W||若X=0(原點(diǎn))，則g(X)=WTx+w0=w0否則：r0=g(0)/||W||=w0/||W||8利用線性判別函數(shù)決策，就是用一超平面將特征空間分為兩個(gè)決策域。超平面的方向由W確定，位置由W0決定。g(x)>0,X在H的正側(cè)；X∈

ω1g(x)<0,X在H的負(fù)側(cè)；X∈ω2線性判別函數(shù)：優(yōu)點(diǎn)：具有形式簡(jiǎn)單；計(jì)算方便的優(yōu)點(diǎn)；已被充分研究確定：但局限較大，不適合非凸決策域和多連通區(qū)域的劃分。910例如：欲設(shè)計(jì)這樣一個(gè)一維樣本的分類器，使其性能為：若X<b或X>a，則X∈ω1；若a<X<b，則X∈ω2（如下圖）1）此時(shí)，采用線性判別函數(shù)，則無(wú)法將兩類樣本無(wú)錯(cuò)誤的分開。2）若設(shè)計(jì)非線性判別函數(shù)

g(x)＝(x-a)(x-b)

采用決策規(guī)則：若：g(x)>0,決策：X∈w1

g(x)<0,決策：X∈w2則可將所有樣本正確分類。但是，非線性判別函數(shù)的計(jì)算復(fù)雜。解決辦法之一：廣義線性判別函數(shù)

2、廣義線性判別函數(shù)選擇一種映射X→Y，將原樣本特征向量X映射成另一向量Y，從而可以采用線性判別函數(shù)的方法。希望采用這種方式將線性判別函數(shù)的處理方法擴(kuò)展至原本適宜非線性判別函數(shù)的領(lǐng)域。例如，對(duì)于二次函數(shù)情況，其一般式可表示成：g(x)=c0+c1+x+c2x2采用映射x→Y:Y=[1y1y2]T=[1xx2]T則：判別函數(shù)g(x)又可表示成:

g(x)=ATY,A=[c0c1c2]Tg(x)被稱為廣義線性判別函數(shù)，a

稱為廣義權(quán)向量

11按照這種原理，任何形式的高次判別函數(shù)都可轉(zhuǎn)化成線性判別函數(shù)來(lái)處理。這種處理非線性分類器的方法，在支持向量機(jī)中得到充分的研究。產(chǎn)生問(wèn)題:維數(shù)會(huì)增加很多12線性判別函數(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)常用到。

133線性分類器設(shè)計(jì)步驟

線性分類器設(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)題:

1）確定所需的準(zhǔn)則函數(shù)J2）用最優(yōu)化技術(shù)確定準(zhǔn)則函數(shù)J達(dá)到極值的解w*及w0*，或增廣權(quán)向量a*144

Fisher線性判別是研究線性判別函數(shù)中最有影響的方法之一R.A.Fisher在1936年發(fā)表的論文Fisher線性判別函數(shù)基本原理設(shè)計(jì)線性分類器首先要確定準(zhǔn)則函數(shù)，然后再利用訓(xùn)練樣本集確定該分類器的參數(shù)，以求使所確定的準(zhǔn)則達(dá)到最佳。維數(shù)問(wèn)題:降低維數(shù)線性判別函數(shù)把d維空間映射到1維空間g(X)可看作各樣本向量X在向量W上的投影15（1）Fisher準(zhǔn)則函數(shù)

Fisher的基本問(wèn)題在1維直線上不一定能夠分開樣本希望在1維直線上不同類別的樣本分得越開越好如何找到這條最好的、最易于分類的投影線16如果在二維空間中一條直線能將兩類樣本分開，或者錯(cuò)分類很少，則同一類別樣本數(shù)據(jù)在該直線的單位法向量上的投影的絕大多數(shù)都應(yīng)該超過(guò)某一值。而另一類數(shù)據(jù)的投影都應(yīng)該小于(或絕大多數(shù)都小于)該值，則這條直線就有可能將兩類分開。Fisher準(zhǔn)則就是要找到一個(gè)最合適的投影軸，使兩類樣本在該軸上投影的交迭部分最少，從而使分類效果為最佳。分析w1方向之所以比w2方向優(yōu)越，可以歸納出這樣一個(gè)準(zhǔn)則向量W的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些而使類內(nèi)樣本的離散程度盡可能小17樣本在d維特征空間的一些描述量(1)各類樣本均值向量mi(2)樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw

(3)樣本類間離散度矩陣Sb若考慮先驗(yàn)概率，則：

18在一維Y空間的描述量(1)各類樣本均值

(2)樣本類內(nèi)離散度和總類內(nèi)離散度(3)樣本類間離散度

19Fisher準(zhǔn)則的函數(shù)形式Fisher選擇投影方向W的原則：y=WTX

類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求評(píng)價(jià)投影方向W的函數(shù)上式并不是W的顯函數(shù)，需化為W的顯函數(shù)20進(jìn)一步化為W的顯函數(shù)分子分母21因此最佳W的確定最佳W值的確定:求取使JF達(dá)極大值時(shí)的w*可以采用拉格朗日乘子算法解決設(shè)計(jì)一拉格朗日函數(shù)

或

22由于Sw非奇異，兩邊乘以Sw-1得

又：Fisher準(zhǔn)則及最小錯(cuò)誤率的貝葉斯決策使Fisher準(zhǔn)則函數(shù)JF達(dá)極大值的解，也就是按Fisher準(zhǔn)則將d維X空間投影到一維Y空間的最佳投影線。1）兩類是正態(tài)分布且具有相同的協(xié)方差矩陣Σ時(shí)，按最小錯(cuò)誤率的貝葉斯決策：2）按Fisher準(zhǔn)則，Sw=Σ1+Σ2=2Σ，Sb=(u1-u2)，結(jié)論：若兩類樣本的離散矩陣相近，也就是說(shuō)兩類分布的形式很相近，按Fisher準(zhǔn)則，錯(cuò)分率就應(yīng)比較小（接近最小錯(cuò)誤率），F(xiàn)isher準(zhǔn)則的合理性可以在這里體現(xiàn)。23最佳W0的確定若維數(shù)d足夠大，樣本數(shù)足夠多，可估計(jì)各類樣本在1維上的方差和均值、先驗(yàn)概率等，然后，按最小錯(cuò)誤率Bayes決策確定閾值W0。否則，按如下方法確定：1、2、

3、（P(W1)、P(W2)已知時(shí)）24分類規(guī)則255感知準(zhǔn)則函數(shù)感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，企圖將其用于腦模型感知器，因此被稱為感知準(zhǔn)則函數(shù)。特點(diǎn)：隨意確定判別函數(shù)的初始值，在對(duì)樣本分類訓(xùn)練過(guò)程中逐步修正直至最終確定。感知準(zhǔn)則函數(shù)：是設(shè)計(jì)線性分類器的重要方法感知準(zhǔn)則函數(shù)使用增廣樣本向量與增廣權(quán)向量2627在兩類別情況下，判別準(zhǔn)則是為簡(jiǎn)單起見，我們不考慮g(X)＝0的情況。為了討論原理方便，這一節(jié)在線性可分條件下討論問(wèn)題，并且只談兩類識(shí)別問(wèn)題。28線性可分性設(shè)已知樣本集{y1,y2,…,yN}，yn是d維增廣樣本向量,分屬于ω1和ω2類。若存在權(quán)向量a,使任何y∈ω1,都有：aTy>0y∈ω2,都有：aTy<0

則稱這組樣本集線性可分。或：若訓(xùn)練樣本集是線性可分的，則必存在一個(gè)權(quán)向量a，可使該訓(xùn)練樣本集中的每個(gè)樣本正確分類。a29樣本規(guī)范化在線性可分條件下，廣義權(quán)向量a應(yīng)有：

若Y∈ω1,則：aTY>0Y∈ω2,則：aTY<0為了方便起見，令：Y’稱為規(guī)范化的增廣樣本向量。則合適的a能使所有的Y'滿足aTY’>0.需要解決的問(wèn)題:找到滿足上式的a

30解區(qū)與解向量滿足aTY’>0的權(quán)向量a稱為解向量。解向量存在無(wú)窮多個(gè)，解向量組成的區(qū)域稱為解區(qū)31分析：怎樣確定準(zhǔn)則函數(shù)在給定一個(gè)規(guī)范化增廣樣本集Y1,…,YN的條件下，對(duì)于任何一個(gè)增廣權(quán)向量a

，可計(jì)算:aTyi顯然如果該向量是一個(gè)能將此樣本集正確分類的增廣權(quán)向量，則應(yīng)有:

aTyi>0,i=1,2,….,N而對(duì)可導(dǎo)致錯(cuò)分類的增廣權(quán)向量，則必有若干個(gè)yi,使aTyi<0。令被錯(cuò)分類的規(guī)范化增廣樣本組成的集用yk表示，并定義一準(zhǔn)則函數(shù)Jp(a)對(duì)線性可分情況，yk是空集。因此，確定向量a的問(wèn)題變?yōu)榍驤p(a)的極小值的問(wèn)題。準(zhǔn)則函數(shù)Jp(a)就是感知準(zhǔn)則函數(shù)32感知準(zhǔn)則函數(shù)方法的思路1）隨意找一個(gè)初始向量a(0)2）用訓(xùn)練樣本集中的每個(gè)樣本Y來(lái)計(jì)算aTY’若Y’使aTY’<0，則a不適合，需修正。若對(duì)當(dāng)前經(jīng)k次疊代修正的廣義權(quán)向量為a(k)修正并使其滿足：

則，aTY’增加，有可能大于0。即新的a(k+1)有可對(duì)Y’正確分類。如何求？33求感知準(zhǔn)則函數(shù)的極小值

--------梯度下降算法對(duì)第k次迭代值，求其梯度向量：可見：感知準(zhǔn)則函數(shù)的梯度向量是所有被錯(cuò)分類的規(guī)范化增廣樣本向量之和。令迭代向量a沿此負(fù)梯度向量方向修正（迭代公式）

（步長(zhǎng)系數(shù)）34算法1）給定初始權(quán)向量a(k)，k=0；

（

如a(0)=[1,1,….,1]T）2）利用a(k)對(duì)對(duì)樣本集分類，設(shè)錯(cuò)分類樣本集為yk3）若yk是空集，則a=a(k)，迭代結(jié)束；

否則，轉(zhuǎn)4）4）計(jì)算：ρk,

令k=k+15）轉(zhuǎn)2）35感知準(zhǔn)則函數(shù)利用梯度下降算法可簡(jiǎn)單敘述為：任意給定一向量初始值a(1)，第k+1次迭代時(shí)的權(quán)向量a(k+1)等于第k次的權(quán)向量a(k)加上被錯(cuò)分類的所有樣本之和與ρk

的乘積。

由于每次修正a時(shí)都要計(jì)算成批樣本，因此，該算法也稱為“批處理感知算法”可以證明，對(duì)于線性可分的樣本集，經(jīng)過(guò)有限次修正，一定可以找到一個(gè)解向量，即算法能在有限步內(nèi)收斂。收斂速度取決于初始權(quán)向量a(0)和系數(shù)ρk

。

36單個(gè)樣本修正的感知器算法對(duì)上述批處理做修正：順序輸入樣本，一旦發(fā)現(xiàn)分類錯(cuò)誤即對(duì)權(quán)向量修正算法其他部分和成批處理相同收斂性證明：即：新的權(quán)向量a(k+1)可能將yi正確分類37步長(zhǎng)ρk

的計(jì)算1、固定增量ρk

=1。稱為固定增量法。Rosenblatt提出2、可變?cè)隽?/p>

稱為絕對(duì)增量法此時(shí)：38感知準(zhǔn)則函數(shù)方法是一種利用錯(cuò)分類樣本對(duì)現(xiàn)決策權(quán)向量進(jìn)行修正直至收斂的方法。感知準(zhǔn)則函數(shù)方法只對(duì)線性可分樣本集有效對(duì)線性不可分的樣本集，該算法不能收斂。其它方法，如最小錯(cuò)分樣本數(shù)準(zhǔn)則等。這一節(jié)對(duì)感知準(zhǔn)則函數(shù)的討論，只是很初步的，并且只討論了線性可分的情況。但這種利用錯(cuò)誤提供的信息，進(jìn)行自修正的思想意義是十分深遠(yuǎn)的。這種只解決線性分類的感知器稱為單層感知器，由它基礎(chǔ)上發(fā)展起來(lái)的多層感知器在原理上能解決非線性分類、多類劃分，以及非線性擬和非線性映射等多種功能，是人工神經(jīng)元網(wǎng)絡(luò)的基礎(chǔ)。2.2.2非線性判別函數(shù)對(duì)實(shí)際的模式識(shí)別問(wèn)題來(lái)說(shuō)，各類在特征空間中的分布往往比較復(fù)雜，因此無(wú)法用線性分類函數(shù)得到好的效果。傳統(tǒng)的模式識(shí)別技術(shù)，則側(cè)重于使用分段線性判別函數(shù)，因此基本上是沿用了線性判別函數(shù)的方法。人工神經(jīng)元網(wǎng)絡(luò)（第3章）如多層感知器等網(wǎng)絡(luò)能夠?qū)嵱梅浅?fù)雜的非線性分類，以及非線性函數(shù)擬合，非線性映射等。支持向量機(jī)(SupportVectorMachine----SVM)提出了一種基于特征映射的方法（第5章），也就是使用某種映射，使本來(lái)在原特征空間必須使用非線性分類技術(shù)才能解決的問(wèn)題,映射到一個(gè)新的空間以后,使線性分類技術(shù)能繼續(xù)使用。

391非線性判別函數(shù)

與分段線性判別函數(shù)

非線性判別函數(shù)可用分段線性判別函數(shù)近似分段段數(shù)問(wèn)題過(guò)少：效果差過(guò)多：計(jì)算量大40分段線性判別函數(shù)每一類的樣本數(shù)據(jù)在特征空間中的分布呈復(fù)雜分布時(shí)，使用線性判別函數(shù)就會(huì)產(chǎn)生很差的效果如果能將它們分割成子集，而每個(gè)子集在空間聚集成團(tuán)，那么子集與子集的線性劃分就可以取得比較好的效果。同一類樣本可以用若干個(gè)子類來(lái)描述，子類的數(shù)目就可作為確定分段段數(shù)的依據(jù)。因此分段線性判別的主要問(wèn)題是如何對(duì)數(shù)據(jù)劃分成子集的問(wèn)題（聚類方法）。41分段線性判別函數(shù)的一般形式同一類樣本可以用若干個(gè)子類來(lái)描述，子類的數(shù)目就可作為確定分段段數(shù)的依據(jù)。分段線性判別函數(shù)的一般形式可定義為

表示第i類第l段線性判別函數(shù)，li為i類所具有的判別函數(shù)個(gè)數(shù)。分別是第l段的權(quán)向量與閾值權(quán)42判別規(guī)則若：則：其中：

稱為第i類的判別函數(shù)決策面方程：

如第i類的第n個(gè)子類與第j類的第m個(gè)子類相鄰，則判別規(guī)則及決策面方程432基于距離的分段線性判別函數(shù)正態(tài)分布條件下，兩類別問(wèn)題在各特征統(tǒng)計(jì)獨(dú)立、同方差、且先驗(yàn)概率相等時(shí)，最小錯(cuò)誤率bayes決策可按最小距離決策。最近距離分類器：把各類別樣本特征向量的均值作為各類的代表點(diǎn)

（每類只有1個(gè)代表點(diǎn)）樣本的類別按它到各類別代表點(diǎn)的最小距離劃分決策面是兩類別均值連線的垂直平分面只有在各類別密集地分布在其均值附近時(shí)才有效，否則，會(huì)產(chǎn)生很大的錯(cuò)誤率44最近距離分類器分段線性距離分類器最近距離分類器：只有在各類別密集地分布在其均值附近時(shí)才有效。對(duì)于右圖所示情況，若企圖用每類一個(gè)均值代表點(diǎn)產(chǎn)生最小距離分類器，就會(huì)產(chǎn)生很明顯的錯(cuò)誤率。45分段線性距離分類器原理是最小按距離分類器的原理推廣將各類別劃分成相對(duì)密集的子類，每個(gè)子類以它們的均值作為代表點(diǎn)，然后按最小距離分類對(duì)樣本進(jìn)行子類的合適劃分是分段線性距離分類器性能好壞的一個(gè)關(guān)鍵問(wèn)題46決策規(guī)則如果對(duì)于ωi有l(wèi)i個(gè)子類，則有l(wèi)i個(gè)代表點(diǎn)，或者說(shuō)把屬于ωi的決策域Ri分成li個(gè)子域，即

每個(gè)子區(qū)域Ril均值用mil表示，作為該子區(qū)域的代表點(diǎn)判別函數(shù)定義為：

判別規(guī)則是：

如果

473分段線性分類器設(shè)計(jì)的一般考慮1）已知樣本的子類數(shù)目及子類劃分

把每個(gè)子類看成一個(gè)類，然后按多類線性判別函數(shù)算法將各子類分開。2）子類數(shù)目已知，但子類劃分未知

采用錯(cuò)誤修正算法3）子類數(shù)目、子類劃分均未知

方法很多，典型方法是樹狀分段線性分類器484錯(cuò)誤修正算法感知準(zhǔn)則函數(shù)的擴(kuò)展1）aiTy，ajTy相比較的含義

aiTy是ai向量與y向量的點(diǎn)積，點(diǎn)積值比較大則表示這兩個(gè)向量在方向上比較一致，即：向量間的夾角較小。即：同一類規(guī)范化增廣樣本向量與代表自己一類的增廣權(quán)向量的點(diǎn)積的最大值比與其它類增廣權(quán)向量的點(diǎn)積值要大。

如果某一類樣本比較分散，但是能用多個(gè)增廣權(quán)向量表示。若同一類規(guī)范化增廣樣本向量與代表自己一類的某一增廣權(quán)向量的點(diǎn)積的最大值比與其它類所有增廣權(quán)向量的點(diǎn)積值都要大，可以做到正確分類。492）思路這種算法就是要用錯(cuò)誤提供的信息進(jìn)行疊代修正。它對(duì)每類樣本集進(jìn)行具體劃分可以采用假設(shè)初始權(quán)向量，然后由樣本提供的錯(cuò)誤率信息進(jìn)行迭代修正，直至收斂。該算法希望能知道每類所需的增廣權(quán)向量數(shù)目。該數(shù)目可以在計(jì)算過(guò)程中按分類效果調(diào)整。

503）算法的基本要點(diǎn)：1、對(duì)每個(gè)類別的子類賦予一初始增廣權(quán)向量aj1(1)，aj2(1),…,ajl(1);j=1,2,…,c2、對(duì)每次迭代所得增廣權(quán)向量用樣本去檢測(cè)，如發(fā)生錯(cuò)誤分類，則利用錯(cuò)誤分類的信息進(jìn)行修正。其做法是：1）先將某一j類的增廣樣本向量yj，與該類所有增廣權(quán)向量ajl(k)求內(nèi)積ajl(k)Tyj

，找到其中的最大值ajm(k)Tyj：

ajm(k)Tyj=max{ajl(k)Tyj，l=1,2，….，lj}

512)將該yj與其它類(如i類)的權(quán)向量求內(nèi)積，若：

ajm(k)Tyj≥ail(k)Tyji=1,…,c,i≠j,;l=1,…,li表明這些權(quán)向量不影響yj的正確分類，不需要修改。轉(zhuǎn)入4）若：存在某個(gè)或幾個(gè)子類不滿足上述條件，例如某個(gè)子類ωin的現(xiàn)有權(quán)向量ain(k)使得

ajm(k)Tyj≤ain(k)Tyji≠j這表明yj將被錯(cuò)分類，有關(guān)權(quán)向量需要轉(zhuǎn)入（3）修正523）首先找到導(dǎo)致yj錯(cuò)分類的所有權(quán)向量中具有與yj內(nèi)積最大值的權(quán)向量ain’(k)T=max(ain(k)Tyj)

接著對(duì)ajm(k)Tyj

與ain’(k)T作相應(yīng)修正:ajm(k+1)=ajm(k)+ρkyjain’(k+1)=ain’(k)-ρkyj4）然后利用權(quán)向量的新值重復(fù)以上過(guò)程，直到收斂或迫使其收斂。這種算法在樣本確實(shí)能被分段線性判別函數(shù)正確劃分的條件下是收斂的；但當(dāng)該條件不滿足時(shí)，則需逐步減小ρk的數(shù)值，迫使其“收斂”,但會(huì)有相應(yīng)的錯(cuò)誤率存在。535、用交遇區(qū)樣本設(shè)計(jì)分段線性判別函數(shù)

----局部訓(xùn)練法分段數(shù)最少的分段線性判別函數(shù)設(shè)計(jì)方法。出發(fā)點(diǎn)：類間的分界面必然處在兩類樣本的交界處，只需找出這些交界處的樣本，對(duì)這些鄰近的不同類樣本要確定分界面即可。交遇區(qū)：兩類樣本十分靠近或相互交疊的區(qū)域稱之為“交遇區(qū)”局部訓(xùn)練法就是基于交遇區(qū)內(nèi)的樣本進(jìn)行設(shè)計(jì)的。54問(wèn)題：(1)如何從樣本集中找到“交遇區(qū)”？(2)如何利用“交遇區(qū)”中樣本設(shè)計(jì)線性分類器？(3)如何進(jìn)行分類決策？一、交遇區(qū)的確定1）首先對(duì)兩類樣本進(jìn)行聚類分析，找出它們各自的一些相對(duì)密集的子區(qū)域（稱為“原型區(qū)”）

2）在每個(gè)原型區(qū)中找到一個(gè)質(zhì)心或距質(zhì)心很近的樣本作為各原型區(qū)的代表點(diǎn)（稱為“原型”）。如：V11,V12,V13，….V21,V22,V23,….第i類的原型集合：Vi={V11,V12,V13,….},i=1,2原型對(duì)：

(V1m,V2n)注：下標(biāo)i表示“類”，

上標(biāo)m,n表示“某類的第幾個(gè)原型”5556I）找出各原型在對(duì)方類型中相距最近的原型對(duì)，集合記為：

L12={[V1m,V2n(V1m)]}L21={[V2n,V1m(V2n)]}其中：V2n(V1m)=min{d(V1m,V2ln),ln=1,..}V1m(V2n)=min{d(V2n,V1lm),lm=1,..}

這里，V2n(V1m)表示V1m在ω2中的最近距離的原型是V2n。d表示距離。3）若分屬兩類的兩個(gè)原型互為最近鄰，那么這兩個(gè)原型就被認(rèn)定為處在兩類樣本決策域的交界處，它們所在區(qū)域就成為交遇區(qū)。具體做法如下：II)找到互為最小距離的原型對(duì)組成“緊互對(duì)原型對(duì)”:L=L12∩L21III）緊互對(duì)原型對(duì)的集合L所代表的原型區(qū)組成“交遇區(qū)”。二、分界面的設(shè)計(jì)：局部訓(xùn)練法基本思想：邊界由若干個(gè)交遇區(qū)確定，在每個(gè)交遇區(qū)中只有兩種不同類型的樣本。由這些樣本產(chǎn)生一個(gè)合適的分界面，一般使用分段線性分界面。具體做法：利用處于最緊貼邊界的緊互對(duì)原型對(duì)產(chǎn)生一初始分界面，然后利用交遇區(qū)進(jìn)行調(diào)整，這種調(diào)整屬于局部性的調(diào)整。步驟一：產(chǎn)生初始超平面

由緊互對(duì)原型對(duì)集合L中最近的一對(duì)(v1m,v2n

)產(chǎn)生一個(gè)初始決策面的方程H1（方法不限，例如可由這兩個(gè)原型的垂直平分平面作為初始界面）。

57步驟二：初始決策面最佳化1）確定H1能正確分類的所有緊互對(duì)原型對(duì)。2）由這些原型對(duì)中的樣本組成局部訓(xùn)練的樣本集，按所使用的準(zhǔn)則設(shè)計(jì)出線性決策面H1*。

3）對(duì)該H1*決策面又可找出它能正確分類的所有緊互對(duì)原型對(duì)。4）如果H1*與H1的分類效果相同，則H1不需再調(diào)整，轉(zhuǎn)步驟3。否則由H1*作為初始決策面，重復(fù)1）~3），直到局部訓(xùn)練樣本集不再發(fā)生變化為止，并記最后的超平面為H1。58H1H1*’步驟三：新決策面的產(chǎn)生與最佳化1）找到一個(gè)最佳的決策面段后，將相應(yīng)的局部訓(xùn)練樣本從原緊互對(duì)原型對(duì)集合中撤走。2）在剩下的緊互對(duì)原型對(duì)集合按步驟1~2，產(chǎn)生另一個(gè)超平面分界面H2。3）重復(fù)1）~2），直到所有緊互對(duì)原型對(duì)都被處理完畢，得到一系列超平面，組成分段線性分類器：

Hj

：aj,j=1,2,….,m

59H1H1*’三、決策域的確定及決策規(guī)則子決策域的劃分與表示

設(shè)得到的m段決策面為：Hi：aiTy=0,i=1,2,….,m；

I)對(duì)每一個(gè)樣本yj，對(duì)每一個(gè)決策面，定義

II)對(duì)m個(gè)決策面，可得m維向量：Z(Xj)={Z1(Xj),Z2(Xj),……,Zm(Xj)}

j=1,2，……，N全體訓(xùn)練樣本被劃分成若干子集（域），最大可能的子集數(shù)為2m個(gè)處在同一子域的樣本都有同樣的Z向量602）子域所屬類別的確定（決策域的確定）每個(gè)子集都可能包含兩個(gè)類別的訓(xùn)練樣本，但在每個(gè)子集中兩類樣本分布的不同，將作為劃分與改進(jìn)決策域的依據(jù)。I）計(jì)算第k個(gè)子集中屬于ωi的樣本的數(shù)：Ni(Zk)

{k＝1，…，2m;i＝1，2}II）計(jì)算每個(gè)子集中ω1類樣本所占比例：

III）子域所屬類別的確定

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)一步劃分。IV）重復(fù)上述過(guò)程，直至對(duì)所有區(qū)域都能合理地確定為哪一類的決策域，或拒識(shí)區(qū)域?yàn)橹埂?162例：圖中的樣本采用上述方法后，決策平面由兩個(gè)(H1、H2)增至三個(gè)，即H1、H2與H3組成。至于對(duì)每類樣本的決策域劃分，可用上面提到的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）決策方法對(duì)待識(shí)別樣本X，利用得到的aj計(jì)算Z(X)={Z1(X),Z2(X),……,Zm(X)}若Z(X)=ZK，則X屬于ZK表示的類別63§2.3近鄰法

自動(dòng)分類的基本方法：1）將特征空間劃分成決策域，這就要確定判別函數(shù)或確定分界面方程。2）模板匹配：即將待分類樣本與標(biāo)準(zhǔn)模板進(jìn)行比較，看跟哪個(gè)模板匹配度更好些，從而確定待測(cè)試樣本的分類。近鄰法：Cover和Hart于1968年提出，理論上分析與研究深入，是非參數(shù)法中最重要的方法之一；原理上屬于模板匹配近鄰法的優(yōu)點(diǎn)：在模板數(shù)量很大時(shí)其錯(cuò)誤率小近鄰法的缺點(diǎn)：計(jì)算量大，存儲(chǔ)量大改進(jìn)的辦法：剪輯近鄰法與壓縮近鄰法

642.3.1近鄰法原理及其決策規(guī)則最小距離分類器：

在每個(gè)類別中確定一個(gè)代表點(diǎn)。測(cè)試樣本的類別以其與代表點(diǎn)距離最近作決策。基于距離的分段線性函數(shù)

每個(gè)類別用多個(gè)“代表點(diǎn)”表示

將各類訓(xùn)練樣本劃分成若干子類，并在每個(gè)子類中確定代表點(diǎn)。測(cè)試樣本的類別則以其與這些代表點(diǎn)距離最近作決策。該法的缺點(diǎn)：所選擇的代表點(diǎn)并不一定能很好地代表各類，其后果將使錯(cuò)誤率增加。65基于距離的分段線性函數(shù)的

極端情況----近鄰法每個(gè)樣本是一個(gè)子類分類方法:以全部訓(xùn)練樣本作為“代表點(diǎn)”，計(jì)算測(cè)試樣本與這些“代表點(diǎn)”（即所有樣本）的距離，并以最近鄰者（最近似的”代表點(diǎn)”）的類別作為分類的類別。------這種決策方法就是近鄰法近鄰法是分段線性判別函數(shù)的特例662.3.1.1最近鄰法決策規(guī)則

1）判別函數(shù)：對(duì)一個(gè)C類別問(wèn)題，每類有Ni個(gè)樣本，i＝1，…，C，則第i類ωi的判別函數(shù)

gi(X)=min||X-Xik

||,k=1,2,…,NiXik表示是ωi類的第k個(gè)樣本2）決策規(guī)則：若：gj(X)=min{gi(X),i=1,2,…,C}；則：X∈ωj

即：樣本X的類別與離該樣本距離最近的樣本（近鄰）同類

672.3.1.2k-近鄰法決策規(guī)則最近鄰法可以擴(kuò)展成找測(cè)試樣本的k個(gè)最近樣本作決策依據(jù)的方法基本規(guī)則

1）在所有N個(gè)樣本中找到與測(cè)試樣本的k個(gè)最近鄰者，其中各類別所占個(gè)數(shù)表示成：Ki,i＝1，…，C2）

決策規(guī)則：

如果：Kj(X)=max{Ki(X)，i=1,2,…,C}則：X∈ωj

682.3.2近鄰法錯(cuò)誤率近鄰法的錯(cuò)誤率是比較難算的：

因?yàn)橛?xùn)練樣本集的數(shù)量總是有限的，有時(shí)多一個(gè)少一個(gè)訓(xùn)練樣本對(duì)測(cè)試樣本分類的結(jié)果影響很大在漸近概念下來(lái)分析錯(cuò)誤率：

利用訓(xùn)練樣本數(shù)量增至極大，來(lái)對(duì)其性能進(jìn)行評(píng)價(jià)。具體分析這里不做討論，我們直接給出結(jié)論69最近鄰法的錯(cuò)誤率的上下界

與貝葉斯錯(cuò)誤率的關(guān)系當(dāng)N→∞時(shí)，最近鄰法的漸近平均錯(cuò)誤率的下界是貝葉斯錯(cuò)誤率，這發(fā)生在樣本對(duì)某類別后驗(yàn)概率處處為1的情況或各類后驗(yàn)概率相等的情況。

在其它條件下，最近鄰法的錯(cuò)誤率要高于貝葉斯錯(cuò)誤率（P*），可以證明以下關(guān)系式成立：P*≤P≤P*[2-C/(C-1)P*]一般情況下P*很小則：P*≤P≤2P*

70最近鄰法錯(cuò)誤率上下界與貝葉斯錯(cuò)誤率關(guān)系（紅線：下界；藍(lán)線：上界）k-近鄰法錯(cuò)誤率

1）當(dāng)k增大時(shí)錯(cuò)誤率是單調(diào)遞減的。2）因此,在N→∞的條件下，k-近鄰法的錯(cuò)誤率要低于最近鄰法的錯(cuò)誤率。3）一般P*≤P≤2P*(1-P*)所以：P*≤P≤P*(2-2P*)≤P*(2-c/(c-1)P*)（最近鄰法）

≤2P*即：P*≤P≤2P*不同k值時(shí)，k近鄰法錯(cuò)誤率上下界與貝葉斯錯(cuò)誤率關(guān)系(C=2)00.250.50.50.250712.3.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)。以簡(jiǎn)單的方式降低樣本數(shù)量，只能使其性能降低，這也是不希望的。

72改進(jìn)的思路要研究既能減少近鄰法計(jì)算量與存儲(chǔ)量，同時(shí)又不明顯降低其性能的一些改進(jìn)算法。改進(jìn)的方法大致分為兩種原理。一種是對(duì)樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測(cè)試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算?？蓽p少計(jì)算量另一種原理則是在原有樣本集中挑選出對(duì)分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。732.3.3.1近鄰法的快速算法（略）這種方法著眼于只解決減少計(jì)算量，但沒(méi)有達(dá)到減少存儲(chǔ)量的要求。其基本思想是將樣本集按鄰近關(guān)系分解成組，給出每組的質(zhì)心所在，以及組內(nèi)樣本至該質(zhì)心的最大距離。這些組又可形成層次結(jié)構(gòu)，即組又分子組，因而待識(shí)別樣本可將搜索近鄰的范圍從某一大組，逐漸深入到其中的子組，直至樹的葉結(jié)點(diǎn)所代表的組，確定其相鄰關(guān)系。742.3.3.2剪輯近鄰法快速算法只是研究如何減少計(jì)算量的問(wèn)題，而不考慮存儲(chǔ)量的壓縮。實(shí)際上由于對(duì)樣本進(jìn)行分層次分組，并附有一些參數(shù)，實(shí)際的存儲(chǔ)量還有可能增加。本節(jié)討論的算法著眼于如何減少模板樣本數(shù)目，從而可同時(shí)減少分類時(shí)的計(jì)算量及模板樣本的存儲(chǔ)量，同時(shí)還能進(jìn)一步改進(jìn)分類器的性能，如降低錯(cuò)誤率等要求。75剪輯近鄰法的基本思想當(dāng)不同類別的樣本在分布上有交迭部分的，分類的錯(cuò)誤率主要來(lái)自處于交迭區(qū)中的樣本。當(dāng)我們得到一個(gè)作為識(shí)別用的參考樣本集時(shí)，由于不同類別交迭區(qū)域中不同類別的樣本彼此穿插，導(dǎo)致用近鄰法分類出錯(cuò)。如果能將不同類別交界處的樣本以適當(dāng)方式篩選，可以實(shí)現(xiàn)既減少樣本數(shù)又提高正確識(shí)別率的雙重目的。為此可以利用現(xiàn)有樣本集對(duì)其自身進(jìn)行剪輯。761、兩分剪輯近鄰法假設(shè)現(xiàn)有一個(gè)樣本集N，樣本數(shù)量為N。將樣本集分成兩個(gè)互相獨(dú)立的樣本子集。一個(gè)被當(dāng)作考試集?NT，另一個(gè)作為參考集?NR，數(shù)量分別為NT與NR，NT+NR＝N。將?NT中的樣本表示成Xi(i=1,2,…,NT)

在?NR中的樣本表示為Yj(j=1,2,…,NR)

將樣本集分成兩個(gè)相互獨(dú)立的樣本子集是指：分完以后的兩個(gè)子集具有相同的分布且相互獨(dú)立。實(shí)際做時(shí)要用從總的集合中隨機(jī)抽取的方式進(jìn)行。77（兩類樣本的）剪輯過(guò)程首先對(duì)?NT

中每一個(gè)Xi在?NR中找到其最近鄰的樣本。如果Yi與Xi不屬于同一類別，則將Xi從?NT

中刪除。對(duì)?NT中的所有樣本重復(fù)1~2，結(jié)束時(shí)，?NT中將是一個(gè)經(jīng)過(guò)剪輯的剪輯樣本集：?NTE

。

將?NTE作為新的訓(xùn)練樣本集,對(duì)待識(shí)別樣本分類。剪輯的過(guò)程也可用k-近鄰法進(jìn)行，即