基于標(biāo)準(zhǔn)序列浮動前向特征選擇的改進算法研究

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

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

基于標(biāo)準(zhǔn)序列浮動前向特征選擇的改進算法研究

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

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

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

特征選擇；浮動前向選擇；Bayesian分類器；目標(biāo)識別

0 引言

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

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

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

1 特征與特征選擇

1.1 特征

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

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

1) 特征的穩(wěn)定性，指特征應(yīng)具備與噪聲和非相關(guān)信息的不敏感特性；

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

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

1.2 特征選擇

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

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

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

特征選擇方法的數(shù)學(xué)表征可由如下公式表示。

(1)

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

圖1 特征選擇方法分類圖

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

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

2 標(biāo)準(zhǔn)序列浮動前向特征選擇算法

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

1)前向操作

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

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

2)返向操作

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

標(biāo)準(zhǔn)SFFS算法的具體流程如圖2所示。

圖2 標(biāo)準(zhǔn)SFFS算法流程示意圖

標(biāo)準(zhǔn)SFFS算法的一個優(yōu)勢就是能夠在一定程度上規(guī)避特征集合的局部最優(yōu)問題，而是選擇出一個最優(yōu)特征子集，作為分類器的分類輸入。

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

3.1 基于分類正確率的評價判據(jù)

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

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

1)訓(xùn)練樣本集：

在所有圖像樣本中選取一定的樣本構(gòu)建訓(xùn)練集Ptr，個數(shù)為Xtr，其所有目標(biāo)分類情況均為已知，用于訓(xùn)練Bayesian分類器。

2)測試樣本集：

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

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

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

(2)

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

(3)

其期望如下式所示:

(4)

3.2 基于標(biāo)準(zhǔn)SFFS的改進算法

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

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

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

1)前向操作。

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

ω+=argmaxCA(PT0+ω+)

(5)

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

T1=T0∪ω+

(6)

當(dāng)n>0執(zhí)行前向操作時，首先判定擇取特征與已選特征集合關(guān)聯(lián)性情況，并依據(jù)具體關(guān)聯(lián)程度設(shè)定重復(fù)次數(shù)，從而減少低貢獻度特征的重復(fù)計算次數(shù)，提升運行效率。

假定擇取特征為ωy，已選特征集合為Tn，那么擇取特征ωy與已選特征集合Tn間關(guān)聯(lián)性表示為：

(7)

(8)

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

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

2)返向操作。

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

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

設(shè)定該特征重復(fù)次數(shù)后，若該特征同時滿足:

ω-=argmaxCA(PTn-ω-)

(9)

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

(10)

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

3)特征輸出。

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

4 實驗結(jié)果及分析

4.1 實驗圖像及特征提取

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

圖3 船舶目標(biāo)仿真實驗圖像

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

圖4 實驗圖像目標(biāo)特征向量

4.2 標(biāo)準(zhǔn)SFFS與改進SFFS的特征選擇方法比較實驗

實驗中，設(shè)置折數(shù)S=15，最大重復(fù)次數(shù)Q=100，各特征的重復(fù)次數(shù)與關(guān)聯(lián)性分析結(jié)果成正比關(guān)系。

如表1所示，分別給出了標(biāo)準(zhǔn)SFFS及改進SFFS的特征選擇方法的運行時間，可以發(fā)現(xiàn)改進SFFS算法耗時明顯少于標(biāo)準(zhǔn)SFFS算法，這是由于在進行交叉驗證時，首先基于擇取特征的關(guān)聯(lián)性程度分析優(yōu)化了交叉驗證重復(fù)次數(shù)，有效提升了算法收斂時間，實現(xiàn)了算法效率的改進。

表1 運行時間比較表

圖5 MCCR和置信區(qū)間比較

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

5 結(jié)論

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

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

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

[3]榮盤祥，曾凡永，黃金杰.數(shù)據(jù)挖掘中特征 選擇算法研究[J].哈爾濱理工大學(xué)學(xué)報，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]邊肇祺, 張學(xué)工. 模式識別[M]. 北京: 清華大學(xué)出版社, 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]孫君頂, 趙珊. 圖像低層特征提取與檢索技 術(shù)[M]. 北京: 電子工業(yè)出版社, 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