模式識別特征的選擇和提取.ppt

1、第七章 特征的選擇和提取,7.1 引言,以前討論分類器設(shè)計時，都假定模式的特征向量已經(jīng)提取出來了（有多少特征確定了）。 特征的多少（維數(shù)）、”好壞” 對分類器的設(shè)計和性能有很大的影響。 好的特征容易把類分開，或表示時誤差較小。,1.特征的維數(shù)和特征的“好壞”,特征選擇和提取的任務(wù)是如何從許多特征中找出那些最有效的特征，把高維特征空間壓縮到低維特征空間。 特征的種類有物理的、結(jié)構(gòu)的、數(shù)學(xué)的。物理的、結(jié)構(gòu)的特征，人的感覺器官容易感受，數(shù)學(xué)的特征，如均值、相關(guān)系數(shù)、協(xié)方差矩陣的特征值和特征向量等。 物理和結(jié)構(gòu)特征和所處理的具體問題有關(guān)，在解決實際問題時可以依據(jù)具體問題而定。 這一節(jié)研究一般的特征提取

2、和選擇的方法。,2.幾個術(shù)語的含義,在一些書籍和文獻中，在不完全相同的意義上使用“特征提取”和“特征選擇”的術(shù)語。例如“特征提取”，有的專指特征的形成過程，有的指特征的形成、經(jīng)選擇或變換后得到有效特征的過程。 為了方便以后的討論，我們把特征提取、特征選擇的含義明確一下。,模式特征的產(chǎn)生過程一般包括以下步驟： 1原始特征的形成：用儀表或傳感器測量出來的一些特征量，或通過計算得到的一些特征（對波形和圖象），稱為原始特征、原始測量或一次特征。,2特征提?。涸继卣鞯臄?shù)量可能很大，需要通過變換（映射）把高維特征空間降到低維空間，這時的特征叫二次特征，它們一般是原始特征的某種組合。 通過變換A： X Y

3、， 測量空間 特征空間 需要盡可能多地保留對分類和表示有利的信息。好處 ：減少計算量; 在樣本少時，便于估計密度函數(shù)；提高分類器設(shè)計的性能。,3特征選擇：從得到的一組特征中，挑選最有效的特征以進一步減少特征空間的維數(shù)，得到它的一個有效子集。,特征的提取和選擇是人類的一項基本智能活動，從相關(guān)和不相關(guān)信息中找出主要因素。 例如在細胞識別中，用變換的方法較少的特征，用選擇的方法專家意見，或用數(shù)學(xué)方法進行篩選，從n個m個。 但“提取”和“選擇”不是截然分開的。 具體指什么要從上下文去理解。 特征選擇時，前m個最好的不一定組合后也是最好的。,特征提取可以看作是在減少維數(shù)的同時，又能代表、表示原觀測向量。

4、模式識別的任務(wù)是判別、分類。維數(shù)減少、一般錯誤率要增加，要限制在一定范圍內(nèi)。,7.2 基于特征向量分析的特征提取方法,這一節(jié)討論基于相關(guān)矩陣或協(xié)方差矩陣的特征向量的特征抽取方法。這一方法和統(tǒng)計上的主因子分析以及隨機過程中的K-L（Karhunen-Loeve）變換（展開）有密切關(guān)系。,1.模式最優(yōu)表示特征的提取,假定有一n維向量x，希望能用m（ n）個向量的線性組合來近似x，這m個向量來自一組標準正交基uj，j = 1，2，n。即把x近似表示為前m個基的組合： = y1u1 + y2u2 + + ymum 式中 yj = ujT x,寫成矩陣形式， = Um y ( n m，m 1 ) n 1

5、 y = UmT x ( m n，n 1 ) m 1 其中: y1 y = Um = u1 u2 um ym ,由于uj，j = 1，2，n是標準正交基，用 表示x時的誤差（殘差）為 = x - = 其中，yj = ujT x , j m問題是找一組基uj ，使得均方誤差 = E|2= E|x - |2 最小。這時的yi 就是從x導(dǎo)出的特征，而 y = umT x就表示特征變換（由n維m維）。,根據(jù)誤差公式和基是標準正交的條件， = ET = E（ ）（ ） = 如果把yj2 寫成yj2 =（yj）（yj）=（ujTx）(xTuj) 則 Eyj2=ujT ExxTuj =ujTRuj ， 其中

6、R是自相關(guān)矩陣,(*),= 要找一組基，使最小，同時要滿足： ujT uj = 1，j = m+1, , n.把約束ujT uj = 1用拉格朗日乘子（法）寫入誤差中，有 = +,（*）式的誤差化為：,=2(Ruj uj)=0, j = m+1，,n 上式說明uj必須是R的特征向量。 （Re =e） 這樣，= = =為了使最小，特征向量 um+1，un 必須是對應(yīng)最小特征值的，而近似x時所用的m個特征向量是對應(yīng)m個最大特征值的。,使取極值的必要條件是：,+,上面推導(dǎo)出的特征還有其它意義上的最優(yōu)性質(zhì)。一個分布的熵定義為 H = -Ep(y)粗略地說，當分布很平、延伸很廣時，熵最大。如果x是零均值

7、的高斯分布，那么可以證明所選擇的特征向量具有最大熵。這些特征向量沿最大方差方向，這樣的方向是最隨機的，最不確定的，這些方向應(yīng)保留下來作為特征。對最不確定的事，若有信息（測量），最有用。,例 三維觀測向量的特征提取 有一三維觀測向量，其相關(guān)矩陣為 3 -1 0 R = -1 3 0 00 3它的特征值和特征向量為1 = 4， 2 = 3， 3 = 2,1/ 0 1/ e1 = -1/ e2 = 0 e3 = 1/ 0 1 0要選一個特征，應(yīng)選e1方向，均方誤差是2 +3 = 5，要選兩個特征，應(yīng)選e1 、e2方向，均方誤差是3 = 2.,表示模式的特征和用于分類的特征的不同（1） 均值大小的影響

8、若均值較大，均值就會起大作用，特征在均值方向。當兩類問題的均值相差較大時，可以分類；但若均值差不多，則不會有好的效果。,m, R=+mmT,（2）也可以使用協(xié)方差矩陣，以均值為參考點，相對于均值。 （3）最好的表示特征不一定是最好的分類特征。（3）有時可將坐標系移到一個類的均值處，這時相關(guān)矩陣的最大特征值的特征向量將沿兩個均值的方向排列。,*7.3 多類問題的特征提取,下面介紹的方法是Fukunaga和Koontz在1970年提出的。出發(fā)點是要同時考慮所有的類。,1.兩類時的情況,令R1和R2分別是兩類觀測向量的相關(guān)矩陣。即 Ri = EixxT ，i = 1，2另 Q = R1 + R2令S

9、是一線性變換，使得STQS = ST R1S + ST R2S = I (*) (R1 + R2 = I),其中 1/ S = v1 v2 vn 1/ 1/vi和ui分別為Q的特征向量和特征值。,一般地說，S并不把R1和R2對角化，但通過S的線性變換，它把觀測向量x變?yōu)椋?x = STx 變換后的相關(guān)矩陣為Ri = STRiS由（*）式有 R1 + R2 = I （*）,STQS = ST R1S + ST R2S = I,現(xiàn)在考慮在變換后新坐標系下的特征。 首先，注意到R1和R2的特征向量是相同的。假設(shè)e是R1的一個特征向量，相應(yīng)的特征值是，由（*）式：R2 e = (IR1)e = e-e

10、 =(1-)e e也是R2的特征向量，相應(yīng)的特征值是(1),R1 + R2 = I,由于相關(guān)矩陣的R1 、R2是半正定的，它們的特征值是非負的， 01這樣，R1的大特征值正好是R2的小特征值，R1的小特征值正好是R2的大特征值，,這個關(guān)系如下圖： R1 1 e1 11 R2重 2 e2 12要 性 n-1 e n-1 1n-1減 n en 1n小 重要性減小,對類1是最好的表示方向，對類2是最壞的，反之亦然。如何來選特征呢？有兩種可能的方法。1每類各選m/2個最大特征值所對應(yīng)的特征向量，當m是奇數(shù)時，再選一個不管哪類的最大特征值所對應(yīng)的特征向量。2從兩類的特征值中，不管哪一類，選最大的m個特征

11、值所對應(yīng)的特征向量。一般地說，這兩種方法誰好誰壞和具體問題有關(guān)。,一旦特征向量選好后，則特征變換由下式確定： ej1T y = Tx = ej2T STx， ： ej1T 其中S是滿足STQS = I的矩陣。,* 2.C類時的情況,現(xiàn)在考慮將模式分為C類時的特征提取問題。模式原來是用n維測量空間的向量x來表示的。每類的相關(guān)矩陣為Ri = EixxT假定各個相關(guān)矩陣的最大特征值max1，這并不失一般性，可以通過調(diào)整線性空間的比例來實現(xiàn)。又由于相關(guān)矩陣是半正定的，各Ri的特征值在01之間。,和前面一樣，令uj，j = 1，2，n是觀測空間的標準正交基。另x是任一觀測向量,x是它的截尾表示形式，x

12、= y1u1 + y2u2 + + ymum對于第i類，我們選擇一組uj，它能使第i類的均方誤差最小，i = Ei|x-x|2 = （*）,而同時使其它類的均方誤差最大。 k = Ek|x-x|2 = (k = 1，2，c，ki) (*)單獨使i最小，而不管上式的條件已在前面討論過。若同時也滿足（*）式的條件，將使得所選擇的基能最優(yōu)的表示第i類，但不能最優(yōu)的表示其它類。由于一般不能同時使i最小，而k最大，下面引入另外一個相關(guān)的準則。,和7.2節(jié)一樣，可以表示 k = ，k=1，2，c由于Ri是半正定的，且max1， k的大小為下式限定： 0 kn-m， k =1，2，,c這樣，使（*）式最大等

13、價于使下式最小（ki）(nm)k = =,k = Ek|x-x|2 =,(k = 1，2，c，ki) (*),最大k（ki，k=1，2，,c）和最小i的準則可以寫成下面的組合形式，并用類數(shù)標準化。Ci=,把i = 和（nm）k的表達式代入，有 Ci =式中，Gi= (*)上式的準則在形式上和7.2節(jié)討論的一樣。為了選取m個特征向量ui來表示x,以使Ci最小，這時的特征向量應(yīng)是Gi 的最大的m個特征值所對應(yīng)的特征向量。,下面的分析說明確實是這樣。假定e是Gi的標準特征向量，那么相應(yīng)特征值可以表示為= eTGie = 由于max1和相關(guān)矩陣的半正定性質(zhì)，上式括號中每一個二次項的特征值在01之間，

14、01。而且接近于1時要求eTRie1,而eTRke(ki)卻0，,這樣，Gi的相應(yīng)于特征值接近1的特征向量對應(yīng)著i類最重要的特征。當e = 2 時，（*）式變?yōu)镚1 + G2 = I這和兩類時的情況相似，G1 和 G2 的特征向量相同，其特征值間的關(guān)系和變換后的矩陣R1 、R2時的一樣。,當C2時，情況就復(fù)雜了。上述的方法還可以進一步簡化?？梢园严嚓P(guān)矩陣進行變換，使它滿足 = = I線性變換S的推導(dǎo)和上節(jié)一樣。當使用變換后的相關(guān)矩陣時，Gi簡化為 Gi= 1/c 2 Ri +(C2)I當C = 2時，Gi= Ri，和前面的結(jié)果相同。,7.4 圖像特征抽取的奇異值分解法,一幅圖像可以表示為按一定

15、順序排列的像素的一個陣列（矩陣）。假定陣列有N行N列，這時觀測向量就由N2個像素的灰度值組成。由于觀測向量的維數(shù)很大，我們希望用（抽?。﹫D像的特征來表示圖像。,圖像特征抽取的方法有許多種。例如從二維頻率譜中抽取特征。這一節(jié)我們討論由一組基圖像的加權(quán)和表示圖像的方法，這種方法和前面討論過的利用特征值的特征抽取的方法很相似。,假定圖像是用一個NN的矩陣B表示的，B的元素表示像素的灰度值?？紤]兩個NN的標準正交矩陣U和V，矩陣B可以變換為另一矩陣A，A = UTBV由于U和V是標準正交的，所以信息并無損失。B可以通過下式（*） B = UAVT = 式中aij 是A的元素，Ui、Vj 是U和V的列向

16、量。,由于每一UiVjT都是一個NN矩陣，所以上式可以看作B圖像在一組基圖像下的展開，而aij是展開時的系數(shù)。特征抽取的思路是找一組基（圖像），從而可以用少數(shù)n個系數(shù)aij來表示原圖像。這時的圖像B是上式的截尾形式。而aij即它的特征。Hadamard、Harr和Fourier變換都可以實現(xiàn)這一目的。,下面要介紹的奇異值分解是另外一種方法。它使得矩陣A的元素只有對角線的元素非零。在這種基圖像下，原圖像只要用N個（或更少）的系數(shù)就可以表示了。,考慮下面的矩陣的積 BBT=UAVT .VATUT=UAATUT容易證明，BBT是對稱的和半正定的。因此它有N個非零的實特征值和N個線性獨立的特征向量。,

17、A = UTBV,B = UAVT,如果U的列向量取BBT的特征向量，則AAT是由BBT的特征值所形成的對角矩陣。為了下面分析的方便，將AAT表示為（*） 12 AAT = 22 N2同樣，可以形成矩陣BTB = VATUT .UAVT = VATAVT,如果V矩陣的列向量是BTB的列向量，則ATA必定有對角線形式 12 ATA = 22 （*） N2,（*）和（*）能同時滿足的條件是i =i 。此時A是一對角矩陣，其對角線元素是1 ，2 ，n 這時B化為B = 其中ui和vi分別是BBT和BTB的特征向量。而i則由下式確定 i = uiTBvi i = 1，2，,Ni稱為B的奇異值。,上式可

18、以用來計算圖像B（或類似數(shù)據(jù)）的N個特征來表示B。另外，也可以選m(n)個最大的奇異值而放棄其余的奇異值。當矩陣B不是方陣時，仍然可以進行奇異值分解。但奇異值的數(shù)目只能等于B的較小的維數(shù)。,當我們要把兩類或更多的類進行分類時，所抽取的特征應(yīng)該是最有效地保留了類的分離性。類的分離性準則和坐標系無關(guān)，而且和（信號）類的表示準則是完全不同的。,* 7.5 用于分類的特征的提取,類的分離性準則不僅和類的分布有關(guān)，而且和所用的分類器有關(guān)。例如，對線性分類器最好的特征集，對其它類型的分類器就不一定是最好的特征集。為了避免這種額外的復(fù)雜性，我們假定要找的最優(yōu)的特征集是以貝葉斯分類器為基準的。這樣，類的可分性

19、就等價于貝葉斯分類器的錯誤率。因此，從理論上說，貝葉斯錯誤率是特征的有效性的最好度量。,用貝葉斯錯誤率作為準則的一個主要缺點是較難得到它的數(shù)學(xué)表達式（除了少數(shù)特殊情況外）。在第三章我們曾經(jīng)分析過，即使對正態(tài)分布，除了等協(xié)方差的情況外，貝葉斯錯誤率的計算也要用到數(shù)值積分。,下面將給出的幾個準則都有很好的數(shù)學(xué)表達形式，它們是從物理概念中得到的。應(yīng)當提醒的是，當提出一種準則時，這種準則的性能的分析都要和貝葉斯錯誤率聯(lián)系起來。,一、分類特征提取時的一些問題,1模式“表示”和模式“分類”的不同模式分類特征的提取和模式表示特征的提取在許多方面是不同的，特別是所用的準則和所用的變換。,例如，在描述人類時，兩眼、嘴、兩只手、兩條腿但是在區(qū)別東方人和歐洲人時，這些特征毫無用途。因此，用于分類的特征的有效性準則是用類的重疊和分離來度量的，而不是均方誤差的擬合。,B 變換,當特征抽取是用于模式的表示時，所用的變換一般是標準正交變換，因為標準正交變換保留了分布的形狀。而類的重疊和可分性在任何非奇異變換不是不變的，包括線性和非線性的變換。然而，任何奇異的變換都把X映射到較低維的Y，這時將損失一些分類的信息。,因此，用于分類的特征抽取可以看作是在所有的可能的奇異變換中尋找最好的子空間，它盡可