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

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

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

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

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

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

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

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

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

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

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

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

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