1、 模式識別原理與應(yīng)用模式識別原理與應(yīng)用 專專 業(yè)：業(yè)： 模式識別與智能系統(tǒng)模式識別與智能系統(tǒng) 學(xué)生姓名：學(xué)生姓名： * 任課教師：任課教師： 余老師余老師一、基本概念u特征的選擇與提取特征的選擇與提取是模式識別中重要而困是模式識別中重要而困難的一個(gè)環(huán)節(jié)：難的一個(gè)環(huán)節(jié)：分析各種特征的有效性并選出最有代表性的特分析各種特征的有效性并選出最有代表性的特征是模式識別的關(guān)鍵一步。征是模式識別的關(guān)鍵一步。降低特征維數(shù)在很多情況下是有效設(shè)計(jì)分類器降低特征維數(shù)在很多情況下是有效設(shè)計(jì)分類器的重要課題。的重要課題。引言特征的形成信號獲取或測量原始測量原始特征u實(shí)例數(shù)字圖象中的各像素灰度值人體的各種生理指標(biāo)u原始特

2、征分析：原始測量很大程度上不能反映對象本質(zhì)高維原始特征不利于分類器設(shè)計(jì)：計(jì)算量大，冗余，樣本分布十分稀疏。引言二、特征的選擇與提取u兩類提取有效信息、壓縮特征空間的方法：兩類提取有效信息、壓縮特征空間的方法：特征提取和特征選擇特征提取和特征選擇u特征提取特征提取 (extraction)用映射（或變換）用映射（或變換）的方法把原始特征變換為較少的新特征的方法把原始特征變換為較少的新特征u特征選擇特征選擇(selection)從原始特征中挑選出從原始特征中挑選出一些最有代表性，分類性能最好的特征。一些最有代表性，分類性能最好的特征。u特征的選擇與提取與具體問題有很大關(guān)系，特征的選擇與提取與具體問

3、題有很大關(guān)系，目前沒有理論能給出對任何問題都有效的目前沒有理論能給出對任何問題都有效的特征選擇與提取方法。特征選擇與提取方法。特征的選擇與提取舉例u細(xì)胞自動識別：原始測量：（正常與異常）細(xì)胞的數(shù)字圖像原始特征（特征的形成，找到一組代表細(xì)胞性質(zhì)的特征）：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，核漿比壓縮特征：原始特征的維數(shù)仍很高，需壓縮以便于分類 特征選擇：挑選最有分類信息的特征 特征提?。簲?shù)學(xué)變換 傅立葉變換或小波變換 用PCA方法作特征壓縮三、特征提取與K-L變換u特征提?。河糜成洌ɑ蜃儞Q）的方法把原始特征變換為較少的新特征uPCA (Principle Component Anal

4、ysis)方法：進(jìn)行特征降維變換，不能完全地表示原有的對象，能量總會有損失。希望找到一種能量最為集中的的變換方法使損失最小。uK-L (Karhunen-Loeve)變換：最優(yōu)正交線性變換，相應(yīng)的特征提取方法被稱為PCA方法 特征值特征值100kkkNNANkNAIN對于一個(gè)的矩陣 ，有 個(gè)標(biāo)量 ，滿足稱為矩陣的一組特征值。如果給定的矩陣是奇異的，那么 個(gè)特征值中至少有一個(gè)為 。矩陣的秩 定義為矩陣非零特征值的個(gè)數(shù)。矩陣的條件數(shù) 定義為最大特征值與最小特征值的比值的絕對值。病態(tài)矩陣 條件數(shù)很大。212122112140211 3A 例： 特征向量特征向量1,0kkkkkkNvAvvAvAV滿足

5、下式的的向量則 稱為 的特征向量。求特征向量的方法是解線性方程組11122212212211 0 2212213 0 221Avvvv 例： 求其特征向量。K-L變換 離散K-L變換：對向量x用標(biāo)準(zhǔn)正交向量系uj進(jìn)行線性變換，得到新的向量Y. 經(jīng)過KL變換組合，輸出Y的各分量之間將具有最小的相關(guān)性.1jjjyxuTjjy ux:Lxy特征提取離散K-L變換的均方誤差u用有限項(xiàng)估計(jì)x ：1djjjyxu()()TExxxx211TTjjjjdjdEyEuxxuE ()Tijijrx xE Rxx11TTTjjjjjdjdEuxxuuR u特征提取因?yàn)閡j是確定性向量，所以有求解最小均方誤差正交基

6、u用Lagrange乘子法，可以求出滿足正交條件下的取極值時(shí)的坐標(biāo)系統(tǒng)：1if then TjjjjjjdR uuuR u 取 得 極 值u結(jié)論：以相關(guān)矩陣R R的d個(gè)特征向量uj為基向量來展開x x時(shí)，其截?cái)嗑秸`差取得最小值為：1jjduK-L變換：當(dāng)取矩陣R R的d個(gè)最大特征值對應(yīng)的特征向量來展開x x時(shí)，其截?cái)嗑秸`差最小。這d個(gè)特征向量組成的正交坐標(biāo)系稱作x x所在的D維空間的d維K-L變換坐標(biāo)系， x x在K-L坐標(biāo)系上的展開系數(shù)向量y y稱作x x的K-L變換特征提取K-L變換的表示uK-L變換的變換的向量展開表示向量展開表示：Tjjy uxuK-L變換的變換的矩陣表示矩陣表示：

7、12,.,dxuuuyU yTyUx1djjjyxu特征提取K-L變換的性質(zhì)uy的相關(guān)矩陣是對角矩陣：TTTTijijijTTijijjiijEy yEER uxxuuxxuuuuuTTTTEEUUUUy yxxR特征提取K-L變換的性質(zhì)1200duK-L坐標(biāo)系把矩陣坐標(biāo)系把矩陣R R對角化，即對角化，即通過通過K-L變變換消除原有向量換消除原有向量x的各分量間的相關(guān)性的各分量間的相關(guān)性，從而有可能去掉那些帶有較少信息的分從而有可能去掉那些帶有較少信息的分量以達(dá)到降低特征維數(shù)的目的量以達(dá)到降低特征維數(shù)的目的特征提取主成分分析主成分分析 ( PCA ) 主分量分析（主分量分析（Primary C

8、omponent Analysis, PCA）就）就是基于是基于K-L變換的提取圖像特征的一種最優(yōu)正交線性變變換的提取圖像特征的一種最優(yōu)正交線性變換，可以有效去掉一個(gè)隨機(jī)向量中各元素間的相關(guān)性。換，可以有效去掉一個(gè)隨機(jī)向量中各元素間的相關(guān)性。PCA的目的：尋找能夠表示采樣數(shù)據(jù)的最好的投影子的目的：尋找能夠表示采樣數(shù)據(jù)的最好的投影子空間空間. PCA的求解：特征向量常被叫做的求解：特征向量常被叫做“主分量主分量”，每個(gè)樣，每個(gè)樣本被它在前幾個(gè)主分量上的投影近似表示，本被它在前幾個(gè)主分量上的投影近似表示，U張成的空張成的空間稱為原空間的子空間，間稱為原空間的子空間，PCA實(shí)際上就是在子空間上的實(shí)際

9、上就是在子空間上的投影投影. 從幾何意義來看，變換后的主分量空間坐標(biāo)系與變從幾何意義來看，變換后的主分量空間坐標(biāo)系與變換前的空間坐標(biāo)系相比旋轉(zhuǎn)了一個(gè)角度。而且新坐標(biāo)系的換前的空間坐標(biāo)系相比旋轉(zhuǎn)了一個(gè)角度。而且新坐標(biāo)系的坐標(biāo)軸一定指向數(shù)據(jù)信息量較大的方向。以二維空間為例，坐標(biāo)軸一定指向數(shù)據(jù)信息量較大的方向。以二維空間為例，假定某樣本的分布呈橢圓狀，那么經(jīng)過旋轉(zhuǎn)后，新坐標(biāo)系假定某樣本的分布呈橢圓狀，那么經(jīng)過旋轉(zhuǎn)后，新坐標(biāo)系的坐標(biāo)軸一定分別指向橢圓的長半軸和短半軸方向的坐標(biāo)軸一定分別指向橢圓的長半軸和短半軸方向主主分量方向，因?yàn)殚L半軸這一方向的信息量最大。分量方向，因?yàn)殚L半軸這一方向的信息量最大。x

10、1x2u2u1主成分是這個(gè)橢圓的長軸方向。短軸的方向和長軸垂直，是第二個(gè)主成分的方向。變換后的各分量，它們所包括的信息量不同，呈逐漸減少趨勢。事實(shí)上，第一主分量集中了最大的信息量，常常占80以上。第二、三主分量的信息量依次很快遞減，到了第n分量，信息幾乎為零。Principalcomponent PCA對于橢球狀分布的樣本集有很好的效果對于橢球狀分布的樣本集有很好的效果, 學(xué)習(xí)所學(xué)習(xí)所得的主方向就是橢球的主軸方向得的主方向就是橢球的主軸方向. PCA 是一種非監(jiān)督的算法是一種非監(jiān)督的算法, 能找到很好地代表所有樣能找到很好地代表所有樣本的方向本的方向, 但這個(gè)方向?qū)τ诜诸愇幢厥亲钣欣牡@個(gè)方

11、向?qū)τ诜诸愇幢厥亲钣欣?人臉識別就是將已檢測到的待識別人臉與數(shù)據(jù)庫中的已知人臉進(jìn)行比較匹配，得出相關(guān)信息，來鑒別該人是誰。這一過程的核心是選擇恰當(dāng)?shù)娜四槺碚鞣绞脚c匹配策略，即選擇合適的人臉模式的特征，根據(jù)所提取的特征進(jìn)行匹配。 人臉圖像所包含的模式特征十分豐富,它不僅包括一些能直觀感覺到的特征，如膚色、發(fā)色等顏色特征，臉的輪廓等輪廓特征，用到的更多的是不能感覺，只能通過變換等處理之后才表現(xiàn)出來的特征，如特征臉、小波特征等變換域特征，均值、方差等模板特征。人臉特征表述人臉特征表述 基于基于PCA構(gòu)建特征臉空間是對圖像進(jìn)行構(gòu)建特征臉空間是對圖像進(jìn)行K-L變換，以去除樣變換，以去除樣本間的相關(guān)性，

12、然后根據(jù)特征值的大小選擇特征向量。本間的相關(guān)性，然后根據(jù)特征值的大小選擇特征向量。 這種方法首先將人臉圖像映射為高維空間的向量，然后應(yīng)這種方法首先將人臉圖像映射為高維空間的向量，然后應(yīng)用基于統(tǒng)計(jì)的離散用基于統(tǒng)計(jì)的離散K-L變換方法，構(gòu)造一個(gè)各分量互不相變換方法，構(gòu)造一個(gè)各分量互不相關(guān)的特征空間，即特征臉空間，再將人臉圖像在高維空間關(guān)的特征空間，即特征臉空間，再將人臉圖像在高維空間中的向量映射到特征臉空間，得到特征系數(shù)。中的向量映射到特征臉空間，得到特征系數(shù)。PCA構(gòu)建特征臉空間構(gòu)建特征臉空間 ORL標(biāo)準(zhǔn)人臉庫由40人，每人10幅11292圖像組成。這些圖像是拍攝于不同時(shí)期的；人的臉部表情和臉部

13、細(xì)節(jié)有著不同程度的變化，比如，笑或不笑，眼睛或睜或閉，戴或不戴眼鏡；人臉姿態(tài)也有相當(dāng)程度的變化，深度旋轉(zhuǎn)和平面旋轉(zhuǎn)可達(dá)20度；人臉的尺度也有多達(dá)10的變化。ORL人臉庫人臉庫(英國劍橋大學(xué)英國劍橋大學(xué)) M幅人臉圖像樣本，其圖像矩陣 ，將它們轉(zhuǎn)化為向量 形式，得到M個(gè)維向量 MTTT,21M,21MnnM11 均值差值nnn圖像集的協(xié)方差矩陣 TMnTnnAAMC11), 2 , 1(Mii), 2 , 1(Miui特征值特征向量 可以從以上求得的M個(gè)特征向量中取出對構(gòu)造圖像影響最大的m個(gè)，這樣就可以構(gòu)造了一個(gè)原始圖像空間的m維子空間，這個(gè)m維子空間稱為特征臉空間。 ,圖像集的協(xié)方差矩陣 TM

14、nTnnAAMC11), 2 , 1(Mii特征值特征向量,特征值與特征圖像特征值與特征圖像 特征值ORL 20人 10幅 特征臉空間特征提取LDA 線性判別分析：線性判別分析：LinearDiscriminantAnalysis (LDA) Fisher(1936)在線性判別函數(shù)一章，我們講過在線性判別函數(shù)一章，我們講過Fisher線性判線性判別函數(shù)。它的思想是，找一個(gè)方向作投影，使得別函數(shù)。它的思想是，找一個(gè)方向作投影，使得投影后的數(shù)據(jù)類間距盡可能大，類內(nèi)距盡可能小。投影后的數(shù)據(jù)類間距盡可能大，類內(nèi)距盡可能小。這實(shí)際上是兩類數(shù)據(jù)的特征提取，提取的特征數(shù)這實(shí)際上是兩類數(shù)據(jù)的特征提取，提取的特

15、征數(shù)是。這一思想可以推廣到任意類數(shù)據(jù)，提取任是。這一思想可以推廣到任意類數(shù)據(jù)，提取任意多個(gè)特征。意多個(gè)特征。 LDA的思想的思想: 尋找最能把兩類樣本分開的投影直線尋找最能把兩類樣本分開的投影直線. LDA的目標(biāo)的目標(biāo): 使投影后兩類樣本的均值之差與投影使投影后兩類樣本的均值之差與投影樣本的總類散布的比值最大樣本的總類散布的比值最大 . LDA的求解的求解: 經(jīng)過推導(dǎo)把原問題轉(zhuǎn)化為關(guān)于樣本集經(jīng)過推導(dǎo)把原問題轉(zhuǎn)化為關(guān)于樣本集總類內(nèi)散布矩陣和總類間散布矩陣的廣義特征值總類內(nèi)散布矩陣和總類間散布矩陣的廣義特征值問題問題.Best projection direction for classifica

16、tion多重判別分析多重判別分析 (MDA) MDA把把LDA推廣到多類的情況推廣到多類的情況. 對于對于c-類問題類問題, MDA把樣本投影到把樣本投影到 c-1 維子空間維子空間. 目標(biāo)和解法與目標(biāo)和解法與LDA相似相似,只是類內(nèi)散布矩陣的定只是類內(nèi)散布矩陣的定義義更為復(fù)雜更為復(fù)雜, 求解的廣義特征值問題也更為復(fù)雜求解的廣義特征值問題也更為復(fù)雜.-1-0.500.51-1-0.500.5105101520線性方法的缺點(diǎn)線性方法的缺點(diǎn) 線性方法對于很多數(shù)據(jù)不能進(jìn)行有效的處理線性方法對于很多數(shù)據(jù)不能進(jìn)行有效的處理. 現(xiàn)實(shí)中數(shù)據(jù)的有用特性往往不是特征的現(xiàn)實(shí)中數(shù)據(jù)的有用特性往往不是特征的線性線性組

17、合組合.幾種流形學(xué)習(xí)算法幾種流形學(xué)習(xí)算法 局部線性嵌入局部線性嵌入(LLE).S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, pp. 2323-2326, 2000. 等距映射等距映射(Isomap).J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality redu

18、ction. Science, vol. 290, pp. 2319-2323, 2000. 拉普拉斯特征映射拉普拉斯特征映射(Laplacian Eigenmap).M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 1396, 2003 . 在這個(gè)例子里，用在這個(gè)例子里，用LLE LLE 進(jìn)行降維成功的體現(xiàn)了數(shù)進(jìn)行降維成功的體現(xiàn)了數(shù)據(jù)內(nèi)在的局部分布結(jié)構(gòu)，而用據(jù)

19、內(nèi)在的局部分布結(jié)構(gòu)，而用PCA PCA 映射則會將高維空映射則會將高維空間里的遠(yuǎn)點(diǎn)映射到低維空間后變成了近鄰點(diǎn)。間里的遠(yuǎn)點(diǎn)映射到低維空間后變成了近鄰點(diǎn)。u特征選擇:=從原始特征中挑選出一些最有代表性、分類性能最好的特征進(jìn)行分類。u從D個(gè)特征中選取d個(gè),共CdD種組合。 典型的組合優(yōu)化問題u特征選擇的方法大體可分兩大類：Filter方法：根據(jù)獨(dú)立于分類器的指標(biāo)J來評價(jià)所選擇的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作為最優(yōu)特征子集。不考慮所使用的學(xué)習(xí)算法。 Wrapper方法：將特征選擇和分類器結(jié)合在一起，即特征子集的好壞標(biāo)準(zhǔn)是由分類器決定的，在學(xué)習(xí)過程中表現(xiàn)優(yōu)異的的特征

20、子集會被選中。四、特征的選擇dDC一種Filter算法: FOCUS 該算法致力于尋找一個(gè)能夠正確區(qū)分所有該算法致力于尋找一個(gè)能夠正確區(qū)分所有類別的最小特征集合。類別的最小特征集合。例如，區(qū)分每個(gè)人的特征有：姓名、例如，區(qū)分每個(gè)人的特征有：姓名、性別、籍貫、工作單位、身份證號性別、籍貫、工作單位、身份證號 則該算法會選擇：身份證號則該算法會選擇：身份證號搜索時(shí)先看一個(gè)特征能能正確區(qū)分樣搜索時(shí)先看一個(gè)特征能能正確區(qū)分樣本，不能，則考察兩個(gè)特征本，不能，則考察兩個(gè)特征以此類推以此類推經(jīng)典特征選擇算法u許多特征選擇算法力求解決搜索問題，經(jīng)典算法有：分支定界法單獨(dú)最優(yōu)特征組合法順序后退法順序前進(jìn)法模擬

21、退火法Tabu搜索法遺傳算法特征選擇順序前進(jìn)法u自下而上搜索方法。u每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得的J值為最大，直至特征數(shù)增加到d為止。u該方法考慮了所選特征與已入選特征之間的相關(guān)性。特征選擇順序后退法u該方法根據(jù)特征子集的分類表現(xiàn)來選擇特征u搜索特征子集：從全體特征開始，每次剔除一個(gè)特征，使得所保留的特征集合有最大的分類識別率u依次迭代，直至識別率開始下降為止u用“l(fā)eave-one-out”方法估計(jì)平均識別率：用N-1個(gè)樣本判斷余下一個(gè)的類別，N次取平均特征選擇遺傳算法u從生物進(jìn)化論得到啟迪。遺傳，變異，自然選擇。u基因鏈碼：待解問題的解的編碼，每個(gè)

22、基因鏈碼也稱為一個(gè)個(gè)體。對于特征選擇，可用一個(gè)D位的0/1構(gòu)成的串表示一種特征組合。u群體：，干個(gè)個(gè)體的集合，即問題的一些解的集合。u交叉：由當(dāng)前兩個(gè)個(gè)體的鏈碼交叉產(chǎn)生新一代的個(gè)體。u變異：由一個(gè)鏈碼隨機(jī)某基因使其翻轉(zhuǎn)。特征選擇遺傳算法u適應(yīng)度：每個(gè)個(gè)體xi的函數(shù)值fi，個(gè)體xi越好，fi越大。新一代群體對環(huán)境的平均適應(yīng)度比父代高。u遺傳算法的基本框架：特征選擇Initialsolutionsstart1100101010101110111000110110011100110001encodingchromosome110010101010111011101100101110101110101

23、000110110010011001001crossovermutation110010111010111010100011001001solutions candidatesdecodingfitness computationevaluationroulette wheelselectiontermination condition?YNbest solutionstop newpopulationoffspringoffspringt 0 P(t)CC(t)CM(t)P(t) + C(t)遺傳算法的求解步驟模擬退火法u模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在 每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。u用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到 解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終 止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。 特征選擇u假設(shè)材料在狀態(tài)i的能量為E(i)，那么材料在溫度T時(shí)從狀態(tài)i進(jìn)入狀態(tài)j遵循如下規(guī)律：如果E(j) E(i)，接受該狀態(tài)被轉(zhuǎn)換。如果E(j)E(i)，則狀態(tài)轉(zhuǎn)換以