王紅蔚 ， 席紅旗 ， 孔 波

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

0 引言

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

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

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

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

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

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

令

(1)

(2)

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

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

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

2 實驗分析

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

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

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

3 結(jié)論

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

參考文獻：

[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] 門昌騫，王文劍. 一種基于多學習器標記的半監(jiān)督SVM學習方法[J] . 廣西師范大學學報：自然科學版， 2008, 26(1): 186-189.

[7] 朱美琳, 楊佩. 半監(jiān)督支持向量機的多分類學習算法[J]. 鄭州大學學報：理學版，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/.