核對齊多核模糊支持向量機

何強，張嬌陽

（北京建筑大學 理學院，北京 100044）

支持向量機(SVM)是Vapnik 等人于1995 年提出，以統(tǒng)計學習理論為基礎建立起來的一類新的機器學習算法[1]。它以最小化結構風險[2]為原則來提高學習機泛化能力，實現期望風險的最小化，從而達到在統(tǒng)計樣本量較少的情況下，亦能獲得良好統(tǒng)計規(guī)律的目的。SVM 能夠很好地解決小樣本、非線性、高維度、局部極小等問題，現已被應用到很多領域，如文本分類、語音識別、情感分析、回歸分析等。

隨著SVM 的不斷發(fā)展和應用，其部分局限性也逐漸顯露出來，在很多方面的研究還有待探索和改進。例如，SVM 易受到噪聲和孤立點影響，為解決此問題，Lin 等[3]提出了模糊支持向量機(fuzzy support vector machine，FSVM)的概念，即將模糊隸屬度引入到支持向量機中。FSVM 降低了噪聲和孤立點對最終決策函數的影響，提高了分類精度，現在也應用到了風險預測、故障診斷、手寫字符串識別等領域。

此外，SVM 中核函數和核參數的選擇對最終的學習結果有著重要影響，然而目前還沒有關于核函數以及核參數選取的有效手段。作為核方法的重要成果，多核學習(multiple kernel learning，MKL)[4-5]近年來已成為機器學習領域廣大學者的研究熱點。單一核函數往往無法充分刻畫數據間的相似性，尤其是復雜數據間的相似性，不同的核函數對應于不同的相似性表示，多核相結合可以較準確的表達數據間的相似性，同時也克服了核函數選擇這一難題。受模糊支持向量機和多核學習的啟發(fā)，為了同時解決這兩大問題，本文提出模糊多核支持向量機模型。

本文的主要工作有：1) 將基于核對齊[6]的多核學習方法引入到模糊支持向量機中，提出了基于核對齊的模糊多核支持向量機，同時解決了核函數選擇難題和對噪聲數據敏感問題；2)利用基于Gaussian 核的模糊粗糙集下近似算子來確定每個樣本點的隸屬度[7]，更有效地減小噪聲點和孤立點對分類超平面的影響；3)根據最大化組合核與理想核之間的相似性，計算核權重，使組合核更精確地刻畫數據間的相似性；4)實驗結果驗證了本文所提方法比經典支持向量機(SVM)、模糊支持向量機(FSVM)和多核支持向量機(MSVM)表現更為優(yōu)異。

1 相關工作

1.1 經典支持向量機

對于給定數 據T={(x1,y1),(x2,y2),···,(xl,yl)}，其中xi∈Rn，yi∈{-1,1}，i=1,2,···,l。SVM 的目標是得到最優(yōu)超平面f(x)=ωTx+b，其不僅能將這組數據正確分為兩類，同時能夠保證兩類樣本到分類超平面的距離之和最大。根據結構風險最小化原則，可將尋找最優(yōu)超平面的過程歸結為如下的優(yōu)化問題[1-2]：

式中： ξi為誤差項；C為懲罰系數。

利用Lagrange 乘子法，上述優(yōu)化問題可轉化為如下對偶問題：

式中： αi是樣本點xi的Lagrange 乘子； 〈·,·〉 表示內積。最終得到的分類決策函數有如下形式：

對于線性不可分數據，雖然通過引入誤差項ξi可以得到分割超平面，然而其并無法實現對所有樣例的正確劃分。引入非線性映射 φ :Rn→H，將數據從原空間映射到高維特征空間中，并在該空間中構造最優(yōu)分割超平面。由SVM 模型可知，只需要計算出 φ (x) 和 φ (x′) 的內積。通過核函數k(x,x′)[2]可以獲得兩點在特征空間中的內積：

則(2)式可轉化為

所以在實際應用中并不需要知道 φ，只通過核函數k(x,x′) 就可以得到相應的決策函數：

常用的核函數主要有線性核、多項式核和Gaussian 核[1-2]。

1.2 模糊支持向量機

在實際問題中，數據易受到噪聲等各種因素的干擾，SVM 往往難以獲得令人滿意的學習效果。為了有效地排除不確定環(huán)境中野點（標簽錯誤的訓練樣本）的干擾，2002 年Lin 將樣本隸屬度引入SVM，使樣本由于隸屬度的不同而對超平面有不同的影響，得到模糊支持向量機(FSVM)[3,8]。野點和噪聲數據往往被賦予較小的隸屬度，從而削弱其對于分類超平面的影響。FSVM 對應如下優(yōu)化問題：

這 里si是 樣 例xi屬 于 類 別yi的 隸 屬 度 。 顯然si對目標函數中的 ξi起加權作用，使得噪聲點對最終得到的超平面有較小的影響。該算法增強了SVM 的魯棒性。

由Lagrange 乘子法可將式(7)轉化為對偶形式：

分類決策函數為

經過不斷發(fā)展，基于上述FSVM 算法，其他學者也提出了各種模糊SVM 來處理不同的具體問題。這些方法都是針對實際問題中的某種不確定性而提出的，是對傳統(tǒng)SVM 的改進與完善。

2 多核學習

在支持向量機處理分類問題時，核函數的選擇對分類效果有非常重要的影響。在核函數選擇的過程中，普遍采用試算方法，核函數與核參數選擇的計算代價較大。多核學習將多個核函數組合在一起，取代了經典支持向量機的單個核函數。多核組合往往能夠更加準確地刻畫樣本間的相似性，從而使得SVM 在相對較小的計算開銷前提下，獲得了較好的分類性能。

多核支持向量機(MSVM)主要研究問題為核函數的組合方式和相關權系數的計算。目前來說，核函數的組合方式可以分為以下3 種：

1）線性組合方式[9]，也是現在使用最廣泛的方式，如簡單單核相加和加權線性組合：

式中： ηm為核權重， ηm都為1 時即為簡單單核相

加；p為核函數個數。

2）非線性組合方式[10]，例如乘積、點積和冪：

3）數據相關組合方式[11]，這種方式會對每個數據樣本分配一個特定的權重，這樣可以得到數據的局部分布狀況，進而根據分布情況對每個區(qū)域學習到合適的組合規(guī)則。

多核權系數的計算在多核學習研究中是關鍵問題，目前，相關權系數的計算方式具體來說有以下5 類：固定規(guī)則學習方式[12]、啟發(fā)式學習方式[6,13]、最優(yōu)化求解方式[14]、貝葉斯學習方式[11]和Boosting 學習方式[15]。

本文中采用啟發(fā)式學習方式來獲得核權重，通過核對齊[6,16-18]的方式計算多核權系數，即計算核函數相應核矩陣之間的相似性來確定權系數。基于訓練集T，兩個核函數k1和k2對應的核矩陣K1與K2之間的核對齊定義為

多核SVM 的優(yōu)化問題由(1)轉化為

式中：ωη為高維特征空間中分類超平面的法向量，映射 Φη將數據由原空間映射到高維特征空間。分類決策函數變?yōu)?/p>

3 模糊多核支持向量機

針對核函數選擇難題和對噪聲數據敏感問題，本文將基于核對齊加權求和多核學習方法引入到模糊支持向量機模型中，并利用模糊粗糙集方法得到樣例隸屬度，提出了基于核對齊的模糊多核支持向量機(multiple kernel fuzzy support vector machine, MFSVM)。

粗糙集(RS) 是20 世紀80 年代波蘭學者Pawlak 提出的一種不確定性數學理論[19]，可以對數據進行分析和推理，從中發(fā)現隱含的知識。經典的RS 理論建立在等價關系基礎上，其只能處理符號數據。作為RS 的推廣，模糊粗糙集(FRS)技術可以處理實值數據。FRS 理論最早是由Dubois 和Prade 提出[20-21]，之后得到了快速發(fā)展。現有的FRS 方法已經被成功應用于很多實際問題。本文中，使用基于Gaussian 核的FRS 的下近似算子來作為事例的隸屬度[7,22]。取k(x,x′) 為Gaussian 核函數。對樣√例xi∈A， 令si為xi屬于A的隸屬度，則

本文采用基于核對齊加權求和的多核組合方式，多核組合公式為

式中： ηm是核權重，m=1,2,···,p；Km是一組基礎核矩陣，m=1,2,···,p，優(yōu)化目標為最大化組合核與理想核的相似性，即(可得到如)下公式[6,23]：

通過Lagrange 乘子法，轉化為其對偶問題：

觀察式 (18)， λ 隨著C的變化而變化，根據核對齊的定義，當核權重 ηm做線性變化時，核對齊的值保持不變，所以可考慮λ=1，那么式 (18) 優(yōu)化問題變?yōu)?/p>

為了避免核函數在訓練集中過擬合，在優(yōu)化問題中添加對 ηm的約束，即變?yōu)?/p>

由于式 (21) 是凸二次規(guī)劃問題，所以可求得 η 的唯一解，代入式(15)后得到合成核，再將其引入到上述基于模糊粗糙集隸屬度的模糊支持向量機中，優(yōu)化問題即變?yōu)?/p>

引入Langrange 乘子，其對偶問題由式(8)可轉化為

決策函數為

基于核對齊的模糊多核支持向量機的算法實現流程圖如圖1 所示。

圖1 算法流程圖Fig.1 Flow chart of algorithm

4 實驗仿真

UCI 數據庫是加州大學歐文分校提出的用于機器學習的數據庫，是常用的標準測試數據庫集，為了驗證本文所提出方法的可行性與有效性，本文在UCI 中選取了9 個數據集，有關信息如表1 所示。由于本文只考慮兩類分類問題，所以對于wine 數據集，將類別2 與3 視為一類處理。

表1 實驗數據信息Table 1 Data information

實驗在一臺PC 機（CPU：2.6 GHz，內存4 GB）上進行，操作系統(tǒng)為Windows 8.1，實驗工具為Matlab R2014b。實驗中將所有數據都做歸一化處理，核函數采用的是不同核參數的Gaussian 核。給定懲罰系數C=100，解核對齊優(yōu)化問題時的參數 δ =102。選擇7 個參數 σ 不同的Gaussian 核作為基礎核，每個數據集對應的核參數如表2 所示。所有精度都采用10 折交叉驗證方式獲得，其中單核支持向量機結果為不同參數Gaussian 核精度最大值。實驗對本文提出的基于粗糙集隸屬度的模糊多核支持向量機(MFSVM)和經典支持向量機(SVM)、模糊支持向量機(FSVM)、多核支持向量機(MSVM)的分類性能進行對比。

無噪聲情況下實驗結果如表3 所示。從實驗結果可以看出，在無噪聲的情況下，本文提出的MFSVM 方法在9 個數據集中分類精度最高，其中在lymphography 數據集和wine 數據集中，MFSVM 和MSVM 分類精度一樣，并且比SVM 和FSVM 的分類精度高，而且在計算效率方面，MSVM 與MFSVM 比SVM 和FSVM 顯著提高。

表2 高斯核參數設置Table 2 Parameters setting of base kernel

表3 無噪聲情況下分類精度與訓練時間比較Table 3 Comparison of classification accuracy and training time without noise

為了進一步驗證MFSVM 在噪聲環(huán)境中的表現，接下來在所有9 個數據集中都隨機選擇一定比例的分類超平面附近訓練樣本改變其類標簽。通過這樣的方式構造了帶有10%、20%的噪聲水平的數據。表4 和表5 分別是噪聲比例為10%和20%時，4 種算法的測試精度比較結果。

從實驗結果可以看出，當加入10% 的噪聲時，MFSVM 方法在所有9 個數據集中的分類精度均高于其他3 種方法，具有最高的分類精度。在噪聲比例為20%的情況下，雖然4 種方法的分類精度較于表4 中都相對變低，但在所有數據庫上，MFSVM 都具有最高的分類精度。該結果也進一步驗證了，本文所提出的MFSVM 方法在抗噪聲能力與計算開銷兩方面集中了MSVM 與FSVM 的優(yōu)勢，不僅避免了核選擇難題，而且具有較強的抗噪聲能力。從而MFSVM 不僅可行，且有更廣的應用范圍。

表4 10%噪聲下分類精度與訓練時間比較Table 4 Comparison of classification accuracy and training time with 10% noise

表5 20%噪聲下分類精度與訓練時間比較Table 5 Comparison of classification accuracy and training time with 20% noise

5 結論

本文是在模糊支持向量機和多核學習的基礎之上，通過將基于核對齊的多核方法引入到模糊支持向量機中，提出了基于核對齊的模糊多核支持向量機模型。實驗仿真表明此方法綜合了模糊支持向量機和多核學習的優(yōu)點，在分類性能上有一定程度的提升，特別是在有噪聲的樣本中表現更為突出，證實了本文方法在解決核函數選擇難和對噪聲數據敏感問題上的可行性和有效性。由于本文方法中涉及到了多核組合和隸屬度的計算，因此下一步將進一步研究更優(yōu)的核組合方式以及如何改進樣本隸屬度的計算。

參考文獻：：

[1]VAPNIK V N.The nature of statistical learning theory[M].2nd ed.New York: Springer-Verlag, 1999: 69-110.

[2]鄧乃揚, 田英杰.支持向量機: 理論、算法與拓展[M].北京: 科學出版社, 2009: 115-132.

[3]LIN Chunfu, WANG Shengde.Fuzzy support vector machines[J].IEEE transactions on neural networks, 2002,13(2): 464-471.

[4]SIAHROUDI S K, MOODI P Z, BEIGY H.Detection of evolving concepts in non-stationary data streams: a multiple kernel learning approach[J].Expert systems with applications, 2018, 91: 187-197.

[5]GONEN M, ALPAYDIN E.Multiple kernel learning algorithms[J].Journal of machine learning research, 2011,12: 2211-2268.

[6]CRISTIANINI N, SHAWE-TAYLOR J, ELISSEEFF A, et al.On kernel-target alignment[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic.Vancouver,Canada, 2001: 367-373.

[7]HE Qiang, WU Congxin.Membership evaluation and feature selection for fuzzy support vector machine based on fuzzy rough sets[J].Soft computing, 2011, 15(6):1105-1114.

[8]LIN Chunfu, WANG Shengde.Training algorithms for fuzzy support vector machines with noisy data[J].Pattern recognition letters, 2004, 25(14): 1647-1656.

[9]CRISTIANINI N, SHAWE-TAYLOR J.An introduction to support vector machines and other kernel-based learning methods[M].Cambridge: Cambridge University Press,2000: 1-28.

[10]DE DIEGO I M, MU?OZ A, MOGUERZA J M.Methods for the combination of kernel matrices within a support vector framework[J].Machine learning, 2010,78(1/2): 137-174.

[11]CHRISTOUDIAS C M, URTASUN R, DARRELL T.Bayesian localized multiple kernel learning.Technical Report No.UCB/EECS-2009-96[R].Berkeley: University of California, 2009: 1531-1565.

[12]BEN-HUR A, NOBLE W S.Kernel methods for predicting protein-protein interactions[J].Bioinformatics, 2005, 21(S1).

[13]QIU Shibin, LANE T.A Framework for multiple kernel support vector regression and its applications to siRNA efficacy prediction[J].IEEE/ACM transactions on computational biology and bioinformatics, 2009, 6(2): 190-199.

[14]VARMA M, RAY D.Learning the discriminative powerinvariance trade-off[C]//Proceedings of 2007 IEEE 11th International Conference on Computer Vision.Rio de Janeiro, Brazil, 2007: 1-8.

[15]杜海洋.簡化多核支持向量機的研究[D].北京: 北京交通大學, 2015: 13-25.DU Haiyang.Research of reduced multiple kernel support vector machine[D].Beijing: Beijing Jiaotong University, 2015: 13-25.

[16]WANG Tinghua, ZHAO Dongyan, TIAN Shengfeng.An overview of kernel alignment and its applications[J].Artificial intelligence review, 2015, 43(2): 179-192.

[17]ZHONG Shangping, CHEN Daya, XU Qianfen, et al.Optimizing the Gaussian kernel function with the formulated kernel target alignment criterion for two-class pattern classification[J].Pattern recognition, 2013, 46(7):2045-2054.

[18]劉向東, 駱斌, 陳兆乾.支持向量機最優(yōu)模型選擇的研究[J].計算機研究與發(fā)展, 2005, 42(4): 576-581.LIU Xiangdong, LUO Bin, CHEN Zhaoqian.Optimal model selection for support vector machines[J].Journal of computer research and development, 2005, 42(4):576-581.

[19]周煒, 周創(chuàng)明, 史朝輝, 等.粗糙集理論及應用[M].北京: 清華大學出版社, 2015: 57-64.

[20]DUBOIS D, PRADE H.Rough fuzzy sets and fuzzy rough sets[J].International journal of general systems,1990, 17(2/3): 191-209.

[21]DUBOIS D, PRADE H.Putting rough sets and fuzzy sets together[M]//S?OWI?SKI R.Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht, Netherlands: Springer,1992: 203-232.

[22]CHEN Degang, YANG Yongping, WANG Hui.Granular computing based on fuzzy similarity relations[J].Soft computing, 2011, 15(6): 1161-1172.

[23]CHEN Linlin, CHEN Degang, WANG Hui.Alignment based kernel selection for multi-label learning[J].Neural processing letters, 2019, 49(3): 1157-1177.