《模式識別導論》課件第7章

第7章特征提取與選擇7.1特征提取與選擇的基本概念7.2基于距離的特征提取7.3基于離散K-L變換的特征提取7.4特征選擇方法前面幾章討論傳統模式識別方法時，一直假定給定的數據集的特征都是對識別問題非常重要的。然而在很多實際問題中，數據的某些特征可能和識別任務是不相關的或者特征之間存在冗余。特征提取與選擇的主要任務是研究如何從眾多的特征中求出那些對分類識別任務最有效的特征。

為使特征能夠代表對象，且便于實際操作和算法實現，并使分類結果真實可靠，要求所選用的特征應滿足以下五個條件：

(1)真實性，特征應能準確地包含分類對象的物理信息。(2)有效性，所選用的特征和特征組合對分類是有效的，盡量使得對象易于分類識別。

(3)簡約性，信息充分且數據冗余量少。

(4)魯棒性，當所選用的特征受到測量誤差較大影響時，盡量使得算法的有效性不被破壞。

(5)提取特征方便經濟，便于實際操作。

本章不涉及具體的應用背景，因此不對(1)、(4)和(5)進行討論，主要針對(2)和(3)的一些重要理論和技術進行詳細介紹。

本章主要討論特征提取與選擇的基本概念、基于距離的特征提取、基于離散K-L變換的特征提取以及特征選擇方法。

7.1特征提取與選擇的基本概念

7.1.1特征的種類

特征是描述待分析對象性質的一種量，是對對象的一種抽象。從形式上看，特征可以分為以下三類：

1.物理特征

物理特征是根據對象的外在表現抽取的特征。例如為了描述某個人，通常采用性別、身高、胖瘦、膚色等特征，這些特征都屬于物理特征。物理特征是比較直接、容易感知的特征，一般在設計模式識別系統時被選用。

2.結構特征

結構特征是能表征觀察對象結構信息的特征。例如人的指紋具有小橋、環、分叉點、三角點和端點等特征，這些特征都屬于結構特征。結構特征的獲取是先將觀察對象分割成若干基本構成要素，然后確定基本要素間的相互連接關系，通過各個要素和相互的連接關系表達對象。結構特征比物理特征要抽象一些，但仍屬比較容易感知的特征，其表達能力一般要高于物理特征。結構特征在實際模式識別問題中已經有較多的成功應用，例如指紋識別和人臉識別等。

3.數學特征

數學特征是為了表征觀察對象而人為設定的特征。例如每個學生的學號就是一種數學特征。數學特征有時和觀察對象的固有屬性沒有關系，有時則是觀察對象的物理或結構特征的計算結果。需要指出，數學特征是人為設定的，可以保證唯一性，但這種特征是抽象的，不容易被人感知。由于物理和結構特征很容易被視覺、觸覺以及其他感覺器官所發現，因此人們通常利用這些特征來識別對象，但是這些特征對于計算機而言有時比較復雜。計算機在抽取和處理數學特征的能力方面要比人強得多。在本章中，計算機使用的數學特征包括統計平均值、相關矩陣和協方差矩陣的特征值及特征向量等。7.1.2特征提取與選擇

特征提取是指通過映射或變換獲取有效特征的過程。提取后的特征稱為二次特征，它們是原始特征的某種組合，最常見的是線性組合。需要強調的是，特征提取一定要進行數學變換。特征選擇是指從一組特征中挑選出對分類最有效的特征，實現特征選擇的前提是確定特征是否有效的標準，在這種標準下方可尋找最有效的特征子集。用于特征選擇的特征既可以是原始特征，也可以是經特征提取后得到的二次特征。在實現特征提取和選擇的目標之前，需要首先制定特征提取和選擇的標準，這些標準應該能夠反映各類在特征空間的分布情況或刻畫出特征對分類識別的重要性。在具體實施特征提取和選擇時可以遵循如下兩個基本的途徑：

(1)已知可分性判據J，在使得該判據取得最大值的目標下，對原始特征進行變換降維，即對原始特征空間進行坐標變換，再取子空間。該類變換方法主要有基于距離可分性測度的特征提取方法和基于離散K-L變換的特征提取方法等。

(2)直接尋找原始特征空間中的低維子空間，即直接選擇法。在選擇的過程中，尋找能夠使得可分性判據最大化的那組低維特征空間組合。直接特征選擇方法包括最優搜索法和次優搜索法等。特征提取和特征選擇都是在不降低或較少降低分類性能的情況下，降低特征空間的維數。其主要作用在于：

(1)簡化計算。特征空間的維數越高，需要占用的計算機資源越多，計算的復雜度也就越高。

(2)簡化特征空間結構。特征提取和選擇是去除類間差別小的特征，保留類間差別大的特征，使得每類所占據的子空間結構可分離性更強，從而也可以簡化類間分界面形狀的復雜度。

需要指出，特征提取和選擇并不是截然分開的。例如，可以先將原始特征空間映射到維數較低的空間，然后在這個空間中進行特征選擇來進一步降低維數。

7.2基于距離的特征提取

特征提取與選擇的目的是獲得一組對于分類識別最有效的特征，從而實現特征空間維數的約簡。然而，把一個高維特征變為低維特征的方法是很多的，需要一個標準來衡量哪種方法最有效，這種標準即為類別可分性測度。一般希望所構造的可分性判據應滿足下列幾個要求：

(1)與錯誤率(或錯誤率的上界及下界)有單調關系，即使得可分性測度取最大(或最小)值時，錯誤率也最小。

(2)當特征相互獨立時，可分性測度具有可加性,即

這里，x1，x2，…，xd是對象不同種類特征的測量值;Jij(·)是第i類和第j類之間的可分性測度函數，Jij越大，表示兩類的分離程度就越大。

(3)度量特性，主要包括非負性和對稱性：

Jij>0，當i≠j時

Jij=0，當i=j時(7-2)

Jij=Jji

(7-1)

(4)單調性，即加入新的特征后，該可分性測度的值不會減小：

Jij(x1，x2，…，xd)≤Jij(x1，x2，…，xd，xd+1)

(7-3)

很多人在這方面做了不少工作，提出了各種可分性測度，本節主要介紹基于距離的類別可分性測度，以及基于這些可分性測度的特征提取方法。7.2.1基于距離的類別可分性測度

一般地講，各類中的樣本可以被分開是因為它們位于特征空間中的不同區域，我們總是希望不同類的樣本之間的距離大一些，而同類的樣本較集中。不同類區域之間距離越大或者重疊的部分越小，類別可分性就越好，因此，利用距離準則來構造類別可分性判據是可行的。我們在第6章的6.2節給出了多類情況下總的類內離散度矩陣SW、類間離散度矩陣SB和總的離散度矩陣ST的定義，并給出了利用它們構造的聚類準則函數J1~J6。實際上，這些聚類準則函數可以作為類別可分性判據來進行特征提取，這里，把它們稱之為基于距離的類別可分性測度。除了第6章給出的J1~J6這六個類別可分性測度，下面給出另外三個類別可分性測度；(7-4)(7-5)(7-6)為了使所使用的特征能夠有效地進行分類，我們希望類間離散度盡量大，同時類內離散度盡量小。所以，J4、J5和J6這三個測度越小越好，剩余六個測度則是越大越好。這些類別可分性測度之間存在關聯，有的可分性測度之間幾乎等

價，但性能上略有不同。7.2.2基于距離可分性測度的特征提取

設原始樣本為x=(x1，x2，…，xq)T，其中，q為特征的維數。對x作線性變換，產生d維特征向量y=(y1，y2，…，yd)T，d≤q，即

y=WTx

(7-7)

其中，q×d矩陣W為特征提取矩陣或者變換矩陣。本小

節我們討論在基于距離的類別可分性測度準則下，如何求得最優變換矩陣W。采用基于距離的類別可分性測度J1~J9進行特征提取時，需要求矩陣的跡最大(最小)或者行列式值最大(最小)。下面我們先以J1測度為例說明如何求矩陣跡最大化，再以J9測度為例說明如何求行列式值最大，其他類別可分性測度可類似處理。J1的定義如下；

其中，SW和SB分別為原始樣本的類內和類間離散度矩陣。在新的變換特征空間中，新樣本的類內和類間離散度矩陣S*W和S*B可定義為；(7-8)(7-9)

在新的變換特征空間中

若W為非奇異矩陣，可以等價為，這表明在非奇異變換條件下，原特征空間的類可分判據與新空間的判據是相同的。設WT是標準正交矩陣，利用該矩陣對進行對角化，得到(7-10)(7-11)(7-12)其中，λi(i=1，2，…，q)為的特征值，WT的列向量wi是對應于特征值λi的特征向量。由于一個方陣的跡等于它的所有特征值之和，因此可得

當新特征空間的維數d確定之后，取出的d個較大特征值對應的特征向量wi構造特征提取矩陣W，即

W=(w1，w2，…，wd)

(7-14)

此時采用W對x作變換，可分性測度J1達到了最大值,即(7-13)(7-15)其中，λ1≥λ2≥…≥λd≥…≥λq。

下面以J9為例，介紹如何運用以行列式形式出現的可分性測度求最優變換矩陣W。

易知SW是對稱正定矩陣，存在非奇異矩陣A，使得

ATSWA=I

(7-16)

其中，I為單位矩陣。有標準正交矩陣V，可使V-1ATSTAV

=，為對角陣，而

令U=AV，則存在非奇異矩陣U，使得(7-17)且

UTSWU=I

(7-18)

對上式兩邊同時取逆，有

對上式兩邊左乘(7-16)式兩邊，得

再對上式左乘U，則有

從上式可知，U和分別為的特征向量構成的矩陣及特征值構成的對角陣。由于(7-19)(7-20)(7-21)

所以

即

如果設的特征值矩陣Λ=diag(λ1，λ2，…，λq)，則

那么(7-22)(7-23)(7-24)(7-25)(7-26)對于給定的d，取的前d個較大特征值對應的特征向量構成變換矩陣W，可使可分性測度J9達到最大值,即

其中，λ1≥λ2≥…≥λd≥…≥λq。(7-27)例7.1給定具有兩個模式類的樣本集X={x1，x2，…，x7}，其中，ω1：x1=(1，1)T，x2=(1，2)T，x3=(3，1)T，x4=(3，3)T；ω2：x5=(－2，－2)T，x6=(－2，－3)T，

x7=(－3，－2)T。利用類別可分性測度J9將樣本特征維數變為一維。

解(1)計算矩陣。首先分別計算各類樣本均值向量mi(i=1，2)和樣本總體均值向量m。

然后計算每一類的類內離散度矩陣，i=1，2,即接著計算總的類內離散度矩陣SW；然后計算總的離散度矩陣ST；

最后計算

(2)計算D的特征值和特征向量。根據|D-λI|=0，可得

λ1=14.09，λ2=1.00

根據，可得λ1和λ2對應的特征向量分別為；

w1=(0.60，0.80)T

w2=(-0.69，0.73)T

(3)選擇w1構成變換矩陣W，即

W=w1

(4)利用W對樣本集X中的每一個樣本進行特征提取，即

yi=WTxi

最終結果為

y1=1.40，y2=2.20，y3=2.60，y4=4.20

y5=－2.80，y6=－3.60，y7=－3.40

特征提取結果如圖7.1所示。圖7.1基于類別可分性測度J9的特征提取結果

7.3基于離散K-L變換的特征提取

離散K-L變換又稱為霍特林變換或主成分分析，是一種基于目標統計特性的正交變換。該變換具有如下重要性質：(1)變換后產生的新分量是正交或者不相關的；(2)變換后各分量的非零平方期望或方差更趨于不均；(3)采用部分新分量表示原向量時均方誤差最小，即具有最佳逼近性；(4)變換后向量能量更加集中，即變換使能量向某些分量相對集中；(5)變換后向量在總體上更趨確定性。鑒于離散K-L變換具有上述諸多性質，它已經在特征提取方面得到了極為重要的應用。7.3.1離散K-L變換(DKLT)

設q維隨機向量x=(x1，x2，…，xq)T，其均值向量為，相關矩陣為Rx=E［xxT］，協方差矩陣為

。x經過標準正交矩陣WT正交變換后變成向量y=(y1，y2，…，yq)T，即(7-28)明顯可以看出，y的各個分量為

而且由于WT為正交矩陣，因此，i=1，2，…，q

(7-29)(7-30)選擇x關于yi的展開式的l項在最小均方誤差準則下來線性估計x，此時，x的估計式為，1≤l≤q

(7-31)該估計式與x的均方誤差為

為了使得均方誤差ε2(l)在W為標準正交矩陣的約束下(即

)取得最小值，可以采用下式作為準則函數：

由可得(7-32)(7-33)

即

Rxwi=λiwi，i=l+1，…，q

(7-35)

式中，λi為x的相關矩陣Rx的特征值；wi為Rx的對應于λi的特征向量。將上式代入均方誤差ε2(l)表達式(7-32)中，可得

如果在x的估計式中保留l個yi，而余下的q-l個分量yi(i=l+1，…，q)分別由預選的q-l個常數bi代替，此時的估計式可以表示為i=l+1，…，q

(7-34)(7-36)

估計的均方誤差為

最佳的bi可以通過ε2/bi=0求得，即

可得(7-37)(7-38)(7-39)(7-40)于是

在W為標準正交矩陣的約束下，求使得ε2(l)→min的wi的方法和前面類似，構造準則函數為

由可得

Cxwi=λiwi，i=l+1，…，q

(7-43)(7-41)(7-42)從上式可以看出，λi和wi分別為x的協方差矩陣Cx的特征值和相應的特征向量。將上式代入均方誤差ε2(l)表達式(7-41)中，可得

當采用式(7-31)估計x時，使均方誤差最小的正交變換矩陣是隨機向量x的相關矩陣Rx的特征向量矩陣的轉置；而當采用式(7-37)估計x時，使均方誤差最小的正交變換矩陣是x的協方差矩陣Cx的特征向量矩陣的轉置。無論上述哪種情況，為使ε2(l)最小化，都是采用前l個較大特征值對應的特征向量構造l×q的變換矩陣?？偨Y上面的內容，我們給出下面的定理。(7-44)定理7.1在一切標準正交變換z=VTx=(v1v2…vq)Tx中，用隨機向量x的協方差矩陣Cx的特征向量矩陣(w1w2…wq)對其進行變換所得的向量y可使

式中，(w1

w2…wq)的各列對應的特征值滿足λ1≥λ2≥…≥λq，。

這種采用x的相關矩陣Rx或者協方差矩陣Cx的特征向量矩陣作為變換矩陣的變換稱為離散K-L變換，此時，式(7-30)稱為x的K-L展開。

(7-45)7.3.2離散K-L變換在特征提取中的應用

設X={x1，x2，…，xn}表示一個具有c個模式類的樣本集合，其中，每個樣本xi是一個q維向量。下面介紹如何采用離散K-L變換對樣本集進行特征提取，將樣本的特征維數從q維降到d維。

(1)求c類樣本集X的總體自相關矩陣R。

(2)求R的特征值λi和對應的特征向量wi，i=1，2，…，q，并將特征值按照從大到小的順序進行排列。(7-46)

(3)將R的前d個較大特征值對應的特征向量wi構成變換矩陣W，即

W=［w1，w2，…，wd]

(7-47)

(4)對樣本集X={x1，x2，…，xn}中的每一個樣本xi進行K-L變換，得到相應的d維向量yi，即

yi=WTxi

(7-48)上面我們介紹了利用樣本集的自相關矩陣R進行特征提取，同理可以先獲得樣本集的協方差矩陣C，形式如下：

然后利用C進行特征提取，該過程與上述過程類似，這里就不再贅述。(7-49)例7.2利用K-L變換將例7.1中樣本集的特征維數由兩維降為一維。

解(1)計算X的總體自相關矩陣R。

(2)計算R的特征值和特征向量。根據|]R-λI|=0，可得

λ1=9.37，λ2=0.49

根據Rwi=λiwi，可得λ1和λ2對應的特征向量分別為；

w1=［0.74，0.68］T

w2=［-0.68，0.74］T

(3)選擇w1構成變換矩陣W，即

W=w1

(4)利用W對樣本集X中的每一個樣本進行K-L變換，即

yi=WTxi

變換結果為

y1=1.42，y2=2.10，y3=2.90，y4=4.26

y5=－2.84，y6=－3.52，y7=－3.58

7.4特征選擇方法

7.2和7.3節介紹了對原始特征空間進行變換來獲得有效特征的方法。我們也可以采用特征選擇的方法，依據某種準則或者策略從原始特征中挑選出一些最有代表性的，分類性能最好的特征出來。因此，特征選擇方法需要解決以下兩個問題：(1)如何評價特征組合的有效性；(2)尋找有效特征組合的方法和策略。一般情況下，原始特征空間的維數是已知的，為保證選擇出的特征具有一定的分類性能，可以通過7.2節介紹的各種可分性判據對特征組合的有效性進行度量。此外，由于選擇后的特征維數d一般是未知的，假設原始特征空間維數為q，則d的選擇范圍是1~q之間的任何一個自然數，因此，所有可能的特征組合數目為。顯而易見，這是一個典型的組合優化問題，如果q值很大，選擇的特征數目也很多，則特征選擇的復雜度是非常高的。為此，人們提出了一系列特征選擇的策略。本節介紹兩種特征選擇方法：最優搜索法和次優搜索法。7.4.1最優搜索法

分支定界法是一種經典的最優搜索方法。在該算法中，尋找全局最優特征組合的搜索過程可以用一個樹形結構來描述，稱其為搜索樹。搜索方案是沿著搜索樹從上而下、從右向左進行，由于該樹的每個節點代表一種特征組合，因此所有的特征組合都被考慮到了。分支定界法的關鍵是利用了特征選擇可分性判據J的單調性，即對于兩個特征子集X和Y,有

因此某些特征組合并不需要計算且又不影響全局最優特征組合的搜索。此外，該算法先從結構簡單的部分開始搜索，所以效率很高。(7-50)下面采用一個從5個特征中選擇2個特征的例子來說明分支定界法的原理。設原空間中的5個特征為{x1，x2，x3，x4，x5}，整個搜索過程的樹形結構如圖7.2所示。在該圖中，根節點代表全部特征，節點上的數字表示所選特征的編號，因此其上的數字為(1，2，3，4，5)。每個節點表示一個特征組合，子節點所代表的特征比其父節點代表的特征少一個，同父的各子節點分別代表從父節點的特征組合中舍棄不同的一個特征后余下的特征。由于每個節點只刪除一個特征，如果是從q個特征中選擇d個，那么根節點到葉節點的層數由q-d決定，因此本例中為3層(根節點在第0層)。為使各個特征子集不重復，從父節點到子節點的特征刪除過程中，要按照特征編號的順序依次刪除一個不同的特征。例如在第1層中，從左往右各個子節點刪除的特征分別為1、2和3。只有三個子節點的原因是由于對某個子節點來講，其左邊同父節點已丟棄的特征以后不能在要丟棄的特征組合里，這樣可以防止得到重復的特征組合。另外，從圖中可以看出，每個分支最右邊的節點總是只有一個子節點。圖7.2分支定界法搜索樹示例分支定界法的基本原理是先找到一個d維組合，期望該特征組合的判據值盡可能的大，并以此為界，然后將后續搜索到的節點的判據值與該界值進行比較。如果某節點的特征組合的判據值小于界值，則由判據的單調性，該節點的所有子節點不可能是最優特征組合，也就不需要再進行搜索。在已獲得樹結構的條件下，特征組合搜索過程總體上是從分支數量不密集的部分到分支數最密集的部分，也就是從上到下、從右到左進行。在這個過程中包含幾個可能的子過程：向下搜索、更新界值、向上回溯、停止回溯再向下搜索。在搜索之前先將界值B初始化為0，然后從樹的根節點沿最右邊的一支自上而下搜索。在搜索樹中，一個節點的子樹最右邊一支總是無分支的，因此從根節點開始可以直接到達葉節點，得到特征集(1，2)。假設該葉節點的特征組合的可分性判據值為J(1，2)=75，此時更新界值B=75，然后向上回溯。一旦遇到有分支的節點就停止回溯，轉而向下搜索。因此，從特征集為(1，2)的節點向上回溯遇到根節點停止，轉而向特征集為(1，3，4，5)的節點分支進行搜索。由于J(1，3，4，5=82>J(1，2)，繼續往右邊分支進行搜索，從圖7.3中可知，一直可以搜索到葉子節點并計算特征組合(1，3)的判據值J(1，3)=79

>B，因此更新界值B=79，然后再向上回溯。依此類推，可以搜索到特征組合(1，5)的判據值J(1，5)=81>B，因此更新界值B=81。從特征集為(1，5)的節點向上回溯遇到根節點停止，轉而向特征集為(2，3，4，5)的節點分支進行搜索。由于J(2，3，4，5)=78<B，根據單調性，該特征集合的所有子集的可分性判據都低于其自身的可分性判據。此時分支定界法停止搜索，得到最優特征組合(1，5)。圖7.3分支定界法搜索回溯示意圖分支定界法的高效性在于：(1)利用了可分性判據的單調性，從而避免了有相當多的特征組合的判據計算。如果樹上某個節點a的可分性判據值滿足Ja≤B，可知a的子樹上各節點的可分性判據值都不會大于B，因此節點A的子樹節點都不用去搜索，這就是所謂的分支定界；(2)分支定界法的搜索過程是從右至左進行的，由于樹的右邊分支要比左邊分支結構簡單，因此分支定界法具有高效的性能。7.4.2次優搜索法

1.單獨最優的特征選擇法

單獨最優特征選擇法是最簡單的一種特征選擇算法。該算法首先計算每個特征單獨使用時的可分性判據值，然后根據得到的判據值對各個特征進行排序，最后選擇前d個分類效果最好的特征作為最終的特征組合。

一般情況下，即使各個特征之間是統計獨立的，單獨最優特征選擇算法選出的d個特征也不一定是最優的特征組合。只有當可分性判據J寫為如下形式時：或(7-51)這種算法才能獲得最優的特征組合。例如在正態分布情況下，當各個特征是相互獨立時，用馬氏距離作為判據選出的d個特征就是最優的特征組合。

2.順序前進法

順序前進法(SequentialForwardSelection，SFS)也稱為增添特征法，是一種最簡單的自下而上的搜索算法。該算法的基本思路是,每次從未選入的特征中選擇一個特征，使它與已選入的特征組合在一起的可分性判據最大，直到特征數目達到指定的數目d為止。假設已經選擇了k個特征，記為Xk，把未選擇的q-k個特征xj(j=1，2，…，q-k)逐個與Xk組合后計算可分性判據值J，若

則選擇x*與Xk構成新的特征組合，該過程一直進行到選入的特征數目達到指定維數d為止。

順序前進法考慮了所選特征與已選入