一種新型的自適應(yīng)多核學(xué)習(xí)算法

聶逯松, 常方圓, 常學(xué)智, 劉 暢, 金有為, 劉國晟, 付加勝, 韓霄松

(1. 吉林大學(xué) 共青團吉林大學(xué)委員會, 長春 130012； 2 吉林大學(xué) 護理學(xué)院, 長春 130012；3. 吉林大學(xué) 生物與農(nóng)業(yè)工程學(xué)院, 長春 130022； 4. 長春中醫(yī)藥大學(xué) 醫(yī)藥信息學(xué)院， 長春 130117；5. 吉林大學(xué) 符號計算與知識工程教育部重點實驗室 長春 130012; 6. 吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 長春 130012; 7. 吉林大學(xué) 軟件學(xué)院, 長春 130012；8. 中國石油集團工程技術(shù)研究院有限公司, 北京 102206)

核學(xué)習(xí)是一種解決非線性分類和回歸問題的方法, 但傳統(tǒng)的核分類器都是基于單個核. 針對基于傳統(tǒng)特征的分類問題, 構(gòu)建的特征通常從不同角度描述數(shù)據(jù), 將這些特征完全映射到同一空間進行分類效果不佳, 多核學(xué)習(xí)(multiple kernel learning, MKL)[1]可解決上述問題. MKL可將多個子核整合到一個統(tǒng)一的優(yōu)化框架內(nèi)以尋求最佳組合. 研究表明, 使用多核模型可提升學(xué)習(xí)模型的性能, 同時獲得可解釋的決策函數(shù). 但多核算法的應(yīng)用存在核函數(shù)組合方式多樣且不易選取, 很難找到多核函數(shù)解決問題的最優(yōu)解以及計算復(fù)雜度較高等缺陷. 目前, 多核學(xué)習(xí)方法主要分為合成核方法、 多尺度核方法和無限核方法三類. 而針對多核學(xué)習(xí)方法的優(yōu)化則圍繞優(yōu)化組合系數(shù)和選取基核函數(shù)展開. 優(yōu)化組合系數(shù)有兩種方法, 即一階段法和二階段法. 一階段法主要優(yōu)化包括組合系數(shù)和分類器參數(shù)的目標(biāo)函數(shù), Bach等[2]考慮了支持向量機(SVM)的核矩陣圓錐形組合, 并證明這種組合系數(shù)的優(yōu)化可簡化為凸優(yōu)化問題, 稱為二次約束二次規(guī)劃(QCQP)； Lanckriet等[3]提出了一種基核矩陣的半正定性優(yōu)化方法； Feng等[4]提出了利用判別核對準(zhǔn)作為度量準(zhǔn)則以計算核函數(shù)的組合系數(shù)方法； Niazmardi等[5]實驗表明, 利用度量準(zhǔn)則計算組合系數(shù)的方法分類精度較低. 而二階段法則分別考慮組合系數(shù)與分類器參數(shù), 即先優(yōu)化組合系數(shù)后, 再集成以優(yōu)化分類器參數(shù), Gu等[6]采用該方法進行分類, 提出了一種非監(jiān)督計算組合系數(shù)的MKL方法, 之后又利用非負矩陣分解和核非負矩陣分解方法獲得組合系數(shù)的最優(yōu)解[7]； Yeh等[8]將順序最小化技術(shù)(SMO)與梯度投影法相結(jié)合, 提出了一種二階段多核學(xué)習(xí)算法, 提高了系統(tǒng)的整體性能. 二階段法隨著核數(shù)量的增加, 精度和速度都比一階段法好. 在選取基核函數(shù)方面, Kavazoglu等[9]研究表明, 高斯核函數(shù)的魯棒性強于多項式核函數(shù); Bazi等[10]利用遺傳算法進行支持向量機核函數(shù)參數(shù)的選取; Hu等[11]利用高斯核函數(shù)和Sigmoid核函數(shù)各自的特點, 設(shè)計了多核學(xué)習(xí)算法分別發(fā)揮其優(yōu)勢； 李陽等[12]將多核方法與矩陣化最小二乘支持向量機相結(jié)合應(yīng)用于肺結(jié)節(jié)的識別， 取得了較好的結(jié)果.

本文提出一種自適應(yīng)的多核學(xué)習(xí)算法(self-adaptive multiple kernel learning, SaMKL), 該算法能根據(jù)數(shù)據(jù)分布有效地將特征空間進行劃分, 并解決核函數(shù)參數(shù)的優(yōu)化問題, 避免了傳統(tǒng)人為設(shè)計核函數(shù)組合的主觀性, 從而提高了尋找最優(yōu)核參數(shù)的速度.

1 自適應(yīng)多核學(xué)習(xí)算法

為進一步提升多核學(xué)習(xí)的性能, 本文提出一種自適應(yīng)的多核學(xué)習(xí)算法. 首先, 進行基于聚類的相似維發(fā)現(xiàn), 根據(jù)不同數(shù)據(jù)集的數(shù)據(jù)分布對特征進行聚類, 在每個聚簇內(nèi)進行基于相似維的單核學(xué)習(xí), 即利用SVM對每個聚簇進行學(xué)習(xí)； 其次, 為進一步提升學(xué)習(xí)效果, 采用蟻群算法優(yōu)化每個SVM的核參數(shù), 從而得到最優(yōu)的核函數(shù)組合； 最后, 利用算法集成層將生成的各最優(yōu)核函數(shù)組合, 生成最優(yōu)的學(xué)習(xí)結(jié)果. 算法流程如圖1所示.

1.1 基于AP聚類的相似維發(fā)現(xiàn)

SaMKL的自適應(yīng)性主要體現(xiàn)在可根據(jù)每個特征的不同分布, 利用不同核函數(shù)映射到不同的高維空間, 本文利用聚類算法發(fā)現(xiàn)分布相似的維度, 即相似維發(fā)現(xiàn), 然后將每組相似維映射到不同空間. AP聚類算法(affinity propagation, AP)[13]是一種基于近鄰傳播的聚類算法, 其最大特征就是無需在運行算法前人為確定聚類的個數(shù), 且聚類效果不依賴初值, 本文采用AP聚類進行相似維的發(fā)現(xiàn).

AP聚類在數(shù)據(jù)點之間存在兩類信息交換, 分別為吸引度r(i,k)和歸屬度a(i,k),r(i,k)表示數(shù)據(jù)點k適合作為數(shù)據(jù)點i聚類中心的程度,a(i,k)表示數(shù)據(jù)點i選擇數(shù)據(jù)點k作為其聚類中心的程度,s(i,k)表示數(shù)據(jù)點i和k的相似度.初始情形下,a(i,k)=0,r(i,k)采用如下公式進行更新：

(1)

a(i,k)采用如下公式進行更新：

(2)

a(k,k)的更新公式為

(3)

對于點i,a(i,k)+r(i,k)取最大值時的k值, 當(dāng)k=i時, 確定點i為一個聚類中心, 否則確定數(shù)據(jù)點k是點i的聚類中心.同時, 為防止數(shù)據(jù)震蕩, AP算法引入了衰減系數(shù), 即每個信息值等于前一次迭代更新信息值的λ倍再加上此輪更新值的(1-λ)倍. 算法流程如圖2所示.

圖1 自適應(yīng)多核算法流程Fig.1 Flow chart of self-adaptive multiple kernel algorithm

圖2 AP聚類算法流程Fig.2 Flow chart of AP clustering algorithm

1.2 基于相似維的單核學(xué)習(xí)

本文采用SVM對相似維發(fā)現(xiàn)后的數(shù)據(jù)進行單核學(xué)習(xí), SVM是常用的單核學(xué)習(xí)算法, 其基本模型是定義在特征空間上間隔最大的線性分類器. SVM的學(xué)習(xí)策略是間隔最大化, 可形式化為一個求解凸二次規(guī)劃問題, 也等價于正則化的合頁損失函數(shù)最小化問題, 其學(xué)習(xí)算法即為求解凸二次規(guī)劃的最優(yōu)化算法.

對于輸入空間中的非線性分類問題, 可通過非線性變換將其轉(zhuǎn)換為某維度特征空間中的線性分類問題, 在高維特征空間中構(gòu)建線性SVM. 由于在線性SVM學(xué)習(xí)的對偶問題中, 目標(biāo)函數(shù)和分類決策函數(shù)都只涉及實例與實例之間的內(nèi)積, 所以不需要顯式地指定非線性變換, 而是采用核函數(shù)替換其中的內(nèi)積. 核函數(shù)表示通過一個非線性轉(zhuǎn)換后兩個實例間的內(nèi)積, 設(shè)K(x,z)為一個核函數(shù), 則存在一個從輸入空間到特征空間的映射φ(x), 使得對任意輸入空間中的x,z, 均有

K(x,z)=φ(x)·φ(z).

(4)

本文采用高斯核函數(shù)(也稱為徑向基核函數(shù))：

K(xi,xj)=e-γ‖xi-xj‖2,γ>0.

(5)

由于高斯核函數(shù)是局部性較強的核函數(shù), 應(yīng)用廣泛, 無論對大樣本還是小樣本性能都較好, 因此本文選擇高斯核函數(shù)進行實驗.高斯核函數(shù)最重要的兩個參數(shù)是懲罰因子C和核函數(shù)系數(shù)γ：

1) 懲罰因子C用于控制損失函數(shù)的懲罰系數(shù), 類似于LR的正則化系數(shù).C越大, 其懲罰松弛變量越強, 使松弛變量接近0, 即對誤分類的懲罰增大, 趨向于對訓(xùn)練集全分對的情況, 會出現(xiàn)訓(xùn)練集測試時準(zhǔn)確率很高, 但泛化能力較弱, 易導(dǎo)致過擬合； 若C值較小, 則對誤分類的懲罰也較小, 容錯能力和泛化能力增強, 但也可能欠擬合.

2) 核函數(shù)系數(shù)γ表示高斯函數(shù)幅寬, 代表泛化能力.γ越大, 高斯函數(shù)越細長, 對未知樣本分類越差； 反之, 平滑效應(yīng)過大, 會影響訓(xùn)練集的識別率, 導(dǎo)致學(xué)習(xí)失敗.

1.3 基于蟻群優(yōu)化算法的核優(yōu)化

SaMKL的自適應(yīng)性還體現(xiàn)在對每個聚簇的SVM利用蟻群優(yōu)化(ant colony optimization, ACO)算法[14]進行自動參數(shù)尋優(yōu), 從而提高算法的準(zhǔn)確率. 蟻群優(yōu)化算法受螞蟻覓食行為的啟發(fā), 核心是螞蟻之間通過化學(xué)信息素進行通信. 螞蟻在路徑上釋放信息素, 當(dāng)螞蟻遇到還未走過的路口時, 就隨機挑選一條路走, 同時螞蟻釋放濃度與路徑長度成反比的信息素. 當(dāng)后來的螞蟻再次碰到該路口時, 即選擇信息素濃度較高的路徑. 這樣最優(yōu)路徑上信息素的濃度越來越大, 使螞蟻群找到了巢穴與食物源之間的最短路徑. ACO算法流程如圖3所示. SVM的參數(shù)選取是參數(shù)的組合優(yōu)化問題, 本文用ACO算法進行搜索, 最終得到每個SVM合適的參數(shù)組合.

圖3 蟻群優(yōu)化算法流程Fig.3 Flow chart of ant colony optimization algorithm

蟻群優(yōu)化算法將目標(biāo)函數(shù)作為評判優(yōu)化結(jié)果的直接因素, 本文利用F1值判斷分類算法的執(zhí)行效果.F1值在精度(precision)P與召回率(recall)R之間進行了權(quán)衡, 計算方法如下：

(6)

(7)

(8)

其中TP表示被判定為正樣本的正樣本, FP表示被判定為正樣本的負樣本, FN表示被判定為負樣本的正樣本.

綜上, 可得：

算法1自適應(yīng)多核學(xué)習(xí)算法.

步驟1) 輸入數(shù)據(jù)集, 用AP聚類算法進行相似維發(fā)現(xiàn), 將特征集合劃分為M組；

步驟2) 利用劃分好的相似維將數(shù)據(jù)集劃分為M組；

步驟3) 針對每組數(shù)據(jù)進行SVM學(xué)習(xí), 并利用蟻群算法的優(yōu)化核函數(shù)；

① 蟻群算法參數(shù)初始化, 目標(biāo)函數(shù)設(shè)置為F1值, 每只螞蟻編碼為M組位置向量(C,γ)×M；

② 根據(jù)每只螞蟻分配的位置向量, 利用訓(xùn)練集對每組數(shù)據(jù)通過SVM進行學(xué)習(xí)；

③ 初始化ACO中的信息素；

先計算當(dāng)前迭代次數(shù)條件下編號為i的螞蟻的轉(zhuǎn)移概率, 再計算當(dāng)前迭代次數(shù)條件下所有螞蟻的轉(zhuǎn)移概率；

⑤ 更新蟻群位置, 直到當(dāng)前迭代次數(shù)k下所有螞蟻的位置向量都更新完畢：

⑥ 利用信息素揮發(fā)因子與激勵因子更新當(dāng)前迭代次數(shù)k下所有螞蟻的信息素值；

⑨ 更新種群迭代次數(shù),k=k+1；

步驟4) 對M組數(shù)據(jù)進行優(yōu)化和SVM后, 針對二分類問題, 利用投票法集成每組數(shù)據(jù)的輸出, 得到最終分類結(jié)果.

2 數(shù)值實驗

2.1 數(shù)據(jù)獲取及實驗設(shè)計

UCI數(shù)據(jù)集是美國加州大學(xué)歐文分校收集的用于機器學(xué)習(xí)的數(shù)據(jù)庫, 因其數(shù)據(jù)格式標(biāo)準(zhǔn)、 內(nèi)容豐富, 所以在機器學(xué)習(xí)過程中被廣泛應(yīng)用于測試各類開發(fā)程序. 為選取適用于進行相似維發(fā)現(xiàn)及多核融合的數(shù)據(jù)集, 同時方便計算數(shù)據(jù)測試結(jié)果的F1值, 本文選擇特征數(shù)較高且數(shù)據(jù)樣本量適中的二分類數(shù)據(jù)集, 各數(shù)據(jù)集信息列于表1.

表1 數(shù)據(jù)集信息

圖4 當(dāng)C=1時, 高斯核函數(shù)下F1值與γ值的關(guān)系曲線Fig.4 Relation curve between F1 value and γ value under Gaussian kernel function when C=1

本文按8∶2將數(shù)據(jù)集分為訓(xùn)練集和測試集兩類. 為提高ACO的尋優(yōu)效率, 在實驗中對C和γ值范圍進行特別優(yōu)化.懲罰因子C表示SVM對分類錯誤的容忍程度, 為保證算法優(yōu)化結(jié)果的有效性并提高優(yōu)化效率, 將其上界設(shè)定為訓(xùn)練樣本數(shù)量的1/5, 下界設(shè)定為1.

對于參數(shù)γ, 計算默認γ值公式為

(9)

其中k為樣本類別數(shù)量, 本文采用的測試集均為二分類問題, 因此k=2,γ0=0.5.為得到γ的合理取值范圍, 以cylinder-bands作為測試集, 令γ在[0.01γ0,5γ0]內(nèi)進行搜索, 步長為0.01γ0,C=1, 所得F1值如圖4所示.由圖4可見, 當(dāng)γ=0.703時,F1取得峰值.為使蟻群移動幅度維持在一個能使優(yōu)化結(jié)果取得較優(yōu)解的范圍內(nèi), 實驗中將[0.01γ0,5γ0]設(shè)定為γ值的取值范圍.

2.2 實驗結(jié)果分析

為驗證SaMKL的效果, 本文在上述標(biāo)準(zhǔn)測試集中分別運行SVM和SaMKL, 實驗結(jié)果列于表2. 本文將ACO的各變量初始化為： 迭代次數(shù)gen=200, 種群大小m=100, 信息素揮發(fā)因子ρ=0.8, 激勵因子Q=1. 實驗結(jié)果均為10次重復(fù)實驗后所得. 由表2可見, SaMKL相比于SVM在分類準(zhǔn)確率和F1值方面均有明顯提升, 證明了SaMKL的優(yōu)勢.

表2 SVM和SaMKL實驗結(jié)果對比

3 應(yīng) 用

圖5 某學(xué)生的成長能力分布Fig.5 Distribution of a student’s growth ability

將本文算法應(yīng)用于吉林大學(xué)團委“吉小鵝”APP中. 應(yīng)用中需要體現(xiàn)學(xué)生在使用“吉小鵝”APP進行項目設(shè)計完成后的成長能力分布, 由于學(xué)生數(shù)量較大， 統(tǒng)計的相關(guān)成長因素較多， 本文算法可將多種成長因素自動歸類， 并分別進行評價， 最終通過合成層進行總體評價. 根據(jù)本文算法劃分的成長因素可被命名為成長能力、 科研能力、 領(lǐng)導(dǎo)能力、 協(xié)作能力和競賽能力， 結(jié)果如圖5所示.

綜上所述, 針對樣本基數(shù)較大、 維數(shù)較高、 特征復(fù)雜的數(shù)據(jù)集訓(xùn)練問題, 本文提出了一種自適應(yīng)多核學(xué)習(xí)算法, 該算法能自適應(yīng)地對特征進行劃分, 再基于該劃分進行多個不同的單核學(xué)習(xí), 利用蟻群算法進行自適應(yīng)地參數(shù)尋優(yōu), 并利用數(shù)據(jù)集分布自適應(yīng)地確定每個單核學(xué)習(xí)機參數(shù)的取值范圍, 通過與SVM實驗結(jié)果進行比較, 本文算法能自適應(yīng)地找到最優(yōu)的核函數(shù), 分類效果比傳統(tǒng)的單核學(xué)習(xí)SVM更優(yōu), 魯棒性與普適性更好.