基于改進局部極化準則的多核SVM模型

梁盛楠,劉文博,李雅芝

(1.黔南民族師范學院數學與統計學院,貴州 都勻 558000;2.黔南民族師范學院貴州省高等學校復雜系統與智能優化重點實驗室,貴州 都勻 558000)

0 引言

20世紀90年代,Vapnik系統介紹了統計學習理論,同時提出了SVM算法[1].由于該算法在文本挖掘領域的出色表現[2],逐漸成為機器學習中的主流技術.SVM算法取得的巨大成功正式拉開了核方法研究的序幕,并促進了核方法的普及與應用,使其逐步擴展到機器學習的諸多領域,如模式識別[3]、特征選擇[4]等.核函數直接決定了SVM分類算法性能的優劣,因為一個恰當的核函數可以將樣本映射到一個合適的特征空間,使得同類樣本之間緊密而異類樣本之間分散.

由于不同核函數具有不同特性,因此在不同的應用場景,核函數所表現出的性能差別也較大.為了提升核函數的靈活性、適用性,將多個核函數進行核組合,即多核學習受到越來越多學者的關注.Yang等[5]提出多核學習支持向量機粒子群優化模型對肺結節進行識別,獲得了更好的識別效率.高巍等[6]提出了一種用于高光譜圖像分類的馬氏距離多核學習方法,將馬氏基本核進行線性加權組合,將高光譜數據映射到一個類內距離更小、類間距離更大的特征空間后進行分類.Gone等[7]將典型的多核學習算法進行分類總結,通過理論與實驗分析得出多核學習可以提高預測精度、降低訓練時間.上述研究工作已經證明利用多核替代單核可以增強決策函數的可解釋性,使學習器獲取更優的性能.

針對基本核函數的構造與多核學習中權系數的求解問題,本文提出基于改進核極化準則的多核SVM模型.受柯西密度函數啟發,構造了廣義p-范數柯西核,并給出理論證明;依據局部核極化準則重新定義關聯系數,建立權系數與核參數優化目標函數,利用局部梯度與廣義拉格朗日乘子算法進行求解,將構造的核函數進行核組合用于SVM分類預測;實驗分析表明,與傳統單核函數相比,本文提出的多核SVM模型在多數情況下其性能表現更好.

1 多核SVM模型

支持向量機(Support Vector Machine,SVM)是基于“結構風險最小化原則”面向二分類問題的判別分類算法,也可推廣到多類分類問題中.它的基本模型是定義在特征空間上的間隔最大線性分類器,由于核函數的引入,使其實質上成為非線性分類器.

給定訓練集T={(xi,yi)|xi∈p,yi∈{+1,-1},i=1,…,n}.其中:n表示樣本容量,xi表示具有p個特征的輸入向量,yi表示對應于xi的類別標簽.SVM可形式化為如下凸二次規劃問題:

(1)

其中:ω表示分類超平面的法向量,決定了方向;b為位移項,決定了超平面與原點的距離;C是懲罰系數,C越大意味著誤分類產生的代價越高;ξi表示松弛變量,度量了真實值yi與SVM預測值之間的距離.SVM的目標就是要最大化間隔2/‖ω‖.

基于核技巧的SVM是通過非線性映射φ(x),將樣本從原始空間映射到一個高維特征空間中,使得樣本在該特征空間中線性可分.φ(x)的形式往往未知,引入形式已知的核函數[8]代替復雜的內積運算,即κ(xi,xj)=φ(xi)·φ(xj).

在求解SVM的過程中,一般用到模型(1)的對偶形式

(2)

b依據訓練集中的支持向量可被求解,形式為

其中:xs為支持向量,n′為支持向量的個數.

最終的分類超平面或SVM分類器為

由于不同的核適用領域不盡相同,為了將不同核函數的優勢進行集成,最為直接的想法就是將多個不同的單核進行組合,基本形式為

(3)

(4)

2 廣義p-范數柯西核

SVM的性能表現絕大程度上取決于核函數與核參數的選取,這就需要嘗試構造新類型的核函數,使得SVM可適用于不同領域的數據分析.受到柯西概率密度函數的啟發,本節將構造廣義柯西核函數并將其擴展為廣義p-范數柯西核.

柯西概率密度函數為

(5)

(6)

其中x,α,β>0.那么(6)式能否作為核函數,可由定理1—2給出.

定理1[9]若X?n,f：(0,∞)→,κ是X×X上的函數且κ(x,z)=f(‖x-z‖2),則當f完全單調時,κ(x,z)是正定核.

定理2 當α>0,β>0時,(6)式為核函數,其中x>0.

證明對(6)式求n階導數可得

f′(x)=-α(x+β)-2,…,f(n)(x)=(-1)nα(x+β)-(n+1),

由于α>0,β>0,有

(-1)nf(n)(x)=(-1)2nα(x+β)-(n+1)=α(x+β)-(n+1)≥0.

因此f(x)完全單調,根據定理1可得(6)式為核函數.

將核函數(6)式推廣為如下形式:

(7)

需要考慮參數v滿足什么條件可以使上式成為核函數.

定理3 當α>0,β>0,ν>0時,(7)式為核函數,其中x>0.

證明對(7)式求n階導數可得

f(n)(x)=(-1)nανv(v+1)…(v+(n-1))(x+β)-(v+n),

(-1)nf(n)(x)=(-1)2nανv(v+1)…(v+(n-1))(x+β)-(v+n).

若保證(-1)nf(n)(x)≥0,則需ν≥0.

依據定理1,當α>0,β>0,ν>0時,f(x)完全單調,所以f(x)=(α/(x+β))ν為核函數.

在具體的應用中,(7)式取如下形式:

(8)

(8)式稱為具有p-范數距離形式的廣義柯西核函數,簡稱廣義p-范數柯西核.

3 核權重與核參數優化

本文依據核匹配準則,建立優化模型對核權重、核參數進行求解.該方法只依賴于訓練樣本且與后續分類器無關,因此該策略因實現簡單而被廣為使用.

3.1 核匹配準則

對核權重進行優化,其關鍵在于建立一個合理的目標函數.本文依據核匹配準則建立優化權重的目標函數.核匹配準則是基于矩陣匹配原理建立的參數優化準則,其基本原理如下:

給定訓練集T={(xi,yi)|xi∈p,yi∈{1,2,…,l}}.核矩陣Κ=(κ(xi,xj))n×n,令Y=yyT=(yij)n×n為類標簽矩陣,也稱為理想核矩陣:

核匹配準則的目標就是要使得核矩陣與理想核矩陣之間的余弦相似度達到最大,其表達式如下:

(9)

其中:〈·,·〉F為Frobenius內積,‖·‖F為Frobenius范數.文獻[10]證明了核匹配準則的可靠性、實用性以及核分類器泛化誤差的有界性.在(9)式的基礎上,Baram[11]提出了核極化準則(Kernel Polarization,KP):

(10)

核極化準則僅考慮了類間的可分離性而忽視了類內局部結構,Wang等[12]提出了局部核極化準則(Local Kernel Polarization,LKP):

(11)

定義關聯系數Aij為

其中t>0為調節參數.

3.2 核權重與核參數優化

依據LKP的基本思想,構建改進的局部核極化準則模型以獲取最優的核權重與核參數,改進部分體現在對LKP中的關聯系數進行重新定義,具體的優化模型如下:

(12)

重新定義關聯系數,以更好地刻畫任意兩個樣本之間的相關程度:

(13)

對模型(12)的求解采用局部梯度與廣義拉格朗日乘子相結合的優化算法[13-14],模型的梯度形式如下:

3.3 多核SVM分類模型計算過程

依據廣義p-范數柯西核構造原理以及多核模型的建立與求解過程,加權廣義p-范數柯西核SVM分類算法的基本流程如下:

輸入:訓練樣本集Ttrain={(xi,yi)|xi∈p,yi∈Y,i=1,2,…,n},其中Y={1,2,…,l}表示類別標簽;

步驟1:將原始數據集進行折交叉分層抽樣,將其劃分為訓練集Ttrain與測試集Ttest;

步驟2:依據(3)式選取具體的核函數;

步驟3:依據(13)式建立關聯系數矩陣;

步驟4:依據(12)式建立核權重與和參數優化的目標函數;

步驟5:基于訓練集利用具體的優化算法對模型(12)進行求解,獲取最優的權重系數ωi與核參數;

步驟6:將步驟5中得到的最優核權重與核參數帶入到(3)式中;

步驟7:將步驟6中得到的(3)式帶入到模型(4),得到具體的多核SVM的對偶基本型;

步驟8:利用分層抽樣得到的訓練集Ttrain對模型(4)進行擬合;

4 實驗結果與分析

4.1 實驗設定

為了驗證本文構造的加權廣義p-范數柯西核(Weight Generalizedp-Norm Cauchy Kernel,WGpCK)對SVM分類性能的影響,將其與多個傳統的單核函數進行對比,包括多項式核(Polynomial Kernel,PolyK)、雙曲正切核(Sigmoid Kernel,SigK)、高斯核(Gaussian Kernel,GauK)與拉普拉斯核(Laplace Kernel,LapK).本文提出的算法和實驗基于R語言(版本號:3.6.3)編碼實現.實驗數據包括:慢性腎病(Kidney)、皮膚病(Dermatology)、皮馬族糖尿病(Pima)、結腸癌(Colon)和乳腺癌(Breast)基因表達數據集,信息見表1.

表1 數據集信息

為了比較不同核函數對SVM分類性能的影響,實驗采用5折交叉驗證劃分訓練集與測試集,評價準則采用分類精度、Kappa系數.將不同的核SVM方法分別記為PolyK+SVM、SigK+SVM、GauK+SVM、LapK+SVM和WGpCK+SVM.

4.2 對比實驗

表2 基于不同核函數的SVM算法5折交叉驗證分類精度

表3 基于不同核函數的SVM算法5折交叉驗證分類Kappa系數

通過表2—3的實驗結果可知,將廣義p-范數柯西核進行加權組合,將其應用于SVM算法對5個真實數據集進行分類預測時,WGpCK+SVM算法在精度上有4處達到最優,1處達到次最優;在Kappa系數上有4處達到最優,1處達到次最優.在分析的5個數據集上,WGpCK+SVM有8處達到最優,2處達到次最優,表明本文構造的廣義p-范數柯西核,在多數情形下可以有效提高SVM算法的分類預測性能.

4.3 p-范數距離顯著性分析

對于WGpCK +SVM算法,當面對不同的數據集時設定了不同的p-范數距離,因為在實驗分析的過程中發現,在廣義p-范數柯西核中取定不同的范數會影響到SVM算法的分類性能,具體情況見圖1,其中p的取值范圍設置成[1,50]步長為0.5.

從圖1中可以明顯地看出,Colon、Kidney和Pima數據集的精度、Kappa系數都隨著p-范數距離的增加呈現出較為顯著的變化.對于Pima與Kidney數據集,其2個評價指標值逐漸增加到一個最高點,然后總體呈下降趨勢,中間略有波動,最后趨于平穩.對于Colon數據集,其3個評價指標值隨p-范數變化呈現出明顯的隨機波動趨勢.對于Breast數據集,其精度和Kappa系數達到最高點后開始下降并基本維持在一個水平上.對于Dermatology數據集,其評價指標值只是隨p-范數變化產生了微小的波動.從圖1的可視化結果可以得出,設定不同的p-范數距離在有些數據集上對分類算法性能產生了顯著影響,而在有些數據集上影響不顯著.

5 結論

依據柯西概率密度函數,本文構造了廣義p-范數柯西核.將核函數進行加權組合,依據局部核匹配準則,建立優化模型對權系數、核參數進行求解.將最終得到的多核模型應用于SVM分類,通過在5個醫學數據集上的實驗分析,與傳統的單核相比,本文提出的多核SVM模型具有更好的分類預測性能,這對正確識別正常人群與患病人群、不同類型癌癥基因有著重要應用價值.通過可視化分析了p-范數距離對WGpCK+SVM算法預測性能的影響,得出針對不同的數據集,不同的范數距離會對算法性能產生不同的影響效果,有的影響顯著,有的影響微小.在未來的工作中,可以將提出的多核SVM模型應用于金融、經濟等領域,如股票收益率預報、企業信用評級等.