第五章特征選擇與特征提取-Read

第五章特征選擇與特征提取5.1問題的提出前面主要介紹的是各種分類器的設(shè)計方法， 實(shí)際上我們已經(jīng)完全可以解決模式識別的問題了。然而在實(shí)際應(yīng)用中，在分類器設(shè)計之前，往往需要對抽取出的特征進(jìn)行一下處理，爭取盡量減小特征的維數(shù)。在實(shí)踐中我們發(fā)現(xiàn)，特征的維數(shù)越大，分類器設(shè)計的難度也越大，一維特征的識別問題最容易解決，我們只要找到一個閾值t,大于t的為一類，小于t的為一類。冋時特征維數(shù)越大，要求的訓(xùn)練樣本數(shù)量越多，例如在一維的情況下，10個訓(xùn)練樣本就可以比較好的代表一個類別了，而在 10維空間中，1o個訓(xùn)練樣本則是遠(yuǎn)遠(yuǎn)不夠的。這一章中我們就來介紹一下減小特征維數(shù)的方法。一般來說模式識別系統(tǒng)的輸入是傳感器對實(shí)物或過程進(jìn)行測量所得到的一些數(shù)據(jù)，其中有一業(yè)數(shù)據(jù)直接可以作為特征， 有一業(yè)數(shù)據(jù)經(jīng)過處理之后可以作為特征，這樣的一組特征一般稱為原始特征。在原始特征中并不一定每個特征都是有用的， 比如在識別蘋果和橙子的系統(tǒng)中，我們可以抽取出的特征很多， （體積，重量，顏色，高度，寬度，最寬處高度） ，同樣還有可能抽取出其它更多的特征。在這些特征中對分類有用的是（顏色，高度，最寬處高度），其它特征對識別意義不大，應(yīng)該去除掉。這樣的過程稱為是特征選擇，也可以稱為是特征壓縮。特征選擇可以描述成這樣一個過程，原始特征為 N維特征X=（X1,X2AI,XNf，從中T選擇出M個特征構(gòu)成新的特征矢量丫二Xi,Xijl|,XiM，M::N。同時，特征矢量的每一個分量并不一定是獨(dú)立的， 它們之間可能具有一定的相矢性， 比如說高度和最寬處的高度，高度值越大， 最寬處的高度值也越大，它們之間具有相矢性，我們可以通過一定的變換消除掉這種相矢性，比如取一個比值：最寬處的高度過程稱為特征提取。/高度。這樣的特征提取可以描述為這樣一個過程，對特征矢量 X=X1,X2,HI,XN丁施行變換：%=h（X）,i=1,2,川，M，McN，產(chǎn)生出降維的特征矢量丫二（敘丫2,川皿$。在一個實(shí)際系統(tǒng)的設(shè)計過程中，特征的選擇和提取過程一般都需要進(jìn)行，首先進(jìn)行特征選擇，去除掉無矢特征，這些特征實(shí)踐上根本就不需要抽取出來， 這部分傳感器根本不需要安裝，這樣也可以減小系統(tǒng)的的成本。然后進(jìn)行特征提取，降低特征的維數(shù)。然后利用降維之后的樣本特征來設(shè)計分類器。5.2模式類別的可分性判據(jù)在討論特征選擇和特征壓縮之前， 我們先要確定一個選擇和提取的原則。對一個原始特征來說，特征選擇的方案很多，從N維特征種選擇出M個特征共有Cm巴中M!(N—M)!選法，其中哪一種方案最佳，則需要有一個原則來進(jìn)行指導(dǎo)。同樣，特征的壓縮實(shí)際上是要

找到M個N元函數(shù)，N元函數(shù)的數(shù)量是不可數(shù)的，這也要有一個原則來指導(dǎo)找出 M個最佳的N元函數(shù)。我們進(jìn)行特征選擇和特征提取的最終目的還是要進(jìn)行識別， 因此應(yīng)該是以對識別最有利原則，這樣的原則我們稱為是類別的可分性判據(jù)。 用這樣的可分性判據(jù)可以度量當(dāng)前特征維數(shù)下類別樣本的可分性?？煞中栽酱螅瑢ψR別越有利，可分性越小，對識別越不利。人們對的特征的可分性判據(jù)研究很多，然而到目前為止還沒有取得一個完全滿意的結(jié)果，沒有哪一個判據(jù)能夠完全度量出類別的可分性。 下面介紹幾種常用的判據(jù)，我們需要根據(jù)實(shí)際問題，從中選擇出一種。一般來說，我們希望可分性判據(jù)滿足以下幾個條件：? 與識別的錯誤率由直接的聯(lián)系，當(dāng)判據(jù)取最大值時，識別的錯誤率最小；當(dāng)特征獨(dú)立時有可加性，即：NJijXv|，X2,|11，Xn八JijxkJij是第i類和第j類的可分性判據(jù)，Jij越大'兩類的可分程度越大'Xi,X2,川,Xn為N維特征；應(yīng)具有某種距離的特點(diǎn)：Jij*0，當(dāng)ij時;Jj=o,當(dāng)/=j時；J??I>??IJ=Jjl,單調(diào)性，加入新的特征后，判據(jù)不減小：JijX|>X2JXN-JijX1>X2I>XN>XN1?但是遺憾的是現(xiàn)在所經(jīng)常使用的各種判據(jù)很難滿足上述全部條件， 只能滿足一個或幾個條件。一、基于幾何距離的可分性判據(jù)在介紹這一類判據(jù)之前，先來看一下各種幾何距離的定義。7?點(diǎn)與點(diǎn)的距離這是我們前面已經(jīng)介紹過的一種距離，可以有多種形式，如歐氏距離、街市距離、馬氏距離等，特征矢量X和Y之間的距離可以表示為：Td(X5Y)=(X-Y)(X-Y)(歐氏距離)點(diǎn)與類別之間的距離這也是我們前面定義過的一種距離度量，常用的有：平均樣本法、平均距離法、最這也是我們前面定義過的一種距離度量，常用的有：平均樣本法、平均距離法、最近距離法，K?近鄰法等。特征矢量X與幾類別之間距離的平方可以表示為:1叫d?（XQ）=—一瓦d?（X,X門）（平均距離法）Nik4其中Xi,X2J|I，X/V為ij類中的樣本，Ni為類別中的樣本數(shù)。?類內(nèi)距離設(shè)「了由樣本集Xi,X2川|，Xn「，樣本的均值矢量為m>，則由樣本集定義的類內(nèi)均方距離為：NiNi、“cbXsX/k=1I4當(dāng)取歐氏距離時有：叫Td2j）=一二Xj-打LXkm'NikA4.類別之間的距離在第二章中對類別之間的距離也做過定義， 包括最短距離法，最長距離法，類平均距離法等?！怖漕惻cj類之間的距離可以表示為：1NiNjdJLj=RR：-dXk>Xi （平均距離法）當(dāng)取歐氏距離時，可定義兩類之間的均方距離：[%叫丁NN遲遲（X￡）—X卩））（Xk）—X{j））'J k壬I壬有了距離度量之后，我們就可以在此基礎(chǔ)上定義可分性測度了。 一般來講，當(dāng)各個類別的類內(nèi)距離越小時可分性越強(qiáng)， 而類間距離越大時，可分性越強(qiáng)。因此可以有以各類樣本之間的平均距離作為判據(jù)：1M MJdX PJVPJdJQj2i=1 j=1JdX所反映的主要還是類別之間的分離程度，對類內(nèi)的聚集程度反映不夠。通常我們采用跟一般的矩陣形式來構(gòu)造可分性判據(jù)。1?類內(nèi)散度矩陣設(shè)有M個類別，OJII,Om,Oi類樣本集{X11X2川l,XN‘‘，Qi類的散度矩陣定義為：Ni TsP=p（X“品驅(qū)卩人⑴Nik=i

總的類內(nèi)散度矩陣為：M M 1NiSw八P『Sw/[PJ—Xk1i4 i=J Mk=1類間散度矩陣第i個類別和第j個類別之間的散度矩陣定義為：sBu)=(mO-m(0)(m°)—m(J))總的類間散度矩陣可以定義為：M MP「Sbj=M MP「Sbj=—、PjPjm-mjm-mjL— j~Sb=—Pi二 i4M令：m為總體均值，m=ZP(OimD，則有:i:4\o"CurrentDocument"M TSbPQiXmO-mXm(")-m)■—*I—k總體散度矩陣總體散度矩陣可以定義為：St-JXimXiNi：-M其中N為總的樣本數(shù)，N= N\?？梢宰C明：5心氐*Sb。i:—可以看出三個散度矩陣均為實(shí)對稱矩陣。上面我們所定義的判據(jù)： JdX=JdxjutrSri=trSw-sbotr表示取一個矩N陣的跡，也就是主對角線元素之和， N維方陣Z的跡為：trZ二、aw同樣我們可以利用三個散度矩陣定義出一系列的可分性判據(jù):J—=trSwSb其中A表示方陣A的行列式的值，比較常用的判據(jù)是Ji?；趲缀尉嚯x的可分性判據(jù)計算起來比較簡單，只要我們已知各個類別的訓(xùn)練樣本集，就可以計算出三個散度矩陣，同時也就可以計算出各種可分性判據(jù)。二、基于概率分布的可分性判據(jù)基于幾何距離的可分性判據(jù)計算起來比較簡單， 然而它沒有考慮各類別的概率分布， 因此與識別錯誤率之間的聯(lián)系卻不是很緊密。下面介紹一種直接基于概率分布的可分性判據(jù)。先以最簡單的一維特征、兩類問題為例，下圖表示了兩種極端情況：第一種情況是兩類完全可分：對所有p(X|0第一種情況是兩類完全可分：對所有p(X|0〃/0的點(diǎn)，有p(X02)=0;第二種情況是兩類完全不可分：對所有的X第二種情況是兩類完全不可分：對所有的X有p(X|0u)=p(X|02)o下面我們可以定義兩個類條件概率密度函數(shù)之間的距離 Jp作為交疊程度的度量，Jp應(yīng)該滿足如下條件：非負(fù)性，Jp-0;當(dāng)兩類完全重疊時Jp取最大值，即若對所有X有p(XQ2)式0時，pXJ=0，貝uJp二max;當(dāng)兩類密度函數(shù)完全相同時， Jp應(yīng)為零，即若p(X|C2)=P(X|0i)，則JP=0o按照這樣的要求，可以定義出多種可分性判據(jù)，這里我們只介紹其中一種 一散度?，F(xiàn)在考慮ixffi門j兩類之間的可分性，取其對數(shù)似然比:LiX=ln則Ji類對Jj類的平均可分性信息可以定義為:

lj(X戶EliX「xpxjln同樣」類對」類的平均可分性信息：P(X|Ojlji(X)=Ejji(X)]=Lp(X|Cj)ln dXPXJ散度Jp定義為區(qū)分門i類和門j類的總平均信息：=fx[p(X|0i)-P(X0j川n從Jp的定義可以看出，當(dāng)兩類分不完全性同 p(XOi)=p(XQ\)時，Jp=o;當(dāng)兩類完全可分時，Jp=?。基于概率的可分性判據(jù)優(yōu)點(diǎn)是直接與識別的錯誤率相聯(lián)系， 缺點(diǎn)是需要已知各個類別類概率密度函數(shù)，只有當(dāng)我們預(yù)先已知各類別的概率分布時，才可以利用訓(xùn)練樣本集合估計出概率密度函數(shù)，但是對很多實(shí)際問題來說各類別的概率分布情況我們是無法預(yù)先知道的。5.3特征選擇所謂特征選擇，就是從一組數(shù)量為 N的特征中選擇出一組數(shù)量為 M的最優(yōu)特征，(NM)這里有兩個問題要解決，1、選擇一種可分性判據(jù)作為最優(yōu)特征選擇的標(biāo)準(zhǔn)； 2、找到一個好的算法，來選擇出這組最優(yōu)特征。下面我們就來介紹幾種特征選擇的算法。一個最簡單的思路是：我們假設(shè) N個特征之間相互獨(dú)立，并且使用的可分性判據(jù)滿足N可加性：JX=?Jx，這時候我們只要把N個特征每個單獨(dú)使用時的可分性判據(jù)7JXi計算出來，然后從大到小排序： Jx,?JX2 IIIJXn?選擇出前M個特征就是一組最優(yōu)的特征。然而問題往往沒有這么簡單，這種特征獨(dú)立性假設(shè)多數(shù)情況下并不成立，并且可分性判據(jù)也不一定滿足可加性。另外一個簡單的思路是(窮舉法)：對從N中選擇出M個特征的所有組合情況都計算其可分性判據(jù)，然后選擇出其中的最大者作為解決方案。當(dāng) N的數(shù)值比較小時，這種方法一定是可行的，然而當(dāng)N比較大時，這個組合數(shù)會非常大，比如 N=100，M=10時，組合數(shù)的數(shù)量級是1，當(dāng)N=20,M=10時，組合數(shù)為184756°將所有的組合都計算一遍顯然是不現(xiàn)實(shí)的。因此我們需要有一個搜索算法來進(jìn)行特征選擇。一、最優(yōu)搜索算法一分支定界算法到目前為止唯一能夠找到最優(yōu)解的算法是“分支定界”算法。它所利用的是可分性判據(jù)

到目前為止唯一能夠找到最優(yōu)解的算法是“分支定界”算法。它所利用的是可分性判據(jù)中的單調(diào)性質(zhì)：JjXi3X23|||中的單調(diào)性質(zhì)：JjXi3X23|||3Xn質(zhì)。mXi,X2,|]|3Xn,Xni 們前面定義的各種判據(jù)都滿足這個性分支定界的思想分支定界算法實(shí)際上是對一彳、特征選擇的搜索樹進(jìn)行搜索,情況來說明一下搜索樹。F面先以N=6，M=2的45Xi,在搜索樹中根節(jié)點(diǎn)Xo代表全部特征的集合x2,1H,X6』，每向下一級節(jié)點(diǎn)代表從集Xi,合中刪除一個特征，節(jié)點(diǎn)邊上的數(shù)字表示在這一級中刪除的特征，代表fxi9比如A節(jié)點(diǎn)表示刪除X2特征,Xa,|||,X6?，因為最后要保留2個特征，因此樹的級數(shù)為N?合中刪除一個特征，節(jié)點(diǎn)邊上的數(shù)字表示在這一級中刪除的特征，代表fxi9葉節(jié)點(diǎn)代表一種組合‘比如 C節(jié)點(diǎn)代表：Xi,xA>o由于可分性判據(jù)具有單調(diào)性， 因此在搜索樹中的節(jié)點(diǎn)具有這樣的性質(zhì)： 每個節(jié)點(diǎn)代表的特征集合的可分性判據(jù)要大于其后繼節(jié)點(diǎn)代表的特征集合的可分性判據(jù)，比如：JA-JB-JC根據(jù)這樣的性質(zhì)，我們就可以有如下的搜索算法。分支定界算法（不嚴(yán)格）1） 搜索從右向左進(jìn)行，首先設(shè)置一個界值 B，初始化為B=0;2） 如果當(dāng)前節(jié)點(diǎn)沒有分支， 則向下搜索，直到葉節(jié)點(diǎn)為止，計算葉節(jié)點(diǎn)代表的特征集合的可分性判據(jù)，如果大于界值 B，則將B替換為這個判據(jù)值，并記錄這個特征集合，作為當(dāng)前的最優(yōu)選擇；向上回溯，直到有節(jié)點(diǎn)有未搜索過的分支為止， 按照從右向左的順序搜索其子節(jié)點(diǎn)；3） 如果當(dāng)前節(jié)點(diǎn)有分支，則計算當(dāng)前節(jié)點(diǎn)代表的特征集合的可分性判據(jù)，如果小于界值B，則中止該節(jié)點(diǎn)向下的搜索，因為其子節(jié)點(diǎn)的可分性判據(jù)已經(jīng)不可能大于 B了。否則按照從右向左的順序搜索其子節(jié)點(diǎn)。分支定界算法的計算時間是不確定的，同最優(yōu)解分支所在位置有矢，如果最優(yōu)解分支在分支定界算法的計算時間是不確定的，同最優(yōu)解分支所在位置有矢，如果最優(yōu)解分支在3組可最右端，并且去掉Xi或X23組可分性判據(jù)；如果每個分支的可分性判據(jù)都大于其左端分支的可分性判據(jù)，則搜索時間最長，需計算可分性判據(jù)的次數(shù)可能 15次。二、次優(yōu)搜索算法順序前進(jìn)法（SequentialForwardSelection,SFS）每次從未入選的特征中選擇一個特征， 使得它與已入選的特征組合到一起所得到的可分性判據(jù)最大，直到特征數(shù)增加到 M為止。用Xk表示在第k步時的特征集合，搜索算法如下：1） 開始時，X。二以，從N個特征中選擇一個JXi最大的特征，加入已選特征集，X;tA2） 在第k步，Xk中包含已經(jīng)選擇的 k個特征，對未入選的 N-k個特征計算，JXku「Xj?,其中j=1,2,HI,N-k，并且按照由大到小排序，將可分性判據(jù)最大的特征xi加入Xk，Xk廠XkUX；；3）直到所選的特征數(shù)等于M為止。順序后退法（SequentialBackwardSelection,SBS）同順序前進(jìn)法的過程剛好相反， 最開始時取X。?\為，III,XA?，每次從中剔除一個特征，使得剩余的特征可分性判據(jù)最大。增1減「法（I-r法）前兩種方法可以進(jìn)一步改進(jìn)，比如每次不是加入 1個特征，而是加入|彳、特征；或者每次不是剔除一個特征，而是剔除r個特征。這樣的效果要比每次加1或減1的效果好，但是計算量要增大。另外一種改進(jìn)方法是將SFS和SBS結(jié)合，先使用SFS算法逐個選入I個最佳特征，然后使用SBS算法逐個剔除r個最差特征，I?r，再使用SFS算法增加I個特征，再使用SBS剔除r個特征，…，直到選出M個特征為止。5.4特征提取特征抽取的方法很多，下面我們以其中的一種一基于離散K丄變換（DKLT）的特征抽取，其它方法與此類似。設(shè)原始特征為N為矢量X=（xi,X2,IH,Xn「，均值矢量m=E（X】，相尖矩陣Rx=eXXt）協(xié)方差矩陣cx=EL（X-m\X-m）l我們可以對X我們可以對X作如下的標(biāo)準(zhǔn)正交變換，將其變?yōu)槭噶縴=（%,『m八Y=TTY=TTX=T2Y的每個分量：屮二丁?X，其中T為一個NN的標(biāo)準(zhǔn)正交矩陣，Ti為其第i個列矢J。也就是說YJ。也就是說Y的每個分量是X每一個分量的線性組合。6i?j同樣X可以表示為：T-1 V2X二TY二TY=「T2川Tn7N我們要進(jìn)行特征提取，也就是要用Y的M項來代替X，這種代替必然帶來誤差，下面我們來對這個誤差進(jìn)行估計：M令：乂二yTi，1vM::N，引入的均方誤差為：i生TOC\o"1-5"\h\z- T ?N Ne2(M)=Ei(X—X)(X—X)=2E[yA=S丘陽]N N\o"CurrentDocument"=571tEXXT〕T|=ETrRxTii=MI1 ?i1這又變成一個優(yōu)化問題，我們希望尋找到一個標(biāo)準(zhǔn)正交矩陣 T，使得e2M