模式識(shí)別特征選擇和提取PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1模式識(shí)別模式識(shí)別(m sh sh bi)特征選擇和提特征選擇和提取取第一頁，共46頁。第1頁/共46頁第二頁，共46頁。第2頁/共46頁第三頁，共46頁。第3頁/共46頁第四頁，共46頁。第4頁/共46頁第五頁，共46頁。第5頁/共46頁第六頁，共46頁。n另一種方式是用映射（或稱變換）的方法把原始特征變換為較少的特征，稱之為特征提取。第6頁/共46頁第七頁，共46頁。第7頁/共46頁第八頁，共46頁。第8頁/共46頁第九頁，共46頁。u類別可分離性判據(jù)：衡量不同特征及其組合對(duì)分類是否有效的定量準(zhǔn)則u理想準(zhǔn)則：某組特征使分類器錯(cuò)誤概率最小u實(shí)際的類別可分離性判據(jù)應(yīng)滿足的條件：u度量特性

2、：u與錯(cuò)誤率有單調(diào)關(guān)系u當(dāng)特征獨(dú)立時(shí)有可加性：u單調(diào)性：u常見(chn jin)類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)0, if ;0, if ;ijijijjiJij Jij JJ121(,.,)()dijdijkkJx xxJx12121(,.,)(,.,)ijdijddJx xxJx xxx第9頁/共46頁第十頁，共46頁。u類間可分性:=所有(suyu)樣本間的平均距離：( )( )111111( )(,)2jinnccijdijklijklijJPPnn xxx(8-1)( )( )( )( )( )( )(,)() ()ijijTijklklklxxxxxxsquared E

3、uclidian( )11iniikkinmx1ciiiPmm( )111( )(,)(,)incidikiiikiJPnxxmm m(8-5)類內(nèi)平均(pngjn)距離類間距離(jl)1111(,)(,)2ccciiijijiijPPP m mm m(8-6)第10頁/共46頁第十一頁，共46頁。1()()cTbiiiiSPmm mm( )( )111()()inciiTwikikiikiSPnxmxm( )tr()dwbJSSx基于(jy)距離的準(zhǔn)則概念直觀，計(jì)算方便，但與錯(cuò)誤率沒有直接聯(lián)系樣本(yngbn)類間離散度矩陣樣本(yngbn)類內(nèi)離散度矩陣類間可分離性判據(jù)第11頁/共46頁第

4、十二頁，共46頁。第12頁/共46頁第十三頁，共46頁。u特征選擇:=從原始特征中挑選出一些最有代表性、分類性能最好的特征進(jìn)行分類。u從D個(gè)特征中選取d個(gè),共CdD種組合。若不限定特征選擇個(gè)數(shù)，則共2D種組合 典型的組合優(yōu)化問題u特征選擇的方法大體可分兩大類：uFilter方法：根據(jù)獨(dú)立于分類器的指標(biāo)J來評(píng)價(jià)(pngji)所選擇的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作為最優(yōu)特征子集。不考慮所使用的學(xué)習(xí)算法。uWrapper方法：將特征選擇和分類器結(jié)合在一起，在學(xué)習(xí)過程中表現(xiàn)優(yōu)異的的特征子集會(huì)被選中。dDC第13頁/共46頁第十四頁，共46頁。經(jīng)典(jngdin)特征

5、選擇算法u許多特征選擇算法力求(lqi)解決搜索問題，經(jīng)典算法有：u分支定界法: 最優(yōu)搜索，效率比盲目窮舉法高。u單獨(dú)最優(yōu)特征組合法：次優(yōu)搜索。u順序后退法u順序前進(jìn)法u模擬退火法uTabu搜索法u遺傳算法特征(tzhng)選擇第14頁/共46頁第十五頁，共46頁。單獨(dú)最優(yōu)特征(tzhng)組合u計(jì)算各特征單獨(dú)使用時(shí)的可分性判據(jù)J并加以排隊(duì)，取前d個(gè)作為選擇結(jié)果u不一定是最優(yōu)結(jié)果u當(dāng)可分性判據(jù)對(duì)各特征具有(廣義)可加性，該方法可以(ky)選出一組最優(yōu)的特征來，例：u各類具有正態(tài)分布u各特征統(tǒng)計(jì)獨(dú)立u可分性判據(jù)基于Mahalanobis距離1( )()()TDijijJx121(,.,)()di

6、jdijkkJx xxJx特征(tzhng)選擇第15頁/共46頁第十六頁，共46頁。順序(shnx)前進(jìn)法u自下而上搜索方法。u每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得的J值為最大，直至特征數(shù)增加(zngji)到d為止。u該方法考慮了所選特征與已入選特征之間的相關(guān)性。特征(tzhng)選擇第16頁/共46頁第十七頁，共46頁。順序(shnx)后退法u該方法根據(jù)特征子集的分類(fn li)表現(xiàn)來選擇特征u搜索特征子集：從全體特征開始，每次剔除一個(gè)特征，使得所保留的特征集合有最大的分類(fn li)識(shí)別率u依次迭代，直至識(shí)別率開始下降為止特征(tzhng)選擇第17

7、頁/共46頁第十八頁，共46頁。遺傳算法u從生物進(jìn)化論得到啟迪。遺傳，變異，自然選擇。u基因鏈碼：待解問題的解的編碼，每個(gè)基因鏈碼也稱為一個(gè)個(gè)體。對(duì)于特征選擇，可用一個(gè)D位的0/1構(gòu)成的串表示一種特征組合。u群體：若干個(gè)個(gè)體的集合，即問題的一些解的集合。u交叉：由當(dāng)前兩個(gè)個(gè)體的鏈碼交叉產(chǎn)生新一代的個(gè)體。u變異：由一個(gè)鏈碼隨機(jī)(su j)某基因使其翻轉(zhuǎn)。特征(tzhng)選擇第18頁/共46頁第十九頁，共46頁。遺傳算法u適應(yīng)度：每個(gè)個(gè)體(gt)xi的函數(shù)值fi，個(gè)體(gt)xi越好，fi越大。新一代群體對(duì)環(huán)境的平均適應(yīng)度比父代高。u遺傳算法的基本框架：特征(tzhng)選擇第19頁/共46頁第

8、二十頁，共46頁。6.5 討論(toln)u特征的選擇與提取是模式識(shí)別中重要而困難的一步u模式識(shí)別的第一步：分析各種特征的有效性并選出最有代表性的特征u降低特征維數(shù)在很多情況下是有效設(shè)計(jì)分類器的重要課題u三大類特征：物理、結(jié)構(gòu)和數(shù)學(xué)特征u物理和結(jié)構(gòu)特征：易于為人的直覺感知，但難于定量描述，因而(yn r)不易用機(jī)器判別u數(shù)學(xué)特征：易于用機(jī)器定量描述和判別第20頁/共46頁第二十一頁，共46頁。n則，間接判斷每一種子集的優(yōu)劣。n對(duì)于獨(dú)立特征的選擇準(zhǔn)則n一般特征的散布矩陣準(zhǔn)則第21頁/共46頁第二十二頁，共46頁。(dl)地進(jìn)行分析，從中選出m個(gè)最好的作為分類特征即可。n例：對(duì)于i和j兩類訓(xùn)練樣本

9、的特征選擇第22頁/共46頁第二十三頁，共46頁。第23頁/共46頁第二十四頁，共46頁。需要有足夠數(shù)量的模式樣本才能獲得有效的結(jié)果。第24頁/共46頁第二十五頁，共46頁。第25頁/共46頁第二十六頁，共46頁。第26頁/共46頁第二十七頁，共46頁。6.3 特征提取與K-L變換(binhun)u特征提取：用映射（或變換）的方法把原始特征變換為較少的新特征uPCA (Principle Component Analysis)方法：進(jìn)行特征降維變換，不能完全地表示(biosh)原有的對(duì)象，能量總會(huì)有損失。希望找到一種能量最為集中的的變換方法使損失最小。uK-L (Karhunen-Loeve)

10、變換：最優(yōu)正交線性變換，相應(yīng)的特征提取方法被稱為PCA方法(*)argm ax()JJxxx第27頁/共46頁第二十八頁，共46頁。K-L變換(binhun)u離散K-L變換：對(duì)向量(xingling)x用確定的完備正交歸一向量(xingling)系uj展開1jjjyxuTijijuuTjjy uxxy特征(tzhng)提取第28頁/共46頁第二十九頁，共46頁。離散K-L變換(binhun)的均方誤差u用有限(yuxin)項(xiàng)估計(jì)x ：1djjjyxu()()TExxxx211TTjjjjdjdEyEuxxuE ()Tijijrx xE Rxx11TTTjjjjjdjdEuxxuuR uTjj

11、y ux特征提取第29頁/共46頁第三十頁，共46頁。求解(qi ji)最小均方誤差正交基u用Lagrange乘子法：1if then TjjjjjjdR uuuR u 取 得 極 值1jjd特征提取第30頁/共46頁第三十一頁，共46頁。求解(qi ji)最小均方誤差正交基u用Lagrange乘子法：1if then TjjjjjjdR uuuR u 取 得 極 值1jjd特征提取第31頁/共46頁第三十二頁，共46頁。K-L變換(binhun)的表示uK-L變換的向量(xingling)展開表示：Tjjy uxuK-L變換(binhun)的矩陣表示：12,.,dxuuuyU yTyUx1d

12、jjjyxu特征提取第32頁/共46頁第三十三頁，共46頁。K-L變換(binhun)的性質(zhì)uy的相關(guān)矩陣是對(duì)角的相關(guān)矩陣是對(duì)角(du jio)矩陣：矩陣：TTTTijijijTTijijjiijEy yEER uxxuuxxuuuuuTTTTEEUUUUy yxxR特征(tzhng)提取第33頁/共46頁第三十四頁，共46頁。K-L變換(binhun)的性質(zhì)1200duK-L坐標(biāo)系把矩陣R對(duì)角化，即通過K-L變換消除原有向量x的各分量間的相關(guān)性，從而有可能去掉那些帶有較少信息的分量以達(dá)到(d do)降低特征維數(shù)的目的特征(tzhng)提取第34頁/共46頁第三十五頁，共46頁。K-L變換的數(shù)

13、據(jù)壓縮(sh j y su)圖解u取2x1變換矩陣U=u1，則x的K-L變換y為： y = UTx = u1T x = y1u變換的能量(nngling)損失為2222221215.9 %41特征(tzhng)提取第35頁/共46頁第三十六頁，共46頁。K-L變換的產(chǎn)生(chnshng)矩陣u數(shù)據(jù)集KN=xi的K-L變換的產(chǎn)生矩陣由數(shù)據(jù)的二階統(tǒng)計(jì)量決定(judng)，即K-L坐標(biāo)系的基向量為某種基于數(shù)據(jù)x的二階統(tǒng)計(jì)量的產(chǎn)生矩陣的本征向量uK-L變換的產(chǎn)生矩陣可以有多種選擇：ux的相關(guān)函數(shù)矩陣R=ExxTux的協(xié)方差矩陣C=E(x-) (x-)Tu樣本總類內(nèi)離散度矩陣：1,E()(),cTwii

14、iiiiiSPxxx特征(tzhng)提取第36頁/共46頁第三十七頁，共46頁。未知類別樣本(yngbn)的K-L變換u用總體樣本的協(xié)方差矩陣C=E(x-) (x-)T進(jìn)行K-L變換，K-L坐標(biāo)系U=u1,u2,.,ud按照(nzho)C的本征值的下降次序選擇u例：設(shè)一樣本集的協(xié)方差矩陣是：求最優(yōu)2x1特征提取器U解答：計(jì)算特征值及特征向量V, D=eig(C);特征值D=24.736, 2.263T,特征向量:由于12，故最優(yōu)2x1特征提取器此時(shí)的K-L變換式為：19.59.59.57.5C0.8750.4820.4820.875V10.8750.482Uu120.8750.482TTxUxyxux特征(tzhng)提取第37頁/共46頁第三十八頁，共46頁。第38頁/共46頁第三十九頁，共46頁。