郝勇智

(中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原 030051)

傳統(tǒng)機(jī)器學(xué)習(xí)問題分為兩類:無監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)。無監(jiān)督學(xué)習(xí)僅僅利用為無標(biāo)簽樣本集，而監(jiān)督學(xué)習(xí)則需要大量有標(biāo)簽的樣本集，但在很多實(shí)際應(yīng)用中，獲取少量的已標(biāo)記數(shù)據(jù)通常需要較大的代價(jià)，但獲取未標(biāo)記數(shù)據(jù)的代價(jià)要小很多。這就使得同時(shí)利用已標(biāo)記樣本集和未標(biāo)記樣本集的半監(jiān)督學(xué)習(xí)方法快速發(fā)展起來。

支持向量機(jī)(SVM)是20 世紀(jì)90 年代由V.Vapnik 首先提出，它建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上的新型機(jī)器學(xué)習(xí)算法。標(biāo)準(zhǔn)支持向量機(jī)具有良好的推廣能力，已經(jīng)被應(yīng)用到很多場(chǎng)景中并發(fā)揮著重要作用。標(biāo)準(zhǔn)支持向量機(jī)算法都屬于監(jiān)督學(xué)習(xí)的算法，倘若可以將半監(jiān)督學(xué)習(xí)的思想很好地引入到標(biāo)準(zhǔn)支持向量機(jī)中，就能解決標(biāo)準(zhǔn)支持向量機(jī)依賴大量已標(biāo)記樣本的問題，進(jìn)而改進(jìn)監(jiān)督分類方法［1］的性能，訓(xùn)練得到分類性能更好的分類器，從而獲得更好的分類效果。

1 背景知識(shí)

1.1 流形判別分析(MDA)

流形判別分析［2］是由劉忠寶等提出的，文獻(xiàn)［2］在借鑒線性判別分析(Linear Discriminant Analysis，LDA)［3］，通過在Fisher 準(zhǔn)則基礎(chǔ)上，最大化基于流形的類內(nèi)離散度與基于流形的類間離散度之比實(shí)現(xiàn)降低維度，進(jìn)而提出了流形判別分析方法(MDA)。

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

基于聚類假設(shè)的半監(jiān)督支持向量機(jī)(S3VM)和直推式支持向量機(jī)(TSVM)是等價(jià)的，因?yàn)樗僭O(shè)不同類別的未標(biāo)記數(shù)據(jù)可以由一個(gè)較大的邊界區(qū)分開。由于S3VM 主要是通過最大化未標(biāo)記數(shù)據(jù)邊界來實(shí)現(xiàn)該算法，所以S3VM 是帶有未標(biāo)記數(shù)據(jù)的標(biāo)準(zhǔn)支持向量機(jī)的擴(kuò)展。標(biāo)準(zhǔn)支持向量機(jī)算法只能使用已標(biāo)記數(shù)據(jù)作為訓(xùn)練集，但在S3VM 算法中，已標(biāo)記和未標(biāo)記均能被利用。為了利用未標(biāo)記的數(shù)據(jù)，半監(jiān)督支持向量機(jī)在標(biāo)準(zhǔn)支持向量機(jī)的基礎(chǔ)上，增加了兩個(gè)對(duì)未標(biāo)記數(shù)據(jù)點(diǎn)的限制。其中一個(gè)約束是假設(shè)此點(diǎn)屬于第一個(gè)類別，并且計(jì)算它的錯(cuò)分率;另外一個(gè)假設(shè)此點(diǎn)屬于第二個(gè)類別，并且也計(jì)算它的錯(cuò)分率。目標(biāo)函數(shù)選兩個(gè)錯(cuò)分率中較小的作為該樣本的類別標(biāo)簽。以上做法通過所加入的約束項(xiàng)來使未標(biāo)記數(shù)據(jù)能夠落在邊界之外，這就可以使得線性邊界在已標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)上都有最大邊界，決策邊界在未標(biāo)記數(shù)據(jù)集上有最小的泛化誤差。

圖1 S3VM

如圖1 所示，未標(biāo)記數(shù)據(jù)有助于決定邊界的稀疏區(qū)域。若僅有已標(biāo)記數(shù)據(jù)，則最大邊界由虛線表示，如果還有未標(biāo)記點(diǎn)(空心點(diǎn))，則實(shí)線表示最大邊界。

算法1 半監(jiān)督SVM 算法

輸入:核K，權(quán)值λ1和λ2，已標(biāo)記樣本集未標(biāo)記樣本集L={x1，y1}，未標(biāo)記樣本集U={xu}。

輸出:由f(x)的符號(hào)對(duì)測(cè)試樣例x 的分類。

TSVM 能夠看作在未標(biāo)記樣本上增加一個(gè)額外正則化項(xiàng)。令f(x)=h(x)+b，此處h(x)∈Hx。最優(yōu)化問題為:

此部分進(jìn)一步分析下TSVM 算法。利用歸納推理為在給定的點(diǎn)估算函數(shù)的值包括兩個(gè)步驟，首先，由訓(xùn)練點(diǎn)估計(jì)用于整個(gè)輸入空間的函數(shù)。其次，在單獨(dú)的測(cè)試點(diǎn)基于所估計(jì)的參數(shù)來計(jì)算得到函數(shù)的值。與此相反，正如Vapnik 指出的直推式問題比歸納式問題簡(jiǎn)單，在直推理論，其最終目的是在預(yù)定的測(cè)試點(diǎn)決斷函數(shù)的值。文獻(xiàn)［4］表明，只要最終目標(biāo)函數(shù)是在選定點(diǎn)的值時(shí)，直推方法比歸納法更精確和直接，并產(chǎn)生更好的結(jié)果，這是因?yàn)闇y(cè)試集被重新構(gòu)造作為學(xué)習(xí)的問題的一部分。圖2 展示出歸納式SVM 和直推式SVM 在分類邊界上的比較。圖2(a)利用歸納學(xué)習(xí)支持向量機(jī)分類器發(fā)現(xiàn)邊界。只有標(biāo)記點(diǎn)(+和o)用于訓(xùn)練。圖2(b)利用直推式學(xué)習(xí)支持向量機(jī)分類器邊界。所有點(diǎn)，包括有標(biāo)簽的和測(cè)試(沒有標(biāo)簽的)，都用于訓(xùn)練。在測(cè)試樣本中得到了較好的分類結(jié)果。

圖2 直推式在二維輸入空間的精度示例

TSVM 是一個(gè)使用直推式推理的有趣的支持向量機(jī)版本。在這種情況下，TSVM 嘗試找到的超平面＜w，b ＞和以最大限度的最小誤差找到測(cè)試數(shù)據(jù)標(biāo)簽，從而獲取測(cè)試數(shù)據(jù)在某一個(gè)步驟中的標(biāo)簽。

Vapnik 等人在特定的測(cè)試集中通過加入誤差而使得測(cè)試集最小化的方法所提出的規(guī)劃加強(qiáng)了分類器的準(zhǔn)確性。我們注意到，以最小成本的錯(cuò)誤找到分離訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)的超平面來解決問題，以便最大限度地減少訓(xùn)練誤差和測(cè)試誤差。采用組合優(yōu)化方法的目的是首先找到一組二元變量。然后，固定，進(jìn)而我們得到以下式子必須最大化:

優(yōu)化問題相對(duì)于所有組合問題的大小增加，想找到確切的解決方案需要在未標(biāo)記的數(shù)據(jù)的所有可能的標(biāo)簽中搜索。顯然，對(duì)于大量的數(shù)據(jù)這是不可行的［5］。

Joachims 提出了以某種啟發(fā)式算法解決其問題的組合方法，它的實(shí)現(xiàn)解決了大問題;但是，仍不能保證其收斂性。隨后，Chapelle 等提出的應(yīng)用分支定界技術(shù)來獲得全局最優(yōu)解。雖然他們的方法提供了一個(gè)很好的解決方案，但它不能應(yīng)用于一個(gè)大的數(shù)據(jù)集。有趣的是，作者的結(jié)論是，直推式推理可以用來比較半監(jiān)督學(xué)習(xí)用在未標(biāo)記測(cè)試數(shù)據(jù)集中預(yù)測(cè)結(jié)果的好壞。事實(shí)上，最大化邊緣在兩個(gè)已標(biāo)記和未標(biāo)記的數(shù)據(jù)間提供了一個(gè)低密度區(qū)(半監(jiān)督學(xué)習(xí)聚類假設(shè))的決策邊界［6］。

2 基于流形判別分析的半監(jiān)督支持向量機(jī)

2.1 最優(yōu)化問題

鑒于SVM 在應(yīng)用中所面臨的泛化能力有限、有標(biāo)記樣本點(diǎn)不足等問題。本文提出了基于流形判別分析的半監(jiān)督支持向量機(jī)MDASSVM。流形判別分析的引入保證了分類決策對(duì)樣本分布特征、邊界信息、局部信息的考慮。

MDASSVM 的最優(yōu)化問題可表示如下:

由Lagrangian 定理可得上述最優(yōu)化問題的對(duì)偶形式為:

式中，k(ri，rj)=φ(ri)Tφ(rj)。

2.2 決策函數(shù)

MDASSVM 的決策函數(shù)定義為:

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

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中使用的測(cè)試數(shù)據(jù)為一組人造數(shù)據(jù)集和一組實(shí)際數(shù)據(jù)集，實(shí)際數(shù)據(jù)集選自UCI 數(shù)據(jù)集。所有算法均在Matlab2013 上實(shí)現(xiàn)。實(shí)驗(yàn)平臺(tái)為Intel?Pentium?CPU G645，4G內(nèi)存，Windows7。通過與SVM，PTSVM 等分類方法的比較實(shí)驗(yàn)驗(yàn)證MDASSVM 學(xué)習(xí)泛化能力。通過測(cè)試人造數(shù)據(jù)集來表明該方法在選擇分類函數(shù)過程所依據(jù)的基本原理以及參數(shù)的影響，在真實(shí)數(shù)據(jù)集上的測(cè)試是為了說明該方法在分類決策時(shí)同時(shí)考慮樣本的類間信息、分布特征以及類內(nèi)流行結(jié)構(gòu)情況下的分類性能。上述方法的分類精度均與參數(shù)選擇有關(guān)，且所有實(shí)驗(yàn)樣本首先歸一化為［－1，1］。本文采用5倍交叉驗(yàn)證法來獲取實(shí)驗(yàn)參數(shù)，參數(shù)通過網(wǎng)格搜索策略選擇網(wǎng)格{0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9}。對(duì)于非線性映射采用徑向基函數(shù)(Radial basis function，RBF):K(x，y)其中γ值在集合中選取，其中σ 為訓(xùn)練樣本平均范數(shù)的平方根。對(duì)算法的評(píng)價(jià)標(biāo)準(zhǔn)是分類精度，即分類的正確率(正確分類的個(gè)數(shù)除以總的分類個(gè)數(shù))。

3.2 人造數(shù)據(jù)

取2 類正態(tài)隨機(jī)分布的樣本，類概率分別為P(ω1)=0.6;P(ω2)=0.4。

類1 和類2 的樣本均值為μ1=［0 0］T，μ2=［1 2 1 2］T。

從每一個(gè)類別中選出20% 作為有標(biāo)簽樣本，剩下的80%作為無標(biāo)簽樣本;在以上的環(huán)境條件中進(jìn)行100 次獨(dú)立實(shí)驗(yàn)并取平均值，表1 給出了實(shí)驗(yàn)的對(duì)比結(jié)果。

表1 人造數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果比較

從表1 中結(jié)果可以看出，在樣本分布相同的情況下，標(biāo)準(zhǔn)SVM 訓(xùn)練時(shí)間明顯小于PTSVM 算法的訓(xùn)練時(shí)間。而MDASSVM 算法的訓(xùn)練時(shí)間介于標(biāo)準(zhǔn)SVM 和PTSVM 之間，這是因?yàn)樵诘^程MDASSVM 算法采用SSVM 算法，每次迭代的訓(xùn)練時(shí)間都大于標(biāo)準(zhǔn)SVM 算法的時(shí)間小于PTSVM。從分類精度上看，該實(shí)驗(yàn)所使用的人工生成的數(shù)據(jù)集基本滿足線性可分的條件，在這種情況下，標(biāo)準(zhǔn)SVM、PTSVM 和MDASSVM 擁有相似的分類精度，但對(duì)于標(biāo)準(zhǔn)SVM 而言，有標(biāo)簽樣本數(shù)過少在一定程度上影響了分類器的分類性能。

3.3 實(shí)際數(shù)據(jù)集

所用UCI 數(shù)據(jù)集如表2 所示。

表2 UCI 數(shù)據(jù)集

其中Liver 數(shù)據(jù)集中訓(xùn)練樣本由每類中抽取40 個(gè)樣本組成，測(cè)試樣本由每類中抽取20 個(gè)樣本組成，剩余樣本組成無標(biāo)記樣本;Ionosphere 數(shù)據(jù)集中訓(xùn)練樣本及測(cè)試樣本分別抽取20 個(gè)樣本組成，剩余組成無標(biāo)記樣本;Wine 數(shù)據(jù)集和Diabetes 數(shù)據(jù)集訓(xùn)練樣本及測(cè)試樣本分別從每類中抽取出20 個(gè)組成，剩下的組成無標(biāo)記樣本。

在上述的環(huán)境中獨(dú)立進(jìn)行10 次實(shí)驗(yàn)取平均精度，實(shí)驗(yàn)結(jié)果如表3。

表3 實(shí)際數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果比較

從表3 中可以看出，同樣情況下，MDASSVM 算法的訓(xùn)練精確度較PTSVM 算法有所提高;2 個(gè)半監(jiān)督學(xué)習(xí)算法訓(xùn)練的精度比標(biāo)準(zhǔn)SVM 這種傳統(tǒng)的監(jiān)督學(xué)習(xí)算法要大得多，MDASSVM 也體現(xiàn)了半監(jiān)督式學(xué)習(xí)的優(yōu)勢(shì)同時(shí)也驗(yàn)證了該文前面的分析，達(dá)到了算法的預(yù)期效果。

4 結(jié)論

大量的實(shí)驗(yàn)結(jié)果表明，高維數(shù)的數(shù)據(jù)點(diǎn)分布在一個(gè)低維的流形上，故本文在流形判別分析的基礎(chǔ)上提出了基于流形判別分析的半監(jiān)督支持向量機(jī)(MDASSVM)。通過在人造數(shù)據(jù)集和實(shí)際數(shù)據(jù)集(部分UCI 數(shù)據(jù)集)上的實(shí)驗(yàn)，驗(yàn)證了提出的算法相比于現(xiàn)有算法，在減少算法時(shí)間的同時(shí)更能提高分類的準(zhǔn)確率。盡管MDASSVM 采用MDA 對(duì)原始輸入數(shù)據(jù)進(jìn)行降維處理來達(dá)到解決問題的目的，但是仍然還有如:降維維數(shù)的優(yōu)化問題、降維后信息缺失問題等有待進(jìn)一步解決。

［1］Collobert R，Sinz F，Weston J.Large Scale Transductive SVMs［J］.Journal of Machine Learning Research，2006，7:1687－1712.

［2］劉忠寶，潘廣貞，趙文娟.流形判別分析［J］.電子與信息學(xué)報(bào)，2013，35(9):2047－2053.

［3］Belkin M，Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation［J］.Neural Computation，2003，15(6):1373－1396.

［4］Zhang Z Y，Zha H Y.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment［J］.SIAM Journal of Scientific Computing，2005，26(1):313－338.

［5］王守覺.仿生模式識(shí)別(拓?fù)淠Ｊ阶R(shí)別)一種模式識(shí)別新模型的理論與應(yīng)用［J］.電子學(xué)報(bào)，2002，30(10):1417－1420.

［6］Martinez A M，Kak A C.PCA versus LDA［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(2):228－233.