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

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

或拒絕將某一未知模式

X

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

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

。則此模式X就無法作出確切的判決。如圖另一種情況是IR2區域，判別函數都為負值。IR1，IR2，IR3，IR4。都為不確定區域。231、第一種情況（續）解：三個判別邊界分別為：241、第一種情況（續）結論：因為所以它屬于ω2類。251、第一種情況（續）26272、第二種情況（續）多類問題圖例（第二種情況）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類判別區域

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

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

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

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

對于M類模式的分類，兩分法共需要M個判別函數，但兩分法需要M(M-1)/2個。當時M>3時，后者需要更多個判別式（缺點），但對模式的線性可分的可能性要更大一些（優點）。原因：

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

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

如果第k+1次迭代生成的權矢量比第k次迭代生成的權矢量更接近解矢量，則收斂，即：2023/2/1模式識別導論43例子1已知兩類訓練樣本，(0,0),(0,1)屬于w1，(1,0),(1,1)屬于w2，試用感知器算法求解w*訓練樣本分量增廣化以及符號規范化。將訓練樣本增加一個分量1，且把來自w2的樣本各分量乘以-1，得到訓練模式集x1=(0,0,1),x2=(0,1,1),x3=(-1,0,-1),x4=(-1,-1,-1)運用訓練算法，給權向量賦初值w(1)=(1,1,1)T，取增量c=1，置迭代步數k=1，下面是迭代過程2023/2/1模式識別導論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模式識別導論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模式識別導論46例子1通過上面的結果可以看出，經過對x1,x2,x3,x4一輪迭代后，使用w(14)已經能夠對所有訓練樣本正確分類，增廣權矢量的值不再發生變化，所以算法收斂于w(14)，w(14)就是所求的解向量，即w*=(-3,0,1)T。由此可以得到區分界面為：-3x1+1=0采用多類情況3的方法時，應有：2.感知器算法用于多類情況若，則對于M類模式應存在M個判決函數：算法主要內容：設有M種模式類別：設其權向量初值為：

第k次迭代時，一個屬于ωi類的模式樣本X

被送入分類器，計算所有判別函數訓練樣本為增廣向量形式，但不需要規范化處理。分二種情況修改權向量：②若第l個權向量使，則相應的權向量作調整，即：

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

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

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

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

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

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

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

可得到近似解（最小二乘近似解）。③LMSE算法的思路：轉化為轉化為準則函數定義為：“最小二乘”：——最小：使方程組兩邊誤差最小，也即使J最小。——二乘：次數為2，乘了兩次最小平方（誤差算法）考察向量(XW－B)有：可以看出：①當函數J達到最小值，等式XW=B有最優解。即又將問題轉化為求準則函數極小值的問題。②因為J有兩個變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。XW=B

的近似解也稱“最優近似解”：——使方程組兩邊所有誤差之和最小（即最優）的解。準則函數：使J對W求最小，令，得：2)推導LMSE算法遞推公式與問題相關的兩個梯度：(3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求遞推公式：(1)求W的遞推關系X為N×(n+1)長方陣，X#為(n+1)×N長方陣。稱為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)總結：設初值B(1)，各分量均為正值，括號中數字代表迭代次數。……W(k+1)、B(k+1)互相獨立，先后次序無關。……求出B，W后，再迭代出下一個e，從而計算出新的B，

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

如果e(k)>0

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

。③

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

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

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

如果e(k)=0

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

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

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

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

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

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

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

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

，選為

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

Fisher線性判別準則2023/2/1模式識別導論862023/2/1模式識別導論872023/2/1模式識別導論882023/2/1模式識別導論892.4

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

維空間到一維空間投影軸