潘笑天,王麗萍,張夢輝

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

1 引 言

特征選擇(Feature Selection,FS)是模式識別和數(shù)據(jù)挖掘領(lǐng)域常用的降維方法,其目的是刪除數(shù)據(jù)集中含有的冗余或噪聲特征信息,提高模型的識別準(zhǔn)確率.良好的特征選擇算法是從問題域中找到最大程度表征原始特征,且具有較高準(zhǔn)確度的最小特征子集,從而簡化學(xué)習(xí)模型,加快算法學(xué)習(xí)過程.對于一個含有n個特征的數(shù)據(jù)集,其可能的特征選擇方案有2n種,在沒有先驗(yàn)知識的情況下,很難從中選擇更優(yōu)模型精度和更少特征維度的方案解[1],并且由于特征之間存在的復(fù)雜相關(guān)性,例如一個冗余(或強(qiáng)相關(guān))的特征與其他特征組合可能變得強(qiáng)相關(guān)(或冗余),因此將特征作為獨(dú)立變量進(jìn)行評估,并不能獲得滿意的特征子集[2].

在特征選擇問題中,評估方法和搜索策略一直是解決該問題的關(guān)鍵.目前已有的特征選擇方法按評估機(jī)制可以分為3類[3]:1)濾波法,2)包裝法和3)嵌入式法.其中,濾波法按照特征的統(tǒng)計(jì)特性對所有特征進(jìn)行排名,并將低于設(shè)定閾值的特征刪除,通常一次運(yùn)算能夠獲得一組高統(tǒng)計(jì)特性的特征子集,計(jì)算量較小,但是該方法獨(dú)立于模型訓(xùn)練過程,缺乏基于學(xué)習(xí)器的評估過程,所選的特征子集在一些學(xué)習(xí)器上表現(xiàn)不佳.包裝法是將學(xué)習(xí)器作為黑盒評估器,將學(xué)習(xí)器的性能作為目標(biāo)函數(shù),該方法通常能找到適合當(dāng)前學(xué)習(xí)器的最佳特征子集,但是計(jì)算復(fù)雜度較高,因此還需要高效的搜索策略提高算法的整體效率.嵌入式法將模型構(gòu)建過程與特征排序過程相結(jié)合,得到各個特征的權(quán)值系數(shù),并根據(jù)權(quán)值系數(shù)從大到小選擇特征,但是該方法的適用范圍有限,只有可以得到特征系數(shù)(邏輯回歸、線性回歸、神經(jīng)網(wǎng)絡(luò))或者特征重要度(樹模型)的算法才可以使用嵌入式法.

包裝法通常能獲得比濾波法更高的模型精度,且比嵌入法更廣泛的適用范圍,是目前廣泛研究的課題.在包裝法研究中,搜索技術(shù)是提升算法效率的關(guān)鍵.目前已有的搜索技術(shù)[4],包括窮舉法,隨機(jī)搜索,啟發(fā)式搜索(如貪婪搜索,進(jìn)化計(jì)算,群智能方法等).隨著特征維數(shù)的增加,最優(yōu)特征組合的數(shù)量也在成倍增加.啟發(fā)式搜索能夠明顯提高搜索效率,表現(xiàn)出更快的收斂速度,但大多數(shù)啟發(fā)式方法易收斂于局部最優(yōu)值.近年來,進(jìn)化計(jì)算(Evolutionary Computation,EC)因其全局可搜索性而受到廣泛關(guān)注,并且與其他搜索技術(shù)相比,EC不需要領(lǐng)域知識或和對搜索空間的假設(shè),更適用于求解FS問題[5].根據(jù)優(yōu)化目標(biāo)的數(shù)量,可進(jìn)一步劃分為單目標(biāo)FS和多目標(biāo)FS,其中單目標(biāo)FS主要以特征屬性最大化或模型性能最優(yōu)為評估標(biāo)準(zhǔn);而在多目標(biāo)FS中,通常將多個特征屬性或特征數(shù)目作為額外的優(yōu)化目標(biāo),從而獲得模型精度或者特征屬性最大化的緊湊型特征子集.在濾波法和包裝法中均可以使用基于多目標(biāo)優(yōu)化的FS方法.因此,在多目標(biāo)優(yōu)化框架下,結(jié)合濾波法的統(tǒng)計(jì)特性和包裝法的模型評估優(yōu)勢,并設(shè)計(jì)高性能的搜索機(jī)制,提出了一種基于靶向量引導(dǎo)的稀疏多目標(biāo)特征選擇算法.貢獻(xiàn)有以下3點(diǎn):

1)提出一種包裝法與濾波法混合的多目標(biāo)特征選擇算法框架.利用濾波法的特征統(tǒng)計(jì)特性引導(dǎo)包裝法搜索最優(yōu)特征子集,并根據(jù)包裝法的模型評估更新特征交互特性,由交互式引導(dǎo)和更新策略充分結(jié)合兩種方法的優(yōu)勢.

2)設(shè)計(jì)靶向量引導(dǎo)的最優(yōu)特征子集搜索機(jī)制.包括3個改進(jìn)策略:基于互信息的高質(zhì)量特征子集初始化策略;稀疏翻轉(zhuǎn)&修復(fù)策略保證后代子集的稀疏性;并由靶向量更新策略動態(tài)評估特征的重要性.

3)提出的WF-MOFS算法在15個常用數(shù)據(jù)集與5種流行的特征選擇算法相比,在算法性能(HV均值),獲得的模型精度和特征維數(shù),以及時間復(fù)雜度上均具有優(yōu)勢.

2 相關(guān)工作

2.1 多目標(biāo)特征選擇問題優(yōu)化模型

假設(shè)數(shù)據(jù)集S中包含K個樣本和D維特征,Fset為所有特征的集合,一個多目標(biāo)特征選擇方法是從Fset中選擇d個特征子集(d?D)來滿足優(yōu)化目標(biāo),其數(shù)學(xué)定義如下:

MinimizeF=(F1(X),F2(X),…,Fm(X))T
s.t.X=(x1,x2,…,xD)

(1)

其中,xj∈{0,1},j=1,2,…,D,X為二進(jìn)制字符串,當(dāng)時表示第個特征被包含在最優(yōu)特征子集中,當(dāng)時表示第個特征被剔除,表示被選擇的特征數(shù)量.

在濾波法中,通常將最大化互信息、最大化信息熵和最小化冗余度等作為優(yōu)化目標(biāo);而在包裝法中,通常將最小化模型誤差率和最小化特征選擇數(shù)量作為優(yōu)化目標(biāo).而在混合方法中,通常在算法的不同階段考慮上述兩組優(yōu)化目標(biāo).

2.2 多目標(biāo)特征選擇算法研究進(jìn)展

在多目標(biāo)特征選擇問題中,通常需要在提高特征的多個統(tǒng)計(jì)特性和降低冗余,或者在提高模型精度和簡化學(xué)習(xí)模型之間求得目標(biāo)平衡.多目標(biāo)優(yōu)化算法因其能夠求解多個相互沖突的優(yōu)化目標(biāo),并獲得一組Pareto解供決策者選擇,因此被廣泛應(yīng)用于特征選擇中.基于多目標(biāo)的特征選擇方法(MOFS)按評估機(jī)制可以分為基于濾波法、基于包裝法、基于濾波法和包裝法混合的多目標(biāo)特征選擇方法.

1)基于濾波法的MOFS.如Xue等人[6]以特征子集的信息熵和冗余度作為兩個優(yōu)化目標(biāo),設(shè)計(jì)了基于非支配排序的二進(jìn)制粒子群算法(CMDfsMI)用來選取最優(yōu)特征子集,該方法與單目標(biāo)濾波法相比,在特征降維方面優(yōu)勢明顯,但是算法設(shè)計(jì)時并沒有進(jìn)行模型評估,也沒有與基于包裝法的多目標(biāo)特征選擇算法進(jìn)行對比,因此所獲得的特征子集并不一定能夠達(dá)到較高的分類精度.

2)基于包裝法的MOFS.通常不考慮特征的統(tǒng)計(jì)特性,而是依賴算法搜索能力在目標(biāo)空間中尋找最優(yōu)的特征組合,目前研究集中在根據(jù)問題的稀疏性、變量的二元屬性及高維特性等設(shè)計(jì)高性能的算法,包括新的支配關(guān)系、遺傳算子、大規(guī)模優(yōu)化等幾個角度提高算法性能.如李小林等人[7]提出改進(jìn)的帝王蝶優(yōu)化算法用于特征選擇,但是在支配關(guān)系中強(qiáng)調(diào)準(zhǔn)確度大于特征數(shù)要求,雖然有利于算法快速收斂,但是可能會獲得最優(yōu)精度的非最小特征子集,在簡化模型方面優(yōu)勢不明顯.Xue[8]等人同時優(yōu)化特征數(shù)量和分類精度,為了提高算法搜索能力,設(shè)計(jì)了5種交叉算子,并在進(jìn)化不同階段由輪盤賭選擇,該方法雖然獲得的解集質(zhì)量優(yōu)于5種對比算法,但是并沒有結(jié)合特征選擇問題本身的求解特點(diǎn),僅是對多目標(biāo)優(yōu)化算法的一種改進(jìn)方法.近年來大規(guī)模多目標(biāo)優(yōu)化算法被廣泛應(yīng)用于求解特征選擇問題中,如Tian等人[9]在SparseEA提出了稀疏初始化和稀疏算子用于求解維度較高特征選擇問題.Tian等人[10]在PMMOEA中利用頻繁模式挖掘最大和最小頻繁項(xiàng)集,有利于減少算法搜索空間,加速算法收斂.但上述兩種算法同樣是針對多目標(biāo)算法本身的改進(jìn),雖然在處理稀疏大規(guī)模多目標(biāo)優(yōu)化問題上具有優(yōu)勢,但是在處理特征選擇問題時缺乏對特征統(tǒng)計(jì)特性的分析,因此也存在一定的局限性.

3)基于濾波法和包裝法混合的MOFS,集成特征統(tǒng)計(jì)特性分析與模型評估兩種方法的優(yōu)點(diǎn),是近年來研究的熱點(diǎn).Ghosh等人[11]在WFACOFS方法中首先使用特征相似度選擇特征子集,然后再啟動包裝法對所選特征進(jìn)一步評估.Huang等人[12]提出Relief-BSTA算法,算法分為兩階段:在濾波法階段,利用Relief減少搜索空間,并提供特征信息,在包裝法階段,利用BSTA算法根據(jù)學(xué)習(xí)器性能評估特征子集.盡管基于包裝-濾波混合的特征選擇方法的解集質(zhì)量明顯優(yōu)于使用單個方法,但是在上述兩種方法中,濾波法和包裝法還是分階段使用的,兩種方法之間的信息傳遞和引導(dǎo)效果不明顯.最近一些研究探討混合算法的交互策略,Liu等人[13]提出了GR-MOEA算法,包含兩個種群,即濾波種群和包裝種群,并提出了一種交互方案,包裝種群引導(dǎo)濾波種群朝高質(zhì)量種群發(fā)展,而濾波種群用于修復(fù)包裝種群,由于該算法使用了兩個種群,其中濾波種群對包裝種群的作用只是對全0列變量的修復(fù),而要花費(fèi)與包裝法種群相同的進(jìn)化代價,算法的整體效率不高.Cheng等人[14]提出了SM-MOEA算法,通過轉(zhuǎn)向矩陣計(jì)算每個個體中每個特征被選擇的概率,在初始化過程中轉(zhuǎn)向矩陣是由特征的互信息和種群排序決定,并使用降維算子和修復(fù)算子更新個體特征的選擇概率,但是作者也在文中提及對每個個體及特征的導(dǎo)向值進(jìn)行更新,計(jì)算成本仍然很高.

2.3 研究動機(jī)

通過上述分析可知,目前研究存在的不足主要包括以下幾個方面:1)基于濾波法的MOFS側(cè)重于對多個特征統(tǒng)計(jì)特性同時進(jìn)行組合優(yōu)化,獲得高統(tǒng)計(jì)特性的最優(yōu)特征子集,由于未使用模型評估,算法復(fù)雜度小,但是特征間存在復(fù)雜的交互關(guān)系,高統(tǒng)計(jì)特性的特征組合并不一定能夠構(gòu)建良好的分類模型,因此分類精度無法保證;2)基于包裝法的MOFS側(cè)重對算法的改進(jìn)研究,提高模型的分類精度,但是并沒有降低模型評估代價,且大多數(shù)方法在選擇特征子集時并沒有結(jié)合特征統(tǒng)計(jì)特性,如果缺乏特征信息的引導(dǎo),巨大搜索空間單純依靠算法的搜索能力獲得高質(zhì)量的解集同樣困難;3)基于濾波-包裝混合的MOFS彌補(bǔ)上述兩種方法的不足,能夠獲得比使用單一方法更高質(zhì)量的特征子集.但是在大多混合方法中并沒有充分結(jié)合兩者優(yōu)勢,目前分階段和分種群使用兩種方法,濾波法對包裝法的引導(dǎo)作用效果不大,而在進(jìn)化中對個體和特征逐個引導(dǎo)和評估的計(jì)算成本也較高,此外在混合方法中算法的求解效率也待進(jìn)一步提高.因此,在混合方法中還需解決3個問題:1)如何利用濾波法以較小的計(jì)算開銷獲得特征的統(tǒng)計(jì)特性,并引導(dǎo)包裝法進(jìn)行特征選擇,同時結(jié)合包裝法的評估機(jī)制保證子集的分類精度,更新特征的交互特性;2)如何設(shè)計(jì)引導(dǎo)和更新機(jī)制能充分結(jié)合兩種方法的優(yōu)勢,且降低評估復(fù)雜度;3)如何設(shè)計(jì)高性能的多目標(biāo)優(yōu)化算法提高混合算法的求解效率.為解決上述問題,提出了靶向量引導(dǎo)的稀疏多目標(biāo)特征選擇算法(WF-MOFS),并在下文進(jìn)行詳細(xì)介紹.

3 算法設(shè)計(jì)

在WF-MOFS中,設(shè)計(jì)了3個策略用于充分結(jié)合濾波法和包裝法的優(yōu)勢,包括:基于互信息的種群初始化策略和靶向量初始化策略,基于種群表現(xiàn)和特征頻率的靶向量更新策略,以及基于靶向量的稀疏翻轉(zhuǎn)及修復(fù)算子,算法步驟如下:

Step1.將數(shù)據(jù)集按6∶2∶2比例劃分為訓(xùn)練集,測試集和驗(yàn)證集;

Step2.初始化種群Pop和特征靶向量TV,見算法1;

Step3.訓(xùn)練學(xué)習(xí)模型,評估初始種群的目標(biāo)函數(shù)值,即模型誤差error和特征個數(shù)1×1,計(jì)算初始目標(biāo)函數(shù)均值作為初始種群表現(xiàn)Pef,計(jì)算初始特征選擇頻率Occ.

Step4.當(dāng)Gen<=Maxgen,算法迭代優(yōu)化:

Step4.1.利用錦標(biāo)賽法選擇父代個體[15];

Step4.2.對父代個體使用基于靶向量的稀疏翻轉(zhuǎn)&修復(fù)算子產(chǎn)生子代,見算法3和算法4;

Step4.3.訓(xùn)練學(xué)習(xí)模型并評估子代個體目標(biāo)函數(shù)值;

Step4.4.對父子代個體進(jìn)行環(huán)境選擇[15];

Step4.5.更新靶向量,見算法2;

Step4.6.Gen=Gen+1;

Step5.當(dāng)Gen>Maxgen,輸出當(dāng)前種群,并在驗(yàn)證集上測試,計(jì)算模型誤差.

1)基于互信息的種群及靶向量初始化策略,如算法1所示.

算法1.初始化策略

輸入：訓(xùn)練集Train_data

輸出：初始化特征靶向量TV和初始化種群Pop

1.利用公式(2)計(jì)算每個特征與類標(biāo)簽的互信息

2.利用公式(3)～公式(4)計(jì)算初始特征靶向量TV

3.fori=1:N

4.Pop(i,TounamentSelection(2,ceil(rand×D),Tv))=1

5. end

在初始代,側(cè)重利用統(tǒng)計(jì)特性來評估特征的重要性,并選擇重要性高的特征組合作為初始種群,相較于隨機(jī)初始化策略,提供了一種理想的特征組合方案,有利于進(jìn)化朝著有前景的方向發(fā)展.互信息提供了一種特征與類標(biāo)簽關(guān)聯(lián)強(qiáng)度的度量方式,如公式(2)所示:

Ij=I(Fj,C)=H(C)-H(C|Fj)

(2)

其中,Fj表示數(shù)據(jù)集中的第個特征,j=1,2,…,D,D為特征個數(shù).C表示類標(biāo)簽向量,I(Fj,C)表示第j個特征與類標(biāo)簽向量的相關(guān)性,Ij值越大,相關(guān)性越強(qiáng),重要性越高.

靶向量(Target Vector)用來記錄每個特征的重要程度,初始代由訓(xùn)練集中每個特征的互信息計(jì)算而得,如公式(3)所示:

TV={Tvj|j=1,2,…,D}

(3)

其中,Tvj=1-softmax(Ij).softmax(Ij)是采用softmax方法對每個特征的互信息值進(jìn)行歸一化,取值范圍(0,1),softmax方法能夠避免最小的特征靶值Tvj的歸一化結(jié)果為0,在后續(xù)靶向量更新過程中始終計(jì)算為0等不利影響,如公式(4)所示:

(4)

Tvj越小,特征的重要性越強(qiáng),在種群初始化過程中被選擇的概率越大,如算法1第4行,利用錦標(biāo)賽法根據(jù)TV值對特征進(jìn)行比較,最終選擇獲勝的ceil(rand*D)個特征所對應(yīng)的變量初始化為1,其余變量初始化為0.

2)基于種群表現(xiàn)和特征選擇頻率的靶向量更新策略.如2.3節(jié)所述,特征選擇是組合優(yōu)化的結(jié)果,由于特征間存在的復(fù)雜相關(guān)性,高統(tǒng)計(jì)特性的特征結(jié)合并不一定能構(gòu)建良好的學(xué)習(xí)模型,因此需要根據(jù)不同特征組合的種群表現(xiàn)對靶向量進(jìn)行更新,如算法2所示.

算法2.靶向量更新策略

輸入：輸入t-1代的種群表現(xiàn)Pef, 特征頻率Occ,靶向量Tv,和當(dāng)代種群Pop.decs,Pop.objs

輸出：更新后的Pef,Occ,Tv

1.new_Pef=mean(Pop.objs);%計(jì)算當(dāng)代種群目標(biāo)函數(shù)均值

2.temp_Pef=new_Pef./Pef;% 計(jì)算目標(biāo)函數(shù)值變化率

3.Pef=new_Pef;

4.Tv_Pef=temp_Pef(1)*temp_Pef(2);%計(jì)算當(dāng)代種群表現(xiàn)

5.new_Occ=sum(Pop.decs,1)./N;%計(jì)算當(dāng)代種群的特征選擇頻率

6.Tv_Occ=new_Occ./Occ; %計(jì)算特征頻率的變化率

7.Occ=new_Occ;

8.Tv=Tv./(Tv_Pef*Tv_Occ);%計(jì)算更新后靶向量

為了更好理解更新靶向量的計(jì)算過程,圖1給出種群個體數(shù)Pop=3,特征數(shù)目D=7的t-1代和t代種群構(gòu)成及更新靶向量的計(jì)算過程.

對于第t-1代和第t代種群,分別計(jì)算每個個體的目標(biāo)函數(shù)值F1(模型誤差)和F2(選擇的特征個數(shù)),則每代種群表現(xiàn)(Perf)為所有個體目標(biāo)函數(shù)值均值.然后計(jì)算每代種群中各個特征的選擇頻數(shù)(Sum_Occ),并采用歸一化的方法計(jì)算特征選擇頻率(Occ),如公式(5)所示:

Occj=Sum_Occj/D

(5)

其中,Occj表示第個特征選擇頻率的歸一化結(jié)果,D為特征個數(shù).則靶向量的更新因子(Update factor,Uf)及更新方式如式(6)、式(7)所示:

(6)

TVt=TVt-1/(Uf)

(7)

3)基于靶向量的稀疏翻轉(zhuǎn)及修復(fù)算子.如2.3節(jié)所述,如果缺乏特征信息的引導(dǎo),巨大搜索空間單純依靠算法的搜索能力獲得高質(zhì)量的特征子集,通常需要耗費(fèi)更多的評估次數(shù).因此在遺傳操作過程中,設(shè)計(jì)了基于靶向量的稀疏翻轉(zhuǎn)及修復(fù)算子,其偽代碼如算法3、算法4所示.

算法3.稀疏翻轉(zhuǎn)算子

輸入：父代交配集Parent1和Parent2,靶向量TV

輸出：新生成的種群Offspring

1.for i=1:N %交叉算子;

2.if rand<0.5;

3. index=find(Parent1(i,:)&～Parent2(i,:))

4. 用錦標(biāo)賽選擇靶值較大的一個index;

5. Offspring*(i,index)= 0;

6.else

7. index=find(～Parent1(i,:)& Parent2(i,:));

8. 用錦標(biāo)賽選擇靶值較小的一個index;

9. Offspring*(i,index)= 1;

10.end

11.end

12.for i=1:N %變異算子

13. if rand<0.5

14.從Offspring*(i,:)= 1中用錦標(biāo)賽選擇index將其變?yōu)?;

15. else

16.從Offspring*(i,:)= 0中用錦標(biāo)賽選擇index將其變?yōu)?;

17. end

18.end

為了充分探索潛在的搜索空間并保持子代的稀疏特性,對父母個體按位匹配,以rand<0.5的概率找到Parent1為1,Parent2為0的位變量,用錦標(biāo)賽從中選擇靶值較大的一位將其變?yōu)?,或以rand≥0.5的概率找到Parent1為0,Parent2為1的位變量,用錦標(biāo)賽從中選擇靶值較小的一位將其變?yōu)?.為了進(jìn)一步實(shí)現(xiàn)全局搜索,以rand<0.5的概率從后代解中找到值為1的位變量,用錦標(biāo)賽從中選擇靶值較大的一位將其變異為0,或以rand≥0.5的概率找到值為0的位變量,用錦標(biāo)賽從中選擇靶值較小的一位將其變異為1,如圖2所示.

圖2 稀疏翻轉(zhuǎn)算子Fig.2 Sparse turn operator

由于在遺傳操作過程中可能會產(chǎn)生全0行向量,即所有特征均不選擇,則無法對模型建模,或者全0列向量,表明在當(dāng)代種群中該特征的選擇頻率為0,則在更新靶向量時導(dǎo)致該特征靶值計(jì)算為0,因此進(jìn)一步提出了基于靶向量的修復(fù)算子.其算法偽代碼如算法4所示.

算法4.基于靶向量的修復(fù)算子

輸入：稀疏翻轉(zhuǎn)后得到的Offspring,靶向量TV

輸出：修復(fù)后的Offspring

// 對全0列向量的修復(fù)

1.找到種群中全0列向量:

indec=find(sum(Offspring,1)==0);

2. 找到特征選擇個數(shù)最小的行:

mr=find(sum(Offspring,2)==min(sum(Offspring,2)));

3.Offspring(mr,indec)=1;

4.Offspring*(i,index)= 0;

// 對全0行向量的修復(fù)

5. 找到種群中全0行向量:

inder=find(sum(Offspring,2)==0);

6. 計(jì)算當(dāng)前平均特征選擇個數(shù)mFS=mean(Offspring,2);

7. [～,ind]=sort(TV);%對特征靶值排序

8.Offspring(inder,ind(1,1:mFS))=1;

對于種群中的全0列向量,取行向量值總和最小的行(即特征選擇個數(shù)最小的個體)將其變異為1;對于種群中行全為0的向量,根據(jù)當(dāng)前種群平均特征選擇個數(shù),將該行特征按靶值由低到高所在的位變異為1,因此修復(fù)后的后代解并不是隨機(jī)產(chǎn)生的,而是由當(dāng)前靶值較低(重要性較高)的特征組成的個體.

4 對比實(shí)驗(yàn)及結(jié)果分析

為了測試WF-MOFS算法的有效性,從策略有效性,參數(shù)對比,以及與當(dāng)前5種先進(jìn)的MOFS對比3個方面進(jìn)行實(shí)驗(yàn).所有對比實(shí)驗(yàn)均在MATLABR2020b運(yùn)行.為了保證實(shí)驗(yàn)結(jié)果的公平性及降低實(shí)驗(yàn)誤差,所有數(shù)據(jù)集按6∶2∶2的比例劃分訓(xùn)練集、測試集、驗(yàn)證集,每個數(shù)據(jù)集做交叉驗(yàn)證10次,將KNN(k=3)分類器性能作為評估指標(biāo),取各算法在各個數(shù)據(jù)集上10次實(shí)驗(yàn)的平均值和方差作為實(shí)驗(yàn)結(jié)果.

為了評估各算法尋找最優(yōu)解的能力,利用超體積(HV)指標(biāo)[16]評估在相同進(jìn)化代數(shù)下各算法獲得最優(yōu)解的質(zhì)量,計(jì)算如下:

(8)

其中,δ為Lebesgue測度,用來計(jì)算體積,|s|表示非支配解集的數(shù)目,vi表示參照點(diǎn)與解集中第i個解構(gòu)成的超體積.HV值越大,解集質(zhì)量越優(yōu),算法綜合性能越好,通常將參照點(diǎn)設(shè)置為(1,1).

為了進(jìn)一步評估各算法獲得的最優(yōu)特征子集的質(zhì)量,將各個最優(yōu)特征子集所構(gòu)建的KNN模型在驗(yàn)證集上進(jìn)行測試,評估模型誤差(error)和所選特征個數(shù)(nFS),兩者越小,代表該特征子集對原數(shù)據(jù)集的表征能力越強(qiáng),所構(gòu)建的學(xué)習(xí)模型的泛化能力越強(qiáng).

(9)

(10)

其中,T為分類正確的樣本個數(shù),即在驗(yàn)證集上預(yù)測標(biāo)簽與真實(shí)標(biāo)簽一致的樣本個數(shù),Nvalid_data為驗(yàn)證集中樣本總個數(shù).|X|為被選擇的特征數(shù)量,同公式(1),D為特征總數(shù).

選擇常用的15個數(shù)據(jù)集用于對比實(shí)驗(yàn),數(shù)據(jù)來源于http://www.keel.es/和kfst.uok.ac.ir.其中20-90維特征的數(shù)據(jù)集7個,100～2000維特征的數(shù)據(jù)集8個,所選數(shù)據(jù)集的其他參數(shù)見表1.

表1 15個常用數(shù)據(jù)集及其他參數(shù)Table 1 15 common datasets and other parameters

4.1 策略有效性驗(yàn)證實(shí)驗(yàn)

為了驗(yàn)證WF-MOFS算法提出的3個策略的有效性.在保留NSGA-II錦標(biāo)賽選擇和環(huán)境選擇方法(非支配排序和擁擠距離計(jì)算)的基礎(chǔ)上,依次使用“互信息初始化策略”,和“基于靶向量的稀疏翻轉(zhuǎn)及修復(fù)算子”替換“隨機(jī)初始化策略”和“一點(diǎn)交叉和按位變異”,并加入“靶向量更新策略”,在所有數(shù)據(jù)集上進(jìn)行對比實(shí)驗(yàn).設(shè)置種群個數(shù)100個,迭代100次,計(jì)算10次重復(fù)實(shí)驗(yàn)的HV均值和方差作為各算法優(yōu)化性能的評估結(jié)果.

圖3 依次使用3種改進(jìn)策略后HV均值變化圖Fig.3 Line chart of mean value of HV changes after using three advanced strategies

為了直觀顯示依次使用3種改進(jìn)策略后解集質(zhì)量的變化情況,圖3給出了HV均值變化折線圖,圖中數(shù)字為在同一數(shù)據(jù)集上各算法HV均值排名,其中,第1列為未使用新策略的NSGA-II算法,中間兩列為依次使用改進(jìn)策略后所形成的新算法,最后一列為提出的WF-MOFS算法.

從圖3可以看出,在大多數(shù)數(shù)據(jù)集上,使用新策略后算法的HV均值有逐漸提升趨勢.其中,使用互信息初始化策略替換隨機(jī)初始化策略后,在部分測試集上算法獲得的最優(yōu)解質(zhì)量明顯提升,這是因?yàn)樾滤惴ㄍㄟ^最大化互信息有目的的產(chǎn)生初始種群,相較于隨機(jī)初始化種群,通常初始種群的解集質(zhì)量更高,使后代種群在此基礎(chǔ)上向最優(yōu)解方向快速收斂.在互信息初始化策略的此基礎(chǔ)上,使用稀疏翻轉(zhuǎn)和修復(fù)算子與使用一點(diǎn)交叉和按位變異遺傳算子進(jìn)行對比,在超過半數(shù)的數(shù)據(jù)集上解集質(zhì)量有進(jìn)一步提升.這是因?yàn)橄∈璺D(zhuǎn)和修復(fù)算子使用初始靶向量指導(dǎo)后代解的生成,引導(dǎo)后代解朝著更優(yōu)解方向發(fā)展,并通過控制翻轉(zhuǎn)和變異數(shù)量保持子代的稀疏性,對于高維特征選擇問題能夠?qū)崿F(xiàn)對特征子集的快速降維.在前兩個改進(jìn)策略的基礎(chǔ)上,使用靶向量更新策略,形成WF-MOFS算法,與不使用更新策略的算法相比,解集質(zhì)量在超過半數(shù)數(shù)據(jù)集上得到明顯提升,分析其原因是更新策略在考慮特征的獨(dú)立統(tǒng)計(jì)特性的基礎(chǔ)上,進(jìn)一步基于模型評估考慮特征之間的交互作用,因此通常能夠產(chǎn)生更高質(zhì)量的組合方案解.

為了直觀顯示3種策略獲得的解集質(zhì)量情況,圖4給出了在MUSK1數(shù)據(jù)集上,使用3種改進(jìn)策略前后的實(shí)際運(yùn)行效果圖.由圖4(a)可以看出,采用隨機(jī)初始化策略產(chǎn)生的種群特征選擇比例集中在50%左右,即隨機(jī)種群的二元變量0,1分布較為均勻,而采用互信息初始化策略產(chǎn)生的種群已經(jīng)形成了較好的Pareto前沿面,這是由于在初始化過程中考慮了特征的統(tǒng)計(jì)特性,并且通過錦標(biāo)賽選擇和rand*D來控制特征組合數(shù)量,因此形成了不同特征數(shù)量的較優(yōu)組合方案解.在圖4(b)遺傳算子實(shí)際運(yùn)行效果圖中,稀疏翻轉(zhuǎn)&修復(fù)算子獲得的解在特征數(shù)量上優(yōu)化效果更好,這是因?yàn)樵撍阕釉诜D(zhuǎn)和變異過程中仍舊能保持子代的稀疏度.最后在圖4(c)中比較運(yùn)行第2代時有無更新策略的解集質(zhì)量,顯然采用更新策略的解集收斂效果更好,這是因?yàn)槌跏及邢蛄恐豢紤]了特征的獨(dú)立統(tǒng)計(jì)特性,而更新策略在此基礎(chǔ)上進(jìn)一步考慮特征交互特征并評估模型表現(xiàn),有利于引導(dǎo)算法找到適合當(dāng)前分類器的更優(yōu)組合方案解.

圖4 使用3種改進(jìn)策略前后算法實(shí)際運(yùn)行效果圖Fig.4 Actual running effect of the algorithm before and after using the three advanced strategies

4.2 參數(shù)對比實(shí)驗(yàn)

WF-MOFS算法只需要對靶向量的更新頻率Uf進(jìn)行參數(shù)設(shè)置,在本節(jié)對比了5種參數(shù)選擇方案,分別是Uf=1,2,5,10,20,即每隔Uf代對靶向量進(jìn)行更新.在種群個數(shù)100,進(jìn)化代數(shù)為100代情況下,在所有數(shù)據(jù)集上運(yùn)行10次,計(jì)算HV均值和方差來評估各參數(shù)設(shè)置下算法獲得的解集質(zhì)量.為了直觀對比5種參數(shù)設(shè)置下的解集質(zhì)量,圖5給出了HV均值折線圖及在各數(shù)據(jù)集上的HV均值排名.

圖5 不同靶向量更新頻率的HV均值變化圖Fig.5 Change diagram of HV mean value with different TV update frequency

從圖5可以看出,5種更新頻率的HV均值總體相差不大,因此WF-MOFS算法對更新頻率的敏感度相對較小.但是通過對HV均值排名的進(jìn)一步計(jì)算可得,Uf=1優(yōu)于Uf=2優(yōu)于Uf=5優(yōu)于Uf=10優(yōu)于Uf=20,即更新頻率較頻繁的解集質(zhì)量相對較優(yōu),分析其原因是因?yàn)楦骂l率較慢可能會導(dǎo)致特征交互信息反饋滯后,而更新相對頻繁能夠降低反饋滯后所帶來的影響,因此在5種參數(shù)設(shè)置中,更適合將WF-MOFS算法的更新頻率設(shè)置為Uf=1.

4.3 算法對比實(shí)驗(yàn)

在本節(jié),將WF-MOFS與5種先進(jìn)的多目標(biāo)特征選擇算法(CDMfsMI、PMMOEA、SparseEA、SM-MOEA、GR-MOEA)進(jìn)行對比.其中,CDMfsMI是經(jīng)典的基于濾波法的特征選擇算法,以特征信息熵和冗余度為優(yōu)化目標(biāo).而PMMOEA和SparseEA是最近提出的基于包裝法的多目標(biāo)特征選擇算法,在處理高維特征選擇問題時算法性能較突出,通常以評估模型性能和特征個數(shù)為優(yōu)化目標(biāo),但不考慮特征的統(tǒng)計(jì)特性.SM-MOEA和GR-MOEA是最近提出的融合濾波和包裝法的混合多目標(biāo)特征選擇算法,該類方法綜合考慮特征個體的統(tǒng)計(jì)特性和特征子集的模型表現(xiàn),并且利用多目標(biāo)優(yōu)化算法的全局搜索能力來尋找最優(yōu)特征子集.為了評估各算法尋找最優(yōu)解的能力及其最優(yōu)特征子集表征模型的泛化能力,分別計(jì)算各算法在相同迭代次數(shù)下在測試集上的HV均值,及其最優(yōu)子集在驗(yàn)證集上的分類誤差率.

由于CDMfsMI算法與其他5種對比算法的優(yōu)化目標(biāo)不同,導(dǎo)致其最優(yōu)解的收斂程度和收斂方向有所差異,因此CDMfsMI不能與其他算法在同一度量維度下對比HV值,則將WFMOFS算法與其他4個對比算法10次重復(fù)實(shí)驗(yàn)的HV均值及方差進(jìn)行對比,其結(jié)果如表2所示.

從表2可以看出,WF-MOFS算法的HV均值在超過半數(shù)(9/15)數(shù)據(jù)集上排名第一,表明WF-MOFS在相同迭代次數(shù)和種群規(guī)模設(shè)置下能夠逼近最優(yōu)解方向,所獲得的解集質(zhì)量更優(yōu).對排名值的進(jìn)一步計(jì)算可得,WF-MOFS總排名值為24,SMMOEA總排名值為56,GRMOEA總排名值為53,SparseEA總排名值為40,PMMOEA總排名值為52.從排名值知,基于包裝法的多目標(biāo)特征選擇方法(SparseEA和PMMOEA)略優(yōu)于混合多目標(biāo)特征選擇方法(SMMOEA和GRMOEA),在此基礎(chǔ)上結(jié)合兩者優(yōu)勢的WF-MOFS性能表現(xiàn)較突出.

表2 5種對比算法在測試集上的HV均值和方差Table 2 Mean and variance of HV values of the 5 comparison algorithms on test set

具體分析算法性能差異如下:SparseEA和GRMOEA雖然在搜索最優(yōu)解過程忽略了特征屬性,但是兩種算法通過改進(jìn)搜索機(jī)制上在尋找最優(yōu)解能力上明顯提高,其中,SparseEA提出基于適應(yīng)度值的稀疏優(yōu)化策略,在大規(guī)模優(yōu)化問題上能夠?qū)崿F(xiàn)決策變量的快速降維和提高局部搜索能力;PMMOEA采用頻繁模式挖掘發(fā)現(xiàn)最小和最大頻繁項(xiàng)集,最小項(xiàng)集保留了最優(yōu)解信息,并加強(qiáng)對最大項(xiàng)集的局部搜索,因此上述兩種方法是通過加強(qiáng)對決策變量的局部搜索,從而獲得最優(yōu)特征組合.SMMOEA和GRMOEA充分結(jié)合特征統(tǒng)計(jì)特性和多目標(biāo)全局搜索能力尋找最優(yōu)特征子集,其中,SMMOEA設(shè)計(jì)了轉(zhuǎn)向矩陣用來記錄特征個體屬性和種群屬性,但是當(dāng)本次迭代種群表現(xiàn)沒有提升時,算法將重新啟動搜索機(jī)制,并且算法在設(shè)計(jì)時缺乏環(huán)境選擇和精英保留機(jī)制,整體選擇壓力不強(qiáng).GRMOEA通過濾波和包裝兩個種群的信息交互搜索最優(yōu)解,兩個種群均采用NSGA-II算法迭代優(yōu)化,但是NSGA-II在并沒有設(shè)計(jì)有效的策略處理特征選擇問題,如圖4中第1列數(shù)據(jù),特別是對于高維特征選擇問題,由于缺乏大規(guī)模變量處理機(jī)制,在降低特征維度方面效果不明顯.如2.3節(jié)所述,雖然混合算法(SMMOEA和GRMOEA)考慮特征的統(tǒng)計(jì)特性在算法前期有利于生成高質(zhì)量種群,但是在算法后期生成最優(yōu)解能力和選擇壓力方面動力不足,因此仍需要高性能的搜索機(jī)制提高算法尋優(yōu)能力.WF-MOFS正是考慮上述算法的不足,提出靶向量引導(dǎo)機(jī)制和稀疏翻轉(zhuǎn)算子,綜合特征屬性和種群表現(xiàn)引導(dǎo)局部搜索,并采用稀疏策略加速進(jìn)化,因此在相同進(jìn)化代數(shù)下,WF-MOFS獲得的解集質(zhì)量優(yōu)于對比算法.

為了對比5種算法的求解效率,圖6給出了5種對比算法在D=44,256,856這3個不同維度數(shù)據(jù)集上HV指標(biāo)變化趨勢圖.GRMOEA在算法前期HV值提升相對較慢,分析原因是GRMOEA采用雙種群混合特征選擇方法,包裝種群通常能獲得比濾波種群模型精度更高的解,而濾波種群只對包裝種群起修復(fù)作用,兩個種群計(jì)算代價一致,但是發(fā)揮作用相差較大,因此進(jìn)化效率相對較低.相比GRMOEA,其他4種對比算法在進(jìn)化初期能夠達(dá)到較高的HV值,但是在35～55代左右的時候,HV值開始增長緩慢,而WFMOFS較其他幾種算法能夠在50代以后仍有較明顯的提升,這與靶向量引導(dǎo)稀疏翻轉(zhuǎn)&修復(fù)算子加強(qiáng)最優(yōu)特征子集的局部搜索有關(guān),因此WFMOFS在相同進(jìn)化代數(shù)下能夠獲得更高質(zhì)量解集.

為了進(jìn)一步對比各算法獲得的特征子集所構(gòu)建模型的泛化能力,統(tǒng)計(jì)各個算法10次對比實(shí)驗(yàn)中獲得的Pareto解集在驗(yàn)證集上的平均誤差率(error)和特征數(shù)(nFS),如表3所示.并用粗體表示出在各個驗(yàn)證集上最小誤差率,當(dāng)該算法同時獲得最小誤差率和最小特征個數(shù)時同樣用粗體表示.

表3 6種對比算法在驗(yàn)證集上的平均誤差率和特征選擇個數(shù)Table 3 Average error rate and the number of feature selection of the six comparison algorithms on the valid set

圖7 對比算法在10次重復(fù)實(shí)驗(yàn)中獲得的平均特征數(shù)(nFS)和平均誤差率(error rate)散點(diǎn)圖Fig.7 Scatter plots of the average nFS and error rate obtained by the comparison algorithms in 10 repeated experiments

由表3所示,GRMOEA獲得最優(yōu)解在更多驗(yàn)證集上取得了更小的平均誤差率,但是選擇的平均特征個數(shù)也明顯高于其他五種對比算法,這是因?yàn)樘卣鲾?shù)量與模型誤差是相互矛盾的優(yōu)化目標(biāo),因此優(yōu)化結(jié)果要在誤差率與特征數(shù)目上有所折衷.與其他算法相比,WF-MOFS在spectheart、hillvalley兩個數(shù)據(jù)集上同時獲得最小誤差率和最小特征子集,因此在這兩個數(shù)據(jù)集上WF-MOFS算法獲得的最優(yōu)特征子集完全優(yōu)于對比算法.并且WF-MOFS在所有數(shù)據(jù)集上比超過半數(shù)的對比算法,在選取更小數(shù)目特征子集的同時獲得更小的模型誤差率.為了更直觀顯示各算法10次對比實(shí)驗(yàn)獲得的最優(yōu)解集在驗(yàn)證集上的表現(xiàn),圖7繪制了各算法在10次重復(fù)實(shí)驗(yàn)中獲得的平均特征數(shù)和平均誤差率的散點(diǎn)圖.

從圖7可以看出,SMMOEA獲得的平均特征數(shù)在部分?jǐn)?shù)據(jù)集上明顯少于對于算法,但是平均誤差率也相對較高,這是因?yàn)镾MMOEA使用了降維算子,將轉(zhuǎn)向矩陣中特征值低于個體平均特征值的變量由1變?yōu)?,因此每組解中被選擇特征數(shù)量迅速減少,然后使用修復(fù)算子根據(jù)種群表現(xiàn)將個體中的變量由0轉(zhuǎn)向1,但是其結(jié)果仍舊保持了較低的特征維數(shù),但是由于特征數(shù)與誤差率的矛盾性,因此SMMOEA優(yōu)化獲得的特征子集誤差率較高.與其他5種算法相比,隨著數(shù)據(jù)集中待優(yōu)化的特征維度增加,CMDMIfs算法在降低特征冗余和模型誤差方面性能明顯下降,這是因?yàn)榛跒V波法的CMDMIfs算法在求解特征選擇問題時并沒有考慮模型性能,并且二進(jìn)制粒子群進(jìn)化機(jī)制在求解高維特征選擇問題時快速降維能力不足.從整體上看,WF-MOFS的平均特征數(shù)和平均誤差率在大多數(shù)數(shù)據(jù)集上更逼近最優(yōu)前沿,如圖7(e)、圖7(g)、圖7(h)和圖7(i),說明WF-MOFS算法獲得的最優(yōu)特征子集訓(xùn)練模型的泛化能力較好.

4.4 時間復(fù)雜度分析

WF-MOFS、SparseEA、GRMOEA的計(jì)算量主要由非支配排序決定,其時間復(fù)雜度為O(mN2),PMMOEA的計(jì)算量主要由模式挖掘操作決定,其時間復(fù)雜度為O(g×n×D2),SM-MOEA的計(jì)算量主要由轉(zhuǎn)向矩陣更新操作決定,其時間復(fù)雜度為O(DN2).其中,m為目標(biāo)維數(shù),N為種群個數(shù),g是模式挖掘迭代次數(shù),n是挖掘種群大小,D為決策變量大小.由于O(mN2)< O(DN2),且通常情況下,O(mN2)< O(g×n×D2).因此,WF-MOFS在時間復(fù)雜度上并不高于對比算法.

5 總結(jié)及展望

通過對WF-MOFS算法3個策略的有效性以及與5種先進(jìn)的多目標(biāo)特征選擇算法對比,結(jié)果表明了WF-MOFS的3個改進(jìn)策略有效性及在大多數(shù)特征選擇問題上的優(yōu)越性.并且WF-MOFS算法結(jié)合了濾波法和包裝法的多目標(biāo)特征選擇算法的優(yōu)勢,與單獨(dú)使用濾波法和包裝法相比,既考慮各個特征的獨(dú)立統(tǒng)計(jì)特性,同時通過模型性能評估,衡量特征間的交互特性,用于引導(dǎo)多目標(biāo)優(yōu)化算法實(shí)現(xiàn)有目的地進(jìn)化搜索;與現(xiàn)有混合多目標(biāo)特征選擇算法相比,在算法設(shè)計(jì)上,結(jié)合稀疏大規(guī)模優(yōu)化思想,提出了基于靶向量引導(dǎo)的稀疏翻轉(zhuǎn)&修復(fù)算子,保證子代個體的稀疏性,有利于實(shí)現(xiàn)對高維特征的快速降維和生成高質(zhì)量解集.為了降低靶向量的計(jì)算復(fù)雜度,WF-MOFS的靶向量更新策略是基于種群整體表現(xiàn)和特征選擇頻率對特征合作能力的綜合評估結(jié)果,并沒有考慮不同個體中不同特征的組合關(guān)系,因此如何設(shè)計(jì)更精準(zhǔn)的特征靶向量并降低計(jì)算復(fù)雜度之間仍是未來值得研究的課題.