王利文， 劉瓊蓀

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

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

1 直推式支持向量機(jī)

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

(1)

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

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

2 直推式支持向量機(jī)的幾種改進(jìn)算法

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

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

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

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

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

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

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

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

2.2 TSVM中Np的確定新方法

(2)

(3)

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

(4)

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

(5)

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

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

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

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

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

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

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

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

s.t. 0

(6)

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

s.t. -1

(7)

其中

(8)

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

2.6 Semi TSVM 算法[13]

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

(1) 半標(biāo)定樣本點(diǎn)的選擇。在選擇半標(biāo)定樣本加入到混合訓(xùn)練樣本集的時(shí)候，主要考慮兩點(diǎn)：選擇的樣本應(yīng)該被加入到正確的類別中；應(yīng)該選擇含有“信息”的半標(biāo)定樣本。因?yàn)榉诸惓矫媸墙⒃谥С窒蛄康幕A(chǔ)之上，所以應(yīng)該選擇含分類信息最豐富的兩類樣本的支持向量。

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

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

(9)

(10)

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

(11)

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

2.7 改進(jìn)的TSVM最新算法

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

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

3 總 結(jié)

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

參考文獻(xiàn)：

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

[4] 薛貞霞，劉三陽，劉萬里.基于SVDD的漸近直推式支持向量機(jī)學(xué)習(xí)算法[J].模式識(shí)別與人工智能.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流量識(shí)別方法[J].西安交通大學(xué)學(xué)報(bào).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] 王磊.支持向量機(jī)學(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)督支持向量機(jī)學(xué)習(xí)算法研究[C].哈爾濱工程大學(xué)博士論文，2010：38-45

[11] 劉宇，朱隨江，劉寶旭.采用改進(jìn)PTSVM的入侵檢測(cè)研究[J].計(jì)算機(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ī)分類算法[J].儀器儀表學(xué)報(bào)，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