第五章特征選擇2特征選擇5.1引言5.2類別可分離性判據(jù)5.3特征子集的搜索策略3特征選擇5.1引言5.2類別可分離性判據(jù)5.3特征子集的搜索策略4尺寸重量顏色5對分類器設(shè)計(jì)來說，使用什么樣的特征描述事物，也就是說使用什么樣的特征空間是個(gè)很重要的問題。這個(gè)問題稱之為描述量的選擇問題，意思是指保留哪些描述量，刪除哪些描述量的問題。本章研究對特征空間進(jìn)行改造,目的在于提高其某方面的性能，因此又稱特征的優(yōu)化問題。

基本概念5.1引言65.1引言75.1引言8對特征空間的改造、優(yōu)化,主要的目的是降維，即把維數(shù)高的特征空間改成維數(shù)低的特征空間，降維主要有兩種途徑。一種是篩選掉一些次要的特征，問題在于如何確定特征的重要性，以及如何篩選。另一種方法是使用變換的手段，限定在線性變換的方法上，通過變換來實(shí)現(xiàn)降維。

5.1引言9特征的選擇與提取：分析各種特征的有效性并選出最有代表性的特征是模式識(shí)別系統(tǒng)設(shè)計(jì)的關(guān)鍵步驟。降低特征維數(shù)在很多情況下是有效設(shè)計(jì)分類器的重要課題。數(shù)據(jù)獲取預(yù)處理特征提取

與選擇分類決策分類器

設(shè)計(jì)信號(hào)空間特征空間5.1引言基本概念10三大類特征三大類特征：物理、結(jié)構(gòu)和數(shù)字的■物理和結(jié)構(gòu)特征：易于為人的直覺感知，但有時(shí)難于定量描述，因而不易用于機(jī)器判別。■數(shù)字特征：易于用機(jī)器定量描述和判別，如基于統(tǒng)計(jì)的特征。5.1引言11假設(shè)有D維特征向量空間，y={y1,y2,…yD}：

特征選擇是指從原有的D維特征空間，刪去一些特征描述量，從而得到精簡后的特征空間。在這個(gè)特征空間中，樣本由降維后的d維的特征向量描述：x={x1,x2,…xd}，d＜D。由于x只是y的一個(gè)子集，因此每個(gè)分量xi必然能在原特征集中找到其對應(yīng)的描述量xi=yj。

特征提取則是找到一個(gè)映射關(guān)系：A:Y→X，使新樣本特征描述維數(shù)比原維數(shù)降低。其中每個(gè)分量xi是原特征向量各分量的函數(shù)，即xi=WTyi。特征優(yōu)化兩種方法5.1引言

特征選擇在概念上十分簡單，即對原有特征進(jìn)行刪選優(yōu)化.一般人常想，只要逐個(gè)分析每個(gè)特征，判斷它對分類的價(jià)值，然后根據(jù)其價(jià)值刪去或保留，這是人們常采用的方法，但是這種方法并不能保證特征空間的最優(yōu)組合優(yōu)化，因此本節(jié)僅討論一些原理上更好的方法。1213特征選擇:從原始特征中挑選出一些最有代表性、分類性能最好的特征進(jìn)行分類。（可解釋性好）要解決兩個(gè)問題：選擇的標(biāo)準(zhǔn)，如可分離性判據(jù)快速特征子集搜索算法從D個(gè)特征中選取d個(gè),共

種組合。若不限定特征選擇個(gè)數(shù)，則共2D種組合

－典型的組合優(yōu)化問題14特征選擇的方法：是否直接考慮分類器性能Filter方法：根據(jù)獨(dú)立于分類器的指標(biāo)J來評價(jià)所選擇的特征子集S，在所有可能的特征子集中搜索出使得J最大的特征子集作為最優(yōu)特征子集。不考慮所使用的學(xué)習(xí)算法。Wrapper方法：將特征選擇和分類器結(jié)合在一起，在分類過程中表現(xiàn)優(yōu)異的的特征子集會(huì)被選中。選擇特征的順序：自下而上：特征數(shù)從零逐步增加到d。自上而下：特征數(shù)從D開始逐步減少到d。15特征選擇5.1引言5.2類別可分離性判據(jù)5.3特征子集的搜索策略16特征選擇任務(wù)是從n個(gè)特征中求出對分類最有效的m個(gè)特征(m＜n)。對于特征選擇來講，從n個(gè)特征中選擇出m個(gè)特征，有種組合方式。哪一種特征組的分類效果最好？這需要有一個(gè)比較標(biāo)準(zhǔn)，即需要一個(gè)定量的準(zhǔn)則來衡量選擇結(jié)果的好壞。5.2類別可分性判據(jù)17很自然地會(huì)想到，既然模式識(shí)別的目的是設(shè)計(jì)分類器，那么用分類器的錯(cuò)誤概率作為準(zhǔn)則就行了，也就是說，使分類器錯(cuò)誤概率最小的那組特征，就應(yīng)當(dāng)是一組最有效的特征。從理論上講，這是完全正確的，但在實(shí)際使用中卻有很大困難。從錯(cuò)誤概率的計(jì)算公式就會(huì)發(fā)現(xiàn)，即使在類條件概率密度已知的情況下錯(cuò)誤概率的計(jì)算就很復(fù)雜，何況實(shí)際問題中概率分布常常不知道，這使得直接用錯(cuò)誤概率作為準(zhǔn)則來評價(jià)特征的有效性比較困難。5.2類別可分性判據(jù)18用以定量檢驗(yàn)分類性能的準(zhǔn)則稱為類別可分性準(zhǔn)則Jij,需要滿足以下幾點(diǎn)：5.2類別可分性判據(jù)19用以定量檢驗(yàn)分類性能的準(zhǔn)則稱為類別可分性準(zhǔn)則Jij,需要滿足以下幾點(diǎn)：5.2類別可分性判據(jù)20（1）與錯(cuò)誤概率有單調(diào)關(guān)系（2）當(dāng)特征獨(dú)立時(shí)有可加性（3）度量特性（4）單調(diào)性設(shè)計(jì)分類器錯(cuò)誤概率最小新的標(biāo)準(zhǔn)目的理論最理想×5.2類別可分性判據(jù)215.2類別可分性判據(jù)1.基于距離的可分性判據(jù)2.基于概率分布的可分性判據(jù)3.基于熵函數(shù)的可分性判據(jù)221.基于距離的可分性判據(jù)基于距離的可分性判據(jù)的實(shí)質(zhì)是Fisher準(zhǔn)則的延伸，即綜合考慮不同類樣本的類內(nèi)聚集程度與類間的離散程度這兩個(gè)因素。判據(jù)的優(yōu)化體現(xiàn)出降維特征空間較好地體現(xiàn)類內(nèi)密集。一些不能體現(xiàn)類間分隔開的特征很可能被排除掉了。掌握利用離散矩陣來描述數(shù)據(jù)離散程度的方法。5.2類別可分性判據(jù)23基于距離度量是常用來進(jìn)行分類的重要依據(jù)，因?yàn)橐话闱闆r下同類物體在特征空間呈聚類狀態(tài)，即從總體上說同類物體內(nèi)各樣本由于具有共性，因此類內(nèi)樣本間距離應(yīng)比跨類樣本間距離小。Fisher準(zhǔn)則是以使類間距離盡可能大同時(shí)又保持類內(nèi)距離較小這一種原理為基礎(chǔ)的。同樣在特征選擇中也可以使用類似的原理，這一類被稱為基于距離的可分性判據(jù)。為了度量類內(nèi)、類間的距離，可用其他方法描述方法，即描述樣本的離散程度的方法。5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)24各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準(zhǔn)則5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)25各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準(zhǔn)則5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)26各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準(zhǔn)則5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)均值向量總平均向量27各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準(zhǔn)則5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)均值向量總平均向量樣本到質(zhì)心的平方距離某類均值向量到總體樣本向量之間的平方距離28各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離的平均值作為可分性準(zhǔn)則5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)均值向量總平均向量各類均值向量的平均平方距離29樣本類間

離散度矩陣樣本類內(nèi)

離散度矩陣類間可分離性判據(jù)5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)30樣本類間

離散度矩陣樣本類內(nèi)

離散度矩陣類間可分離性判據(jù)5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)31基于距離的準(zhǔn)則概念直觀，計(jì)算方便，但與錯(cuò)誤率沒有直接聯(lián)系樣本類間

離散度矩陣樣本類內(nèi)

離散度矩陣類間可分離性判據(jù)5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)32基于距離的可分性判據(jù)的其他表達(dá)形式：5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)33優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：定義直觀、易于實(shí)現(xiàn)，因此比較常用。缺點(diǎn)：沒有直接考慮樣本的分布情況，很難在理論上建立起它們與分類錯(cuò)誤率的聯(lián)系，而且當(dāng)兩類樣本的分布有重疊時(shí)，這些判據(jù)不能反映重疊的情況。5.2類別可分性判據(jù)1.基于距離的可分性判據(jù)34基于距離的可分性判據(jù)原理直觀，計(jì)算簡便。但是這種原理沒有考慮概率分布，因此當(dāng)不同類樣本中有部分在特征空間中交迭分布時(shí)，簡單地按距離劃分，無法表明與錯(cuò)誤概率之間的聯(lián)系。基于概率分布的可分性判據(jù)則依據(jù)如下觀察到的現(xiàn)象。如果不考慮各類的先驗(yàn)概率，或假設(shè)兩類樣本的先驗(yàn)概率相等，那么從兩類條件概率分布可以看出，如果兩類條件概率分布互不交迭，即對p(X|ω2)≠0處都有p(X|ω1)＝0，則這兩類就完全可分；另一種極端情況是對所有X都有p(X|ω1)＝p(X|ω2)，則兩類就完全不可分。5.2類別可分性判據(jù)2.基于概率分布的可分性判據(jù)35完全可分對p(X|ω2)≠0處都有p(X|ω1)＝0完全不可分對所有X都有p(X|ω1)＝p(X|ω2)5.2類別可分性判據(jù)2.基于概率分布的可分性判據(jù)36顯然不同類別在特征空間x中的分布要盡可能不一樣，則分類就比較容易，通俗的講，則不同類別在特征空間的不同區(qū)域聚集，則分類就容易，它們重迭的程度越低，越有別于分類。為了考查在不同特征下兩類樣本概率分布的情況，定義了基于概率分布的可分性判據(jù)。5.2類別可分性判據(jù)2.基于概率分布的可分性判據(jù)37顯然不同類別在特征空間x中的分布要盡可能不一樣，則分類就比較容易，通俗的講，則不同類別在特征空間的不同區(qū)域聚集，則分類就容易，它們重迭的程度越低，越有別于分類。為了考查在不同特征下兩類樣本概率分布的情況，定義了基于概率分布的可分性判據(jù)。分布密度的交疊程度可用p(X|ω1)及p(X|ω2)這兩個(gè)分布密度函數(shù)之間的距離Jp來度量，距離Jp有以下幾個(gè)共同點(diǎn)：1.Jp是非負(fù)，即Jp≥0；2.當(dāng)兩類完全不交迭時(shí)Jp達(dá)到其最大值；3.當(dāng)兩類分布密度相同時(shí)，Jp＝05.2類別可分性判據(jù)2.基于概率分布的可分性判據(jù)381.Bhattacharyya距離（巴氏距離）：顯然，當(dāng)p(X|ω1)＝p(X|ω2)對所有X值成立時(shí)JB＝0，而當(dāng)兩者完全不交迭時(shí)JB無窮大。巴氏距離與錯(cuò)誤率的上界有直接關(guān)系，因此JB不僅用來對特征空間進(jìn)行降維優(yōu)化，而且也用來對分類器的錯(cuò)誤率作出估計(jì)。2.Chernoff（切諾夫）界限：其中S取[0，1]區(qū)間的一個(gè)參數(shù)，顯然在S＝0.5時(shí)就變?yōu)镴B式，因此JB是JC的一個(gè)特例。5.2類別可分性判據(jù)2.基于概率分布的可分性判據(jù)393.散度：區(qū)分i，j兩類總的平均信息對wi類的平均可分信息對wj類的平均可分信息散度Jd為兩類平均可分信息之和wi，wj對數(shù)似然比5.2類別可分性判據(jù)2.基于概率分布的可分性判據(jù)40當(dāng)兩類樣本都服從正態(tài)分布，且協(xié)方差矩陣相等的情況下Mahalanobis距離5.2類別可分性判據(jù)散度為：這也等于兩類均值之間的Mahalanobis距離。2.基于概率分布的可分性判據(jù)41特征對分類的有效性也可以從后驗(yàn)概率角度來考慮。已知最佳分類器是由后驗(yàn)概率決定的，如果對某些特征，各類后驗(yàn)概率都相等，即：P(ωi|x)=1/c，其中c為類別數(shù)，則樣本的類屬就無法確定，或者只能任意指定樣本所屬類別。此時(shí)錯(cuò)誤率為(c-1)/c。5.2類別可分性判據(jù)3.基于熵的可分性判據(jù)42如果考慮另一極端，假設(shè)能有一組特征使得：P(ωi|x)=1,且P(ωj|x)=0,對任意j≠i。則此時(shí)樣本x肯定屬于ωi類，錯(cuò)誤率為0。由此可看出，后驗(yàn)概率越集中，錯(cuò)誤概率就越小，反之后驗(yàn)概率分布越平緩，即接近均勻分布，則分類錯(cuò)誤概率就越大。為了衡量后驗(yàn)概率分布的集中程度，借用信息論中熵的概念，定義了基于熵的類別可分性判據(jù)。5.2類別可分性判據(jù)3.基于熵的可分性判據(jù)43

把類別ωi,i=1,2,…,c看作一系列隨機(jī)事件，它的發(fā)生依賴于隨機(jī)向量x，給定x后ωi的后驗(yàn)概率是P(ωi|x)。

如果根據(jù)x能完全確定ω，則ω就沒有不確定性，對ω本身的觀察就不會(huì)再提供信息量，此時(shí)熵為0，特征最有利于分類；熵來度量均一性。

如果x完全不能確定ω，則ω不確定性最大，對ω本身的觀察所提供信息量最大，此時(shí)熵為最大，特征最不利于分類。5.2類別可分性判據(jù)3.基于熵的可分性判據(jù)44

■熵函數(shù)：衡量后驗(yàn)概率分布的集中程度■

Shannon熵：■平方熵：■熵函數(shù)期望表征類別的分離程度：5.2類別可分性判據(jù)3.基于熵的可分性判據(jù)45特征選擇5.1引言5.2類別可分離性判據(jù)5.3特征子集的搜索策略46許多特征選擇算法力求解決搜索問題，經(jīng)典算法有：5.3特征子集的搜索策略471.單獨(dú)最優(yōu)特征組合計(jì)算各特征單獨(dú)使用時(shí)的可分性判據(jù)J并加以排隊(duì)，取前d個(gè)作為選擇結(jié)果組合起來不一定是最優(yōu)結(jié)果當(dāng)可分性判據(jù)對各特征具有(廣義)可加性，該方法可以選出一組最優(yōu)的特征來，例：各類具有正態(tài)分布各特征統(tǒng)計(jì)獨(dú)立可分性判據(jù)基于Mahalanobis距離5.3特征子集的搜索策略482.順序前進(jìn)法（SFS）:最簡單的自下而上搜索算法自下而上搜索方法。每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得的可分性或分類識(shí)別率為最大，直至特征數(shù)增加到d為止。該方法考慮了所選特征與已入選特征之間的相關(guān)性。比單獨(dú)最優(yōu)特征組合效果好。缺點(diǎn)：一旦某特征已入選，即使由于后加入的特征使它變?yōu)槎嘁矡o法再把它剔除。5.3特征子集的搜索策略49推廣：3.廣義順序前進(jìn)法（GSFS），每次從未入選的特征中選擇出r個(gè)特征，使得這r個(gè)特征加入后J值達(dá)最大。SFS每次只增加一個(gè)特征，它未考慮未入選特征之間的統(tǒng)計(jì)相關(guān)性；GSFS法可以克服這個(gè)缺點(diǎn)，計(jì)算量增大，它比SFS更可靠，但仍然無法拿出已入選的特征。5.3特征子集的搜索策略504.順序后退法（SBS）：自上而下的方法該方法根據(jù)特征子集的分類表現(xiàn)來選擇特征搜索特征子集：從全體特征開始，每次剔除一個(gè)特征，使得所保留的特征集合有最大的可分性或分類識(shí)別率。依次迭代，直至可分性或識(shí)別率開始下降為止。和順序前進(jìn)法比較，順序后退法有兩個(gè)特點(diǎn)：計(jì)算過程中可以估計(jì)每此去掉一個(gè)特征所造可分性的降低；由于順序后退法的計(jì)算是在高位空間進(jìn)行的，所以計(jì)算量比順序前進(jìn)法要大推廣：廣義順序后退法5.3特征子集的搜索策略515.增l減r法（l-r）避免上述方法的一旦被選入（或剔除）就不能再剔除（或選入）的缺點(diǎn)，可在選擇過程中加入局部回溯過程。在第k步可先用SFS法一個(gè)個(gè)加入特征到k+l個(gè)，然后再用SBS法一個(gè)個(gè)剔除r個(gè)特征。5.3特征子集的搜索策略52步驟：假設(shè)已經(jīng)選了k個(gè)特征，得出特征組Xk1.用SFS法在未入選特征組XD-Xk中逐個(gè)選入特征l個(gè)，形成新特征組Xk+l，置k=k+l,

Xk=Xk+l2.用SBS法從Xk中逐個(gè)剔除r個(gè)最差的特征，形成新特征組Xk-r，置k=k-r,

若k=d則終止算法，否則，置Xk=Xk-r,轉(zhuǎn)向第一步。5.增l減r法（l-r）5.3特征子集的搜索策略53說明：當(dāng)l>r時(shí)，l-r法是自下而上的算法，先執(zhí)行第一步，然后執(zhí)行第二步，起始時(shí)應(yīng)置k=0,X0從空開始。當(dāng)l<r時(shí)，l-r法是自上而下的算法，先執(zhí)行第二步，然后執(zhí)行第一步，起始時(shí)應(yīng)置k=D,X0從全部特征開始。推廣：6.廣義l-r法，上述方法是逐個(gè)增加和逐個(gè)刪除的5.增l減r法（l-r）5.3特征子集的搜索策略546.遺傳算法從生物進(jìn)化論得到啟迪。遺傳，變異，自然選擇?；谠撍枷氚l(fā)展了遺傳優(yōu)化算法?；蜴湸a：待解問題的解的編碼，每個(gè)基因鏈碼也稱為一個(gè)個(gè)體。對于特征選擇，可用一個(gè)D位的0/1構(gòu)成的串表示一種特征組合。群體：若干個(gè)個(gè)體的集合，即問題的一些解的集合。交叉：由當(dāng)前兩個(gè)個(gè)體的鏈碼交叉產(chǎn)生新一代的兩個(gè)個(gè)體。變異：由一個(gè)鏈碼隨機(jī)選取某基因使其翻轉(zhuǎn)。5.3特征子集的搜索策略555.3特征子集的搜索策略56適應(yīng)度：每個(gè)個(gè)體xi的函數(shù)值fi，個(gè)體xi越好，適應(yīng)度fi越大。新一代群體對環(huán)境的平均適應(yīng)度比父代高。遺傳算法的基本框架：Step1:令進(jìn)化代數(shù)t=0。Step2:給出初始化群體P(t)，令xg為任一個(gè)體。Step3:對P(t)中每個(gè)個(gè)體估值，并將群體中最優(yōu)解x’與xg比較，如