王利文， 劉瓊蓀

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

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

1 直推式支持向量機

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

(1)

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

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

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

2.1 漸近直推式支持向量機學習算法

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

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

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

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

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

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

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

2.2 TSVM中Np的確定新方法

(2)

(3)

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

(4)

或者測試樣本被標記為負樣本，它所對應的松弛變量ξ*滿足如下條件：

(5)

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

2.3 TSVM的模糊漸進式學習算法

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

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

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

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

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

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

s.t. 0

(6)

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

s.t. -1

(7)

其中

(8)

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

2.6 Semi TSVM 算法[13]

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

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

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

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

(9)

(10)

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

(11)

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

2.7 改進的TSVM最新算法

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

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

3 總 結

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

參考文獻：

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

[4] 薛貞霞，劉三陽，劉萬里.基于SVDD的漸近直推式支持向量機學習算法[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].西安交通大學學報.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] 王磊.支持向量機學習算法的若干問題的研究[C].電子科技大學博士論文，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)督支持向量機學習算法研究[C].哈爾濱工程大學博士論文，2010：38-45

[11] 劉宇，朱隨江，劉寶旭.采用改進PTSVM的入侵檢測研究[J].計算機工程與應用，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].儀器儀表學報，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