模式識(shí)別北大十特征空間

1、第十章 特征空間10.0 引言10.1 特征提取10.2 特征選擇10.0 引言模式識(shí)別中把每個(gè)對(duì)象都量化為一組特征來描述，構(gòu)建特征空間是所有模式識(shí)別問題的第一步通過直接測(cè)量得到的特征稱為原始特征比如人體的各種生理指標(biāo)（描述其健康狀況）數(shù)字圖象中的每點(diǎn)灰度值（以描述圖像內(nèi)容）10.0 引言原始特征數(shù)量可能很大，不利于學(xué)習(xí)。比如 1024*768的灰度圖像，256灰度級(jí)。直接表示，每幅需要786,432 bytes。進(jìn)行訓(xùn) 練識(shí)別所需空間、時(shí)間、計(jì)算量都無法承受！很少的樣本分布會(huì)在如此高維的特征空間中顯得十分稀疏，因而產(chǎn)生過學(xué)習(xí)的現(xiàn)象。特征空間有很大的冗余。完全可以用很小的空間相當(dāng)好地近似表示圖

2、像，這一點(diǎn)與壓縮的思想類似。10.0 引言如何提取特征與具體問題有很大關(guān)系，特征是對(duì)象的表達(dá)，根據(jù)知識(shí)來考慮特征的穩(wěn)定性特征的可分性例：白細(xì)胞的濃度指紋的細(xì)節(jié)特征指紋細(xì)節(jié)特征10.0 引言模式識(shí)別中處理特征空間的方法可分為兩類：特征提取(Feature Extraction)：用映射（或變換）的方法把原始特征變換為新特征，稱為特征提取傅立葉變換小波變換PCA變換ICA變換Gabor變換。10.0 引言特征選擇(Feature Selection)：從原始特征中挑選出一些最有代表性、可分性能最好的特征來，稱為特征選擇10.1 特征提取10.1 特征提取特征提取的目的是希望通過變換把原來的特征變換

3、到新的特征空間，使得特征的可分性更好。PCALDA10.1 特征提取PCA12m希望通過變換，用較少的特征(y , y , y)T12n可以近似表示原來的對(duì)象x (x , x, x)，T而且誤差盡量的小。m n在所有正交線性變換中，這種最優(yōu)的變換是Karhunen-Loeve (KL)變換，相應(yīng)的特征提取方法被稱為Principle Component Analysis (PCA)。10.1 特征提取PCA正交變換給定n維空間中的一組標(biāo)準(zhǔn)正交基 1,2 ,.,n ，它誘導(dǎo)了一個(gè)線性變換：L : x yL(x) y ( y , y,., y)T12ni 1,2,., n.Tiiy x .ni1反

4、之，任何一個(gè)正交變換也確定了一組正交基。x yii .正交展開10.1 特征提取PCA誤差用m個(gè)分量表示帶來的誤差：mnx(m) x yii yii .i1im1希望誤差平方的期望最小：im1ine2 (m) E x(m) 2 E y 2 .對(duì)所有的 x求期望。10.1 特征提取PCA求解最小均方誤差正交基：首先假定隨機(jī)矢量為零均值（期望）的，否則減掉均值即可。Ex 0.找n個(gè)正交基 1,2 ,n ，使得對(duì)任意一組正交基 1,2 ,n，和所有的 m n,(m) E22im1nnim1iT2(x ).iT2(m) E) e(xe10.1 特征提取PCA對(duì)于一個(gè)固定的m min(m) min En

5、iTiim1nTTiiim1xxmin e22i 1, i m 1, m 2,ns.t. E(xxT ).協(xié)方差矩陣。10.1 特征提取PCA用Lagrange 乘子法：2 )im1im1iiTiinnmin( 得到i iii 是 的特征向量，i 是特征根。(m) nniTiiim1im1e210.1 特征提取PCA協(xié)方差矩陣的所有特征根是實(shí)數(shù)，特征向量也是實(shí)的，所有n個(gè)特征向量構(gòu)成一組標(biāo)準(zhǔn)正交基，記作 1,2 ,n ，分別對(duì)應(yīng)特征根 1 2 n .n n T T : 1T2 2112n ( ,.)10.1 特征提取PCA選擇協(xié)方差矩陣的特征向量 1,2 ,n 作為正交基，可以使得均方誤差最小

6、10.1 特征提取PCA總結(jié)：向量在協(xié)方差矩陣的特征向量上的展開稱為 Karhunen-Loeve(KL)展開，誘導(dǎo)的線性變換叫做Karhunen-Loeve變換；實(shí)際應(yīng)用中，協(xié)方差矩陣是未知的，用樣本協(xié)方差矩陣代替；10.1 特征提取PCA特征向量常被叫做“主分量”，每個(gè)樣本被它在前幾個(gè)主分量上的投影近似表示iiTiinmmiiy y (x ) .x i1i1i1特征值標(biāo)記著相應(yīng)特征向量上的能量1,2 ,m 張成的空間稱為原空間的子空間，PCA實(shí)際上是在子空間上的投影，并且222iii1221x xmmi1i11ii y ynn1ii2ii i1y y10.1 特征提取PCAPCA的問題：由

7、于用樣本協(xié)方差矩陣代 替協(xié)方差矩陣，主分量與訓(xùn)練數(shù)據(jù)有著 很大關(guān)系，用一批訓(xùn)練數(shù)據(jù)得到的主成 分，可能不反映其另外一批數(shù)據(jù)的特征。10.1 特征提取PCAPCA的例子：x1x21yy212b1b22110.1 特征提取LDA線性判別分析：Linear Discriminant Analysis (LDA)Fisher(1936), Rao(1965)在線性判別函數(shù)一章，我們講過Fisher線性判別函數(shù)。它的思想是，找一個(gè)方向作投影，使得投影后的數(shù)據(jù)類間距盡可能大，類內(nèi)距 盡可能小。這實(shí)際上是兩類數(shù)據(jù)的特征提取，提取的特征數(shù)是。這一思想可以推廣到任 意類數(shù)據(jù)，提取任意多個(gè)特征。10.1 特征提取

8、LDA準(zhǔn)則：用原來的特征表示的數(shù)據(jù)記作x n ,kbk(m m)(m m)Tijij 1S1 i, jkSw (1 2 k ).提取的特征表示的數(shù)據(jù)記作 y Wx m , W是m n 的矩陣。沿用Fisher判別函數(shù)中的記號(hào)，假設(shè)共有 k 類：類間散度矩陣類內(nèi)總散度矩陣10.1 特征提取LDA個(gè)特征表示的數(shù)據(jù)的類內(nèi)、類間散用提取的m準(zhǔn)則：求W，希望類內(nèi)距小、類間距大。度矩陣記作：TwwbbS WSW.S WS W T , tr(WSW T )1 (WS W T ).wb1 J (W ) tr(SwSb )10.1 特征提取LDA求W ：令 J (W ) 0.W得到：T1 W(SwSb ).wb

9、(S 1S)W T小技巧：對(duì)角化(SwSb ).1 1. 為對(duì)角陣11 Sb A存在矩陣 A(mm) ，使得： ASw（見習(xí)題）10.1 特征提取LDA于是： (S 1S)W T W T AA1wb1(S 1S)W T A W T A .wb1是wb(SS)1的 m個(gè)特征向量！WAT這說明特征向量的求解就用前面的對(duì)角化方法：wbnnnn2S 1SB B.2 nnwbnnB1 S 1SB10.1 特征提取LDAm維空間中的任何非奇異變換矩陣A都不改變J(W)的值，因此可以忽略A。(請(qǐng)自己證明）設(shè)矩陣(S 1S) 的特征值為：wb1 2 n則選取前m個(gè)特征值對(duì)應(yīng)的特征向量作為W，則imJ (W )

10、 i 110.1 特征提取LDA關(guān)于LDA的幾點(diǎn)說明：對(duì)于k類問題，選出的特征個(gè)數(shù)最多只有k-1，這是因?yàn)?Sb的秩最多為k-1。因此，對(duì)應(yīng)非零特征根的特征向量最多有k-1個(gè)，那些零特征根對(duì)應(yīng)的特征向量對(duì)判據(jù) J 的值沒有任何影響。10.1 特征提取LDALDA可以從另一個(gè)角度很容易的推出：假設(shè)每類數(shù)據(jù)服從不同均值，相同協(xié)方差均陣 Sw的正態(tài)分布。從最小錯(cuò)誤率準(zhǔn)則出發(fā)就可以得到相同的結(jié)果?；貞汢ayes決策理論一章的習(xí)題，兩類問題，正態(tài)分布且相同協(xié)方差矩陣的假設(shè)下，決策面是超平面： wT x const.(m1 m2 )1w特征：w S10.1 特征提取LDAw(m1 m2 )1w S就是矩陣

11、TwbwS S(m1 m2 )(m1 m2 )11S的特征向量。因?yàn)?SwSbww S(m1 m2 ) wwTw S(m m)(m m)(m m)S12111212110.1 特征提取LDA推廣：LDA可以從相同協(xié)方差矩陣的正態(tài)分布假設(shè)和最小錯(cuò)誤率準(zhǔn)則推出，是Campbell在1984年指出的?？梢宰鰞煞矫娴耐茝V：假設(shè)各類服從協(xié)方差矩陣不同的正態(tài)分布，稱為Heteroscedastic Discriminant Analysis (HDA).假設(shè)各類服從協(xié)方差矩陣相同的Gauss混合分布。10.2 特征選擇10.2 特征選擇特征選擇是從原始特征中挑選出一些最有代表性，分類性能最好的特征來。每個(gè)

12、特征的狀態(tài)是離散的 選與不選種組合。若不限定個(gè)數(shù)，則共2N種。NP 問題這是一個(gè)典型的組合優(yōu)化問題N從N個(gè)特征中選取k個(gè),共 Ck10.2 特征選擇特征選擇的方法大體可分兩大類：Filter方法：不考慮所使用的學(xué)習(xí)算法。通常給出一個(gè)獨(dú)立于分類器的指標(biāo)來評(píng)價(jià)所選擇的特征子集S，然后在所有可能的特征子集中搜索出使得 最大的特征子集作為最優(yōu)特征子集。Wrapper方法：將特征選擇和分類器結(jié)合在一起，即特征子集的好壞標(biāo)準(zhǔn)是由分類器決定的，在學(xué)習(xí)過程中表現(xiàn)優(yōu)異的的特征子集會(huì)被選中。10.2 特征選擇一種Filter算法: FOCUS該算法致力于尋找一個(gè)能夠正確區(qū)分所有類別的最小特征集合。例如，若區(qū)分每個(gè)

13、人的特征有：姓名、性別、籍貫、工作單位、身份證號(hào)則該算法會(huì)選擇：身份證號(hào)搜索時(shí)先看一個(gè)特征能否正確區(qū)分樣本，若不能，則考察兩個(gè)特征以此類推10.2 特征選擇一種Wrapper算法：OBLIVION該方法與最近鄰法結(jié)合，根據(jù)特征子集的分類表現(xiàn)來選擇特征用順序后退法搜索特征子集：從全體特征開始，每次剔除一個(gè)特征，使得所保留的特征集合有最大的分類識(shí)別率（基于最近鄰法)。依次迭代，直至識(shí)別率開始下降為止用leave-one-out 方法估計(jì)平均識(shí)別率：用N-1個(gè)樣本判斷余下一個(gè)的類別，N次取平均10.2 特征選擇許多特征選擇算法力求解決搜索問題，經(jīng)典算法有 ：分支定界法順序后退法順序前進(jìn)法模擬退火法T

14、abu 搜索法遺傳算法10.2 特征選擇遺傳算法該算法受進(jìn)化論啟迪，根據(jù)“物競(jìng)天擇，適者生存”這一規(guī)則演變幾個(gè)術(shù)語：基因鏈碼：使用遺傳算法時(shí)要把問題的每個(gè)解編碼成一個(gè)基因鏈碼。比如要從D個(gè)特征中挑選d個(gè),就用一個(gè)D位的0或1組成的字符串表示一種特征組合。1表示該特征被選中每個(gè)基因鏈碼代表一個(gè)解，稱作一個(gè)“個(gè)體”，其中的每一位看作一個(gè)“基因”10.2 特征選擇遺傳算法群體：若干個(gè)體的集合，也就是一些解的集合交叉：選擇群體中的兩個(gè)個(gè)體，以這兩個(gè)個(gè)體為雙親作基因鏈碼的交叉，從而產(chǎn)生兩個(gè)新的個(gè)體，作為后代。X110001100X1 1000 1010X201001010X20100 1100變異：對(duì)某

15、個(gè)體，隨機(jī)選取其中一位，將其翻轉(zhuǎn)10000101001010適應(yīng)度：對(duì)每個(gè)解，以給定的優(yōu)化準(zhǔn)則來評(píng)價(jià)其性能的優(yōu)劣，作為其適應(yīng)度10.2 特征選擇遺傳算法1.遺傳算法的基本框架：初始化進(jìn)化世代數(shù) t=02.給出初始化群體P(t)，令xg為任一個(gè)體3.對(duì)P(t) 中每個(gè)個(gè)體估值，并將群體中最優(yōu)解x與xg比較，若優(yōu)于xg，則令xg=x4.如果終止條件滿足，則算法結(jié)束，xg為最終結(jié)果。否則，轉(zhuǎn)步驟55.從P(t)選擇個(gè)體并進(jìn)行交叉和變異操作，得到新一代個(gè)體P(t+1)，令t=t+1，轉(zhuǎn)步驟3。10.2 特征選擇遺傳算法關(guān)于遺傳算法的說明：由步驟3保證了最終解是所搜索過的最優(yōu)解常用的終止條件是群體的世代

16、數(shù)超過一個(gè)給定值，或連續(xù)數(shù)個(gè)世代都沒有得到更優(yōu)解群體的大小和演化代數(shù)是值得重視的參數(shù)。在一定范圍內(nèi)，這兩個(gè)參數(shù)大些能得到更好的解對(duì)交叉的親本選擇可采用如下規(guī)則：個(gè)體的性能越好，被選中的可能性也越大10.2 特征選擇例：用于癌癥分類的基因選擇根據(jù)癌癥患者與正常人的基因表達(dá)數(shù)據(jù)，挑選出與癌癥相關(guān)的基因。這種相關(guān)基因很可能就是致病基因，它可以幫助我們查找病源，進(jìn)而可以指導(dǎo)設(shè)計(jì)藥物在選出的基因上作病患識(shí)別，可以提高識(shí)別率，有助于臨床診斷10.2 特征選擇基因選擇的困難人類大約有3萬個(gè)左右的基因，但與某種疾病有關(guān)的基因并不多基因數(shù)（成千上萬）遠(yuǎn)遠(yuǎn)大于實(shí)驗(yàn)樣本數(shù)（幾十）10.2 特征選擇單基因選擇算法：基

17、于某種準(zhǔn)則給每個(gè)基因打分，把得分低的基因?yàn)V掉，選取那些得分高的基因組成特征子集。例如G-S算法 ：該方法以Fisher判別指標(biāo)對(duì)每個(gè)特征打分。根據(jù)每維特征上兩類的距離和方差來評(píng)價(jià)它分類能力。準(zhǔn)則函數(shù)為其中分別是基因g在訓(xùn)練樣本中在第一類和第二類的均值和標(biāo)準(zhǔn)差。在分類時(shí)，該分值可作為每個(gè)特征的分類權(quán)重gggg2GS _ correlation( gene _ g ) 112 gggg2112, , , 10.2 特征選擇多基因選擇算法：與分類器相聯(lián)系，采用各種搜索算法或優(yōu)化算法進(jìn)行特征選擇Recursive Feature Elimination (RFE) 算法：根據(jù)訓(xùn)練得到的SVM線性分類器

18、的系數(shù)來判斷每個(gè)特征的重要性和分類能力。 b假設(shè)由線性SVM得到的分類器為 f ( x) wi xi當(dāng) wi 較大時(shí)，第i個(gè)特征對(duì)分類器影響較大；當(dāng) wi 較小時(shí)，第i個(gè)特征對(duì)分類器影響較??；當(dāng) wi 為0時(shí)，第i個(gè)特征對(duì)分類器幾乎沒有影響10.2 特征選擇wwT SwFisher優(yōu)化模型（FOM）Fisher判別wT S wJ (w) bSw w m但是基因數(shù)遠(yuǎn)遠(yuǎn)大于樣本數(shù)，上面的式子無法求解，我們通過正則化來求解21wF (w) Sw m w 210.2 特征選擇過引入，求解使得下式最?。篘k 10 w2k (w) 1w我們的目的是進(jìn)行特征選擇，即希望得到的 w 最好是由少數(shù)非零元素組成。通1222 w (w)2wF (w) Sw mNii12 w122(1e)2wF(w) S wm w10.2 特征選擇00.5Third Ite ration102040608010000.5Fourth Ite ration10102030405000.511=5000010