面向算法選擇的元學(xué)習(xí)研究綜述

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

1.國防科技創(chuàng)新研究院，北京100071

2.軍事科學(xué)院，北京100091

3.天津（濱海）人工智能創(chuàng)新中心，天津300457

人工智能是數(shù)據(jù)處理與分析的重要技術(shù)，為人們利用數(shù)據(jù)進行決策和研究提供了有力支撐。在人工智能的不同領(lǐng)域中，研究人員提出了大量算法，然而，不同算法在有限數(shù)量的問題上具備優(yōu)越性能，不存在一個適用于所有問題的可行算法，該現(xiàn)象被稱為算法的性能互補性（performance complementarity）現(xiàn)象[1]，與“沒有免費午餐”（no free lunch）定理相印證[2]。算法的性能互補性現(xiàn)象普遍存在于不同領(lǐng)域，如何為給定問題從大量可行算法中選擇滿足應(yīng)用需求的算法成為了各領(lǐng)域面臨的重要挑戰(zhàn)，即算法選擇問題（algorithm selection problem）[3]。算法選擇問題通常采用人工選擇或自動選擇的方法解決。人工選擇方法通過實驗試錯或依賴專家選擇合適的算法，然而實驗試錯方法成本較高，專家選擇與專家的經(jīng)驗知識相關(guān)且靈活性較低[4]。自動選擇方法通過設(shè)計算法和模型，根據(jù)問題的特點自動選擇滿足應(yīng)用需求的算法，包括活躍測試（active test）方法、推薦系統(tǒng)方法以及基于元學(xué)習(xí)（meta-learning）的方法[5-7]。其中基于元學(xué)習(xí)的方法研究基礎(chǔ)較為深厚，具備開銷低和靈活度高等優(yōu)點，成為了解決算法選擇問題的主要方法[8-9]。

本文對基于元學(xué)習(xí)的算法選擇進行綜述總結(jié)，為研究人員了解相關(guān)領(lǐng)域的發(fā)展現(xiàn)狀提供參考。

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

本章介紹算法選擇模型的概念，給出基于元學(xué)習(xí)的算法選擇框架，詳細說明框架的組成部分和一般流程，概括相關(guān)的綜述工作。

1.1 算法選擇模型

圖1 給出了算法選擇的抽象模型[10]，模型包含四部分：（1）問題空間P，表示問題實例集合；（2）特征空間F，表示問題實例的可測度特征集合；（3）算法空間A，表示適用于所有問題實例的候選算法集合；（4）性能空間Y，表示對于給定的性能指標(biāo)m，A中每個算法的性能集合。模型的具體流程為：對于具有特征f(x)∈F的問題實例x，找到一個到算法空間A的選擇映射S(f(x))，使得所選算法α∈A在性能指標(biāo)m上最大化性能映射y(α(x),m)∈Y。

圖1 算法選擇抽象模型Fig.1 Algorithm selection abstract model

元學(xué)習(xí)即“學(xué)會學(xué)習(xí)的學(xué)習(xí)”，它利用歷史學(xué)習(xí)經(jīng)驗進行學(xué)習(xí)，以達到適應(yīng)新任務(wù)的目標(biāo)[11]。元學(xué)習(xí)將算法選擇問題視為常規(guī)的機器學(xué)習(xí)問題，通過機器學(xué)習(xí)算法構(gòu)建問題特征與候選算法性能之間的映射關(guān)系[12]。在問題特征提取和映射構(gòu)建等方面，基于元學(xué)習(xí)的算法選擇已經(jīng)形成了較為成熟的方法理論，是目前各學(xué)科領(lǐng)域中算法選擇研究的熱點方向[13-15]。

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

在算法選擇模型的基礎(chǔ)上，基于元學(xué)習(xí)的算法選擇一般框架如圖2 所示[4,16]?？蚣馨ㄔ獢?shù)據(jù)集（meta-dataset）構(gòu)建和元模型（meta-model）訓(xùn)練兩個主要階段。元數(shù)據(jù)集構(gòu)建階段首先獲取元知識（metaknowledge），包括元特征（meta-feature），即歷史數(shù)據(jù)集可測度特征和候選算法在歷史數(shù)據(jù)集上的性能；然后將算法選擇問題轉(zhuǎn)換為監(jiān)督學(xué)習(xí)問題，結(jié)合元目標(biāo)（meta-target），即算法選擇目標(biāo)，利用元知識構(gòu)建元實例（meta-example）形成元數(shù)據(jù)集。具體地，元實例的屬性為元特征，元實例的標(biāo)簽根據(jù)元目標(biāo)和候選算法性能確定。元模型訓(xùn)練階段應(yīng)用元算法（meta-learner），即相應(yīng)的監(jiān)督學(xué)習(xí)算法，在元數(shù)據(jù)集上訓(xùn)練得到元模型。

圖2 基于元學(xué)習(xí)的算法選擇框架Fig.2 Framework of algorithm selection based on meta-learning

對新數(shù)據(jù)集提取其元特征后，將元特征輸入至已訓(xùn)練好的元模型，元模型根據(jù)給定的元目標(biāo)預(yù)測并輸出新數(shù)據(jù)集的合適算法。

元目標(biāo)包括最優(yōu)算法、算法排序和算法集合三種形式。最優(yōu)算法和算法排序根據(jù)候選算法的性能指標(biāo)值確定，其中算法排序分為全排序和部分排序，部分排序即全排序中前k個（top-k）性能最優(yōu)的算法。算法集合則應(yīng)用統(tǒng)計顯著性檢驗方法確定，具體而言，檢驗其他候選算法與最優(yōu)候選算法的性能差異顯著性，將其中不存在顯著性能差異的算法和最優(yōu)算法視為合適算法構(gòu)造算法集合[17]。

對于已訓(xùn)練好的元模型，通過元模型性能指標(biāo)，計算給定元目標(biāo)下歷史數(shù)據(jù)集的歷史算法信息與元模型預(yù)測算法結(jié)果的差異，即歷史最優(yōu)算法與預(yù)測最優(yōu)算法、歷史算法排序與預(yù)測算法排序、歷史算法集合與預(yù)測算法集合之間的偏差，從而量化元模型的性能，檢驗算法選擇方法的有效性。

1.3 相關(guān)工作

多年來，基于元學(xué)習(xí)的算法選擇研究形成了豐富的文獻，在此基礎(chǔ)上，一些研究人員對其進行了綜述總結(jié)。文獻[10]首先介紹基于元學(xué)習(xí)的方法在分類算法選擇中的發(fā)展成果，然后概述方法在諸如回歸、優(yōu)化等其他學(xué)科領(lǐng)域的拓展研究，并對方法跨學(xué)科應(yīng)用的局限性和可行性進行了總結(jié)分析。文獻[16]提出一個多學(xué)科通用的基于元學(xué)習(xí)算法選擇框架，對元特征和元算法進行分類概述，最后從框架內(nèi)容、學(xué)科領(lǐng)域等方面總結(jié)了問題與發(fā)展方向。文獻[18]歸納整合元學(xué)習(xí)的不同定義，分析并指出元學(xué)習(xí)與算法選擇的深刻聯(lián)系，為基于元學(xué)習(xí)的算法選擇方法提供了一定的理論依據(jù)。文獻[19]簡述元學(xué)習(xí)相關(guān)概念的發(fā)展歷程，重點介紹了基于元學(xué)習(xí)算法選擇方法在工作流設(shè)計和改進措施方面的發(fā)展，以及其在不同學(xué)科領(lǐng)域中的研究趨勢。文獻[4]提出基于元學(xué)習(xí)的分類算法選擇框架，對相關(guān)的元特征和元算法進行分類綜述，并通過實驗對比不同類型元特征和元算法的應(yīng)用效果。

區(qū)別于上述綜述工作，本文總結(jié)近年基于元學(xué)習(xí)的算法選擇研究，在對元特征和元算法進行分類的基礎(chǔ)上，從不同角度分析并詳細說明各類型方法的特性和優(yōu)缺點；考慮算法選擇方法的性能測度，對元模型性能指標(biāo)進行分類描述，并對比不同指標(biāo)的優(yōu)缺點；以學(xué)習(xí)任務(wù)為出發(fā)點，歸納介紹方法的應(yīng)用情況；通過實驗定量分析不同類型元算法的優(yōu)劣勢與適用性；總結(jié)方法的現(xiàn)有問題和發(fā)展趨勢，為后續(xù)研究提供參考。

2 基于元學(xué)習(xí)的算法選擇研究進展

在基于元學(xué)習(xí)的算法選擇方法中，元特征和元算法是影響方法性能的關(guān)鍵因素，而元模型的性能評估則是方法改進優(yōu)化的重要參考。隨著研究的深入，上述內(nèi)容取得了一定的發(fā)展成果，出現(xiàn)了不同類型的方法。根據(jù)反映數(shù)據(jù)集特性的不同，可以將元特征分為基于統(tǒng)計和信息論、基于模型、基于基準和基于問題復(fù)雜度的方法；按照技術(shù)特點的不同，元算法可以分為基于規(guī)則、基于距離、基于回歸和基于集成學(xué)習(xí)的方法；根據(jù)元目標(biāo)的不同，可以將元模型性能指標(biāo)分為基于最優(yōu)算法、基于算法排序和基于算法集合的指標(biāo)，如圖3 所示。

圖3 基于元學(xué)習(xí)的算法選擇研究內(nèi)容與方法Fig.3 Research contents and methods of algorithm selection based on meta-learning

本章圍繞元特征、元算法和元模型性能指標(biāo)展開分析，分類并總結(jié)不同方法的優(yōu)缺點。

2.1 元特征的研究進展

合適的元特征能充分反映數(shù)據(jù)集偏差，使元特征與算法性能的映射關(guān)系更精確，從而提升算法選擇方法的性能，因此，如何提取并使用具備較強偏差反映能力的元特征成為了算法選擇研究的主要問題。

分類算法選擇是研究較為深入的領(lǐng)域，研究人員提出了多種分類問題元特征，其元特征提取思路和方法也被廣泛借鑒和應(yīng)用于其他學(xué)科的算法選擇研究。本節(jié)以分類問題元特征為主，根據(jù)反映數(shù)據(jù)集特性和提取方法的不同，將元特征歸納為四類，分別是基于統(tǒng)計和信息論的元特征（statistical and information-theoretical based meta-features）、基于模型的元特征（model based meta-features）、基于基準的元特征（landmarking based meta-features）和基于問題復(fù)雜度的元特征（problem complexity based metafeatures），如表1 所示。

表1 元特征分類Table 1 Classification of meta-features

2.1.1 基于統(tǒng)計和信息論的元特征

基于統(tǒng)計的元特征和基于信息論的元特征是發(fā)展較為深入、應(yīng)用較為廣泛的元特征，在研究中常被合并使用，稱為基于統(tǒng)計和信息論的元特征。統(tǒng)計特征包括數(shù)據(jù)集的整體統(tǒng)計特征和屬性統(tǒng)計特征：整體統(tǒng)計特征包含數(shù)據(jù)集實例、屬性以及類的統(tǒng)計信息，如數(shù)據(jù)集實例個數(shù)、屬性個數(shù)、含缺失值屬性個數(shù)等。屬性統(tǒng)計特征反映數(shù)據(jù)集數(shù)值類型屬性的中心趨勢和離散程度[20]，如屬性的均值、方差、偏斜度（skewness）、峰度（kurtosis）等，偏斜度和峰度反映屬性值分布的不對稱情況和陡峭程度，其計算分別如式（1）和式（2）所示：

其中，n表示數(shù)據(jù)集的實例數(shù)，xi表示第i個實例的屬性值，xˉ表示屬性均值?；谛畔⒄摰脑卣饔嬎銛?shù)據(jù)集枚舉類型屬性的熵、互信息、噪聲率（noise signal ratio，NSR）等[21]，反映屬性的一致性和屬性間的相關(guān)性，NSR 的計算如式（3）所示：

其中，(A)表示屬性熵的均值，(C,A)表示互信息的均值，噪聲率反映了分類數(shù)據(jù)集中冗余信息的比例，其值越小數(shù)據(jù)集越容易分類。值得注意的是，研究中常用均值或標(biāo)準差對各屬性的特征信息進行歸納，得到各屬性峰度的均值、各屬性熵的標(biāo)準差等作為元特征。

大型分類算法比較項目STATLOG[22]首次使用了16 個基于統(tǒng)計的元特征描述分類數(shù)據(jù)集。在STATLOG 項目的基礎(chǔ)上，研究人員引入基于信息論的元特征[21]，擴展使用分類數(shù)據(jù)集中含缺失值屬性、含異常值屬性（異常值指屬性的錯誤或不合理值）、屬性分布頻率、數(shù)據(jù)集主成分屬性等的統(tǒng)計特征，擴充了元特征數(shù)量[23-25]。該類型元特征后續(xù)被廣泛應(yīng)用于其他學(xué)科的算法選擇研究中，取得了較好的效果[26-28]。

2.1.2 基于模型的元特征

基于模型的元特征將數(shù)據(jù)集映射在不同結(jié)構(gòu)的模型中，如決策樹模型、圖模型、聚類簇模型等，然后提取模型的結(jié)構(gòu)屬性作為元特征。

文獻[29]總結(jié)了基于決策樹模型的分類數(shù)據(jù)集元特征，該方法首先使用決策樹算法在數(shù)據(jù)集上訓(xùn)練得到?jīng)Q策樹模型，然后計算決策樹的節(jié)點數(shù)、最大路徑長度、劃分屬性出現(xiàn)次數(shù)標(biāo)準差等作為元特征，反映數(shù)據(jù)集的整體特性。決策樹模型中，決策樹節(jié)點是數(shù)據(jù)集實例的集合，從包含全部實例的根節(jié)點開始，模型通過若干個分支節(jié)點評估數(shù)據(jù)集屬性對類別的判別能力，選擇判別能力較強者作為節(jié)點劃分屬性將節(jié)點實例集合劃分到子節(jié)點，逐次劃分直到葉節(jié)點完成分類決策，這樣從根節(jié)點到葉節(jié)點的劃分過程稱為決策樹路徑。值得一提的是，該方法可使用不同算法生成決策樹模型，所提取元特征的具體值也會隨之變化。

文獻[30]將數(shù)據(jù)集實例視為頂點，測度頂點之間的距離，使用邊連接距離小于給定閾值的頂點，通過頂點的連接路徑表示實例間的關(guān)系，使數(shù)據(jù)集映射為圖模型，并以頂點、邊、路徑等的統(tǒng)計信息作為元特征，如頂點數(shù)、邊數(shù)、最大路徑長度等。

文獻[31]首先使用基于貪心的聚類算法得到一個聚類簇集合，該集合中的聚類簇只包含同類別數(shù)據(jù)集實例且聚類簇之間互不相交，之后提取聚類簇的統(tǒng)計信息作為元特征，如聚類簇個數(shù)等。

2.1.3 基于基準的元特征

基于基準的元特征使用算法的性能指標(biāo)值作為元特征。文獻[32]提出以基準算法（實現(xiàn)簡單且運行快速的分類算法）在數(shù)據(jù)集上的性能作為分類數(shù)據(jù)集元特征。其基本思想是：對于給定問題，候選算法與最優(yōu)基準算法的學(xué)習(xí)偏差相近，則該候選算法更可能具備優(yōu)越性能?；鶞仕惴☉?yīng)具備較低的計算成本和相異的學(xué)習(xí)偏差，因此，分類算法選擇的研究中常用決策樹樁（只有一個劃分屬性的決策樹）、1-最近鄰（1-nearest neighbor，1-NN）、樸素貝葉斯（naive Bayes，NB）、線性判別分析（linear discriminant analysis，LDA）等基準算法。

在基準算法的啟發(fā)下，文獻[33]提出以候選算法在原始數(shù)據(jù)集采樣上的性能作為元特征，稱為采樣基準元特征。在此基礎(chǔ)上，文獻[34]以候選算法在原始數(shù)據(jù)集采樣上的性能學(xué)習(xí)曲線為元特征，該性能學(xué)習(xí)曲線是采樣規(guī)模以幾何級數(shù)遞增，算法性能隨采樣規(guī)模變化的曲線，由向量(ai,1,ai,2,…,ai,z)表示，其中ai,m表示候選算法a在第i個數(shù)據(jù)集的第m個采樣上的性能。

針對聚類問題，文獻[35]隨機采樣原始聚類數(shù)據(jù)集10%的實例形成子集，在該子集上應(yīng)用DBSCAN（density-based spatial clustering of applications with noise）算法進行聚類，然后將聚類結(jié)果用作子集實例的標(biāo)簽，使其轉(zhuǎn)換為分類數(shù)據(jù)集，最后計算基準算法在該分類數(shù)據(jù)集上的準確率（accuracy，Acc）作為元特征。

2.1.4 基于問題復(fù)雜度的元特征

基于問題復(fù)雜度的元特征是對數(shù)據(jù)集幾何復(fù)雜度進行評估得到的元特征。根據(jù)提取方法的角度不同，可以將基于問題復(fù)雜度的元特征分為基于屬性方法、基于線性可分性（linear separability）方法、基于距離方法、基于稀疏度方法和基于類不平衡（class imbalance）方法[36]。

基于屬性方法通過數(shù)據(jù)集屬性評估數(shù)據(jù)集的類重疊（class overlapping）程度（類重疊指不同類別的實例在某些屬性上的值相近似），可計算得到最大費舍爾判別率（maximum Fisher discriminant ratio，MFDR）、重疊區(qū)間積（volume of overlapping region）等元特征。MFDR 是研究中常用的元特征，其計算各數(shù)值類型屬性的費舍爾判別率（Fisher discriminant ratio，F(xiàn)DR），然后選擇其中最大的FDR 值作為元特征，F(xiàn)DR 的計算如式（4）所示：

其中，k表示數(shù)據(jù)集類別的總數(shù)，pci表示第i類的實例比例，類別越平衡的數(shù)據(jù)集，NCE 值越大，當(dāng)所有類別的實例數(shù)相等時，得到其最大值為1。

文獻[37]通過數(shù)據(jù)集屬性與標(biāo)簽的關(guān)聯(lián)度、線性擬合度和實例的空間分布情況對回歸問題的復(fù)雜度進行評估，得到回歸問題的復(fù)雜度元特征。

針對聚類問題，文獻[38]使用了基于距離的元特征，即計算數(shù)據(jù)集實例間的歐式距離，以距離的均值、峰度、偏斜度等統(tǒng)計信息作為元特征。

總結(jié)相關(guān)研究，可以發(fā)現(xiàn)元特征的3 個主要關(guān)注點：（1）充分反映數(shù)據(jù)集偏差；（2）充分體現(xiàn)不同算法的學(xué)習(xí)偏差，反映算法性能互補性；（3）降低元特征計算成本和獲取難度。

基于統(tǒng)計和信息論的元特征在提取方法上易于理解和實現(xiàn)，然而其偏差反映能力較弱，研究中通常選取少數(shù)該類型元特征作為其他元特征的補充?；谀Ｐ偷脑卣魈崛》椒ㄏ喈?dāng)于進行2 次特征提取，其首先通過算法訓(xùn)練模型提煉數(shù)據(jù)集的關(guān)鍵結(jié)構(gòu)，在此基礎(chǔ)上使用統(tǒng)計方法提取得到元特征，能夠較好地反映數(shù)據(jù)集偏差?；诨鶞实脑卣魇箶?shù)據(jù)集被映射在基準算法及其性能指標(biāo)值所構(gòu)成的空間中，量化數(shù)據(jù)集對不同算法的偏好程度，體現(xiàn)算法的學(xué)習(xí)偏差，應(yīng)用效果較好?；趩栴}復(fù)雜度的元特征反映數(shù)據(jù)集的數(shù)據(jù)質(zhì)量和解決問題的困難程度，這兩方面與候選算法在數(shù)據(jù)集上的性能緊密關(guān)聯(lián)，使該類元特征具備較強的偏差反映能力。

從計算復(fù)雜程度、提取方法的可擴展性和偏差因素三方面對不同類型的元特征進行對比分析，結(jié)果如表2 所示。

表2 元特征對比Table 2 Comparison of meta-features

基于統(tǒng)計和信息論的元特征計算簡單且成本較低，但其度量數(shù)據(jù)集屬性的統(tǒng)計和信息熵特性，難以充分反映數(shù)據(jù)集的整體特征，可擴展性相對較弱。基于模型的元特征將數(shù)據(jù)集映射在模型中，通過模型的結(jié)構(gòu)屬性描述數(shù)據(jù)集整體特征，方法的可擴展性較強，但是數(shù)據(jù)集映射和元特征提取的過程較為復(fù)雜。基于基準的元特征反映候選算法的學(xué)習(xí)偏差，然而算法性能的計算開銷高昂，難以適應(yīng)實時性要求較高的情況，且方法的可擴展性不強。基于問題復(fù)雜度的元特征測度數(shù)據(jù)集的空間分布復(fù)雜度，從類重疊、類決策邊界、數(shù)據(jù)稀疏度、類不平衡等方面整體地描述數(shù)據(jù)集，具備較強的可擴展性，諸如ECol[39]等特征提取工具降低了元特征的獲取難度，但其計算復(fù)雜度較大，且當(dāng)數(shù)據(jù)集維度較高或存在缺失數(shù)據(jù)時，某些元特征的計算方法會失效。

2.2 元算法的研究進展

元算法是算法選擇研究的關(guān)鍵之一，根據(jù)訓(xùn)練元模型的技術(shù)特點，可以將元算法分為四類：基于規(guī)則的元算法、基于距離的元算法、基于回歸的元算法和基于集成學(xué)習(xí)的元算法。

2.2.1 基于規(guī)則的元算法

基于規(guī)則的元算法為每個候選算法生成選擇規(guī)則，當(dāng)元特征滿足選擇規(guī)則時，表示對應(yīng)的候選算法為問題的合適算法。常采用C4.5、C5.0 等決策樹算法建立數(shù)據(jù)集元特征與候選算法的關(guān)聯(lián)，生成規(guī)則并憑此完成合適算法的決策。

STATLOG 項目使用決策樹算法C4.5 作為元算法，生成22 個候選分類算法的選擇規(guī)則。文獻[40]以C5.0 決策樹為元算法，通過對決策樹的剪枝參數(shù)進行搜索優(yōu)化，分別為8 個候選分類算法訓(xùn)練預(yù)測性能最好的決策樹，生成各候選算法最優(yōu)的選擇規(guī)則，使構(gòu)建的規(guī)則集合具備較高的可信度，圖4給出了OneR（one rule）候選算法的選擇規(guī)則示意，表示當(dāng)數(shù)據(jù)集的實例數(shù)不小于1 728 且屬性峰度的均值大于19.887 9時，OneR 算法為該數(shù)據(jù)集的合適算法。文獻[41]使用213 個數(shù)據(jù)集和161 種元特征，以包括C4.5 在內(nèi)的5 種元算法構(gòu)建元模型，預(yù)測5 種特征選擇算法的算法排序。針對負荷需求預(yù)測問題，文獻[42]提取18 種數(shù)據(jù)集元特征，使用分類回歸樹（classification and regression tree，CART）算法從6 種候選算法中選擇最優(yōu)算法。

圖4 候選算法選擇規(guī)則Fig.4 Candidate algorithm selection rule

2.2.2 基于距離的元算法

基于距離的元算法利用元特征測度問題實例間的距離，對于新問題，利用與其距離最近的其他問題實例預(yù)測其合適算法。其基本思想是：算法在相似問題上的性能相近，而問題的相似度可以通過元特征距離進行量化計算。

在基于距離的元算法中，k-最近鄰（k-nearest neighbor，k-NN）算法應(yīng)用較為廣泛。利用元特征對數(shù)據(jù)集特性的反映能力，可以將歷史數(shù)據(jù)集映射在由元特征構(gòu)成的空間中，提取新數(shù)據(jù)集的元特征后，k-NN 通過元特征測度其與歷史數(shù)據(jù)集在上述空間中的距離，從中選擇距離最近的k個歷史數(shù)據(jù)集，然后基于這k個“鄰居”的歷史算法信息預(yù)測算法在新數(shù)據(jù)集上的性能表現(xiàn)。例如，當(dāng)元目標(biāo)為算法排序時，算法在新數(shù)據(jù)集上的預(yù)測排序由其在k個最相似歷史數(shù)據(jù)集上的平均歷史排序決定。k值和距離度量方法對于k-NN 的性能表現(xiàn)有著關(guān)鍵影響。文獻[25]設(shè)置固定k值，對比分析了歐氏距離、曼哈頓距離、余弦距離和賈卡德系數(shù)4 種距離度量的應(yīng)用效果，表示歐氏距離和曼哈頓距離的效果較好。文獻[43]使用以距離倒數(shù)為權(quán)重的加權(quán)歐式距離，采用將所有元實例視為“鄰居”的all-NN 構(gòu)建元模型。文獻[44]采用曼哈頓距離和80 個數(shù)據(jù)集進行實驗，結(jié)果表明，使用不同類型元特征形成的元數(shù)據(jù)集，其對應(yīng)的最優(yōu)k值存在明顯差異。文獻[45]使用曼哈頓距離和2 700個數(shù)據(jù)集，對比了5-NN、10-NN、50-NN、500-NN 和all-NN 元算法的表現(xiàn)，其中50-NN 的性能較優(yōu)。

少數(shù)研究使用了基于案例推理（case based reasoning）的方法構(gòu)建算法選擇系統(tǒng)[23,46]。在基于案例推理的系統(tǒng)中，元實例被表示為案例，元數(shù)據(jù)集被稱為案例庫，新數(shù)據(jù)集則對應(yīng)新案例，通過案例檢索、案例重用和案例學(xué)習(xí)的查詢流程為新數(shù)據(jù)集選擇合適算法并更新案例庫。上述流程中，案例檢索通過元特征測度案例間的距離，從案例庫中檢索相似案例；案例重用使用相似案例為新案例選擇合適算法；案例學(xué)習(xí)評估查詢的效果，將滿足條件的新案例及其查詢結(jié)果加入到案例庫中。

2.2.3 基于回歸的元算法

部分研究將算法選擇問題映射為回歸問題，應(yīng)用回歸算法訓(xùn)練元模型。具體而言，該方法生成以算法性能指標(biāo)值為標(biāo)簽的元實例，為每個候選算法構(gòu)建單獨的元數(shù)據(jù)集；應(yīng)用回歸算法訓(xùn)練回歸模型，對各候選算法的性能指標(biāo)值進行預(yù)測；根據(jù)各算法的預(yù)測性能輸出給定元目標(biāo)的合適算法。

文獻[47]提取27 種元特征，使用數(shù)據(jù)集元特征和候選算法的性能指標(biāo)值為18 種候選算法分別構(gòu)建元數(shù)據(jù)集后，對各元數(shù)據(jù)集采用線性回歸（linear regression，LR）算法訓(xùn)練得到18 個回歸元模型，通過元模型預(yù)測候選算法在新數(shù)據(jù)集上的性能指標(biāo)值，形成預(yù)測算法排序。文獻[37]使用支持向量回歸（support vector regression，SVR）算法作為元算法，為14 個候選回歸算法和2 類回歸問題元特征分別構(gòu)建了28 個回歸模型，根據(jù)模型性能分析了2 類元特征的應(yīng)用效果差異。文獻[48]使用SVR 等3 種回歸元算法，對5 種候選分類算法的性能指標(biāo)值進行預(yù)測，根據(jù)預(yù)測偏差對不同類型元特征的應(yīng)用效果進行對比。文獻[49]對基于聚類簇的元特征開展實驗研究，分別使用SVR、CART 等5 種回歸元算法，預(yù)測5 種候選分類算法的準確率，分析表示基于聚類簇的元特征具備較強的偏差反映能力。

2.2.4 基于集成學(xué)習(xí)的元算法

該方法采用集成學(xué)習(xí)的思想，通過組合多個性能較弱的元模型（基學(xué)習(xí)器），得到具有較強泛化性能和算法選擇性能的元模型。

隨機森林（random forest，RF）是基于元學(xué)習(xí)的算法選擇研究中廣泛應(yīng)用的元算法之一，它采用自助采樣法生成若干訓(xùn)練數(shù)據(jù)集，在這些數(shù)據(jù)集上并行地訓(xùn)練決策樹基學(xué)習(xí)器并加以組合。文獻[50]首先使用時序預(yù)測模型擬合原始時序數(shù)據(jù)，通過模型生成與原始數(shù)據(jù)具有相似分布的模擬數(shù)據(jù)，共同構(gòu)成歷史數(shù)據(jù)集；然后，對于歷史數(shù)據(jù)集中的每一份時序數(shù)據(jù)，提取其32 種時序元特征，將其劃分為訓(xùn)練時間段和測試時間段，訓(xùn)練9 種時序預(yù)測模型并根據(jù)測試性能確定最優(yōu)模型，以元特征為屬性，以最優(yōu)模型為標(biāo)簽形成元實例構(gòu)建元數(shù)據(jù)集；最后使用RF 元算法訓(xùn)練元模型，對于新時序數(shù)據(jù)，提取其元特征，使用元模型對其最優(yōu)時序模型進行分類預(yù)測。文獻[51]通過強化學(xué)習(xí)從多種元特征中選擇合適的元特征子集，建立元數(shù)據(jù)集并使用RF 訓(xùn)練元模型，從4 種分類算法中選擇最優(yōu)算法。文獻[52]針對多目標(biāo)回歸問題，基于RF 構(gòu)建元模型，從2 種回歸算法和6 種多目標(biāo)回歸問題轉(zhuǎn)換方法中選擇合適的組合。

極端梯度提升（extreme gradient boosting，XGB）算法順序訓(xùn)練并組合若干個基學(xué)習(xí)器，具體而言，在訓(xùn)練過程中，算法根據(jù)上一個基學(xué)習(xí)器的表現(xiàn)調(diào)整訓(xùn)練數(shù)據(jù)的分布，以提升當(dāng)前基學(xué)習(xí)器的學(xué)習(xí)性能，當(dāng)基學(xué)習(xí)器數(shù)量達到閾值時按照順序組合所有基學(xué)習(xí)器。文獻[53]使用10 種聚類性能指標(biāo)測度17 個聚類算法的性能，通過單獨使用和結(jié)合使用10 種指標(biāo)的方法構(gòu)建11 個元數(shù)據(jù)集，在構(gòu)建元數(shù)據(jù)集時，每一個歷史數(shù)據(jù)集和候選算法的成對組合對應(yīng)一個元實例，該元實例由歷史數(shù)據(jù)集的元特征、候選算法在該數(shù)據(jù)集上的歷史排序以及用于表示該候選算法的離散值構(gòu)成；采用排序?qū)W習(xí)策略的XGB 訓(xùn)練元模型，輸入新數(shù)據(jù)集的元特征后，元模型即可以生成各候選算法的預(yù)測排序。文獻[54]利用大量已有的分類算法研究成果，將算法性能和數(shù)據(jù)集的相互關(guān)系通過向量嵌入（vector embedding）方法表示為元特征，然后基于XGB 生成元模型，驗證該元特征的使用效果。文獻[55]設(shè)計可應(yīng)用于分類或回歸問題的算法選擇系統(tǒng)AutoGRD，該系統(tǒng)為分類和回歸任務(wù)設(shè)置了不同的XGB 元算法參數(shù)，并通過對比實驗展示了系統(tǒng)的適用性。

除上述元算法外，個別研究使用生成對抗網(wǎng)絡(luò)（generative adversarial network）構(gòu)建元模型[56-57]。然而，該深度學(xué)習(xí)方法需要大量具備統(tǒng)一格式的訓(xùn)練數(shù)據(jù)，在歷史數(shù)據(jù)集的收集和處理以及元數(shù)據(jù)集的構(gòu)建方面均存在較大問題，難以泛化應(yīng)用。

表3 展示了不同類型元算法的優(yōu)缺點。

表3 元算法優(yōu)缺點對比Table 3 Comparison of advantages and disadvantages in different meta-learners

基于規(guī)則的元算法生成候選算法的選擇規(guī)則，可解釋性較好，但在增減候選算法時需要重新訓(xùn)練元模型，靈活性不足?；诰嚯x的元算法易于實現(xiàn)，在元數(shù)據(jù)集的規(guī)模較小時仍具備較好的性能，然而算法的最優(yōu)k值受多種因素影響，設(shè)置較為困難，且算法在元數(shù)據(jù)集維度較高時難以使用?；诨貧w的方法在增減候選算法時較為靈活，不會影響已訓(xùn)練的回歸模型，但是訓(xùn)練多個模型的成本較高，且元實例數(shù)變化時需要重新訓(xùn)練所有模型?；诩蓪W(xué)習(xí)的元算法相對于單個元算法常有更優(yōu)表現(xiàn)，然而復(fù)雜的參數(shù)設(shè)置使元模型的調(diào)優(yōu)更具挑戰(zhàn)性，此外，基學(xué)習(xí)器的設(shè)置是該方法的關(guān)鍵，不同基學(xué)習(xí)器的應(yīng)用效果仍待探究。

元目標(biāo)是選用元算法的關(guān)鍵參考，現(xiàn)結(jié)合元目標(biāo)對元算法做進一步分析?；谝?guī)則的元算法常用于預(yù)測最優(yōu)算法，該方法訓(xùn)練較快，生成的規(guī)則有利于對元特征進行深入分析，然而其泛化性能較差，應(yīng)用較為有限?；诰嚯x的元算法訓(xùn)練過程不受元實例標(biāo)簽的影響，易于實現(xiàn)且應(yīng)用靈活，是算法排序研究中的經(jīng)典方法，同時也適用于其他元目標(biāo)，但是設(shè)置最優(yōu)k值的難題限制了其快速應(yīng)用，而性能表現(xiàn)也是其短板之一。根據(jù)候選算法的預(yù)測性能指標(biāo)值，基于回歸的元算法可以間接完成不同元目標(biāo)，且算法選擇結(jié)果易于理解，然而多個模型的調(diào)整成本和整體誤差較高?；诩蓪W(xué)習(xí)的元算法通過設(shè)置基學(xué)習(xí)器和學(xué)習(xí)策略可適用于不同元目標(biāo)，其具備較強的泛化性能和適用性，在近年的研究中更受青睞，但訓(xùn)練速度較慢。

2.3 元模型性能指標(biāo)的研究進展

元模型的性能評估是算法選擇研究的一項重要內(nèi)容，而其中的關(guān)鍵問題是采用何種性能度量指標(biāo)。本節(jié)根據(jù)元目標(biāo)和元模型輸出結(jié)果的不同，將元模型性能指標(biāo)分為基于最優(yōu)算法指標(biāo)、基于算法排序指標(biāo)和基于算法集合指標(biāo)，如表4 所示。

表4 元模型性能指標(biāo)Table 4 Performance measures of meta-model

2.3.1 基于最優(yōu)算法指標(biāo)

預(yù)測最優(yōu)算法常被視為分類任務(wù)，在這種情況下，分類性能指標(biāo)對于元模型性能評估具有天然的適用性，如準確率指標(biāo)和基于混淆矩陣的指標(biāo)。此外，推薦準確率（recommendation accuracy，RA）指標(biāo)也是研究中常用的指標(biāo)之一。

準確率指標(biāo)計算預(yù)測最優(yōu)算法與歷史最優(yōu)算法相一致的元實例在若干測試元實例中所占比例，是應(yīng)用較為廣泛的經(jīng)典指標(biāo)。

對于類不平衡元數(shù)據(jù)集，即不同歷史最優(yōu)算法類別的元實例數(shù)量差距較大的元數(shù)據(jù)集，準確率難以評估元模型對少數(shù)類的預(yù)測效果，對此，許多研究選用如下所述基于混淆矩陣的指標(biāo)。

考慮元模型從兩種候選算法（不妨設(shè)為正例候選算法和反例候選算法）中為測試元實例預(yù)測最優(yōu)算法的情況，其預(yù)測結(jié)果的混淆矩陣如表5 所示。

表5 最優(yōu)算法預(yù)測結(jié)果混淆矩陣Table 5 Confusion matrix of prediction results of best algorithms

表5 中，真正例（true positive，TP）表示正確預(yù)測正例候選算法為最優(yōu)的元實例數(shù)，假反例（false negative，F(xiàn)N）表示錯誤預(yù)測反例候選算法為最優(yōu)的元實例數(shù)，真反例（true negative，TN）表示正確預(yù)測反例候選算法為最優(yōu)的元實例數(shù)，假正例（false positive，F(xiàn)P）表示錯誤預(yù)測正例候選算法為最優(yōu)的元實例數(shù)。

基于混淆矩陣，查準率（precision，Pre）、查全率（recall，Rec）、假正例率（false positive rate，F(xiàn)PR）和特異度（specificity）指標(biāo)的計算如式（6）～式（9）所示，其中查全率也被稱為真正例率（true positive rate，TPR）或靈敏度（sensitivity）。

F1 得分是上述查準率和查全率的加權(quán)調(diào)和平均，其計算如式（10）所示：

基于TPR和FPR，可以計算得到AUC（area under curve）性能指標(biāo)，如式（11）所示：

平衡準確率（balanced accuracy，BA）指標(biāo)計算靈敏度和特異度的均值，如式（12）所示：

文獻[24]提出RA 指標(biāo)，其度量預(yù)測最優(yōu)算法與歷史最優(yōu)算法的性能差距，如式（13）所示：

其中，PAp,D和PAb,D分別表示在給定數(shù)據(jù)集D上的預(yù)測最優(yōu)算法與歷史最優(yōu)算法的性能，PAw,D表示數(shù)據(jù)集D上歷史最差算法的性能，該歷史最差算法根據(jù)元知識中的候選算法性能信息確定。

2.3.2 基于算法排序指標(biāo)

對算法排序結(jié)果進行評估的指標(biāo)包括斯皮爾曼排序相關(guān)系數(shù)（Spearman rank correlation coefficient，SRC）、平均排序倒數(shù)（mean reciprocal rank，MRR）和排序命中率（hit ratio，HR）。

SRC 測度預(yù)測算法排序和歷史算法排序的相似度，可以較為準確地評估算法全排序的結(jié)果，其計算如式（14）所示：

其中，q為候選算法數(shù)，ri和分別表示第i個候選算法在預(yù)測算法排序和歷史算法排序中的位置。SRC值為[-1,1]，其值越大表示元模型的預(yù)測結(jié)果越精確。

歷史最優(yōu)算法在預(yù)測算法排序中的排序位置是研究人員較為關(guān)心的結(jié)果，MRR 即通過歷史最優(yōu)算法快速地評估算法排序效果，其計算如式（15）所示：

其中，m為數(shù)據(jù)集數(shù)，branki表示數(shù)據(jù)集i的歷史最優(yōu)算法在預(yù)測算法排序中的排序位置，MRR值越大表明元模型性能越好。

針對輸出算法部分排序的元模型，常用排序HR指標(biāo)測度其性能，該指標(biāo)對元模型預(yù)測算法的可用性進行簡要評估，其計算如式（16）所示：

其中，m為數(shù)據(jù)集數(shù)；對于數(shù)據(jù)集i，其歷史算法排序中的前k個最優(yōu)算法構(gòu)成一個集合，預(yù)測算法部分排序中的k個算法構(gòu)成另一個集合；當(dāng)上述集合的交集不為空時，HitCounti值為1，表示預(yù)測“命中”，反之，HitCounti值為0，表示“未命中”。隨著k值增加，預(yù)測更容易“命中”，命中率隨之提高。

2.3.3 基于算法集合指標(biāo)

在以算法集合為元目標(biāo)的研究中，常用向量(a1,a2,…,aq)表示算法集合，其中ai值為1 表示第i個候選算法為合適算法，為0 表示非合適算法，使用的元模型性能指標(biāo)包括排名損失（ranking loss，RL）、漢明損失（Hamming loss，HL）和集合HR。

文獻[58]預(yù)測算法為合適算法的概率并根據(jù)概率對算法排序，當(dāng)概率超過給定閾值時將算法并入預(yù)測算法集合，從而同時獲取預(yù)測算法集合和預(yù)測算法排序；當(dāng)合適算法的排序比非合適算法的排序大時，則預(yù)測錯誤，由此可以通過RL 指標(biāo)計算歷史算法集合中的合適算法被錯誤預(yù)測次數(shù)，如式（17）所示：

其中，A和表示數(shù)據(jù)集D上的歷史算法集合及其補集，ranka和rankb分別表示算法a∈A和算法b∈Aˉ在預(yù)測算法排序中的排序位置。RL 指標(biāo)值越小，說明元模型的錯誤預(yù)測次數(shù)越少，其性能越強。

HL 指標(biāo)利用算法集合向量元素值的二元性質(zhì)，計算預(yù)測算法集合與歷史算法集合向量的差異程度，如式（18）所示：

其中，q為候選算法數(shù)；對于數(shù)據(jù)集D，PD表示預(yù)測算法集合，TD表示歷史算法集合；Δ 表示逐個對比PD和TD的對位元素，若相異則PDΔTD值加1。HL指標(biāo)值越小表示元模型性能越好。

集合HR 與排序HR 指標(biāo)計算方法一致，區(qū)別在于歷史算法集合固定，集合HR 不受參數(shù)k影響。集合HR 值越大，元模型的表現(xiàn)越好。

此外，在使用回歸元算法的研究中，均方誤差（mean squared error，MSE）和均方根誤差（root mean squared error，RMSE）指標(biāo)被用于測度元模型性能，其計算回歸模型的性能指標(biāo)值預(yù)測誤差，分別如式（19）和式（20）所示：

其中，m表示數(shù)據(jù)集數(shù)；對于數(shù)據(jù)集i，yi表示元知識中候選算法的歷史性能指標(biāo)值表示候選算法的預(yù)測性能指標(biāo)值。

表6 總結(jié)了不同元模型性能指標(biāo)的優(yōu)缺點。

表6 元模型性能指標(biāo)優(yōu)缺點對比Table 6 Comparison of advantages and disadvantages in different meta-model performance measures

基于最優(yōu)算法的指標(biāo)中，準確率指標(biāo)應(yīng)用廣泛，計算簡單，但當(dāng)元數(shù)據(jù)集存在類不平衡時難以反映元模型的綜合性能；相較于準確率，查準率、查全率、F1 得分等基于混淆矩陣的指標(biāo)考慮了正負例的預(yù)測性能，更適用于類不平衡的元數(shù)據(jù)集，但指標(biāo)在多分類情況下的計算較為復(fù)雜；RA 指標(biāo)計算預(yù)測最優(yōu)算法和歷史最優(yōu)算法的歸一化性能差距，然而在候選算法的性能差距較小時，該指標(biāo)的效果較差。

基于算法排序的指標(biāo)中，SRC 指標(biāo)能夠有效度量算法排序結(jié)果的偏差程度，但隨著候選算法數(shù)增加，其計算成本也快速增加；MRR 指標(biāo)計算簡單，但是指標(biāo)忽略了除最優(yōu)算法外的其他候選算法，不能反映算法排序結(jié)果的整體偏差；排序HR 指標(biāo)可以根據(jù)需求設(shè)置不同k值，較為靈活，然而該指標(biāo)不能反映候選算法排序位置的具體偏差。

基于算法集合的指標(biāo)中，RL 指標(biāo)能較好地反映預(yù)測結(jié)果的誤差，然而其計算量較大；HL 指標(biāo)考慮了將合適算法預(yù)測為非合適以及將非合適算法預(yù)測為合適的兩類誤差，提供了綜合性的評估結(jié)果，但是不能提供不同誤差的明確信息；集合HR 指標(biāo)易于計算，然而其無法衡量將非合適算法預(yù)測為合適算法的誤差程度。MSE 和RMSE 指標(biāo)評估性能指標(biāo)值的預(yù)測誤差，易于實現(xiàn)，但是在給定元目標(biāo)下，兩種指標(biāo)難以評估算法選擇方法的有效性。

3 基于元學(xué)習(xí)的算法選擇應(yīng)用

為了降低對數(shù)據(jù)進行分析決策的成本，研究人員廣泛使用了基于元學(xué)習(xí)的方法進行算法選擇。本章根據(jù)使用數(shù)據(jù)集類型和學(xué)習(xí)任務(wù)的不同，將算法選擇研究分為分類應(yīng)用、回歸應(yīng)用和聚類應(yīng)用。考慮具體的應(yīng)用內(nèi)容，近年的算法選擇研究應(yīng)用情況如表7 所示。

表7 基于元學(xué)習(xí)的算法選擇應(yīng)用Table 7 Application of algorithm selection based on meta-learning

3.1 分類應(yīng)用

分類問題是算法選擇重要的研究方向，出現(xiàn)了大量的研究文獻。為了構(gòu)建具備一定規(guī)模的元數(shù)據(jù)集，提供更可信的算法選擇結(jié)果，多數(shù)研究廣泛使用來源于不同應(yīng)用領(lǐng)域的分類數(shù)據(jù)集和不同種類的候選分類算法，并基于不同類型的元算法訓(xùn)練元模型完成算法選擇[17,31,48]。自動機器學(xué)習(xí)（automated machine learning）是相關(guān)研究的熱點之一，其通過算法選擇和超參數(shù)優(yōu)化等多個流程為給定任務(wù)構(gòu)建最優(yōu)機器學(xué)習(xí)模型[59-60]。部分研究采用基于元學(xué)習(xí)的方法從多個候選算法中選擇部分較優(yōu)算法，在此基礎(chǔ)上，對所選算法進行超參數(shù)優(yōu)化以減少整體時間開銷。文獻[61]選用12 種候選分類算法，采用k-NN 從中篩選較優(yōu)算法進行超參數(shù)優(yōu)化。文獻[62]基于候選算法性能設(shè)計一種比較規(guī)則，根據(jù)規(guī)則為每個數(shù)據(jù)集確定較優(yōu)算法，并采用決策樹算法構(gòu)建元模型。文獻[63]在上述研究的基礎(chǔ)上，針對自動機器學(xué)習(xí)的可擴展性問題，提出了一種分布式自動機器學(xué)習(xí)框架，實驗表明該框架在大型數(shù)據(jù)集上具備較優(yōu)性能。

隨著各領(lǐng)域數(shù)據(jù)量的增加和方法技術(shù)的擴展，聚焦于特定領(lǐng)域的算法選擇研究逐漸增多。在生物分析領(lǐng)域中層次分類（hierarchical classification）問題較為常見，其數(shù)據(jù)集的類別之間存在層次關(guān)系，文獻[64]提出27 種層次分類數(shù)據(jù)集元特征，采用J48 決策樹算法訓(xùn)練元模型，生成層次分類算法的選擇規(guī)則。文獻[65]面向網(wǎng)絡(luò)安全領(lǐng)域中的網(wǎng)絡(luò)攻擊檢測問題，通過SVR 元算法訓(xùn)練元模型，預(yù)測5 種候選分類算法的查全率并據(jù)此完成算法排序。

在針對圖像數(shù)據(jù)進行分析的研究中，文獻[66]采用卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）提取圖像元特征向量，在此基礎(chǔ)上使用RF 訓(xùn)練元模型，選擇用于圖像分類任務(wù)的最優(yōu)CNN 模型。圖像分割對圖像進行像素級別的分類，是圖像數(shù)據(jù)處理中的重要步驟，文獻[67]從色彩、質(zhì)量、紋理等多個方面提取圖像元特征，對比了3 種元算法的算法選擇效果，其中RF 元算法的性能更優(yōu)。針對醫(yī)學(xué)影像的圖像分割任務(wù)，文獻[68]使用CNN 提取圖像元特征，通過基于回歸的方法預(yù)測深度學(xué)習(xí)模型的圖像分割性能。

部分研究為分類數(shù)據(jù)集選擇數(shù)據(jù)處理技術(shù)。分類數(shù)據(jù)集類不平衡問題可以通過多種數(shù)據(jù)集采樣方法加以解決，如過采樣、欠采樣等，文獻[44,69]首先確定用于類不平衡數(shù)據(jù)集的分類算法，在此基礎(chǔ)上采用基于元學(xué)習(xí)的方法為數(shù)據(jù)集選擇合適采樣方法，提升分類算法的性能。異常檢測（anomaly detection）技術(shù)是提升數(shù)據(jù)集數(shù)據(jù)質(zhì)量的重要手段，在諸多領(lǐng)域中得到了重視。文獻[70]提出5 種異常數(shù)據(jù)元特征，使用基于元學(xué)習(xí)的方法選擇最優(yōu)異常檢測算法，驗證所提元特征的應(yīng)用效果。文獻[71]針對航空設(shè)備故障診斷數(shù)據(jù)的高維問題，以選擇最優(yōu)特征選擇算法為目標(biāo)，設(shè)計基于元學(xué)習(xí)的算法選擇系統(tǒng)以避免遍歷特征選擇算法的時間和空間成本。文獻[72]對基因表達數(shù)據(jù)分析展開研究，設(shè)計從4 種特征選擇算法和3 種分類算法中選擇最優(yōu)組合的算法選擇方法，對比實驗了神經(jīng)網(wǎng)絡(luò)、輕量梯度提升機（light gradient boosting machine）和k-NN 元算法的性能差異，結(jié)果顯示神經(jīng)網(wǎng)絡(luò)和輕量梯度提升機均優(yōu)于k-NN。

此外，文獻[73]考慮集成分類算法在人類活動識別系統(tǒng)中的應(yīng)用，基于k-NN 元算法為集成分類器選擇最優(yōu)集成剪枝（ensemble pruning）算法，對集成分類器中的基學(xué)習(xí)器進行修剪篩除，從而降低應(yīng)用集成分類算法的計算開銷。

3.2 回歸應(yīng)用

回歸與分類均為有監(jiān)督學(xué)習(xí)問題，在數(shù)據(jù)集屬性等方面具有一定的相似性，文獻[37]受到分類元特征研究的啟發(fā)提出回歸數(shù)據(jù)集元特征，文獻[46,55]則設(shè)計可以兼顧分類和回歸任務(wù)的算法選擇系統(tǒng)。

算法選擇研究在回歸應(yīng)用中也呈現(xiàn)出一定的領(lǐng)域針對性。定量構(gòu)效關(guān)系（quantitative structure activity relationship）表示化合物分子結(jié)構(gòu)和化合物活性之間的映射關(guān)系，文獻[45]分析定量構(gòu)效關(guān)系學(xué)習(xí)問題中藥物成分和蛋白質(zhì)靶標(biāo)的特征，采用基于元學(xué)習(xí)的方法選擇最優(yōu)回歸算法。文獻[74]基于元學(xué)習(xí)方法設(shè)計算法選擇框架，采用RF 元算法形成15 個候選回歸算法的算法排序，為數(shù)據(jù)科學(xué)家在大數(shù)據(jù)分析過程中提供決策助力。

基于時序數(shù)據(jù)的回歸預(yù)測是不同領(lǐng)域中的重要任務(wù)[50]。文獻[42]重點研究外部天氣因素對短期電力負荷需求的影響，基于此提出相應(yīng)的元特征并開展算法選擇研究。針對電力消耗預(yù)測問題，文獻[75]分別采用了k-NN、RF 等5 種元算法生成元模型，從4種時序預(yù)測算法中選擇最優(yōu)算法，其中RF 具備優(yōu)異表現(xiàn)。文獻[76]以能源消耗預(yù)測為應(yīng)用領(lǐng)域，考慮時序數(shù)據(jù)中的時間屬性，結(jié)合匯總統(tǒng)計方法提出基于時間屬性的元特征，并通過聚類方法分析該元特征的使用效果。在文獻[76]的基礎(chǔ)上，文獻[77-78]使用多種時序數(shù)據(jù)集元特征，結(jié)合大數(shù)據(jù)和微服務(wù)技術(shù)，構(gòu)建基于元學(xué)習(xí)的時序預(yù)測算法選擇框架。正確評估軟件在一定時間段內(nèi)發(fā)生故障失效的概率可以降低軟件測試、維護和發(fā)布的成本，文獻[79]提出4 種元特征描述軟件故障數(shù)據(jù)，分別采用J48 決策樹和神經(jīng)網(wǎng)絡(luò)作為元算法，從5 種軟件可靠性分析模型中選擇最優(yōu)模型。

推薦系統(tǒng)（recommendation system）旨在通過推薦算法建立用戶與項目之間的關(guān)系，預(yù)測用戶對項目的評分，從而為用戶推薦感興趣的項目。文獻[80]結(jié)合聚類方法構(gòu)建推薦算法選擇系統(tǒng)，其首先通過k均值（k-means）聚類算法將用戶推薦數(shù)據(jù)集劃分為10個聚類簇，然后根據(jù)推薦算法在聚類簇各實例上的平均性能為聚類簇選定最優(yōu)推薦算法。最后，基于1-NN 為新數(shù)據(jù)集確定最近鄰的聚類簇，得到最優(yōu)算法的預(yù)測結(jié)果。文獻[81]在使用14 個用戶推薦數(shù)據(jù)集和3 種推薦算法構(gòu)建元數(shù)據(jù)集的基礎(chǔ)上，根據(jù)14 個元實例的統(tǒng)計數(shù)據(jù)合成新的元實例擴充元數(shù)據(jù)集，分別應(yīng)用了4 種元算法進行實驗。文獻[82]將推薦算法在用戶推薦數(shù)據(jù)集上的排名線性轉(zhuǎn)換為評分作為算法元特征，結(jié)合數(shù)據(jù)集元特征構(gòu)建元數(shù)據(jù)集，實驗對比了3 種元算法的性能表現(xiàn)。

3.3 聚類應(yīng)用

相較于算法選擇在分類和回歸任務(wù)中的應(yīng)用，面向聚類問題的算法選擇研究相對較少。文獻[26]使用10 種候選聚類算法和11 種聚類性能指標(biāo)展開研究，其利用元實例的元特征信息，通過聚類算法劃分元實例的聚類簇并選出簇的原型，然后采用1-NN 為新數(shù)據(jù)集選擇與其元特征距離最近的原型，使用原型所對應(yīng)的單個元實例或元實例聚類簇完成算法選擇決策。文獻[35]使用7 種聚類算法和4 種聚類指標(biāo)進行實驗，對k-NN 與DeepFM 深度學(xué)習(xí)模型的算法排序性能進行對比，結(jié)果顯示DeepFM 的性能較優(yōu)。文獻[38]選用10 種聚類算法和13 種聚類指標(biāo)設(shè)計算法選擇實驗，將所提元特征與其他3 類元特征進行對比分析，結(jié)果驗證了所提元特征對聚類數(shù)據(jù)集特性具有良好的反映能力。文獻[83]面向在線算法服務(wù)問題，考慮運行時間和準確率兩種算法服務(wù)質(zhì)量，采用分類元算法為用戶選擇最優(yōu)聚類算法，采用回歸元算法預(yù)測聚類算法的服務(wù)質(zhì)量為用戶提供算法排序。文獻[84]通過基于回歸的方法構(gòu)建元模型預(yù)測8種聚類算法的性能指標(biāo)值，分析25 種聚類問題元特征的應(yīng)用效果。

個別研究考慮聚類算法中的關(guān)鍵參數(shù)，通過基于元學(xué)習(xí)的方法進行選擇設(shè)置。文獻[13]從9 種距離度量方法中進行選擇，通過RF 元算法預(yù)測最優(yōu)距離度量方法，采用k-NN 元算法預(yù)測距離度量方法的排序，分別為兩種聚類算法確定其在不同數(shù)據(jù)集上的合適度量方法。文獻[28]以聚類算法的聚類簇個數(shù)設(shè)置為研究點，提出一種元特征向量描述聚類數(shù)據(jù)集的數(shù)據(jù)密度，通過基于回歸的方法預(yù)測聚類算法在設(shè)置不同聚類簇個數(shù)時的性能指標(biāo)值，為算法確定其最優(yōu)聚類簇個數(shù)設(shè)置。

4 實驗分析

為了比較不同類型元算法的性能并分析其適用性，本章通過分類算法選擇實驗對元算法的算法選擇性能進行量化對比。

4.1 實驗設(shè)置

考慮到實驗的可參考性，數(shù)據(jù)集、元特征、候選算法、元目標(biāo)等均采用現(xiàn)有研究中常見的設(shè)置，具體如下所述。

使用來自UCI、KEEL 和StatLib 的140 個分類數(shù)據(jù)集，這些數(shù)據(jù)集在數(shù)據(jù)來源領(lǐng)域、實例個數(shù)、屬性個數(shù)和類型等方面具有一定的差異性，構(gòu)成多樣化的數(shù)據(jù)集，從而能夠有效評估元算法的性能。實驗數(shù)據(jù)集信息如表8 所示。為了使元特征能夠提取并反映數(shù)據(jù)集的原始特性，實驗暫不考慮數(shù)據(jù)質(zhì)量對算法性能的影響，不對數(shù)據(jù)集進行數(shù)據(jù)預(yù)處理。

表8 實驗數(shù)據(jù)集信息Table 8 Information of experiment datasets

通過元特征提取工具MFE[12]提取數(shù)據(jù)集的150種元特征，包括77 種基于統(tǒng)計和信息論的元特征、24種基于模型的元特征、14 種基于基準的元特征和35種基于問題復(fù)雜度的元特征。

使用8 種sklearn[85]機器學(xué)習(xí)平臺的分類算法作為候選算法，包括k-NN、RF、支持向量機（support vector machine，SVM）、邏輯回歸（logistic regression，LoR）、NB、LDA、C4.5 決策樹和多層感知機（multilayer perceptron，MLP），均采用sklearn 中的默認參數(shù)設(shè)置。MLP 是深度學(xué)習(xí)中的經(jīng)典算法之一，而深度學(xué)習(xí)中所令人熟知的代表性技術(shù)是CNN。為提供較為全面的參考，本文基于Keras[86]構(gòu)建CNN 模型，出于實現(xiàn)的簡易性和對不同數(shù)據(jù)集的適用性考慮，使用一個含有32 個卷積核的一維卷積層、一個全連接層以及一個最大池化層構(gòu)成CNN 的隱藏層。此外，設(shè)置卷積層和全連接層使用ReLU（rectified linear unit）激活函數(shù)，輸出層使用Softmax 激活函數(shù)。

以最優(yōu)算法為元目標(biāo)，通過5 次10 折交叉驗證計算各候選算法在實驗數(shù)據(jù)集上的準確率、查準率、查全率、F1 得分和ARR（adjusted ratio of ratios）[87]指標(biāo)值，確定各數(shù)據(jù)集的最優(yōu)算法，構(gòu)建5 種指標(biāo)對應(yīng)的元數(shù)據(jù)集。上述指標(biāo)中，ARR 綜合考慮算法的準確率和運行時間，其計算如式（21）所示：

其中，ap和aq表示候選算法；Acc和Rt表示算法在數(shù)據(jù)集上的準確率和運行時間；α為可變參數(shù)，表示準確率和運行時間的相對重要程度，α值越大則運行時間越重要。實驗中ARR 的α參數(shù)取值包括研究中常用的0.1、0.01 和0.001，以獲取更全面的算法性能比較結(jié)果。

采用sklearn 中默認參數(shù)設(shè)置的C4.5、CART、k-NN、LR、SVR、RF 和XGB 作為元算法，通過留一法交叉驗證獲取元算法的準確率、查準率、查全率、F1 得分和推薦準確率性能指標(biāo)值。

4.2 實驗結(jié)果與分析

分別用MAcc、MPre、MRec和MF1代表準確率、查準率、查全率和F1 得分指標(biāo)對應(yīng)的元數(shù)據(jù)集，使用MA1、MA2和MA3表示ARR 指標(biāo)在α值分別取0.1、0.01 和0.001 時生成的元數(shù)據(jù)集，各元數(shù)據(jù)集中各候選算法的勝出次數(shù)如表9 所示。從表9 可以看出，RF候選算法僅在MA1元數(shù)據(jù)集上的勝出次數(shù)較少，可見其具有優(yōu)越的分類性能，但是運行時間是其較為明顯的短板。與RF 相對的是k-NN 和NB，得益于算法較快的運行速度，其在ARR 指標(biāo)上具備一定優(yōu)勢，但分類性能較差，因此，隨著α值的減小，運行時間的重要性降低，二者在ARR 元數(shù)據(jù)集中的勝出次數(shù)減少。SVM 和LoR 的分類性能較優(yōu)且具有合適的時間開銷，在5 種指標(biāo)上均取得了較好結(jié)果。LDA 和C4.5的分類性能強于k-NN 和NB，另一方面，兩種候選算法在ARR 指標(biāo)上也具有優(yōu)良表現(xiàn)，說明其在運行時間和準確率兩方面較為均衡。MLP 和CNN 在各數(shù)據(jù)集上的運行時間最長，但二者在部分數(shù)據(jù)集上的分類性能具有一定優(yōu)勢，因而在MA2和MA3上仍取得了一定次數(shù)的勝出。

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

元算法在各元數(shù)據(jù)集上的準確率、查準率、查全率、F1 得分和推薦準確率指標(biāo)值如表10～表14 所示。

表10 元算法準確率指標(biāo)值Table 10 Accuracy value of meta-learners

表11 元算法查準率指標(biāo)值Table 11 Precision value of meta-learners

表12 元算法查全率指標(biāo)值Table 12 Recall value of meta-learners

表13 元算法F1 得分指標(biāo)值Table 13 F1 score value of meta-learners

表14 元算法推薦準確率指標(biāo)值Table 14 Recommendation accuracy value of meta-learners

觀察表10～表14 可以發(fā)現(xiàn)，基于規(guī)則的C4.5 和CART 元算法在各元數(shù)據(jù)集上的性能表現(xiàn)相對平庸且穩(wěn)定，兩種元算法的整體性能較為接近，在不同元數(shù)據(jù)集和性能指標(biāo)上各有優(yōu)劣。基于距離的k-NN 元算法在各項指標(biāo)上表現(xiàn)較差，難以在算法選擇性能方面與其他元算法競爭?；诨貧w的LR 和SVR 元算法性能非常接近，兩者在準確率指標(biāo)上的性能較好，在查準率、查全率和F1 得分指標(biāo)上的表現(xiàn)較差；另一方面，除MA1外，其在各元數(shù)據(jù)集上具備優(yōu)越的推薦準確率性能?；诩蓪W(xué)習(xí)的RF和XGB元算法在不同元數(shù)據(jù)集的多個指標(biāo)上可以取得最好結(jié)果，而兩種元算法中RF更勝一籌，展現(xiàn)了一定的性能優(yōu)勢。

根據(jù)實驗結(jié)果對元算法進行總結(jié)分析，基于規(guī)則的元算法整體表現(xiàn)較好，然而，該類元算法在各方面不具備突出優(yōu)勢，既在靈活性方面不如k-NN 元算法，又在算法選擇性能方面不如基于集成學(xué)習(xí)的元算法?；诰嚯x的k-NN 元算法整體表現(xiàn)較差，但其易于實現(xiàn)和調(diào)整、運行開銷較小的特點，使其在對算法選擇性能要求寬松但需要快速獲得算法選擇結(jié)果的應(yīng)用場景中更有用武之地?；诨貧w的元算法可以產(chǎn)生與歷史最優(yōu)算法在性能上較接近的預(yù)測結(jié)果，但該方法生成多個回歸元模型，具有較高的運行時間開銷。此外，當(dāng)回歸元數(shù)據(jù)集中的性能指標(biāo)值較為接近時，多個元模型的誤差使該方法更容易將與最優(yōu)算法性能指標(biāo)值較為接近的其他候選算法預(yù)測為最優(yōu)，因此，該方法難以適用于候選算法數(shù)較多或算法性能指標(biāo)值差距較小的情況?；诩蓪W(xué)習(xí)的元算法整體表現(xiàn)出優(yōu)異且穩(wěn)定的算法選擇性能，然而其運行開銷較高。此外，直接使用常規(guī)的策略和參數(shù)設(shè)置難以充分利用集成的優(yōu)勢，該類型元算法仍有較大的性能提升空間。

5 問題與發(fā)展方向

基于元學(xué)習(xí)的方法經(jīng)過多年發(fā)展，已經(jīng)成為了解決算法選擇問題的主要方法，相關(guān)研究成果也表明了這一方法在不同領(lǐng)域的適用性。然而，基于元學(xué)習(xí)的算法選擇方法仍然存在許多亟待解決的問題，本章結(jié)合方法的關(guān)鍵內(nèi)容和實際應(yīng)用，探討當(dāng)前研究存在的挑戰(zhàn)，闡述未來發(fā)展方向。

（1）元特征方面。隨著不同類型元特征的提出和完善，元特征數(shù)量逐漸增加，元特征冗余現(xiàn)象也愈加突出。為了提高元算法性能，降低元模型訓(xùn)練和元特征提取的計算成本，可以研究計算開銷更低且更能反映數(shù)據(jù)集特性的元特征，或者設(shè)計方法從已有的元特征中選擇互補的元特征集合。

隨著深度學(xué)習(xí)的快速發(fā)展，不同結(jié)構(gòu)的數(shù)據(jù)都可以通過相應(yīng)的向量嵌入方法映射為長度固定的向量，而將歷史數(shù)據(jù)集轉(zhuǎn)換為統(tǒng)一結(jié)構(gòu)，通過向量嵌入方法提取元特征向量成為了元特征發(fā)展的一大趨勢。

（2）元數(shù)據(jù)集方面。研究中，元數(shù)據(jù)集經(jīng)常存在元實例數(shù)量較少或類不平衡的問題。對此，可以選擇在來源領(lǐng)域、實例個數(shù)、屬性類型和個數(shù)等方面互補的歷史數(shù)據(jù)集，形成更多樣化、數(shù)量更豐富的問題實例；應(yīng)用數(shù)據(jù)增強方法亦可以擴大元數(shù)據(jù)集規(guī)模，使訓(xùn)練的元模型具備更強的泛化能力[67]；最后，采用多種準則評估候選算法性能[88]，降低綜合性能較弱的候選算法選擇概率，能夠在一定程度上解決元數(shù)據(jù)集的類不平衡問題。

目前，多數(shù)研究關(guān)注于構(gòu)建靜態(tài)元數(shù)據(jù)集，即元數(shù)據(jù)集的內(nèi)容固定不變，而根據(jù)已完成的算法選擇結(jié)果，對元數(shù)據(jù)集進行反饋調(diào)整是研究方向之一。

（3）元算法方面。以算法集合為元目標(biāo)構(gòu)建多標(biāo)簽分類元數(shù)據(jù)集的研究較少，多標(biāo)簽分類算法和相關(guān)技術(shù)的應(yīng)用是后續(xù)研究的一個重要研究點。此外，在部分應(yīng)用場景中數(shù)據(jù)的獲取較為困難，難以構(gòu)建較大規(guī)模的元數(shù)據(jù)集，能夠利用少量數(shù)據(jù)進行訓(xùn)練，充分發(fā)掘元特征與候選算法性能關(guān)系的元算法仍有待研究。

考慮到元特征的提取較為靈活，同時，元特征從不同角度描述數(shù)據(jù)集，具備一定互補性。設(shè)計集成學(xué)習(xí)方法，提取不同元特征構(gòu)建元模型并進行組合，是提升算法選擇方法整體泛化性能的可行方向。

（4）元模型性能指標(biāo)方面。元模型的性能依賴于所選擇的性能指標(biāo)，如何根據(jù)元目標(biāo)和元數(shù)據(jù)集特點選擇合適的性能指標(biāo)是必需考慮的問題之一。

研究中使用的指標(biāo)忽略了錯誤預(yù)測的成本，對不同類型的預(yù)測錯誤設(shè)置不同成本權(quán)重，如合適算法被分類為不合適算法的錯誤成本更高，是元模型性能指標(biāo)發(fā)展方向之一。

（5）動態(tài)算法選擇方面。在實際應(yīng)用場景中，針對流式數(shù)據(jù)的算法選擇成為了基于元學(xué)習(xí)的算法選擇方法發(fā)展趨勢之一[89-90]。在此基礎(chǔ)上，更進一步地根據(jù)資源需求和環(huán)境特點，動態(tài)地完成算法選擇決策，是算法選擇方法與實際應(yīng)用需求相匹配的一個重要發(fā)展方向。

數(shù)據(jù)集的實例數(shù)量、類別數(shù)量、屬性個數(shù)等特性易于獲取且對數(shù)據(jù)集整體結(jié)構(gòu)有著直觀的表現(xiàn)。利用上述數(shù)據(jù)集信息，在算法選擇過程中動態(tài)地為給定的候選算法提供指導(dǎo)性規(guī)則或偏好權(quán)重，是未來研究中的關(guān)注點之一。