模式識(shí)別之特征選擇與提取

1、特征選擇與特征提取特征選擇與特征提取5.1 基本概念基本概念5.2 類別可分性測(cè)度類別可分性測(cè)度5.3 基于類內(nèi)散布矩陣的單類模式特征提取基于類內(nèi)散布矩陣的單類模式特征提取5.4 基于基于K-L變換的多類模式特征提取變換的多類模式特征提取第第5章章 特征選擇與特征提取特征選擇與特征提取5.1 基本概念基本概念 由于測(cè)量上可實(shí)現(xiàn)性的限制或經(jīng)濟(jì)上的考慮，所獲得的測(cè)量值為數(shù)不多。 能獲得的性質(zhì)測(cè)量值很多。如果全部直接作為分類特征，耗費(fèi)機(jī)時(shí)，且分類效果不一定好。有人稱之為“特征維數(shù)災(zāi)難”。 特征選擇和提取的目的特征選擇和提取的目的：經(jīng)過選擇或變換，組成識(shí)別特征，盡可能保留分類信息，在保證一定分類精度的

2、前提下，減少特征維數(shù)，使分類器的工作即快又準(zhǔn)確。1兩種數(shù)據(jù)測(cè)量情況兩種數(shù)據(jù)測(cè)量情況(1) 具有很大的識(shí)別信息量。即應(yīng)具有很好的可分性。(2) 具有可靠性。模棱兩可、似是而非、時(shí)是時(shí)非等不易判別 的特征應(yīng)丟掉。(3) 盡可能強(qiáng)的獨(dú)立性。重復(fù)的、相關(guān)性強(qiáng)的特征只選一個(gè)。(4) 數(shù)量盡量少，同時(shí)損失的信息盡量小。2對(duì)特征的要求對(duì)特征的要求3. 特征選擇和特征提取的異同特征選擇和特征提取的異同（1）特征選擇：從L個(gè)度量值集合 中按一定準(zhǔn) 則選出供分類用的子集，作為降維（m維，m L）的分類 特征。Lxxx,21（2）特征提取：使一組度量值 通過某種變換 產(chǎn)生新的m個(gè)特征 ，作為降維的分類特征， 其中

3、。),(21Lxxxih),(21myyyLmmi;, 2 , 1(c)是具有分類能力的特征，故選(c)，扔掉(a) 、 (b) 。BA解：法1 特征抽?。簻y(cè)量三個(gè)結(jié)構(gòu)特征 (a) 周長(zhǎng) (b) 面積 (c)兩個(gè)互相垂直的內(nèi)徑比 特征選擇：一般根據(jù)物理特征或結(jié)構(gòu)特征進(jìn)行壓縮。 分析：例：特征選擇與特征提取的區(qū)別：對(duì)一個(gè)條形和圓進(jìn)行識(shí)別。 當(dāng)模式在空間中發(fā)生移動(dòng)、旋轉(zhuǎn)、縮放時(shí)，特征值應(yīng)保持不變，保證仍可得到同樣的識(shí)別效果。法2： 特征抽?。簻y(cè)量物體向兩個(gè)坐標(biāo)軸的投影值，則A、B各有2個(gè)值域區(qū)間。可以看出，兩個(gè)物體的投影有重疊，直接使用投影值無法將兩者區(qū)分開。 特征選擇：將坐標(biāo)系按逆時(shí)針方向做一旋

4、轉(zhuǎn)變化，或物體按順時(shí)針方向變，并適當(dāng)平移等。根據(jù)物體在 軸上投影的坐標(biāo)值的正負(fù)可區(qū)分兩個(gè)物體。2x特征提取，一般用數(shù)學(xué)的方法進(jìn)行壓縮。 BA2x1x22Bx22Ax12Bx12Ax11Bx11Ax21Bx21AxBA2x1x2x1x5.2 類別可分性測(cè)度類別可分性測(cè)度5.2.1 基于距離的可分性測(cè)度基于距離的可分性測(cè)度類別可分性測(cè)度：衡量類別間可分性的尺度。相似性測(cè)度：衡量模式之間相似性的一種尺度類內(nèi)距離和類間距離類概率密度函數(shù) 類別可分性測(cè)度空間分布：隨機(jī)模式向量： 錯(cuò)誤率 與錯(cuò)誤率有關(guān)的距離 1類內(nèi)距離和類內(nèi)散布矩陣類內(nèi)距離和類內(nèi)散布矩陣1) 類內(nèi)距離：同一類模式點(diǎn)集內(nèi)，各樣本間的均方距離

5、。 平方形式：|22jiEDXX )()(TjijiEXXXXXi,，Xj： n維模式點(diǎn)集X中的任意兩個(gè)樣本 。特征選擇和提取的結(jié)果應(yīng)使類內(nèi)散布矩陣的跡愈 ？愈好。特征選擇和提取的結(jié)果應(yīng)使類內(nèi)散布矩陣的跡愈 小小愈好。22TT2XXXXEEED 2TTMMXXEtr2TMMRtr2Cnkk122若X中的樣本相互獨(dú)立，有式中，R：該類模式分布的自相關(guān)矩陣； M：均值向量； C：協(xié)方差矩陣； ：C主對(duì)角線上的元素，表示模式向量第k個(gè)分量的方差；2k tr：矩陣的跡（方陣主對(duì)角線上各元素之和）。2) 類內(nèi)散布矩陣：表示各樣本點(diǎn)圍繞均值的散布情況,即該類分布的協(xié)方差矩陣。T()() iiEXXMMiw

6、類類間散布矩陣的跡愈大大愈有利于分類。2類間距離和類間散布矩陣類間距離和類間散布矩陣1) 類間距離：模式類之間的距離，記為 。 bD每類模式均值向量與模式總體均值向量之間平方距離的先驗(yàn)概率加權(quán)和。ciiibPD1202|)(MMciiiiP10T0)()(MMMM XME0cii, 2 , 1,XciiiP1)(M2) 類間散布矩陣：表示c類模式在空間的散布情況，記為Sb。ciiiibP1T00)()(MMMMS類間散布矩陣的跡愈？愈有利于分類。3) 類間距離與類間散布矩陣的關(guān)系：tr2bbDS注意：與類間距離的轉(zhuǎn)置位置不同。3多類模式向量間的距離和總體散布矩陣多類模式向量間的距離和總體散布矩

7、陣1）兩類情況的距離 q個(gè) p個(gè) 12共pq個(gè)距離 兩個(gè)類區(qū)之間的距離 = pq個(gè)距離的平均距離多類間任意兩個(gè)點(diǎn)間距離的平均距離類似地 多類情況多類間任意兩個(gè)點(diǎn)間平方距離的平均值inkjnljlikcjjijciidDnnPPJ11211),(1)()(21XX（5-8） inkikiin11XMi類的均值向量： （5-10） ciiiP10)(MMc類模式總體的均值向量： （5-11） 2）多類情況的距離(2) Jd的另一種形式：將以下3式代入(5-8)式(1)多類模式向量間的平均平方距離Jd)()(),(T2jlikjlikjlikDXXXXXX（5-9） 平方距離：任意類的組合特定兩類間

8、任意樣本的組合得)()()()(1)(0T01T1MMMMMXMXiiiikinkiikiciidnPJ某類類內(nèi)平方距離平均值 某類類間平方距離多類模式向量之間的平方距離=各類平方距離的先驗(yàn)概率加權(quán)和 某類的平方距離模式類間的距離模式類內(nèi)的距離多類模式向量之間的距離3）多類情況的散布矩陣ciiiibP1T00)()(MMMMS多類類間散布矩陣 ：4）多類模式平均平方距離與總體散布矩陣的關(guān)系)(tr)(trwbtdJSSS多類類內(nèi)散布矩陣： ciiiiwEP1T)()(MXMXSiXciinkiikiikinP11Ti)(1)( MXMX 各類模式協(xié)方差矩陣的 先驗(yàn)概率加權(quán)平均值。 多類模式的總

9、體散布矩陣： wbtESSMXMXS)(T00得)()()()(1)(0T01T1MMMMMXMXiiiikinkiikiciidnPJ 距離與散布矩陣作為可分性測(cè)度的特點(diǎn)： * 計(jì)算方便，概念直觀（反映模式的空間分布情況 ）； * 與分類錯(cuò)誤率沒有直接的聯(lián)系。211)|()(RdpePXX122)|()(RdpePXX)()()()()(2211ePPePPeP5.2.2 基于概率分布的可分性測(cè)度基于概率分布的可分性測(cè)度1散度散度出發(fā)點(diǎn)：對(duì)數(shù)似然比含有類別的可分性信息。 )()(lnjiijpplXX1）散度的定義 )()(lnijjipplXX 對(duì)不同的X，似然函數(shù)不同，對(duì)數(shù)似然比體現(xiàn)的可

10、分性不同，通常采用平均可分性信息對(duì)數(shù)似然比的期望值 。 i類對(duì)數(shù)似然比的期望值：XXXXdppplEIXjiiijij)()(ln)(類對(duì)數(shù)似然比的期望值：jXXXXdppplEIXijjjiji)()(ln)(散度等于兩類的對(duì)數(shù)似然比期望值之和。 XXXXXdppppIIJjiXjijiijij)()(ln)()()()(xdxxpxEXXXXXdppppIIJijXijijjiji)()(ln)()( 散度表示了區(qū)分i類和j 類的總的平均信息。2）散度的性質(zhì)（1）jiijJJXXXXXdppppIIJjiXjijiijij)()(ln)()(特征選擇和特征提取應(yīng)使散度盡可能的 ？特征選擇和

11、特征提取應(yīng)使散度盡可能的大。（3）錯(cuò)誤率分析中，兩類概率密度曲線交疊越少，錯(cuò)誤率越小。 XXXXXdppppIIJjiXjijiijij)()(ln)()(由散度的定義式可知，散度愈大，兩類概率密度函數(shù)曲線相差愈大，交疊愈少，分類錯(cuò)誤率愈小。 據(jù)此可估計(jì)每一個(gè)特征在分類中的重要性： 散度較大的特征含有較大的可分信息保留。（5）可加性表明，加入新的特征，不會(huì)使散度減小。即),(),(12121nnijnijxxxxJxxxJ3）兩個(gè)正態(tài)分布模式類的散度設(shè)i類和j 類的概率密度函數(shù)分別為 ),()(CMXiiNp),()(CMXjjNp11tr()() ()()ijijijijijJCMMMMMM

12、CMM兩類模式之間馬氏距離的平方 一維正態(tài)分布時(shí)： 22)(mmJjiij兩類均值向量距離越遠(yuǎn)，散度愈大每類自身分布愈集中，兩類間的散度愈大模式識(shí)別導(dǎo)論（齊敏）p1355.3 基于類內(nèi)散布矩陣的單類模式特征提取基于類內(nèi)散布矩陣的單類模式特征提取對(duì)某類模式：壓縮模式向量的維數(shù)。 對(duì)多類分類：壓縮維數(shù)； 保留類別間的鑒別信息，突出可分性。 特征提取的目的：特征提取操作方法：AXX *m1 mn n1 (m n)注意：維數(shù)降低后，在新的m維空間里各模式類之間的分布規(guī) 律應(yīng)至少保持不變或更優(yōu)化。討論內(nèi)容： * 根據(jù)類內(nèi)散布矩陣如何確定變換矩陣A； * 通過A如何進(jìn)行特征提取。1根據(jù)類內(nèi)散布矩陣確定變換

13、矩陣根據(jù)類內(nèi)散布矩陣確定變換矩陣 XMET)(MXMXC E式中，X為n維向量，C為 nn 的實(shí)對(duì)稱矩陣。ijij, 0, 1Tjiuu n個(gè)特征向量相互正交，且都是單位長(zhǎng)度。 若選n個(gè)歸一化特征向量作為A的行，則A為歸一化正交矩陣：TTTnuuuA21nuuuA21TIAA T)(T*MXMXC E)(TAMAXAMAX ETT)(AMXMXAETACAAMXAAXXM*EEE(1)(2)nnnnuuuuuuuuuuuunC2121212121TTTTTTn0021AnnkkuCukijij, 0, 1Tjiuu|2*2jiEDXX )()(*T*jijiEXXXX)()(TjijiEAXA

14、XAXAX)()(TTjijiEXXAAXX)()(TjijiEXXXX|2jiEXX (3) 變換后的類內(nèi)距離變換后：類內(nèi)距離保持不變 。n0021*C根據(jù)以上特點(diǎn)得到構(gòu)造變換矩陣的方法：思路：目標(biāo)：構(gòu)造一變換矩陣，可以將n維向量X變換成m維（mn）。 將變換前的C的n個(gè)特征值從小到大排隊(duì)選擇前m個(gè)小的特征值對(duì)應(yīng)的特征向量作為矩陣A的行（mn）對(duì)X進(jìn)行A變換 優(yōu)點(diǎn)：壓縮了維數(shù)； 類內(nèi)距離減小，樣本更密集 相當(dāng)去掉了方差大的特征分量。后 續(xù)nmnmnxxaaaa11111*1mxx2特征提取的方法特征提取的方法NiiiN1T)(1MXMXCNiiN11XM其中， 第二步：計(jì)算C的特征值，對(duì)特征

15、值從小到大進(jìn)行排隊(duì)，選擇 前m個(gè)。TTTmuuuA21第四步：利用A對(duì)樣本集X進(jìn)行變換。AXX *則m維（m n）模式向量X *就是作為分類用的模式向量。解：1) 求樣本均值向量和協(xié)方差矩陣。31T 3. 1, 231iiXM31TT3 . 01 . 01 . 07 . 031iiiMMXXC由 03 . 01 . 01 . 07 . 0得3 . 01 . 01 . 07 . 0C2765. 017236. 02211選由歸一化特征向量u1構(gòu)成變換矩陣A：1 . 2, 5 . 066. 41A74. 01*1 AXX48. 12*2 AXX28. 03*3 AXXT1 1, 1 XT22, 2

16、XT3 1, 3X變換前變換后5.4 基于基于K-L變換的多類模式特征提取變換的多類模式特征提取對(duì)一類模式：維數(shù)壓縮。對(duì)多類模式：維數(shù)壓縮，突出類別的可分性。 特征提取的目的： 卡洛南-洛伊（Karhunen-Loeve）變換（K-L變換）：* 一種常用的特征提取方法；* 最小均方誤差意義下的最優(yōu)正交變換；* 適用于任意的概率密度函數(shù)；* 在消除模式特征之間的相關(guān)性、突出差異性方面 有最優(yōu)的效果。離散K-L變換連續(xù)K-L變換分為：1K-L展開式展開式1jjajuXaj：隨機(jī)系數(shù)；用有限項(xiàng)估計(jì)X時(shí) ：djja1juX引起的均方誤差：)()(TXXXX E12djjaEijij, 0, 1Tjiu

17、u代入X、 ，利用X12djjaE1jjajuX由 兩邊 左乘 得 。TjuXujTja1TTdjEjjuXXu1TdjtEjjuXXuuj為確定性向量 1TdjRjjuuR：自相關(guān)矩陣。 ) 1()(1T1TdjdjgjjjjjjuuuRuuj：拉格朗日乘數(shù) 0)(jjuIR, 1 dj說明：當(dāng)用X的自相關(guān)矩陣R的特征值對(duì)應(yīng)的特征向量展開X 時(shí)，截?cái)嗾`差最小。 選前d項(xiàng)估計(jì)X時(shí)引起的均方誤差為1T11TtrdjjdjdjjjjjuRuuRu 因此，當(dāng)用X的正交展開式中前d項(xiàng)估計(jì)X時(shí)，展開式中的uj應(yīng)當(dāng)是前d個(gè)較大的特征值對(duì)應(yīng)的特征向量。) 1()(1T1TdjdjgjjjjjjuuuRuuK

18、-L變換方法：對(duì)R的特征值由大到小進(jìn)行排隊(duì)： 121dd均方誤差最小的X的近似式：djja1juXUaX ijij, 0, 1TjiuuIuuuuuuUUddTTTT2121矩陣形式： 式中， ， 。 T21,daaaa,duuuUjdn1T21,jnjjuuuju其中： （5-49） K-L展開式 對(duì)式(5-49)兩邊左乘U t ：XUaT K-L變換 系數(shù)向量a就是變換后的模式向量。 11NjjjE XXX XNR自相關(guān)矩陣2利用自相關(guān)矩陣的利用自相關(guān)矩陣的K-L變換進(jìn)行特征提取變換進(jìn)行特征提取第一步：求樣本集X的總體自相關(guān)矩陣R。 NjjjNE1TT1XXXXR,duuuU21XUXT*

19、決定壓縮后的維數(shù) 3不同散布矩陣的不同散布矩陣的K-L變換變換 根據(jù)不同的散布矩陣進(jìn)行K-L變換，對(duì)保留分類鑒別信息的效果不同。多類類內(nèi)散布矩陣： ciiiiwEP1T)()(MXMXSiX若要突出各類模式的主要特征分量： 選用對(duì)應(yīng)于大特征值的特征向量組成變換矩陣； 若要使同一類模式聚集于最小的特征空間范圍： 選用對(duì)應(yīng)于小特征值的特征向量組成變換矩陣。類間散布矩陣： ciiiibP1T00)()(MMMMS 適用于類間距離比類內(nèi)距離大得多的多類問題，選擇與大特征值對(duì)應(yīng)的特征向量組成變換矩陣?？傮w散布矩陣： wbtESSMXMXS)(T00 把多類模式合并起來看成一個(gè)總體分布。 適合于多類模式在

20、總體分布上具有良好的可分性的情況。采用大特征值對(duì)應(yīng)的特征向量組成變換矩陣，能夠保留模式原有分布的主要結(jié)構(gòu)。1）變換在均方誤差最小的意義下使新樣本集X *逼近原樣本集 X的分布，既壓縮了維數(shù)又保留了類別鑒別信息。利用K-L變換進(jìn)行特征提取的優(yōu)點(diǎn)：2）變換后的新模式向量各分量相對(duì)總體均值的方差等于原樣本 集總體自相關(guān)矩陣的大特征值，表明變換突出了模式類之間 的差異性。dE00)(21T*MXMXC3）C*為對(duì)角矩陣說明了變換后樣本各分量互不相關(guān)，亦即消 除了原來特征之間的相關(guān)性，便于進(jìn)一步進(jìn)行特征的選擇。K-L變換的不足之處： 1）對(duì)兩類問題容易得到較滿意的結(jié)果。類別愈多，效果愈差。2）需要通過足

21、夠多的樣本估計(jì)樣本集的協(xié)方差矩陣或其它類型的散布矩陣。當(dāng)樣本數(shù)不足時(shí)，矩陣的估計(jì)會(huì)變得十分粗略，變換的優(yōu)越性也就不能充分的地顯示出來。3）計(jì)算矩陣的本征值和本征向量缺乏統(tǒng)一的快速算法，給計(jì)算帶來困難。 例5.3 兩個(gè)模式類的樣本分別為利用自相關(guān)矩陣R作K-L變換，把原樣本集壓縮成一維樣本集。 解：第一步：計(jì)算總體自相關(guān)矩陣R。3 . 73 . 63 . 67 . 56161TTjjjEXXXXR第二步：計(jì)算R的本征值，并選擇較大者。由 得 0| IRT75. 0,66. 01u多類類內(nèi)散布矩陣Sw5.5 特征選擇特征選擇 從n個(gè)特征中選擇d個(gè)(d n)最優(yōu)特征構(gòu)成分類用特征向量。5.5.1 特征選取擇的準(zhǔn)則特征選取擇的準(zhǔn)則1散布矩陣準(zhǔn)則散布矩陣準(zhǔn)則類別可分性測(cè)度類間散布矩陣Sb多類總體散布矩陣St)(tr11bwJSS)(tr)(tr2wbJSSwbJSSln3wbwJSSS 4特征選擇準(zhǔn)則 使tr(Sw)最小使tr(Sb)最大使J1J4最大 2散度準(zhǔn)則散度準(zhǔn)則用于正態(tài)分布的模式類。兩類的散度表達(dá)式 )()(tr21)(tr21T1111jijijijiijijJMMMMCCC