模式識別patternrecognition特征選擇與提取

1、《模式識別》 《Pattern Recognition》特征選擇與提取,佘勇課件密碼 ： kys2006Tel:13980905197Email:sy@cuit.edu.cn辦公室：科教樓110,特征選擇與提取-關(guān)鍵性,特征選擇和提取是模式識別中的一個關(guān)鍵問題前面討論分類器設(shè)計(jì)的時候，一直假定已給出了特征向量維數(shù)確定的樣本集，其中各樣本的每一維都是該樣本的一個特征；這些特征的選擇是很重要的，它強(qiáng)烈地影響到分類器的設(shè)

2、計(jì)及其性能；假若對不同的類別，這些特征的差別很大，則比較容易設(shè)計(jì)出具有較好性能的分類器。,特征選擇與提取-復(fù)雜性,特征選擇和提取是構(gòu)造模式識別系統(tǒng)時的一個復(fù)雜的重要課題在很多實(shí)際問題中，往往不容易找到那些最重要的特征，或受客觀條件的限制，不能對它們進(jìn)行有效的測量；因此在測量時，由于人們心理上的作用，只要條件許可總希望把特征取得多一些；另外，由于客觀上的需要，為了突出某些有用信息，抑制無用信息，有意加上一些比值、指數(shù)或?qū)?shù)等組合計(jì)

3、算特征；如果將數(shù)目很多的測量值不做分析，全部直接用作分類特征，不但耗時，而且會影響到分類的效果，產(chǎn)生“特征維數(shù)災(zāi)難”問題。,特征選擇與提取的方法,為了設(shè)計(jì)出效果好的分類器，通常需要對原始的測量值集合進(jìn)行分析，經(jīng)過選擇或變換處理，組成有效的識別特征；在保證一定分類精度的前提下，減少特征維數(shù)，即進(jìn)行“降維”處理，使分類器實(shí)現(xiàn)快速、準(zhǔn)確和高效的分類?！敖稻S”處理方法：特征選擇特征提取,特征選擇,特征選擇：從一組特征中選擇一些最有效

4、的特征以達(dá)到降低特征空間維數(shù)的目的從n個度量值集合{x1, x2,…, xn}中，按某一準(zhǔn)則選取出供分類用的子集，作為降維（m維，m<n）的分類特征為達(dá)到上述目的，關(guān)鍵是所提供的識別特征應(yīng)具有很好的可分性，使分類器容易判別。為此：應(yīng)去掉模棱兩可、不易判別的特征；所提供的特征不要重復(fù)，即去掉那些相關(guān)性強(qiáng)且沒有增加更多分類信息的特征。,特征提取,特征提取:就是使n維特征(x1, x2,…, xn)通過某種變換，產(chǎn)生m個特征

5、(y1, y2,…, ym) (m<n) ，作為新的分類特征（或稱為二次特征）方法：基于K-L變換的特征提取,特征空間的一般處理方法,在一個實(shí)際系統(tǒng)的設(shè)計(jì)過程中，特征的選擇和提取過程一般都需要進(jìn)行首先進(jìn)行特征選擇，去除掉無關(guān)特征然后進(jìn)行特征提取，降低特征的維數(shù)然后利用降維之后的樣本特征來設(shè)計(jì)分類器,特征評判標(biāo)準(zhǔn)-類別可分性判據(jù),在分類器設(shè)計(jì)過程中，必須對所選取的特征進(jìn)行類別可分性評判類別的可分性判據(jù)：用這樣的可分性

6、判據(jù)可以度量當(dāng)前特征維數(shù)下類別樣本的可分性可分性越大，對識別越有利，可分性越小，對識別越不利 使分類器錯誤率最小的特征即為最好特征,類別可分性判據(jù),我們希望可分性判據(jù)滿足以下幾個條件：與錯誤率有單調(diào)關(guān)系，當(dāng)判據(jù)取最大值時，識別的錯誤率最小當(dāng)特征獨(dú)立時有可加性，即：Jij是第i類和第就類的可分性判據(jù)，Jij越大，兩類的可分程度越大，(x1,x2,…,xN)為N維特征；應(yīng)具有某種距離的特點(diǎn)： Jij＞

7、0，當(dāng)i≠j時 Jij＝0，當(dāng)i＝j(luò)時 Jij＝Jji單調(diào)性，加入新的特征后，判據(jù)不減?。?,,基于幾何距離的可分性判據(jù),基于距離的可分性判據(jù)出發(fā)點(diǎn)：各類樣本之間的距離越大、類內(nèi)散度越小，則類別的可分性越好距離的定義：1、點(diǎn)與點(diǎn)的距離：如歐氏距離、馬氏距離等，特征矢量和之間的距離可以表示為 歐氏距離：2、點(diǎn)與類別之間的距離：常用的有：平均樣本法、平均距離法、最近距離法等。

8、特征矢量與類別之間距離的平方可以表示（平均距離法）：,,,3、類內(nèi)距離,4、類間距離,基于距離的可分性判據(jù),有了距離度量之后，我們就可以在此基礎(chǔ)上定義可分性測度了?？梢杂酶黝悩颖局g的平均距離作為判據(jù) Jd(X)所反映的主要還是類別之間的分離程度，對類內(nèi)的聚集程度反映不夠。通常我們采用跟一般的矩陣形式來構(gòu)造可分性判據(jù),,類內(nèi)散度矩陣,類間散度矩陣,總體散度矩陣,常用的基于距離的可分性判據(jù),基于概率分布的可分性,基于距離的可分性判據(jù)

9、的局限性：基于幾何距離的可分性判據(jù)計(jì)算起來比較簡單，然而它沒有考慮各類別的概率分布，因此與識別錯誤率之間的聯(lián)系卻不是很緊密 基于概率分布的可分性判據(jù)基于概率的可分性判據(jù)優(yōu)點(diǎn)是直接與識別的錯誤率相聯(lián)系缺點(diǎn)是需要已知各個類別類概率密度函數(shù),基于概率分布的可分性實(shí)例,基于概率距離的可分性判據(jù),我們可以定義兩個類條件概率密度函數(shù)之間的距離JP作為交疊程度的度量，JP應(yīng)該滿足如下條件：,類之間的平均可分性,散度可分性判據(jù),幾種特征選擇方法

10、,特征選擇，就是從一組數(shù)量為的特征中選擇出一組數(shù)量為的最優(yōu)特征，（N＞M）這里有兩個問題要解決，1、選擇一種可分性判據(jù)作為最優(yōu)特征選擇的標(biāo)準(zhǔn)；2、找到一個好的算法，來選擇出這組最優(yōu)特征,獨(dú)立特征的選擇,假設(shè)N個特征之間相互獨(dú)立，并且使用的可分性判據(jù)滿足可加性：把N個特征每個單獨(dú)使用時的可分性判據(jù)計(jì)算出來，然后從大到小排序： 選擇出前M個特征就是一組最優(yōu)的特征,,,窮舉法,對從N中選擇出M個特征的所有組合情況都計(jì)算其可分性判據(jù)

11、，然后選擇出其中的最大者作為解決方案。當(dāng)N的數(shù)值比較小時，這種方法一定是可行的，然而當(dāng)N比較大時，這個組合數(shù)會非常大 需要有一個搜索算法來進(jìn)行特征選擇,最優(yōu)搜索算法—分支定界算法,利用的是可分性判據(jù)中的單調(diào)性質(zhì)： ，我們前面定義的各種判據(jù)都滿足這個性質(zhì)。分支定界算法實(shí)際上是對一個特征選擇的搜索樹進(jìn)行搜索,,,N=6，M=2時的搜索樹,分支定界搜索算法,次優(yōu)搜索算法-順序前進(jìn)法SFS

12、,次優(yōu)搜索算法-順序后退法SBS,同順序前進(jìn)法的過程剛好相反，最開始時取每次從中剔除一個特征，使得剩余的特征可分性判據(jù)最大,,次優(yōu)搜索算法-增l減r法,前兩種方法可以進(jìn)一步改進(jìn)，比如每次不是加入一個特征，而是加入l個特征；或者每次不是剔除一個特征，而是剔除r個特征。這樣的效果要比每次加1或減1的效果好，但是計(jì)算量要增大。另外一種改進(jìn)方法是將SFS和SBS結(jié)合如果l＞r，先使用SFS算法逐個選入個最佳特征，然后使用SBS算法逐個剔