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

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

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

與選擇分類(lèi)決策分類(lèi)器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Shannon熵：■平方熵：■熵函數(shù)期望表征類(lèi)別的分離程度：5.2類(lèi)別可分性判據(jù)3.基于熵的可分性判據(jù)45特征選擇5.1引言5.2類(lèi)別可分離性判據(jù)5.3特征子集的搜索策略46許多特征選擇算法力求解決搜索問(wèn)題，經(jīng)典算法有：5.3特征子集的搜索策略471.單獨(dú)最優(yōu)特征組合計(jì)算各特征單獨(dú)使用時(shí)的可分性判據(jù)J并加以排隊(duì)，取前d個(gè)作為選擇結(jié)果組合起來(lái)不一定是最優(yōu)結(jié)果當(dāng)可分性判據(jù)對(duì)各特征具有(廣義)可加性，該方法可以選出一組最優(yōu)的特征來(lái)，例：各類(lèi)具有正態(tài)分布各特征統(tǒng)計(jì)獨(dú)立可分性判據(jù)基于Mahalanobis距離5.3特征子集的搜索策略482.順序前進(jìn)法（SFS）:最簡(jiǎn)單的自下而上搜索算法自下而上搜索方法。每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得的可分性或分類(lèi)識(shí)別率為最大，直至特征數(shù)增加到d為止。該方法考慮了所選特征與已入選特征之間的相關(guān)性。比單獨(dú)最優(yōu)特征組合效果好。缺點(diǎn)：一旦某特征已入選，即使由于后加入的特征使它變?yōu)槎嘁矡o(wú)法再把它剔除。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更可靠，但仍然無(wú)法拿出已入選的特征。5.3特征子集的搜索策略504.順序后退法（SBS）：自上而下的方法該方法根據(jù)特征子集的分類(lèi)表現(xiàn)來(lái)選擇特征搜索特征子集：從全體特征開(kāi)始，每次剔除一個(gè)特征，使得所保留的特征集合有最大的可分性或分類(lèi)識(shí)別率。依次迭代，直至可分性或識(shí)別率開(kāi)始下降為止。和順序前進(jìn)法比較，順序后退法有兩個(gè)特點(diǎn)：計(jì)算過(guò)程中可以估計(jì)每此去掉一個(gè)特征所造可分性的降低；由于順序后退法的計(jì)算是在高位空間進(jìn)行的，所以計(jì)算量比順序前進(jìn)法要大推廣：廣義順序后退法5.3特征子集的搜索策略515.增l減r法（l-r）避免上述方法的一旦被選入（或剔除）就不能再剔除（或選入）的缺點(diǎn)，可在選擇過(guò)程中加入局部回溯過(guò)程。在第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說(shuō)明：當(dāng)l>r時(shí)，l-r法是自下而上的算法，先執(zhí)行第一步，然后執(zhí)行第二步，起始時(shí)應(yīng)置k=0,X0從空開(kāi)始。當(dāng)l<r時(shí)，l-r法是自上而下的算法，先執(zhí)行第二步，然后執(zhí)行第一步，起始時(shí)應(yīng)置k=D,X0從全部特征開(kāi)始。推廣：6.廣義l-r法，上述方法是逐個(gè)增加和逐個(gè)刪除的5.增l減r法（l-r）5.3特征子集的搜索策略546.遺傳算法從生物進(jìn)化論得到啟迪。遺傳，變異，自然選擇?；谠撍枷氚l(fā)展了遺傳優(yōu)化算法?；蜴湸a：待解問(wèn)題的解的編碼，每個(gè)基因鏈碼也稱(chēng)為一個(gè)個(gè)體。對(duì)于特征選擇，可用一個(gè)D位的0/1構(gòu)成的串表示一種特征組合。群體：若干個(gè)個(gè)體的集合，即問(wèn)題的一些解的集合。交叉：由當(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)度f(wàn)i越大。新一代群體對(duì)環(huán)境的平均適應(yīng)度比父代高。遺傳算法的基本框架：Step1:令進(jìn)化代數(shù)t=0。Step2:給出初始化群體P(t)，令xg為任一個(gè)體。Step3:對(duì)P(t)中每個(gè)個(gè)體估值，并將群體中最優(yōu)解x’與xg比較，如