李庚松, 劉 藝,*, 鄭奇斌, 秦 偉, 李紅梅, 任小廣, 宋明武

(1. 國(guó)防科技創(chuàng)新研究院, 北京 100071; 2. 軍事科學(xué)院, 北京 100091;3. 天津(濱海)人工智能創(chuàng)新中心, 天津 300457)

0 引 言

機(jī)器學(xué)習(xí)是數(shù)據(jù)分析和決策支撐的關(guān)鍵技術(shù),廣泛應(yīng)用于科研、工業(yè)等領(lǐng)域。然而,“沒(méi)有免費(fèi)午餐”定理表明,不存在一個(gè)適用于所有問(wèn)題的“最優(yōu)”算法[1]。因此,工程中常見(jiàn)的關(guān)鍵問(wèn)題是如何從大量可行算法中為給定任務(wù)選擇滿足需求的合適算法,即算法選擇問(wèn)題[2]。

算法選擇問(wèn)題可以通過(guò)人工方法或自動(dòng)方法解決。人工方法包括實(shí)驗(yàn)試錯(cuò)法和專家選擇法,實(shí)驗(yàn)試錯(cuò)法通過(guò)實(shí)驗(yàn)獲得候選算法的性能,根據(jù)應(yīng)用需求選擇合適的算法;專家選擇法依賴領(lǐng)域?qū)＜医?jīng)驗(yàn)進(jìn)行算法選擇。然而,實(shí)驗(yàn)試錯(cuò)法成本較高,專家選擇法基于專家的經(jīng)驗(yàn)知識(shí),存在人為偏差,難以實(shí)現(xiàn)大規(guī)模應(yīng)用。自動(dòng)方法利用問(wèn)題的抽象特征,通過(guò)設(shè)計(jì)模型實(shí)現(xiàn)算法選擇過(guò)程的自動(dòng)化,包括基于元學(xué)習(xí)的方法和基于協(xié)同過(guò)濾的方法[3-4]。其中,基于元學(xué)習(xí)的方法具有計(jì)算開(kāi)銷低和靈活度高等優(yōu)點(diǎn),在故障診斷、圖像分類、異常檢測(cè)等領(lǐng)域得到了廣泛應(yīng)用[5-7]。

基于元學(xué)習(xí)的方法主要包括提取元特征、測(cè)度候選算法性能、訓(xùn)練算法選擇模型等步驟,其中如何選擇元特征是方法的關(guān)鍵問(wèn)題。研究人員提出了多種元特征和元特征提取方法[8],在實(shí)際應(yīng)用中取得了一定的效果。文獻(xiàn)[9]在分類數(shù)據(jù)集上提取了27種元特征,應(yīng)用線性回歸(linear regression,LR)學(xué)習(xí)元特征與算法性能的映射關(guān)系,通過(guò)預(yù)測(cè)候選算法的性能選擇合適算法。文獻(xiàn)[10]在提取使用22種元特征的基礎(chǔ)上,采用隨機(jī)森林回歸(random forest regression,RFR)預(yù)測(cè)候選算法在新數(shù)據(jù)集上的性能。文獻(xiàn)[11]選用12種元特征,應(yīng)用支持向量回歸(support vector regression,SVR)選擇候選算法。文獻(xiàn)[12]提取22種元特征,采用隨機(jī)森林(random forest,RF)構(gòu)建元特征到最優(yōu)算法的映射模型。文獻(xiàn)[13]使用32種元特征,基于k最近鄰(k nearest neighbors,kNN)訓(xùn)練映射模型,為新數(shù)據(jù)集選擇最優(yōu)算法。盡管當(dāng)前方法能夠有效解決算法選擇問(wèn)題,但是元特征的選用仍存在一些缺點(diǎn):首先,多數(shù)研究采用固定的元特征,與問(wèn)題的耦合度較高,可擴(kuò)展性較弱;其次,現(xiàn)有的方法難以有效利用元特征的互補(bǔ)性。

蟻獅優(yōu)化(ant lion optimization,ALO)[14]算法是一種受自然界中蟻獅捕食螞蟻的行為機(jī)制啟發(fā)所提出的新型演化算法。相較于其他演化算法,ALO算法因其收斂速度快、參數(shù)設(shè)置少、尋優(yōu)性能強(qiáng)、易于理解和實(shí)現(xiàn)等優(yōu)點(diǎn)而備受青睞[15],被廣泛應(yīng)用于網(wǎng)絡(luò)傳輸、污水處理、醫(yī)學(xué)分析等諸多領(lǐng)域并取得了良好的效果[16-18]。

為了有效利用元特征,進(jìn)一步提升基于元學(xué)習(xí)算法選擇的性能,提出基于ALO的魯棒元特征選擇(robust meta-feature selection based on ALO,RMA)方法。采用魯棒初始化機(jī)制生成初始種群,增強(qiáng)所選元特征子集的魯棒性;在搜索個(gè)體解的過(guò)程中,使用動(dòng)態(tài)邊界策略增加種群多樣性;采用混沌映射變異策略,提升方法的全局搜索能力。以分類算法選擇為測(cè)試問(wèn)題,通過(guò)130個(gè)數(shù)據(jù)集、150種元特征、8種分類算法和5種性能指標(biāo)構(gòu)建元數(shù)據(jù)集,在此基礎(chǔ)上應(yīng)用RMA選擇互補(bǔ)性較強(qiáng)的元特征;分析混沌映射變異策略的參數(shù)敏感性,對(duì)采用的機(jī)制和策略效果進(jìn)行驗(yàn)證;使用準(zhǔn)確率、查準(zhǔn)率、查全率、F1分?jǐn)?shù)指標(biāo)對(duì)比評(píng)估方法的性能,驗(yàn)證RMA的有效性及優(yōu)越性。

1 相關(guān)概念

1.1 基于元學(xué)習(xí)的算法選擇

1.1.1 基于元學(xué)習(xí)的算法選擇框架

基于元學(xué)習(xí)算法選擇框架如圖1所示[19-20]。

框架的具體流程如下所述:首先提取歷史數(shù)據(jù)集的元特征,獲取各候選算法在歷史數(shù)據(jù)集上的算法性能;然后以元特征為屬性,以算法性能或最優(yōu)算法為標(biāo)簽構(gòu)建元數(shù)據(jù)集;最后,應(yīng)用元算法在元數(shù)據(jù)集上進(jìn)行訓(xùn)練,獲得元模型。

對(duì)于新數(shù)據(jù)集,提取其元特征作為元模型的輸入,元模型對(duì)最優(yōu)算法或各候選算法的性能進(jìn)行預(yù)測(cè),根據(jù)預(yù)測(cè)結(jié)果確定并輸出最優(yōu)算法。

1.1.2 元特征類型

根據(jù)反映數(shù)據(jù)集特性的不同,元特征可以分為4類:基于統(tǒng)計(jì)和信息論的元特征、基于模型的元特征、基于基準(zhǔn)的元特征和基于問(wèn)題復(fù)雜度的元特征。

基于統(tǒng)計(jì)和信息論的元特征采用統(tǒng)計(jì)學(xué)和信息論的方法抽取數(shù)據(jù)集的信息,從數(shù)據(jù)集、數(shù)值類型屬性和枚舉類型屬性等方面描述數(shù)據(jù)集特性[19],包括整體統(tǒng)計(jì)特征、屬性統(tǒng)計(jì)特征和屬性信息熵特征。該類型元特征應(yīng)用較為廣泛,提取過(guò)程較為簡(jiǎn)單,然而其難以較好地刻畫(huà)數(shù)據(jù)集特性。

基于模型的元特征將數(shù)據(jù)集映射為決策樹(shù)模型,使用模型的結(jié)構(gòu)信息作為元特征[20],能夠較好地反映數(shù)據(jù)集的整體特性,但提取成本高昂。

基于基準(zhǔn)的元特征將運(yùn)行快速且易于實(shí)現(xiàn)的算法,即基準(zhǔn)算法在數(shù)據(jù)集上的性能指標(biāo)值作為元特征[21]。該類型元特征的提取方法相對(duì)簡(jiǎn)單,能夠反映數(shù)據(jù)集對(duì)不同類型算法的偏好,然而其計(jì)算開(kāi)銷較高。

基于問(wèn)題復(fù)雜度的元特征從類重疊、類不平衡、數(shù)據(jù)稀疏度等方面對(duì)數(shù)據(jù)集的幾何復(fù)雜度進(jìn)行量化評(píng)估[22]。這一類型的元特征反映了求解問(wèn)題的困難程度,在研究中的應(yīng)用效果較好,但是其計(jì)算復(fù)雜度較大。

1.2 ALO算法

ALO算法采用隨機(jī)游走、輪盤(pán)賭和精英策略完成個(gè)體解的搜索更新,具體包含如下5個(gè)步驟:蟻獅隨機(jī)在解空間中布置陷阱,選擇其中適應(yīng)度最優(yōu)的個(gè)體為精英蟻獅;螞蟻根據(jù)蟻獅的適應(yīng)度通過(guò)輪盤(pán)賭選擇一個(gè)蟻獅,圍繞該蟻獅和精英蟻獅進(jìn)行隨機(jī)游走搜索較優(yōu)解;蟻獅逐漸縮小陷阱限制螞蟻的游走范圍;蟻獅捕食螞蟻并更新位置;蟻獅在新位置布置陷阱,更新精英蟻獅。

螞蟻隨機(jī)游走方法如下所示:

X(t)=
[0,cumsum(r(t1)),cumsum(r(t2)),…,cumsum(r(tT))]

(1)

式中:t為當(dāng)前迭代次數(shù);T為最大迭代次數(shù);X(t)表示隨機(jī)游走位置;cumsum(·)表示隨機(jī)游走步長(zhǎng)的累加和;r(·)為隨機(jī)游走步長(zhǎng)的生成函數(shù),其計(jì)算如下所示:

(2)

式中:rand表示位于(0,1)之間的隨機(jī)數(shù)。

在隨機(jī)游走過(guò)程中,螞蟻的游走范圍逐漸縮小,如下所示:

(3)

式中:c和d表示個(gè)體各維度值的上界和下界;ct和dt分別表示第t次迭代中螞蟻各維度值搜索范圍的上界和下界;I的計(jì)算如下所示:

(4)

式中:w的值取決于當(dāng)前迭代數(shù)t,t≤0.1T時(shí),w=0;t>0.1T時(shí),w=2;t>0.5T則w=3;t>0.75T則w=4;當(dāng)t>0.9T時(shí),w=5;當(dāng)t>0.95T時(shí),w=6,從而使得10w呈現(xiàn)分段指數(shù)遞增趨勢(shì)。

ALO是一種連續(xù)優(yōu)化算法,而元特征選擇是一種離散優(yōu)化問(wèn)題。為了應(yīng)用ALO算法進(jìn)行元特征選擇,將個(gè)體各維度值的搜索上界和下界設(shè)置為0和1,通過(guò)設(shè)置閾值使其離散化。具體地,ALO算法對(duì)種群進(jìn)行隨機(jī)初始化,如下所示:

Ai=rand

(5)

式中:Ai為個(gè)體第i維的編碼值,反映第i維元特征的選擇狀態(tài)。為了避免引入元特征的選擇概率偏差,本文設(shè)置元特征選擇閾值為0.5,當(dāng)Ai>0.5時(shí),表示選擇第i個(gè)元特征;當(dāng)Ai≤0.5時(shí),表示該元特征未被選擇。將元數(shù)據(jù)集輸入ALO算法后,其根據(jù)元特征數(shù)確定維度數(shù),生成初始個(gè)體;隨后迭代搜索算法選擇性能較優(yōu)的個(gè)體;在迭代終止時(shí),輸出精英蟻獅選擇的元特征子集及其算法選擇性能。

2 RMA方法

2.1 魯棒初始化機(jī)制

由于元數(shù)據(jù)集是對(duì)原始數(shù)據(jù)采樣構(gòu)成的數(shù)據(jù)集,存在一定的偏差,因此需要考慮元特征選擇的魯棒性,即在元數(shù)據(jù)集分布存在微小擾動(dòng)的情況下,能夠生成相同或相似的元特征子集。通過(guò)提升元特征選擇的魯棒性,選擇重要性較高的元特征,從而提高方法的泛化性能。

RMA通過(guò)使用不同數(shù)據(jù)抽樣策略和元特征排序方法獲得多樣化的元特征排序,然后集成各元特征排序生成魯棒元特征排序,并將其用于指導(dǎo)種群的初始化過(guò)程,從而提升所選元特征子集的魯棒性。

魯棒元特征排序的生成方法如圖2所示,從K折劃分法、自助法、隨機(jī)過(guò)采樣和隨機(jī)欠采樣4種方法中隨機(jī)選擇一種方法對(duì)元數(shù)據(jù)集進(jìn)行抽樣,生成抽樣樣本;在抽樣樣本上從F檢驗(yàn)法、卡方檢驗(yàn)法和信息增益法3種方法中隨機(jī)選擇一種方法對(duì)元特征的重要性進(jìn)行評(píng)估,根據(jù)評(píng)估得分對(duì)元特征進(jìn)行排序[23]。最后對(duì)多個(gè)元特征排序進(jìn)行集成,即對(duì)元特征在每個(gè)排序列表中的位置進(jìn)行記錄,采用位置的中值作為該元特征的最終位置(中值相同的元特征按照在元數(shù)據(jù)集中的出現(xiàn)順序進(jìn)行排序),得到魯棒元特征排序。

圖2 魯棒元特征排序生成方法Fig.2 Generation approach of robust meta-feature ranking

RMA首先對(duì)種群進(jìn)行隨機(jī)初始化,然后基于魯棒元特征排序,生成個(gè)體維度編碼值的縮放倍率,如下所示:

(6)

式中:Zi為個(gè)體第i維編碼值的縮放倍率;Ri為第i維元特征在魯棒元特征排序中的排序位置;l和u為縮放倍率的最小值和最大值;D為個(gè)體維度數(shù)。根據(jù)縮放倍率對(duì)個(gè)體維度值進(jìn)行更新,調(diào)整個(gè)體對(duì)元特征的選擇概率,如下所示:

(7)

本文設(shè)置式中的l位于(0,1),u位于(1,2)?？梢钥闯?當(dāng)?shù)趇維元特征位于魯棒元特征排序中靠前(或靠后)的排序位置時(shí),Ai被較大幅度地放大(或縮小);當(dāng)其位于中間排序位置時(shí),Ai的變化幅度較小。通過(guò)這種方式,使得重要性較高的元特征更容易被選擇,提升方法的泛化性能。

綜上,魯棒初始化機(jī)制如算法1所示。

算法 1 魯棒初始化機(jī)制偽代碼輸入: 劃分?jǐn)?shù)K,抽樣規(guī)模的最大值Sm和最小值Sn,抽樣次數(shù)Cb,Co,Cu。輸出: 魯棒初始化種群1. 開(kāi)始2. 將元數(shù)據(jù)集劃分為K份,對(duì)每份抽樣樣本隨機(jī)采用一種方法生成元特征排序;3. 根據(jù)Sm和Sn,對(duì)元數(shù)據(jù)集重復(fù)Cb次自助法抽樣,每個(gè)抽樣隨機(jī)選擇一種方法生成元特征排序;4. 對(duì)元數(shù)據(jù)集進(jìn)行隨機(jī)過(guò)采樣,隨機(jī)選擇一種方法在抽樣上生成元特征排序,重復(fù)該過(guò)程Co次;5. 對(duì)元數(shù)據(jù)集進(jìn)行隨機(jī)欠采樣,隨機(jī)選擇一種方法在抽樣上生成元特征排序,重復(fù)該過(guò)程Cu次;6. 對(duì)上述過(guò)程中生成的多個(gè)元特征排序,通過(guò)集成得到魯棒元特征排序;7. 對(duì)種群進(jìn)行隨機(jī)初始化;8. 利用魯棒元特征排序和式(6)生成縮放倍率,通過(guò)縮放倍率和式(7)對(duì)種群中的個(gè)體維度值進(jìn)行縮放更新,得到魯棒初始化種群;9. 結(jié)束

2.2 動(dòng)態(tài)邊界策略

ALO算法中每只螞蟻隨機(jī)游走的搜索邊界變化過(guò)程相同,導(dǎo)致種群多樣性較弱,為了增加方法的種群多樣性,提出動(dòng)態(tài)邊界策略,對(duì)式(3)進(jìn)行改進(jìn),如下所示:

(8)

從式(4)可以看出,隨著迭代次數(shù)增加,I值呈現(xiàn)分段遞增趨勢(shì),搜索邊界ct和dt與I值成反比,呈現(xiàn)分段遞減趨勢(shì);而在式(8)中,1/[1+e-(T/t-1)]在(0.5,1)隨著迭代次數(shù)增加呈現(xiàn)非線性遞減趨勢(shì),(2·rand-1)/2為位于(-0.5,0.5)的隨機(jī)值,使得{1/[1+e-(T/t-1)]+(2·rand-1)/2}在(0,1.5)呈現(xiàn)具備一定隨機(jī)性的非線性遞減趨勢(shì)。圖3給出了ALO算法與RMA隨機(jī)游走的搜索邊界變化過(guò)程。通過(guò)應(yīng)用動(dòng)態(tài)邊界策略,螞蟻保持搜索邊界變化的整體遞減趨勢(shì)不變,在此基礎(chǔ)上引入了一定的隨機(jī)性,擴(kuò)大了螞蟻個(gè)體間的差異,從而增加了RMA的種群多樣性。

圖3 搜索邊界變化過(guò)程Fig.3 Change process of search boundary

2.3 混沌映射變異策略

針對(duì)ALO算法易陷入局部最優(yōu)的問(wèn)題,RMA引入混沌映射變異操作,提升方法的全局尋優(yōu)能力。首先選擇變異蟻獅種群;然后通過(guò)精英蟻獅編碼值更新變異閾值向量;根據(jù)變異閾值向量對(duì)變異個(gè)體的維度值進(jìn)行離散化的變異轉(zhuǎn)換;最后通過(guò)混沌映射將離散化的維度值映射到連續(xù)域中,在保持變異效果的同時(shí)使得維度值的分布具有一定的隨機(jī)性,提高變異蟻獅的種群多樣性。具體流程如下所述。

根據(jù)變異種群比例p,從N個(gè)蟻獅中選擇M=N×p個(gè)適應(yīng)度值位于中間部分的蟻獅進(jìn)行變異,該部分蟻獅具有較好的尋優(yōu)潛力,通過(guò)變異操作能夠以較大概率產(chǎn)生更好的個(gè)體。變異種群選擇方法如圖4所示。

圖4 變異種群選擇方法Fig.4 Selection approach of mutation population

每次迭代更新精英蟻獅后,記錄其編碼值,利用歷史精英蟻獅和當(dāng)前精英蟻獅的編碼值更新變異閾值向量,如下所示:

(9)

(10)

(11)

上述過(guò)程中,變異蟻獅在向精英蟻獅靠攏的基礎(chǔ)上,改變了部分編碼值使得所選擇的元特征子集發(fā)生變化,從而擴(kuò)大個(gè)體的搜索范圍,提升方法的全局尋優(yōu)能力。

由于混沌映射能夠產(chǎn)生具有較好隨機(jī)性分布的值[24],這里利用Fuch混沌映射轉(zhuǎn)換編碼值,保留變異效果并使變異個(gè)體隨機(jī)分布在連續(xù)域的解空間,如下所示:

(12)

(13)

式中:xh不為0且h∈Z+。

完成上述變異和混沌映射操作后,將變異蟻獅加入到蟻獅種群,從中選擇適應(yīng)度值最優(yōu)的N個(gè)蟻獅構(gòu)成下次迭代的蟻獅種群。

2.4 方法整體描述

RMA的偽代碼如算法2所示。

算法 2 RMA偽代碼輸入: 元數(shù)據(jù)集、最大迭代次數(shù)T、種群個(gè)體數(shù)N、變異種群比例p輸出: 元特征子集及其算法選擇性能1. 開(kāi)始2. 根據(jù)元數(shù)據(jù)集的元特征數(shù)確定個(gè)體維度數(shù);3. 使用魯棒初始化機(jī)制初始化N個(gè)蟻獅和螞蟻,計(jì)算蟻獅的適應(yīng)度值并從中選擇最優(yōu)的個(gè)體作為精英蟻獅;4. while(未達(dá)到最大迭代次數(shù)T)5. for 螞蟻a=1:N6. 通過(guò)輪盤(pán)賭選擇一個(gè)蟻獅;7. 螞蟻根據(jù)式(8)圍繞選擇的蟻獅和精英蟻獅進(jìn)行動(dòng)態(tài)邊界策略的隨機(jī)游走,更新螞蟻的位置;8. 計(jì)算所有螞蟻的適應(yīng)度值,如果螞蟻的適應(yīng)度值優(yōu)于選擇的蟻獅,則將蟻獅的位置更新為螞蟻的位置;9. end for10. 根據(jù)p選擇變異種群,更新精英蟻獅并記錄其編碼值,通過(guò)式(9)更新變異閾值向量;11. 根據(jù)式(10)～式(13)對(duì)變異蟻獅進(jìn)行混沌映射變異操作后,將變異蟻獅加入至蟻獅種群,從中選出N個(gè)適應(yīng)度值最優(yōu)的蟻獅進(jìn)入下輪迭代;12.end13.輸出精英蟻獅選擇的元特征子集和算法選擇性能;14.結(jié)束

現(xiàn)對(duì)RMA的時(shí)間復(fù)雜度進(jìn)行分析:設(shè)元數(shù)據(jù)集含有Y個(gè)元特征,設(shè)方法的種群規(guī)模為N,最大迭代次數(shù)為T(mén),變異種群比例為p,3種元特征排序方法的時(shí)間復(fù)雜度均為O(Y),可得魯棒初始化機(jī)制的時(shí)間復(fù)雜度為O(Y×(K+Cb+Cu+Co));螞蟻隨機(jī)游走的時(shí)間復(fù)雜度為O(Y×T×N),混沌映射變異策略的時(shí)間復(fù)雜度為O(Y×T×N×p);綜上所述,可得出RMA方法整體的時(shí)間復(fù)雜度為O(Y×(K+Cb+Cu+Co+T×N×(1+p)))。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 數(shù)據(jù)集

由于分類算法應(yīng)用的廣泛性,通過(guò)分類算法選擇問(wèn)題進(jìn)行評(píng)估實(shí)驗(yàn)。為了綜合度量方法的性能,實(shí)驗(yàn)使用來(lái)自UCI[25]、KEEL[26]和StatLib[27]的130個(gè)分類數(shù)據(jù)集,這些數(shù)據(jù)集的數(shù)據(jù)來(lái)源領(lǐng)域各異,實(shí)例數(shù)從13到58 000不等,屬性數(shù)從1到1 558不等,具有一定的差異性,構(gòu)成多樣化的數(shù)據(jù)集,從而能夠有效評(píng)估方法的性能。實(shí)驗(yàn)數(shù)據(jù)集信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息Table 1 Information of experiment datasets

3.1.2 元特征

通過(guò)元特征提取工具M(jìn)FE[28]提取常用的150種分類數(shù)據(jù)集元特征,包括77種基于統(tǒng)計(jì)和信息論的元特征、24種基于模型的元特征、14種基于基準(zhǔn)的元特征和35種基于問(wèn)題復(fù)雜度的元特征。元特征信息如表2所示。

表2 元特征信息Table 2 Information of meta-features

3.1.3 候選分類算法

實(shí)驗(yàn)使用8種候選分類算法,包括kNN、RF、支持向量機(jī)(support vector machine,SVM)、邏輯回歸(logistic regression,LoR)、樸素貝葉斯(naive Bayes,NB)、線性判別分析(linear discriminant analysis,LDA)、ID3決策樹(shù)和多層感知機(jī)(multi-layer perceptron,MLP)。上述候選算法均使用sklearn[29]機(jī)器學(xué)習(xí)平臺(tái)中的默認(rèn)參數(shù)設(shè)置。

3.1.4 候選算法性能測(cè)度

使用準(zhǔn)確率、查準(zhǔn)率、查全率、F1分?jǐn)?shù)和ARR(adjusted ratio of ratios)[30]指標(biāo)多方面比較候選算法的性能。

二分類問(wèn)題包括4種分類結(jié)果:真正例(true positive,TP),表示正例被正確分類的數(shù)量;真反例(true negative,TN),表示反例被正確分類的數(shù)量;假正例(false positive,FP),表示反例被錯(cuò)誤分類的數(shù)量;假反例(false negative,FN),表示正例被錯(cuò)誤分類的數(shù)量。基于上述分類結(jié)果計(jì)算準(zhǔn)確率、查準(zhǔn)率、查全率和F1分?jǐn)?shù)指標(biāo)值,分別如下所示:

(14)

(15)

(16)

(17)

ARR綜合考慮算法的運(yùn)行時(shí)間和準(zhǔn)確率,其計(jì)算如下所示:

(18)

式中:ap和aq分別表示候選算法p和q;Acc和Rt表示算法在數(shù)據(jù)集上的準(zhǔn)確率和運(yùn)行時(shí)間;α為用于調(diào)整準(zhǔn)確率和運(yùn)行時(shí)間相對(duì)重要程度的可變參數(shù)。實(shí)驗(yàn)中ARR的α值取0.1、0.01和0.001,以獲得較為全面的算法性能比較結(jié)果。

通過(guò)5次10折交叉驗(yàn)證獲取候選算法在各數(shù)據(jù)集上的性能指標(biāo)值,對(duì)指標(biāo)值進(jìn)行比較從而確定數(shù)據(jù)集的最優(yōu)算法,將最優(yōu)算法作為標(biāo)簽與元特征結(jié)合,構(gòu)建相應(yīng)性能指標(biāo)的元數(shù)據(jù)集。采用DAcc、DPre、DRec和DF1分別表示通過(guò)準(zhǔn)確率、查準(zhǔn)率、查全率和F1分?jǐn)?shù)指標(biāo)構(gòu)建的元數(shù)據(jù)集;在ARR指標(biāo)上,使用DA1、DA2和DA3分別表示指標(biāo)的α參數(shù)值取0.1、0.01和0.001時(shí)生成的元數(shù)據(jù)集。值得注意的是,使用回歸元算法時(shí),需要為各候選算法構(gòu)建單獨(dú)的元數(shù)據(jù)集,訓(xùn)練元模型預(yù)測(cè)算法性能指標(biāo)值,比較各候選算法的預(yù)測(cè)指標(biāo)值進(jìn)而選擇最優(yōu)算法。

3.1.5 RMA設(shè)置

kNN參數(shù)較少且易于實(shí)現(xiàn),是應(yīng)用較為廣泛的元算法。本文以kNN為元算法,應(yīng)用RMA進(jìn)行元特征選擇,驗(yàn)證RMA的有效性。研究表明kNN的距離度量采用歐氏距離,k值取元數(shù)據(jù)集實(shí)例數(shù)的10%～15%時(shí),其表現(xiàn)更好[13,31]。經(jīng)過(guò)測(cè)試,本文設(shè)置k值為15,距離度量采用以距離倒數(shù)為權(quán)重的加權(quán)歐式距離,可獲得較優(yōu)性能。此外,設(shè)置RMA的種群個(gè)體數(shù)N=40、最大迭代次數(shù)T=300。

3.1.6 對(duì)比方法

采用的對(duì)比算法選擇方法包括kNN、RF、LR、基于包裹式元特征選擇方法的LR(LR based on wrapper method,LRW)[9]、SVR和RFR。其中,kNN的參數(shù)設(shè)置與第3.1.5節(jié)一致,其他方法均采用sklearn中的默認(rèn)參數(shù)設(shè)置。

3.2 元數(shù)據(jù)集分析

對(duì)構(gòu)建的7個(gè)元數(shù)據(jù)集進(jìn)行分析,候選算法在各元數(shù)據(jù)集中的勝出次數(shù)如表3所示。

表3 候選算法勝出次數(shù)Table 3 Win times of the candidate algorithms

從表3可以看出,RF候選算法僅在DA1元數(shù)據(jù)集中的勝出次數(shù)較少,可見(jiàn)其具有優(yōu)越的分類性能,但是運(yùn)行時(shí)間是其較為明顯的短板。與RF相對(duì)的是kNN和NB,得益于算法較快的運(yùn)行速度,其在ARR指標(biāo)上具備一定優(yōu)勢(shì),但其分類性能較差。因此,隨著α值的減小,運(yùn)行時(shí)間的重要性降低,兩種候選算法在ARR指標(biāo)元數(shù)據(jù)集中的勝出次數(shù)減少。相較于kNN和NB,LoR的分類性能略優(yōu)但時(shí)間開(kāi)銷更高,在7個(gè)指標(biāo)上的表現(xiàn)較為平庸。SVM的分類性能較優(yōu)且具有合適的時(shí)間開(kāi)銷,在7個(gè)指標(biāo)上均取得了較好結(jié)果。LDA和ID3展現(xiàn)了較好的分類性能,另一方面,兩種候選算法在ARR指標(biāo)的元數(shù)據(jù)集中也取得了較多次數(shù)的勝出,說(shuō)明其在運(yùn)行時(shí)間和準(zhǔn)確率兩方面較為均衡。MLP的分類性能具有一定優(yōu)勢(shì),但其在各數(shù)據(jù)集上的運(yùn)行時(shí)間較長(zhǎng),因此算法在ARR指標(biāo)的元數(shù)據(jù)集中取得的勝出次數(shù)較少。

3.3 參數(shù)敏感性分析

RMA的一個(gè)重要參數(shù)是變異種群比例p,本節(jié)通過(guò)對(duì)比實(shí)驗(yàn),分析方法對(duì)該參數(shù)的敏感性。研究人員通常更關(guān)注算法選擇方法能否正確預(yù)測(cè)最優(yōu)算法,即方法的準(zhǔn)確率,因此,使用準(zhǔn)確率作為性能指標(biāo),通過(guò)5次5折交叉驗(yàn)證計(jì)算指標(biāo)值。p值分別取5/6、4/5、3/4,2/3、1/2、1/3、1/4、1/5和1/6,其他參數(shù)與第3.1.5節(jié)保持一致,對(duì)方法獨(dú)立運(yùn)行20次的平均結(jié)果進(jìn)行比較,結(jié)果如表4所示。

表4 不同變異種群比例準(zhǔn)確率比較Table 4 Comparison of accuracy with different mutation population proportion %

從表4可以看出,變異種群比例對(duì)方法準(zhǔn)確率的影響呈現(xiàn)一定變化趨勢(shì)。以p值取1/2為對(duì)比,當(dāng)p值大于1/2時(shí),大部分蟻獅參與變異向精英蟻獅靠攏,使得蟻獅種群在解空間中的分布性降低,可能導(dǎo)致方法過(guò)早收斂,限制了方法的全局尋優(yōu)能力,降低了方法性能;當(dāng)p值小于1/2時(shí),少量的變異蟻獅難以充分發(fā)揮混沌映射變異策略的優(yōu)勢(shì),方法的泛化性能相對(duì)減弱。另一方面,當(dāng)p值分別取5/6、4/5、3/4、2/3、1/2、1/3、1/4、1/5和1/6時(shí),方法在測(cè)試環(huán)境的運(yùn)行時(shí)間分別為1 913 s、1 864 s、1 837 s、1 711 s、1 585 s、1 432 s、1 323 s、1 290 s和1 270 s。綜合準(zhǔn)確率和運(yùn)行時(shí)間結(jié)果,在上述取值中,p值取1/2或1/3時(shí)方法具有較優(yōu)的算法選擇性能和合適的時(shí)間開(kāi)銷。

3.4 機(jī)制和策略效果驗(yàn)證

為驗(yàn)證RMA中不同機(jī)制策略的應(yīng)用效果,將RMA與ALO算法進(jìn)行對(duì)比。兩種方法獨(dú)立運(yùn)行20次,通過(guò)5次5折交叉驗(yàn)證計(jì)算準(zhǔn)確率、查準(zhǔn)率、查全率和F1分?jǐn)?shù)指標(biāo)值,取運(yùn)行結(jié)果的均值進(jìn)行比較。其中,RMA的變異種群比例p取1/2,其他參數(shù)與第3.1.5節(jié)一致,ALO算法的參數(shù)設(shè)置與RMA相同。

圖5給出了RMA與ALO算法在各元數(shù)據(jù)集上性能指標(biāo)值隨迭代次數(shù)變化的比較結(jié)果。其中,R-Acc、R-Pre、R-Rec和R-F1表示RMA的準(zhǔn)確率、查準(zhǔn)率、查全率和F1性能指標(biāo)值;類似的,A-Acc、A-Pre、A-Rec和A-F1分別表示ALO算法的上述性能指標(biāo)值。

圖5 RMA與ALO算法在各元數(shù)據(jù)集上的性能比較結(jié)果Fig.5 Comparison results of performance between RMA and ALO algorithm on various meta-datasets

對(duì)比分析圖5中的迭代曲線可以發(fā)現(xiàn),使用魯棒初始化機(jī)制后,RMA初始化精英蟻獅的適應(yīng)度優(yōu)于ALO算法;在迭代前期,RMA的動(dòng)態(tài)邊界策略增加了方法種群多樣性,使其收斂速度略優(yōu)于ALO算法;在后期迭代中,ALO算法常陷入局部最優(yōu),而RMA的混沌映射變異策略提升了方法的全局搜索能力,使方法能夠跳出局部最優(yōu),發(fā)現(xiàn)比ALO算法更好的最優(yōu)解;迭代終止時(shí),與ALO算法相比,RMA可以產(chǎn)生適應(yīng)度值更優(yōu)的精英蟻獅,得到更好的元特征子集。

下面評(píng)估方法的運(yùn)行開(kāi)銷,以ALO算法的運(yùn)行時(shí)間作為基準(zhǔn),對(duì)RMA的運(yùn)行時(shí)間進(jìn)行歸一化處理,結(jié)果如表5所示。

表5 RMA和ALO算法的相對(duì)運(yùn)行時(shí)間Table 5 Relative running time of RMA and ALO algorithm

從表5中可以看出,在機(jī)制和策略的影響下,運(yùn)行RMA的開(kāi)銷更高,但是最高僅增加了51%的運(yùn)行時(shí)間。根據(jù)第2.4節(jié)對(duì)RMA時(shí)間復(fù)雜度的分析,其計(jì)算開(kāi)銷相對(duì)于ALO算法增加的主要原因在于執(zhí)行了混沌映射變異策略,這也是下一步可以深入優(yōu)化的部分。

綜上,RMA具備更強(qiáng)的探索全局最優(yōu)解的能力,同時(shí)具有合適的計(jì)算開(kāi)銷,說(shuō)明所提出的機(jī)制和策略能有效增強(qiáng)方法的尋優(yōu)性能。

3.5 實(shí)驗(yàn)結(jié)果分析

下面通過(guò)實(shí)驗(yàn)對(duì)比評(píng)估RMA的性能。使用準(zhǔn)確率、查準(zhǔn)率、查全率和F1分?jǐn)?shù)指標(biāo),通過(guò)5次5折交叉驗(yàn)證計(jì)算RMA和對(duì)比方法的性能指標(biāo)值,實(shí)驗(yàn)中RMA的變異種群比例p取1/2,其他參數(shù)不變,取方法獨(dú)立運(yùn)行20次的平均結(jié)果進(jìn)行比較。表6～表9展示了各方法在4種性能指標(biāo)上的比較結(jié)果。

表6 準(zhǔn)確率比較Table 6 Comparison results of accuracy %

分析表6內(nèi)容發(fā)現(xiàn),在各元數(shù)據(jù)集上,RMA相較于kNN平均提升了15.6%的準(zhǔn)確率,與準(zhǔn)確率較高的RF相比,RMA具有6.2%的平均性能優(yōu)勢(shì),說(shuō)明RMA具備一定的有效性。

觀察表7查準(zhǔn)率,在除RMA以外的方法中,RF在7個(gè)元數(shù)據(jù)集上均取得了較好表現(xiàn)。RMA在各元數(shù)據(jù)集上的查準(zhǔn)率性能均明顯優(yōu)于RF,達(dá)到9.4%的平均性能差距,與kNN相比平均提升了19.7%的查準(zhǔn)率,驗(yàn)證了RMA對(duì)查準(zhǔn)率指標(biāo)的良好應(yīng)用效果。

表7 查準(zhǔn)率比較Table 7 Comparison results of precision %

表8中,RMA在各元數(shù)據(jù)集上的查全率性能差異較小,較為穩(wěn)定,其相較于表現(xiàn)較好的RF有著7.8%的平均性能優(yōu)勢(shì),相較于kNN則平均提升了15.1%的查全率,證明了RMA在查全率指標(biāo)上的有效性。

表8 查全率比較Table 8 Comparison results of recall %

對(duì)表9進(jìn)行分析,RMA與kNN相比平均提升了15.2%的F1分?jǐn)?shù),與RF相比平均領(lǐng)先了8.0%的性能,在7個(gè)元數(shù)據(jù)集上均取得了最優(yōu)結(jié)果,證明了RMA在F1分?jǐn)?shù)指標(biāo)上的優(yōu)越性能。

表9 F1分?jǐn)?shù)比較Table 9 Comparison results of F1 score %

另外值得注意的是,對(duì)于查準(zhǔn)率、查全率和F1分?jǐn)?shù)指標(biāo),LRW在各元數(shù)據(jù)集上的平均性能優(yōu)于LR;而對(duì)于準(zhǔn)確率指標(biāo),LRW的平均性能劣于LR?？梢?jiàn)LRW使用的包裹式元特征選擇方法應(yīng)用效果較弱,其原因在于,該方法的優(yōu)化目標(biāo)為降低對(duì)算法性能的預(yù)測(cè)誤差,與算法選擇目標(biāo)之間存在一定偏差。

綜上所述,使用全部150種元特征時(shí),kNN的性能較低,而通過(guò)RMA進(jìn)行元特征選擇后,其在不同指標(biāo)上均取得了較大的性能提升,在各元數(shù)據(jù)集上獲得了最好的性能評(píng)估結(jié)果,證明了RMA的有效性和優(yōu)越性。

4 結(jié) 論

為提升基于元學(xué)習(xí)的算法選擇性能,提出基于ALO算法的RMA方法。采用魯棒初始化機(jī)制進(jìn)行種群初始化,增強(qiáng)所選元特征子集的魯棒性;使用動(dòng)態(tài)邊界策略,增加種群多樣性;通過(guò)混沌映射變異策略,提升方法的尋優(yōu)性能。結(jié)果顯示,在測(cè)試環(huán)境下,應(yīng)用RMA進(jìn)行元特征選擇后,性能在準(zhǔn)確率指標(biāo)上平均提升了15.6%,在查準(zhǔn)率指標(biāo)上平均提升了19.7%,在查全率指標(biāo)上平均提升了15.1%,在F1分?jǐn)?shù)指標(biāo)上平均提升了15.2%,優(yōu)于其他對(duì)比方法,證明了RMA的有效性和優(yōu)越性。

在后續(xù)研究中,將通過(guò)并行計(jì)算方法,降低RMA的運(yùn)行時(shí)間。另一方面,將增加候選算法和實(shí)驗(yàn)數(shù)據(jù)集,進(jìn)一步擴(kuò)充元數(shù)據(jù)集,提升方法的可擴(kuò)展性,滿足更復(fù)雜的算法選擇需求。