第三章線性判別函數第三章線性判別函數§3.1引言§3.2線性判別函數§3.3廣義線性判別函數§3.4感知器算法§3.5梯度學習算法§3.6最小均方誤差算法（LMSE）§3.7Fisher線性判別§3.1引言聚類分析法（第二章）判決函數法幾何分類法[可訓練的確定性分類器迭代算法]概率分類法[可訓練的模式分類器迭代算法]線性判決函數法（第三章）統計決策方法非線性判決函數法復習與引申：模式識別統計若分屬于和的兩類模式可用一方程來劃分，那么稱為決策函數，或稱判決函數、判別函數。一、判決函數(discriminantfunction)

直接用來對模式進行分類的準則函數。例：一個二維的兩類判別問題，模式分布如圖示，這些分屬于、兩類的模式可用一直線方程來劃分。（3-1）為坐標變量，為方程參數。式中：一、判決函數(discriminantfunction)

顏色（綠/紅）似圓度判別函數(DiscriminantFunction)將某一未知模式X代入：若，則類；若，則類；若，則維數=3時：判別邊界為一平面。維數>3時：判別邊界為一超平面。b)注意：對判別線正負的理解和確定。判別界面正負側的確定，是在訓練判別函數的權值時確定的，不要和幾何上的概念混淆。表示的是一種分類的標準，它可以是1、2、3維的，也可以是更高維的。說明：1、判決函數的幾何性質。它可以是線性的或非線性的函數，維數在特征提取時已經確定。如：已知三維線性分類——判決函數的性質就確定了判決函數的形式：二、確定判別函數的兩個因素例：非線性判決函數2.判決函數的系數。用所給的模式樣本確定。§3.2線性判別函數一、一般形式將二維模式推廣到n維，線性判別函數的一般形式為：(3-2)式中：：權向量，即參數向量。上式也可寫為增廣向量的形式：式中：為增廣權向量，為增廣模式向量。二、線性判決函數的性質識別時：若1、兩類情況：訓練時：（=0是不可判別情況，可以）模式可為M類，、、……、，有三種劃分方式：2、多類情況：兩分法兩分法兩分法特例兩分法(1)用線性判別函數將屬于ωi類的模式與其余不屬于ωi類的模式分開。從而訓練出第i類判決函數的權向量將某個待分類模式X分別代入M個類的d

(X)中，若只有di(X)>0，其他d(X)均<0，則判為ωi類。判別方法判決函數的訓練方法：對每一類的判決函數di(X)，分別將所有已知類別模式依次代入，有：

全部＜０不屬任何類

IR，可能

屬于1w或3w

1w2w3w0)(2=Xd0)(3=Xd++IR，可能

屬于3w或2w

+---0)(1=Xd0,,0312<>ddd0,,0321<>ddd0,0,321<>dddIR，可能屬于1w或2w

0,,0213<>ddd2x1x+對某一模式區，的條件超過一個，或全部的，分類失效。相當于不確定區（IndefiniteRegion，IR）。此法將M個多類問題分成M個兩類問題，識別每一類均需M個判別函數。在識別分類時：例1：設有一個三類問題，其判別式為：現有一模式，試判定應屬于哪類？解：將代入上三式，有：三個判別界面分別為：圖示如下：步驟：a)畫出界面直線。b)判別界面正負側：找特殊點帶入。c)找交集。例2：已知的位置和正負側，找區域。—0)(1=Xd+0)(2=Xd+—0)(3=Xd+—2w3w1w兩分法(2)一個判別界面只能分開兩個類別，不能把其余所有的類別都分開。判決函數為：。這里在M類模式中，與i有關的M-1個判決函數全為正時，X∈ωi。其中若有一個為負，則為IR區。則類，而在判別類模式時不起作用。如：對一個三類問題，如果、判別方法訓練方法：與值無關。例3：一個三類問題，三個判決函數為：問模式屬于哪類？解：計算得可寫成：(4,3)分類時：每分離出一類，需要與I有關的M-1個判決函數；要分開M類模式，共需M(M-1)/2個判決函數。對三類問題需要3(3-1)/2=3個判決函數。即：每次從M類中取出兩類的組合：例4：已知的位置和正負側，找區域。兩分法特例(3)對某類問題有M個判決函數：即：訓練方法：判別方法

判別界面需要做差值。對ωi類，應滿足di>其他所有d。最大判別準則特點：①是第二種情況的特例。因為可以定義：可證明：即：若各類別在第三種情況下可分，則在第二種情況下也可分，但反之不一定。③把M類情況分成了M-1個兩類問題。并且類的判別界面全部與類的判別界面相鄰(向無窮遠處延伸的區域除外)。②除邊界區外，沒有不確定區域。例5：一個三類模式（M=3）分類器，其判決函數為：且分別給出三類的判決界面。試判斷屬于哪一類，解：①類的判決函數：②判決界面如圖所示。類的判決函數：類的判決函數：例六：已知判決界面的位置和正負側，找區域。1、明確概念：線性可分。一旦線性判別函數的系數被確定以后，這些函數就可作為模式分類的基礎。三、小結2、分法的比較：對于M類模式的分類，兩分法共需要M個判別函數，但兩分法需要M(M-1)/2個。當時M>3時，后者需要更多個判別式（缺點），但對模式的線性可分的可能性要更大一些（優點）。原因：一種類別模式的分布要比M-1類模式的分布更為聚集，分法受到的限制條件少，故線性可分的可能性大。§3.3廣義線性判別函數1、目的：對非線性邊界面：通過某映射，把模式空間X變成X*，以便將X空間中非線性可分的模式集，變成在X*空間中線性可分的模式集。2、定義：設一訓練用模式集，在模式空間X中線性不可分，非線性判別函數形式如下：(3.3-1)式中是模式X的單值實函數，廣義形式的模式向量定義為：(3.3-2)的形式是多種多樣的。以X為二維時，選用二次多項式函數為例，如原判別的函數為：這里X*空間的維數k高于X空間的維數n，則(3.3-1)式寫成簡化的向量形式：上式是線性的。討論線性判別函數并不會失去一般性的意義。(3.3-3)定義：則可將線性化為即：。§3.4感知器算法一種設計線性分類器的算法感知器的概念感知器線性閾值單元在（2）式中，令并且令：Y＝1和Y＝－1，分別表示兩種類型，則（2）式演變為：問題：已知訓練樣本集，求加權向量W*。§3.4感知器算法一、概念理解只要求出權向量，分類器的設計即告完成。本節開始介紹如何通過各種算法，利用已知類別的模式樣本訓練出權向量W。（2）“感知器”：對一種分類學習機模型的稱呼，屬于有關機器學習的仿生學領域中的問題，由于無法實現非線性分類而下馬。但“賞罰概念（TheReward-PunishmentConcept）”今天仍在模式識別中起著很大的作用。（1）“訓練”：對于線性判別函數，當模式的維數知道時，判別函數的形式實際上也就定了下來，如：三維時已知兩個訓練模式集，分屬于和，任取權向量初始值W(1)，開始迭代。二、感器學習算法（“賞——罰”過程）1、用全部訓練模式集進行一輪迭代，計算的值。2、分三種情況，更新權向量的值：c為正的校正增量。（3.4-1）則分類器對第i個模式做了①錯誤分類，權向量校正為：為錯誤分類，有：若對的樣本乘以（-1），則（3.4-2）改寫為：（3.4-2）（3.4-3）②③若不是以上兩種情況，表明分類正確，權向量不變，即統一寫為：式中c為正的校正增量。（3.4-4）3、只要有一個樣本判別錯誤，則進行第二輪迭代，直至用全部模式進行訓練都獲得正確分類結果，迭代結束。感知器算法是一種賞罰過程：分類正確時，對權向量“賞”——這里用“不罰”，即權向量不變；分類錯誤時，對權向量“罰”——對其修改，向正確的方向轉換。三、收斂性收斂性：經過算法的有限次迭代運算后，求出了一個使所有樣本都能正確分類的W，則稱算法是收斂的。可以證明感知器算法是收斂的。收斂條件：模式類別線性可分。例：用感知器算法求出將圖示模式分為兩類的權向量解。解：將模式特征向量寫成增廣向量形式，將屬于的訓練樣本乘以（-1）：取c=1，。則迭代過程為：第一輪：第一輪迭代中有兩個≤0的情況（判別錯誤的情況），進行第二輪迭代。第二輪：第三輪：第四輪：該輪迭代的分類全部正確，故解向量相應的判別函數為：判別界面d(X)=0如圖示。當c、W(1)取其他值時，結果可能不一樣，所以感知器算法的解不是單值的。將兩個模式的分類推廣到多個模式分類的情況，采用3.2節中介紹的多類情況中的第三種方法，即：四、感知器算法用于多類情況若，則對于M類模式應存在M個判決函數：算法推導：設有M種模式類別：設其權向量初值為：一個屬于類的模式樣本X被送入分類器，則：1.計算出M個判決函數：②若第l個權向量使，則相應的權向量作調整，即：可以證明：只要該模式類別用情況三判別函數時是可分的，則該算法經過有限次迭代后收斂。，c為一正常數。①若則權向量不變；2.判別：采用多類情況3的方法時，應有：4.感知器算法用于多類情況若，則對于M類模式應存在M個判決函數：算法主要內容：設有M種模式類別：設其權向量初值為：第k次迭代時，一個屬于ωi類的模式樣本X

被送入分類器，計算所有判別函數訓練樣本為增廣向量形式，但不需要規范化處理。分二種情況修改權向量：②若第l個權向量使，則相應的權向量作調整，即：可以證明：只要模式類在情況3判別函數時是可分的，則經過有限次迭代后算法收斂。，c為正的校正增量例3.9設有三個線性可分的模式類，三類的訓練樣本分別為①若則權向量不變；現采用多類情況3的方式分類，試用感知器算法求出判別函數。解：增廣向量形式：注意，這里任一類的樣本都不能乘以（－1）。任取初始權向量；c=1第一次迭代：三個權向量都需要修改：，但且不成立，第二次迭代：，但且不成立，修改權向量：第三次迭代：修改為權向量。，但且不成立，以上進行的一輪迭代運算中，三個樣本都未正確分類，進行下一輪迭代。第四次迭代：……在第五、六、七迭代中，對所有三個樣本都已正確分類。權向量的解：判別函數：設函數f(Y)是向量的函數，則f(Y)的梯度定義為：§3.5梯度學習算法即：

梯度的方向是函數f(Y)在Y點增長最快的方向，梯度的模是f(Y)在增長最快的方向上的增長率。（增長率的最大值）、梯度概念(3.5-1)

梯度向量的最重要性質之一：指出函數f在其自變量增加時，最大增大率的方向。例：對一個二維向量，令，則在幾何上表示一個曲面，這個曲面被（常數）所截得的等高線，在平面上的投影是一條曲線L，不同的C值得到不同的等高線。由、平面所截的等高線在平面的投影為L1、L2。L1上A點的梯度方向與函數f(X)在點A的法線方向一致，是函數f(X)在點A增長最快的方向。若從高度C1到達C2，顯然，若以同樣的速率增長，沿梯度方向肯定是最快到達的。顯然：負梯度指出了最陡下降方向。——梯度算法的依據。二、梯度法設兩個線性可分的模式類ω1和ω2的樣本共N個，ω2類樣本乘(-1)。將兩類樣本分開的判決函數d(X)應滿足：梯度算法的目的仍然是求一個滿足上述條件的權向量，主導思想是將聯立不等式求解W的問題，轉換成求準則函數極小值的問題。——N個不等式準則函數的選取原則：具有唯一的最小值，并且這個最小值發生在W

tXi>0時。因此：尋找滿足WtXi>0的W的問題，變為尋找使J(W,X)達到極小值的W的問題。即通過求準則函數極小值求符合要求的權向量。基本思路：定義一個對錯誤分類敏感的準則函數J(W,X)，在J的梯度方向上對權向量進行修改。一般關系表示成從W(k)導出W(k+1)：其中c是正的比例因子。 (3.5-2)梯度法求解步驟：b)依次將所有樣本X代入準則函數J，對某個特定的X，J是W的函數，即J(W，X)=J(W)。求J對W的導數，代入當時的W(k)的值，求出。a)選擇初始權向量W(1)。c)按(3.5-2)式修改權向量。若對所有樣本均有，則W不再變化，算法收斂。例：選擇準則函數解：不妨簡單地設X=1（標量）。此時錯誤分類時：，對權向量校正。正確分類時：，對權向量不做修正。說明：隨著權向量W向理想值接近，準則函數關于W的導數(即這里的梯度）會越來越趨近于零，這意味著準則函數J越來越接近最小值。當最終時，J達到最小值，此時W不再改變，算法收斂。——將感知器算法中聯立不等式求解W的問題，轉換為求函數J極小值的問題。b)梯度算法是求解權向量的一般解法，算法的具體計算形式取決于準則函數J(W,X)的選擇，J(W,X)的形式不同，得到的具體算法不同。a)c)c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過頭，甚至引起發散。§3.6最小均（平）方誤差算法（LeastMeanSquareError,LMSE；亦稱Ho-Kashyap算法）上述的感知器算法和由梯度導出的固定增量算法或其他類似方法，只是當被分模式可分離時才收斂，在不可分的情況下，算法會來回擺動，始終不收斂。當一次次迭代而又不見收斂時，造成不收斂現象的原因分不清，有兩種可能：a)迭代過程本身收斂緩慢b)模式本身不可分對可分模式收斂。對于類別不可分的情況也能指出來。LMSE算法特點：、分類器的不等式方程兩類分類問題的解相當于求一組線性不等式的解。如果給出分別屬于、兩個模式的訓練樣本集，應滿足：若將的模式乘以（-1），則對全部模式都有：(3.6-1)設模式樣本為n維，兩類模式的訓練樣本總數為N個，將上式分開寫有：寫成矩陣形式為：令N×(n+1)維的長方矩陣為X（正體），則(3.6-1)式變為：(3.6-2)顯然式中：為零向量。感知器算法實際就是通過(3.6-2)不等式組求出W的。(3.6-2)二、LMSE算法（H-K算法）1、原理LMSE算法把對滿足的求解，改為滿足的求解。(3.6-3)∴兩式等價。定義準則函數：(3.6-4)為各分量均為正值的矢量。式中：①在方程組中，當行數>>列數時，通常無解，稱為矛盾方程組，一般求近似解。在模式識別中，通常訓練樣本數N總是大于模式的維數n，因此方程的個數（行數）>>模式向量的維數（列數），即方程組為矛盾方程組，通常無精確解存在，但可求最小二乘解W*，即，W*為近似解。說明：②LMSE算法的出發點：選擇一個準則函數，使得當J達到最小值時，可得到近似解（最小二乘解）。③LMSE算法的思路：轉化為轉化為④使J達到最小值的解W，就是矛盾方程組的最小二乘近似解，也稱最優近似解。“最小二乘”——最小:：使方程組兩邊誤差最小，也即使J最小。——二乘：括號的次數為2，乘了兩次；也即“最小平方（誤差算法）“最優近似解”——使方程組兩邊所有誤差之和最小（即最優）的解。矢量：準則函數的推導：從(3.6-3)和(3.6-4)式可看出：①當函數J達到最小值，等式有最優解。即又將問題轉化為求準則函數極小值的問題。②因為J有兩個變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。(3.6-3)(3.6-4)2、推導LMSE算法遞推公式與問題相關的兩個梯度：

②

1)求W的迭代式：使J對W求最小，有：③由③式可知：只要求出B，就可求出W。求遞推公式：得：令稱為X的偽逆，X為階長方陣，式中：為階。①2)求B的迭代式：利用梯度法中的(3.5-2)式有：②代入：令，定義#1④3)求W(k+1)的迭代式：將④代入③式有：#2式中：②=0設初值B(1)，須使其每一分量都為正值。……W(k+1)、B(k+1)互相獨立，均只與有關。故迭代式中也可先算B(k+1)，然后按來計算，即：……求出B、W后，再迭代出下一個，從而計算出新的B、W。總結LMSE算法迭代式：③#2④#1三、模式類別可分性的判別及算法的特點：（一）可分性判別②如果，這時隱含，有解。如繼續迭代，可使。③如果的所有分量為負數或零（但不是全部為零），停止迭代，無解。此時若繼續迭代下去，數據不再發生變化。

可以證明：當模式類線性可分，且校正系數c滿足時，該算法收斂，可求得解W。理論上不能證明該算法到底需要迭代多少步才能達到收斂，通常在每次迭代計算后檢查一下和誤差向量，從而可以判斷是否收斂。①如果或（即），有解。分以下幾種情況：關于③的說明：通過反證法可以證明：在線性可分情況下，算法進行過程中不會出現的分量全為負的情況；若出現的分量全為負，則說明模式類線性不可分。b)所有分量為非正，繼續迭代數據無變化的情況分析：③如果的所有分量為負數或零（但不是全部為零），停止迭代，無解。此時若繼續迭代下去，數據不再發生變化。或綜上所述：只有當中有大于零的分量時，才需要繼續迭代，一旦的全部分量只有0和負數，則立即停止。事實上，往往早在全部分量都達到非正值以前，就能看出其中有些分量向正值變化得極慢，可及早采取對策。（二）算法特點除了對可分模式是收斂的以外，對于線性不可分的模式，在算法迭代過程中就可明確的表示出來。例1：已知兩類模式訓練樣本：解：1）寫出增廣矩陣：2）求偽逆矩陣求逆矩陣：若，則是的代數余子式，注意兩者的行和列的標號互換。|A|——A的行列式A*——A的伴隨矩陣代數余子式定義：劃去aij所在的行和列的元素，余下元素構成的行列式做aij的余子式，記作Mij，將叫做元素aij的代數余子式。例：行列式:3）開始迭代：取和c=1.故W(1)就是解，即判斷函數為：圖示如下：例2：已知模式訓練樣本：2）求：解：1）增廣矩陣：3）迭代：取和c=1.全部分量為負，無解，停止迭代。為線性不可分模式。

可以看出：2）算法盡管略為復雜一些，但它提供了線性可分的測試特征，并且收斂速度也比前面的梯度法（包括感知器算法）要快一些。1）LMSE算法的明顯缺點是需要對矩陣求逆，好在一個分類問題，只要進行一次求逆。此外，當新的一行加入X中時（即新的模式樣本加入），逆矩陣有迭代算法。小結：1、感知器法、梯度法、最小平方誤差算法討論的分類算法都是通過模式樣本來確定判別函數的系數，所以要使一個分類器設計完善，必須采用有代表性的數據，訓練判別函數的權系數。它們能合理反映模式數據的總體。2、要獲得一個有較好判別性能的線性分類器，所需要的訓練樣本的數目的確定。用指標二分能力Ck來決定訓練樣本的數目：通常訓練樣本的數目不能低于Ck，選為Ck的10~20倍左右。二維：不能低于6個樣本，最好選在60~120個樣本之間。三維：不能低于8個樣本，最好選在80~160個樣本之間。k為模式維數如復習：LMSE算法1、算法過程①由已知類別的樣本寫出增廣矩陣X，求出，設B(1)、c初值，B(1)每一分量必須全為正值