王利文， 劉瓊蓀

(重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 401331)

支持向量機[1](Support Vector Machine，SVM)是目前機器學(xué)習(xí)中有效的學(xué)習(xí)機，在實際中取得了廣泛的應(yīng)用。但傳統(tǒng)的支持向量機主要處理監(jiān)督學(xué)習(xí)問題，即對未來所有樣本的預(yù)期性能達到最優(yōu)。而在實際學(xué)習(xí)中，往往只需要對一些特定的未知樣本進行識別，于是考慮一種更為經(jīng)濟有效的分類器，使它能直接從已知樣本對一些特定樣本進行識別與分類。半監(jiān)督支持向量機的學(xué)習(xí)方法能夠?qū)⒁褬?biāo)注的和未標(biāo)注的樣本所提供的聚類信息有機的結(jié)合，比傳統(tǒng)分類算法更有助于解決實際問題，因此它正逐漸成為當(dāng)前機器學(xué)習(xí)領(lǐng)域的研究熱點。目前，半監(jiān)督支持向量機算法主要有：Joachims提出的直推式支持向量機(TSVM)、Ting等提出的BoostSVM(boosting support machine)，Belkin等人提出LapSVM算法。本文主要研究了直推式支持向量機學(xué)習(xí)算法。

1 直推式支持向量機

在傳統(tǒng)的支持向量機學(xué)習(xí)方法中，學(xué)習(xí)算法的目標(biāo)是使學(xué)習(xí)所得的分類器在訓(xùn)練集上有最小的錯誤率，用訓(xùn)練集的分布來近似預(yù)計測試集的分布。但在實際情況中，學(xué)習(xí)的目標(biāo)是使訓(xùn)練得到的分類器在測試集上有盡可能小的實際誤差。這也是直推式支持向量機所要解決的問題。目前，支持向量機的直推式學(xué)習(xí)算法的主要研究成果是T.Jocachims的直推式支持向量機(TSVM)[2]。下面簡單介紹TSVM的算法原理和實現(xiàn)。

(1)

(1) 設(shè)置參數(shù)C和C*的初始值，使用歸納式學(xué)習(xí)對有標(biāo)簽樣本進行一次初始學(xué)習(xí)，得到一個初始分類器，并按照某個規(guī)則指定一個無標(biāo)簽樣本中的正樣本標(biāo)簽樣本數(shù)Np；

(3) 對所有樣本進行重新訓(xùn)練，對新得到的分類器，按一定的規(guī)則交換一對標(biāo)簽值不同的測試樣本的標(biāo)簽符號，使得模型(1)中的目標(biāo)函數(shù)值獲得最大的下降，復(fù)次循環(huán)，直到找不出符合交換條件的樣本對為止；

2 直推式支持向量機的幾種改進算法

2.1 漸近直推式支持向量機學(xué)習(xí)算法

TSVM算法將把無標(biāo)簽樣本隱含的分布信息引入了支持向量機的學(xué)習(xí)過程中，比單純地使用有標(biāo)簽樣本訓(xùn)練得到的分類器在性能上有顯著地提高。但該算法仍存在一些不足，主要缺陷是算法執(zhí)行之前必須人為地指定待訓(xùn)練的無標(biāo)簽樣本中的正樣本數(shù)Np，而在實際上，Np的值很難較為準(zhǔn)確地估計。在TSVM算法中，一般采用了一種簡單的方法去估計Np，即依據(jù)有標(biāo)簽樣本中的正標(biāo)簽樣本所占的比例來近似地估計無標(biāo)簽樣本集中的正標(biāo)簽樣本的比例，從而估計出Np。但該方法在有標(biāo)簽樣本數(shù)較少的情況下很容易導(dǎo)致較大的估計誤差，當(dāng)預(yù)先設(shè)定Np的值與實際的正標(biāo)簽樣本數(shù)相差較大時，就會導(dǎo)致學(xué)習(xí)機性能的迅速下降。

陳毅松[3]等針對TSVM的上述缺陷提出了一種漸進直推式支持向量機(progressive transductive support vector machine，簡稱PTSVM)。在PTSVM算法[3]中，訓(xùn)練開始前，對無標(biāo)簽樣本的分布特征不作任何估計，而在訓(xùn)練過程中選擇對后續(xù)訓(xùn)練產(chǎn)生較大影響的無標(biāo)簽樣本賦予當(dāng)前狀態(tài)下的標(biāo)簽值，并把它們加入到有標(biāo)簽樣本集合中，然后進行新一輪的訓(xùn)練。為使獲得更準(zhǔn)確的分類超平面，該算法采用成對標(biāo)注法和標(biāo)簽重置法來不斷調(diào)整標(biāo)簽值。文獻[3]中證明了成對標(biāo)注法和標(biāo)簽重置法的合理性。PTSVM訓(xùn)練算法的具體步驟：

(1) 設(shè)置參數(shù)C與C*的初始值，對有標(biāo)簽樣本使用歸納式學(xué)習(xí)進行一次初始學(xué)習(xí)，從而得到初始分類器；

(2) 使用初始分類器對無標(biāo)簽樣本學(xué)習(xí)，計算每一個無標(biāo)簽樣本的判別函數(shù)輸出，用成對標(biāo)注法則對當(dāng)前邊界區(qū)域內(nèi)的無標(biāo)簽樣本標(biāo)注一個新的正、負樣本標(biāo)簽；

(3) 重新訓(xùn)練所有樣本，并計算每一個無標(biāo)簽樣本的判別函數(shù)輸出。若發(fā)現(xiàn)早期標(biāo)注的某個無標(biāo)簽樣本的標(biāo)簽值與當(dāng)前的判別函數(shù)輸出值不一致，則按照標(biāo)簽重置法取消對該樣本的標(biāo)注；

(4) 用成對標(biāo)注法尋找當(dāng)前邊界區(qū)域內(nèi)符合新加標(biāo)注條件的未標(biāo)注的無標(biāo)簽樣本。若存在這樣的無標(biāo)簽樣本，則對其標(biāo)注并返回(3)；若不存在這樣的無標(biāo)簽樣本點，則用當(dāng)前的分割平面對剩下的無標(biāo)簽樣本做分類并加注標(biāo)簽。算法結(jié)束，并輸出結(jié)果。

薛貞霞等在文獻[4]中基于SVDD(支持向量域描述)的可信度設(shè)計提出了PTSVM的改進算法RPTSVM算法。首先對當(dāng)前正類、負類有標(biāo)簽樣本分別進行數(shù)據(jù)域描述，得到包含該類數(shù)據(jù)的最小半徑的超球，再根據(jù)當(dāng)前分類間隔區(qū)域內(nèi)的無標(biāo)簽樣本點與超球球心的距離設(shè)計無標(biāo)簽樣本的可信度。根據(jù)事先設(shè)定的可信度閾值，對那些大于閾值的樣本加以標(biāo)注，這是一種區(qū)域標(biāo)注法。顯然，算法繼承了PTSVM的漸進賦值和動態(tài)調(diào)整規(guī)則的優(yōu)點，同時算法在穩(wěn)定性及訓(xùn)練速度上得到了加強，使得算法能夠更好的適應(yīng)各種不同分布的訓(xùn)練樣本。

2.2 TSVM中Np的確定新方法

(2)

(3)

Np與Nn分別表示正負樣本的數(shù)目，a為正常數(shù)。

(4)

或者測試樣本被標(biāo)記為負樣本，它所對應(yīng)的松弛變量ξ*滿足如下條件：

(5)

那么交換這個測試樣本的標(biāo)簽，目標(biāo)函數(shù)值會減少[5]。

2.3 TSVM的模糊漸進式學(xué)習(xí)算法

模糊隸屬度的確定是一種動態(tài)的方式，它隨著決策函數(shù)f(k)(·)的變化而不斷地變化。因此，稱該方法為模糊隸屬度的“自適應(yīng)”方法。

同時，在PTSVM算法中，“半標(biāo)記”集合D始終是不斷增加的，一方面把未標(biāo)記樣本集中的支持向量逐步引入D中，另一方面也把未標(biāo)記樣本集中的非支持向量引入D中。當(dāng)TSVM的決策超平面趨于穩(wěn)定時，半標(biāo)定樣本集中位于分類間隔邊界之外的樣本成為非支持向量的概率非常大，它們對TSVM的決策超平面沒有什么幫助并且會增大計算和存儲開銷。FPTSVM算法將對這部分樣本在半標(biāo)記樣本中刪除，從而對混合訓(xùn)練集進行縮減，從而減輕了算法每個迭代步的計算開銷。

2.4 最小二乘支持向量機的半監(jiān)督學(xué)習(xí)方法(SLS-SVM)

不論是TSVM算法還是PTSVM算法過程都需要求解二次規(guī)劃獲得最優(yōu)分類面。如果遇到大規(guī)模數(shù)據(jù)樣本集時，訓(xùn)練效率極低。文獻[9]在PTSVM算法的基礎(chǔ)上提出了基于半監(jiān)督學(xué)習(xí)的LS-SVM(最小二乘支持向量機)學(xué)習(xí)算法，記為SLS-SVM算法。LS-SVM中用二次損失函數(shù)來取代TSVM中的ε不敏感函數(shù)，從而將TSVM的二次規(guī)劃問題轉(zhuǎn)換為求解線性方程組的問題。在對無標(biāo)簽樣本的處理方面，SLS-SVM采用的是區(qū)域標(biāo)注法及標(biāo)簽重置法，使得算法具有一定的自適應(yīng)差錯修復(fù)能力。

2.5 實時數(shù)據(jù)更新的改進直推式支持向量機算法

當(dāng)處理諸如網(wǎng)絡(luò)入侵問題時，需要實時對數(shù)據(jù)進行分類，利用PTSVM時，在每次的漸進賦值和動態(tài)調(diào)整后都需要重新訓(xùn)練求解二次規(guī)劃，訓(xùn)練效率就顯得較為低下。文獻[11，12]針對入侵數(shù)據(jù)集的數(shù)據(jù)樣本，從兩個方面優(yōu)化了PTSVM算法。一是采用一種有傾向的區(qū)域標(biāo)注方法；二是采用增量與減量算法。當(dāng)標(biāo)注一個無標(biāo)簽樣本點后，采用增量迭代更新算法；當(dāng)修改早期標(biāo)注錯誤的無標(biāo)簽樣本點時，則采用減量方法。這將克服每次漸進賦值和動態(tài)調(diào)整后所需要重新訓(xùn)練的缺陷。區(qū)域標(biāo)注法的思想：

s.t. 0

(6)

由式(6)描述區(qū)域內(nèi)的樣本標(biāo)為負標(biāo)簽，假設(shè)符合條件的無標(biāo)簽樣本數(shù)為m。

s.t. -1

(7)

其中

(8)

在TSVM與未經(jīng)改良的PTSVM算法中，當(dāng)發(fā)現(xiàn)早期標(biāo)注的樣本點與當(dāng)前判別函數(shù)輸出不一致時，需要重新訓(xùn)練，頻繁求解優(yōu)化模型。改良的PTSVM會取消上述不一致的標(biāo)簽，按照減量方法更新非支持向量集合和α，b，f(x)，訓(xùn)練時間上會大幅減少，明顯提高訓(xùn)練的效率。

2.6 Semi TSVM 算法[13]

如果訓(xùn)練樣本集數(shù)目不足、分類的雙方存在著數(shù)據(jù)不平衡的情況，文獻[13]提出了一種新的基于TSVM的半監(jiān)督分類算法(Semi SVM)。該算法通過對半標(biāo)定樣本的選擇和懲罰參數(shù)C*的調(diào)節(jié)來實現(xiàn)。

(1) 半標(biāo)定樣本點的選擇。在選擇半標(biāo)定樣本加入到混合訓(xùn)練樣本集的時候，主要考慮兩點：選擇的樣本應(yīng)該被加入到正確的類別中；應(yīng)該選擇含有“信息”的半標(biāo)定樣本。因為分類超平面是建立在支持向量的基礎(chǔ)之上，所以應(yīng)該選擇含分類信息最豐富的兩類樣本的支持向量。

ψmax=max(ψ+，ψ-)，ψmin=min(ψ+，ψ-)

設(shè)Amax為ψmax中樣本的個數(shù)，Amin為ψmin中樣本個數(shù)。為了處理不平衡數(shù)據(jù)，針對兩類數(shù)據(jù)分別定義了不同的的閾值公式：

(9)

(10)

當(dāng)候選集中的樣本的|f(x)|值大于閾值時，該樣本被加入到混合樣本集中，成為半標(biāo)定樣本，并將這些樣本從候選樣本集中除去，以更新候選集和混合樣本。

(11)

以此求得每次迭代決策函數(shù)中的半標(biāo)定樣本的懲罰參數(shù)。這樣在迭代運算過程中，使得C*的改變與半標(biāo)定樣本的選擇結(jié)合到一起，并處于動態(tài)的調(diào)節(jié)中的。該算法的具體步驟可參考文獻[13]。

2.7 改進的TSVM最新算法

文獻[16]運用上述算法，它不是將分類間隔內(nèi)所有的樣本加入到候選集中，而是只將那些判別函數(shù)的絕對值大于或者等于事先設(shè)定的閾值的樣本加入候選集中。而且為了平衡樣本，取N=min(N+，N-)，這樣加入候選集中相同數(shù)目的正負樣本，有效避免了因樣本分布不均衡導(dǎo)致分類超平面的偏移。

上述算法能夠得到更為可靠的分類效果，但當(dāng)訓(xùn)練樣本數(shù)目較多時上述迭代過程的訓(xùn)練工作量也較大，且迭代次數(shù)T的確定問題也需要進一步的研究。

3 總 結(jié)

本文基于支持向量機分類的固有特點，闡述了直推式學(xué)習(xí)思想，介紹了幾種改進直推式學(xué)習(xí)算法的支持向量機分類算法。這些分類算法無論是利用成對標(biāo)注法還是區(qū)域標(biāo)注法都能有效地對無標(biāo)簽樣本點循序漸進地作出判別分類，并利用動態(tài)調(diào)整的規(guī)則使分類器具有一定的差錯修復(fù)能力，在保證算法精度的同時提高了訓(xùn)練的速度。支持向量機作為機器學(xué)習(xí)的一個重要內(nèi)容，涉及眾多的學(xué)習(xí)領(lǐng)域，例如人臉識別與檢測、圖像分類、文本分類、醫(yī)療診斷等。直推式學(xué)習(xí)是一個較新的研究領(lǐng)域，很多方面尚不成熟、不完善，許多的研究工作還僅處于初步階段。本文針對直推式支持向量機的學(xué)習(xí)算法做了一些總結(jié)研究工作，但在一定程度上還有很多有意義的課題值得進一步的挖掘和研究。

參考文獻：

[1] VAPNIK V.Statistical Learning Theory[M].New York，USA：Wiley Press，1998

[2] JOACHIMS T.Transductive inference for text classification using support vector machines. In：Proceedings of the 16thInternational Conference on Machine Learning[J]. San Francisco：Morgan Kaufmann Pulishers，1999.200-209

[3] 陳毅松，汪國平，董士海.基于支持向量機的漸近直推式分類學(xué)習(xí)算法[J].軟件學(xué)報，2003，14(3)：451-460

[4] 薛貞霞，劉三陽，劉萬里.基于SVDD的漸近直推式支持向量機學(xué)習(xí)算法[J].模式識別與人工智能.2008，21(6)：721-727

[5] WAHG Y. Training TSVM with The Proper Number of Positive Samples[J].Pattern Recognition Letters 26，2005：2187-2194

[6] 丁要軍，蔡皖東.采用兩階段策略模型的P2P流量識別方法[J].西安交通大學(xué)學(xué)報.2012，46(2)：45-50

[7] YU X，YANG J，ZHANG J P. A Transductive Support Vector MachineAlgorithm Based on Spectral[J].AASRI Procedia.2012，1：384-388

[8] 王磊.支持向量機學(xué)習(xí)算法的若干問題的研究[C].電子科技大學(xué)博士論文，2010：97-105

[9] ZHANG R，WANG W J，MA Y C. Least Square Transduction Support Vector Machine[J]. Neural Process Lett，2009(29)：133-142

[10] 趙瑩.半監(jiān)督支持向量機學(xué)習(xí)算法研究[C].哈爾濱工程大學(xué)博士論文，2010：38-45

[11] 劉宇，朱隨江，劉寶旭.采用改進PTSVM的入侵檢測研究[J].計算機工程與應(yīng)用，2012，48(5)：1-4

[12] CHEN M S，HO T Y，HUANG D Y.Online Transductive Support Vector Machines for Classification[J].2012IEEE.2012：258-261

[13] 王安娜，李云路.一種新的半監(jiān)督直推式支持向量機分類算法[J].儀器儀表學(xué)報，2011，32(7)：1546-1550

[14] MAULIK U，MUKHOPADHYAY A.Gene-Expression-Based Cancer Subtypes Predition Through Feature Selection and Transductive SVM[J].IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING，2013，60(4)：1111-1117

[15] DEBASIS C，SHIBU D.Cancer Classification through Feature Selection and Transductive SVM Using Gene Microarray Data.2012 Thid International Conference on Emerging Applications of Information Technology [J].IEEE.2012.77-80

[16] DEBASIS C，UJJWAL M.Semisupervised Pixel Classification of Remote Sensing Imagery Using Transductive SVM.2011 International Conference on Recent Trends in Information Systems[J].IEEE computer society，2011：30-35