一種新的半監(jiān)督支持向量機(jī)

王紅蔚 ， 席紅旗 ， 孔 波

(1.河南教育學(xué)院 數(shù)學(xué)系 河南 鄭州 450046；2. 河南教育學(xué)院 信息技術(shù)系 河南 鄭州 450046)

0 引言

半監(jiān)督學(xué)習(xí)是近年來(lái)模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域研究的重點(diǎn)問(wèn)題，主要考慮如何利用少量的標(biāo)簽樣本和大量無(wú)標(biāo)簽樣本進(jìn)行訓(xùn)練和分類的問(wèn)題[1].半監(jiān)督學(xué)習(xí)對(duì)于減少標(biāo)注代價(jià)，提高學(xué)習(xí)機(jī)器性能具有重要的實(shí)際意義.最早的一種半監(jiān)督算法應(yīng)用于網(wǎng)頁(yè)分類[2]；文獻(xiàn)[3]利用混合整數(shù)規(guī)劃的方法提出了一種半監(jiān)督支持向量機(jī)(S3VM)，但是該算法很難解決有大量無(wú)類別標(biāo)簽樣本的問(wèn)題；為了解決這個(gè)問(wèn)題，文獻(xiàn)[4]提出了一種凸半監(jiān)督支持向量機(jī)(VS3VM)，該算法先對(duì)無(wú)類別標(biāo)簽樣本進(jìn)行類別標(biāo)示，再使用監(jiān)督學(xué)習(xí)算法.但標(biāo)注過(guò)程本身就非常復(fù)雜，而且準(zhǔn)確率難以保證；為解決該問(wèn)題，文獻(xiàn)[5]提出了一種新的思路，直接對(duì)無(wú)類別標(biāo)簽樣本進(jìn)行分類，使得聚類分類一次完成，并得到了無(wú)監(jiān)督支持向量機(jī)和半監(jiān)督支持向量機(jī)，不過(guò)在這個(gè)方法中，要求最優(yōu)分劃超平面必須過(guò)訓(xùn)練樣本集的質(zhì)心，這顯然不適合解決所有問(wèn)題.文獻(xiàn)[6]通過(guò)不斷地對(duì)無(wú)標(biāo)簽樣本進(jìn)行標(biāo)記提出了一種半監(jiān)督支持向量機(jī)，顯然這不易于處理大樣本情形.文獻(xiàn)[7]提出了一種借助徑向基核函數(shù)求解球類數(shù)據(jù)的半監(jiān)督支持向量機(jī)，這也僅適用于特殊的問(wèn)題.

綜合利用有類別標(biāo)簽和無(wú)類別標(biāo)簽樣本信息構(gòu)造目標(biāo)函數(shù)和約束條件，本文借助二次規(guī)劃模型提出了一種新的半監(jiān)督支持向量機(jī).

1 半監(jiān)督支持向量機(jī)

已知訓(xùn)練集T={x1,y1,…,xl,yl,xl+1,…,xl+k}, 其中xi∈X=Rn，前l(fā)個(gè)屬于有類別標(biāo)簽樣本，即i=1,2,…,l時(shí)，已知yi∈Y={-1,1}；后k個(gè)屬于無(wú)類別標(biāo)簽樣本.尋找X=Rn上的決策函數(shù)f(x)=sgn(ωTφ(x)+b)(其中，ω為權(quán)向量，φ(·)為映射函數(shù)，b為常數(shù)，核函數(shù)Kxi,xj=〈φ(xi),φ(xj)〉)來(lái)推斷任一模式x的類別(正類或者負(fù)類).由此可見(jiàn)，求解分類問(wèn)題，實(shí)質(zhì)上就是找到一個(gè)把Rn上的點(diǎn)分成2部分的規(guī)則.

顯然存在ω∈Rn，b∈R，對(duì)于任一有類別標(biāo)簽樣本xi(i=1,…,l)，都有yiωTφ(xi)+b+ξi≥1,ξi≥0,i=1,…,l.對(duì)于任一無(wú)類別標(biāo)簽樣本xj(j=l+1,…,l+k)，都有ωTφ(xj)+b+rj≥1，ωTφ(xj)+b-sj≤-1，rj,sj≥0,j=l+1,…,l+k.

這樣求解最佳分劃超平面的問(wèn)題就轉(zhuǎn)化為最優(yōu)化問(wèn)題：

令

(1)

(2)

新的半監(jiān)督支持向量機(jī)算法為：

a)已知訓(xùn)練集T={(x1,y1),…,(xl,yl),xl+1,…,xl+k}，其中xi(i=1,…,l)屬于有類別標(biāo)簽樣本，且yi∈Y={-1,1},xj(j=l+1,…,l+k)屬于無(wú)類別標(biāo)簽樣本；

為了有效地突出2種樣本的區(qū)別，懲罰參數(shù)可根據(jù)樣本容量的比例進(jìn)行選取，核函數(shù)可根據(jù)樣本分布選取.

2 實(shí)驗(yàn)分析

UCI數(shù)據(jù)庫(kù)是機(jī)器學(xué)習(xí)的一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)，可以用來(lái)衡量各種模式識(shí)別算法的有效性.為了驗(yàn)證所提出算法的有效性，特選取UCI數(shù)據(jù)庫(kù)上breast cancer wisconsin (original)(BCW)數(shù)據(jù)[9]分別使用支持向量機(jī)(C-SVM)和新半監(jiān)督支持向量機(jī)(NS3VM)算法進(jìn)行了對(duì)比實(shí)驗(yàn).

表1 BCW數(shù)據(jù)準(zhǔn)確率比較Tab.1 Comparison of accuracy about BCW database %

由表1可以看出，利用了未知標(biāo)簽樣本的半監(jiān)督支持向量機(jī)的測(cè)試準(zhǔn)確率優(yōu)于僅使用已知標(biāo)簽樣本的支持向量機(jī),而且已知類別樣本個(gè)數(shù)越少，新的半監(jiān)督支持向量機(jī)的性能越優(yōu)越.

3 結(jié)論

為了有效地利用未知類別樣本進(jìn)行訓(xùn)練，提高學(xué)習(xí)機(jī)器性能，通過(guò)構(gòu)造新的目標(biāo)函數(shù)和約束條件，提出了一個(gè)新的半監(jiān)督學(xué)習(xí)支持向量機(jī).該算法具有3個(gè)優(yōu)點(diǎn)：同傳統(tǒng)的支持向量一樣利用二次規(guī)劃求解問(wèn)題，具有解的優(yōu)良性，并適合處理大量數(shù)據(jù)樣本；可以一次完成求解最優(yōu)分劃超平面，簡(jiǎn)化了標(biāo)注未知類別樣本的復(fù)雜性；有效地解決了文獻(xiàn)[5]要求最優(yōu)分劃超平面過(guò)訓(xùn)練樣本質(zhì)心的問(wèn)題，實(shí)用性得到了提高.實(shí)驗(yàn)結(jié)果印證了該算法可以有效地提高僅利用有類別標(biāo)簽樣本的支持向量機(jī)的分類準(zhǔn)確率.

參考文獻(xiàn)：

[1] Vapnik V. The Nature of Statistical Learning Theory[M]. New York: Springer-Verlag，1995.

[2] Blum A, Mitchell T. Combining labeled and unlabeled data with cotraining[C]//Proceedings of the 11th Annual Conference on Computational Learning Theory. Madison, 1998: 92-100.

[3] Bennett K P, Demiriz A. Semi-supervised Support Vector Machines[C]//Advances in Neural Information Proceeing Systems 11. Cambridge, 1998: 368-374.

[4] Fung G, Mangasarian O L. Semi-supervised support vector machines for unlabeled data classification[J]. Optimization Methods and Software，2001,15: 29-44.

[5] Wu Tao, Zhao Hanqing. Classifying unlabeled data with SVMs[J]. Advances in Intelligent and Soft Computing, 2006,34: 695-702.

[6] 門昌騫，王文劍. 一種基于多學(xué)習(xí)器標(biāo)記的半監(jiān)督SVM學(xué)習(xí)方法[J] . 廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版， 2008, 26(1): 186-189.

[7] 朱美琳, 楊佩. 半監(jiān)督支持向量機(jī)的多分類學(xué)習(xí)算法[J]. 鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2008，40(4): 35-38.

[8] Hsu C W，Lin C J. A simple decomposition method for support vector machines[J]. Machine Learning,2002，46(1/2/3)：291-314.

[9] Blake C L, Merz C J. UCI Repository of machine learning databases[EB/OL]. [2011-01-11] .http://www.ics.uci.edu/～mlearn/databases/.