模式識別原理

模式識別原理第1頁，課件共47頁，創(chuàng)作于2023年2月第三章判別函數(shù)3.1線性判別函數(shù)3.2廣義線性判別函數(shù)3.3分段線性判別函數(shù)3.4模式空間和權(quán)空間3.5感知器算法3.6采用感知器算法的多類模式的分類3.7勢函數(shù)法—一種確定性的非線性分類算法第2頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.1用判別函數(shù)分類的概念模式識別系統(tǒng)的主要作用判別各個模式所屬的類別對一個兩類問題的判別，就是將模式x劃分成ω1和ω2兩類。第3頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.1用判別函數(shù)分類的概念[描述：兩類問題的判別函數(shù)]第4頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.1用判別函數(shù)分類的概念用判別函數(shù)進行模式分類依賴的兩個因素（1）判別函數(shù)的幾何性質(zhì)：線性的和非線性的函數(shù)。線性的是一條直線；非線性的可以是曲線、折線等；線性判別函數(shù)建立起來比較簡單（實際應用較多）；非線性判別函數(shù)建立起來比較復雜。（2）判別函數(shù)的系數(shù)：判別函數(shù)的形式確定后，主要就是確定判別函數(shù)的系數(shù)問題。只要被研究的模式是可分的，就能用給定的模式樣本集來確定判別函數(shù)的系數(shù)。第5頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.2線性判別函數(shù)[n維線性判別函數(shù)的一般形式]權(quán)向量增廣模式向量增廣權(quán)向量分類問題[兩類情況：判別函數(shù)d(x)]多類情況：設模式可分成ω1,ω2,…,ωM共M類，則有三種劃分方法多類情況1多類情況2多類情況3第6頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.2線性判別函數(shù)分類問題[多類情況1][判別函數(shù)][圖例][例子]第7頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.2線性判別函數(shù)分類問題[多類情況2][判別函數(shù)][圖例][例子]第8頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.2線性判別函數(shù)分類問題[多類情況3][判別函數(shù)][圖例][例子]第9頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.2線性判別函數(shù)線性可分模式分類如可用任一個線性函數(shù)來劃分，則這些模式就稱為線性可分的，否則就是非線性可分的。一旦線性函數(shù)的系數(shù)wk被確定，這些函數(shù)就可用作模式分類的基礎。第10頁，課件共47頁，創(chuàng)作于2023年2月3.1線性判別函數(shù)3.1.2線性判別函數(shù)多類情況1和多類情況2的比較對于M類模式的分類，多類情況1需要M個判別函數(shù)，而多類情況2需要M*(M-1)/2個判別函數(shù)，當M較大時，后者需要更多的判別式（這是多類情況2的一個缺點）。采用多類情況1時，每一個判別函數(shù)都要把一種類別的模式與其余M-1種類別的模式分開，而不是將一種類別的模式僅于另一種類別的模式分開。由于一種模式的分布要比M-1種模式的分布更為聚集，因此多類情況2對模式是線性可分的可能性比多類情況1更大一些（這是多類情況2的一個優(yōu)點）。第11頁，課件共47頁，創(chuàng)作于2023年2月作業(yè)（1）在一個10類的模式識別問題中，有3類單獨滿足多類情況1，其余的類別滿足多類情況2。問該模式識別問題所需判別函數(shù)的最少數(shù)目是多少？第12頁，課件共47頁，創(chuàng)作于2023年2月作業(yè)（2）一個三類問題，其判別函數(shù)如下：

d1(x)=-x1,d2(x)=x1+x2-1,d3(x)=x1-x2-1設這些函數(shù)是在多類情況1條件下確定的，繪出其判別界面和每一個模式類別的區(qū)域。設為多類情況2，并使：d12(x)=d1(x),d13(x)=d2(x),d23(x)=d3(x)。繪出其判別界面和多類情況2的區(qū)域。設d1(x),d2(x)和d3(x)是在多類情況3的條件下確定的，繪出其判別界面和每類的區(qū)域。第13頁，課件共47頁，創(chuàng)作于2023年2月3.2廣義線性判別函數(shù)出發(fā)點線性判別函數(shù)簡單，容易實現(xiàn)；非線性判別函數(shù)復雜，不容易實現(xiàn)；若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù)，則有利于模式分類的實現(xiàn)。第14頁，課件共47頁，創(chuàng)作于2023年2月3.2廣義線性判別函數(shù)基本思想 設有一個訓練用的模式集{x}，在模式空間x中線性不可分，但在模式空間x*中線性可分，其中x*的各個分量是x的單值實函數(shù)，x*的維數(shù)k高于x的維數(shù)n，即若取

x*=(f1(x),f2(x),….,fk(x)),k>n

則分類界面在x*中是線性的，在x中是非線性的，此時只要將模式x進行非線性變換，使之變換后得到維數(shù)更高的模式x*，就可以用線性判別函數(shù)來進行分類。[描述]第15頁，課件共47頁，創(chuàng)作于2023年2月3.2廣義線性判別函數(shù)廣義線性判別函數(shù)的意義[線性的判別函數(shù)][fi(x)選用二次多項式函數(shù)][x是二維的情況][x是n維的情況][fi(x)選用r次多項式函數(shù)，x是n維的情況][例子][d(x)的總項數(shù)]說明d(x)的項數(shù)隨r和n的增加會迅速增大，即使原來模式x的維數(shù)不高，若采用次數(shù)r較高的多項式來變換，也會使變換后的模式x*的維數(shù)很高，給分類帶來很大困難。實際情況可只取r=2，或只選多項式的一部分，例如r=2時只取二次項，略去一次項，以減少x*的維數(shù)。第16頁，課件共47頁，創(chuàng)作于2023年2月3.2廣義線性判別函數(shù)[例子：一維樣本空間-〉二維樣本空間]第17頁，課件共47頁，創(chuàng)作于2023年2月3.3分段線性判別函數(shù)出發(fā)點線性判別函數(shù)在進行分類決策時是最簡單有效的，但在實際應用中，常常會出現(xiàn)不能用線性判別函數(shù)直接進行分類的情況。采用廣義線性判別函數(shù)的概念，可以通過增加維數(shù)來得到線性判別，但維數(shù)的大量增加會使在低維空間里在解析和計算上行得通的方法在高維空間遇到困難，增加計算的復雜性。引入分段線性判別函數(shù)的判別過程，它比一般的線性判別函數(shù)的錯誤率小，但又比非線性判別函數(shù)簡單。第18頁，課件共47頁，創(chuàng)作于2023年2月3.3分段線性判別函數(shù)圖例：用判別函數(shù)分類可用一個二次判別函數(shù)來分類也可用一個分段線性判別函數(shù)來逼近這個二次曲線第19頁，課件共47頁，創(chuàng)作于2023年2月3.3分段線性判別函數(shù)分段線性判別函數(shù)的設計采用最小距離分類的方法[最小距離分類]第20頁，課件共47頁，創(chuàng)作于2023年2月3.3分段線性判別函數(shù)圖例：分段線性分類設計第21頁，課件共47頁，創(chuàng)作于2023年2月3.4模式空間和權(quán)空間[分類描述]模式空間對一個線性方程w1x1+w2x2+w3x3=0，它在三維空間(x1x2x3)中是一個平面方程式，w=(w1w2w3)T是方程的系數(shù)。把w向量作為該平面的法線向量，則該線性方程決定的平面通過原點且與w垂直。第22頁，課件共47頁，創(chuàng)作于2023年2月3.4模式空間和權(quán)空間模式空間若x是二維的增廣向量，此時x3=1，則在非增廣的模式空間中即為{x1,x2}二維坐標，判別函數(shù)是下列聯(lián)立方程的解

w1x1+w2x2+w3=0 x3=1

即為這兩個平面相交的直線AB此時，w=(w1w2)T為非增廣的權(quán)向量，它與直線AB垂直；AB將平面分為正、負兩側(cè)，w離開直線的一側(cè)為正，w射向直線的一側(cè)為負。第23頁，課件共47頁，創(chuàng)作于2023年2月3.4模式空間和權(quán)空間模式空間增廣向量決定的平面非增廣向量決定的直線第24頁，課件共47頁，創(chuàng)作于2023年2月3.4模式空間和權(quán)空間權(quán)空間若將方程x1w1+x2w2+w3=0繪在權(quán)向量w=(w1w2w3)T的三維空間中，則x=(x1x21)T為方程的系數(shù)。若以x向量作為法線向量，則該線性方程所決定的平面為通過原點且與法線向量垂直的平面，它同樣將權(quán)空間劃分為正、負兩邊。在系數(shù)x不變的條件下，若w值落在法線向量離開平面的一邊，則wTx>0，若w值落在法線向量射向平面的一邊，則wTx<0。第25頁，課件共47頁，創(chuàng)作于2023年2月3.4模式空間和權(quán)空間權(quán)空間中判別界面的平面示意圖第26頁，課件共47頁，創(chuàng)作于2023年2月作業(yè)兩類模式，每類包括5個3維不同的模式，且良好分布。如果它們是線性可分的，問權(quán)向量至少需要幾個系數(shù)分量？假如要建立二次的多項式判別函數(shù)，又至少需要幾個系數(shù)分量？（設模式的良好分布不因模式變化而改變。）第27頁，課件共47頁，創(chuàng)作于2023年2月3.5感知器算法出發(fā)點一旦判別函數(shù)的形式確定下來，不管它是線性的還是非線性的，剩下的問題就是如何確定它的系數(shù)。在模式識別中，系數(shù)確定的一個主要方法就是通過對已知樣本的訓練和學習來得到。感知器算法就是通過訓練樣本模式的迭代和學習，產(chǎn)生線性（或廣義線性）可分的模式判別函數(shù)。第28頁，課件共47頁，創(chuàng)作于2023年2月3.5感知器算法基本思想采用感知器算法(PerceptionApproach)能通過對訓練模式樣本集的“學習”得到判別函數(shù)的系數(shù)。說明這里采用的算法不需要對各類別中模式的統(tǒng)計性質(zhì)做任何假設，因此稱為確定性的方法。第29頁，課件共47頁，創(chuàng)作于2023年2月3.5感知器算法背景“感知器”一詞出自于20世紀50年代中期到60年代中期人們對一種分類學習機模型的稱呼，它是屬于有關(guān)動物和機器學習的仿生學領(lǐng)域中的問題。當時的一些研究者認為感知器是一種學習機的強有力模型，后來發(fā)現(xiàn)估計過高了，但發(fā)展感知器的一些相關(guān)概念仍然沿用下來。第30頁，課件共47頁，創(chuàng)作于2023年2月3.5感知器算法[感知器的訓練算法]感知器算法實質(zhì)上是一種賞罰過程對正確分類的模式則“賞”，實際上是“不罰”，即權(quán)向量不變。對錯誤分類的模式則“罰”，使w(k)加上一個正比于xk的分量。當用全部模式樣本訓練過一輪以后，只要有一個模式是判別錯誤的，則需要進行下一輪迭代，即用全部模式樣本再訓練一次。如此不斷反復直到全部模式樣本進行訓練都能得到正確的分類結(jié)果為止。第31頁，課件共47頁，創(chuàng)作于2023年2月3.5感知器算法[例子]感知器算法的收斂性只要模式類別是線性可分的，就可以在有限的迭代步數(shù)里求出權(quán)向量。（證明作為練習）第32頁，課件共47頁，創(chuàng)作于2023年2月作業(yè)及編程用感知器算法求下列模式分類的解向量w:

ω1:{(000)T,(100)T,(101)T,(110)T} ω2:{(001)T,(011)T,(010)T,(111)T}編寫求解上述問題的感知器算法程序。第33頁，課件共47頁，創(chuàng)作于2023年2月3.6采用感知器算法的多類模式的分類采用3.1的多類情況3，將感知器算法推廣到多類模式。[多類情況3][感知器算法判別函數(shù)的推導][例子]第34頁，課件共47頁，創(chuàng)作于2023年2月3.6采用感知器算法的多類模式的分類討論這里的分類算法都是通過模式樣本來確定判別函數(shù)的系數(shù)，但一個分類器的判斷性能最終要受并未用于訓練的那些未知樣本來檢驗。要使一個分類器設計完善，必須采用有代表性的訓練數(shù)據(jù)，它能夠合理反映模式數(shù)據(jù)的整體。第35頁，課件共47頁，創(chuàng)作于2023年2月3.6采用感知器算法的多類模式的分類討論要獲得一個判別性能好的線性分類器，究竟需要多少訓練樣本？直觀上是越多越好，但實際上能收集到的樣本數(shù)目會受到客觀條件的限制；過多的訓練樣本在訓練階段會使計算機需要較長的運算時間；一般來說，合適的樣本數(shù)目可如下估計： 若k是模式的維數(shù)，令C=2(k+1)，則通常選用的訓練樣本數(shù)目約為C的10~20倍。第36頁，課件共47頁，創(chuàng)作于2023年2月作業(yè)用多類感知器算法求下列模式的判別函數(shù)：

ω1:(-1-1)T ω2:(00)T

ω3:(11)T第37頁，課件共47頁，創(chuàng)作于2023年2月3.7勢函數(shù)法—一種確定性的非線性分類方法目的用勢函數(shù)的概念來確定判別函數(shù)和劃分類別界面?；舅枷爰僭O要劃分屬于兩種類別ω1和ω2的模式樣本，這些樣本可看成是分布在n維模式空間中的點xk。把屬于ω1的點比擬為某種能源點，在點上，電位達到峰值。隨著與該點距離的增大，電位分布迅速減小，即把樣本xk附近空間x點上的電位分布，看成是一個勢函數(shù)K(x,xk)。對于屬于ω1的樣本集群，其附近空間會形成一個“高地”，這些樣本點所處的位置就是“山頭”。同理，用電位的幾何分布來看待屬于ω2的模式樣本，在其附近空間就形成“凹地”。只要在兩類電位分布之間選擇合適的等高線，就可以認為是模式分類的判別函數(shù)。第38頁，課件共47頁，創(chuàng)作于2023年2月3.7勢函數(shù)法—一種確定性的非線性分類方法3.7.1判別函數(shù)的產(chǎn)生模式分類的判別函數(shù)可由分布在模式空間中的許多樣本向量{xk,k=1,2,…和}的勢函數(shù)產(chǎn)生。任意一個樣本所產(chǎn)生的勢函數(shù)以K(x,xk)表征，則判別函數(shù)d(x)可由勢函數(shù)序列K(x,x1)，K(x,x2)，…來構(gòu)成，序列中的這些勢函數(shù)相應于在訓練過程中輸入機器的訓練模式樣本x1，x2，…。在訓練狀態(tài)，模式樣本逐個輸入分類器，分類器就連續(xù)計算相應的勢函數(shù)，在第k步迭代時的積累位勢決定于在該步前所有的單獨勢函數(shù)的累加。以K(x)表示積累位勢函數(shù)，若加入的訓練樣本xk+1是錯誤分類，則積累函數(shù)需要修改，若是正確分類，則不變。第39頁，課件共47頁，創(chuàng)作于2023年2月3.7勢函數(shù)法—一種確定性的非線性分類方法3.7.1判別函數(shù)的產(chǎn)生[逐步分析]從勢函數(shù)可以看出，積累位勢起著判別函數(shù)的作用當xk+1屬于ω1時，Kk(xk+1)>0，或當xk+1屬于ω2時，Kk(xk+1)<0，則積累位勢不做任何修改就可用作判別函數(shù)。由于一個模式樣本的錯誤分類可造成積累位勢在訓練時的變化，因此勢函數(shù)算法提供了確定ω1和ω2兩類判別函數(shù)的迭代過程。[判別函數(shù)表達式]第40頁，課件共47頁，創(chuàng)作于2023年2月3.7勢函數(shù)法—一種確定性的非線性分類方法3.7.2勢函數(shù)的選擇選擇勢函數(shù)的條件：一般來說，若兩個n維向量x和xk的函數(shù)K(x,xk)同時滿足下列三個條件，則可作為勢函數(shù)。K(x,xk)=K(xk