基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法

張 燁

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法

張 燁

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

當(dāng)處理數(shù)據(jù)規(guī)模較大、屬性較多、且存在噪聲數(shù)據(jù)干擾的醫(yī)療數(shù)據(jù)時(shí)，傳統(tǒng)的支持向量機(jī)會(huì)出現(xiàn)訓(xùn)練速度變慢、參數(shù)敏感且難以保證其準(zhǔn)確率等問(wèn)題。為解決此問(wèn)題，文中提出了一種基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法。通過(guò)引入關(guān)聯(lián)度對(duì)樣本進(jìn)行加權(quán)處理，同時(shí)利用KKT條件對(duì)訓(xùn)練樣本進(jìn)行篩選，不僅節(jié)省了大量的內(nèi)存存儲(chǔ)空間，且減少了訓(xùn)練時(shí)間，進(jìn)一步提高了分類學(xué)習(xí)的準(zhǔn)確度。

支持向量機(jī)；樣本加權(quán)；增量支持向量機(jī)；KKT條件

對(duì)醫(yī)療數(shù)據(jù)進(jìn)行實(shí)時(shí)的數(shù)據(jù)分析和數(shù)據(jù)挖掘處理，可較好地幫助醫(yī)療工作者和研究人員分析隱藏在醫(yī)療數(shù)據(jù)中不同數(shù)據(jù)之間的關(guān)系，為醫(yī)生制定治療方案提供輔助決策[1]。

以Bell實(shí)驗(yàn)室V. Vapnik教授為首的研究小組在1995年最先提出支持向量機(jī)(Support Vector Machine, SVM)這一概念[2]。支持向量機(jī)是一種基于分類邊界的方法，其通過(guò)預(yù)先選擇某一非線性變換，將輸入向量映射到高維特征空間中，構(gòu)造一個(gè)最優(yōu)分類超平面[3]。丁勝峰于2012年提出了一種改進(jìn)的雙支持向量機(jī)，在一定程度上提高了模式分類的識(shí)別率[4]。Quan T W等人在最小二乘支持向量機(jī)算法的基礎(chǔ)之上對(duì)屬性進(jìn)行加權(quán)，提出了基于加權(quán)的最小二乘支持向量機(jī)，以此來(lái)減少孤立點(diǎn)所帶來(lái)的影響[5]。

本文提出的基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法(SCW-ISVM)，就是在增量學(xué)習(xí)支持向量機(jī)基礎(chǔ)之上，增加了樣本加權(quán)分布信息的分類算法，該算法使用樣本關(guān)聯(lián)度權(quán)重法來(lái)確定樣本權(quán)值。并在某婦幼保健院的乳腺癌數(shù)據(jù)集和標(biāo)準(zhǔn)庫(kù)中的數(shù)據(jù)集上，與傳統(tǒng)支持向量機(jī)和基于KKT條件的增量支持向量機(jī)算法在分類精度和訓(xùn)練時(shí)間上進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果顯示，SCW-ISVM比其他兩種支持向量機(jī)算法在分類性能上有所提高，綜合性能更穩(wěn)定。

1 支持向量機(jī)

設(shè)樣本集為(Xi,yi)(i=1,2,…,n)，其中Xi=(xi1,xi2,…,xin)T,yi∈{-1,1}表示該類別標(biāo)號(hào)，類別為1的類稱為正類，類別為-1的類稱為負(fù)類。傳統(tǒng)的支持向量機(jī)(SVM)[6-8]是通過(guò)求解下面的優(yōu)化問(wèn)題進(jìn)而得出最優(yōu)超平面

s.t.Yi((W·Xi+b)+1)≥1-ξii=1,2,…,N

(1)

其中，W為法向量；b為一個(gè)偏移量，是分類模型的參數(shù)；ξi為松弛變量；C為懲罰因子。理論上講，k可以是任意正整數(shù)，對(duì)應(yīng)的方法稱為k階軟邊緣方法，該優(yōu)化問(wèn)題轉(zhuǎn)換為對(duì)偶問(wèn)題如下

(2)

最終，支持向量機(jī)的分類決策函數(shù)為

(3)

2 基于KKT條件的增量支持向量機(jī)

2.1 增量學(xué)習(xí)

設(shè)A為初始樣本集；B為新增樣本集，A、B滿足A∩B=?，則φA表示初始樣本集A上的初始分類器;SVA表示與其對(duì)應(yīng)的支持向量。增量學(xué)習(xí)的目標(biāo)就是要找到在A∪B上的支持向量分類器以及與其對(duì)應(yīng)的支持向量。概括來(lái)講，增量學(xué)習(xí)[9-10]就是指在不斷增加新樣本的學(xué)習(xí)過(guò)程中可以學(xué)到新的知識(shí)，并能夠保留已學(xué)習(xí)到的正確歷史知識(shí)。

2.2 基于KKT的增量學(xué)習(xí)算法

SVM將分類邊界最大化[11-12]，將優(yōu)化問(wèn)題轉(zhuǎn)換成式(2)形式的對(duì)偶問(wèn)題。在求解過(guò)程中，致使拉格朗日系數(shù)滿足約束條件，所以需要引用KKT條件，也稱之為KKT定理[13]。式(3)對(duì)應(yīng)的KKT條件為

(4)

綜上所述，在對(duì)樣本集進(jìn)行訓(xùn)練得到支持向量分類器的過(guò)程中，樣本分布有以下3種情況：(1)當(dāng)α=0時(shí)，樣本點(diǎn)(xi,yi)分布在分類器f(x)=-1和f(x)=1的間隙外；(2) 當(dāng)0<α

綜合上述3種情況可得出，滿足KKT條件的充要條件為

yif(xi)≥1

(5)

3 增量支持向量機(jī)算法

3.1 樣本關(guān)聯(lián)度權(quán)重法

本文提出了一種使用關(guān)聯(lián)度對(duì)樣本進(jìn)行加權(quán)的方法，即樣本關(guān)聯(lián)度權(quán)重法，通過(guò)待檢驗(yàn)樣本與訓(xùn)練樣本的關(guān)聯(lián)度大小來(lái)確定其權(quán)重的大小。

(6)

式(6)中，εi(t)稱為待測(cè)樣本數(shù)列xi對(duì)參考數(shù)列x0的關(guān)聯(lián)系數(shù)；σ∈[0,+∞)為分辨系數(shù)，用于提高關(guān)聯(lián)系數(shù)之間的顯著差異性，σ越大，分辨率越高，反之亦然，本文σ取0.5;

(2) 關(guān)聯(lián)度。由式(6)定義的關(guān)聯(lián)系數(shù)是不同屬性的關(guān)聯(lián)系數(shù)，為了比較兩個(gè)樣本之間的關(guān)聯(lián)關(guān)系，本文選取關(guān)聯(lián)系數(shù)的平均值作為比較過(guò)程的關(guān)聯(lián)程度的量度[14-15]，其表達(dá)式為

(7)

式(7)中，ηi為待測(cè)訓(xùn)練樣本數(shù)列xi和參考數(shù)列x0之間的關(guān)聯(lián)度;

(3) 估計(jì)權(quán)值確定。樣本xi和第j類樣本的關(guān)聯(lián)度的均值向量ηi的歐式距離定義為

(8)

(9)

(10)

上式中，ηj表示第j類樣本；ηi表示第i類樣本。當(dāng)增加了樣本權(quán)值信息后，超平面公式改寫(xiě)為

yi((w·xi)+b)≥dii=1,2,…,N

(11)

通過(guò)等價(jià)變換，轉(zhuǎn)化為下列凸二次規(guī)劃問(wèn)題

(12)

設(shè)λ*、b0是上述凸二次規(guī)劃問(wèn)題的解，則加權(quán)的最優(yōu)超平面決策函數(shù)為

(13)

(14)

其中，x*(1)、d*(1)表示屬于正類的任意1個(gè)支持向量及其權(quán)值；x*(-1)、d*(-1)表示屬于負(fù)類的一個(gè)支持向量及其權(quán)值。

3.2 算法描述

本文提出的基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法(SCW-ISVM)，通過(guò)樣本關(guān)聯(lián)度權(quán)重法對(duì)樣本進(jìn)行加權(quán)，在篩選訓(xùn)練樣本時(shí)仍然采用上一章中提到的KKT條件來(lái)進(jìn)行篩選。該算法分為訓(xùn)練階段和測(cè)試階段兩個(gè)步驟，步驟如下：

輸入 初始樣本集Xa和新增樣本集Xb，核函數(shù)r，懲罰因子C。

輸出Xa∩Xb的分類器模型和支持向量。

步驟1 訓(xùn)練階段；

步驟1.1 將初始樣本集Xa分為訓(xùn)練樣本x1和測(cè)試樣本x2；

步驟1.2 利用式(6)分別計(jì)算訓(xùn)練樣本集和測(cè)試樣本集的關(guān)聯(lián)系數(shù)，并用式(7)計(jì)算其關(guān)聯(lián)度均值向量η1和η2；

步驟1.3 對(duì)樣本用式(8)分別計(jì)算它到η1和η2之間的歐式距離，并根據(jù)式(9)對(duì)歐式距離進(jìn)行加權(quán)；

步驟1.4 完成所有權(quán)值計(jì)算后，代入式(10)，求解出凸二次規(guī)劃的最優(yōu)解，得到相應(yīng)的分類器Ωa和支持向量SVa，Xa作為下次增量學(xué)習(xí)的初始樣本，算法結(jié)束；

步驟2 測(cè)試階段；

步驟2.1 判斷Xb中是否存在不滿足Ωa定義的KKT條件的樣本，如果不存在，則轉(zhuǎn)至步驟2.6；否則，繼續(xù)執(zhí)行下一步；

步驟2.3 判斷Xa中是否存在不滿足Ωb定義的KKT條件的樣本，如果不存在，則轉(zhuǎn)至步驟2.6；否則，繼續(xù)執(zhí)行下一步；

步驟2.5 將初始樣本集Xa和新增樣本集Xb經(jīng)過(guò)上述操作后的剩余樣本重新標(biāo)記為Xb，返回步驟2.1，循環(huán)執(zhí)行；

步驟2.6 輸出更新后的Ωa和SVa，算法結(jié)束。

4 實(shí)驗(yàn)和結(jié)果

4.1 實(shí)驗(yàn)

本節(jié)實(shí)驗(yàn)主要是通過(guò)對(duì)兩個(gè)數(shù)據(jù)集分別使用樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法(SCW-ISVM)、傳統(tǒng)的支持向量機(jī)算法(SVM)和基于KKT條件的增量SVM進(jìn)行實(shí)驗(yàn)，分別在分類準(zhǔn)確度和時(shí)間上進(jìn)行比較。

實(shí)驗(yàn)中使用的懲罰因子 選取為1，核函數(shù)使用高斯徑向核函數(shù)，參數(shù)r選取為0.15，基于KKT條件的增量SVM和基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法(SCW-ISVM)中的距離閥值取為1.5。

本節(jié)實(shí)驗(yàn)數(shù)據(jù)分別來(lái)源于http://archive.ics.uci.edu/ml/提供的標(biāo)準(zhǔn)樣本數(shù)據(jù)庫(kù)中的一個(gè)數(shù)據(jù)集，和某婦幼保健院的乳腺癌數(shù)據(jù)集，一共構(gòu)成兩個(gè)數(shù)據(jù)集，如表1表述，分別在兩個(gè)數(shù)據(jù)集里隨機(jī)抽取一定數(shù)量的訓(xùn)練樣本，然后進(jìn)行6次隨機(jī)抽取新增樣本，如表2表述。

表1 實(shí)驗(yàn)中用到的兩個(gè)數(shù)據(jù)集

表2 每個(gè)數(shù)據(jù)集的初始訓(xùn)練樣本數(shù)和每次新增樣本數(shù)

4.2 結(jié)果

(1) 使用某婦幼保健院乳腺癌數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，表3給出了實(shí)驗(yàn)結(jié)果，圖1為3種算法的訓(xùn)練精度的對(duì)比，圖2為3種算法的訓(xùn)練時(shí)間的對(duì)比。

圖1 3種算法在乳腺癌數(shù)據(jù)集上訓(xùn)練精度的對(duì)比

圖2 3種算法在乳腺癌數(shù)據(jù)集上訓(xùn)練時(shí)間的對(duì)比

(2) 使用Female diabetes數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，表4給出了實(shí)驗(yàn)結(jié)果，圖3為3種算法的訓(xùn)練精度的對(duì)比，圖4為3種算法的訓(xùn)練時(shí)間對(duì)比。

表3 3種算法在乳腺癌數(shù)據(jù)集上的性能對(duì)比

表4 3種算法在Female diabetes數(shù)據(jù)集上的性能對(duì)比

圖3 3種算法在Female diabetes數(shù)據(jù)集上訓(xùn)練精度的對(duì)比

圖4 3種算法在Female diabetes數(shù)據(jù)集上訓(xùn)練時(shí)間的對(duì)比

5 結(jié)束語(yǔ)

本文提出的算法與傳統(tǒng)支持向量機(jī)、基于KKT條件的增量支持向量機(jī)兩種算法，分別在標(biāo)準(zhǔn)數(shù)據(jù)集和某婦幼保健院乳腺癌數(shù)據(jù)集上進(jìn)行算法性能測(cè)試。實(shí)驗(yàn)結(jié)果表明，本文提出的樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法在訓(xùn)練精度上比其他兩個(gè)算法要高。但支持向量機(jī)算法中還有很多的不足之處可進(jìn)行改進(jìn)研究，由于時(shí)間和精力有限，不能實(shí)現(xiàn)所有的想法，在此研究基礎(chǔ)之上，提出進(jìn)一步研究工作的展望。

本文核函數(shù)使用的是高斯徑向核函數(shù)，核函數(shù)結(jié)構(gòu)對(duì)算法性能的影響較大，核優(yōu)化也是提高核學(xué)習(xí)算法性能的直接方法。因此，在后續(xù)工作中應(yīng)該對(duì)核函數(shù)結(jié)構(gòu)以及優(yōu)化方面進(jìn)行研究。

[1] Eric J T.The big medical data miss:challenges in establishing an open medical resource[J].Nature Reviews Genetics,2015,16(5):253-264.

[2] Saimurugan M,Ramachandran K I,Sugumaran V,et al.Multi component fault diagnosis of rotational mechanical system based on decision tree and support vector machine[J].Expert Systems with Applications,2011,38(4):3819-3826.

[3] 黃燕紅.基于SVM算法的癌癥基因數(shù)據(jù)分類研究[D].蘇州:蘇州大學(xué),2015.

[4] 丁勝峰.一種改進(jìn)的雙支持向量機(jī)[J].遼寧石油化工大學(xué)學(xué)報(bào),2012,32(4):76-82.

[5] Quan Tingwei,Liu Xiaomiao,Liu Qian.Weighted least squares support vector machine local region method for nonlinear time series prediction[J].Applied Soft Computing,2010,10(2):562-566.

[6] Farquad M A H,Indranil B.Preprocessing unbalanced data using support vector machine[J].Decision Support Systems,2012,53(1):226-233.

[7] Camelo S,González L M,Quiroz A.Nearest neighbors methods for support vector machines[J].Annals of Operations Research,2015,235(1):85-101.

[8] 崔文斌,溫孚江,牟少敏,等.基于Hadoop的局部支持向量機(jī)[J].計(jì)算機(jī)研究與發(fā)展,2014(S2):116-121.

[9] Li Zhiyu,Zhang Junfeng,Hu Shousong.Incremental support vector machine algorithm based on multi-kernel learning[J].Journal of Systems Engineering and Electronics,2011,22(4):702-706.

[10] 鄭關(guān)勝,王建東,顧彬,等.一類增量式支持向量機(jī)的分析[J].南京航空航天大學(xué)學(xué)報(bào),2015,47(1):113-118.

[11] 田宇馳,胡亮.基于SVM的一種醫(yī)療數(shù)據(jù)分析模型[J].東北師大學(xué)報(bào):自然科學(xué)版,2015,47(1):77-82.

[12] 尚丹.基于參數(shù)優(yōu)化的SVM分類器在肺癌早期診斷中的應(yīng)用[D].鄭州:鄭州大學(xué),2014.

[13] 文波,單甘霖,段修生.基于KKT條件與殼向量的增量學(xué)習(xí)算法研究[J].計(jì)算機(jī)科學(xué),2013,40(3):255-258.

[14] 陳曉紅,戴子敬,劉翔.基于熵和關(guān)聯(lián)系數(shù)的區(qū)間直覺(jué)模糊決策方法[J].系統(tǒng)工程與電子技術(shù),2013,35(4):791-795.

[15] 趙敏,龔聲蓉,高祝靜.基于灰色關(guān)聯(lián)系數(shù)的混合噪聲濾波算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(5):1713-1716.

Incremental Support Vector Machine Algorithm Based on Weight of Sample Correlation Degree

ZHANG Ye

(School of Electronic and Information Engineering, Lanzhou jiaotong University,Lanzhou 730070, China)

When processing data on a larger scale, more properties and noise data of medical data, the traditional support vector machine has the problem of slow training speed, sensitive parameters and difficult to ensure its accuracy. In order to solve this problem, this paper proposes an incremental support vector machine algorithm based on the weight of sample correlation degree. By introducing the correlation degree of the sample weighted, at the same time, the KKT conditions for screening of training samples, improved incremental weighted support vector machine algorithm, and it not only to save the large memory storage space, but also reduces the training time, to further improve the accuracy of classification learning.

support vector machine; sample weighting; incremental support vector machine; KKT condition

2016- 04- 22

甘肅省自然科學(xué)基金資助項(xiàng)目(1308RJZA111)

張燁(1990-)，女，碩士研究生。研究方向：數(shù)據(jù)挖掘及可視化。

10.16180/j.cnki.issn1007-7820.2017.03.012

TP391.41

A

1007-7820(2017)03-041-05