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

1、模式識別第二章線性判別函數(shù)法第1頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論2實例：統(tǒng)計模式識別19名男女同學進行體檢，測量了身高和體重，但事后發(fā)現(xiàn)其中有4人忘記填寫性別，試問（在最小錯誤的條件下）這4人是男是女？體檢數(shù)值如下：第2頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論3實例：統(tǒng)計模式識別（續(xù)）待識別的模式：性別（男或女）測量的特征：身高和體重訓(xùn)練樣本：15名已知性別的樣本特征目標：希望借助于訓(xùn)練樣本的特征建立判別函數(shù)（即數(shù)學模型）第3頁，共124頁，2022年，5月20日，23點34分，星期四2

2、022/9/21模式識別導(dǎo)論4實例：統(tǒng)計模式識別（續(xù)）從圖中訓(xùn)練樣本的分布情況，找出男、女兩類特征各自的聚類特點，從而求取一個判別函數(shù)（直線或曲線）。只要給出待分類的模式特征的數(shù)值，看它在特征平面上落在判別函數(shù)的哪一側(cè)，就可以判別是男還是女了。第4頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論5有關(guān)模式識別的3個問題學習人們在日常生活中幾乎時時刻刻在進行模式識別的活動，從小時候起就開始學習與增強這種能力。如小孩學習認字、認識事物都有一個從不會到會的過程。 確定分類決策的具體數(shù)學公式是通過分類器設(shè)計這個過程確定的。在模式識別學科中一般把這個過程稱為訓(xùn)練

3、與學習的過程。 一般來說，決定使用什么類型的分類函數(shù)往往是人為決定的。但數(shù)學式子中的參數(shù)則往往通過學習來確定 第5頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論6有關(guān)模式識別的3個問題模式的緊致性分類器設(shè)計難易程度與模式在特征空間的分布方式有密切關(guān)系，例如圖(a)、(b)與(c)分別表示了兩類在空間分布的三種狀況。兩類事物分布的區(qū)域不要有相互混迭的情況，事物盡管沒有混迭，但交界線很復(fù)雜。第6頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論71有關(guān)模式識別的3個問題相似性度量同類物體之所以屬于同一類，在于它們的

4、某些屬性相似，因此可選擇適當?shù)亩攘糠椒z測出它們之間的相似性。 在特征空間中用特征向量描述樣本的屬性，用距離來表示相似性度量。 合適的特征空間情況下，同類樣本應(yīng)具有聚類性，或緊致性好，而不同類別樣本應(yīng)在特征空間中顯示出具有較大的距離。 第7頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論84.1 引言分類器設(shè)計方法，是根據(jù)訓(xùn)練樣本集提供的信息，直接進行分類器設(shè)計。這種方法省去了統(tǒng)計分布狀況分析，直接對特征空間進行劃分，也是當前的主要方法之一。第8頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論92.1 引言決策

5、域的分界面是用數(shù)學表達式來描述的，如線性函數(shù)和各種非線性函數(shù)等，所以分界面的方程主要包括函數(shù)類型選擇與最佳參數(shù)確定。一般來說，函數(shù)類型由設(shè)計者選擇，其參數(shù)的確定則是依據(jù)一定的準則函數(shù)，通過一個學習過程來實現(xiàn)優(yōu)化。第9頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論102.1 引言將模式識別的設(shè)計過程，主要是判別函數(shù)、決策面方程的確定過程改成 第10頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論112.1 引言線性分類器以及作為設(shè)計依據(jù)的一些準則函數(shù)，準則函數(shù)包括：感知準則，最小平方誤差準則，最小錯分樣本數(shù)準則

6、，F(xiàn)isher準則。第11頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論122.2.1 線性判別函數(shù)的基本概念 在一個d維的特征空間中，線性判別函數(shù)的一般表達式如下第12頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論132.2.1 線性判別函數(shù)的基本概念如果采用增廣模式，可以表達如下第13頁，共124頁，2022年，5月20日，23點34分，星期四若分屬于1，2的兩類模式可用一方程d(X) =0來劃分，那么稱d(X) 為判別函數(shù)，或稱判決函數(shù)、決策函數(shù)。2.1 判別函數(shù)(discriminant funct

7、ion) 直接用來對模式進行分類的準則函數(shù)。例：一個二維的兩類判別問題，模式分布如圖示，這些分屬于1，2兩類的模式可用一直線方程 d(X)=0來劃分。為坐標變量，為方程參數(shù)。式中：圖3.2 兩類二維模式的分布1判別函數(shù)的定義第14頁，共124頁，2022年，5月20日，23點34分，星期四若 ，則若 ，則 類；若 ，則 類； 或拒絕將某一未知模式 X 代入：維數(shù)=3時：判別邊界為一平面。維數(shù)3時：判別邊界為一超平面。第15頁，共124頁，2022年，5月20日，23點34分，星期四 d(X) 表示的是一種分類的標準，它可以是1、2、3維的，也可以是更高維的。 判別界面的正負側(cè)，是在訓(xùn)練判別函數(shù)

8、的權(quán)值時確定的。2判別函數(shù)正負值的確定圖3.3 判別函數(shù)正負的確定第16頁，共124頁，2022年，5月20日，23點34分，星期四1）判決函數(shù)d(X)的幾何性質(zhì)。它可以是線性的或非線性的函 數(shù)，維數(shù)在特征提取時已經(jīng)確定。如：已知三維線性分類 判決函數(shù)的性質(zhì)就確定了判決函數(shù) 的形式：3. 確定判別函數(shù)的兩個因素例：非線性判決函數(shù)2）判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。第17頁，共124頁，2022年，5月20日，23點34分，星期四18第18頁，共124頁，2022年，5月20日，23點34分，星期四19第19頁，共124頁，2022年，5月20日，23點34分，星期四20多類問題圖

9、例（第一種情況）?不確定區(qū)域第20頁，共124頁，2022年，5月20日，23點34分，星期四211、第一種情況（續(xù)）判別規(guī)則為：如果 則判 比如對圖的三類問題,如果對于任一模式 如果它的 則該模式屬于1類。 第21頁，共124頁，2022年，5月20日，23點34分，星期四221、第一種情況（續(xù)）如果某個X使二個以上的判別函數(shù) di0 。則此模式X就無法作出確切的判決。如圖另一種情況是IR2區(qū)域，判別函數(shù)都為負值。IR1，IR2，IR3，IR4。都為不確定區(qū)域。第22頁，共124頁，2022年，5月20日，23點34分，星期四231、第一種情況（續(xù)）解： 三個判別邊界分別為：第23頁，共12

10、4頁，2022年，5月20日，23點34分，星期四241、第一種情況（續(xù)）結(jié)論： 因為所以它屬于2類。第24頁，共124頁，2022年，5月20日，23點34分，星期四251、第一種情況（續(xù)）第25頁，共124頁，2022年，5月20日，23點34分，星期四26第26頁，共124頁，2022年，5月20日，23點34分，星期四272、第二種情況（續(xù)）多類問題圖例（第二種情況）第27頁，共124頁，2022年，5月20日，23點34分，星期四28第28頁，共124頁，2022年，5月20日，23點34分，星期四29d12(x) = - d21(x) = x1 x2 + 5 = 0d12(x)為正

11、兩分法例題圖示0 1 2 3 4 5 6 7 8 9987654321d21(x)為正第29頁，共124頁，2022年，5月20日，23點34分，星期四30d12(x)為正兩分法例題圖示0 1 2 3 4 5 6 7 8 9987654321d21(x)為正d23(x)= -d32(x)= x1+x2= 0d32(x)為正d23(x)為正第30頁，共124頁，2022年，5月20日，23點34分，星期四31d12(x)為正兩分法例題圖示0 1 2 3 4 5 6 7 8 9987654321d21(x)為正d32(x)為正d23(x)為正d13(x)= -d31(x)= x1+3 = 0d31

12、(x)為正d13(x)為正第31頁，共124頁，2022年，5月20日，23點34分，星期四321類判別區(qū)域 d12(x)0 d13(x)02類判別區(qū)域 d21(x)0 d23(x)0d12(x)為正兩分法例題圖示0 1 2 3 4 5 6 7 8 9987654321d21(x)為正d32(x)為正d23(x)為正d31(x)為正d13(x)為正3類判別區(qū)域 d31(x)0 d32(x)0IR第32頁，共124頁，2022年，5月20日，23點34分，星期四33第33頁，共124頁，2022年，5月20日，23點34分，星期四343、第三種情況（續(xù)）多類問題圖例（第三種情況）第34頁，共12

13、4頁，2022年，5月20日，23點34分，星期四35。第35頁，共124頁，2022年，5月20日，23點34分，星期四36上述三種方法小結(jié): 方法判別函數(shù)的數(shù)目和方法相同，但沒有不確定區(qū)，分析簡單，是最常用的一種方法。時，法比法需要更多當?shù)呐袆e函數(shù)式，這是一個缺點。類與其余的開，而法是將類和類分開，顯然法是將但是類區(qū)分法使模式更容易線性可分，這是它的優(yōu)點。第36頁，共124頁，2022年，5月20日，23點34分，星期四(1) 明確概念：線性可分。 一旦線性判別函數(shù)的系數(shù)Wk被確定以后，這些函數(shù)就可以作為模式分類的基礎(chǔ)。3. 小結(jié)(2) 分法的比較： 對于M類模式的分類， 兩分法共需要M個

14、判別函數(shù)，但 兩分法需要M(M-1)/2個。當時M3時，后者需要更多個判別式（缺點），但對模式的線性可分的可能性要更大一些（優(yōu)點）。 原因： 一種類別模式的分布要比M-1類模式的分布更為聚集， 分法受到的限制條件少，故線性可分的可能性大。第37頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論38.2.1 線性判別函數(shù)的基本概念線性分類器的設(shè)計就是利用訓(xùn)練樣本集建立線性判別函數(shù)式，也就是尋找最優(yōu)的權(quán)向量w的過程。其主要步驟如下采集訓(xùn)練樣本，構(gòu)成訓(xùn)練樣本集。樣本應(yīng)該具有典型性確定一個準則J=J(w,x)，能反映分類器性能，且存在權(quán)值w*使得分類器性能最優(yōu)設(shè)

15、計求解w的最優(yōu)算法，得到解向量w*第38頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論392.2.2 感知器概念及其訓(xùn)練方法感知準則函數(shù)是五十年代由Rosenblatt提出的一種自學習判別函數(shù)生成方法，由于Rosenblatt企圖將其用于腦模型感知器，因此被稱為感知準則函數(shù)。其特點是隨意確定的判別函數(shù)初始值，在對樣本分類訓(xùn)練過程中逐步修正直至最終確定。第39頁，共124頁，2022年，5月20日，23點34分，星期四402.3 感知器算法(Perceptron Approach)任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗分類是否正確對所有訓(xùn)練樣本都正確分類？

16、YesENDYesNo對權(quán)值進行校正No感知器算法流程圖流程:第40頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(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ù)0c1輸入樣本xm x1,x2,xn，計算判決函數(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=

17、k+1，返回第二步，直到w對所有樣本穩(wěn)定不變，結(jié)束第41頁，共124頁，2022年，5月20日，23點34分，星期四42二、收斂定理： 如果訓(xùn)練模式是線性可分的，感知器訓(xùn)練算法在有限次迭代后便可以收斂到正確的解矢量 。 。證明思路： 如果第k+1次迭代生成的權(quán)矢量比第k次迭代生成的權(quán)矢量更接近解矢量，則收斂，即：第42頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論43例子1已知兩類訓(xùn)練樣本，(0,0),(0,1)屬于w1，(1,0),(1,1)屬于w2，試用感知器算法求解w*訓(xùn)練樣本分量增廣化以及符號規(guī)范化。將訓(xùn)練樣本增加一個分量1，且把來自w2的樣

18、本各分量乘以-1，得到訓(xùn)練模式集x1=(0,0,1), x2=(0,1,1), x3=(-1,0,-1), x4=(-1,-1,-1)運用訓(xùn)練算法，給權(quán)向量賦初值w(1)=(1,1,1)T，取增量c=1，置迭代步數(shù)k=1，下面是迭代過程第43頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論44例子1K=1,xm=x1,w(k)Txm=10,w(2)=w(1)K=2, xm=x2,w(k)Txm=20,w(3)=w(2)K=3, xm=x3,w(k)Txm=-20,w(4)=w(3)+ x3=(0,1,0)TK=4, xm=x4,w(k)Txm=-10,

19、w(5)=w(4)+ x4=(-1,0,-1)TK=5, xm=x1,w(k)Txm=-10,w(9)=w(8)第44頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(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=20,w(11)=w(10)K=11, xm=x3,w(k)Txm=10,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(1

20、3)+ x1=(-3,0,1)TK=14, xm=x2,w(k)Txm=10,w(15)=w(14)K=15, xm=x3,w(k)Txm=20,w(16)=w(15)K=16, xm=x4,w(k)Txm=20,w(17)=w(16)K=17, xm=x1,w(k)Txm=10,w(18)=w(17)第45頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論46例子1通過上面的結(jié)果可以看出，經(jīng)過對x1, x2, x3, x4一輪迭代后，使用w(14)已經(jīng)能夠?qū)λ杏?xùn)練樣本正確分類，增廣權(quán)矢量的值不再發(fā)生變化，所以算法收斂于w(14)， w(14)就是所求

21、的解向量，即w*=(-3,0,1)T。由此可以得到區(qū)分界面為：-3x1+1=0第46頁，共124頁，2022年，5月20日，23點34分，星期四采用多類情況3的方法時，應(yīng)有：2. 感知器算法用于多類情況若，則 對于M類模式應(yīng)存在M個判決函數(shù)：算法主要內(nèi)容：設(shè)有 M 種模式類別： 設(shè)其權(quán)向量初值為： 第k次迭代時，一個屬于i類的模式樣本 X 被送入分類器，計算所有判別函數(shù)訓(xùn)練樣本為增廣向量形式，但不需要規(guī)范化處理。 分二種情況修改權(quán)向量：第47頁，共124頁，2022年，5月20日，23點34分，星期四 若第l個權(quán)向量使 ，則相應(yīng)的權(quán)向量作調(diào)整，即： 可以證明：只要模式類在情況3判別函數(shù)時是可分

22、的，則經(jīng)過有限次迭代后算法收斂。， c為正的校正增量例3.9 設(shè)有三個線性可分的模式類，三類的訓(xùn)練樣本分別為 若 則權(quán)向量不變；現(xiàn)采用多類情況3的方式分類，試用感知器算法求出判別函數(shù)。 第48頁，共124頁，2022年，5月20日，23點34分，星期四解：增廣向量形式：注意，這里任一類的樣本都不能乘以（1）。任取初始權(quán)向量；c=1 第一次迭代： 三個權(quán)向量都需要修改：，但且不成立，第49頁，共124頁，2022年，5月20日，23點34分，星期四第二次迭代： ，但且不成立，修改權(quán)向量：第三次迭代： 修改為權(quán)向量。，但且不成立， 以上進行的一輪迭代運算中，三個樣本都未正確分類，進行下一輪迭代。第

23、50頁，共124頁，2022年，5月20日，23點34分，星期四第四次迭代： 在第五、六、七迭代中，對所有三個樣本都已正確分類。權(quán)向量的解：判別函數(shù)：第51頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論522.2.3 感知器準則函數(shù)及其梯度法在兩類樣本線性可分的情況下，通過上面的例子可知，如果將屬于wj的樣本各分量同時乘以-1，則可以由所有滿足wTx0的樣本求出解w*，即可確定決策函數(shù)。但是，對于求解問題，可能存在多個可行解，因此問題進一步轉(zhuǎn)化成如何按一定條件利用優(yōu)化算法求得最優(yōu)解的問題。感知器準則函數(shù)與梯度法。第52頁，共124頁，2022年，5月

24、20日，23點34分，星期四2022/9/21模式識別導(dǎo)論532.2.3 感知器準則函數(shù)及其梯度法梯度法采用最優(yōu)化技術(shù)求線性判別函數(shù)中的增廣權(quán)向量，首先需要構(gòu)造準則函數(shù)。其次再通過優(yōu)化算法求得最優(yōu)解，這里選用梯度法求解。一個可微函數(shù)某點的梯度給出函數(shù)在該點的變化率最大的方向；負梯度給出下降最快的方向。那么對于有極小值的函數(shù)而言，可以沿著負梯度的方向選擇適當?shù)牟介L進行搜索，求解函數(shù)的極小值點。第53頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論54梯度法如果我們定義一個準則函數(shù)J(w,x)，它的最小值對應(yīng)著最優(yōu)解w*，那么完全可以運用數(shù)學分析中這種求極

25、值的方法來進行求解，這便是梯度法的基本思想。由于是迭代算法，所以它有一個迭代公式，并且可以找到數(shù)值解。迭代公式如下：2.2.3 感知器準則函數(shù)及其梯度法第54頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論55感知器準則函數(shù)構(gòu)造準則函數(shù)如下：當|wTx|- wTx=0，該準則函數(shù)可以達到最小值，此時有wTx0，所以可以得到最優(yōu)解，也就是最優(yōu)權(quán)向量w*。2.2.3 感知器準則函數(shù)及其梯度法第55頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論56感知器準則函數(shù)當p=c時，梯度下降法與感知器訓(xùn)練算法的修正公式一致，

26、因此感知器訓(xùn)練算法是梯度下降法的一種特例，一般將p為常數(shù)的梯度法稱為固定增量法。當p在迭代運算時隨k變化，稱為可變增量法。2.2.3 感知器準則函數(shù)及其梯度法第56頁，共124頁，2022年，5月20日，23點34分，星期四2.7 最小平方誤差算法（least mean square error, LMSE；亦稱Ho-Kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他類似方法，只有當模式類可分離時才收斂，在不可分的情況下，算法會來回擺動，始終不收斂。當一次次迭代而又不見收斂時，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a) 迭代過程本身收斂緩慢b) 模式本身不可分對可分模式收斂

27、。對于類別不可分的情況也能指出來。LMSE算法特點：第57頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論582.3 最小平方誤差準則在兩類樣本線性可分的情況下，如果將屬于wj的樣本各分量同時乘以-1，則應(yīng)該有權(quán)向量w，對所有樣本滿足wTxi 0，設(shè)計分類器就是求解一組線性不等式。如果任意給定一個向量b=b1,b2,bnT0，那么上述問題可以轉(zhuǎn)化成求解w，使之滿足wTxibi。第58頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論592.3 最小平方誤差準則設(shè)分別屬于wi與wj的樣本數(shù)為n1與n2，n= n1+

28、n2W為d+1維列向量，通常有：nd+1，那么方程是沒有精確解存在的。定義誤差向量：e=xw-b最小平方誤差準則函數(shù)如下：第59頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論602.3 最小平方誤差準則此時的w*并不是最小平方誤差準則函數(shù)下的解，因為w*還依賴于b。根據(jù)平方誤差準則函數(shù)，使用固定增量的梯度下降法建立b的迭代公式如下（即b的初始值可以任意給定）。第60頁，共124頁，2022年，5月20日，23點34分，星期四1. 分類器的不等式方程 兩類分類問題的解相當于求一組線性不等式的解。如果給出分屬于 ， 兩個模式類的訓(xùn)練樣本集 ，應(yīng)滿足：其中

29、，Xi是規(guī)范化增廣樣本向量， 。上式分開寫為：第61頁，共124頁，2022年，5月20日，23點34分，星期四寫成矩陣形式為 ： 令N (n+1) 的長方矩陣為X，則 變?yōu)椋旱?2頁，共124頁，2022年，5月20日，23點34分，星期四式中：0為零向量 感知器算法是通過解不等式組 ，求出W。第63頁，共124頁，2022年，5月20日，23點34分，星期四2. LMSE算法1) 原理的求解。式中： 兩式等價。為各分量均為正值的矢量。LMSE算法把對滿足 XW 0 的求解，改為滿足 在方程組中當行數(shù)列數(shù)時，通常無解，稱為矛盾方程組，一般求近似解。在模式識別中，通常訓(xùn)練樣本數(shù)N總是大于模式的

30、維數(shù)n，因此方程的個數(shù)(行數(shù))模式向量的維數(shù)(列數(shù))，是矛盾方程組，只能求近似解W*，即說明：第64頁，共124頁，2022年，5月20日，23點34分，星期四 LMSE算法的出發(fā)點：選擇一個準則函數(shù)，使得當J達到最小值時，XW=B 可得到近似解（最小二乘近似解）。 LMSE算法的思路：轉(zhuǎn)化為轉(zhuǎn)化為準則函數(shù)定義為： “最小二乘”： 最?。菏狗匠探M兩邊誤差最小， 也即使J最小。 二乘：次數(shù)為2，乘了兩次最小平方（誤差算法）第65頁，共124頁，2022年，5月20日，23點34分，星期四考察向量(XWB) 有：第66頁，共124頁，2022年，5月20日，23點34分，星期四可以看出： 當函數(shù)J

31、達到最小值，等式XW=B有最優(yōu)解。即又將問題轉(zhuǎn)化為求準則函數(shù)極小值的問題。 因為J有兩個變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。XW=B 的近似解也稱“最優(yōu)近似解”： 使方程組兩邊所有誤差之和最小（即最優(yōu)）的解。準則函數(shù)：第67頁，共124頁，2022年，5月20日，23點34分，星期四使J 對W求最小，令 ，得：2) 推導(dǎo)LMSE算法遞推公式與問題相關(guān)的兩個梯度： (3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求遞推公式：(1) 求W 的遞推關(guān)系X為N(n+1)長方陣，X#為(n+1) N 長方陣。稱為X的偽逆，式中： (3-45)第68頁，共

32、124頁，2022年，5月20日，23點34分，星期四(2) 求B(k+1)的迭代式(3-46)代入，得 令，定義(3-49)(3-50)(3-46)利用梯度算法公式有：第69頁，共124頁，2022年，5月20日，23點34分，星期四(3) 求W(k+1)的迭代式將(3-50)代入(3-47)式W=X#B 有：=0(3-49)(3-50)第70頁，共124頁，2022年，5月20日，23點34分，星期四總結(jié)：設(shè)初值B(1)，各分量均為正值，括號中數(shù)字代表迭代次數(shù) 。W(k+1)、B(k+1)互相獨立，先后次序無關(guān)。求出B，W后，再迭代出下一個e，從而計算出新的B， W?；蛄硪凰惴ǎ合人鉈(k

33、+1)，再算W(k+1)。第71頁，共124頁，2022年，5月20日，23點34分，星期四3）模式類別可分性判別 如果e(k)0 ，表明XW(k)B(k) 0， 隱含有解。繼續(xù)迭代， 可使e(k) 0 。 如果e(k)0，有解。分以下幾種情況：第72頁，共124頁，2022年，5月20日，23點34分，星期四情況分析：e(k)0，線性可分，若進入(5)可使e(k) 0 ，得最優(yōu)解。如果e(k)0，線性不可分，停止迭代，無解，算法結(jié)束。如果e(k)=0，線性可分，解為W(k)，算法結(jié)束。否則，說明e(k)的各分量值有正有負，進入(5)。第75頁，共124頁，2022年，5月20日，23點34分

34、，星期四(5) 計算W(k+1)和B(k+1)。方法1：分別計算方法2：先計算再計算迭代次數(shù)k加1，返回(4)。3. 算法特點(1) 算法盡管略為復(fù)雜一些，但提供了線性可分的測試特征。(2) 同時利用N個訓(xùn)練樣本，同時修改W和B，故收斂速度快。(3) 計算矩陣 復(fù)雜，但可用迭代算法計算。第76頁，共124頁，2022年，5月20日，23點34分，星期四例3.11 已知兩類模式訓(xùn)練樣本： 試用LMSE算法求解權(quán)向量。解：(1) 寫出規(guī)范化增廣樣本矩陣：第77頁，共124頁，2022年，5月20日，23點34分，星期四 Aij是aij的代數(shù)余子式，注意兩者的行和列的標號互換。 (2) 求偽逆矩陣求

35、逆矩陣：若，則 |A|A的行列式A*A的伴隨矩陣第78頁，共124頁，2022年，5月20日，23點34分，星期四 劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij ，將 叫做元素aij的代數(shù)余子式。例：代數(shù)余子式定義： 行列式: 第79頁，共124頁，2022年，5月20日，23點34分，星期四(3) 取 和 c=1 開始迭代：.解為 W(1) ，判斷函數(shù)為：第80頁，共124頁，2022年，5月20日，23點34分，星期四圖示如下：第81頁，共124頁，2022年，5月20日，23點34分，星期四例3.12 已知模式訓(xùn)練樣本： ，( 2) 求 ：解：(1) 規(guī)

36、范化增廣樣本矩陣：(3) 取 和c=1，迭代：用LMSE算法求解權(quán)向量。 第82頁，共124頁，2022年，5月20日，23點34分，星期四 e(1)全部分量為負，無解，停止迭代。為線性不可分模式。 第83頁，共124頁，2022年，5月20日，23點34分，星期四小結(jié)：(1) 感知器法、梯度法、最小平方誤差算法討論的分類算法都是通過模式樣本來確定判別函數(shù)的系數(shù)，所以要使一個分類器設(shè)計完善，必須采用有代表性的數(shù)據(jù)，訓(xùn)練判別函數(shù)的權(quán)系數(shù)。它們能合理反映模式數(shù)據(jù)的總體。(2) 要獲得一個有較好判別性能的線性分類器，所需要的訓(xùn)練樣本的數(shù)目的確定。用指標二分法能力N0來確定訓(xùn)練樣本的數(shù)目：通常訓(xùn)練樣本

37、的數(shù)目不能低于N0 ，選為 N0的510倍左右。二維：不能低于6個樣本，最好選在3060個樣本之間。三維：不能低于8個樣本，最好選在4080個樣本之間。n為模式維數(shù)如第84頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論852.4 Fisher線性判別準則第85頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論86第86頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論87第87頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論88第

38、88頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論892.4 Fisher線性判別準則是將d維空間的樣本映射到了一維樣本集，這個一維空間的方向是相對于Fisher準則為最好的。我們還需要解決分類問題。將d維分類問題轉(zhuǎn)化為一維分類問題后，只需要確定一個閾值點，將投影點與閾值點比較，就可以做出決策。第89頁，共124頁，2022年，5月20日，23點34分，星期四902.4 Fisher線性判別第90頁，共124頁，2022年，5月20日，23點34分，星期四91二維模式向一維空間投影示意圖uroxy第91頁，共124頁，2022年，5月20日，23點3

39、4分，星期四92二維模式向一維空間投影示意圖uroxy第92頁，共124頁，2022年，5月20日，23點34分，星期四93二維模式向一維空間投影示意圖oxyoxy第93頁，共124頁，2022年，5月20日，23點34分，星期四94（1)求解Fish準則函數(shù)第94頁，共124頁，2022年，5月20日，23點34分，星期四95第95頁，共124頁，2022年，5月20日，23點34分，星期四96類間離差度為：第96頁，共124頁，2022年，5月20日，23點34分，星期四97并使其最大,上式稱為Fisher準則函數(shù)。第97頁，共124頁，2022年，5月20日，23點34分，星期四98利用

40、二次型關(guān)于矢量求導(dǎo)的公式可得：（2) 求解Fisher最佳鑒別矢量令可得：第98頁，共124頁，2022年，5月20日，23點34分，星期四99第99頁，共124頁，2022年，5月20日，23點34分，星期四100上式右邊后兩項因子的乘積為一標量，令其為 ，于是可得式中 為一標量因子，其不改變軸的方向，可以取為1,于是有第100頁，共124頁，2022年，5月20日，23點34分，星期四101此時的 可使Fisher準則函數(shù)取最大值，即是n 維空間到一維空間投影軸的最佳方向，由和JF 最大值為:第101頁，共124頁，2022年，5月20日，23點34分，星期四102即稱為Fisher變換函

41、數(shù)JF=第102頁，共124頁，2022年，5月20日，23點34分，星期四103 由于變換后的模式是一維的，因此判別界面實際上是各類模式所在軸上的一個點，所以可以根據(jù)訓(xùn)練模式確定一個閾值 yt，于是Fisher判別規(guī)則為: （3) 求解Fisher判別函數(shù)判別閾值可取兩個類心在u方向上軸的投影連線的中點作為閾值，即:第103頁，共124頁，2022年，5月20日，23點34分，星期四104第104頁，共124頁，2022年，5月20日，23點34分，星期四105（7） 計算 。（8） 計算yt 。（9） 對未知模式x判定模式類。第105頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論106 例一第106頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論107第107頁，共124頁，2022年，5月20日，23點34分，星期四2022/9/21模式識別導(dǎo)論108第108頁，共124頁