基于改進(jìn)局部極化準(zhǔn)則的多核SVM模型

梁盛楠,劉文博,李雅芝

(1.黔南民族師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,貴州 都勻 558000;2.黔南民族師范學(xué)院貴州省高等學(xué)校復(fù)雜系統(tǒng)與智能優(yōu)化重點(diǎn)實(shí)驗(yàn)室,貴州 都勻 558000)

0 引言

20世紀(jì)90年代,Vapnik系統(tǒng)介紹了統(tǒng)計(jì)學(xué)習(xí)理論,同時(shí)提出了SVM算法[1].由于該算法在文本挖掘領(lǐng)域的出色表現(xiàn)[2],逐漸成為機(jī)器學(xué)習(xí)中的主流技術(shù).SVM算法取得的巨大成功正式拉開了核方法研究的序幕,并促進(jìn)了核方法的普及與應(yīng)用,使其逐步擴(kuò)展到機(jī)器學(xué)習(xí)的諸多領(lǐng)域,如模式識(shí)別[3]、特征選擇[4]等.核函數(shù)直接決定了SVM分類算法性能的優(yōu)劣,因?yàn)橐粋€(gè)恰當(dāng)?shù)暮撕瘮?shù)可以將樣本映射到一個(gè)合適的特征空間,使得同類樣本之間緊密而異類樣本之間分散.

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

針對(duì)基本核函數(shù)的構(gòu)造與多核學(xué)習(xí)中權(quán)系數(shù)的求解問題,本文提出基于改進(jìn)核極化準(zhǔn)則的多核SVM模型.受柯西密度函數(shù)啟發(fā),構(gòu)造了廣義p-范數(shù)柯西核,并給出理論證明;依據(jù)局部核極化準(zhǔn)則重新定義關(guān)聯(lián)系數(shù),建立權(quán)系數(shù)與核參數(shù)優(yōu)化目標(biāo)函數(shù),利用局部梯度與廣義拉格朗日乘子算法進(jìn)行求解,將構(gòu)造的核函數(shù)進(jìn)行核組合用于SVM分類預(yù)測(cè);實(shí)驗(yàn)分析表明,與傳統(tǒng)單核函數(shù)相比,本文提出的多核SVM模型在多數(shù)情況下其性能表現(xiàn)更好.

1 多核SVM模型

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

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

(1)

其中:ω表示分類超平面的法向量,決定了方向;b為位移項(xiàng),決定了超平面與原點(diǎn)的距離;C是懲罰系數(shù),C越大意味著誤分類產(chǎn)生的代價(jià)越高;ξi表示松弛變量,度量了真實(shí)值yi與SVM預(yù)測(cè)值之間的距離.SVM的目標(biāo)就是要最大化間隔2/‖ω‖.

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

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

(2)

b依據(jù)訓(xùn)練集中的支持向量可被求解,形式為

其中:xs為支持向量,n′為支持向量的個(gè)數(shù).

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

由于不同的核適用領(lǐng)域不盡相同,為了將不同核函數(shù)的優(yōu)勢(shì)進(jìn)行集成,最為直接的想法就是將多個(gè)不同的單核進(jìn)行組合,基本形式為

(3)

(4)

2 廣義p-范數(shù)柯西核

SVM的性能表現(xiàn)絕大程度上取決于核函數(shù)與核參數(shù)的選取,這就需要嘗試構(gòu)造新類型的核函數(shù),使得SVM可適用于不同領(lǐng)域的數(shù)據(jù)分析.受到柯西概率密度函數(shù)的啟發(fā),本節(jié)將構(gòu)造廣義柯西核函數(shù)并將其擴(kuò)展為廣義p-范數(shù)柯西核.

柯西概率密度函數(shù)為

(5)

(6)

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

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

定理2 當(dāng)α>0,β>0時(shí),(6)式為核函數(shù),其中x>0.

證明對(duì)(6)式求n階導(dǎo)數(shù)可得

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)完全單調(diào),根據(jù)定理1可得(6)式為核函數(shù).

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

(7)

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

定理3 當(dāng)α>0,β>0,ν>0時(shí),(7)式為核函數(shù),其中x>0.

證明對(duì)(7)式求n階導(dǎo)數(shù)可得

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.

依據(jù)定理1,當(dāng)α>0,β>0,ν>0時(shí),f(x)完全單調(diào),所以f(x)=(α/(x+β))ν為核函數(shù).

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

(8)

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

3 核權(quán)重與核參數(shù)優(yōu)化

本文依據(jù)核匹配準(zhǔn)則,建立優(yōu)化模型對(duì)核權(quán)重、核參數(shù)進(jìn)行求解.該方法只依賴于訓(xùn)練樣本且與后續(xù)分類器無關(guān),因此該策略因?qū)崿F(xiàn)簡單而被廣為使用.

3.1 核匹配準(zhǔn)則

對(duì)核權(quán)重進(jìn)行優(yōu)化,其關(guān)鍵在于建立一個(gè)合理的目標(biāo)函數(shù).本文依據(jù)核匹配準(zhǔn)則建立優(yōu)化權(quán)重的目標(biāo)函數(shù).核匹配準(zhǔn)則是基于矩陣匹配原理建立的參數(shù)優(yōu)化準(zhǔn)則,其基本原理如下:

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

核匹配準(zhǔn)則的目標(biāo)就是要使得核矩陣與理想核矩陣之間的余弦相似度達(dá)到最大,其表達(dá)式如下:

(9)

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

(10)

核極化準(zhǔn)則僅考慮了類間的可分離性而忽視了類內(nèi)局部結(jié)構(gòu),Wang等[12]提出了局部核極化準(zhǔn)則(Local Kernel Polarization,LKP):

(11)

定義關(guān)聯(lián)系數(shù)Aij為

其中t>0為調(diào)節(jié)參數(shù).

3.2 核權(quán)重與核參數(shù)優(yōu)化

依據(jù)LKP的基本思想,構(gòu)建改進(jìn)的局部核極化準(zhǔn)則模型以獲取最優(yōu)的核權(quán)重與核參數(shù),改進(jìn)部分體現(xiàn)在對(duì)LKP中的關(guān)聯(lián)系數(shù)進(jìn)行重新定義,具體的優(yōu)化模型如下:

(12)

重新定義關(guān)聯(lián)系數(shù),以更好地刻畫任意兩個(gè)樣本之間的相關(guān)程度:

(13)

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

3.3 多核SVM分類模型計(jì)算過程

依據(jù)廣義p-范數(shù)柯西核構(gòu)造原理以及多核模型的建立與求解過程,加權(quán)廣義p-范數(shù)柯西核SVM分類算法的基本流程如下:

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

步驟1:將原始數(shù)據(jù)集進(jìn)行折交叉分層抽樣,將其劃分為訓(xùn)練集Ttrain與測(cè)試集Ttest;

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

步驟3:依據(jù)(13)式建立關(guān)聯(lián)系數(shù)矩陣;

步驟4:依據(jù)(12)式建立核權(quán)重與和參數(shù)優(yōu)化的目標(biāo)函數(shù);

步驟5:基于訓(xùn)練集利用具體的優(yōu)化算法對(duì)模型(12)進(jìn)行求解,獲取最優(yōu)的權(quán)重系數(shù)ωi與核參數(shù);

步驟6:將步驟5中得到的最優(yōu)核權(quán)重與核參數(shù)帶入到(3)式中;

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

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

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

4.1 實(shí)驗(yàn)設(shè)定

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

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

為了比較不同核函數(shù)對(duì)SVM分類性能的影響,實(shí)驗(yàn)采用5折交叉驗(yàn)證劃分訓(xùn)練集與測(cè)試集,評(píng)價(jià)準(zhǔn)則采用分類精度、Kappa系數(shù).將不同的核SVM方法分別記為PolyK+SVM、SigK+SVM、GauK+SVM、LapK+SVM和WGpCK+SVM.

4.2 對(duì)比實(shí)驗(yàn)

表2 基于不同核函數(shù)的SVM算法5折交叉驗(yàn)證分類精度

表3 基于不同核函數(shù)的SVM算法5折交叉驗(yàn)證分類Kappa系數(shù)

通過表2—3的實(shí)驗(yàn)結(jié)果可知,將廣義p-范數(shù)柯西核進(jìn)行加權(quán)組合,將其應(yīng)用于SVM算法對(duì)5個(gè)真實(shí)數(shù)據(jù)集進(jìn)行分類預(yù)測(cè)時(shí),WGpCK+SVM算法在精度上有4處達(dá)到最優(yōu),1處達(dá)到次最優(yōu);在Kappa系數(shù)上有4處達(dá)到最優(yōu),1處達(dá)到次最優(yōu).在分析的5個(gè)數(shù)據(jù)集上,WGpCK+SVM有8處達(dá)到最優(yōu),2處達(dá)到次最優(yōu),表明本文構(gòu)造的廣義p-范數(shù)柯西核,在多數(shù)情形下可以有效提高SVM算法的分類預(yù)測(cè)性能.

4.3 p-范數(shù)距離顯著性分析

對(duì)于WGpCK +SVM算法,當(dāng)面對(duì)不同的數(shù)據(jù)集時(shí)設(shè)定了不同的p-范數(shù)距離,因?yàn)樵趯?shí)驗(yàn)分析的過程中發(fā)現(xiàn),在廣義p-范數(shù)柯西核中取定不同的范數(shù)會(huì)影響到SVM算法的分類性能,具體情況見圖1,其中p的取值范圍設(shè)置成[1,50]步長為0.5.

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

5 結(jié)論

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