一種基于多目標(biāo)遺傳算法的滿意度特征選擇方法

一種基于多目標(biāo)遺傳算法的滿意度特征選擇方法

1多目標(biāo)滿意優(yōu)化思想在特征選擇中的應(yīng)用在模式識(shí)別、機(jī)器學(xué)習(xí)和挖掘等領(lǐng)域，資源選擇可以降低資源向量維數(shù)，降低資源提取成本，簡(jiǎn)化分類器設(shè)計(jì)和提高識(shí)別率，已成為近年來一個(gè)充滿生機(jī)和活力的研究主題。資源選擇的任務(wù)是利用模型中的內(nèi)部信息，從一組資源中選擇性能最好的資源集，從而在理論上獲得最優(yōu)的資源集。因此，分類誤差概率最小的資源集在理論上是最好的，但分類誤差概率的計(jì)算取決于使用的特殊分類器和一般未知類條件的分布密度。資源選擇是典型的非典型橢圓解決方案的優(yōu)化問題。除了詳細(xì)的搜索方法外，很難確保獲得的資源集是最好的解。因此，在實(shí)際應(yīng)用中，人們總是尋找能夠計(jì)算和應(yīng)用的類分離規(guī)律和性能最好的搜索方法，以便獲得更好的次優(yōu)解。從這個(gè)角度來看，資源選擇本質(zhì)上是一個(gè)優(yōu)化問題，接收到的解是滿意的。此外，現(xiàn)有資源選擇算法相對(duì)較少地考慮資源集的維數(shù)和資源獲取的成本，因此在搜索第二次優(yōu)解的過程中，需要提前指定資源集的維數(shù)和資源集的效率較低。因此，有必要將多目標(biāo)適應(yīng)性優(yōu)化思想引入資源選擇，綜合考慮影響因素，評(píng)估資源選擇的質(zhì)量滿意度。滿意優(yōu)化是針對(duì)最優(yōu)解根本不存在或難以把握的優(yōu)化問題,或者存在最優(yōu)解但無法求得或求解代價(jià)太大的優(yōu)化問題而提出來的.滿意優(yōu)化有著廣泛的應(yīng)用背景,如靳蕃提出神經(jīng)計(jì)算的滿意解原理,席裕庚提出復(fù)雜工業(yè)過程的滿意控制,金煒東對(duì)滿意優(yōu)化的原理和方法作了系統(tǒng)研究,提出了兩類滿意優(yōu)化模型,并用于控制系統(tǒng)參數(shù)優(yōu)化和列車操縱優(yōu)化中,趙舵等和張葛祥等對(duì)滿意優(yōu)化展開了進(jìn)一步研究,分別將它用于模糊控制器設(shè)計(jì)和多變量控制系統(tǒng)設(shè)計(jì)中.這些應(yīng)用均取得了非常顯著的優(yōu)化效果.滿意優(yōu)化摒棄了傳統(tǒng)的最優(yōu)概念,強(qiáng)調(diào)的是“滿意”而不“最優(yōu)”,它將優(yōu)化問題的約束和目標(biāo)融為一體,將性能指標(biāo)要求的滿意設(shè)計(jì)與參數(shù)優(yōu)化融為一體,具有很大的適用性和靈活性.本文將滿意優(yōu)化思想引入到模式識(shí)別中,提出滿意特征評(píng)價(jià)準(zhǔn)則來對(duì)所提取的特征和挑選出的特征子集進(jìn)行滿意程度的質(zhì)量評(píng)價(jià),并提出滿意特征選擇方法(SFSM)來從大量特征中選擇出具有維數(shù)少、復(fù)雜度低和分類能力強(qiáng)的滿意特征集.在給出特征滿意度和特征集滿意度的定義之后,通過設(shè)計(jì)各個(gè)滿意度函數(shù),導(dǎo)出滿意特征選擇的計(jì)算模型,并詳細(xì)描述滿意特征的選擇算法.為驗(yàn)證方法的有效性,將SFSM應(yīng)用來進(jìn)行雷達(dá)輻射源信號(hào)特征的篩選,并與基于距離準(zhǔn)則的順序前進(jìn)法(SFSDC)、新特征選擇法(NFS)和多目標(biāo)遺傳算法(MOGA)進(jìn)行比較,結(jié)果顯示,SFSM在時(shí)間復(fù)雜性和選出的特征品質(zhì)方面都優(yōu)于SFSDC,NFS和MOGA.2評(píng)價(jià)和選擇滿意的特征satisfford2.1特征集類目滿意度衡量特征和特征集的滿意程度,首先需要給出評(píng)價(jià)標(biāo)準(zhǔn),即滿意度.滿意度是滿意優(yōu)化中最基本、最重要的概念,根據(jù)不同應(yīng)用背景和研究方法,已有幾種滿意度定義被提出.根據(jù)樣本的特點(diǎn),這里給出如下特征滿意度和特征集滿意度定義:定義1對(duì)于某一種特征t,設(shè)有n個(gè)分類類別,特征滿意度定義為{St=S(Jt),St∈,Jt=J(Jij),1≤i<j≤n,Jij=JΤ(Xi,Xj).(1)式中S(Jt)為特征滿意度函數(shù),是一單調(diào)不減函數(shù),所得的函數(shù)值表示對(duì)特征t進(jìn)行評(píng)價(jià)后所獲得的滿意度大小,Jt為對(duì)于特征t的類別可分離性判據(jù);J(·)為類別可分離性綜合函數(shù),一般可取線性加權(quán)函數(shù),max和min函數(shù)等.JT(·)為第i類與第j類的可分離性準(zhǔn)則函數(shù),如距離準(zhǔn)則函數(shù)、概率準(zhǔn)則函數(shù)和熵準(zhǔn)則函數(shù)等,Jij表示JT(·)的函數(shù)值,Xi和Xj表示第i類與第j類的特征樣本向量,若樣本數(shù)為M,則Xi=[xi1,xi2,…,xiM],Xj=[xj1,xj2,…,xjM].特征滿意度用于對(duì)單個(gè)特征品質(zhì)優(yōu)劣進(jìn)行評(píng)價(jià),滿意度值越大,則表示該特征的分類能力越強(qiáng),反之,則意味著該特征的分類能力越弱.采用特征滿意度對(duì)若干特征進(jìn)行評(píng)價(jià)后,可采用一些搜索算法(如順序前進(jìn)法等)來求得令人滿意的解.但是,采用這些基于排序思想的優(yōu)化算法得到的特征向量往往不太令人滿意,甚至有時(shí)會(huì)得到質(zhì)量很差的特征向量,所以,給出特征滿意度的定義還不夠,還需要給出特征集的滿意度定義,以便用于挑選質(zhì)量更好的特征集.特征集的滿意程度不僅與類別可分離性有關(guān),還與該特征集的維數(shù)和特征提取的復(fù)雜性有關(guān).所選特征集的維數(shù)大小會(huì)直接影響到分類器設(shè)計(jì)和特征提取的代價(jià),而特征復(fù)雜度的約束會(huì)使挑選出的特征的代價(jià)減少.由此,給出特征集滿意度定義如下:定義2設(shè)有一特征集T=[t1,t2,…,tz],Z為特征集維數(shù)且Z≥2,特征集滿意度定義如下:Sts=φ(sd,sc,sm),Sts∈,(2)式中φ(·)為特征集滿意度函數(shù),sd為特征集維數(shù)的滿意度,sc為特征集復(fù)雜性滿意度,sm為特征集類別可分離性滿意度,sd,sc和sm的定義如下:定義3設(shè)特征集的維數(shù)為d,且dmin≠dmax,則該特征集的維數(shù)滿意度定義為sd=f(d)=dmax-ddmax-dmin,sd∈,(3)式中f(·)為維數(shù)滿意度函數(shù),dmax為原始特征集的維數(shù),dmin為希望選出的特征集的最小維數(shù),若dmin=dmax,則令sd=1.維數(shù)滿意度反映了設(shè)計(jì)人員對(duì)選出的特征集維數(shù)的滿意程度.考慮維數(shù)滿意度是為了后續(xù)優(yōu)化算法在搜索過程中能自動(dòng)確定滿意特征集的維數(shù),可以解決當(dāng)前大多特征可分離性評(píng)價(jià)準(zhǔn)則需要人為預(yù)先確定所選特征集的維數(shù)和需要多次試探不同維數(shù)的問題.定義4設(shè)有一特征集T=[t1,t2,…,tZ],Z為特征集維數(shù),且Cmin≠Csum則該特征集的復(fù)雜性滿意度定義為sC=g(C)=Csum-CCsum-Cmin,sC∈.(4)式中若Cmin=Csum,則sC=1,g(·)為復(fù)雜性滿意度函數(shù),Cmin為原始特征集中復(fù)雜性的最小值,Ssum為原始特征集中所有特征復(fù)雜性的和,即Csum=L∑i=1Ci.(5)其中L為原始特征集維數(shù),Ci為第i個(gè)特征的復(fù)雜性.在式(4)中,C為特征集T的復(fù)雜性,即C=Ζ∑i=1Ci.(6)在模式識(shí)別中,特征提取需要花費(fèi)代價(jià),特征不同,代價(jià)也不同,引入復(fù)雜性滿意度可克服當(dāng)前多數(shù)特征評(píng)價(jià)準(zhǔn)則沒有涉及特征提取的代價(jià)問題.根據(jù)實(shí)際問題的不同,特征提取復(fù)雜性可用時(shí)間、能量等來進(jìn)行定量計(jì)算,不過,對(duì)于大多數(shù)模式識(shí)別問題,如信號(hào)識(shí)別、圖像識(shí)別等,特征的復(fù)雜性多表現(xiàn)為獲取特征所需的時(shí)間.定義5特征集類別可分離性滿意度主要是對(duì)多種特征組成的多維特征向量T=[t1,t2,…,tZ](Z為特征集維數(shù))的分類能力滿意程度的評(píng)價(jià),定義如下:{sm=ψ(Jm),sm∈,Jm=JΜ(Jmij),1≤i<j≤n,Jmij=JΤΜ(Xmi,Xmj).(7)式中ψ(Jm)為特征集類別可分離性滿意度函數(shù),是一單調(diào)不減函數(shù),Jm為特征集類別可分離性判據(jù);JM(·)為特征集類別可分離性綜合函數(shù).JTM(·)為第i類與第j類的特征集可分離性準(zhǔn)則函數(shù),Jmij表示JTM(·)的函數(shù)值,Xmi和Xmj表示第i類與第j類的特征集樣本矩陣,若樣本數(shù)為M,則:Xmi=[xt1i1xt1i2?xt1iΜxt2i1xt2i2?xt2iΜ???xtΖi1xtΖi2?xtΖiΜ]?(8)Xmj=[xt1j1xt1j2?xt1jΜxt2j1xt2j2?xt2jΜ???xtΖj1xtΖj2?xtΖjΜ].(9)綜上所述,滿意特征集評(píng)價(jià)準(zhǔn)則為{Sts=φ(sd,sc,sm),sd=f(d),sc=g(C),sm=ψ(Jm),Jm=JΜ(Jmij,1≤i<j≤n),Jmij=JΤΜ(Xmi,Xmj).(10)2.2qga的全局收斂性根據(jù)滿意特征評(píng)價(jià)準(zhǔn)則,下面逐步描述從一組原始特征集中挑選出滿意特征集的步驟:Step1確定待分類類別數(shù)n和原始特征集的維數(shù)L,并對(duì)于每一種特征的每一類模式,均產(chǎn)生M個(gè)特征樣本,于是,總特征樣本數(shù)為L×n×M.Step2確定參數(shù)dmax和dmin.一般地,dmax取為原始特征集的維數(shù),dmin取為1.并計(jì)算原始特征集中各個(gè)特征的復(fù)雜性,根據(jù)定義4求得參數(shù)Csum和Cmin.Step3采用QGA得到一組特征集.QGA是新發(fā)展起來的一種基于量子計(jì)算原理的概率優(yōu)化方法,它以量子計(jì)算的一些概念和理論為基礎(chǔ),用量子位編碼來表示染色體,用量子門作用和量子門更新染色體來完成進(jìn)化搜索,具有種群規(guī)模小而不影響算法性能、同時(shí)兼有“勘探”和“開采”的能力、收斂速度快和全局尋優(yōu)能力強(qiáng)的特點(diǎn).采用QGA獲得一組特征集的具體過程為:1)QGA的初始化:確定種群大小h和量子位的數(shù)目q,包含h個(gè)個(gè)體的種群P={p1,p2,…,ph},其中pj(j=1,2,…,h)為種群中的第j個(gè)個(gè)體,描述如下:pj=[α1β1┊┊α2β2┊┊??┊┊αqβq].(11)式中αi,βi(i=1,2,…,q)分別為第i個(gè)量子位量子基態(tài)|1?和0?|的概率幅,初始時(shí)所有αi,βi均取為1/2,表示在初始搜索時(shí)所有狀態(tài)以相同的概率進(jìn)行疊加.與傳統(tǒng)遺傳算法相比,QGA的種群h可取得很小,一般取為20左右即可,量子位數(shù)目q取為與原始特征集的維數(shù)相等.2)根據(jù)P中各個(gè)體的概率幅構(gòu)造出量子疊加態(tài)的觀測(cè)態(tài)R,R={a1,a2,…,ah},其中aj(j=1,2,…,h)為每個(gè)個(gè)體的觀測(cè)狀態(tài),即一個(gè)由“0”和“1”組成的二進(jìn)制串,于是可以得到h個(gè)二進(jìn)制串,每一個(gè)二進(jìn)制串就代表著一個(gè)特征集,其中為“1”的位表示該特征包含在此特征集中,為“0”的位表示該特征不包含在此特征集中.Step4根據(jù)各特征集的維數(shù)分別計(jì)算它們的維數(shù)滿意度,計(jì)算公式已由式(3)給出.Step5由各特征集的復(fù)雜性分別計(jì)算它們的復(fù)雜性滿意度,計(jì)算公式已由式(4)給出.Step6根據(jù)式(7)計(jì)算各特征集的分類能力滿意度,在計(jì)算過程中,各函數(shù)設(shè)計(jì)如下:{ψ(Jm)=(Jm)2,JΜ(Jijm,1≤i<j≤n)=∑i=1n-1∑j=i+1nwijJij.(12)JΤΜ(Xim,Xjm)=1-∫?z∫f(x1,?,xΖ)?g(x1,?,xΖ)dx1?dxΖ∫?z∫f2(x1,?,xΖ)dx1?dxΖ∫?z∫g2(x1,?,xΖ)dx1?dxΖ.(13)在式(12)中,wij(1≤i<j≤n)一般取為相等,當(dāng)然,若有特殊要求時(shí),也可取不相等.在式(13)中,Z為特征子集的維數(shù),f(x1,…,xZ)和g(x1,…,xZ)分別為特征子集中第i類與第j類特征樣本分布函數(shù),應(yīng)用場(chǎng)合不同,特征樣本的分布函數(shù)可能有所不同,但一般可取數(shù)學(xué)期望為μi,μj,方差為σi,σj的Guassian函數(shù),即μi=E(Xmi),μj=E(Xmj),σi=D(Xmi),σj=D(Xmj).從式(13)可看出,當(dāng)兩類特征樣本分布函數(shù)在多維特征空間中完全分離時(shí),則該特征集分類能力滿意度值達(dá)到最大值1,隨著兩類特征樣本分布函數(shù)在高維特征空間中交疊程度的增加,滿意度值會(huì)逐漸減小,直到兩分布函數(shù)完全重合時(shí),滿意度值變?yōu)樽钚≈?.順便指出,當(dāng)采用式(1)對(duì)單個(gè)特征的品質(zhì)進(jìn)行滿意度評(píng)價(jià)時(shí),特征滿意度函數(shù)s(·)和類別可分離性綜合函數(shù)j(·)分別可采用與ψ(·)和JM(·)相同的函數(shù),而兩類可分離性準(zhǔn)則函數(shù)JT(·)可采用JTM(·)的特殊形式,即函數(shù)JTM(·)為一維函數(shù)時(shí)的情況.Step7特征集滿意度函數(shù)φ(·)只與3種因素sd,sc和sm有關(guān),因而可直接取為較簡(jiǎn)單的線性加權(quán)函數(shù),即φ(sd,sc,sm)=ωdsd+ωcsc+ωmsmωd+ωc+ωm.(14)式中ωd,ωc,ωm分別為sd,sc,sm的加權(quán)系數(shù).Step8將Step7中的特征集滿意度函數(shù)作為QGA的適應(yīng)度函數(shù)對(duì)種群中的所有個(gè)體進(jìn)行適應(yīng)值評(píng)價(jià).Step9保留最佳個(gè)體,并判斷是否滿足終止條件,若滿足,則算法終止,否則,執(zhí)行下一步.Step10采用文獻(xiàn)中的方法計(jì)算量子旋轉(zhuǎn)門的旋轉(zhuǎn)角,并將量子門作用于種群中所有個(gè)體的概率幅,即將種群P中的所有個(gè)體的概率幅進(jìn)行更新.Step11QGA的進(jìn)化代數(shù)增1,算法轉(zhuǎn)至Step3繼續(xù)進(jìn)行,直到算法結(jié)束.SFSM的全局收斂性直接由QGA的全局收斂性決定,在文獻(xiàn)中,采用隨機(jī)泛函理論對(duì)QGA的全局收斂性進(jìn)行了證明,限于篇幅,這里就不再詳細(xì)討論.3特征選擇特征在我們先前的工作中,已經(jīng)從10種典型雷達(dá)輻射源信號(hào)中分別提取出了16種特征.這10種信號(hào)分別為:CW,FD,LFM,NLFM,BPSK,QPSK,MPSK,IPFE,FSK和CSF.16種特征分別為信息維數(shù)、盒維數(shù)、關(guān)聯(lián)維數(shù)、兩種相像系數(shù)、近似熵、Lempel-Ziv復(fù)雜度、范數(shù)熵和小波包3層分解所得的從低頻到高頻的8個(gè)特征.將這16種特征組成原始特征集,并分別用標(biāo)號(hào)1～16來表示.在實(shí)驗(yàn)前,先對(duì)每一種雷達(dá)輻射源信號(hào)在5～20dB的信噪比范圍內(nèi)每隔5dB產(chǎn)生150個(gè)樣本,這樣,每一種雷達(dá)輻射源信號(hào)總共有600個(gè)樣本,其中200個(gè)樣本用于特征滿意度的評(píng)價(jià)、特征選擇和分類器訓(xùn)練,其余400個(gè)樣本用于分類識(shí)別的測(cè)試實(shí)驗(yàn).為了便于理解特征滿意度的概念和對(duì)照分析下面幾種方法挑選出的特征集的滿意度與特征集所包含的各個(gè)特征的滿意度之間的關(guān)系,先采用特征滿意度來分別評(píng)價(jià)這16種特征的質(zhì)量,得到的從大到小的排序結(jié)果如表1所示.特征12和特征6分別為最滿意和最不滿意的特征.當(dāng)采用SFSM進(jìn)行特征選擇時(shí),根據(jù)前面的分析,參數(shù)L=16,n=10,M=200,dmax=16,dmin=1,Csum=2163.503,Cmin=6.203,P=20,m=16.滿意度指標(biāo)sd,sc和sm的權(quán)值選擇對(duì)算法的結(jié)果將會(huì)產(chǎn)生一定的影響,根據(jù)經(jīng)驗(yàn)和多次反復(fù)試驗(yàn),ωd,ωc和ωm分別取為0.20,0.10和0.70比較合適.算法運(yùn)行100次,所得特征集均由特征5和特征10組成,特征集滿意度為0.9817.該特征集并非由表1中的滿意度值最大的兩特征構(gòu)成,說明采用特征集滿意度選出的特征并不是簡(jiǎn)單的按照單個(gè)特征滿意度值進(jìn)行排序選擇的,這正體現(xiàn)了特征集滿意度還要受維數(shù)和復(fù)雜性的影響.為了進(jìn)行對(duì)比,本文還采用SFSDC,NFS和MOGA進(jìn)行特征選擇,SFSDC的距離準(zhǔn)則函數(shù)為Gt=∑i∑j(mi-mj)2σi2+σj2,(t=1,2,?,U).(15)式中mi,mj分別為第i類和第j類信號(hào)的樣本均值,σi,σj分別為第i類和第j類信號(hào)的樣本方差,U為特征總數(shù).由于SFSDC和NFS都需要事先指定特征集的維數(shù),為了與SFSM進(jìn)行識(shí)別結(jié)果比較,SFSDC和NFS的維數(shù)都指定為與采用SFSM所獲得的特征集維數(shù)相同.MOGA的種群大小取為100,交叉和變異概率分別取為0.8和0.007.算法的最大進(jìn)化代數(shù)設(shè)為500,4種特征選擇方法消耗的計(jì)算時(shí)間的100次實(shí)驗(yàn)的統(tǒng)計(jì)值如表2所示.實(shí)驗(yàn)是在PentiumIV(CPU2.0G,RAM512MB)上完成的.將SFSDC和NFS的維數(shù)都取為2并進(jìn)行特征選擇,SFSDC獲得的最佳特征集由特征4和5組成,NFS獲得的最佳特征集由特征6和7組成,MOGA獲得的最佳特征集則特征1和12構(gòu)成,各特征集滿意度已在表2中給出.分別將SFSM,SFSDC,NFS和MOGA獲得的特征集用來在5～20dB的信噪比范圍內(nèi)進(jìn)行分類識(shí)別測(cè)試實(shí)驗(yàn),實(shí)驗(yàn)中所采用的分類器為神經(jīng)網(wǎng)絡(luò)分類器,其結(jié)構(gòu)為2-15-10,輸入層神