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

閆金花　楊志霞

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

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

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

2 背景知識(shí)

4 數(shù)值實(shí)驗(yàn)

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

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

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

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

5 結(jié)語

在本文中，提出了基于拉普拉斯正則項(xiàng)的半監(jiān)督不平行超平面分類機(jī)，從數(shù)值實(shí)驗(yàn)可以看出，提出的分類方法具有較高的分類精確度，尤其對(duì)于某些數(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]鄧乃揚(yáng)，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機(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.