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

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