判別函數(shù)及幾何分類法

判別函數(shù)及幾何分類法第1頁(yè)，共129頁(yè)，2023年，2月20日，星期一第3章判別函數(shù)及幾何分類法3.1判別函數(shù)3.2線性判別函數(shù)3.3廣義線性判別函數(shù)3.4線性判別函數(shù)的幾何性質(zhì)3.5感知器算法3.6梯度法3.7最小平方誤差算法3.8非線性判別函數(shù)第2頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.1判別函數(shù)聚類分析法（第七章）判決函數(shù)法幾何分類法[確定性事件分類]（第三章）概率分類法[隨機(jī)事件分類]（第二章）線性判決函數(shù)法統(tǒng)計(jì)決策方法非線性判決函數(shù)法復(fù)習(xí)與引申：模式識(shí)別統(tǒng)計(jì)第3頁(yè)，共129頁(yè)，2023年，2月20日，星期一若分屬于ω1，ω2的兩類模式可用一方程d(X)=0來(lái)劃分，那么稱d(X)為判別函數(shù)，或稱判決函數(shù)、決策函數(shù)。3.1判別函數(shù)(discriminantfunction)

直接用來(lái)對(duì)模式進(jìn)行分類的準(zhǔn)則函數(shù)。例：一個(gè)二維的兩類判別問(wèn)題，模式分布如圖示，這些分屬于ω1，ω2兩類的模式可用一直線方程d(X)=0來(lái)劃分。為坐標(biāo)變量，為方程參數(shù)。式中：圖3.2兩類二維模式的分布1．判別函數(shù)的定義第4頁(yè)，共129頁(yè)，2023年，2月20日，星期一若，則若，則類；若，則類；或拒絕將某一未知模式

X

代入：維數(shù)=3時(shí)：判別邊界為一平面。維數(shù)>3時(shí)：判別邊界為一超平面。第5頁(yè)，共129頁(yè)，2023年，2月20日，星期一d(X)表示的是一種分類的標(biāo)準(zhǔn)，它可以是1、2、3維的，也可以是更高維的。判別界面的正負(fù)側(cè)，是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的。2．判別函數(shù)正負(fù)值的確定圖3.3判別函數(shù)正負(fù)的確定第6頁(yè)，共129頁(yè)，2023年，2月20日，星期一1）判決函數(shù)d(X)的幾何性質(zhì)。它可以是線性的或非線性的函數(shù)，維數(shù)在特征提取時(shí)已經(jīng)確定。如：已知三維線性分類——判決函數(shù)的性質(zhì)就確定了判決函數(shù)的形式：3.確定判別函數(shù)的兩個(gè)因素例：非線性判決函數(shù)2）判決函數(shù)d(X)的系數(shù)。用所給的模式樣本確定。第7頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.2線性判別函數(shù)3.2.1線性判別函數(shù)的一般形式將二維模式推廣到n維，線性判別函數(shù)的一般形式為：(3-2)式中：增廣向量的形式：式中：為增廣權(quán)向量，為增廣模式向量。權(quán)向量第8頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.2.2線性判別函數(shù)的性質(zhì)1.兩類情況d(X)=0：不可判別情況，可以）對(duì)M個(gè)線性可分模式類，ω1，ω2，…ωM，有三種劃分方式：2.多類情況兩分法兩分法兩分法特例第9頁(yè)，共129頁(yè)，2023年，2月20日，星期一兩分法(1)多類情況1：用線性判別函數(shù)將屬于ωi類的模式與其余不屬于ωi類的模式分開(kāi)。將某個(gè)待分類模式X分別代入M個(gè)類的d

(X)中，若只有di(X)>0，其他d(X)均<0，則判為ωi類。識(shí)別分類時(shí)：第10頁(yè)，共129頁(yè)，2023年，2月20日，星期一

全部＜０不屬任何類

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+對(duì)某一模式區(qū)，di(X)>0的條件超過(guò)一個(gè)，或全部的di(X)<0，分類失效。相當(dāng)于不確定區(qū)(indefiniteregion，IR)。此法將M個(gè)多類問(wèn)題分成M個(gè)兩類問(wèn)題，識(shí)別每一類均需M個(gè)判別函數(shù)。識(shí)別出所有的M類仍是這M個(gè)函數(shù)。第11頁(yè)，共129頁(yè)，2023年，2月20日，星期一例3.1設(shè)有一個(gè)三類問(wèn)題，其判別式為：現(xiàn)有一模式，X=[7,5]T，試判定應(yīng)屬于哪類？并畫出三類模式的分布區(qū)域。解：將X=[7,5]T代入上三式，有：三個(gè)判別界面分別為：圖示如下：第12頁(yè)，共129頁(yè)，2023年，2月20日，星期一1

0-112x1x0)(2=Xd0)(3=Xd(10)=Xd44

步驟：a)畫出界面直線。b)判別界面正負(fù)側(cè)：找特殊點(diǎn)帶入。c)找交集。第13頁(yè)，共129頁(yè)，2023年，2月20日，星期一0)(3=Xd+—例3.2已知di(X)的位置和正負(fù)側(cè)，分析三類模式的分布區(qū)域?！?)(1=Xd+0)(2=Xd+—2w3w1w第14頁(yè)，共129頁(yè)，2023年，2月20日，星期一兩分法(2)多類情況2：一個(gè)判別界面只能分開(kāi)兩個(gè)類別，不能把其余所有的類別都分開(kāi)。判決函數(shù)為：。這里。在M類模式中，與i有關(guān)的M-1個(gè)判決函數(shù)全為正時(shí)，X∈ωi。其中若有一個(gè)為負(fù)，則為IR區(qū)。則類，而在判別類模式時(shí)不起作用。如：對(duì)一個(gè)三類問(wèn)題，如果，識(shí)別分類時(shí)：判別函數(shù)性質(zhì)：第15頁(yè)，共129頁(yè)，2023年，2月20日，星期一1w2w2x1x--003231>>dd001312>>dd002321>>dd3w+++-

d23(X)=0d12(X)=0d13(X)=0IR000231312?t?yü<><ddd第16頁(yè)，共129頁(yè)，2023年，2月20日，星期一與值無(wú)關(guān)。例3.3一個(gè)三類問(wèn)題，三個(gè)判決函數(shù)為：?jiǎn)柲Ｊ綄儆谀念?？解：?jì)算得可寫成：(4,3)x2x1d23(X)=0d12(X)=0d13(X)=05530第17頁(yè)，共129頁(yè)，2023年，2月20日，星期一1w2w2x1x--003231>>dd001312>>dd002321>>dd3w+++-

d23(X)=0d12(X)=0d13(X)=0IR000231312?t?yü<><ddd5530第18頁(yè)，共129頁(yè)，2023年，2月20日，星期一分類時(shí)：每分離出一類，需要與I有關(guān)的M-1個(gè)判決函數(shù)；要分開(kāi)M類模式，共需M(M-1)/2個(gè)判決函數(shù)。對(duì)三類問(wèn)題需要3(3-1)/2=3個(gè)判決函數(shù)。即：每次從M類中取出兩類的組合：例3.4已知dij(X)的位置和正負(fù)側(cè)，分析三類模式的分布區(qū)域。第19頁(yè)，共129頁(yè)，2023年，2月20日，星期一當(dāng)ωi

/ωj兩分法中的判別函數(shù)dij(X)，可以定義為時(shí)，那么di(X)>dj(X)就相當(dāng)于多類情況2中的dij(X)>0。兩分法特例(3)多類情況3：因此對(duì)具有判別函數(shù)的M類情況，判別函數(shù)性質(zhì)為：或：

第20頁(yè)，共129頁(yè)，2023年，2月20日，星期一識(shí)別分類時(shí)：判別界面需要做差值。對(duì)ωi類，應(yīng)滿足：

di>其他所有dj2313dddd>>01w2w2x1x()0)(21=-XdXd+++---()0)(31=-XdXd()0)(32=-XdXd3212dddd>>3121dddd>>3w第21頁(yè)，共129頁(yè)，2023年，2月20日，星期一②除邊界區(qū)外，沒(méi)有不確定區(qū)域。特點(diǎn)：①是第二種情況的特例。由于dij(X)=di

(X)－dj(X)，若在第三種情況下可分，則在第二種情況下也可分，但反過(guò)來(lái)不一定。2313dddd>>01w2w2x1x()0)(21=-XdXd++---()0)(31=-XdXd()0)(32=-XdXd3212dddd>>3121dddd>>3w③把M類情況分成了(M-1)個(gè)兩類問(wèn)題。并且類的判別界面全部與類的判別界面相鄰（向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外）。特別的定義第22頁(yè)，共129頁(yè)，2023年，2月20日，星期一例3.5一個(gè)三類模式（M=3）分類器，其判決函數(shù)為：試判斷X0=[1,1]T屬于哪一類，且分別給出三類的判決界面。解：①第23頁(yè)，共129頁(yè)，2023年，2月20日，星期一類的判決函數(shù)：②判決界面如圖所示。類的判決函數(shù)：類的判決函數(shù)：-()0)(21=-XdXd2313dddd>>0.5x2++--()0)(31=-XdXd()0)(32=-XdXd3212dddd>>3121dddd>>110.5w1w2w3x1+第24頁(yè)，共129頁(yè)，2023年，2月20日，星期一-O2x1x()0)(21=-XXdd+++--()0)(31=-XXdd()0)(32=-XXdd例3.6已知判決界面的位置和正負(fù)側(cè)，分析三類模式的分布區(qū)域。第25頁(yè)，共129頁(yè)，2023年，2月20日，星期一(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類模式的分布更為聚集，分法受到的限制條件少，故線性可分的可能性大。第26頁(yè)，共129頁(yè)，2023年，2月20日，星期一兩分法

全部＜０不屬任何類

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+若只有di(X)>0，其他d(X)均<0，則判為ωi

類第27頁(yè)，共129頁(yè)，2023年，2月20日，星期一兩分法:1w2w2x1x--003231>>dd001312>>dd002321>>dd3w+++-

d23(X)=0d12(X)=0d13(X)=0IR000231312?t?yü<><ddd第28頁(yè)，共129頁(yè)，2023年，2月20日，星期一兩分法特例定義2313dddd>>01w2w2x1x()0)(21=-XdXd+++---()0)(31=-XdXd()0)(32=-XdXd3212dddd>>3121dddd>>3w第29頁(yè)，共129頁(yè)，2023年，2月20日，星期一1．非線性多項(xiàng)式函數(shù)非線性判別函數(shù)的形式之一是非線性多項(xiàng)式函數(shù)。3.3廣義線性判別函數(shù)目的：對(duì)非線性邊界：通過(guò)某映射，把模式空間X變成X*，以便將X空間中非線性可分的模式集，變成在X*空間中線性可分的模式集。設(shè)一訓(xùn)練用模式集，{X}在模式空間X中線性不可分，非線性判別函數(shù)形式如下：(3-9)式中是模式X的單值實(shí)函數(shù)，。fi(X)取什么形式及d(X)取多少項(xiàng)，取決于非線性邊界的復(fù)雜程度。第30頁(yè)，共129頁(yè)，2023年，2月20日，星期一廣義形式的模式向量定義為：(3-10)這里X*空間的維數(shù)k高于X空間的維數(shù)n，(3-9)式可寫為上式是線性的。討論線性判別函數(shù)并不會(huì)失去一般性的意義。(3-11)隨著小樣本學(xué)習(xí)理論和支持向量機(jī)的迅速發(fā)展，廣義線性判別函數(shù)的“維數(shù)災(zāi)難”問(wèn)題在一定程度上找到了解決的辦法。非線性變換可能非常復(fù)雜。問(wèn)題：維數(shù)大大增加：維數(shù)災(zāi)難。第31頁(yè)，共129頁(yè)，2023年，2月20日，星期一例3.7假設(shè)X為二維模式向量，fi(X)選用二次多項(xiàng)式函數(shù)，原判別函數(shù)為定義：d(X)線性化為：即：廣義線性判別函數(shù)：第32頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.4線性判別函數(shù)的幾何性質(zhì)3.4.1模式空間與超平面模式空間：以n維模式向量X的n個(gè)分量為坐標(biāo)變量的歐氏空間。模式向量的表示：點(diǎn)、有向線段。線性分類：用d(X)進(jìn)行分類，相當(dāng)于用超平面d(X)=0把模式空間分成不同的決策區(qū)域。2.討論1.概念式中，，。設(shè)判別函數(shù)：超平面：第33頁(yè)，共129頁(yè)，2023年，2月20日，星期一(1)模式向量X1和X2在超平面上——W0是超平面的法向量，方向由超平面的負(fù)側(cè)指向正側(cè)。設(shè)超平面的單位法向量為U：第34頁(yè)，共129頁(yè)，2023年，2月20日，星期一(2)X不在超平面上將X向超平面投影得向量Xp，構(gòu)造向量R：r：X到超平面的垂直距離。有(r)——判別函數(shù)d(X)正比于點(diǎn)X到超平面的代數(shù)距離。第35頁(yè)，共129頁(yè)，2023年，2月20日，星期一X到超平面的距離：——點(diǎn)X到超平面的代數(shù)距離（帶正負(fù)號(hào)）正比于d(X)函數(shù)值。(3)X在原點(diǎn)得——超平面的位置由閾值權(quán)wn+1決定：wn+1>0時(shí)，原點(diǎn)在超平面的正側(cè)；wn+1<0時(shí)，原點(diǎn)在超平面負(fù)側(cè)；wn+1=0時(shí)，超平面通過(guò)原點(diǎn)。第36頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.4.2權(quán)空間與權(quán)向量解1.概念權(quán)空間：以的權(quán)系數(shù)為坐標(biāo)變量的（n+1）維歐氏空間增廣權(quán)向量的表示：點(diǎn)、有向線段。2.線性分類判別函數(shù)形式已定，只需確定權(quán)向量。類：X11，X12，…，X1p

類：X21，X22，…，X2q

設(shè)增廣樣本向量：使d(X)=0將ω1和ω2分開(kāi)，需滿足第37頁(yè)，共129頁(yè)，2023年，2月20日，星期一給ω2的q個(gè)增廣模式乘以（－1），統(tǒng)一為,其中——樣本的規(guī)范化過(guò)程。對(duì)每個(gè)已知的X，d(X)=0在權(quán)空間確定一個(gè)超平面，共(p+q)個(gè)。在權(quán)空間中尋找向量W使判別函數(shù)d(X)能把ω1類和ω2類分開(kāi)，就是尋找一個(gè)權(quán)向量，使得上式中的（p+q）個(gè)不等式同時(shí)成立,因此滿足條件的權(quán)向量必然在（p+q）個(gè)超平面的正側(cè)的交迭區(qū)域里(即W的解區(qū))。X：規(guī)范化增廣樣本向量。第38頁(yè)，共129頁(yè)，2023年，2月20日，星期一例：二維權(quán)空間，超平面的方程為：超平面：過(guò)原點(diǎn)的直線；陰影部分：解區(qū)。第39頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.4.3二分法二分法（Dichotomies）：用判別函數(shù)d(X)將給定的N個(gè)模式分成兩類的方法。是一種基本的分類方法。判別函數(shù)的不同分類能力可以通過(guò)二分法總數(shù)衡量。若不限制判別函數(shù)的形式，N個(gè)n維模式用判別函數(shù)分成兩類的二分法總數(shù)為2N。第40頁(yè)，共129頁(yè)，2023年，2月20日，星期一若限定用線性判別函數(shù)，并且樣本在模式空間是良好分布的，即在n維模式空間中沒(méi)有(n+1)個(gè)模式位于(n－1)維子空間中，可以證明，N個(gè)n維模式用線性判別函數(shù)分成兩類的方法總數(shù)，即線性二分法總數(shù)為或線性二分法概率：只要模式的個(gè)數(shù)N小于或等于增廣模式的維數(shù)（n+1），模式類總是線性可分的，第41頁(yè)，共129頁(yè)，2023年，2月20日，星期一例：4個(gè)良好分布的2維模式，若用線性判別函數(shù)分類線性二分法總數(shù)：線性二分法概率：圖3.14線性二分法的概率第42頁(yè)，共129頁(yè)，2023年，2月20日，星期一將λ=2時(shí)的N值定義為閾值N0，稱為二分法能力，即通過(guò)N0，可以對(duì)任意N個(gè)樣本的線性可分性進(jìn)行粗略估計(jì)。第43頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.5感知器算法1.概念理解訓(xùn)練：用已知類別的模式樣本指導(dǎo)機(jī)器對(duì)分類規(guī)則進(jìn)行反復(fù)修改，最終使分類結(jié)果與已知類別信息完全相同的過(guò)程。1）訓(xùn)練與學(xué)習(xí)學(xué)習(xí)：從分類器的角度講非監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)訓(xùn)練只要求出權(quán)向量，分類器的設(shè)計(jì)即告完成。本節(jié)開(kāi)始介紹如何通過(guò)各種算法，利用已知類別的模式樣本訓(xùn)練出權(quán)向量W。對(duì)線性判別函數(shù)，當(dāng)模式維數(shù)已知時(shí)，判別函數(shù)的形式實(shí)際上已經(jīng)確定，如：三維時(shí)第44頁(yè)，共129頁(yè)，2023年，2月20日，星期一3）感知器

對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼，屬于有關(guān)機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問(wèn)題，由于無(wú)法實(shí)現(xiàn)非線性分類而下馬。但“賞罰概念（reward-punishmentconcept）”得到廣泛應(yīng)用。2）確定性分類器處理確定可分情況的分類器。通過(guò)幾何方法將特征空間分解為對(duì)應(yīng)不同類的子空間，又稱為幾何分類器。2.感器算法（perceptionapproach）兩類線性可分的模式類：，設(shè)其中，，應(yīng)具有性質(zhì)第45頁(yè)，共129頁(yè)，2023年，2月20日，星期一對(duì)樣本進(jìn)行規(guī)范化處理，即ω2類樣本全部乘以(－1)，則有：感知器算法通過(guò)對(duì)已知類別的訓(xùn)練樣本集的學(xué)習(xí)，尋找一個(gè)滿足上式的權(quán)向量。感知器算法步驟：（1）選擇N個(gè)分屬于ω1和ω2類的模式樣本構(gòu)成訓(xùn)練樣本集{X1,…,XN}構(gòu)成增廣向量形式，并進(jìn)行規(guī)范化處理。任取權(quán)向量初始值W(1)，開(kāi)始迭代。迭代次數(shù)k=1。（2）用全部訓(xùn)練樣本進(jìn)行一輪迭代，計(jì)算WT(k)Xi的值，并修正權(quán)向量。分兩種情況，更新權(quán)向量的值：第46頁(yè)，共129頁(yè)，2023年，2月20日，星期一c：正的校正增量。分類器對(duì)第i個(gè)模式做了錯(cuò)誤分類，①權(quán)向量校正為：統(tǒng)一寫為：分類正確，權(quán)向量不變：②（3）分析分類結(jié)果：只要有一個(gè)錯(cuò)誤分類，回到（2），直至對(duì)所有樣本正確分類。分類正確時(shí)，對(duì)權(quán)向量“賞”——這里用“不罰”，即權(quán)向量不變；分類錯(cuò)誤時(shí)，對(duì)權(quán)向量“罰”——對(duì)其修改，向正確的方向轉(zhuǎn)換。感知器算法是一種賞罰過(guò)程：第47頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.收斂性收斂性：經(jīng)過(guò)算法的有限次迭代運(yùn)算后，求出了一個(gè)使所有樣本都能正確分類的W，則稱算法是收斂的?？梢宰C明感知器算法是收斂的。收斂條件：模式類別線性可分。例3.8已知兩類訓(xùn)練樣本解：所有樣本寫成增廣向量形式；進(jìn)行規(guī)范化處理，屬于ω2的樣本乘以(－1)。用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù)。第48頁(yè)，共129頁(yè)，2023年，2月20日，星期一任取W(1)=0，取c=1，迭代過(guò)程為：第一輪：有兩個(gè)WT(k)Xi≤0的情況（錯(cuò)判），進(jìn)行第二輪迭代。第49頁(yè)，共129頁(yè)，2023年，2月20日，星期一第二輪：第三輪：第四輪：第50頁(yè)，共129頁(yè)，2023年，2月20日，星期一該輪迭代的分類結(jié)果全部正確，故解向量相應(yīng)的判別函數(shù)為：當(dāng)c、W(1)取其他值時(shí)，結(jié)果可能不一樣，所以感知器算法的解不是單值的。判別界面d(X)=0如圖示。第51頁(yè)，共129頁(yè)，2023年，2月20日，星期一采用多類情況3的方法時(shí)，應(yīng)有：4.感知器算法用于多類情況若，則對(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)向量：第52頁(yè)，共129頁(yè)，2023年，2月20日，星期一②若第l個(gè)權(quán)向量使，則相應(yīng)的權(quán)向量作調(diào)整，即：可以證明：只要模式類在情況3判別函數(shù)時(shí)是可分的，則經(jīng)過(guò)有限次迭代后算法收斂。，c為正的校正增量例3.9設(shè)有三個(gè)線性可分的模式類，三類的訓(xùn)練樣本分別為①若則權(quán)向量不變；現(xiàn)采用多類情況3的方式分類，試用感知器算法求出判別函數(shù)。第53頁(yè)，共129頁(yè)，2023年，2月20日，星期一解：增廣向量形式：注意，這里任一類的樣本都不能乘以（－1）。任取初始權(quán)向量；c=1第一次迭代：三個(gè)權(quán)向量都需要修改：，但且不成立，第54頁(yè)，共129頁(yè)，2023年，2月20日，星期一第二次迭代：，但且不成立，修改權(quán)向量：第三次迭代：修改為權(quán)向量。，但且不成立，以上進(jìn)行的一輪迭代運(yùn)算中，三個(gè)樣本都未正確分類，進(jìn)行下一輪迭代。第55頁(yè)，共129頁(yè)，2023年，2月20日，星期一第四次迭代：……在第五、六、七迭代中，對(duì)所有三個(gè)樣本都已正確分類。權(quán)向量的解：判別函數(shù)：第56頁(yè)，共129頁(yè)，2023年，2月20日，星期一設(shè)函數(shù)f(Y)是向量的函數(shù)，則f(Y)的梯度定義為：3.6梯度法梯度的方向是函數(shù)f(Y)在Y點(diǎn)增長(zhǎng)最快的方向，梯度的模是f(Y)在增長(zhǎng)最快的方向上的增長(zhǎng)率(增長(zhǎng)率最大值)。1.梯度概念梯度向量的最重要性質(zhì)之一：指出函數(shù)f在其自變量增加時(shí)，增長(zhǎng)最快的方向。3.6.1梯度法基本原理顯然：負(fù)梯度指出了最陡下降方向?！荻人惴ǖ囊罁?jù)。即：第57頁(yè)，共129頁(yè)，2023年，2月20日，星期一2.梯度算法設(shè)兩個(gè)線性可分的模式類ω1和ω2的樣本共N個(gè)，ω2類樣本乘(-1)。將兩類樣本分開(kāi)的判決函數(shù)d(X)應(yīng)滿足：梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量，主導(dǎo)思想是將聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的問(wèn)題?！狽個(gè)不等式準(zhǔn)則函數(shù)的選取原則：具有唯一的最小值，并且這個(gè)最小值發(fā)生在W

TXi>0時(shí)。用負(fù)梯度向量的值對(duì)權(quán)向量W進(jìn)行修正，實(shí)現(xiàn)使準(zhǔn)則函數(shù)達(dá)到極小值的目的。第58頁(yè)，共129頁(yè)，2023年，2月20日，星期一基本思路：定義一個(gè)對(duì)錯(cuò)誤分類敏感的準(zhǔn)則函數(shù)J(W,X)，在J的梯度方向上對(duì)權(quán)向量進(jìn)行修改。一般關(guān)系表示成從W(k)導(dǎo)出W(k+1)：其中c是正的比例因子。 梯度法求解步驟：（1）將樣本寫成規(guī)范化增廣向量形式，選擇準(zhǔn)則函數(shù)，設(shè)置初始權(quán)向量W(1)，括號(hào)內(nèi)為迭代次數(shù)k=1。第59頁(yè)，共129頁(yè)，2023年，2月20日，星期一權(quán)向量修正為：迭代次數(shù)k加1，輸入下一個(gè)訓(xùn)練樣本，計(jì)算新的權(quán)向量，直至對(duì)全部訓(xùn)練樣本完成一輪迭代。（3）在一輪迭代中，如果有一個(gè)樣本使，回到(2)進(jìn)行下一輪迭代。否則，W不再變化，算法收斂。（2）依次輸入訓(xùn)練樣本X。設(shè)第k次迭代時(shí)輸入樣本為Xi，此時(shí)已有權(quán)向量W(k)，求：第60頁(yè)，共129頁(yè)，2023年，2月20日，星期一例3.10

選擇準(zhǔn)則函數(shù)，，簡(jiǎn)單地考慮X為一維增廣模式的情況X=1，此時(shí)W=w，兩者均為標(biāo)量，錯(cuò)誤分類時(shí)：，對(duì)權(quán)向量校正。正確分類時(shí)：，對(duì)權(quán)向量不做修正。第61頁(yè)，共129頁(yè)，2023年，2月20日，星期一說(shuō)明：隨著權(quán)向量W向理想值接近，準(zhǔn)則函數(shù)關(guān)于W的導(dǎo)數(shù)()越來(lái)越趨近于零，這意味著準(zhǔn)則函數(shù)J越來(lái)越接近最小值。當(dāng)最終時(shí)，J達(dá)到最小值，此時(shí)W不再改變，算法收斂。——將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題。c)梯度算法是求解權(quán)向量的一般解法，算法的具體計(jì)算形式取決于準(zhǔn)則函數(shù)J(W,X)的選擇，J(W,X)的形式不同，得到的具體算法不同。a)b)c值的選擇很重要，如c值太小，收斂太慢；但若太大，搜索又可能過(guò)頭，甚至引起發(fā)散。第62頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.6.2固定增量法準(zhǔn)則函數(shù)：求W(k)的遞推公式：1.求J的梯度方法：函數(shù)對(duì)向量求導(dǎo)=函數(shù)對(duì)向量的分量求導(dǎo)，即該準(zhǔn)則函數(shù)有唯一最小值“0”，且發(fā)生在的時(shí)候。設(shè)，第63頁(yè)，共129頁(yè)，2023年，2月20日，星期一部分：首先求另：矩陣論中有第64頁(yè)，共129頁(yè)，2023年，2月20日，星期一其中②由①的結(jié)論有：第65頁(yè)，共129頁(yè)，2023年，2月20日，星期一2.求W(k+1)將代入得：第66頁(yè)，共129頁(yè)，2023年，2月20日，星期一由此可以看出，感知器算法是梯度法的特例。即：梯度法是將感知器算法中聯(lián)立不等式求解W的問(wèn)題，轉(zhuǎn)換為求函數(shù)J極小值的問(wèn)題，將原來(lái)有多個(gè)解的情況，變成求最優(yōu)解的情況。上式即為固定增量算法，與感知器算法形式完全相同。即：只要模式類是線性可分的，算法就會(huì)給出解。第67頁(yè)，共129頁(yè)，2023年，2月20日，星期一線性分類器設(shè)計(jì)步驟線性分類器設(shè)計(jì)任務(wù)：給定樣本集K，確定線性判別函數(shù)g(x)=wTx的各項(xiàng)系數(shù)w。步驟：抽取類別標(biāo)志明確的樣本集合K={x1,x2,…,xN}作為訓(xùn)練樣本集。確定一準(zhǔn)則函數(shù)J(K,w)，其值反映分類器的性能，其極值解對(duì)應(yīng)于“最好”決策。用最優(yōu)化技術(shù)求準(zhǔn)則函數(shù)J的極值解w*，從而確定判別函數(shù)，完成分類器設(shè)計(jì)。對(duì)于未知樣本x，計(jì)算g(x)，判斷其類別。第68頁(yè)，共129頁(yè)，2023年，2月20日，星期一4.2Fisher線性判別線性判別函數(shù)y=g(x)=wTx:樣本向量x各分量的線性加權(quán)樣本向量x與權(quán)向量w的向量點(diǎn)積如果||w||=1，則視作向量x在向量w上的投影Fisher準(zhǔn)則的基本原理：找到一個(gè)最合適的投影方向，使兩類樣本在該方向上投影之間的距離盡可能遠(yuǎn)，而每一類樣本的投影盡可能緊湊，從而使分類效果為最佳。第69頁(yè)，共129頁(yè)，2023年，2月20日，星期一Fisher線性判別圖例Fisher判別x1x2w1H:g=0w2Fisher準(zhǔn)則的描述：用投影后數(shù)據(jù)的統(tǒng)計(jì)性質(zhì)

—均值和離散度的函數(shù)作為判別優(yōu)劣的標(biāo)準(zhǔn)。第70頁(yè)，共129頁(yè)，2023年，2月20日，星期一d維空間樣本分布的描述量Fisher判別各類樣本均值向量mi樣本類內(nèi)離散度矩陣Si與總類內(nèi)離散度矩陣Sw

樣本類間離散度矩陣Sb：離散度矩陣在形式上與協(xié)方差矩陣很相似，但協(xié)方差矩陣是一種期望值，而離散矩陣只是表示有限個(gè)樣本在空間分布的離散程度第71頁(yè)，共129頁(yè)，2023年，2月20日，星期一一維Y空間樣本分布的描述量Fisher判別各類樣本均值樣本類內(nèi)離散度和總類內(nèi)離散度樣本類間離散度

以上定義描述d維空間樣本點(diǎn)到一向量投影的分散情況，因此也就是對(duì)某向量w的投影在w上的分布。樣本離散度的定義與隨機(jī)變量方差相類似第72頁(yè)，共129頁(yè)，2023年，2月20日，星期一Fisher準(zhǔn)則函數(shù)定義的原則為，希望投影后，在一維空間中樣本類別區(qū)分清晰，即兩類距離越大越好，也就是類間離散度越大越好；各類樣本內(nèi)部密集，即類內(nèi)離散度越小越好，根據(jù)上述準(zhǔn)則，構(gòu)造Fisher準(zhǔn)則函數(shù)。第73頁(yè)，共129頁(yè)，2023年，2月20日，星期一樣本與其投影統(tǒng)計(jì)量間的關(guān)系Fisher判別第74頁(yè)，共129頁(yè)，2023年，2月20日，星期一類內(nèi)離散度第75頁(yè)，共129頁(yè)，2023年，2月20日，星期一Fisher準(zhǔn)則函數(shù)Fisher判別評(píng)價(jià)投影方向w的原則，使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開(kāi)，類內(nèi)盡可能密集的要求Fisher準(zhǔn)則函數(shù)的定義：Fisher最佳投影方向的求解第76頁(yè)，共129頁(yè)，2023年，2月20日，星期一Fisher最佳投影方向的求解Fisher判別采用拉格朗日乘子算法解決

m1-m2是一向量，對(duì)與(m1-m2)平行的向量投影可使兩均值點(diǎn)的距離最遠(yuǎn)。但是如從使類間分得較開(kāi)，同時(shí)又使類內(nèi)密集程度較高這樣一個(gè)綜合指標(biāo)來(lái)看，則需根據(jù)兩類樣本的分布離散程度對(duì)投影方向作相應(yīng)的調(diào)整，這就體現(xiàn)在對(duì)m1-m2向量按Sw-1作一線性變換，從而使Fisher準(zhǔn)則函數(shù)達(dá)到極值點(diǎn)第77頁(yè)，共129頁(yè)，2023年，2月20日，星期一判別函數(shù)的確定前面討論了使Fisher準(zhǔn)則函數(shù)極大的d維向量w*的計(jì)算方法，判別函數(shù)中的另一項(xiàng)w0（閾值）可采用以下幾種方法確定：

分類規(guī)則:Fisher判別第78頁(yè)，共129頁(yè)，2023年，2月20日，星期一Fisher公式的推導(dǎo)Fisher判別第79頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.7最小平方誤差算法（leastmeansquareerror,LMSE；亦稱Ho-Kashyap算法）上述的感知器算法、梯度算法、固定增量算法或其他類似方法，只有當(dāng)模式類可分離時(shí)才收斂，在不可分的情況下，算法會(huì)來(lái)回?cái)[動(dòng)，始終不收斂。當(dāng)一次次迭代而又不見(jiàn)收斂時(shí)，造成不收斂現(xiàn)象的原因分不清，有兩種可能：a)迭代過(guò)程本身收斂緩慢b)模式本身不可分對(duì)可分模式收斂。對(duì)于類別不可分的情況也能指出來(lái)。LMSE算法特點(diǎn)：第80頁(yè)，共129頁(yè)，2023年，2月20日，星期一1.分類器的不等式方程兩類分類問(wèn)題的解相當(dāng)于求一組線性不等式的解。如果給出分屬于，兩個(gè)模式類的訓(xùn)練樣本集，應(yīng)滿足：其中，Xi是規(guī)范化增廣樣本向量，。上式分開(kāi)寫為：第81頁(yè)，共129頁(yè)，2023年，2月20日，星期一寫成矩陣形式為：令N×(n+1)的長(zhǎng)方矩陣為X，則,變?yōu)椋旱?2頁(yè)，共129頁(yè)，2023年，2月20日，星期一式中：0為零向量感知器算法是通過(guò)解不等式組，求出W。第83頁(yè)，共129頁(yè)，2023年，2月20日，星期一2.LMSE算法1)原理的求解。式中：∴兩式等價(jià)。為各分量均為較小正值的矢量。LMSE算法把對(duì)滿足XW>0的求解，改為滿足①在方程組系數(shù)矩陣中當(dāng)行數(shù)>>列數(shù)時(shí)，通常無(wú)解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù)N總是大于模式的維數(shù)n，因此方程的個(gè)數(shù)(行數(shù))>>模式向量的維數(shù)(列數(shù))，是矛盾方程組，只能求近似解W*，即說(shuō)明：第84頁(yè)，共129頁(yè)，2023年，2月20日，星期一②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，乘了兩次最小平方（誤差算法）第85頁(yè)，共129頁(yè)，2023年，2月20日，星期一考察向量(XW－B)有：第86頁(yè)，共129頁(yè)，2023年，2月20日，星期一可以看出：①當(dāng)函數(shù)J達(dá)到最小值，等式XW=B有最優(yōu)解。即又將問(wèn)題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問(wèn)題。②因?yàn)镴有兩個(gè)變量W和B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。XW=B的近似解也稱“最優(yōu)近似解”：——使方程組兩邊所有誤差之和最?。醋顑?yōu)）的解。準(zhǔn)則函數(shù)：第87頁(yè)，共129頁(yè)，2023年，2月20日，星期一使J對(duì)W求最小，令，得：2)推導(dǎo)LMSE算法遞推公式與問(wèn)題相關(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)第88頁(yè)，共129頁(yè)，2023年，2月20日，星期一(2)求B(k+1)的迭代式(3-46)代入，得令，定義(3-49)(3-50)(3-46)利用梯度算法公式有：第89頁(yè)，共129頁(yè)，2023年，2月20日，星期一(3)求W(k+1)的迭代式將(3-50)代入(3-47)式W=X#B有：=0(3-49)(3-50)第90頁(yè)，共129頁(yè)，2023年，2月20日，星期一總結(jié)：設(shè)初值B(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù)。……W(k+1)、B(k+1)互相獨(dú)立，先后次序無(wú)關(guān)?！蟪鯞，W后，再迭代出下一個(gè)e，從而計(jì)算出新的B，

W?；蛄硪凰惴ǎ合人鉈(k+1)，再算W(k+1)。第91頁(yè)，共129頁(yè)，2023年，2月20日，星期一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，有解。分以下幾種情況：第92頁(yè)，共129頁(yè)，2023年，2月20日，星期一情況③分析：e(k)<0第93頁(yè)，共129頁(yè)，2023年，2月20日，星期一綜上所述：只有當(dāng)e(k)中有大于零的分量時(shí)，才需要繼續(xù)迭代，一旦e(k)的全部分量只有0和負(fù)數(shù)，則立即停止。事實(shí)上，往往早在e(k)全部分量都達(dá)到非正值以前，就能看出其中有些分量向正值變化得極慢，可及早采取對(duì)策。通過(guò)反證法可以證明：在線性可分情況下，算法進(jìn)行過(guò)程中不會(huì)出現(xiàn)e(k)的分量全為負(fù)的情況；若出現(xiàn)e(k)的分量全為負(fù)，則說(shuō)明模式類線性不可分。4)LMSE算法描述(1)根據(jù)N個(gè)分屬于兩類的樣本，寫出規(guī)范化增廣樣本矩陣X。(2)求X的偽逆矩陣。第94頁(yè)，共129頁(yè)，2023年，2月20日，星期一(3)設(shè)置初值c和B(1)，c為正的校正增量，B(1)的各分量大于零，迭代次數(shù)k=1。開(kāi)始迭代：計(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)。第95頁(yè)，共129頁(yè)，2023年，2月20日，星期一(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ì)算。第96頁(yè)，共129頁(yè)，2023年，2月20日，星期一例3.11已知兩類模式訓(xùn)練樣本：試用LMSE算法求解權(quán)向量。解：(1)寫出規(guī)范化增廣樣本矩陣：第97頁(yè)，共129頁(yè)，2023年，2月20日，星期一

Aij是aij的代數(shù)余子式，注意兩者的行和列的標(biāo)號(hào)互換。(2)求偽逆矩陣求逆矩陣：若，則|A|——A的行列式A*——A的伴隨矩陣第98頁(yè)，共129頁(yè)，2023年，2月20日，星期一劃去aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作Mij，將叫做元素aij的代數(shù)余子式。例：代數(shù)余子式定義：行列式:第99頁(yè)，共129頁(yè)，2023年，2月20日，星期一(3)取和c=1開(kāi)始迭代：解為W(1)，判斷函數(shù)為：第100頁(yè)，共129頁(yè)，2023年，2月20日，星期一圖示如下：第101頁(yè)，共129頁(yè)，2023年，2月20日，星期一例3.12已知模式訓(xùn)練樣本：，(2)求：解：(1)規(guī)范化增廣樣本矩陣：(3)取和c=1，迭代：用LMSE算法求解權(quán)向量。第102頁(yè)，共129頁(yè)，2023年，2月20日，星期一

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

第103頁(yè)，共129頁(yè)，2023年，2月20日，星期一小結(jié)：(1)感知器法、梯度法、最小平方誤差算法討論的分類算法都是通過(guò)模式樣本來(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ù)如第104頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.8非線性判別函數(shù)3.8.1分段線性判別函數(shù)線性判別函數(shù)的特點(diǎn)：形式簡(jiǎn)單，容易學(xué)習(xí)；用于線性可分的模式類。非線性判別函數(shù)：用于線性不可分情況。分段線性、超曲面。特點(diǎn)基本組成為超平面。*相對(duì)簡(jiǎn)單；*能逼近各種形狀的超曲面。第105頁(yè)，共129頁(yè)，2023年，2月20日，星期一1．一般分段線性判別函數(shù)設(shè)有M類模式，將ωi類（i=1,2,…,M）劃分為li個(gè)子類：其中第n個(gè)子類的判別函數(shù)：ωi類的判別函數(shù)定義為：M類的判決規(guī)則：若，則用各類判別函數(shù)進(jìn)行分類判決實(shí)際是用各類選出的子類判別函數(shù)進(jìn)行判決判別面由各子類的判別函數(shù)決定第106頁(yè)，共129頁(yè)，2023年，2月20日，星期一若ωi類的第n個(gè)子類和ωj類的第m個(gè)子類相鄰，判別界面方程為：子類之間的判別界面組成各類之間的判別界面類間判別界面分段線性第107頁(yè)，共129頁(yè)，2023年，2月20日，星期一2．基于距離的分段線性判別函數(shù)設(shè)ω1類均值向量：ω2類均值向量：N1，N2：兩類樣本數(shù)。任一模式X到M1和M2的歐氏距離平方：判決規(guī)則：若，則若，則判別界面方程：1）最小距離分類器第108頁(yè)，共129頁(yè)，2023年，2月20日，星期一化簡(jiǎn)得：——X的線性方程，確定一個(gè)超平面?！钚【嚯x分類器第109頁(yè)，共129頁(yè)，2023年，2月20日，星期一2）分段線性距離分類器設(shè)：M類模式，其中ωi類劃分為li個(gè)子類，第n個(gè)子類的均值向量為。每個(gè)子類的判別函數(shù)：每類的判別函數(shù)：判決規(guī)則：若則第110頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.8.2分段線性判別函數(shù)的學(xué)習(xí)方法1．已知子類劃分時(shí)的學(xué)習(xí)方法*每個(gè)子類看成獨(dú)立的類；*在一類范圍內(nèi)根據(jù)多類情況3，學(xué)習(xí)各子類判別函數(shù)；*繼而得到各類判別函數(shù)。2．已知子類數(shù)目時(shí)的學(xué)習(xí)方法用類似于固定增量算法的錯(cuò)誤修正算法學(xué)習(xí)分段線性判別函數(shù)3．未知子類數(shù)目時(shí)的學(xué)習(xí)方法樹(shù)狀分段線性分類器第111頁(yè)，共129頁(yè)，2023年，2月20日，星期一樹(shù)狀分段線性分類器判別函數(shù)的學(xué)習(xí)及分類過(guò)程第112頁(yè)，共129頁(yè)，2023年，2月20日，星期一暫停點(diǎn)：，；：，第113頁(yè)，共129頁(yè)，2023年，2月20日，星期一3.8.3勢(shì)函數(shù)法1.勢(shì)函數(shù)概念劃分屬于ω1和ω2類模式樣本：樣本是模式空間中的點(diǎn)，將每個(gè)點(diǎn)比擬為點(diǎn)能源，在點(diǎn)上勢(shì)能達(dá)到峰值，隨著與該點(diǎn)距離的增大，勢(shì)能分布迅速減小。

ω1類樣本勢(shì)能為正——?jiǎng)菽芊e累形成“高地”；

ω2類樣本勢(shì)能×(-1)——?jiǎng)菽芊e累形成“凹地”；在兩類電勢(shì)分布之間，選擇合適的等勢(shì)面（如零等勢(shì)面），即可認(rèn)為是判別界面了。借用點(diǎn)能源的勢(shì)能概念解決模式分類問(wèn)題。第114頁(yè)，共129頁(yè)，2023年，2月20日，星期一一個(gè)樣本xk的勢(shì)能分布用勢(shì)函數(shù)K(x,xk)表示積累勢(shì)函數(shù)一維情況示例第115頁(yè)，共129頁(yè)，2023年，2月20日，星期一2.勢(shì)函數(shù)法判別函數(shù)的產(chǎn)生依次輸入樣本，利用勢(shì)函數(shù)逐步積累勢(shì)能的過(guò)程。