模式識(shí)別第二章(線性判別函數(shù)法)

第二章線性判別函數(shù)2023/2/1模式識(shí)別導(dǎo)論2實(shí)例：統(tǒng)計(jì)模式識(shí)別19名男女同學(xué)進(jìn)行體檢，測(cè)量了身高和體重，但事后發(fā)現(xiàn)其中有4人忘記填寫性別，試問（在最小錯(cuò)誤的條件下）這4人是男是女？體檢數(shù)值如下：2023/2/1模式識(shí)別導(dǎo)論3實(shí)例：統(tǒng)計(jì)模式識(shí)別（續(xù)）待識(shí)別的模式：性別（男或女）測(cè)量的特征：身高和體重訓(xùn)練樣本：15名已知性別的樣本特征目標(biāo)：希望借助于訓(xùn)練樣本的特征建立判別函數(shù)（即數(shù)學(xué)模型）2023/2/1模式識(shí)別導(dǎo)論4實(shí)例：統(tǒng)計(jì)模式識(shí)別（續(xù)）從圖中訓(xùn)練樣本的分布情況，找出男、女兩類特征各自的聚類特點(diǎn)，從而求取一個(gè)判別函數(shù)（直線或曲線）。只要給出待分類的模式特征的數(shù)值，看它在特征平面上落在判別函數(shù)的哪一側(cè)，就可以判別是男還是女了。2023/2/1模式識(shí)別導(dǎo)論5有關(guān)模式識(shí)別的3個(gè)問題學(xué)習(xí)人們?cè)谌粘Ｉ钪袔缀鯐r(shí)時(shí)刻刻在進(jìn)行模式識(shí)別的活動(dòng)，從小時(shí)候起就開始學(xué)習(xí)與增強(qiáng)這種能力。如小孩學(xué)習(xí)認(rèn)字、認(rèn)識(shí)事物都有一個(gè)從不會(huì)到會(huì)的過程。確定分類決策的具體數(shù)學(xué)公式是通過分類器設(shè)計(jì)這個(gè)過程確定的。在模式識(shí)別學(xué)科中一般把這個(gè)過程稱為訓(xùn)練與學(xué)習(xí)的過程。一般來(lái)說(shuō)，決定使用什么類型的分類函數(shù)往往是人為決定的。但數(shù)學(xué)式子中的參數(shù)則往往通過學(xué)習(xí)來(lái)確定2023/2/1模式識(shí)別導(dǎo)論6有關(guān)模式識(shí)別的3個(gè)問題模式的緊致性分類器設(shè)計(jì)難易程度與模式在特征空間的分布方式有密切關(guān)系，例如圖(a)、(b)與(c)分別表示了兩類在空間分布的三種狀況。兩類事物分布的區(qū)域不要有相互混迭的情況，事物盡管沒有混迭，但交界線很復(fù)雜。2023/2/1模式識(shí)別導(dǎo)論71有關(guān)模式識(shí)別的3個(gè)問題相似性度量同類物體之所以屬于同一類，在于它們的某些屬性相似，因此可選擇適當(dāng)?shù)亩攘糠椒z測(cè)出它們之間的相似性。在特征空間中用特征向量描述樣本的屬性，用距離來(lái)表示相似性度量。合適的特征空間情況下，同類樣本應(yīng)具有聚類性，或緊致性好，而不同類別樣本應(yīng)在特征空間中顯示出具有較大的距離。2023/2/1模式識(shí)別導(dǎo)論84.1引言分類器設(shè)計(jì)方法，是根據(jù)訓(xùn)練樣本集提供的信息，直接進(jìn)行分類器設(shè)計(jì)。這種方法省去了統(tǒng)計(jì)分布狀況分析，直接對(duì)特征空間進(jìn)行劃分，也是當(dāng)前的主要方法之一。2023/2/1模式識(shí)別導(dǎo)論92.1引言決策域的分界面是用數(shù)學(xué)表達(dá)式來(lái)描述的，如線性函數(shù)和各種非線性函數(shù)等，所以分界面的方程主要包括函數(shù)類型選擇與最佳參數(shù)確定。一般來(lái)說(shuō)，函數(shù)類型由設(shè)計(jì)者選擇，其參數(shù)的確定則是依據(jù)一定的準(zhǔn)則函數(shù)，通過一個(gè)學(xué)習(xí)過程來(lái)實(shí)現(xiàn)優(yōu)化。2023/2/1模式識(shí)別導(dǎo)論102.1引言將模式識(shí)別的設(shè)計(jì)過程，主要是判別函數(shù)、決策面方程的確定過程改成2023/2/1模式識(shí)別導(dǎo)論112.1引言線性分類器以及作為設(shè)計(jì)依據(jù)的一些準(zhǔn)則函數(shù)，準(zhǔn)則函數(shù)包括：感知準(zhǔn)則，最小平方誤差準(zhǔn)則，最小錯(cuò)分樣本數(shù)準(zhǔn)則，F(xiàn)isher準(zhǔn)則。2023/2/1模式識(shí)別導(dǎo)論122.2.1線性判別函數(shù)的基本概念在一個(gè)d維的特征空間中，線性判別函數(shù)的一般表達(dá)式如下2023/2/1模式識(shí)別導(dǎo)論132.2.1線性判別函數(shù)的基本概念如果采用增廣模式，可以表達(dá)如下若分屬于ω1，ω2的兩類模式可用一方程d(X)=0來(lái)劃分，那么稱d(X)為判別函數(shù)，或稱判決函數(shù)、決策函數(shù)。2.1判別函數(shù)(discriminantfunction)

直接用來(lái)對(duì)模式進(jìn)行分類的準(zhǔn)則函數(shù)。例：一個(gè)二維的兩類判別問題，模式分布如圖示，這些分屬于ω1，ω2兩類的模式可用一直線方程d(X)=0來(lái)劃分。為坐標(biāo)變量，為方程參數(shù)。式中：圖3.2兩類二維模式的分布1．判別函數(shù)的定義若，則若，則類；若，則類；

或拒絕將某一未知模式

X

代入：維數(shù)=3時(shí)：判別邊界為一平面。維數(shù)>3時(shí)：判別邊界為一超平面。d(X)表示的是一種分類的標(biāo)準(zhǔn)，它可以是1、2、3維的，也可以是更高維的。

判別界面的正負(fù)側(cè)，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的。2．判別函數(shù)正負(fù)值的確定圖3.3判別函數(shù)正負(fù)的確定1）判決函數(shù)d(X)的幾何性質(zhì)。它可以是線性的或非線性的函數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。如：已知三維線性分類——判決函數(shù)的性質(zhì)就確定了判決函數(shù)的形式：3.確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2）判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。181920多類問題圖例（第一種情況）?不確定區(qū)域211、第一種情況（續(xù)）判別規(guī)則為：如果則判比如對(duì)圖的三類問題,如果對(duì)于任一模式如果它的則該模式屬于ω1類。221、第一種情況（續(xù)）如果某個(gè)X使二個(gè)以上的判別函數(shù)di>0

。則此模式X就無(wú)法作出確切的判決。如圖另一種情況是IR2區(qū)域，判別函數(shù)都為負(fù)值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。231、第一種情況（續(xù)）解：三個(gè)判別邊界分別為：241、第一種情況（續(xù)）結(jié)論：因?yàn)樗运鼘儆讦?類。251、第一種情況（續(xù)）26272、第二種情況（續(xù)）多類問題圖例（第二種情況）2829d12(x)=-d21(x)=–x1–x2+5=0d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正30d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正d23(x)=-d32(x)=–x1+x2=0d32(x)為正d23(x)為正31d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正d32(x)為正d23(x)為正d13(x)=-d31(x)=–x1+3=0d31(x)為正d13(x)為正321類判別區(qū)域

d12(x)>0d13(x)>02類判別區(qū)域

d21(x)>0d23(x)>0d12(x)為正兩分法例題圖示0123456789987654321d21(x)為正d32(x)為正d23(x)為正d31(x)為正d13(x)為正3類判別區(qū)域

d31(x)>0d32(x)>0IR33343、第三種情況（續(xù)）多類問題圖例（第三種情況）35。36上述三種方法小結(jié):方法⑶判別函數(shù)的數(shù)目和方法⑴相同，但沒有不確定區(qū)，分析簡(jiǎn)單，是最常用的一種方法。時(shí)，法比法需要更多當(dāng)?shù)呐袆e函數(shù)式，這是一個(gè)缺點(diǎn)。類與其余的開，而法是將類和類分開，顯然法是將但是類區(qū)分法使模式更容易線性可分，這是它的優(yōu)點(diǎn)。(1)明確概念：線性可分。

一旦線性判別函數(shù)的系數(shù)Wk被確定以后，這些函數(shù)就可以作為模式分類的基礎(chǔ)。3.小結(jié)(2)分法的比較：

對(duì)于M類模式的分類，兩分法共需要M個(gè)判別函數(shù)，但兩分法需要M(M-1)/2個(gè)。當(dāng)時(shí)M>3時(shí)，后者需要更多個(gè)判別式（缺點(diǎn)），但對(duì)模式的線性可分的可能性要更大一些（優(yōu)點(diǎn)）。原因：

一種類別模式的分布要比M-1類模式的分布更為聚集，分法受到的限制條件少，故線性可分的可能性大。2023/2/1模式識(shí)別導(dǎo)論38.2.1線性判別函數(shù)的基本概念線性分類器的設(shè)計(jì)就是利用訓(xùn)練樣本集建立線性判別函數(shù)式，也就是尋找最優(yōu)的權(quán)向量w的過程。其主要步驟如下采集訓(xùn)練樣本，構(gòu)成訓(xùn)練樣本集。樣本應(yīng)該具有典型性確定一個(gè)準(zhǔn)則J=J(w,x)，能反映分類器性能，且存在權(quán)值w*使得分類器性能最優(yōu)設(shè)計(jì)求解w的最優(yōu)算法，得到解向量w*2023/2/1模式識(shí)別導(dǎo)論392.2.2感知器概念及其訓(xùn)練方法感知準(zhǔn)則函數(shù)是五十年代由Rosenblatt提出的一種自學(xué)習(xí)判別函數(shù)生成方法，由于Rosenblatt企圖將其用于腦模型感知器，因此被稱為感知準(zhǔn)則函數(shù)。其特點(diǎn)是隨意確定的判別函數(shù)初始值，在對(duì)樣本分類訓(xùn)練過程中逐步修正直至最終確定。402.3感知器算法(PerceptronApproach)任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗(yàn)分類是否正確對(duì)所有訓(xùn)練樣本都正確分類？YesENDYesNo對(duì)權(quán)值進(jìn)行校正No感知器算法流程圖流程:2023/2/1模式識(shí)別導(dǎo)論412.2感知器概念及其訓(xùn)練方法設(shè)訓(xùn)練樣本集X={x1,x2,…,xn}，其中xk屬于wi或者wj，且xk的類別是已知的。為了確定加權(quán)向量w*，執(zhí)行下面的訓(xùn)練算法給定初始值：置k=0，權(quán)向量w(k)為任意值，可選常數(shù)0＜c≤1輸入樣本xm∈{x1,x2,…,xn}，計(jì)算判決函數(shù)值g(xm)=wT(k)xm按如下規(guī)則修改權(quán)向量若xm∈wi，且g(xm)≤0，則w(k+1)=w(k)+cxm若xm∈wj，且g(xm)＞0，則w(k+1)=w(k)-cxm令k=k+1，返回第二步，直到w對(duì)所有樣本穩(wěn)定不變，結(jié)束42二、收斂定理：

如果訓(xùn)練模式是線性可分的，感知器訓(xùn)練算法在有限次迭代后便可以收斂到正確的解矢量。。證明思路：

如果第k+1次迭代生成的權(quán)矢量比第k次迭代生成的權(quán)矢量更接近解矢量，則收斂，即：2023/2/1模式識(shí)別導(dǎo)論43例子1已知兩類訓(xùn)練樣本，(0,0),(0,1)屬于w1，(1,0),(1,1)屬于w2，試用感知器算法求解w*訓(xùn)練樣本分量增廣化以及符號(hào)規(guī)范化。將訓(xùn)練樣本增加一個(gè)分量1，且把來(lái)自w2的樣本各分量乘以-1，得到訓(xùn)練模式集x1=(0,0,1),x2=(0,1,1),x3=(-1,0,-1),x4=(-1,-1,-1)運(yùn)用訓(xùn)練算法，給權(quán)向量賦初值w(1)=(1,1,1)T，取增量c=1，置迭代步數(shù)k=1，下面是迭代過程2023/2/1模式識(shí)別導(dǎo)論44例子1K=1,xm=x1,w(k)Txm=1>0,w(2)=w(1)K=2,xm=x2,w(k)Txm=2>0,w(3)=w(2)K=3,xm=x3,w(k)Txm=-2<0,w(4)=w(3)+x3=(0,1,0)TK=4,xm=x4,w(k)Txm=-1<0,w(5)=w(4)+x4=(-1,0,-1)TK=5,xm=x1,w(k)Txm=-1<0,w(6)=w(5)+x1=(-1,0,0)TK=6,xm=x2,w(k)Txm=0,w(7)=w(6)+x2=(-1,1,1)TK=7,xm=x3,w(k)Txm=0,w(8)=w(7)+x3=(-2,1,0)TK=8,xm=x4,w(k)Txm=1>0,w(9)=w(8)2023/2/1模式識(shí)別導(dǎo)論45例子1K=9,xm=x1,w(k)Txm=0,w(10)=w(9)+x1=(-2,1,1)TK=10,xm=x2,w(k)Txm=2>0,w(11)=w(10)K=11,xm=x3,w(k)Txm=1>0,w(12)=w(11)K=12,xm=x4,w(k)Txm=0,w(13)=w(12)+x4=(-3,0,0)TK=13,xm=x1,w(k)Txm=0,w(14)=w(13)+x1=(-3,0,1)TK=14,xm=x2,w(k)Txm=1>0,w(15)=w(14)K=15,xm=x3,w(k)Txm=2>0,w(16)=w(15)K=16,xm=x4,w(k)Txm=2>0,w(17)=w(16)K=17,xm=x1,w(k)Txm=1>0,w(18)=w(17)2023/2/1模式識(shí)別導(dǎo)論46例子1通過上面的結(jié)果可以看出，經(jīng)過對(duì)x1,x2,x3,x4一輪迭代后，使用w(14)已經(jīng)能夠?qū)λ杏?xùn)練樣本正確分類，增廣權(quán)矢量的值不再發(fā)生變化，所以算法收斂于w(14)，w(14)就是所求的解向量，即w*=(-3,0,1)T。由此可以得到區(qū)分界面為：-3x1+1=0采用多類情況3的方法時(shí)，應(yīng)有：2.感知器算法用于多類情況若，則對(duì)于M類模式應(yīng)存在M個(gè)判決函數(shù)：算法主要內(nèi)容：設(shè)有M種模式類別：設(shè)其權(quán)向量初值為：

第k次迭代時(shí)，一個(gè)屬于ωi類的模式樣本X

被送入分類器，計(jì)算所有判別函數(shù)訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理。分二種情況修改權(quán)向量：②若第l個(gè)權(quán)向量使，則相應(yīng)的權(quán)向量作調(diào)整，即：

可以證明：只要模式類在情況3判別函數(shù)時(shí)是可分的，則經(jīng)過有限次迭代后算法收斂。，c為正的校正增量例3.9

設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為①若則權(quán)向量不變；現(xiàn)采用多類情況3的方式分類，試用感知器算法求出判別函數(shù)。解：增廣向量形式：注意，這里任一類的樣本都不能乘以（－1）。任取初始權(quán)向量；c=1第一次迭代：三個(gè)權(quán)向量都需要修改：，但且不成立，第二次迭代：，但且不成立，修改權(quán)向量：第三次迭代：修改為權(quán)向量。，但且不成立，

以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類，進(jìn)行下一輪迭代。第四次迭代：……在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類。權(quán)向量的解：判別函數(shù)：2023/2/1模式識(shí)別導(dǎo)論522.2.3感知器準(zhǔn)則函數(shù)及其梯度法在兩類樣本線性可分的情況下，通過上面的例子可知，如果將屬于wj的樣本各分量同時(shí)乘以-1，則可以由所有滿足wTx>0的樣本求出解w*，即可確定決策函數(shù)。但是，對(duì)于求解問題，可能存在多個(gè)可行解，因此問題進(jìn)一步轉(zhuǎn)化成如何按一定條件利用優(yōu)化算法求得最優(yōu)解的問題。感知器準(zhǔn)則函數(shù)與梯度法。2023/2/1模式識(shí)別導(dǎo)論532.2.3感知器準(zhǔn)則函數(shù)及其梯度法梯度法采用最優(yōu)化技術(shù)求線性判別函數(shù)中的增廣權(quán)向量，首先需要構(gòu)造準(zhǔn)則函數(shù)。其次再通過優(yōu)化算法求得最優(yōu)解，這里選用梯度法求解。一個(gè)可微函數(shù)某點(diǎn)的梯度給出函數(shù)在該點(diǎn)的變化率最大的方向；負(fù)梯度給出下降最快的方向。那么對(duì)于有極小值的函數(shù)而言，可以沿著負(fù)梯度的方向選擇適當(dāng)?shù)牟介L(zhǎng)進(jìn)行搜索，求解函數(shù)的極小值點(diǎn)。2023/2/1模式識(shí)別導(dǎo)論54梯度法如果我們定義一個(gè)準(zhǔn)則函數(shù)J(w,x)，它的最小值對(duì)應(yīng)著最優(yōu)解w*，那么完全可以運(yùn)用數(shù)學(xué)分析中這種求極值的方法來(lái)進(jìn)行求解，這便是梯度法的基本思想。由于是迭代算法，所以它有一個(gè)迭代公式，并且可以找到數(shù)值解。迭代公式如下：2.2.3感知器準(zhǔn)則函數(shù)及其梯度法2023/2/1模式識(shí)別導(dǎo)論55感知器準(zhǔn)則函數(shù)構(gòu)造準(zhǔn)則函數(shù)如下：當(dāng)|wTx|-wTx=0，該準(zhǔn)則函數(shù)可以達(dá)到最小值，此時(shí)有wTx>0，所以可以得到最優(yōu)解，也就是最優(yōu)權(quán)向量w*。2.2.3感知器準(zhǔn)則函數(shù)及其梯度法2023/2/1模式識(shí)別導(dǎo)論56感知器準(zhǔn)則函數(shù)當(dāng)p=c時(shí)，梯度下降法與感知器訓(xùn)練算法的修正公式一致，因此感知器訓(xùn)練算法是梯度下降法的一種特例，一般將p為常數(shù)的梯度法稱為固定增量法。當(dāng)p在迭代運(yùn)算時(shí)隨k變化，稱為可變?cè)隽糠ā?.2.3感知器準(zhǔn)則函數(shù)及其梯度法2.7最小平方誤差算法（leastmeansquareerror,LMSE；亦稱Ho-Kashyap算法）

上述的感知器算法、梯度算法、固定增量算法或其他類似方法，只有當(dāng)模式類可分離時(shí)才收斂，在不可分的情況下，算法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a)迭代過程本身收斂緩慢b)模式本身不可分對(duì)可分模式收斂。對(duì)于類別不可分的情況也能指出來(lái)。LMSE算法特點(diǎn)：2023/2/1模式識(shí)別導(dǎo)論582.3最小平方誤差準(zhǔn)則在兩類樣本線性可分的情況下，如果將屬于wj的樣本各分量同時(shí)乘以-1，則應(yīng)該有權(quán)向量w，對(duì)所有樣本滿足wTxi>0，設(shè)計(jì)分類器就是求解一組線性不等式。如果任意給定一個(gè)向量b=[b1,b2,…,bn]T>0，那么上述問題可以轉(zhuǎn)化成求解w，使之滿足wTxi＝bi。2023/2/1模式識(shí)別導(dǎo)論592.3最小平方誤差準(zhǔn)則設(shè)分別屬于wi與wj的樣本數(shù)為n1與n2，n=n1+n2W為d+1維列向量，通常有：n>d+1，那么方程是沒有精確解存在的。定義誤差向量：e=xw-b最小平方誤差準(zhǔn)則函數(shù)如下：2023/2/1模式識(shí)別導(dǎo)論602.3最小平方誤差準(zhǔn)則此時(shí)的w*并不是最小平方誤差準(zhǔn)則函數(shù)下的解，因?yàn)閣*還依賴于b。根據(jù)平方誤差準(zhǔn)則函數(shù)，使用固定增量的梯度下降法建立b的迭代公式如下（即b的初始值可以任意給定）。1.分類器的不等式方程

兩類分類問題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于，兩個(gè)模式類的訓(xùn)練樣本集，應(yīng)滿足：其中，Xi是規(guī)范化增廣樣本向量，。上式分開寫為：寫成矩陣形式為：令N×(n+1)的長(zhǎng)方矩陣為X，則變?yōu)椋菏街校?為零向量感知器算法是通過解不等式組，求出W。2.LMSE算法1)原理的求解。式中：∴

兩式等價(jià)。為各分量均為正值的矢量。LMSE算法把對(duì)滿足XW>0

的求解，改為滿足①在方程組中當(dāng)行數(shù)>>列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模式的維數(shù)n，因此方程的個(gè)數(shù)(行數(shù))>>模式向量的維數(shù)(列數(shù))，是矛盾方程組，只能求近似解W*，即說(shuō)明：②LMSE算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng)J達(dá)到最小值時(shí)，XW=B

可得到近似解（最小二乘近似解）。③LMSE算法的思路：轉(zhuǎn)化為轉(zhuǎn)化為準(zhǔn)則函數(shù)定義為：“最小二乘”：——最?。菏狗匠探M兩邊誤差最小，也即使J最小?！耍捍螖?shù)為2，乘了兩次最小平方（誤差算法）考察向量(XW－B)有：可以看出：①當(dāng)函數(shù)J達(dá)到最小值，等式XW=B有最優(yōu)解。即又將問題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問題。②因?yàn)镴有兩個(gè)變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。XW=B

的近似解也稱“最優(yōu)近似解”：——使方程組兩邊所有誤差之和最?。醋顑?yōu)）的解。準(zhǔn)則函數(shù)：使J對(duì)W求最小，令，得：2)推導(dǎo)LMSE算法遞推公式與問題相關(guān)的兩個(gè)梯度：(3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求遞推公式：(1)求W的遞推關(guān)系X為N×(n+1)長(zhǎng)方陣，X#為(n+1)×N長(zhǎng)方陣。稱為X的偽逆，式中：(3-45)(2)求B(k+1)的迭代式(3-46)代入，得

令，定義(3-49)(3-50)(3-46)利用梯度算法公式有：(3)求W(k+1)的迭代式將(3-50)代入(3-47)式W=X#B

有：=0(3-49)(3-50)總結(jié)：設(shè)初值B(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù)?！璚(k+1)、B(k+1)互相獨(dú)立，先后次序無(wú)關(guān)。……求出B，W后，再迭代出下一個(gè)e，從而計(jì)算出新的B，

W。或另一算法：先算B(k+1)，再算W(k+1)。3）模式類別可分性判別②

如果e(k)>0

，表明XW(k)>B(k)>0，隱含有解。繼續(xù)迭代，可使e(k)→0

。③

如果e(k)<0（所有分量為負(fù)數(shù)或零，但不全為零），停止迭代，無(wú)解。此時(shí)若繼續(xù)迭代，數(shù)據(jù)不再發(fā)生變化。

可以證明：當(dāng)模式類線性可分，且校正系數(shù)c滿足時(shí)，該算法收斂，可求得解W。

理論上不能證明該算法到底需要迭代多少步才能達(dá)到收斂，通常在每次迭代計(jì)算后檢查一下XW(k)和誤差向量e(k)，從而可以判斷是否收斂。①

如果e(k)=0

，表明XW(k)=B(k)>0，有解。分以下幾種情況：情況③分析：e(k)<0

綜上所述：只有當(dāng)e(k)中有大于零的分量時(shí)，才需要繼續(xù)迭代，一旦e(k)的全部分量只有0和負(fù)數(shù)，則立即停止。事實(shí)上，往往早在e(k)全部分量都達(dá)到非正值以前，就能看出其中有些分量向正值變化得極慢，可及早采取對(duì)策。

通過反證法可以證明：在線性可分情況下，算法進(jìn)行過程中不會(huì)出現(xiàn)e(k)的分量全為負(fù)的情況；若出現(xiàn)e(k)的分量全為負(fù)，則說(shuō)明模式類線性不可分。4)LMSE算法描述(1)根據(jù)N個(gè)分屬于兩類的樣本，寫出規(guī)范化增廣樣本矩陣X。(2)求X的偽逆矩陣?！?3)設(shè)置初值c和B(1)，c為正的校正增量，B(1)的各分量大于零，迭代次數(shù)k=1。開始迭代：計(jì)算(4)計(jì)算，進(jìn)行可分性判別。如果e(k)>0，線性可分，若進(jìn)入(5)可使e(k)→0

，得最優(yōu)解。如果e(k)<0，線性不可分，停止迭代，無(wú)解，算法結(jié)束。如果e(k)=0，線性可分，解為W(k)，算法結(jié)束。否則，說(shuō)明e(k)的各分量值有正有負(fù)，進(jìn)入(5)。(5)計(jì)算W(k+1)和B(k+1)。方法1：分別計(jì)算方法2：先計(jì)算再計(jì)算迭代次數(shù)k加1，返回(4)。3.算法特點(diǎn)(1)算法盡管略為復(fù)雜一些，但提供了線性可分的測(cè)試特征。(2)同時(shí)利用N個(gè)訓(xùn)練樣本，同時(shí)修改W和B，故收斂速度快。(3)計(jì)算矩陣復(fù)雜，但可用迭代算法計(jì)算。例3.11已知兩類模式訓(xùn)練樣本：試用LMSE算法求解權(quán)向量。解：(1)寫出規(guī)范化增廣樣本矩陣：

Aij是aij的代數(shù)余子式，注意兩者的行和列的標(biāo)號(hào)互換。(2)求偽逆矩陣求逆矩陣：若，則|A|——A的行列式A*——A的伴隨矩陣

劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij，將叫做元素aij的代數(shù)余子式。例：代數(shù)余子式定義：行列式:(3)取和c=1開始迭代：.解為W(1)，判斷函數(shù)為：圖示如下：例3.12已知模式訓(xùn)練樣本：，(2)求：解：(1)規(guī)范化增廣樣本矩陣：(3)取和c=1，迭代：用LMSE算法求解權(quán)向量。

e(1)全部分量為負(fù)，無(wú)解，停止迭代。為線性不可分模式。

小結(jié)：(1)感知器法、梯度法、最小平方誤差算法討論的分類算法都是通過模式樣本來(lái)確定判別函數(shù)的系數(shù)，所以要使一個(gè)分類器設(shè)計(jì)完善，必須采用有代表性的數(shù)據(jù)，訓(xùn)練判別函數(shù)的權(quán)系數(shù)。它們能合理反映模式數(shù)據(jù)的總體。(2)要獲得一個(gè)有較好判別性能的線性分類器，所需要的訓(xùn)練樣本的數(shù)目的確定。用指標(biāo)二分法能力N0來(lái)確定訓(xùn)練樣本的數(shù)目：通常訓(xùn)練樣本的數(shù)目不能低于N0

，選為

N0的5~10倍左右。二維：不能低于6個(gè)樣本，最好選在30~60個(gè)樣本之間。三維：不能低于8個(gè)樣本，最好選在40~80個(gè)樣本之間。n為模式維數(shù)如2023/2/1模式識(shí)別導(dǎo)論852.4

Fisher線性判別準(zhǔn)則2023/2/1模式識(shí)別導(dǎo)論862023/2/1模式識(shí)別導(dǎo)論872023/2/1模式識(shí)別導(dǎo)論882023/2/1模式識(shí)別導(dǎo)論892.4

Fisher線性判別準(zhǔn)則是將d維空間的樣本映射到了一維樣本集，這個(gè)一維空間的方向是相對(duì)于Fisher準(zhǔn)則為最好的。我們還需要解決分類問題。將d維分類問題轉(zhuǎn)化為一維分類問題后，只需要確定一個(gè)閾值點(diǎn)，將投影點(diǎn)與閾值點(diǎn)比較，就可以做出決策。902.4Fisher線性判別91二維模式向一維空間投影示意圖uroxy92二維模式向一維空間投影示意圖uroxy93二維模式向一維空間投影示意圖oxyoxy94（1)求解Fish準(zhǔn)則函數(shù)9596類間離差度為：97并使其最大,上式稱為Fisher準(zhǔn)則函數(shù)。98利用二次型關(guān)于矢量求導(dǎo)的公式可得：（2)求解Fisher最佳鑒別矢量令可得：99100上式右邊后兩項(xiàng)因子的乘積為一標(biāo)量，令其為，于是可得式中為一標(biāo)量因子，其不改變軸的方向，可以取為1,于是有101此時(shí)的可使Fisher準(zhǔn)則函數(shù)取最大值，即是n

維空間到一維空間投影軸