基于標準序列浮動前向特征選擇的改進算法研究

周 陽, 周 炎,周 桃,任 卉,石玲玲

(北京宇航系統工程研究所，北京 100076 )

基于標準序列浮動前向特征選擇的改進算法研究

周 陽, 周 炎,周 桃,任 卉,石玲玲

(北京宇航系統工程研究所，北京 100076 )

信息技術的高速發展促進了信息領域內涵的根本性變革,信息特征的表述方法和內涵不斷擴充，高維特征大幅涌現;這些高維特征中可能存在許多不相關和冗余特征,造成了維度災難,這對基于特征空間聚散特性的分類識別算法提出了更高的要求，需要利用特征選擇算法，降低特征向量維數并消除數據噪音的干擾;針對高維特征向量引入的維度災難等問題，圍繞目標分類識別的具體應用，基于標準的序列浮動前向特征選擇算法，完成交叉驗證重復次數優化，提出了改進的特征選擇算法;通過仿真實驗表明，基于Bayesian分類器開展識別時，改進算法能夠在確保分類識別正確率的前提下，有效提升特征選擇的計算速度，并維持一個相對更為收斂且穩定的置信區間，具備良好的準確度。

特征選擇；浮動前向選擇；Bayesian分類器；目標識別

0 引言

對于典型的模式分類問題來說，決定樣本屬于某一類通常由描述樣本的特征向量決定，即所有的樣本被抽象為一組特征向量，特征向量在特征空間的可分性直接決定了分類器性能的優劣[1]。信息技術的飛速發展引發了信息領域內涵的極大延伸，各類特征提取算法不斷涌現，一方面表征人們對于事物的認識角度得到擴展，另一方面則形成了大量的高維特征數據，這對于分類問題提出了諸多挑戰，如冗余特征信息帶來的計算資源浪費、非預期信息引發的分類器性能降低以及維度災難等，這需要在不降低或有限降低分類器性能的基礎上，提出必要的特征降維方法，確保分類算法的計算效率和實時性指標。

特征選擇是一種典型的特征向量降維方法，其能夠從全維度的特征集合中，基于特定的規則和策略，選取部分特征構成一個低維度的特征子集，用于完成后續的分類問題研究。優秀的特征選擇方法在能夠充分表征該類別既有特征的前提下，能夠有效移除冗余特征和非相關特征，從而降低特征向量維數，改善范磊性能并提高運算效率[2]。

本文主要基于標準序列浮動前向特征選擇算法(sequential floating forward selection，SFFS)，圍繞算法效率和處理速度提出了一種改進算法，并針對Bayesian分類器的目標識別問題，選擇四類船舶目標的紅外圖像，完成了實驗仿真分析，通過仿真結果表明，改進SFFS算法能夠在有效確保識別準確率的同時，有效提升了特征選擇計算速率。

1 特征與特征選擇

1.1 特征

特征是某一類事物區分于其他事物的一次提取或多次提取的信息，或是這些提取信息的集合。在面向具體應用問題中，需要根據實際需求選擇合適的特征提取方法并抽取合適的特征來表述事物本質信息，依靠人工經驗的方法是主觀的，不科學的，也是不可取的[3]。

一般來說，面向圖像目標識別應用的特征提取過程中應滿足的3個基本原則：

1) 特征的穩定性，指特征應具備與噪聲和非相關信息的不敏感特性；

2) 特征的易算性，指特征或特征向量應易于提取和分類計算；

3) 特征的類間可區分性，指圖像中不同類別目標的特征向量距離越大越好，同類目標的特征向量距離越小越好，即具有較小的類內距離和較大的類間距離。

1.2 特征選擇

在圖像目標識別的具體應用問題中，特征提取方法成千上萬，形成的目標特征是一個較高維度的向量，但是高維度的特征空間使得識別問題計算復雜度增高，而部分非相關或非預期特征信息會導致識別率降低。

在目標識別的實際應用中，在完成特征提取后往往會形成較高維度的特征向量，但是過多的特征量會使得計算復雜度增高，同時維數過高的特征向量對于目標識別率會造成負面效果。對于一個具體的分類識別計算模型來說，一般存在一個最大的特征維數，若實際的特征向量維數超過該值時，分類器不僅無法得到分類性能的改善和提高，而且由于高維數據的維度災難和無法預測的特征間耦合關系，將會導致分類器的性能退化現象。因此在具體的目標識別和分類問題中，針對高維度特征向量進行降維是極為必要的，選擇對于識別貢獻率高的特征信息，而去除冗余甚至負影響的特征信息。

特征降維方法主要包括特征選擇、特征變換等方法。其中特征變換是通過相應的映射關系，將高維特征向量變換為一個低維度的特征向量，從而實現特征降維。而特征選擇則是從特征全集中，利用一定的規則和策略，選取部分特征構成一個新的特征空間，并完成后續的分類問題。

特征選擇方法的數學表征可由如下公式表示。

(1)

特征選擇策略大致可分為兩類，即基于搜索及基于評價策略具體如圖1所示[4]。

圖1 特征選擇方法分類圖

基于搜索策略的特征選擇方法主要通過依據給定評價標準，重點強調利用具體的搜索策略從特征全集中選擇出一個合適的特征子集，典型方法包括分支定界算法[5]、遺傳算法[6]、單獨最優特征組合方法[7]及序列選擇方法[8]等。

基于評價策略的特征選擇方法主要關注特征集合的評價策略，如基于濾波式評價策略[9]能夠有效濾除非相關的噪聲信息，但是無法保證較小特征子集的局部最優。

2 標準序列浮動前向特征選擇算法

標準序列浮動前向特征選擇算法(sequential floating forward selection，SFFS)是一種典型的基于搜索策略的特征選擇方法，主要包括兩個步驟。

1)前向操作

即插入步驟，建立一個特征集合(起始時為空集)，每次搜索時基于特定規則從特征全集中選擇一個特征添加到該集合中。

在進行前向操作中，核心就是從候選特征全集中尋找一個特征，使得這個特征加入已選擇特征子集后，已選擇特征集合的分類正確率最大。

2)返向操作

即刪除步驟，從已選特征集合中擇取一個特征，若該特征同時滿足去除該特征后，基于已選特征集合的分類正確率達到最大且大于去除前的條件時，從已選特征集合中刪除該特征。在完成刪除操作時，為避免得到局部最優解，因此需要根據具體情況決定是否執行刪除處理。

標準SFFS算法的具體流程如圖2所示。

圖2 標準SFFS算法流程示意圖

標準SFFS算法的一個優勢就是能夠在一定程度上規避特征集合的局部最優問題，而是選擇出一個最優特征子集，作為分類器的分類輸入。

3 基于改進SFFS的特征選擇方法

3.1 基于分類正確率的評價判據

為驗證改進SFFS算法的特征選擇性能，本節基于Bayesian原理完成分類器設計，其分類正確率作為性能評估依據。

假定共有圖像樣本X個，表示為Pi，其中i=1,2,...,X，共提取Y維目標特征向量，特征全集表示為W={ωy}，y=1,2,...,Y，可把全部圖像樣本按交叉驗證折數S歸為兩類。

1)訓練樣本集：

在所有圖像樣本中選取一定的樣本構建訓練集Ptr，個數為Xtr，其所有目標分類情況均為已知，用于訓練Bayesian分類器。

2)測試樣本集：

將圖像樣本中未歸為訓練樣本的全部圖像用于構建測試樣本集Pte，其樣本個數為Xte，Xte=X-Xtr。測試樣本集中目標分類情況為未知，需要基于選擇的特征子集和Bayesian分類器進行目標識別歸類，其分類正確率用于評估改進SFFS算法的選擇性能。

一般來說，所有訓練樣本中的目標類別判定結果服從等概率分布，則當給定目標類別時，測試訓練集Pte的特征向量是一個分類條件概率密度函數，其服從多元高斯分布，期望向量和協方差矩陣可基于樣本期望向量和離散矩陣完成計算。該分類條件概率密度函數可用一個多元高斯函數進行建模，其中的均值向量和協方差矩陣可分別通過計算樣本均值向量和樣本離散矩陣來得到估計值[10]。

令C是一個非0即1的開關量，表示使用已選擇特征集合對所有樣本進行分類時，當分類正確時將C值置為1，否則為0。已選擇特征集合的分類正確率用CA表示，其初始時為0，具體可由下式表示：

(2)

分類正確率等于各測試樣本中基于特征子集的分類正確率總和，假定總重復次數為Q，第q次重復驗證中，分類正確率的估計可表示為:

(3)

其期望如下式所示:

(4)

3.2 基于標準SFFS的改進算法

標準SFFS算法能夠在一定程度上避免局部最優的問題，但是由于其需要針對每一個特征進行多輪次驗證，算法的計算量較大，在面對一些具體應用時，其算法的實時性無法得到保證。本節主要從標準SFFS算法的前向操作入手，在進行重復驗證時，首先判定該特征的類間區分能力，并依據其類間區分能力決定其重復驗證次數，能夠有效提升計算效率，加快算法收斂時間。

利用Tn表示算法選擇的特征集合，在算法起始時，Tn為一個空集，其中n代表插入和刪除的操作次數，即n=0時，Tn=Φ。假定共有樣本m個，表示為Pi，i=1,2,...,m，訓練樣本經特征提取后形成了特征全集。

改進SFFS算法同樣包含前向和返向兩個步驟。

1)前向操作。

當首次進行前向和返向操作時，即n=0，在特征全集W={ωy} (y=1,2,...,Y)中按標準SFFS算法選取特征ω+，若此時:

ω+=argmaxCA(PT0+ω+)

(5)

則表明ω+為此輪插入操作中的最優特征，則:

T1=T0∪ω+

(6)

當n>0執行前向操作時，首先判定擇取特征與已選特征集合關聯性情況，并依據具體關聯程度設定重復次數，從而減少低貢獻度特征的重復計算次數，提升運行效率。

假定擇取特征為ωy，已選特征集合為Tn，那么擇取特征ωy與已選特征集合Tn間關聯性表示為：

(7)

(8)

W1，W2分別表示特征ω1，ω2在樣本空間的表征向量，Cov表示協方差計算，D表示方差計算。

擇取特征的重復次數需要依據具體的分類應用確定，如設定關聯性程度門限為G，超過該門限時進行足額的重復驗證，未超過時可視情見啥重復次數，也可分級設定多個關聯性程度門限，并在各級內執行不同的重復次數縮減制度，從而在整體上減少對于擇取特征的交叉驗證重復次數。

2)返向操作。

刪除步驟，即滿足特定條件時，從已選特征集合中刪除一個特征。在完成刪除操作時，為避免得到局部最優解，因此需要根據具體情況決定是否執行刪除處理。

在執行第n次插入或刪除操作時，假定有ω-∈Tn，并判定是否對其執行刪除操作。首先計算去除該特征后，選特征集合Tn-ω-的關聯性程度，并設定相應門限，評估交叉驗證重復次數。

設定該特征重復次數后，若該特征同時滿足:

ω-=argmaxCA(PTn-ω-)

(9)

CA(PTn-ω-)>CA(PTn)

(10)

即判定在選擇特征集合中刪除特征ω-，若沒有滿足條件的特征，則返回插入操作步驟。

3)特征輸出。

在完成N次插入和刪除操作后，若再無滿足條件的插入特征和刪除特征，則算法收斂并結束。此時對應的已選擇特征集合為TN，即為最優特征子集，其對應的分類正確率為CA(PTN)。

4 實驗結果及分析

4.1 實驗圖像及特征提取

實驗選取四類船舶目標的紅外目標來進行改進SFFS算法性能驗證，具體如圖3所示。通過對4幅紅外圖像進行平移變換、角度變換、尺度變換，每類目標生成500幅圖像樣本，共計產生2 000副圖像樣本。

圖3 船舶目標仿真實驗圖像

對于每個紅外船舶圖像樣本，分別提取15種特征構成的74維目標特征向量，從而構建出一個特征矩陣數據庫，用來進行特征選擇和分類識別[11-15]。

圖4 實驗圖像目標特征向量

4.2 標準SFFS與改進SFFS的特征選擇方法比較實驗

實驗中，設置折數S=15，最大重復次數Q=100，各特征的重復次數與關聯性分析結果成正比關系。

如表1所示，分別給出了標準SFFS及改進SFFS的特征選擇方法的運行時間，可以發現改進SFFS算法耗時明顯少于標準SFFS算法，這是由于在進行交叉驗證時，首先基于擇取特征的關聯性程度分析優化了交叉驗證重復次數，有效提升了算法收斂時間，實現了算法效率的改進。

表1 運行時間比較表

圖5 MCCR和置信區間比較

圖5則給出了標準SFFS算法及改進SFFS算法的平均分類識別率及其置信區間對于特征選擇步驟數的曲線圖。由圖可見，本文提出的改進SFFS算法在提升計算效率的情況下，相比于標準SFFS算法，其平均分類識別率指標并未下降甚至略有提升，同時圖5(b)中平均分類識別率的置信區間的寬度窄且較為固定，這表明其收斂程度更好，置信度更加穩定。

5 結論

本文主要基于高維特征涌現引入的諸多數據處理困難，基于標準序列浮動前向特征選擇算法，圍繞計算速度和準確度兩個方面，提出了一種改進方法，并通過仿真實驗表明，改進SFFS算法在一定程度上能夠有效提升特征選擇的計算速度，并隨著特征選擇步驟的增加，能夠維持一個相對更為收斂且穩定的置信區間，具備良好的準確度。

[1]王 飛. 模式分類中混合特征選擇方法研究[D].蘭州：蘭州大學，2015.

[2]田曠.面向高位數據的特征選擇算法研究[D].北京 ： 北京交通大學，2012.

[3]榮盤祥，曾凡永，黃金杰.數據挖掘中特征 選擇算法研究[J].哈爾濱理工大學學報，2016,21(1) :106-109

[4]Sun Z, G.Bebis, R.Miller. Object detection using feature subset selection [J]. Pattern recognition, 2004, 37(11): 2165-2176.

[5]Hamamoto Y, Uchimura S, Matsuura Y, et al. Evaluation of the branch and bound algorithm for feature selection[J]. Pattern Recognition Letters, 1990, 11(7): 453-456.

[6]Siedlecki W, Sklansky J. A note on genetic algorithms for large-scale feature selection[J]. Pattern Recognition Letters, 1989, 10(5): 335-347.

[7]邊肇祺, 張學工. 模式識別[M]. 北京: 清華大學出版社, 2000.

[8]Mao K Z. Fast orthogonal forward selection algorithm for feature subset selection[J]. Neural Networks, 2002, 13(5): 1218-1224.

[9]Zhou X, Wang X, R.D.Edward. Nonlinear probit gene classification using mutual information and wavelet-based feature selection[J]. Biological Systems, 2004, 12(3): 371-386.

[10]Tao C, Jin H. Max-margin based Bayesian classifier[J]. Frontiers of Information Technology&Electronic Engineering, 2016, 17(10):973-981.

[11]孫君頂, 趙珊. 圖像低層特征提取與檢索技 術[M]. 北京: 電子工業出版社, 2009.

[12]Freeman H. Shape description via the use of critical points[J]. Pattern recognition, 1978, 10(3): 159-166.

[13]He X C, Yung N. Curvature scale space corner detector with adaptive threshold and dynamic region of support[C]. Hong Kong, China: Proceedings of IEEE International Conference on Pattern Recognition, 2004: 791-794.

[14]Chen C C. Improved moment invariants for shape discrimination[J]. Pattern recognition, 1993, 26(5): 683-686.

[15]Gupta L, Srinath MD. Contour sequence moments for the classification of closed planar shapes[J]. Pattern recognition, 1987, 20(3): 267-272.

Research on Improved Algorithm Based on The Sequential Floating Forward Selection

Zhou Yang，Zhou Yan，Zhou Tao，Ren Hui， Shi Lingling

(Beijing Institute of Astronautical System Engineering,Beijing 100076, China)

With the rapid development of information technology, the indicative method on the information characteristics keep expanding，high-dimensional feature emerge and grow with a massive trend. These high-dimensional feature contain much redundant and irrelevant feature, which will result in the curse of dimensionality. This situation will further lead to higher requirements and more challenges for the classification and recognition algorithm，need the feature selection algorithm to reduce the dimension of eigenvector and data noise.Aim at the dimension disaster introduced by the high dimension eigenvector，and the application oriented ATR algorithm，porpose an improved algorithm based on the sequential floating forward selection，by optimizing the repeat number of cross-test.The results of the simulation experiments shows that on the premise of the high classification accuracy，this improved algorithm can upgrade the calculation speed effectively and could maintain a more astringent and more stable confidence interval what means a better accuracy.

feature selection; SFFS; bayesian classifier; object recognition

2017-04-04；

2017-04-24。

周 陽(1984-)，男，遼寧葫蘆島人，碩士研究生，主要從事信息集成與信息安全方向的研究。

1671-4598(2017)07-0294-04

10.16526/j.cnki.11-4762/tp.2017.07.073

TP751.1

A