第五講特征提取和特征選擇

1、模式識(shí)別講義2011版：第五講 特征捉取和特征選抒第五講特征提取和特征選擇、基本概念1、特征選取圖1特征選取的內(nèi)容在模式識(shí)別系統(tǒng)中，確定分類和學(xué)習(xí)過程所使用的特征是非常重要的一個(gè)環(huán) 節(jié)，獲得對(duì)分類最有效的特征，同時(shí)盡最大可能減少特征維數(shù)，是特征選収的主 要任務(wù)。特征選取可以分成原始特診的采集和轉(zhuǎn)換、有效特征的生成兩個(gè)步驟。(1) 原始特征的采集和轉(zhuǎn)換對(duì)于一個(gè)模式識(shí)別任務(wù)，見過模式采集和預(yù)處理得到的模式信息不一定能直 接用于模式分類，需要從中經(jīng)過數(shù)據(jù)處理和轉(zhuǎn)換得到對(duì)具體分類任務(wù)有效的特 征。例如對(duì)于模式采集到的圖像信息，其原始數(shù)據(jù)為像素點(diǎn)的顏色值矩陣，而對(duì) 于不同的模式識(shí)別任務(wù)和模式識(shí)別算法，可

2、以提取出不同類型的特征：輪廓特征：圖像中物體的邊緣輪廓顏色特征：圖像中顏色分布和均值紋理特征：圖像各個(gè)部位的主體紋理 數(shù)學(xué)特征：各像素點(diǎn)相關(guān)性等其他物理意義不明顯的數(shù)學(xué)特征(2) 有效特征的生成在獲得了原始特征后，需要生成有效的特征，其主要目的是大幅度降低特征 維度，減少模式識(shí)別算法的計(jì)算量。如果不經(jīng)過這一降維過程，可能出現(xiàn)“維數(shù) 災(zāi)難”，無法進(jìn)行有效的模式識(shí)別分類。例如：在文本分類中，如果采用原始的 詞頻統(tǒng)計(jì)數(shù)據(jù)作為分類特征，則有多少個(gè)不同的詞就有多少維特征，一片長(zhǎng)文的 特征維度會(huì)超過1000維，基本無法進(jìn)行計(jì)算。在降低特征維度的同時(shí)，還要提升所獲得特征的有效性，因?yàn)楸M管特征數(shù)量 越多，用于

3、分類的信息也越充足，但特征數(shù)星與分類有效性之間并不是線性關(guān)系。 降維到同樣數(shù)量時(shí)，不同的特征對(duì)分類的有效性是不同的。特征選取需要采用適 當(dāng)?shù)乃惴ǎ诮档吞卣骶S度的同時(shí)，最大可能地保留對(duì)分類有效的信息。特征選取的主要方法包括特征提取和特征選擇。前考從高維特征空間映射得 到低維待征空間，新的特征和舊的特征并不相同；而后者是從高維特征中選擇一 部分特征組成低維特征空間，并不改變每個(gè)特征維度本身。2、特征提取特征提取是通過某種變換，將原始特征從高維空間映射到低維空間。A： 4匕/稱為特征提取器，通常是某種正交變換。對(duì)于各種可能的特征提取器，需要選擇最優(yōu)的一種，也就是降維后分類最有 效的一種，通常設(shè)定一

4、個(gè)準(zhǔn)則函數(shù)幾4),使得取到最優(yōu)特征提取時(shí)，準(zhǔn)則函數(shù)值 取到最大值，即J(X*)=max J()o3>特征選擇特征選擇是從高維特征中挑選出一些最有效的特征，以達(dá)到降低特征空間維 數(shù)的目的。S：x“2,兒yt w S,Z = 1,2,.,;d <D原始特征集合S中包含D個(gè)特征，目標(biāo)特征集合F中包含d個(gè)特征。同樣，對(duì)于各種可能的特征選擇方案，需要選擇最優(yōu)的一種，也就是降維后 分類最有效的一種，通常設(shè)定一個(gè)準(zhǔn)則函數(shù)<7(5),使得取到最優(yōu)特征選擇時(shí)，準(zhǔn) 則函數(shù)值取到最大值，即J(F*)=max<7(/904、準(zhǔn)則函數(shù)的選取(1)準(zhǔn)則函數(shù)的選取原則在設(shè)定了準(zhǔn)則函數(shù)后，求取最優(yōu)的特

5、征提取或特征選擇可以看作一個(gè)泛函求 極值的問題，因此，準(zhǔn)則函數(shù)的選取是特征提取或特征選擇算法的關(guān)鍵。分類正確率是最佳的準(zhǔn)則函數(shù)，如果經(jīng)過某種方案的特征提取或特征選擇 后，得到的低維特征是所有可能方案中分類正確率最高的，就是最優(yōu)的特征提取或特征選擇。但是分類正確率難以直接計(jì)算，因此可以用特征選取方案對(duì)類別的可分性測(cè)度作為準(zhǔn)則函數(shù)，通常兩類之間的類別可分性測(cè)度要滿足以下標(biāo)準(zhǔn)：與分類正確率有單調(diào)遞增關(guān)系d當(dāng)特征獨(dú)立時(shí)具有可加性，即人（兀,花k-1%>0,當(dāng)iH丿時(shí)具有標(biāo)量測(cè)度特性：爲(wèi)=0,當(dāng)心川寸JfJ,對(duì)特征數(shù)最具單調(diào)性，W：（.丫,?！?兀力）V J/;（ X，兀2，,Xd，Xd+i）常用

6、的類別可分析測(cè)度有基于類內(nèi)類間距離和概率距離兩種。（2）類內(nèi)類間距離對(duì)于一個(gè)己知的樣本集，類內(nèi)類間距離的數(shù)學(xué)定義為：設(shè)一個(gè)分類問題共有c類，令瑠，x嚴(yán)分別為®類及何類中的D維 特征向量，（球，堺）為這兩個(gè)向量間的出羈，則各類中各特征 向量之間的距離的平均值，稱為類內(nèi)類間距離：1 cC1 叫 Y陸）二扭吃弓補(bǔ)工D （昭堺）厶 i=l y=l ninj *=1 /=1川為q中的樣本數(shù).4為呼P的樣本數(shù)，Pi. B是各類的先驗(yàn)概率。例:第3頁門動(dòng)化學(xué)院模式識(shí)別與智能系統(tǒng)研究所高琪 cn模式識(shí)別講義2011版：第五講 特征捉取和特征選抒1601234心）巧+士 $?

7、（対），申）-E 7=1 叭"）k=l f=lc = 2,片=0.6, P? = °4 加1 = 3, /I? = 2無（??；1>£巧想Ei?（昭堺） -口 ；=1 ninj k=l Z=11 1 3 3V加號(hào)占工1?（職）- * * E M3“+;恥殆工玄理,申）_I M3- 1 k-1 M- 一 n m對(duì)于隨機(jī)性的統(tǒng)計(jì)分類，如果樣本集是給定的，則無論其中各類樣本如何劃 分，類內(nèi)類間距離都是相等的，也就是說，類內(nèi)類間距離本身和分類錯(cuò)誤率不相 關(guān)，不能直接用于類別可分性測(cè)度。雖然類內(nèi)類間跖離本身不能用作類別可分性測(cè)度，但對(duì)其進(jìn)行分解處理后， 可以得到與類別可

8、分性相關(guān)的測(cè)度指標(biāo)。如采用均方歐氏距離來 度量?jī)蓚€(gè)特征向量之間的距離, 則有5（£,卻）= （£_£）円垃）_申） 用表示第F類樣本集的均值向量:叫=古丈 £'k = l用加表示所有各類樣本集的總均值向量：m = Vil則AlJd（x）=工B右工-"山-"叫）+ （叫-第#頁門動(dòng)化學(xué)院模式識(shí)別與智能系統(tǒng)研究所高琪 cn模式識(shí)別講義2011版：第五講特征捉取和持征選擇令類內(nèi)離散度矩陣和類間離散度矩陣分別為Sb = 丫 m ： - m X"巧一 m 廣i=i則 Jdx） = rr（Sw + Sb

9、）= ”（S“）+ ”（軌）=Jw + Jb兒稱為類內(nèi)平均距離，厶稱為是類間平均距離。從類別可分性的要求來看, 希望厶盡可能小，厶盡可能大。(3) 概率距離類間的概率距離可用分布函數(shù)之間的距離來度最，例如對(duì)兩類問題：當(dāng)兩類完全可分時(shí)，若p(x <0 0 HO,則p(x o>J=0；當(dāng)兩類完全不可分時(shí): 對(duì)任意x,都有p(x cjj) = p(x2)： 一般情況下，兩類會(huì)介于完全可分和完全 不可分之間。依據(jù)以上度量方式，可定義類別可分析的概率距離準(zhǔn)則：若任何函數(shù)兒() = Jgp(x|0),p(x|初)，片，鈕dx滿足以下條件：a、Jp >0；b、當(dāng)兩類完全可分時(shí) <，取

10、得最大值；c、當(dāng)炳類完仝不可分是 丿戸為0；則可作為兩類之間可分性的概率距離度呈。二、使用類內(nèi)類間距離進(jìn)行特征提取1、準(zhǔn)則函數(shù)的構(gòu)造類內(nèi)類間距離可表示為：Jd=Jw+Jb=tF(Sw+Sb)其中幾是類內(nèi)平均距離，是類間平均距離。對(duì)于一個(gè)給定的樣本集，人是固定不變的。而通過特征提取后，新獲得的特 征使得樣本集可以劃分為不同的類，最佳的特征提取應(yīng)當(dāng)是使得各類之間的可分 性最好，也就是幾最大，兒最小。因此，可以直接采用厶作為特征提取的準(zhǔn)則 函數(shù)，稱為刀準(zhǔn)則。但直接使用準(zhǔn)則難以得到可行的特征提取算法，考慮到類內(nèi)離散度矩陣Sw 和類間離散度矩陣Sb是對(duì)稱矩陣，跡和行列式值在正交變換下具有不變性，常 第5

11、頁門動(dòng)化學(xué)院模式識(shí)別與智能系統(tǒng)研究所 高琪 cn模式識(shí)別講義2011版：第五講 特征捉取和特征選抒構(gòu)造以下兒種特征提取準(zhǔn)則函數(shù):tr(Sw)Sw + SbJ5=Sw(、SbJ2 = tr(Sn lSb J3 = ln, Sw2、基于丿2準(zhǔn)則的特征提取算法假設(shè)有D個(gè)原始特征：x = x1,x2,.9xdt通過特征提取后壓縮為個(gè)特征：廠其映射關(guān)系為：y = WTx令凡、冷為原始特征空間中樣本集的離散度矩陣，S；、S為特征提取 后新特征空間中樣本集的離散度矩陣，則有：對(duì)于力準(zhǔn)則，進(jìn)行特征提取后，準(zhǔn)則函數(shù)值為：力=trss；）= tr（WTSyWTSbW求最優(yōu)的特征提取，就是

12、求址優(yōu)的變換陣"，使得準(zhǔn)則函數(shù)值在此變換下能 取得最大值。將準(zhǔn)則函數(shù)對(duì)"求偏導(dǎo)，并令其為0,解出的"就是可使得準(zhǔn)則函數(shù)刀取 得最大值的變換陣。結(jié)論為：將矩陣的特征值按大小排序：入2毎.上心則前d個(gè)特征值對(duì)應(yīng)的特征向量耳,畑,兒可構(gòu)成變換陣W.即爐二叢，如，,“訂此時(shí)的準(zhǔn)則函數(shù)值為：丿2（ W） =£兒1=1基于J2準(zhǔn)則的特征提取算法事實(shí)上是保留了原特征空間中方差最大的特征 維度成份。例題：給定先驗(yàn)概率相等的兩類，其均值向最分別為：曲=1,3,-1丁 和“2 =-l,-lJr,協(xié)方差矩陣為：_4 1 0_1 1 0_5=1 4 0,£>=1

13、 2 00 0 10 0 1試基于4準(zhǔn)則求最優(yōu)特征提取。解：進(jìn)行特征提取前總均值向量為：“ =|（/Z14-/Z2） = OJ,OF 類間離散度矩陣為：1 2為=5工（“一“也一 "）7 21 24-1 -2-1-21類內(nèi)離散度矩陣為:3-10_，sg 12-1-13010-50088-168310130001-1 = 1_8因?yàn)镾，Sb的秩為1,因此&鼻只有一個(gè)非0特征值，"是DX1維的矩 陣,即向量w。求解方程得最優(yōu)特征提収變換陣為：w = 6（1,5, - 8）了O三、特征選擇算法特征選擇是從D個(gè)特征中挑選出最有效的d個(gè)特征的過程，常用的算法有 以下兒種。1、

14、獨(dú)立算法獨(dú)立算法是指分別計(jì)算D個(gè)特征單獨(dú)使用時(shí)的準(zhǔn)則函數(shù)值，選取最優(yōu)的前d 個(gè)特征。除非各特征相互獨(dú)立，準(zhǔn)則函數(shù)滿足可加性，否則獨(dú)立算法所得到的特征組 合均不能保證是最優(yōu)的特征組合。因此除特殊情況外，獨(dú)立算法并不實(shí)用。第7頁門動(dòng)化學(xué)院模式識(shí)別與智能系統(tǒng)研究所高琪 cn模式識(shí)別講義2011版：第五講 特征捉取和特征選擇2、窮舉算法特征選擇是一個(gè)組合過程，因此如從D個(gè)特征中考査所有可能的d個(gè)特征 組合，計(jì)算其準(zhǔn)則函數(shù)，找到最優(yōu)的一個(gè)，從而得到最佳的特征選擇結(jié)果，就是 窮舉法的算法。D(Z>-J)!J!窮舉法可以保證得到所有解中的全丿最優(yōu)解，但問題是計(jì)算星太大，例如當(dāng)

15、 D=1OO, d=10,需要經(jīng)過(100-10)110 =17310309456440次計(jì)算才能得到特征選擇結(jié)果，這在有限資源下基本是無解的。3、分支定界算法（D算法原理分支定界算法依賴于特征選取準(zhǔn)則函數(shù)構(gòu)造時(shí)的特性，即：準(zhǔn)則函數(shù)值對(duì)特 征數(shù)量具有單調(diào)性，xd) < Ji)(xi9x2,.9xd,xd) o此時(shí)如果某組合包含上+1個(gè)特征，其準(zhǔn)則函數(shù)值已經(jīng)驗(yàn)證比另一種上個(gè)特征 的組合的準(zhǔn)則函數(shù)值小，則在這XI個(gè)特征中繼續(xù)去除特征，準(zhǔn)則函數(shù)值只會(huì)更 小，不能達(dá)到求取準(zhǔn)則函數(shù)最大值的目的，可以不再繼續(xù)計(jì)算。其具體原理為：1）從原始的特征數(shù)D開始依次減少特征數(shù)，直至到達(dá)所需的特征數(shù)d:2）將過

16、程中所有可能的組合情況組合成一棵搜索樹：特征數(shù)少的組合作為特 征數(shù)多的組合的子節(jié)點(diǎn)；3）按特定路線遍歷整個(gè)搜索樹，計(jì)算所遇到的每一個(gè)節(jié)點(diǎn)的準(zhǔn)則函數(shù)，尋找 最大的準(zhǔn)則函數(shù)值，此時(shí)對(duì)應(yīng)的特征組合就是最優(yōu)的特征選擇；4）如遇到某個(gè)節(jié)點(diǎn)的準(zhǔn)則函數(shù)值比已得到的特征數(shù)更少的節(jié)點(diǎn)的準(zhǔn)則函數(shù) 值還小，則放棄其下所有節(jié)點(diǎn)的計(jì)算。顯然，分支定界法是一種窮舉算法，它在準(zhǔn)則函數(shù)丿對(duì)特征數(shù)量單調(diào)的情況 下能保證取得最優(yōu)解。但其搜索樹的所有節(jié)點(diǎn)如都需要計(jì)算一遍，則計(jì)算量遠(yuǎn)大 于只從D個(gè)特征中考査所有d個(gè)特征組合的窮舉法；只有當(dāng)計(jì)算過程中利用準(zhǔn) 則函數(shù)J對(duì)特征數(shù)量的單調(diào)性跳過大量節(jié)點(diǎn)計(jì)算時(shí)，計(jì)算星才有可能比窮舉法 少。（3

17、）搜索樹的構(gòu)造分支定界法的搜索樹可以按照以下原則構(gòu)造：根節(jié)點(diǎn)為0級(jí)，包含Q個(gè)特征； 每一級(jí)舍棄1個(gè)特征；下一級(jí)在上一級(jí)基礎(chǔ)上繼續(xù)舍棄特征； 整個(gè)搜索樹共有D-d級(jí)，每個(gè)葉節(jié)點(diǎn)代表了一種所需的d個(gè)特征組合:為避免組合重復(fù)，從左至右每個(gè)子樹包含的分支依次減少，對(duì)搜索樹進(jìn) 行簡(jiǎn)化。例：原始特征=心衛(wèi)丸3兀， D=4,d=2圖3原始的搜索樹圖4簡(jiǎn)化的搜索樹（3）搜索路由分支定界法對(duì)搜索樹的遍歷可以采用回溯法，也可以采用剪枝法。剪枝法是先計(jì)算少數(shù)兒個(gè)葉節(jié)點(diǎn)的準(zhǔn)則函數(shù)值，然后從上到下依次處理各層 節(jié)點(diǎn)，把那些準(zhǔn)則函數(shù)值小于已知葉節(jié)點(diǎn)準(zhǔn)則函數(shù)值的節(jié)點(diǎn)的以下分支均剪除 掉，直至獲得無法剪除的所有葉節(jié)點(diǎn)，再從中

18、選擇準(zhǔn)則函數(shù)值最大的一個(gè)作為最 優(yōu)特征選擇方案?；厮莘▽?duì)搜索樹的遍歷路由是：1）從根節(jié)點(diǎn)開始，沿最右邊路徑下行，計(jì)算每個(gè)節(jié)點(diǎn)的丿值，把第一個(gè)遇到 的葉節(jié)點(diǎn)的丿值設(shè)為邊界初值沿原路徑回溯，遇到第一個(gè)分叉點(diǎn)后沿 新路徑下行，計(jì)算遇到的每個(gè)節(jié)點(diǎn)的丿值；2）如遇到某節(jié)點(diǎn)的丿值小于則放棄其下的所有分支的計(jì)算，向上回溯；3）如遇到下一個(gè)葉節(jié)點(diǎn)的丿值大于E,則更新8為新的葉節(jié)點(diǎn)的丿值。4）遍歷整個(gè)搜索樹，最終得到的£值對(duì)應(yīng)的葉節(jié)點(diǎn)，就是最優(yōu)特征組合。更新B初始圖5搜索樹的回溯法遍歷例題：有一個(gè)分類問題，原始特征空間包含5個(gè)特征，試選擇2個(gè)最重要的特征來 降低特征空間的維數(shù)。各特征間是相互獨(dú)立的，并且都有一個(gè)獨(dú)立的重要性指數(shù)，其值如下：特征X1X2X4“5重要性0.10.4解：因各特征是相互獨(dú)立的，所以特征組合的準(zhǔn)則函數(shù)值/可由組合中各特征的 準(zhǔn)則函數(shù)值/(X相加得到。*3 X4 xs X4(J=O. 9)xs(J=0.6)x5(J=0.8) x4 K xs(J=0.5) xs(J=O. 7)B=0.9B=0.8B=0.7得到最優(yōu)特征選擇為小吳5，這和獨(dú)立