哈工大模式識別課件

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

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

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

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

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

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

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

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

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

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

11、它版本貝葉斯分類器的其它版本p先驗(yàn)概率先驗(yàn)概率P(i i)未知：極小化極大準(zhǔn)則；未知：極小化極大準(zhǔn)則；p約束一定錯誤率（風(fēng)險）：約束一定錯誤率（風(fēng)險）：Neyman-Pearson準(zhǔn)則；準(zhǔn)則；p某些特征缺失的決策：某些特征缺失的決策：p連續(xù)出現(xiàn)的模式之間統(tǒng)計(jì)相關(guān)的決策：連續(xù)出現(xiàn)的模式之間統(tǒng)計(jì)相關(guān)的決策：模式識別 緒論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維特征，先驗(yàn)概率相同時：維特征，先驗(yàn)概率相同時：模式識別 緒論線性分類器線性分類器 兩類問題，高維特征，先驗(yàn)概率相同時：兩類問題，高維特征，先驗(yàn)概率相同時：模式識別 緒論線性分類器線性分類器 兩類問題，兩類問題，1維特征，先驗(yàn)概率不同時：維特征，先驗(yàn)概率不同時：模式識別 緒論線性分類器線性分類器 兩類問題，高維特征，先驗(yàn)概率不同時：兩類問題，高維特征，先驗(yàn)概率不同時：模式識別 緒論情況三：情況三： 任意任意i 判

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

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

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

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

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

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

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

21、似然估計(jì)很難得到對某些復(fù)雜分布模型假設(shè)，最大似然估計(jì)很難得到解析解時的迭代算法。解析解時的迭代算法。模式識別 緒論基本基本EM算法算法p令令X是觀察到的樣本數(shù)據(jù)集合，是觀察到的樣本數(shù)據(jù)集合，Y為丟失的數(shù)為丟失的數(shù)據(jù)集合，完整的樣本集合據(jù)集合，完整的樣本集合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步：計(jì)算步：計(jì)算 ; ;4. M步：步：5. until 6.return 01iQ 11iiiiQQT 1i1argmaxiiQ 模式識別 緒論混合密度模型混合密度模型p一個復(fù)雜的概率密度分布函數(shù)可以由多個簡一個復(fù)雜的概率密度分布函數(shù)可以由多個簡單的密度函數(shù)混合構(gòu)成：單的密度函數(shù)混合構(gòu)成：1,Miiiipa px x 最常用的是高斯

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

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

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

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

27、量，稱為一個觀察值。模式識別 緒論一階一階Markov模型模型p一階一階Markov模型由模型由M個狀態(tài)構(gòu)成，在每個時刻個狀態(tài)構(gòu)成，在每個時刻t，模型處于某個狀態(tài)模型處于某個狀態(tài)w(t)，經(jīng)過，經(jīng)過T個時刻，產(chǎn)生出一個個時刻，產(chǎn)生出一個長度為長度為T的狀態(tài)序列的狀態(tài)序列WT=w(1),w(T)。模式識別 緒論一階一階Markov模型的狀態(tài)轉(zhuǎn)移模型的狀態(tài)轉(zhuǎn)移p模型在時刻模型在時刻t處于狀態(tài)處于狀態(tài)wj的概率完全由的概率完全由t-1時刻時刻的狀態(tài)的狀態(tài)wi決定，而且與時刻決定，而且與時刻t無關(guān)，即：無關(guān)，即： 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)轉(zhuǎn)移概率相乘得到。與各次狀態(tài)轉(zhuǎn)移概率相乘得到。p例如：例如：W5=w1, w1, w3, w1, w2，則模型，則模型輸出該序列的概率為：輸出該序列的概率為：51111

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

30、法觀察到，只能觀察到輸出的觀察值狀態(tài)轉(zhuǎn)移過程無法觀察到，只能觀察到輸出的觀察值序列。序列。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)轉(zhuǎn)移矩陣：狀態(tài)轉(zhuǎn)移矩陣：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ù)已知，計(jì)算這個模型輸出特定的觀察序列計(jì)算這個模型輸出特定的觀察序列VT的概率；的概率；p解碼問題：已有一個：已有一個HMM模型，其參數(shù)已知，模型，其參數(shù)已知，計(jì)算最有可能輸出特定的觀察序列計(jì)算最有可能輸出特定的觀察序列VT的隱狀態(tài)的隱狀態(tài)轉(zhuǎn)移序列轉(zhuǎn)移序列WT；p學(xué)習(xí)問題：已知一個：已知一個HMM模型的結(jié)構(gòu)，其參數(shù)模型的結(jié)構(gòu)，其參數(shù)未知，根據(jù)一組訓(xùn)練序列對參數(shù)進(jìn)行訓(xùn)練；未知，根據(jù)一組訓(xùn)練序列對參數(shù)進(jìn)行訓(xùn)練；模式

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

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

34、最大值，計(jì)算復(fù)雜度為：計(jì)算復(fù)雜度為：O(MTT)。p同樣存在著優(yōu)化算法：同樣存在著優(yōu)化算法：Viterbi算法。算法。模式識別 緒論Viterbi算法算法1.因?yàn)樾枰厮纷顑?yōu)路徑，所以建立一個矩陣因?yàn)樾枰厮纷顑?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. 迭代計(jì)算：迭代計(jì)算：4.4. 結(jié)束：結(jié)束：5.5. 路徑回朔：路徑回朔： 11,1,iiibviM 10i 11max1 ,1,ijjiij Mtt ab v tiM 11argmaxijjij Mtt a *

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

36、狀態(tài)處于狀態(tài)i，并且，并且從從1t-1時刻之間產(chǎn)生觀察序列時刻之間產(chǎn)生觀察序列V1t-1的概率；的概率；p ：表示在：表示在t時刻時刻HMM處于狀態(tài)處于狀態(tài)j，并且從，并且從t+1T時刻之間產(chǎn)生觀察序列時刻之間產(chǎn)生觀察序列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)轉(zhuǎn)移概率：狀態(tài)轉(zhuǎn)移概率：輸出概率：輸出概率： 11Miijj 111TijtijTMiktktat 1,111kTMiltv tvlikTMiltltb vt 模式識別 緒論HMM的其它問題的其它問題p連續(xù)連續(xù)HMM模型：在觀察序列中每個觀察值是一個特征模型：在觀察序列中每個觀察值是一個特征矢量，相應(yīng)的模型中輸出概率矢量，相應(yīng)的模型中輸出概率b就需要用一個概率密度就需要用一個概率密度函數(shù)描述，其函數(shù)形式需要假設(shè)，通常使用函數(shù)描述，其函數(shù)形式需要假設(shè)，通常使用GMM。p訓(xùn)練問題：通?？梢杂妹總€訓(xùn)練樣本分別計(jì)算訓(xùn)練

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

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

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

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

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

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

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

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ù)網(wǎng)絡(luò)徑向基函數(shù)網(wǎng)絡(luò)(RBF, Radial Basis Function)pRBF與與PNN的差異的差異1.PNN模式層神經(jīng)元數(shù)等于訓(xùn)練樣本數(shù)，而模式層神經(jīng)元數(shù)等于訓(xùn)練樣本數(shù)，而RBF小于小于等于訓(xùn)練樣本數(shù)；等于訓(xùn)練樣本數(shù)；2.PNN模式層到類別層的連接權(quán)值恒為模式層到類別層的連接權(quán)值恒為

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

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

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

49、本分類規(guī)則：在訓(xùn)練樣本集中尋找與待識別樣本x距離最近的樣本距離最近的樣本x，將，將x分類到分類到x所屬的類別。所屬的類別。p最近鄰規(guī)則相當(dāng)于最近鄰規(guī)則相當(dāng)于k=1的的k-近鄰分類，其分類界近鄰分類，其分類界面可以用面可以用Voronoi網(wǎng)格表示。網(wǎng)格表示。模式識別 緒論Voronoi網(wǎng)格網(wǎng)格模式識別 緒論距離度量距離度量p距離度量應(yīng)滿足如下四個性質(zhì)：距離度量應(yīng)滿足如下四個性質(zhì)：1.非負(fù)性：非負(fù)性：2.自反性：自反性： 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)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最近鄰分類器計(jì)算的時間復(fù)雜度和空間復(fù)雜度都最近鄰分類器計(jì)算的時間復(fù)雜度和空間復(fù)雜度都為為O(dn)，d為特征維數(shù)，通常只有當(dāng)樣本數(shù)為特征維數(shù)，通常只有當(dāng)樣本數(shù)n非常大時，分類效果才會好。非常大時，分類效果才會好。p簡化方

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

53、索樹）預(yù)分類（搜索樹）模式識別 緒論預(yù)分類（搜索樹）預(yù)分類（搜索樹）p在特征空間中首先找到在特征空間中首先找到m個有代表性的樣本點(diǎn)，個有代表性的樣本點(diǎn)，用這些點(diǎn)代表一部分訓(xùn)練樣本；用這些點(diǎn)代表一部分訓(xùn)練樣本；p待識別模式待識別模式x首先與這些代表點(diǎn)計(jì)算距離，找到首先與這些代表點(diǎn)計(jì)算距離，找到一個最近鄰，然后在這個最近鄰代表的樣本點(diǎn)中一個最近鄰，然后在這個最近鄰代表的樣本點(diǎn)中尋找實(shí)際的最近鄰點(diǎn)。尋找實(shí)際的最近鄰點(diǎn)。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網(wǎng)絡(luò)網(wǎng)絡(luò)模式識別 緒論RCE網(wǎng)絡(luò)的訓(xùn)練算法網(wǎng)絡(luò)的訓(xùn)練算法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網(wǎng)絡(luò)的分類算法網(wǎng)絡(luò)的分類算法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: 權(quán)矢量；權(quán)矢量；pw0：偏置：偏置(bias)。 0tgwxw x模式識別 緒論線性判別函數(shù)的增廣形式線性判別函數(shù)的增廣形式py=(1, x1, x2, xd)t: 增廣的特征矢量；增廣的特征矢量；pa=(w0, w1, w2, , wd)t: 增廣的權(quán)矢量；增廣的權(quán)矢量； tgya y模式識別 緒論兩類問題線性判別準(zhǔn)則兩類問題線性判別準(zhǔn)則 1020,0,0,tgwxxw xx拒識模式識別 緒論線性分類器的分類界面線性分類器的分類界面模式識別 緒論分類界面的幾何解釋分類界面的幾何解釋1.線性分類界面線性分類界

58、面H是是d維空間中的一個超平面；維空間中的一個超平面；2.分類界面將分類界面將d維空間分成兩部分，維空間分成兩部分，R1，R2分分別屬于兩個類別；別屬于兩個類別；3.判別函數(shù)的權(quán)矢量判別函數(shù)的權(quán)矢量w是一個垂直于分類界面是一個垂直于分類界面H的矢量，其方向指向區(qū)域的矢量，其方向指向區(qū)域R1 ；4.偏置偏置w0與原點(diǎn)到分類界面與原點(diǎn)到分類界面H的距離有關(guān)：的距離有關(guān)：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模式識別 緒論多類問題（情況二）分類界面多類問題（情況二）分類界面模式識別 緒論多類問題（情況二）判別準(zhǔn)則多類問題（情況二）判別準(zhǔn)則p如果對任意如果對任意ji ，有，有g(shù)ij(x)0 ，則決策，則決策x屬于屬于i。 p其它情況，則拒識。其它情況，則拒識。模式識別 緒論多類問題（情況三）多類問題（情況三）p情況三是情況二的特例，不存在拒識區(qū)域。情況三是情況二的特例，不存在拒識區(qū)域。 模式識別 緒論多類問題（情況三）判別函數(shù)多類問題（情況三）判別函數(shù)pc個類別需要個類別需要c個線性函數(shù)