王冬海，戴 磊

(中國(guó)電子科學(xué)研究院，北京 100041)

0 引 言

從提高信息質(zhì)量，降低軍事信息系統(tǒng)計(jì)算存儲(chǔ)開銷，提升軍事信息系統(tǒng)效能的角度出發(fā)，提出了一種面向高維數(shù)據(jù)的特征選擇方法。該方法對(duì)現(xiàn)有特征選擇一般過程進(jìn)行改良，更宜于處理高維特征數(shù)據(jù)。

在有關(guān)信息質(zhì)量研究方面，Cropley［1］研究C4ISR系統(tǒng)中信息的特點(diǎn)，總結(jié)了一種定性的信息模型，嘗試解決信息度量問題。Clayton 等人［2］從用戶角度考慮的信息質(zhì)量，把信息質(zhì)量分為三個(gè)指標(biāo):信息豐富性、適應(yīng)性和可獲取性。在文獻(xiàn)［3］中，則討論信息質(zhì)量的三個(gè)屬性:客觀性、完整性和效用性，給出了有關(guān)定義。在軍事信息系統(tǒng)作戰(zhàn)效能方面，美國(guó)麻省理工大學(xué)信息決策實(shí)驗(yàn)室自20 世紀(jì)80 年代初就開始了C3I 系統(tǒng)效能分析和評(píng)估的研究。隨后，美國(guó)軍事運(yùn)籌學(xué)會(huì)推薦了一個(gè)C3I 系統(tǒng)性能表征與軍事效能相聯(lián)系的一個(gè)度量層次結(jié)構(gòu)［4～6］。Poirier等人［7］則提出了C4ISR 系統(tǒng)能力層次結(jié)構(gòu)，該結(jié)構(gòu)將提供遠(yuǎn)程的、多層次的信息感知和武器信息能力定義為系統(tǒng)頂層能力之一。在上述軍事信息系統(tǒng)效能體系中，信息傳輸、處理能力都是系統(tǒng)效能評(píng)估中的重要指標(biāo)。

為有效處理現(xiàn)代戰(zhàn)場(chǎng)產(chǎn)生的海量實(shí)時(shí)數(shù)據(jù)，提升信息質(zhì)量及軍事信息系統(tǒng)效能，在對(duì)現(xiàn)有特征選擇理論技術(shù)進(jìn)行深入分析的基礎(chǔ)上，提出了一種面向高維數(shù)據(jù)的特征選擇方法。

1 特征選擇理論

1.1 數(shù)學(xué)模型

給定一個(gè)特征子集F ={f1，f2，…，fN}，N 是特征集的大小。一個(gè)特征子集可以用一個(gè)二進(jìn)制向量表示:S=(s1，s2，…，sN)，si∈{0，1}，i =1，2，…，N，si=1 表示第i 個(gè)特征fi被選擇，反之對(duì)第i 個(gè)特征fi不作選擇。把評(píng)價(jià)函數(shù)在給定的特征子集S 上所具有的最大性能G(S)作為目標(biāo)函數(shù)值，則特征選擇問題轉(zhuǎn)化為下列尋優(yōu)問題:

1.2 一般過程

特征選擇一般經(jīng)過的四個(gè)階段是特征子集產(chǎn)生、特征子集評(píng)估、評(píng)估停止條件和結(jié)果驗(yàn)證。四個(gè)階段的流程圖，如圖1 所示。特征選擇的核心階段是特征子集產(chǎn)生與特征子集評(píng)估，即搜索策略和評(píng)估標(biāo)準(zhǔn)。

圖1 特征選擇的四個(gè)階段

在圖1 的每一次循環(huán)過程中，一個(gè)候選的特征子集被生成與評(píng)估。特征子集的產(chǎn)生方式?jīng)Q定于搜索策略。搜索策略主要包括三種:窮舉搜索［8］，啟發(fā)式搜索［9］，隨機(jī)搜索［10］。窮舉搜索是搜索所有可能的特征子集，這種搜索策略一定可以發(fā)現(xiàn)最優(yōu)的特征子集，但搜索空間大，是NP 問題;啟發(fā)式搜索按照一定的啟發(fā)式規(guī)則搜索特征子集，這種搜索策略的搜索空間比較小，可能丟失最優(yōu)子集，比較典型的有前向搜索，關(guān)聯(lián)搜索［11］。隨機(jī)搜索實(shí)際上是一種對(duì)上述兩種搜索的平衡方法，比較典型的隨機(jī)搜索有遺傳算法［12］和爬山算法［13］。在基于特征選擇的入侵檢測(cè)模型研究領(lǐng)域，用的較多的搜索策略是遺傳算法。

2 面向高維數(shù)據(jù)的特征選擇

2.1 缺陷分析

常用的特征選擇技術(shù)都基于上述一般過程選取優(yōu)化特征子集，可以看出，在特征選擇的一般過程中，特征子集的生成與評(píng)估循環(huán)是計(jì)算開銷的主要部分，即生成的特征子集的數(shù)量決定了特征選擇算法的計(jì)算量?；谏鲜鎏卣鬟x擇一般過程選取優(yōu)化特征子集時(shí)，如果要保證選取的特征子集足夠優(yōu)良，一個(gè)重要的條件就是在生成的特征子集數(shù)量相對(duì)于特征子集的總數(shù)量而言能夠滿足一定的覆蓋率，因此原始特征集中的特征數(shù)量與特征選擇過程中需要生成的特征子集的數(shù)量有著密切關(guān)系。可以看出，對(duì)于高維特征而言，這種特征選擇過程的計(jì)算量過于龐大，難于實(shí)現(xiàn)。

2.2 改進(jìn)策略

在特征選擇的一般過程中，為了維持一定的覆蓋率，生成與評(píng)估特征子集的數(shù)量應(yīng)當(dāng)相對(duì)特征的總數(shù)量呈指數(shù)級(jí)增長(zhǎng)，如果特征的總數(shù)量高達(dá)到一定程度，特征選擇的計(jì)算量將過于龐大，導(dǎo)致算法難以生成足夠數(shù)量的特征子集維持覆蓋率，最后選取的優(yōu)化特征子集的質(zhì)量也無法保證。因此，如何以相對(duì)較少的特征子集生成與評(píng)估次數(shù)，產(chǎn)生高質(zhì)量的分類特征子集，是特征選擇技術(shù)在處理高維特征需要研究的重要問題。

所提出的改進(jìn)策略是首先對(duì)每個(gè)特征包含的分類信息進(jìn)行測(cè)算，然后根據(jù)測(cè)算結(jié)果對(duì)特征進(jìn)行重新排序，再結(jié)合相應(yīng)的啟發(fā)式搜索策略，優(yōu)先將含分類信息較多的特征選入特征子集，這樣就可以在減少生成特征子集數(shù)量的同時(shí)，保證重要的分類特征在特征選擇過程中不會(huì)被遺漏。

2.3 高維數(shù)據(jù)特征選擇算法設(shè)計(jì)

對(duì)于高維的特征空間，常用的特征選擇算法無法保證選擇特征子集的覆蓋率，為了降低搜索的盲目性，結(jié)合上述特征選擇過程改進(jìn)策略，提出了一種變異的混合型特征選擇算法，該算法基于信息增益與Bayes 分類算法。信息增益源于Shannon 提出的信息論，具有堅(jiān)實(shí)的理論基礎(chǔ)，而Bayes 算法則具有執(zhí)行速度快的優(yōu)點(diǎn)，根據(jù)［14］中對(duì)5 種常用算法的對(duì)比實(shí)驗(yàn)，各分類算法取得的準(zhǔn)確率接近，而Bayes 算法能夠提供最快的建模及分類速度，選取它作為混合型特征選擇算法的評(píng)估器，可以有效減少特征選擇過程中交叉驗(yàn)證的時(shí)間。一般混合型特征算法可以分為兩個(gè)階段:首先根據(jù)數(shù)據(jù)自身的特性使用過濾型特征選擇算法選取候選特征子集;然后在候選特征子集中使用特定的學(xué)習(xí)算法進(jìn)行交叉驗(yàn)證，選取優(yōu)化特征子集。該算法與傳統(tǒng)的混合型特征選擇算法不同，該算法在第一階段不是利用過濾型算法產(chǎn)生候選特征子集，而是通過計(jì)算信息增益對(duì)所有特征進(jìn)行排序，在第二階段使用貪心前向搜索法(GFS，greedy forward search)作為搜索策略，以核密度的Bayes 分類器作為評(píng)估器進(jìn)行封裝型特征選擇。通過計(jì)算信息增益對(duì)特征排序，能夠?qū)?duì)類別區(qū)分度高的特征排在前方，而GFS 方法則能夠優(yōu)先將這些區(qū)分度高的重要特征選入特征子集，降低搜索過程的盲目性，在減少搜索評(píng)估循環(huán)次數(shù)的同時(shí)，提高特征選擇的效果。為了方便表示，使用IGi，c表示特征Ai和類別C 之間的信息增益，算法的具體過程如下。

(1)計(jì)算每個(gè)特征與類別的信息增益IGi，c，根據(jù)信息增益值從大到小對(duì)特征進(jìn)行排序。

(2)特征排序完成后，進(jìn)入封裝型特征選擇循環(huán)。在循環(huán)中，使用GFS 作為搜索策略產(chǎn)生特征子集，基于核密度的Bayes 分類器作評(píng)估器，選取優(yōu)化特征子集。

算法使用Bayes 分類器5 折交叉驗(yàn)證獲得的分類錯(cuò)誤率均方差與分類錯(cuò)誤率均值的比值作為特征選擇循環(huán)的終止條件，該值的計(jì)算方法為

式中，R 是5 折交叉驗(yàn)證獲取的5 次分類錯(cuò)誤率，MSE(R)用于計(jì)算分類錯(cuò)誤率的均方差，MEAN(R)用于計(jì)算分類錯(cuò)誤率的均值。當(dāng)ferror值較小時(shí)，表明交叉驗(yàn)證的分類錯(cuò)誤率接近，分類結(jié)果穩(wěn)定。設(shè)定閾值ε，當(dāng)該值小于ε 時(shí)，終止特征選擇循環(huán)。文中經(jīng)過多次實(shí)驗(yàn)設(shè)定ε 值為1%。

3 實(shí)驗(yàn)及評(píng)估

3.1 實(shí)驗(yàn)方法

為評(píng)估所述方法的有效性，下面進(jìn)行了相關(guān)實(shí)驗(yàn)。實(shí)驗(yàn)具體步驟包含兩部分，第一部分直接采用核密度的Bayes 分類器進(jìn)行檢測(cè)，第二部分則采用第2 節(jié)描述的特征選擇技術(shù)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，然后采用基于核分布的Bayes 分類器進(jìn)行檢測(cè)。最后，對(duì)比采用上述特征選擇技術(shù)處理前后的檢測(cè)效果，以驗(yàn)證對(duì)信息質(zhì)量的影響。

實(shí)驗(yàn)使用的數(shù)據(jù)集源自Goose Bay 雷達(dá)系統(tǒng)返回的電離層的雷達(dá)信號(hào)，該系統(tǒng)共使用了16 個(gè)天線，傳輸功率在6.4 千瓦［15］。數(shù)據(jù)集共包含351 個(gè)樣本，共分為兩類，其中，有目標(biāo)出現(xiàn)的樣本225 條，未出現(xiàn)目標(biāo)的樣本126 條，每個(gè)樣本包含的特征數(shù)量共34 個(gè)，關(guān)于數(shù)據(jù)集及樣本特征的詳細(xì)描述參見［16］。

實(shí)驗(yàn)結(jié)果的評(píng)估采用了5 折交叉驗(yàn)證方式，即將數(shù)據(jù)集均分成5 份，每次使用其中的1 份作為測(cè)試數(shù)據(jù)，其余5 份作為訓(xùn)練數(shù)據(jù)，用于建立識(shí)別模型，這樣循環(huán)5 次，最后統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果。在檢測(cè)效果的評(píng)估指標(biāo)方面，采用常用檢測(cè)率(TP，true positive)、誤報(bào)率(FP，false positive)及準(zhǔn)確率(Accuracy)。在計(jì)算性能方面，由于數(shù)據(jù)集中的數(shù)據(jù)量過于小，難以通過實(shí)驗(yàn)進(jìn)行合理評(píng)價(jià)，但可以特征維度降低程度進(jìn)行評(píng)估。

3.2 實(shí)驗(yàn)結(jié)果及評(píng)估

特征選擇后剩余7 個(gè)特征，其編號(hào)分別是3、4、5、14、16、20、24。采用本文所述特征選擇方法前后的實(shí)驗(yàn)結(jié)果對(duì)比，如圖2 所示。

圖2 特征選擇前后實(shí)驗(yàn)結(jié)果對(duì)比

可以看出，采用本文所述的方法后，不僅數(shù)據(jù)維度大幅縮減，而且總體的識(shí)別準(zhǔn)確率、檢測(cè)率都得到了大幅提升，僅誤報(bào)率小幅上升。實(shí)驗(yàn)具體結(jié)果數(shù)據(jù)，見表1。

表1 特征選擇前后核密度Bayes 分類器實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明:本文所述方法能夠有效減少需要處理的數(shù)據(jù)量，提升信息質(zhì)量及軍事信息系統(tǒng)效能，適用于現(xiàn)代作戰(zhàn)環(huán)境。

4 結(jié) 語

伴隨物聯(lián)網(wǎng)等信息技術(shù)在軍事領(lǐng)域的不斷推廣應(yīng)用，促進(jìn)了現(xiàn)代作戰(zhàn)理論及實(shí)踐的發(fā)展。在新的作戰(zhàn)環(huán)境下，信息正成為取得作戰(zhàn)先機(jī)的關(guān)鍵要素。面向現(xiàn)代戰(zhàn)場(chǎng)環(huán)境產(chǎn)生的海量實(shí)時(shí)數(shù)據(jù)處理需求，本文提出了一種面向高維數(shù)據(jù)的特征選擇方法。實(shí)驗(yàn)結(jié)果表明:所提出的特征選擇方法能夠有效降低數(shù)據(jù)特征維度，減少需要處理的數(shù)據(jù)量，適用于網(wǎng)絡(luò)中心戰(zhàn)條件下的數(shù)據(jù)處理和傳輸。如何將所述的方法結(jié)合具體作戰(zhàn)任務(wù)，應(yīng)用于實(shí)際戰(zhàn)場(chǎng)環(huán)境，并依據(jù)實(shí)際情況加以優(yōu)化，是下一步工作的重點(diǎn)。

［1］ CROPLEY D H. Information and C4ISR Systems［EB/OL］. (1998－09－01). http://www. unisa. edu. au/seec/pubs/98papers/cropley%20－c4isr.pdf.

［2］ CLAYTON K. Information Quality:the Relationship to Recruitment in Pre－tertiary IT Education［R］. Australia:Griffith University，Brisbane，2003:65－77.

［3］［佚名］. The Economic Research Service's Information Quality Guide－lines［EB/OL］. (2003－08－07). /http://www.ers.usda.gov/a_bouters/quality/guide/lines3.pdf.

［4］(美)國(guó)防部參謀長(zhǎng)聯(lián)系會(huì)議.2010 年聯(lián)合作戰(zhàn)框架［R］. 1993.

［5］羅雪山，等. C3I 系統(tǒng)理論基礎(chǔ)［M］.長(zhǎng)沙:國(guó)防科技大學(xué)出版社，2000.

［6］吳枕江，劉雨. 指揮控制系統(tǒng)分析概論［M］. 長(zhǎng)沙:國(guó)防科技大學(xué)出版社，1992.

［7］POIRIER J A，BATES E，TEMPESTILLI M. How Much is a pound of C4ISR worth?［EB/OL］. http://www.dodccrp. org/events/2003/8th _ ICCRTS/pdf/143. pdf，2004－04－11/2004－06－26.

［8］NARENDRA P M，F(xiàn)UKUNAGA K. A Branch and Bound Algorithm for Feature Subset Selection［J］. Computers，IEEE Transactions on，1977，C－26(9):917－922.

［9］LIU H，MOTODA H.Feature Selection for Knowledge Discovery and Data Mining［M］. Holland:Kluwer Academic Publishers，1998.

［10］DOAK J. An Evaluation of Feature Selection Methods and Their Application to Computer Security［R］. Technical Report，Univ.of California at Davis，Dept. Computer Science，1992.

［11］ JAIN A，ZONGKER D. Feature Selection:Evaluation，Application，and Small Sample Performance［J］. Pattern Analysis and Machine Intelligence，IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19(2):153－158.

［12］ HOLLAND J. Adaption in natural and artificial systems［Z］.The University of Michigan Press.Ann Arbor，1975.

［13］ SKALAK B D. Prototype and Feature Selection by Sampling and Random Mutation Hill Climbing Algorithms［C］//Proceedings of the Eleventh International Conference on Machine Learning，1994:293－301.

［14］WILLIAMS N，ZANDER S，ARMITAGE G. A Preliminary Performance Comparison of Five Machine Learning Algorithms for Practical IP Traffic Flow Classification［J］. Computer Communication Review，2006，36(5):7－15.

［15］ http://eric. univ－lyon2. fr/ ～ricco/dataset/ionosphere.arff.

［16］SIGILLITO，V G，WING S P，HUTTON，L.V，et al. Classification of Radar Returns From The Ionosphere Using Neural Networks［J］. Johns Hopkins APL Technical Digest，1989(10):262－266.