2.1.1 特征的提取與選擇

特征選擇與提取的目的是獲取一組“少而精”的分類特征，它是模式識別中的關鍵問題之一，同時也是最困難的問題。

確定合適的特征空間是設計模式識別系統的關鍵問題之一。如果所選用的特征空間能使同類物體分布具有緊致性，將為分類器設計提供良好的基礎；反之，如果不同類別的樣本在特征空間中混雜在一起，再好的分類器設計方法也無法提高分類器的準確性。利用信息獲取裝置產生的模式（已經經過了適當的預處理）往往含有的數據量很大，或者說模式處于一個高維的模式空間中。從模式空間向特征空間的轉換有兩種方法：一種是特征提取，通過某種映射改造原特征空間，構造一個有較好緊致性的精簡的特征空間；另一種是特征選擇，從一組特征中挑選出一些最有效的特征，以達到降低特征空間維數的目的。

本節將在特征評判標準的基礎上，介紹兩種常用的特征選擇和提取的方法：分支界定法和基于K-L變換的特征提取法。

1.特征評判標準——類別可分性判據

特征評判標準主要是衡量類別間的可分性，顯然，能使分類器錯誤概率最小的特征就是最好的特征。從理論上講這是正確的，但在實際應用中存在很大困難。因此，通常需要采用一些更實用的、更具有可操作性的評判標準，這些標準應滿足以下幾點：

·與錯誤概率有單調關系，這樣可以保證使準則取極值時其分類錯誤概率也較小。

·具有度量特性，即滿足：

式中，Jij是用于衡量類ωi和類ωj的準則函數。

·具有單調性，當加入新特征時，判據不減少，即

特征獨立時，滿足可加性，即

在特征提取中常用的特征評價標準有基于分類誤差的可分性判據、基于概率距離度量的可分性判據、基于概率依賴度量的可分性判據、基于熵度量的概率可分性判據和基于距離的可分性判據。

基于距離的可分性判據直接依靠樣本計算，直觀簡潔，物理概念清晰，應用最為廣泛。基于距離的可分性判據的出發點是各類樣本之間的距離越大、類內聚度越小，則類別的可分性越好。直觀上，各類樣本之間的距離越大，則類別可分性越大。因此，可以用各類樣本之間的距離平均值作為可分性準則。用δ(ξik,ξjl)表示第i類中第k個模式和第 j類中第l個模式間距離的度量值，平均距離可定義為：

式中，C表示類別數；如果距離度量δ采用歐幾里得距離，則有：

考慮到式（2-4）的計算比較復雜，可將其轉化為相應的矩陣來度量和處理。

第i類類內散布矩陣：

總體類內散布矩陣：

總體類間散布矩陣：

總體散布矩陣：

存在關系：

上面各式中，為第i類均值向量；，為樣本集的均值向量； 為第i類協方差 為樣本總的協方差。

類內散布矩陣表征各樣本點圍繞它均值的散布情況，類間散布均值表征各類間的距離分布情況，它們依賴于樣本類別屬性和劃分。而總體散布矩陣與樣本劃分及類別屬性無關。

構造準則有跡和行列式兩種方法，兩種方法的示例分別如下。

跡準則：

行列式準則：

表2-1所示為以類內散布矩陣SW、類間散布矩陣SB和總體散布矩陣ST為基礎的一些準則和它們的意義。

2.特征選擇及分支界定法

特征選擇實質上就是從D個特征中選出d（d<D）個最有效的特征。顯然，要得到最有效的特征，必須依據前述的可分性準則，采用一定的算法才能實現。有兩個極端的特征選擇算法，一個是單獨選擇法，另一個是窮舉選擇法。

單獨選擇法就是把D個特征中的每一個特征單獨使用時的可分性準則函數值算出來，然后按準則函數值從大到小排序，取使準則函數較大的前d個特征作為選擇的結果。這種方法看起來很簡單，但是其得到的特征組不能保證是最佳特征組，即使是所有的特征都相互獨立，也無法保證所選出的是最佳特征組。

窮舉法就是將從D個特征取出d個特征的組合對應的可分性準則函數值都計算出來，然后看哪種組合的準則函數值最大，就選中該種組合作為最佳特征。顯然這種方法能夠得到所期望的最佳特征組，但是，當特征數過多時，該方法計算量太大，以致無法實現。

除了以上兩個極端選擇算法外，還有一種非極端算法——分支界定算法，其是一種自上而下的搜索方法，具有回溯功能，不需要顯示評估所有d個特征的可能組合而確定最佳特征組，計算量遠小于窮舉法。但是，該算法的應用需假定特征選擇準則滿足單調性。用 X( j)表示含有 j個特征的候選特征組，單調性指的是對于具有下列嵌套關系的特征組x(j)：

其準則函數J(xj)應滿足

這點由構造特征評判準則的定義可得到保證。

為引出分支界定搜索算法的基本觀點，以從5個特征中挑選2個特征值為例。特征中所有可能組合由圖2-1所示的樹表示，頂稱為根結點，中間稱枝結點，共有D-d+1層。

現假設按自底向上，再由上向下的搜索方式從右結點開始評估樹的每個結點的特征，并進行特征選擇。設初始葉結點的 J 為 J0（為x4 x5的準則函數），在每個結點處，將結點的準則函數值和目前最優特征組的J0值進行比較。如果結點準則函數值大于J0，則還有發現更佳特征組的機會，而且必須繼續沿著最右邊的未勘探分支搜索。如果到達了樹底的結點且相應準則值大于J0，則此結點定義了當前新的最佳特征組，而J0則做相應的更新。

另一方面，如果在某結點的準則函數值小于 J0，則此結點為起始點的分支就不需勘探。因為根據單調性，再往下的特征組合將導致準則函數值的進一步減小。如此按這一規律，由底向上，再自上而下，從右向左搜索全樹，可獲得最佳的二特征組合。此搜索算法特別快捷有效。

3.特征提取及主分量分析

特征提取就是通過某種數學變換，把n個特征壓縮為m個特征，即

式中，x是具有n個特征的向量；變換矩陣A是一個n×m階的矩陣；經變換后的向量y是m維的，m<n。可見，與特征選擇簡單的舍去部分特征相比，特征提取力圖盡可能地保留原來全體特征的信息。

特征提取的關鍵問題是，求取最佳變換矩陣，使得變換后的m維模式空間中，類別可分性準則值最大。

主分量分析是最常用且非常有效的特征提取方法，它是以離散K-L變換為基礎的數據壓縮技術，下面將主要介紹這種方法。

（1）離散K-L變換展開式

K-L變換是一種常用的正交變換。

假設x為n維的隨機變量，x可以用n個基向量的加權和來表示：

式中，αi為加權系數，?i為正交基向量，滿足：

式（2-16）還可以用矩陣的形式表示：

式中

Φ由正交向量構成，所以Φ是正交矩陣，即

考慮到Φ為正交矩陣，由x=Φα得：

即

我們希望向量α的各個向量間互不相關。那么如何保證α的各個分量互不相關呢？這取決于選取什么樣的正交向量集{?j}。

設隨機向量的總體自相關矩陣為

將x=Φα代入上式，得

我們要求向量α的各個分量間互不相關，即滿足下列關系：

寫成矩陣的形式是：

則

將上式兩邊右乘Φ，得

因為Φ是正交矩陣，所以得

即

可以看出，λj是x的自相關矩陣R的本征值，?j是對應的本征向量。因為R是實對稱矩陣，其不同本征值對應的本征向量應正交。

綜上所述，K-L變換展開式的系數可用下列步驟求出：

（a）求隨機向量x的自相關矩陣即

（b）求出自相關矩陣R的本征值λj和對應的本征向量?j（j=1,2,…,n），得到如下矩陣：

（c）展開系數即

（2）主分量分析

從n個本征向量中取出m個組成變換矩陣A，即

這時A是一個n×m的矩陣，x為n維向量，經過ATx變換，得到降維為m的新向量。現在的問題是選取哪m個本征向量構成變換矩陣A，使降維的新向量在最小均方誤差準則下接近原來的向量x。

對于式（2-16），現在取m項，對略去的項用預先選定的常數bj來代替，這時對x的估計值為

由此產生的誤差為

均方誤差為

要使最小，對bj的選擇應滿足：

所以有

這就是說，對于省略掉的那些α中的分量，應該用它們的期望值來代替。

如果在K-L變換前，將模式總體的均值向量作為新坐標系的原點，即在新坐標系中，E[x]=0，根據式（2-39）得

這樣式子（2-37）給出的均方誤差變為

式中，λj是x的自相關矩陣R的第j個本征值；?j是與λj對應的本征向量。顯然，所選的λj值越小，均方誤差也越小。

綜上所述，基于K-L變換的特征提取的步驟如下：

（a）平移坐標系，將模式總體的均值向量作為新坐標的原點；

（b）求出自相關矩陣R；

（c）求出R的本征值λ1,λ2,…,λn及其對應的本征向量?1,?2,…,?n；

（d）將本征值按從大到小排序，如

取前m個大的本征值所對應的本征向量構成變換矩陣，即

（e）將n維的原向量變換成m維的新向量，即

K-L變換是在均方誤差最小的情況下獲得數據降維的最佳變換。如果采用大本征值對應的本征向量構成變換矩陣，則能對應地保留原樣本中方差最大的數據，所以K-L變換達到了減小相關性、突出差異性的效果，因此K-L變換又稱主分量分析。