1、模式識別模式識別模式識別模式識別第一章第一章 緒論緒論模式識別 緒論一、模式識別的概念一、模式識別的概念p什么是模式識別？什么是模式識別？p模式識別研究的內容？模式識別研究的內容？模式識別 緒論二、模式識別的應用二、模式識別的應用p工業(yè)用途：產品質量檢驗，設備故障檢測，智工業(yè)用途：產品質量檢驗，設備故障檢測，智能機器人的感知系統(tǒng)；能機器人的感知系統(tǒng)；p商業(yè)用途：錢幣的自動識偽，信函的自動分揀，商業(yè)用途：錢幣的自動識偽，信函的自動分揀，電話信息查詢，聲控撥號；電話信息查詢，聲控撥號；p醫(yī)學用途：對心電、腦電、醫(yī)學用途：對心電、腦電、CT等信號進行處等信號進行處理和識別，自動進行疾病的診斷；理和識

2、別，自動進行疾病的診斷；p安全領域：生理特征鑒別安全領域：生理特征鑒別(Biometrics)，網，網上電子商務的身份確認，對公安對象的刑偵和上電子商務的身份確認，對公安對象的刑偵和鑒別；鑒別； 模式識別 緒論二、模式識別的應用二、模式識別的應用p軍事領域：巡航導彈的景物識別，戰(zhàn)斗單元的軍事領域：巡航導彈的景物識別，戰(zhàn)斗單元的敵我識別；敵我識別； p辦公自動化：文字識別技術和聲音識別技術；辦公自動化：文字識別技術和聲音識別技術； p數(shù)據挖掘：數(shù)據分析；數(shù)據挖掘：數(shù)據分析； p網絡應用：文本分類。網絡應用：文本分類。 模式識別 緒論三、相關領域三、相關領域p人工智能：人工智能：Artificia

3、l Intelligence (AI)p模式識別：模式識別：Pattern Recognition (PR)p機器學習：機器學習：Machine Learningp人工神經網絡：人工神經網絡：Neural Network (NN)p計算機視覺：計算機視覺：Computer Vision (CV)模式識別 緒論四、模式識別的過程四、模式識別的過程模式識別 緒論什么是特征？什么是特征？模式識別 緒論什么是特征？什么是特征？模式識別 緒論什么是特征？什么是特征？模式識別 緒論特征抽取特征抽取模式識別 緒論特征抽取特征抽取模式識別 緒論特征的分布特征的分布模式識別 緒論特征的分布特征的分布模式識別 緒

4、論五、模式識別系統(tǒng)五、模式識別系統(tǒng) 分類分類訓練訓練模式識別 緒論六、模式識別問題的描述六、模式識別問題的描述給定一個訓練樣本的特征矢量集合：給定一個訓練樣本的特征矢量集合：分別屬于分別屬于c個類別：個類別：設計出一個分類器，能夠對未知類別樣本設計出一個分類器，能夠對未知類別樣本x進行分類進行分類2,dniDR1x xxx12,c ,1,dygRcx模式識別 緒論分類方法分類方法模式識別 緒論模式識別方法的分類模式識別方法的分類p有監(jiān)督學習（有教師學習）：預先已知訓有監(jiān)督學習（有教師學習）：預先已知訓練樣本集中每個樣本的類別標號；練樣本集中每個樣本的類別標號；p無監(jiān)督學習（無教師學習）：預先不

5、知道無監(jiān)督學習（無教師學習）：預先不知道訓練樣本集中每個樣本的類別標號；訓練樣本集中每個樣本的類別標號；模式識別 緒論七、參考書目七、參考書目pRichard Duda, Peter Hart, David Stork, Pattern Classification, 2nd edition, John Wiley, 2001p模式分類模式分類，機械工業(yè)出版社，機械工業(yè)出版社，Richard O. Dudap模式識別模式識別（第二版），清華大學出版社，邊（第二版），清華大學出版社，邊肇祺，張學工；肇祺，張學工；模式識別 緒論期刊期刊pIEEE Transaction on Pattern An

6、alysis and Machine Intelligence，PAMI；pPattern Recognition；pPattern Recognition Letter；p模式識別與人工智能；模式識別與人工智能；p講義下載講義下載:22用戶名用戶名: prai 密碼密碼: prai模式識別第二章第二章 貝葉斯決策理論貝葉斯決策理論模式識別 緒論2.1 最小錯誤率準則最小錯誤率準則模式識別 緒論各種概率及其關系各種概率及其關系p先驗概率：先驗概率：p后驗概率：后驗概率：p類條件概率：類條件概率：p貝葉斯公式：貝葉斯公式：iPiPxiPx iiiPPPPxxx

7、模式識別 緒論兩個類別，一維特征兩個類別，一維特征模式識別 緒論兩類問題的錯誤率兩類問題的錯誤率p觀察到特征觀察到特征x時作出判別的錯誤率：時作出判別的錯誤率：1221,PP errorPxxx判定判定 兩類問題最小錯誤率判別準則：兩類問題最小錯誤率判別準則：121122,PPPPxxxxxx如果如果模式識別 緒論多類問題最小錯誤率多類問題最小錯誤率p判別判別x屬于屬于i i的錯誤率：的錯誤率：1jij iP errorPP xxx 判別準則為：判別準則為：1argmax,jj ciP xix則：則：模式識別 緒論貝葉斯最小錯誤率準則貝葉斯最小錯誤率準則 jjjpPPpxxx jjjgpPxx

8、 1argmaxjj cig xixBayes判別準則：判別準則：，則模式識別 緒論貝葉斯分類器的錯誤率估計貝葉斯分類器的錯誤率估計11iciiRP errorpdxx1px2px模式識別 緒論例例2.1p 對一大批人進行癌癥普查，設對一大批人進行癌癥普查，設1 1類代表患癌類代表患癌癥，癥，2 2類代表正常人。已知先驗概率：類代表正常人。已知先驗概率：120.005,0.995PP以一個化驗結果作為特征以一個化驗結果作為特征x: 陽性，陰性陽性，陰性，患癌癥，患癌癥的人和正常人化驗結果為陽性的概率分別為：的人和正常人化驗結果為陽性的概率分別為：現(xiàn)有一人化驗結果為陽性，問此人是否患癌癥？現(xiàn)有一

9、人化驗結果為陽性，問此人是否患癌癥？120.95,0.01P xP x陽性陽性模式識別 緒論2.2 最小平均風險準則貝葉斯分最小平均風險準則貝葉斯分 類器類器p問題的提出問題的提出 有有c個類別個類別1, 2 ,. , c, 將將i i類的樣本判類的樣本判別為別為j j類的代價為類的代價為ij。p將未知模式將未知模式x判別為判別為j j類類的平均風險為：的平均風險為： 1cjijiiPxx模式識別 緒論最小平均風險判別準則最小平均風險判別準則p利用利用Bayes公式，構造判別函數(shù)：公式，構造判別函數(shù)： jjg xx 1cjijiiiPPxx模式識別 緒論貝葉斯分類器貝葉斯分類器模式識別 緒論例

10、例2.2p 對一大批人進行癌癥普查，設對一大批人進行癌癥普查，設1類代表患癌癥，類代表患癌癥，2類代表正常人。已知先驗概率：類代表正常人。已知先驗概率：120.005,0.995PP以一個化驗結果作為特征以一個化驗結果作為特征x: 陽性，陰性陽性，陰性，患癌癥，患癌癥的人和正常人化驗結果為陽性的概率分別為：的人和正常人化驗結果為陽性的概率分別為：判別代價：判別代價： 11 = 0, 22 = 0, 12 = 100, 21 = 25現(xiàn)有一人化驗結果為陽性，問此人是否患癌癥？現(xiàn)有一人化驗結果為陽性，問此人是否患癌癥？120.95,0.01PxPx陽 性陽 性模式識別 緒論2.3 貝葉斯分類器的其

11、它版本貝葉斯分類器的其它版本p先驗概率先驗概率P(i i)未知：極小化極大準則；未知：極小化極大準則；p約束一定錯誤率（風險）：約束一定錯誤率（風險）：Neyman-Pearson準則；準則；p某些特征缺失的決策：某些特征缺失的決策：p連續(xù)出現(xiàn)的模式之間統(tǒng)計相關的決策：連續(xù)出現(xiàn)的模式之間統(tǒng)計相關的決策：模式識別 緒論2.4 正態(tài)分布的貝葉斯分類器正態(tài)分布的貝葉斯分類器p單變量正態(tài)分布密度函數(shù)（高斯分布）：單變量正態(tài)分布密度函數(shù)（高斯分布）： 211e x p22xpx 模式識別 緒論11 2211exp22tiiiidipxxx多元正態(tài)分布函數(shù)多元正態(tài)分布函數(shù)模式識別 緒論正態(tài)分布的判別函數(shù)正

12、態(tài)分布的判別函數(shù)p貝葉斯判別函數(shù)可以寫成對數(shù)形式：貝葉斯判別函數(shù)可以寫成對數(shù)形式： lnlniiigpPxx 類條件概率密度函數(shù)為正態(tài)分布時：類條件概率密度函數(shù)為正態(tài)分布時： 111ln2lnln222tiiiiiidgP xxx模式識別 緒論情況一情況一：21,iiPcI 2tiiiigxx x x 判別函數(shù)可以寫成：判別函數(shù)可以寫成： 此分類器稱為距離分類器，判別函數(shù)可以用此分類器稱為距離分類器，判別函數(shù)可以用待識模式待識模式x與類別均值與類別均值i i之間的距離表示：之間的距離表示： ,iigdxx 模式識別 緒論情況二：情況二：i 11ln2tiiiigPxx x 1101ln2ttt

13、iiiiiiigPwx x w x 判別函數(shù)可以寫成：判別函數(shù)可以寫成： 可以簡化為：可以簡化為：稱為線性分類器稱為線性分類器模式識別 緒論線性分類器線性分類器 兩類問題，兩類問題，1維特征，先驗概率相同時：維特征，先驗概率相同時：模式識別 緒論線性分類器線性分類器 兩類問題，高維特征，先驗概率相同時：兩類問題，高維特征，先驗概率相同時：模式識別 緒論線性分類器線性分類器 兩類問題，兩類問題，1維特征，先驗概率不同時：維特征，先驗概率不同時：模式識別 緒論線性分類器線性分類器 兩類問題，高維特征，先驗概率不同時：兩類問題，高維特征，先驗概率不同時：模式識別 緒論情況三：情況三： 任意任意i 判

14、別函數(shù)可以寫成：判別函數(shù)可以寫成： 分類界面為分類界面為2次曲線（面）次曲線（面） 111111lnln222tttiiiiiiiiigP xx x x 模式識別 緒論二次分類曲線二次分類曲線模式識別 緒論二次分類曲面二次分類曲面模式識別第三章第三章 概率密度函數(shù)的概率密度函數(shù)的參數(shù)估計參數(shù)估計模式識別 緒論3.0 引言引言p貝葉斯分類器中最主要的問題是類條件概率密貝葉斯分類器中最主要的問題是類條件概率密度函數(shù)的估計。度函數(shù)的估計。p問題可以表示為：已有問題可以表示為：已有c個類別的訓練樣本集個類別的訓練樣本集合合D1，D2，Dc，求取每個類別的類條件，求取每個類別的類條件概率密度概率密度 。

15、ipx模式識別 緒論概率密度函數(shù)的估計方法概率密度函數(shù)的估計方法p參數(shù)估計方法：預先假設每一個類別的概率密度參數(shù)估計方法：預先假設每一個類別的概率密度函數(shù)的形式已知，而具體的參數(shù)未知；函數(shù)的形式已知，而具體的參數(shù)未知；n最大似然估計最大似然估計(MLE, Maximum Likelihood Estimation)；n貝葉斯估計貝葉斯估計(Bayesian Estimation)。p非參數(shù)估計方法。非參數(shù)估計方法。模式識別 緒論3.1 最大似然估計最大似然估計p樣本集樣本集D中包含中包含n個樣本：個樣本：x1，x2， , xn，樣，樣本都是本都是獨立同分布獨立同分布的隨機變量的隨機變量(i.i

16、.d，independent identically distributed)。p對類條件概率密度函數(shù)的函數(shù)形式作出假設，參對類條件概率密度函數(shù)的函數(shù)形式作出假設，參數(shù)可以表示為參數(shù)矢量數(shù)可以表示為參數(shù)矢量：,iipx模式識別 緒論似然函數(shù)似然函數(shù)p由獨立同分布假設，樣本集由獨立同分布假設，樣本集D出現(xiàn)的概率為：出現(xiàn)的概率為：121,nniip Dppx xx x 定義對數(shù)似然函數(shù)：定義對數(shù)似然函數(shù)： 1lnlnniilp Dpx 模式識別 緒論最大似然估計最大似然估計p最大似然估計就是要尋找到一個最優(yōu)矢量最大似然估計就是要尋找到一個最優(yōu)矢量 ，使，使得似然函數(shù)得似然函數(shù) 最大。最大。 arg

17、maxl l 模式識別 緒論正態(tài)分布的似然估計正態(tài)分布的似然估計pGauss分布的參數(shù)由均值矢量分布的參數(shù)由均值矢量和協(xié)方差矩陣和協(xié)方差矩陣構成，最大似然估計結果為：構成，最大似然估計結果為：11ntiiinxx11niinx模式識別 緒論3.2 貝葉斯估計貝葉斯估計p已有獨立同分布訓練樣本集已有獨立同分布訓練樣本集D；p已知類條件概率密度函數(shù)已知類條件概率密度函數(shù)p(x|)的形式，但參數(shù)的形式，但參數(shù)未知；未知；p已知參數(shù)已知參數(shù)的先驗概率密度函數(shù)的先驗概率密度函數(shù)p()；p求在已有訓練樣本集求在已有訓練樣本集D的條件下，類條件概率密的條件下，類條件概率密度函數(shù)度函數(shù)p(x|D)。模式識別

18、緒論貝葉斯估計與最大似然估計的差別貝葉斯估計與最大似然估計的差別p最大似然估計認為最大似然估計認為是一個確定的未知矢量；是一個確定的未知矢量；p貝葉斯估計認為貝葉斯估計認為是一個隨機變量，以一定的概是一個隨機變量，以一定的概率分布取所有可能的值。率分布取所有可能的值。模式識別 緒論貝葉斯估計的一般理論貝葉斯估計的一般理論 ,pDpD dppD dxx x 由于參數(shù)矢量由于參數(shù)矢量是一個隨機變量，所以類是一個隨機變量，所以類條件概率可以用下式計算：條件概率可以用下式計算： 11niiniippp DppDp Dpdppdx x 根據貝葉斯公式，有：根據貝葉斯公式，有：模式識別 緒論單變量正態(tài)分布

19、的貝葉斯估計單變量正態(tài)分布的貝葉斯估計2,p xN 已知概率密度函數(shù)滿足正態(tài)分布，其中方已知概率密度函數(shù)滿足正態(tài)分布，其中方差差2 2已知，均值已知，均值未知，假設未知，假設的先驗概的先驗概率滿足正態(tài)分布，即：率滿足正態(tài)分布，即： 200,pN 模式識別 緒論均值的后驗概率均值的后驗概率 1niip DppDp xpp Dpd202222100111exp22niiNx經推導可得，在已知訓練樣本集合經推導可得，在已知訓練樣本集合D的條件的條件下，參數(shù)下，參數(shù)的分布：的分布：211exp22nnn模式識別 緒論均值的后驗概率均值的后驗概率均值的后驗概率仍滿足正態(tài)分布，其中：均值的后驗概率仍滿足正

20、態(tài)分布，其中：2200222200nnnnn11nniixn2220220nn 模式識別 緒論均值分布的變化均值分布的變化模式識別 緒論類條件概率密度的計算類條件概率密度的計算 p x Dp xpD d221111expexp2222nnnxd222,1exp22nnnnfx 2222222221,exp2nnnnnnxfdu 模式識別 緒論3.3期望最大化算法期望最大化算法(EM算法算法)pEM算法的應用可以分為兩個方面：算法的應用可以分為兩個方面：1.訓練樣本中某些特征丟失情況下，分布參數(shù)的最大訓練樣本中某些特征丟失情況下，分布參數(shù)的最大似然估計；似然估計；2.對某些復雜分布模型假設，最大

21、似然估計很難得到對某些復雜分布模型假設，最大似然估計很難得到解析解時的迭代算法。解析解時的迭代算法。模式識別 緒論基本基本EM算法算法p令令X是觀察到的樣本數(shù)據集合，是觀察到的樣本數(shù)據集合，Y為丟失的數(shù)為丟失的數(shù)據集合，完整的樣本集合據集合，完整的樣本集合D=X Y。p DpX,Y lnllDlp X,YX,Y 由于由于Y未知，在給定參數(shù)未知，在給定參數(shù)時，時，似然函數(shù)可以似然函數(shù)可以看作看作Y的函數(shù)：的函數(shù)：模式識別 緒論基本基本EM算法算法p由于由于Y未知，因此我們需要尋找到一個在未知，因此我們需要尋找到一個在Y的的所有可能情況下，平均意義下的似然函數(shù)最所有可能情況下，平均意義下的似然函數(shù)

22、最大值，即似然函數(shù)對大值，即似然函數(shù)對Y的期望的最大值：的期望的最大值：11,iiQElY X,YX 1argmaxiiQ 1ln,iEpYX,Y X 模式識別 緒論基本基本EM算法算法1.begin initialize ，T，i0；2. do ii+13. E步：計算步：計算 ; ;4. M步：步：5. until 6.return 01iQ 11iiiiQQT 1i1argmaxiiQ 模式識別 緒論混合密度模型混合密度模型p一個復雜的概率密度分布函數(shù)可以由多個簡一個復雜的概率密度分布函數(shù)可以由多個簡單的密度函數(shù)混合構成：單的密度函數(shù)混合構成：1,Miiiipa px x 最常用的是高斯

23、混合模型最常用的是高斯混合模型(GMM，Gauss Mixture Model)： 1;Miiiipa Nxx ,11Miia模式識別 緒論GMM模型產生的模型產生的2維樣本數(shù)據維樣本數(shù)據模式識別 緒論兩個高斯函數(shù)的混合兩個高斯函數(shù)的混合 0.710,20.3 (5,3)p xNN模式識別 緒論混合密度模型的參數(shù)估計混合密度模型的參數(shù)估計p混合密度模型的參數(shù)可以表示為：混合密度模型的參數(shù)可以表示為：1212,MMa aa 參數(shù)的估計方法：參數(shù)的估計方法：1. 利用最優(yōu)化方法直接對似然函數(shù)進行優(yōu)化，如利用最優(yōu)化方法直接對似然函數(shù)進行優(yōu)化，如梯度下降法；梯度下降法；2. 引入未知隱變量引入未知隱變

24、量Y對問題進行簡化，將對問題進行簡化，將Y看作丟看作丟失的數(shù)據，使用失的數(shù)據，使用EM算法進行優(yōu)化。算法進行優(yōu)化。模式識別 緒論GMM模型的參數(shù)估計模型的參數(shù)估計p首先引入隱含數(shù)據集合首先引入隱含數(shù)據集合:12,nYy yy 其中：其中： 代表第代表第i個訓練樣本是個訓練樣本是由第由第 個高斯函數(shù)產生的，將個高斯函數(shù)產生的，將Y作為丟失作為丟失數(shù)據集合，采用數(shù)據集合，采用EM算法進行迭代估計。算法進行迭代估計。1,iyMiy模式識別 緒論GMM參數(shù)的參數(shù)的EM估計算法估計算法1.設定混合模型數(shù)設定混合模型數(shù)M，初始化模型參數(shù)，初始化模型參數(shù) ，閾值，閾值T，i0；2.用下列公式迭代計算模型參數(shù)

25、，直到似然函數(shù)變化用下列公式迭代計算模型參數(shù)，直到似然函數(shù)變化小于小于T為止：為止：01,iimmtmitMiijjtjja pp ma px x x 111,niimttap mnx 111,nittitmnittp mp mxx x 11111,ntiiittmtmitmnittp mp mx xxx 模式識別 緒論EM算法的性質算法的性質pEM算法具有收斂性；算法具有收斂性；pEM算法只能保證收斂于似然函數(shù)的局部最大值算法只能保證收斂于似然函數(shù)的局部最大值點（極值點），而不能保證收斂于全局最優(yōu)點。點（極值點），而不能保證收斂于全局最優(yōu)點。模式識別 緒論隱含隱含Markov模型模型 (Hi

26、dden Markov Model, HMM)p有一些模式識別系統(tǒng)處理的是與時間相關的問有一些模式識別系統(tǒng)處理的是與時間相關的問題，如語音識別，手勢識別，唇讀系統(tǒng)等；題，如語音識別，手勢識別，唇讀系統(tǒng)等；p對這類問題采用一個特征矢量序列描述比較方對這類問題采用一個特征矢量序列描述比較方便，這類問題的識別便，這類問題的識別HMM取得了很好的效果。取得了很好的效果。模式識別 緒論輸入語音波形輸入語音波形模式識別 緒論觀察序列觀察序列p信號的特征需要用一個特征矢量的序列來表示：信號的特征需要用一個特征矢量的序列來表示：12,TTVv vv 其中的其中的vi為一個特征矢量，稱為一個觀察值。為一個特征矢

27、量，稱為一個觀察值。模式識別 緒論一階一階Markov模型模型p一階一階Markov模型由模型由M個狀態(tài)構成，在每個時刻個狀態(tài)構成，在每個時刻t，模型處于某個狀態(tài)模型處于某個狀態(tài)w(t)，經過，經過T個時刻，產生出一個個時刻，產生出一個長度為長度為T的狀態(tài)序列的狀態(tài)序列WT=w(1),w(T)。模式識別 緒論一階一階Markov模型的狀態(tài)轉移模型的狀態(tài)轉移p模型在時刻模型在時刻t處于狀態(tài)處于狀態(tài)wj的概率完全由的概率完全由t-1時刻時刻的狀態(tài)的狀態(tài)wi決定，而且與時刻決定，而且與時刻t無關，即：無關，即： 1TP w t WP w t w t 1jiijP w tw ta模式識別 緒論Mark

28、ov模型的初始狀態(tài)概率模型的初始狀態(tài)概率p模型初始于狀態(tài)模型初始于狀態(tài)wi的概率用的概率用 表示。表示。p完整的一階完整的一階Markov模型可以用參數(shù)模型可以用參數(shù) 表示，其中：表示，其中： i,A1,M111212122212MMMMMMaaaaaaAaaa模式識別 緒論一階一階Markov模型輸出狀態(tài)序列的模型輸出狀態(tài)序列的概率概率p模型輸出狀態(tài)序列的概率可以由初始狀態(tài)概率模型輸出狀態(tài)序列的概率可以由初始狀態(tài)概率與各次狀態(tài)轉移概率相乘得到。與各次狀態(tài)轉移概率相乘得到。p例如：例如：W5=w1, w1, w3, w1, w2，則模型，則模型輸出該序列的概率為：輸出該序列的概率為：51111

29、33112P Wa a a a模式識別 緒論一階隱含一階隱含Markov模型模型p隱含隱含Markov模型中，狀態(tài)是不可見的，在每一模型中，狀態(tài)是不可見的，在每一個時刻個時刻t，模型當前的隱狀態(tài)可以輸出一個觀察值。，模型當前的隱狀態(tài)可以輸出一個觀察值。p隱狀態(tài)輸出的觀察值可以是離散值，連續(xù)值，也隱狀態(tài)輸出的觀察值可以是離散值，連續(xù)值，也可以是一個矢量?？梢允且粋€矢量。模式識別 緒論HMM的工作原理的工作原理pHMM的內部狀態(tài)轉移過程同的內部狀態(tài)轉移過程同Markov模型相同，在模型相同，在每次狀態(tài)轉移之后，由該狀態(tài)輸出一個觀察值，只是每次狀態(tài)轉移之后，由該狀態(tài)輸出一個觀察值，只是狀態(tài)轉移過程無

30、法觀察到，只能觀察到輸出的觀察值狀態(tài)轉移過程無法觀察到，只能觀察到輸出的觀察值序列。序列。p以離散的以離散的HMM為例，隱狀態(tài)可能輸出的觀察值集合為為例，隱狀態(tài)可能輸出的觀察值集合為v1, v2, , vK，第，第i個隱狀態(tài)輸出第個隱狀態(tài)輸出第k個觀察值的個觀察值的概率為概率為bik。p例如：例如：T=5時，可能的觀察序列時，可能的觀察序列V5=v3v2v3v4v1模式識別 緒論HMM的工作過程的工作過程模式識別 緒論HMM的參數(shù)表示的參數(shù)表示p狀態(tài)轉移矩陣：狀態(tài)轉移矩陣：A，M*M的方陣；的方陣；p狀態(tài)輸出概率：狀態(tài)輸出概率：B，M*K的矩陣；的矩陣；p初始概率：初始概率：，包括，包括M個元

31、素。個元素。M個狀態(tài)，個狀態(tài)，K個可能的輸出值。個可能的輸出值。, A B模式識別 緒論HMM的三個核心問題的三個核心問題p估值問題：已有一個：已有一個HMM模型，其參數(shù)已知，模型，其參數(shù)已知，計算這個模型輸出特定的觀察序列計算這個模型輸出特定的觀察序列VT的概率；的概率；p解碼問題：已有一個：已有一個HMM模型，其參數(shù)已知，模型，其參數(shù)已知，計算最有可能輸出特定的觀察序列計算最有可能輸出特定的觀察序列VT的隱狀態(tài)的隱狀態(tài)轉移序列轉移序列WT；p學習問題：已知一個：已知一個HMM模型的結構，其參數(shù)模型的結構，其參數(shù)未知，根據一組訓練序列對參數(shù)進行訓練；未知，根據一組訓練序列對參數(shù)進行訓練；模式

32、識別 緒論估值問題估值問題p一個一個HMM模型產生觀察序列模型產生觀察序列VT可以由下式計算：可以由下式計算： max1rTTTTrrrP VP VWP Wrmax=MT為為HMM所有可能的狀態(tài)轉移序列數(shù)；所有可能的狀態(tài)轉移序列數(shù)； 為狀態(tài)轉移序列為狀態(tài)轉移序列 輸出觀察序列輸出觀察序列 的概的概率；率； 為為 狀態(tài)轉移序列狀態(tài)轉移序列 發(fā)生的概率。發(fā)生的概率。 TTrP VWTrP WTrWTVTrW模式識別 緒論估值問題的計算估值問題的計算 112231rrrrrrrTrwwwwww Tw TP Waaa 1212rrrTTrwwwTP VWbvbvbv T max11122112rrrr

33、rrTwwwwwrP Vbvabv 1rrrwTwTwTabv Tp計算復雜度：計算復雜度：TO M T模式識別 緒論HMM估值算法的簡化估值算法的簡化模式識別 緒論HMM的前向算法的前向算法1.初始化：初始化：2.迭代計算：迭代計算：3.結束輸出：結束輸出： 11,1,iiib viM 111 ,1,Mijjiijtt ab v tiM 1MTiiP VT計算復雜度：計算復雜度：2O M T模式識別 緒論解碼問題解碼問題p解碼問題的計算同估值問題的計算類似，最直觀的解碼問題的計算同估值問題的計算類似，最直觀的思路是遍歷所有的可能狀態(tài)轉移序列，取出最大值，思路是遍歷所有的可能狀態(tài)轉移序列，取出

34、最大值，計算復雜度為：計算復雜度為：O(MTT)。p同樣存在著優(yōu)化算法：同樣存在著優(yōu)化算法：Viterbi算法。算法。模式識別 緒論Viterbi算法算法1.因為需要回朔最優(yōu)路徑，所以建立一個矩陣因為需要回朔最優(yōu)路徑，所以建立一個矩陣，其元，其元素素 保存第保存第t t步，第步，第i i個狀態(tài)在第個狀態(tài)在第t-1t-1步的最優(yōu)狀態(tài)。步的最優(yōu)狀態(tài)。 ti2.2. 初始化：初始化：3.3. 迭代計算：迭代計算：4.4. 結束：結束：5.5. 路徑回朔：路徑回朔： 11,1,iiibviM 10i 11max1 ,1,ijjiij Mtt ab v tiM 11argmaxijjij Mtt a *

35、1max,Tjj MPVT *1argmaxjj MwTT *11wtwtt模式識別 緒論Viterbi算法圖示算法圖示模式識別 緒論學習問題學習問題pHMM的學習問題：的學習問題：已知一組觀察序列已知一組觀察序列(訓練樣本集合訓練樣本集合)：1212,nTTTnVVVV如何確定最優(yōu)的模型參數(shù)如何確定最優(yōu)的模型參數(shù)，使得模型產生訓，使得模型產生訓練集合練集合V V的聯(lián)合概率最大的聯(lián)合概率最大max P V這同樣是一個最大似然估計問題，需要采用這同樣是一個最大似然估計問題，需要采用EMEM算算法。法。模式識別 緒論圖示圖示模式識別 緒論變量說明變量說明p ：表示在：表示在t-1時刻時刻HMM處于

36、狀態(tài)處于狀態(tài)i，并且，并且從從1t-1時刻之間產生觀察序列時刻之間產生觀察序列V1t-1的概率；的概率；p ：表示在：表示在t時刻時刻HMM處于狀態(tài)處于狀態(tài)j，并且從，并且從t+1T時刻之間產生觀察序列時刻之間產生觀察序列Vt+1T的概率；的概率；1it jt 11iiib v1121Mijjiijttab v t 1jT 111Mjjiijitatbv t模式識別 緒論變量說明變量說明p輸出觀察序列輸出觀察序列VT時，在時，在t-1時刻時刻HMM處于處于i狀態(tài)，在時刻狀態(tài)，在時刻t處于處于j狀態(tài)的概率：狀態(tài)的概率： 1iijjjijTta bv tttP V模式識別 緒論前向前向-后向算法后

37、向算法(Baum-Welch算法算法)p迭代公式：迭代公式：初始概率：初始概率：狀態(tài)轉移概率：狀態(tài)轉移概率：輸出概率：輸出概率： 11Miijj 111TijtijTMiktktat 1,111kTMiltv tvlikTMiltltb vt 模式識別 緒論HMM的其它問題的其它問題p連續(xù)連續(xù)HMM模型：在觀察序列中每個觀察值是一個特征模型：在觀察序列中每個觀察值是一個特征矢量，相應的模型中輸出概率矢量，相應的模型中輸出概率b就需要用一個概率密度就需要用一個概率密度函數(shù)描述，其函數(shù)形式需要假設，通常使用函數(shù)描述，其函數(shù)形式需要假設，通常使用GMM。p訓練問題：通常可以用每個訓練樣本分別計算訓練

38、問題：通?？梢杂妹總€訓練樣本分別計算值，然值，然后分子和分母部分分別進行累加，最后統(tǒng)一進行參數(shù)修后分子和分母部分分別進行累加，最后統(tǒng)一進行參數(shù)修正；正；p模型的拓撲結構：模型結構可以根據實際問題的需要來模型的拓撲結構：模型結構可以根據實際問題的需要來設計，在初始化狀態(tài)轉移矩陣設計，在初始化狀態(tài)轉移矩陣A時，將某些元素設為時，將某些元素設為0即可。即可。模式識別 緒論“左左-右右”模型結構模型結構123模式識別 緒論帶跨越的帶跨越的“左左-右右”結構結構HMM模模型型1234模式識別第四章第四章 概率密度函數(shù)的概率密度函數(shù)的非參數(shù)估計非參數(shù)估計模式識別 緒論4.1 基本思想基本思想模式識別 緒論

39、4.1 基本思想基本思想p令令R是包含樣本點是包含樣本點x的一個區(qū)域，其體積為的一個區(qū)域，其體積為V，設有設有n個訓練樣本，其中有個訓練樣本，其中有k個落在區(qū)域個落在區(qū)域R中，中，則可對概率密度作出一個估計：則可對概率密度作出一個估計： k npVxp相當于用相當于用R區(qū)域內的平均性質來作為一點區(qū)域內的平均性質來作為一點x的估的估計，是一種數(shù)據的平滑。計，是一種數(shù)據的平滑。模式識別 緒論有效性有效性p當當n固定時，固定時，V的大小對估計的效果影響很的大小對估計的效果影響很大，過大則平滑過多，不夠精確；過小則大，過大則平滑過多，不夠精確；過小則可能導致在此區(qū)域內無樣本點，可能導致在此區(qū)域內無樣本

40、點，k=0。p此方法的有效性取決于樣本數(shù)量的多少，此方法的有效性取決于樣本數(shù)量的多少，以及區(qū)域體積選擇的合適。以及區(qū)域體積選擇的合適。模式識別 緒論收斂性收斂性p構造一系列包含構造一系列包含x的區(qū)域的區(qū)域R1, R2, ，對應，對應n=1,2,，則，則對對p(x)有一系列的估計：有一系列的估計： nnnk npVxp 當滿足下列條件時，當滿足下列條件時，pn(x)收斂于收斂于p (x)：lim0nnVlimnnk lim0nnkn模式識別 緒論區(qū)域選定的兩個途徑區(qū)域選定的兩個途徑pParzen窗法：區(qū)域體積窗法：區(qū)域體積V是樣本數(shù)是樣本數(shù)n的函數(shù)，如：的函數(shù)，如：1nVnpK-近鄰法：落在區(qū)域

41、內的樣本數(shù)近鄰法：落在區(qū)域內的樣本數(shù)k是總樣本數(shù)是總樣本數(shù)n的的函數(shù)，如：函數(shù)，如：nkn模式識別 緒論Parzen窗法和窗法和K-近鄰法近鄰法模式識別 緒論4.2 Parzen窗方法窗方法p定義窗函數(shù)定義窗函數(shù) 1,1 20,juu其它1,20,jijnnxxhhix-x其它dnnVh1,jd 模式識別 緒論1維數(shù)據的窗函數(shù)維數(shù)據的窗函數(shù)模式識別 緒論概率密度函數(shù)的估計概率密度函數(shù)的估計p超立方體中的樣本數(shù)：超立方體中的樣本數(shù)：p概率密度估計：概率密度估計：1nninkhix-x 111nninnpnVhix-xx模式識別 緒論窗函數(shù)的要求窗函數(shù)的要求p上述過程是一個內插過程，樣本上述過程是

42、一個內插過程，樣本xi距離距離x越近，越近，對概率密度估計的貢獻越大，越遠貢獻越小。對概率密度估計的貢獻越大，越遠貢獻越小。p只要滿足如下條件，就可以作為窗函數(shù)：只要滿足如下條件，就可以作為窗函數(shù)： 0u 1duu模式識別 緒論窗函數(shù)的形式窗函數(shù)的形式模式識別 緒論窗函數(shù)的寬度對估計的影響窗函數(shù)的寬度對估計的影響phn稱為窗的寬度稱為窗的寬度模式識別 緒論窗函數(shù)的寬度對估計的影響窗函數(shù)的寬度對估計的影響模式識別 緒論識別方法識別方法1.保存每個類別所有的訓練樣本；保存每個類別所有的訓練樣本；2.選擇窗函數(shù)的形式，根據訓練樣本數(shù)選擇窗函數(shù)的形式，根據訓練樣本數(shù)n選擇窗函選擇窗函數(shù)的數(shù)的h寬度；寬

43、度；3.識別時，利用每個類別的訓練樣本計算待識別識別時，利用每個類別的訓練樣本計算待識別樣本樣本x的類條件概率密度：的類條件概率密度：4.采用采用Bayes判別準則進行分類。判別準則進行分類。111iinjnijinpnVhx-xx模式識別 緒論Parzen窗的神經網絡實現(xiàn)窗的神經網絡實現(xiàn)p神經元模型神經元模型1dtiiinetw xw xtyf netfw x模式識別 緒論簡化神經元模型簡化神經元模型模式識別 緒論Parzen窗函數(shù)的神經元表示窗函數(shù)的神經元表示p窗函數(shù)取窗函數(shù)取Gauss函數(shù)，所有的樣本歸一化，令神經元的函數(shù)，所有的樣本歸一化，令神經元的權值等于訓練樣本，即：權值等于訓練樣

44、本，即：,kkwx21,txx x21tkkkww w 2exp2tkkknhxwxwxw221expexp2knettttkkkx x+w w -2w xp 則有：則有：模式識別 緒論概率神經網絡概率神經網絡(PNN, Probabilistic Neural Network)模式識別 緒論PNN的訓練算法的訓練算法1.begin initialize j = 0; n =訓練樣本數(shù)，訓練樣本數(shù)，aij=02.do j j + 13. normalize :4. train : wjxj5. if then aji16.until j = njjjxxxjix模式識別 緒論PNN分類算法分類

45、算法1.begin initialize k = 0; x 待識模式待識模式2. do k k + 13. 4. if aki = 1 then 5. until k = n6. return 7.endTkknet w x2exp1iikyynet1argmaxii cclassy 模式識別 緒論徑向基函數(shù)網絡徑向基函數(shù)網絡(RBF, Radial Basis Function)pRBF與與PNN的差異的差異1.PNN模式層神經元數(shù)等于訓練樣本數(shù)，而模式層神經元數(shù)等于訓練樣本數(shù)，而RBF小于小于等于訓練樣本數(shù)；等于訓練樣本數(shù)；2.PNN模式層到類別層的連接權值恒為模式層到類別層的連接權值恒為

46、1，而，而RBF的的需要訓練；需要訓練；3.PNN的訓練過程簡單，只需一步設置即可，而的訓練過程簡單，只需一步設置即可，而RBF一般需要反復迭代訓練；一般需要反復迭代訓練；模式識別 緒論徑向基函數(shù)網絡的訓練徑向基函數(shù)網絡的訓練pRBF的訓練的三種方法：的訓練的三種方法：1.根據經驗選擇每個模式層神經元的權值根據經驗選擇每個模式層神經元的權值wi以及映射函以及映射函數(shù)的寬度數(shù)的寬度，用最小二乘法計算模式層到類別層的權，用最小二乘法計算模式層到類別層的權值值；2.用聚類的方法設置模式層每個神經元的權值用聚類的方法設置模式層每個神經元的權值wi以及映以及映射函數(shù)的寬度射函數(shù)的寬度，用最小二乘法計算模

47、式層到類別層，用最小二乘法計算模式層到類別層的權值的權值；3.通過訓練樣本用誤差糾正算法迭代計算各層神經元的通過訓練樣本用誤差糾正算法迭代計算各層神經元的權值，以及模式層神經元的寬度權值，以及模式層神經元的寬度；模式識別 緒論4.3 近鄰分類器近鄰分類器p后驗概率的估計后驗概率的估計Parzen窗法估計的是每個類別的類條件概率密窗法估計的是每個類別的類條件概率密度度 ，而，而k-近鄰法是直接估計每個類別的后驗概近鄰法是直接估計每個類別的后驗概率率 。將一個體積為將一個體積為V的區(qū)域放到待識樣本點的區(qū)域放到待識樣本點x周圍，包含周圍，包含k個訓個訓練樣本點，其中練樣本點，其中ki個屬于個屬于i類

48、，總的訓練樣本數(shù)為類，總的訓練樣本數(shù)為n，則，則有：有：ipxipx,inik npVx 1,niniiicnnjjppkppkpxxxxx模式識別 緒論k-近鄰分類器近鄰分類器pk-近鄰分類算法近鄰分類算法1.設置參數(shù)設置參數(shù)k，輸入待識別樣本，輸入待識別樣本x；2.計算計算x與每個訓練樣本的與每個訓練樣本的距離距離；3.選取距離最小的前選取距離最小的前k個樣本，統(tǒng)計其中包含個樣本，統(tǒng)計其中包含各個類別的樣本數(shù)各個類別的樣本數(shù)ki；4. 1argmaxii cclassk 模式識別 緒論k-近鄰分類，近鄰分類，k=13模式識別 緒論最近鄰規(guī)則最近鄰規(guī)則p分類規(guī)則：在訓練樣本集中尋找與待識別樣

49、本分類規(guī)則：在訓練樣本集中尋找與待識別樣本x距離最近的樣本距離最近的樣本x，將，將x分類到分類到x所屬的類別。所屬的類別。p最近鄰規(guī)則相當于最近鄰規(guī)則相當于k=1的的k-近鄰分類，其分類界近鄰分類，其分類界面可以用面可以用Voronoi網格表示。網格表示。模式識別 緒論Voronoi網格網格模式識別 緒論距離度量距離度量p距離度量應滿足如下四個性質：距離度量應滿足如下四個性質：1.非負性：非負性：2.自反性：自反性： 當且僅當當且僅當3.對稱性：對稱性：4.三角不等式：三角不等式：0Da,b0Da,babDDa,bb,aDDDa,bb,ca,c模式識別 緒論常用的距離函數(shù)常用的距離函數(shù) 121

50、221,dtiiiDxyx yx-yx-yp歐幾里德距離：歐幾里德距離：(Eucidean Distance) 模式識別 緒論常用的距離函數(shù)常用的距離函數(shù)p街市距離：街市距離：(Manhattan Distance)1,diiiDxyx y模式識別 緒論常用的距離函數(shù)常用的距離函數(shù)p明氏距離：明氏距離：(Minkowski Distance)11,mdmiiiDxyx y模式識別 緒論常用的距離函數(shù)常用的距離函數(shù) 1,tDx yx-y x-yp馬氏距離：馬氏距離：(Mahalanobis Distance) 模式識別 緒論常用的距離函數(shù)常用的距離函數(shù)p角度相似函數(shù)：角度相似函數(shù)：(Angle

51、Distance),tDx yx yx y模式識別 緒論常用的距離函數(shù)常用的距離函數(shù)1,tdxxx1,tdyyy ,0,1iix y p海明距離：海明距離：(Hamming Distance) x和和y為為2值特征矢量：值特征矢量： D(x,y)定義為定義為x,y中使得不等式中使得不等式 成立的成立的i的個的個數(shù)。數(shù)。iixy模式識別 緒論最近鄰分類器的簡化最近鄰分類器的簡化p最近鄰分類器計算的時間復雜度和空間復雜度都最近鄰分類器計算的時間復雜度和空間復雜度都為為O(dn)，d為特征維數(shù)，通常只有當樣本數(shù)為特征維數(shù)，通常只有當樣本數(shù)n非常大時，分類效果才會好。非常大時，分類效果才會好。p簡化方

52、法可以分為三種：簡化方法可以分為三種：1.部分距離法；部分距離法；2.預分類法；預分類法；3.剪輯近鄰法。剪輯近鄰法。模式識別 緒論部分距離法部分距離法p定義：定義：1221rriiiDxyx,yDr(x,y)是是r的單調不減函數(shù)。令的單調不減函數(shù)。令Dmin為當前搜索到的最近鄰為當前搜索到的最近鄰距離，當待識別樣本距離，當待識別樣本x與某個訓練樣本與某個訓練樣本xi的部分距離的部分距離Dr(x,xi)大于大于 Dmin時，時， Dd(x,xi)一定要大于一定要大于Dmin ，所以，所以xi一定不是最一定不是最近鄰，不需要繼續(xù)計算近鄰，不需要繼續(xù)計算Dd(x,xi) 。模式識別 緒論預分類（搜

53、索樹）預分類（搜索樹）模式識別 緒論預分類（搜索樹）預分類（搜索樹）p在特征空間中首先找到在特征空間中首先找到m個有代表性的樣本點，個有代表性的樣本點，用這些點代表一部分訓練樣本；用這些點代表一部分訓練樣本；p待識別模式待識別模式x首先與這些代表點計算距離，找到首先與這些代表點計算距離，找到一個最近鄰，然后在這個最近鄰代表的樣本點中一個最近鄰，然后在這個最近鄰代表的樣本點中尋找實際的最近鄰點。尋找實際的最近鄰點。p這種方法是一個次優(yōu)的搜索算法。這種方法是一個次優(yōu)的搜索算法。模式識別 緒論剪輯近鄰法剪輯近鄰法p最近鄰剪輯算法最近鄰剪輯算法1.begin initialize j = 0;D =

54、data set; n = number of training samples2.construct the full Voronoi diagram of D3.do j j + 1; 4. Find the Voronoi neighbors of Xj5. if any neighbor is not from the same class as Xj then mark Xj6.until j = n7.Discard all points that are not marked8.Construct the Voronoi diagram of the remaining samp

55、les9.end模式識別 緒論剪輯近鄰法剪輯近鄰法模式識別 緒論剪輯近鄰法剪輯近鄰法模式識別 緒論RCE網絡網絡模式識別 緒論RCE網絡的訓練算法網絡的訓練算法1.begin initialize j=0, n=#patterns, =small pattern, m=max radius，aij=02.do jj+13. train weight: wj=xj4. if then aji = 15. find nearest point not in i:6. set radius: 7.until j = nargminijDxxx ,xmin,jjmD x ,xjix模式識別 緒論模式識

56、別 緒論RCE網絡的分類算法網絡的分類算法1.begin initialize j=0, k=0, x, 2. do jj+13. if then4. until j = n5. if category of all is the same 6. then return the label7. else “ambiguous” labeltD ttjDDx,jjD x xjtD x模式識別 線性判別函數(shù)第五章第五章 線性判別函數(shù)線性判別函數(shù)模式識別 緒論5.1 線性判別函數(shù)和判別界面線性判別函數(shù)和判別界面模式識別 緒論線性不可分情況線性不可分情況模式識別 緒論線性判別函數(shù)線性判別函數(shù)px=(x

57、1, x2, xd)t: 特征矢量；特征矢量；pw=(w1, w2, , wd)t: 權矢量；權矢量；pw0：偏置：偏置(bias)。 0tgwxw x模式識別 緒論線性判別函數(shù)的增廣形式線性判別函數(shù)的增廣形式py=(1, x1, x2, xd)t: 增廣的特征矢量；增廣的特征矢量；pa=(w0, w1, w2, , wd)t: 增廣的權矢量；增廣的權矢量； tgya y模式識別 緒論兩類問題線性判別準則兩類問題線性判別準則 1020,0,0,tgwxxw xx拒識模式識別 緒論線性分類器的分類界面線性分類器的分類界面模式識別 緒論分類界面的幾何解釋分類界面的幾何解釋1.線性分類界面線性分類界

58、面H是是d維空間中的一個超平面；維空間中的一個超平面；2.分類界面將分類界面將d維空間分成兩部分，維空間分成兩部分，R1，R2分分別屬于兩個類別；別屬于兩個類別；3.判別函數(shù)的權矢量判別函數(shù)的權矢量w是一個垂直于分類界面是一個垂直于分類界面H的矢量，其方向指向區(qū)域的矢量，其方向指向區(qū)域R1 ；4.偏置偏置w0與原點到分類界面與原點到分類界面H的距離有關：的距離有關：00wr w模式識別 緒論多類問題（情況一）多類問題（情況一）p每一類模式可以用一個超平面與其它類別分開；每一類模式可以用一個超平面與其它類別分開；p這種情況可以把這種情況可以把c個類別的多類問題分解為個類別的多類問題分解為c個兩個

59、兩類問題解決，需要類問題解決，需要c個線性分類界面；個線性分類界面；p第第i類與其它類別之間的判別函數(shù)：類與其它類別之間的判別函數(shù)： tiigya y模式識別 緒論多類問題（情況一）分類界面多類問題（情況一）分類界面模式識別 緒論多類問題（情況一）判別規(guī)則多類問題（情況一）判別規(guī)則p若存在若存在i，使得，使得gi(x)0， gj(x)0，ji，則，則判別判別x屬于屬于i i類類；p其它情況，拒識。其它情況，拒識。模式識別 緒論多類問題（情況二）多類問題（情況二）p每兩個類別之間可以用一個超平面分開；每兩個類別之間可以用一個超平面分開；pc個類別的問題需要個類別的問題需要c(c-1)/2個線性分

60、類界面；個線性分類界面；p第第i類與第類與第j類之間的判別函數(shù)為：類之間的判別函數(shù)為： ,tijijgya yij模式識別 緒論多類問題（情況二）分類界面多類問題（情況二）分類界面模式識別 緒論多類問題（情況二）判別準則多類問題（情況二）判別準則p如果對任意如果對任意ji ，有，有gij(x)0 ，則決策，則決策x屬于屬于i。 p其它情況，則拒識。其它情況，則拒識。模式識別 緒論多類問題（情況三）多類問題（情況三）p情況三是情況二的特例，不存在拒識區(qū)域。情況三是情況二的特例，不存在拒識區(qū)域。 模式識別 緒論多類問題（情況三）判別函數(shù)多類問題（情況三）判別函數(shù)pc個類別需要個類別需要c個線性函數(shù)