模式識別-第10講-特征的選擇與提取2

模式識別

授課教師薛耀紅xueyh@第10講特征的選擇與提取(2)本節(jié)課主要內(nèi)容1類別可分離性判據(jù)2特征提取3特征選擇§3特征選擇1最優(yōu)搜索算法2次優(yōu)搜索法3可分性判據(jù)的遞推計算4.特征選擇的幾種新方法

特征選擇的任務(wù)是從一組數(shù)量為D的特征中選擇出數(shù)量為d（D>d）的一組最優(yōu)特征來.

利用窮舉法總可以找出最優(yōu)的特征集,但計算量太大.從D個特征中選取d個,共

種組合。如:若D=20,d=10,則從D個特征中選取d個特征的組合數(shù)q=184756,對每一種組合需要計算判據(jù)值J(x)最優(yōu)特征的選擇，要解決兩個問題:選擇的標(biāo)準(zhǔn)，這可以用類可分離性判據(jù).確定一個較好的算法，以便找出最優(yōu)的特征集.本節(jié)主要討論第二個問題，簡單介紹幾種優(yōu)化算法.自下而上法

特征數(shù)從0逐步增加到d用優(yōu)化算法進(jìn)行特征選擇的兩種策略:自上而下法

從特征數(shù)從D開始逐步減少到d1.最優(yōu)搜索算法到目前為止唯一能獲得最優(yōu)結(jié)果的搜索方法是“分支定界”算法，它是一種“自上而下”的方法，但具有回溯功能，可使所有可能的特征組合都被考慮到。由于合理的組織搜索過程，使得有可能避免計算某些特征組合而不影響結(jié)果為最優(yōu)。整個搜索過程可用樹來表示樹的根結(jié)點(diǎn)表示原始特征集,其他結(jié)點(diǎn)表示從其父結(jié)點(diǎn)所代表的特征子集中去掉某一特征后所得到的特征子集,結(jié)點(diǎn)上的標(biāo)號是去掉的特征的編號.分支定界法的搜索樹示意圖(D=6，d=2)根結(jié)點(diǎn):原始特征集結(jié)點(diǎn)標(biāo)號:去掉的特征每一結(jié)點(diǎn)表示去掉若干特征后得到的子集.從左到右同一級結(jié)點(diǎn)對應(yīng)的特征子集的類可分性判據(jù)值遞增.說明分支定界法之所以有效,這主要是利用了可分離性判據(jù)的單調(diào)性，即對有包含關(guān)系的特征組Ak，k=1，2，……，I，即有：可分性判據(jù)滿足：2.次優(yōu)搜索法最優(yōu)搜索法在有些情況下計算量太大而難以實(shí)現(xiàn)，這時不得不放棄最優(yōu)解而采取計算量較小的次優(yōu)搜索方法。下面我們介紹一些不同的算法，面對實(shí)際問題時可靈活選擇。（1）單獨(dú)最優(yōu)特征組合最簡單的方法是計算各特征單獨(dú)使用時的判據(jù)值并加以排隊，取前d個作為選擇結(jié)果。但我們需要注意的是，即使各特征是統(tǒng)計獨(dú)立的，這一結(jié)果也不一定就是最優(yōu)結(jié)果。只有當(dāng)可分性判據(jù)J可寫為如下兩種形式時，這種方法才能選出一組最優(yōu)的特征來：（2）順序前進(jìn)法（SFS）這是最簡單的“自下而上”的搜索方法。每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得判據(jù)J值為最大，直到特征數(shù)增加到d為止（3）順序后退法（SBS）它與順序前進(jìn)法的思路剛好相反。這是一種“自上而下”的方法，從全體特征開始每次剔除一個，所剔除的特征應(yīng)使仍然保留的特征組的判據(jù)J值最大，直到特征數(shù)減少到d為止。和順序前進(jìn)法比較，該方法用兩個特點(diǎn)：一是在計算過程中可以估計每去掉一個特征所造成可分性的降低；二是由于它的計算是在高維空間中進(jìn)行的，所以計算量比較大。比方說，在第k步可先用SFS法一個個加入特征到k+l

個，然后再用SBS法一個個剔去r個特征，我們把這樣一種算法叫增l減r法（l–r法）（4）增

l減

r法（l–r法）這種方法是基于前兩種算法的特點(diǎn)提出的.為了避免前面方法的一旦被選入(或剔除)就不能再剔除(或選入)的缺點(diǎn)可在選擇過程中加入局部回溯過程。3.可分性判據(jù)的遞推計算所有上述搜索算法都有一個共同點(diǎn)，即第k

步特征組是在第k–1步特征組上加入或剔除某些特征來構(gòu)成的，因此我們可以分析一下，是否有可能從k–1步的判據(jù)值J(k-1)推算出J(k),而不必完全重新計算.事實(shí)上，對于這些判據(jù)遞推關(guān)系是存在的，即求J(k)時可在J(k-1)的基礎(chǔ)上把新加入（或剔除）特征的影響加進(jìn)去即可，不必從頭算起，這樣就大大簡化了計算工作.我們注意到在進(jìn)行特征選擇時需要以可分性判據(jù)來度量特征選擇的好壞.特征選擇是一個組合優(yōu)化問題,因此可以使用解決優(yōu)化問題的方法來解決特征選擇問題.優(yōu)化問題是很多研究人員關(guān)注的一個熱點(diǎn)問題，近年來出現(xiàn)了一些有特色的解決方法,如:1)模擬退火算法2)遺傳算法3)Tabu搜索算法4.特征選擇的幾種新方法來源于統(tǒng)計力學(xué)。材料粒子從高溫開始，非常緩慢地降溫(退火)，粒子就可在每個溫度下達(dá)到熱平衡。假設(shè)材料在狀態(tài)i的能量為

E(i)，那么材料在溫度

T時從狀態(tài)i進(jìn)入狀態(tài)j遵循如下規(guī)律1)模擬退火算法如果

E(j)≤E(i)，接受該狀態(tài)被轉(zhuǎn)換。如果

E(j)>E(i)，則狀態(tài)轉(zhuǎn)換以如下概率被接受：1)模擬退火算法模擬退火優(yōu)化法：f

:x→R+，其中x∈S，表示優(yōu)化問題的一個可行解。N(x)≤S

表示x的一個鄰域集合。首先給定初始溫度T0和初始解

x(0)，以概率P生成下一個新解x’1)模擬退火算法對于溫度Ti和該優(yōu)化問題的解x(k)，可以生成新解x’經(jīng)過多次轉(zhuǎn)換，降低溫度得到

T

i+1<

Ti。在Ti+1下重復(fù)上述過程，最終的解是對該問題尋優(yōu)的結(jié)果。1)模擬退火算法:步驟Step1:

令i=0,k=0,給出初始溫度T0和初始特征組合x(0)。Step2:

在x(k)的鄰域N(x(k))中選擇一個狀態(tài)x’，即新特征組合。計算其可分性判據(jù)J(x’)，并按概率P接受x(k+1)=x’。Step3:

如果在Ti下還未達(dá)到平衡，則轉(zhuǎn)到Step2。Step4:

如果Ti已經(jīng)足夠低，則結(jié)束，當(dāng)時的特征組合即為算法的結(jié)果。否則繼續(xù)。Step5:

根據(jù)溫度下降方法計算新的溫度Ti+1。轉(zhuǎn)到Step2。該算法受進(jìn)化論啟迪，根據(jù)“物競天擇，適者生存”這一規(guī)則演變.2)遺傳算法基因鏈碼：使用遺傳算法時要把問題的每個解編碼成一個基因鏈碼。比如要從D個特征中挑選d個,就用一個D位的0或1組成的字符串表示一種特征組合。1表示該特征被選中，每個基因鏈碼代表一個解，稱作一個“個體”，其中的每一位看作一個“基因”群體：若干個體的集合，也就是一些解的集合交叉：選擇群體中的兩個個體，以這兩個個體為雙親作基因鏈碼的交叉，從而產(chǎn)生兩個新的個體，作為后代。2)遺傳算法變異：對某個體，隨機(jī)選取其中一位，將其翻轉(zhuǎn)適應(yīng)度：對每個解，以給定的優(yōu)化準(zhǔn)則來評價其性能的優(yōu)劣，作為其適應(yīng)度，即函數(shù)fi的值，個體xi越好，fi越大。新一代群體對環(huán)境的平均適應(yīng)度比父代高Step1:令進(jìn)化代數(shù)t=0。Step2:給出初始化群體P(t)，令xg為任一個體。Step3:對P(t)中每個個體估值，并將群體中最優(yōu)解x’

與xg比較，如果x’的性能優(yōu)于xg，則xg=x’Step4:如果終止條件滿足，則算法結(jié)束，xg為算法的結(jié)果。否則繼續(xù)。Step5:從P(t)中選擇個體并進(jìn)行交叉和變異操作，得到新一代群體P(t+1)。令t=t+1,轉(zhuǎn)到Step3。2)遺傳算法：步驟關(guān)于遺傳算法的說明：由步驟3保證了最終解是所搜索過的最優(yōu)解常用的終止條件是群體的世代數(shù)超過一個給定值，或連續(xù)數(shù)個世代都沒有得到更優(yōu)解群體的大小和演化代數(shù)是值得重視的參數(shù)。在一定范圍內(nèi)，這兩個參數(shù)大些能得到更好的解對交叉的親本選擇可采用如下規(guī)則：個體的性能越好，被選中的可能性也越大3)Tabu搜索算法自學(xué)…本節(jié)課結(jié)束謝謝大家！經(jīng)過有限次轉(zhuǎn)換，在溫度Ti下的平衡態(tài)xi的分布為1)模擬退火算法當(dāng)溫度T降為0時，xi的分布為模式識別

授課教師薛耀紅xueyh@第9講特征的選擇與提取(1)本節(jié)課主要內(nèi)容1類別可分離性判據(jù)2特征提取3特征選擇

特征提取與選擇的基本任務(wù)是研究如何從眾多特征中求出那些對分類識別最有效的特征，從而實(shí)現(xiàn)特征空間維數(shù)的壓縮,即獲取一組“少而精”且分類錯誤概率小的分類待征.

可以把特征分為三類1物理的；2結(jié)構(gòu)的：易于為人的直覺感知，但有時難于定量描述，因而不易用于機(jī)器判別3數(shù)學(xué)的：易于用機(jī)器定量描述和判別，如基于統(tǒng)計的特征x1x2x3..xd對象模式的特征的有效性直接影響分類器的設(shè)計和性能.由信息獲取部分獲得的原始數(shù)據(jù)量一般是相當(dāng)大的.為了有效地實(shí)現(xiàn)分類識別，要對原始數(shù)據(jù)進(jìn)行選擇或變換，得到最能反應(yīng)分類本質(zhì)的待征，構(gòu)成特征向量.這就是特征抽取與選擇的過程.傳感器y1y2y3..ym學(xué)習(xí).訓(xùn)練選擇.提取分類器特征選擇：從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的，這個過程叫特征選擇。特征提?。涸谠继卣鞯木S數(shù)很高的情況下，通過映射（或變換）的方法用低維空間來表示樣本，這個過程叫特征提取，映射后的特征稱作二次特征。

特征形成：

根據(jù)被識別的對象產(chǎn)生出一組基本特征（也可稱為原始特征），它可以是計算出來的，也可以是用儀表或傳感器測量出來的,稱作原始特征。

有時特征提取和選擇并不是截然分開的。例如，可以先將原始特征空間映射到維數(shù)較低的空間，在這個空間中再進(jìn)行選擇以進(jìn)一步降低維數(shù)；也可以先經(jīng)過選擇去掉那些明顯沒有分類信息的特征，再進(jìn)行映射以降低維數(shù)。本講討論特征的選擇與提取方法.特征提取特征選擇細(xì)胞自動識別：原始測量：（正常與異常）細(xì)胞的數(shù)字圖像原始特征（特征的形成，找到一組代表細(xì)胞性質(zhì)的特征）：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，核漿比壓縮特征：原始特征的維數(shù)仍很高，需壓縮以便于分類（2種方式）1.特征提?。河糜成洌ɑ蚍Q變換）的方法把原始特征變換為較少的新特征2.特征選擇：從原始特征中去挑選出一些最有代表性的特征特征的選擇與提取舉例1特征的選擇與提取舉例2特征提取和選擇：對單個魚的信息進(jìn)行特征選擇，從而通過測量某些特征來減少信息量長度亮度寬度魚翅的數(shù)量和形狀嘴的位置，等等…分類決策：把特征送入決策分類器特征的選擇與提取舉例特征的選擇與提取舉例特征的選擇與提取舉例特征的選擇與提取舉例§1類別可分離性判據(jù)1.準(zhǔn)則函數(shù)-判據(jù)2.基于類間距離的可分性判據(jù)3.基于概率分布的可分性判據(jù)4.基于熵函數(shù)的可分性判據(jù)1.準(zhǔn)則函數(shù)特征選擇與提取的任務(wù):求出一組對分類最有效的特征。類別可分離性判據(jù)：衡量不同特征及其組合對分類是否有效的定量準(zhǔn)則理想準(zhǔn)則：某組特征使分類器錯誤概率最小常用類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)類別可分離性判據(jù)

我們可以依據(jù)某種準(zhǔn)則進(jìn)行特征提取和選擇，為此，應(yīng)當(dāng)首先構(gòu)造這樣的準(zhǔn)則——類別可分離性判據(jù)。這些判據(jù)應(yīng)能反映各類在特征空間中的分布情況，應(yīng)能刻畫各特征分量在分類識別中的重要性或貢獻(xiàn)。1類別可分離性判據(jù)滿足的要求（1）與錯誤概率（或其的上下界）有單調(diào)關(guān)系；（2）當(dāng)特征獨(dú)立時有可加性（3）具有“距離”的某些特性，即（4）對特征數(shù)目是單調(diào)不減，即加入新的特征后，判據(jù)值不減。

這里指出，所構(gòu)造的可分離性判據(jù)并不一定同時具有上述的四個性質(zhì)，但這并不影響它在實(shí)際使用中的性質(zhì)。下面對幾種常用的判據(jù)進(jìn)行討論。2.類內(nèi)類間距離各類樣本可以分開是因?yàn)樗鼈兾挥谔卣骺臻g的不同區(qū)域，顯然這些區(qū)域之間距離越大，類別可分性就越大。如何表示兩個類之間的距離?2.類內(nèi)類間距離點(diǎn)到點(diǎn)的距離點(diǎn)到點(diǎn)集的均方歐式距離類內(nèi)均值向量樣本總均值向量各類均值向量Pi

先驗(yàn)概率2.類內(nèi)類間距離類內(nèi)均方歐式距離類內(nèi)離差矩陣類內(nèi)離差矩陣SWi的跡等于類內(nèi)均方歐式距離兩類之間的均方距離C類特征向量之間的平均距離為：2.類內(nèi)類間距離(8-5)類內(nèi)平均距離類間距離(8-6)(8-1)2.類內(nèi)類間距離基于距離的準(zhǔn)則概念直觀，計算方便，但與錯誤率沒有直接聯(lián)系樣本類間

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

離散度矩陣類間可分離性判據(jù)1)基于類內(nèi)類間距離的可分離性判據(jù)是一種常用的判據(jù)，它實(shí)際上是各類向量之間的平均距離。2)具體而言，即J(x)表示各類特征向量之間的平均距離，我們通常認(rèn)為J(x)越大，可分離性越好。

3)這種判據(jù)優(yōu)點(diǎn)是計算簡單；缺點(diǎn)是當(dāng)類間距離較小，類內(nèi)距離較大時，判據(jù)仍有可能取得較大的值，而此時的可分離性并不大。2.類內(nèi)類間距離3.基于概率分布的可分性判據(jù)上面介紹的距離準(zhǔn)則是直接從各類樣本間的距離算出的,沒有考慮各類的概率分布,不能確切表明各類交疊的情況，因此與錯誤概率沒有直接聯(lián)系,下面提出一些基于概率分布的可分性判據(jù).兩個分布密度函數(shù)之間的距離

任何函數(shù)J，如果滿足下述條件，都可用來作為類分離性的概率距離度量。1)J具有非負(fù)性2)當(dāng)兩類完全不交疊時，J取最大值3)當(dāng)兩類分布密度相同時，J應(yīng)為0如圖所示，圖1表示兩類為完全可分的情況，而圖2則表示兩類完全不可分的。P（x∣ω1）=P（x∣ω2）圖2圖1P（x∣ω1）P（x∣ω2）=0(1)Bhattacharyya距離注：s是在[0,1]區(qū)間取值的一個參數(shù)，當(dāng)s=0.5時，上述二者相等(2)Chernoff距離定義散度等于各類平均可分信息之和：(3)散度對數(shù)似然比提供ω1類對ω2類的可分性信息ω1類對ω2類的平均可分性信息為4.基于熵函數(shù)的可分性判據(jù)

最佳分類器由后驗(yàn)概率確定，所以可由特征的后驗(yàn)概率分布來衡量它對分類的有效性。兩種特殊情形下最佳分類器的錯誤率:1)

各類后驗(yàn)概率是相等錯誤率錯誤率可見后驗(yàn)概率越集中,錯誤概率就越小.后驗(yàn)概率分布越平緩(接近均勻分布)，則分類錯誤概率就越大.

設(shè)ω為可能取值為ωi,(i=1,2,…,c)的一個隨機(jī)變量,

它的取值依賴于分布密度為p(x)的隨機(jī)向量x(特征向量),即給定x后ω的概率為p(ω/x).

為了衡量后驗(yàn)概率分布的集中程度，需要規(guī)定一個定量準(zhǔn)則.我們可以借助于信息論中關(guān)于熵的概念.

我們想知道的是：給定某一x后，我們從觀察得到的結(jié)

果中得到了多少信息?或者說ω的不確定性減少了多少?

從特征提取的角度看，顯然用具有最小不確定性的那些特征進(jìn)行分類是有利的。在信息論中用“熵”作為不確定性的度量.4.基于熵函數(shù)的可分性判據(jù)ωiωjωi

ωj

重疊程度越大熵函數(shù)值越大4.基于熵函數(shù)的可分性判據(jù)1)廣義熵α為大于1的正數(shù)2)Shannon熵4.基于熵函數(shù)的可分性判據(jù)3)平方熵為了對所提取的特征進(jìn)行評價，我們要計算空間每一點(diǎn)的熵函數(shù).在熵函數(shù)取值較大的那一部分空間，不同類的樣本必然在較大的程度上互相重疊.可以表征類別的分離程度，它可用來作為所提取特征的分類性能的準(zhǔn)則函數(shù).因此熵函數(shù)的期望值4.基于熵函數(shù)的可分性判據(jù)§2特征提取1按歐氏距離度量的特征提取方法2基于判別熵最小化的特征提取3兩維顯示y1y2y3yDox1x2xdo特征提取D>dY空間

D維原始特征集Y空間

d維新特征集變換確定變換的依據(jù):類別可分性判據(jù)目標(biāo):

在新的特征空間中,各類之間容易區(qū)分.§2特征提取

根據(jù)前面提到的類別可分離性判據(jù)。我們可以依據(jù)這些判據(jù)進(jìn)行特征的提取。

設(shè)原特征向量，對作線性變換，產(chǎn)生d維向量，，即

矩陣稱為特征提取矩陣或變換矩陣，稱為二次特征。①s階Minkowski度量多維空間中兩個向量之間有多種距離度量②歐氏距離在Minkowski度量中，令s=2，得到常用的歐氏距離：1.按歐氏距離度量的特征提取方法③Chebychev距離:棋盤距離④Mahalanobis距離:式中Q是給定的正定標(biāo)尺矩陣在實(shí)際應(yīng)用中，在計算的復(fù)雜性方面，在是否便于進(jìn)行解析分析以及用它進(jìn)行特征提取的效果方面都各不相同。由于歐氏距離在很多情況下便于分析和計算.前面已經(jīng)推導(dǎo)出了基于歐氏距離的一種度量函數(shù)，其中Sb為類間離散度矩陣,Sw為類內(nèi)離散度矩陣.同樣的，我們還可以提出下面各種判據(jù)：以J2為例,特征提取的步驟如下①

作線性映射：其中Y為D維原始特征向量；X為d維壓縮后的特征向量②

令其中Sw，Sb為原空間（即Y的）離散度矩陣，S*w，S*b為映射后（即X的）離散度矩陣。③J2的表達(dá)式為：④求變換矩陣W,使

J2（W）最大將上式對W的各分量求偏導(dǎo)數(shù)并令其為零,可以確定一個W，從而得到使判據(jù)達(dá)最大的變換W⑤新特征集為其中Y為原始特征集(D維),X為新特征集(d維)注:W的計算（適用于J2—J5判據(jù)）：則選前d個特征值對應(yīng)的特征向量作為W，即：

W=[u1,u2,……,ud

]此時2.基于判別熵最小化的特征提取上節(jié)中討論了用熵作為不確定性的一種度量的表達(dá)式，這里我們引入判別熵W(p,q)來表征兩類分布p(xi)和q(xj)差別大小,令：對于特征提取來說，我們應(yīng)該求得一組特征，它使上述判別熵最小。計算步驟如下:①A=G1-G2,G1，G2分別是第一類樣本集和第二類樣本集的協(xié)方差矩陣Y為所要求的一組特征，它使得判別熵最小③新特征集為②將矩陣A的特征值進(jìn)行排序選取前d個特征值對應(yīng)的特征向量構(gòu)成變換矩陣W=[U1，U2，……，Ud]3.兩維顯示

人的經(jīng)驗(yàn)和直觀對分類有很大作用，如果能將各樣本在特征空間的分布情況顯示出來，我們可以直接觀察哪些樣本聚集在一起，因而可能屬于一類。最好能把原來的高維特征空間映射到二維平面上顯示出來，這一映射要盡可能的保持原來樣本的分布情況，或者盡量使各樣本間相互距離關(guān)系保持不變.

上述所討論的各種變換方法有利于我們解決這樣一種兩維顯示的任務(wù).①線性映射兩維顯示只不過是前面所涉及的各種映射(線性)的一種特殊情況,即d=2②非線性映射對一些比較復(fù)雜的樣本,線性映射常不能滿足上面所提的保持分布不變的要求,可以用非線性映射替代設(shè)映射前兩點(diǎn)間距離為D，映射后該兩點(diǎn)間距離為D*.希望映射后D*盡可能等于D.令e=D–D*為任意兩點(diǎn)映射前后距離之差，我們要