基于模糊多核學(xué)習(xí)的改進(jìn)支持向量機(jī)算法研究

劉建峰，淦 燕

(1.重慶三峽學(xué)院 教務(wù)處，重慶 404100; 2.電子科技大學(xué) 計(jì)算機(jī)視聽覺實(shí)驗(yàn)室，重慶 404100)

?

基于模糊多核學(xué)習(xí)的改進(jìn)支持向量機(jī)算法研究

劉建峰1，淦 燕2

(1.重慶三峽學(xué)院 教務(wù)處，重慶 404100; 2.電子科技大學(xué) 計(jì)算機(jī)視聽覺實(shí)驗(yàn)室，重慶 404100)

針對(duì)傳統(tǒng)SVM對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感的問題，以及不能解決樣本特征規(guī)模大、含有異構(gòu)信息、在特征空間中分布不平坦的問題，將模糊隸屬度融入多核學(xué)習(xí)中，提出了一種模糊多核學(xué)習(xí)的方法；通過實(shí)驗(yàn)驗(yàn)證了模糊多核學(xué)習(xí)比傳統(tǒng)SVM、模糊支持向量機(jī)以及多核學(xué)習(xí)具有更好的分類效果，從而驗(yàn)證了所提方法能夠有效的克服傳統(tǒng)SVM對(duì)噪聲點(diǎn)敏感以及數(shù)據(jù)分布不平坦的問題。

支持向量機(jī)；模糊支持向量機(jī)；多核學(xué)習(xí)；模糊多核學(xué)習(xí)

0 引言

自20世紀(jì)90年代Vapnik等人提出支持向量機(jī)理論[1](Support Vector Machine, SVM)以來，已經(jīng)在手寫數(shù)字識(shí)別、語音識(shí)別、人臉識(shí)別、文本分類和醫(yī)學(xué)圖像分類等領(lǐng)域中得到廣泛應(yīng)用，均表現(xiàn)出良好的分類效果。簡(jiǎn)單地說SVM就是升維和線性化，升維即通過一個(gè)非線性映射將樣本空間映射到一個(gè)高維(或是無窮維)的特征空間，在特征空間中尋找一個(gè)最優(yōu)分類超平面，該分類超平面能將一個(gè)二分類問題正確的劃分，且要求分類間隔最大化。尋找最優(yōu)超平面的過程可以歸結(jié)為一個(gè)二次規(guī)劃問題，通過Lagrangian乘子法求出它的對(duì)偶問題的解，從而得到其本身的解。為了更好地理解SVM的本質(zhì)，需要理解以下四點(diǎn)[2]：分類面；最大間隔；軟間隔；核函數(shù)。這四點(diǎn)也說明了SVM對(duì)訓(xùn)練樣本內(nèi)的噪聲和孤立點(diǎn)非常敏感，會(huì)影響分類的正確率，為解決此問題，Lin等[3]通過引入一個(gè)模糊隸屬度函數(shù)來對(duì)每個(gè)輸入樣本賦予不同的權(quán)值，以此來構(gòu)建目標(biāo)函數(shù)，提出模糊支持向量機(jī)(fuzzy support vector machine, FSVM)。

在模糊支持向量機(jī)中，其核心是：如何構(gòu)建一個(gè)合理的模糊隸屬度函數(shù)？使得不同的樣本賦予不同的權(quán)值，而且要求對(duì)噪聲和孤立點(diǎn)賦予較小的權(quán)值，然后用不同權(quán)值的樣本來訓(xùn)練，得到一個(gè)較好的分類面，從而提高分類正確率。針對(duì)模糊隸屬段函數(shù)的構(gòu)建問題，不同的學(xué)者提出了不同的觀點(diǎn)，Lin等[4]于2004年提出了帶有噪聲數(shù)據(jù)的模糊支持向量機(jī)訓(xùn)練算法，通過使用啟發(fā)函數(shù)來構(gòu)建模糊隸屬度函數(shù)。Jiang等[5]于2006年提出了一種新的模糊隸屬度模糊支持向量機(jī)，該方法先將樣本空間的映射到特征空間，再確定模糊隸屬度函數(shù)。

無論是SVM，還是模糊支持向量機(jī)，均是單核的形式進(jìn)行學(xué)習(xí)的，單核函數(shù)主要有兩種類型[6]：局部核函數(shù)和全局核函數(shù)。局部核函數(shù)允許相距較近的點(diǎn)對(duì)核函數(shù)的值有影響，而全局核函數(shù)則允許相距較遠(yuǎn)的點(diǎn)對(duì)核函數(shù)的值有影響。近些年隨著SVM的應(yīng)用和發(fā)展，使用單核核函數(shù)不能解決樣本特征規(guī)模大、含有異構(gòu)信息、在特征空間中分布不平坦的問題，針對(duì)這些問題，提出了核組合的方法，即多核學(xué)習(xí)(Multiple kernel learning，MKL)[5]。該方法融合了單核函數(shù)的優(yōu)點(diǎn)，克服了單核函數(shù)的不足，在實(shí)際應(yīng)用中表現(xiàn)出良好的性能。

結(jié)合模糊支持向量機(jī)和多核學(xué)習(xí)的優(yōu)勢(shì)，本文將啟發(fā)函數(shù)確定模糊隸屬度函數(shù)的方法運(yùn)用到多核學(xué)習(xí)中，提出一種模糊多核學(xué)習(xí)方法，通過實(shí)驗(yàn)，提出的方法比SVM、模糊支持向量機(jī)和多核學(xué)習(xí)方法表現(xiàn)出更好的分類效果。

1 支持向量機(jī)、模糊支持向量機(jī)和多核學(xué)習(xí)

如沒有特殊說明，均認(rèn)為是討論二分類問題，下面簡(jiǎn)要地介紹一下支持向量機(jī)、模糊支持向量機(jī)和多核學(xué)習(xí)。

1.1 支持向量機(jī)

假設(shè)訓(xùn)練集T={(x1,y1),(x2,y2),…,(xl,yl)}，其中xi∈Rn，yi∈{-1,1}，i=1,2,…,l。用最大間隔法可以將該二分類問題劃分，尋找最優(yōu)超平面的過程可以歸結(jié)為求解一個(gè)二次規(guī)劃的問題。描述如下：

(1)

其中:w是權(quán)向量且w∈Rn，b是偏置量且b∈R。對(duì)于線性不可分問題，引入松弛變量ξi≥0,i=1,2,…,l，可得到“軟化”了的約束條件：

(2)

由(2)式可知，當(dāng)ξi充分大時(shí)，訓(xùn)練集T中的點(diǎn)總可以滿足(2)式的約束條件，為了避免ξi取值過大，必須在目標(biāo)函數(shù)中加入懲罰項(xiàng)。軟間隔分類描述如下：

(3)

在實(shí)際求解(1)或(3)式時(shí)，需要通過一個(gè)非線性映射函數(shù)φ(x)，將樣本映射到一個(gè)高維(或是無窮維)的特征空間中，φ(x)需滿足Mercer核定理[8]。為了解決(1)或(3)式問題，需要計(jì)算φ(xi)·φ(xj)，但我們并不知道φ(x)的具體表達(dá)形式，只清楚核函數(shù)K(xi,xj)的表達(dá)形式：

(4)

通過使用Lagrangian乘子法和核函數(shù)方法，可以得到?jīng)Q策函數(shù)：

(5)

1.2 模糊支持向量機(jī)

雖然支持向量機(jī)是解決分類問題的強(qiáng)大工具，但是它仍有不足，在訓(xùn)練樣本時(shí)，給每個(gè)訓(xùn)練點(diǎn)都賦予相同的權(quán)值，對(duì)于每一個(gè)訓(xùn)練點(diǎn)要么屬于一類，要么屬于另一類。但是，在實(shí)際應(yīng)用中，訓(xùn)練點(diǎn)的影響通常是不同的，而且可能存在噪聲點(diǎn)和孤立點(diǎn)，如果給噪聲點(diǎn)和孤立點(diǎn)也賦予相同的權(quán)值，這樣訓(xùn)練的分類器分類精度一般不理想。針對(duì)此不足，Lin等[3]提出了基于類中心的模糊支持向量機(jī)。

假設(shè)訓(xùn)練集：T={(x1,y1,u1),(x2,y2,u2),…(xl,yl,ul)},i=1,2,…,l，其中xi∈Rn,yi∈{-1,1},ui∈(0,1]，T+表示訓(xùn)練集中的正類樣本，T-表示訓(xùn)練集中的負(fù)類樣本，即T+={xi|xi∈T,yi=1}，T-={xi|xi∈T,yi=-1},T=T+∪T-,ui是xi隸屬于某一類的程度，ξi是度量xi被錯(cuò)分的程度，uiξi是對(duì)不同權(quán)重的樣本的錯(cuò)分度量。則該分類問題的描述如下：

(6)

假設(shè)x+和x-分別表示正類樣本T+和負(fù)類樣本T-的平均值，正類樣本半徑表示為：

(7)

同理，負(fù)類樣本半徑為：

(8)

由(7) 和(8) 式可知模糊隸屬度函數(shù)[3]為：

(9)

其中是一個(gè)常數(shù)且δ>0。

1.3 多核學(xué)習(xí)

近些年隨著SVM的應(yīng)用和發(fā)展，使用單核核函數(shù)存在一些不足，如不能解決樣本特征規(guī)模大、含有異構(gòu)信息、在特征空間中分布不平坦的問題，針對(duì)這些問題，提出了核組合的方法，即多核學(xué)習(xí)(Multiple kernel learning，MKL)[5]。多核學(xué)習(xí)是一類基于核學(xué)習(xí)的方法，靈活性強(qiáng)，近年來，在理論和應(yīng)用方面證明了利用多核方法代替單核方法能夠提高分類器的性能。具體來說，多核學(xué)習(xí)的本質(zhì)就是確定基本核函數(shù)之前的系數(shù)問題。

(10)

假設(shè)Χ=Rd1×Rd2×…×Rdm，Ηk=Rdk，φk(xi)=xi,k，xi,k表示將xi映射到Rdk的特征空間中，基于l1-norm的多核學(xué)習(xí)[10]表示如下：

(11)

(12)

2 基于模糊多核學(xué)習(xí)的改進(jìn)支持向量機(jī)算法

針對(duì)訓(xùn)練集中存在噪聲點(diǎn)和孤立點(diǎn)問題，以及不能解決樣本特征規(guī)模大、含有異構(gòu)信息、在特征空間中分布不平坦的問題，提出一種新的學(xué)習(xí)方法—模糊多核學(xué)習(xí)，模糊多核學(xué)習(xí)使用啟發(fā)函數(shù)去構(gòu)造模糊隸屬度函數(shù)，有效地減小了噪聲點(diǎn)和孤立點(diǎn)在構(gòu)造最優(yōu)超平面時(shí)的影響，同時(shí)結(jié)合了單核的優(yōu)點(diǎn)，從而提高了分類的精度。

本文選取組合方式構(gòu)建多核核函數(shù)，即采用多項(xiàng)式核函數(shù)和高斯核函數(shù)的組合，

(13)

假設(shè)訓(xùn)練集：T={(x1,y1,u1),(x2,y2,u2),…,(xl,yl,ul)},i=1,2,…,l，其中xi∈Rn,yi∈{-1,1},ui∈(0,1],ui是xi隸屬于某一類的程度，ξi是度量xi被錯(cuò)分的程度，uiξi是對(duì)不同權(quán)重樣本的錯(cuò)分程度的度量，φk(xi)=xi,k，xi,k表示將xi映射到Rdk的特征空間中。則該分類問題描述如下：

(14)

模糊隸屬度函數(shù)ui的確立，文獻(xiàn)[4]中Lin等提出核目標(biāo)度量的啟發(fā)函數(shù)，本文采用該方法，相關(guān)描述如下：

(15)

(16)

(17)

其中：K(xi,xj)選取高斯核函數(shù)。則根據(jù) (15)、(16)和(17) 式得出模糊隸屬段函數(shù)ui：

(18)

其中：τ=0.001是一個(gè)很小的大于零的數(shù)，η取值為2。

本文結(jié)合主動(dòng)學(xué)習(xí)策略和改進(jìn)加權(quán)貝葉斯分類模型，提出了基于改進(jìn)加權(quán)貝葉斯算法的主動(dòng)學(xué)習(xí)與半監(jiān)督學(xué)習(xí)結(jié)合算法( Active Learning KL Semi-supervised，ALKLSS)。算法分兩個(gè)階段進(jìn)行，第一階段，利用改進(jìn)加權(quán)貝葉斯分類算法對(duì)有標(biāo)記樣本進(jìn)行初始分類；第二階段計(jì)算KL距離對(duì)未標(biāo)記樣本進(jìn)行主動(dòng)選擇，選出信息量最大的樣本，交由專家標(biāo)記，再用改進(jìn)貝葉斯進(jìn)行分類。本文算法的框架如下：

輸入：訓(xùn)練集T={(x1,y1),(x2,y2),…,(xl,yl)}；

輸出：測(cè)試集的類標(biāo)記。

Step1：選取基本核函數(shù)以及核參數(shù)，即計(jì)算公式(13)；

Step2：構(gòu)造并求解凸二次規(guī)劃問題，即求解公式(14)；

Step3：根據(jù)Step 2得到的解，計(jì)算偏置量uiξi；

Step4：根據(jù)公式(18)確定模糊隸屬度ui，

Step5：結(jié)合Step2和Step3計(jì)算的結(jié)果構(gòu)造分類超平面；

Step6：使用得到的分類超平面對(duì)測(cè)試集進(jìn)行分類，得出分類結(jié)果。

3 實(shí)驗(yàn)驗(yàn)證和分析

為了比較SVM、FSVM和FMKL 的分類性能，實(shí)驗(yàn)環(huán)境：AMD Sempron Dual Core Processer 2100，1.81 GHz，2.87 GB的內(nèi)存，Windows XP系統(tǒng)，Matlab版本：R2010b。

4種分類方法均采用：隨機(jī)產(chǎn)生100個(gè)訓(xùn)練集，其中有50個(gè)正類樣本(1個(gè)噪聲點(diǎn))，50個(gè)負(fù)類樣本(1個(gè)噪聲點(diǎn))，測(cè)試數(shù)據(jù)集隨機(jī)產(chǎn)生111個(gè)數(shù)據(jù)點(diǎn)。經(jīng)過多次的參數(shù)調(diào)整實(shí)驗(yàn)，以下4種方法的參數(shù)均選擇的是所做實(shí)驗(yàn)結(jié)果中比較理想的參數(shù)。4種實(shí)驗(yàn)具體描述如下：

1)SVM 采用高斯核函數(shù)K(x,y)=exp(-0.5*(norm(x-y)/s)^2)，取C=10,s=1。

2)FSVM采用高斯核函數(shù)K(x,y)=exp(-0.5*(norm(x-y)/s)^2)，取C=45,s=1，使用(18)式來確定ui。

3)MKL采用高斯核函數(shù)K(x,y)=exp(-0.5*(norm(x-y)/s)^2)，取C=65,s=1，K(x,y)=(x'*y+c)^d，c=1，d=3，K=λKploy+(1-λ)KRBF，λ=0.106 1。

4)FMKL采用高斯核函數(shù)K(x,y)=exp(-0.5*(norm(x-y)/s)^2)，取C=65,s=1，K(x,y)=(x'*y+c)^d，c=1，d=3，K=λKploy+(1-λ)KRBF，λ=0.106 1，使用(18)式來確定ui。

通過編程實(shí)驗(yàn)，其結(jié)果如圖1所示。

圖1 采用4種方法的結(jié)果

從圖1(a)～(d)中可以看出，測(cè)試數(shù)據(jù)集中正類和負(fù)類樣本均含有噪聲點(diǎn)，4種方法相比較而言，F(xiàn)SVM方法得到的分類面優(yōu)于傳統(tǒng)的SVM方法得到的分類面，其次是FMKL方法得到的分類面優(yōu)于MKL方法、FSVM方法得到的分類面和傳統(tǒng)的SVM方法得到的分類面，更能夠?qū)⒎诸悊栴}正確劃分，從而驗(yàn)證了本文提出的模糊多核學(xué)習(xí)方法的有效性。

4 結(jié)論

針對(duì)傳統(tǒng)SVM中，對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感的問題，單核學(xué)習(xí)存在靈活性差的不足，主要表現(xiàn)在學(xué)習(xí)能力和泛化能力兩個(gè)方面。為了克服傳統(tǒng)SVM對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感的問題和綜合考慮學(xué)習(xí)能力和泛化能力，提出了一種模糊多核學(xué)習(xí)的方法，該方法能夠有效的克服傳統(tǒng)SVM的不足，通過實(shí)驗(yàn)驗(yàn)證了模糊多核學(xué)習(xí)的有效性。下一步工作將改進(jìn)模糊多核學(xué)習(xí)的效率，提高算法執(zhí)行效率。

[1]Vladimir Vapnik. Statistical Learning Theory[M]. New York, 1998.[2] William S Noble. What is a support vector machine?[J]. Nature biotechnology, 2006, 24(12): 1565-1567.

[3] Lin C F, Wang S D. Fuzzy support vector machines[J]. IEEE Trans. Neural Networks 2002, 13(2): 464-471.

[4] Lin C F, Wang S D. Training algorithms for fuzzy support vector machines with noisy data[J]. Pattern Recognition Letters, 2004,25: 1647-1656.

[5] Lewis D P, Jebara T, Noble W S. Nonstationary kernel combination[A]. In: Proceedings of the 23rd International Conference on Machine Learning[C]. Pittsburgh, USA: ACM, 2006: 553-560.[6] Smola A J. Learning with Kernel [D]. Berlin: Ph D Thesis Berlin, 1998.

[7] 鄧乃揚(yáng)，田英杰.支持向量機(jī)：理論、算法與拓展[M].北京：科學(xué)出版社，2009.

[8] 鄧乃揚(yáng)，田英杰.數(shù)據(jù)挖掘中的新方法—支持向量機(jī)[M].北京：科學(xué)出版社，2004.

[9] Wu Z P, Zhang X G. Elastic Multiple Kernel Learning[J]. Acta Automatica Sinica, 2011, 37 (6): 693-699.

[10] Bach F R, Lanckriet G R G, Jordan M I. Multiple kernel learning, conic duality, and the SMO algorithm[A]. In: Proceedings of the 21st International Conference on Machine Learning[C]. New York, USA: ACM, 2004: 1-8.

Study on Improved SVM Algorithm Based on Fuzzy Multiple Kernel Learning

Liu Jianfeng1, Gan Yan2

(1.ZhongQing Three Gorge University, Wanzhou 404100, China;2.University of Electronic Science and Techology, Wanzhon 404100, China)

According to issues on noise and isolated points sensitive, the traditional SVM can not solve the sample characteristics of large scale, containing the heterogeneous information and the uneven feature space distribution. The fuzzy membership is draw into multiple kernel learning, and this paper proposes a method of fuzzy multiple kernel learning. Experimental results show that fuzzy multiple kernel learning is more effective and feasible than SVM, Fuzzy support vector machine and Multiple kernel learning. So, proposed method in this paper can effectively overcome the traditional SVM on noise sensitive and data distribution uneven problem.

support vector machine; fuzzy support vector machine; multiple kernel learning; fuzzy multiple kernel learning

2015-09-20；

2015-10-26。

重慶市自然科學(xué)項(xiàng)目(cstc2014jcyjA40011);重慶市教委科技項(xiàng)目(KJ1400513)。

劉建峰(1984-)，男，河南濮陽(yáng)人，碩士，主要從事機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘方向的研究。

1671-4598(2016)03-0231-03

10.16526/j.cnki.11-4762/tp.2016.03.063

TP18; TP391.4

A