Laplacian正則項半監(jiān)督不平行超平面分類機

閆金花　楊志霞

摘要：本文通過引入拉普拉斯（Laplacian）正則項，針對半監(jiān)督分類問題我們建立了基于拉普拉斯正則項的半監(jiān)督不平行超平面分類機。和經(jīng)典的雙支持向量機相比，該算法不僅繼承了不平行超平面決策的優(yōu)點，并且將其推廣到了半監(jiān)督分類問題中。最后在人工數(shù)據(jù)上進(jìn)行數(shù)值實驗，與拉普拉斯雙支持向量機和拉普拉斯支持向量機做比較，數(shù)值結(jié)果表明我們提出算法的可行性和有效性，特別是對于交叉型數(shù)據(jù)集，基于拉普拉斯正則項的半監(jiān)督不平行超平面分類機具有明顯較高的分類精確度。

關(guān)鍵詞：支持向量機 半監(jiān)督分類問題 拉普拉斯正則項 不平行超平面分類機

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）06-0221-04

Abstract：In this paper， we have proposed a novel Laplacian nonparallel hyperplanes classifier for the semi-supervised classification problem.Compared with the twin support vector machine， it has the advantage of nonparallel hyperplanes classifier and can be used for the semi-supervised classification problem. Finally， compared with the Laplacian twin support vector machine and the Laplacian support vector machine， the results of experiments on artificial dataset and UCI datasets show that our method is feasible， especially for“Cross Planes”datasets.

Key Words：Support vector machine； Semi-supervised classification problem； Laplacian regularization； Nonparallel hyperplanes classifier

1 引言

機器學(xué)習(xí)在人工智能的研究中具有非常重要的地位。支持向量機是Vapnik等在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的針對小樣本的機器學(xué)習(xí)方法[1]。該方法由于具有較強的泛化能力、方便對高維的數(shù)據(jù)進(jìn)行操作而得到了日益廣泛的研究和應(yīng)用。傳統(tǒng)的有監(jiān)督的分類方法，雖然能夠有效地解決各種實際問題，但是需要事先對大量樣本進(jìn)行標(biāo)記以獲取足夠的訓(xùn)練樣本，代價高，效率低。因此，根據(jù)實際需要研究人員提出了一些半監(jiān)督支持向量機分類方法。Bennett， K.，& Demiriz，A.于1999年提出了半監(jiān)督支持向量機（S3VM[2]），它基于聚類假設(shè)，試圖通過探索未標(biāo)記數(shù)據(jù)來規(guī)范調(diào)整決策邊界，從而提高運算的準(zhǔn)確度。21世紀(jì)以來，Melacci，S.，&Belkin，M提出了拉普拉斯（Laplacian）支持向量機[3]，主要是通過圖的拉普拉斯矩陣來探索數(shù)據(jù)的流形結(jié)構(gòu)，通過對無標(biāo)記的數(shù)據(jù)找到合適的類別，以使它們與已標(biāo)記的數(shù)據(jù)和潛在的圖的結(jié)構(gòu)的不一致性最小化，從而提高了預(yù)測精確度。

本文將拉普拉斯（Laplacian）正則項引入到不平行超平面分類機[4]之中，建立了拉普拉斯正則項的半監(jiān)督不平行超平面分類機。同時，在數(shù)值試驗中，從精度和速度上，和經(jīng)典的拉普拉斯正則項支持向量機和拉普拉斯正則項雙支持向量機做了對比，表明了提出的算法的優(yōu)良性。

2 背景知識

4 數(shù)值實驗

這一節(jié)通過數(shù)值實驗來檢驗基于拉普拉斯正則項的不平行超平面分類機（Lap-NHSVM）。具體地，主要由分類準(zhǔn)確率和計算時間作為判別指標(biāo)，與拉普拉斯支持向量分類機（Lap-SVM）、拉普拉斯雙支持向量分類機（Lap-TSVM）作對比，這里考慮了線性和非線性兩種情形。利用UCI數(shù)據(jù)庫中的六組數(shù)據(jù)。本文中核函數(shù)定為高斯核，在實驗中參數(shù)均選自于集合隨機的選取30%的數(shù)據(jù)集通過十折交叉檢驗法[1]來確定參數(shù)。數(shù)值實驗在Windows 7系統(tǒng)上完成，處理器為英特爾酷睿雙核，主頻為 2.2GHz，內(nèi)存為2GB。程序代碼基于Matlab R2010a平臺上完成。具體的算法我們采用逐次松弛迭代算法（SOR）[4]。

圖1表示Lap-SVM，Lap-TSVM和Lap-NPSVM的分類比較，小正方形代表有標(biāo)簽正類樣本點，大正方形代表無標(biāo)簽正類樣本點，小圓代表有標(biāo)簽負(fù)類樣本點，大圓代表無標(biāo)簽負(fù)類樣本點。

Lap-TSVM和Lap-NHSVM做對比，從圖1可以看出Lap-NHSVM具有明顯比較好的分類精度，能夠更好的利用未標(biāo)簽的數(shù)據(jù)，從而使分類效果更好。

在下面表1和表2的實驗中，我們利用UCI數(shù)據(jù)中的六個數(shù)據(jù)來做數(shù)值實驗，包括Diabetes，German，Ionosphere，Sonar，Australian，Heart。在機器學(xué)習(xí)中，這些數(shù)據(jù)經(jīng)常會被用來檢測算法的優(yōu)劣，在實驗中，取每個數(shù)據(jù)集的40%作為有標(biāo)簽的樣本集，30%作為無標(biāo)簽的樣本集，進(jìn)行十次試驗，取十次實驗結(jié)果的平均值加減方差構(gòu)成。對于CPU時間，同樣取十次實驗結(jié)果的平均值。如圖所示，黑體表示最高精確度對應(yīng)的數(shù)據(jù)，表1表示線性情形時，Lap-SVM，Lap-TSVM和Lap-NHSVM的比較，表2表示非線性情形時，Lap-SVM，Lap-TSVM和Lap-NHSVM的比較，從實驗結(jié)果可以明顯的看出，對于大部分?jǐn)?shù)據(jù)集，拉普拉斯不平行超平面分類機具有更高的分類精確度，例如，對于Lonosphere數(shù)據(jù)集，Lap-NHSVM對應(yīng)的精確度為88.32%，而Lap-SVM，Lap-TSVM對應(yīng)的精確度遠(yuǎn)小于它，另一方面，從下表可以看出，Lap-NHSVM對應(yīng)的CPU時間要比Lap-SVM的快速，卻比Lap-SVM和Lap-TSVM的精確度高。

5 結(jié)語

在本文中，提出了基于拉普拉斯正則項的半監(jiān)督不平行超平面分類機，從數(shù)值實驗可以看出，提出的分類方法具有較高的分類精確度，尤其對于某些數(shù)據(jù)集，例如交叉數(shù)據(jù)集，我們的算法可以得到更精準(zhǔn)的結(jié)果，因此我們可以看出，本文提出的半監(jiān)督不平行超平面分類方法值得肯定。

參考文獻(xiàn)

[1]V.Vapnik.The Nature of Statistical Learning Theory. Springer-Verlag， 2nd edition， 1998.

[2]Bennett，K.，& Demiriz， A. （1999）. Semi-supervised support vector machines.In Advances in Neural Information Processing Systems 11， 368-374.

[3]Melacci，S.，&Belkin，M（2011）.Laplacian support vector machines trained in the primal.Journal of Machine Learning Research，12.

[4]Shao Y H， Chen W J， Deng N Y. Nonparallel hyperplane support vector machine for binary classification problems[J]. Information Sciences263（2014）22-35.

[5]Belkin et al.，（2006）.Manifold regularization；a geometric framework for learning from labeled and unlabeled examples.Journal of Machine Research，7，2399-2434.

[6]O.L. Mangasarian， E.W. Wild， Multisurface proximal support vector classification via generalize deigenvalues， IEEE Transactions on Pattern Analysisand Machine Intelligence28 （1）（2006） 69-74.

[7]鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機[M].2版.北京：科學(xué)出版社，2009：356-357.

[8]O.L.Mangasarian， E.W. Wild， Multisurface proximal support vector classification via generalize deigenvalues， IEEE Transactions on Pattern Analysisand Machine Intelligence 28 （1） （2006） 69-74.

[9]Y.H.Shao，C.H.Zhang，X.B.Wang， N.Y. Deng， Improvements on twin support vector machines，IEEE Transactions on Neural Networks 22（6）（2011）962-968.