張素文-第3章線性判別函數(shù)

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

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

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

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

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

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

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

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

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

②

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

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

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