Laplacian正則項半監督不平行超平面分類機

閆金花　楊志霞

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

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

中圖分類號：TP181 文獻標識碼：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 引言

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

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

2 背景知識

4 數值實驗

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

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

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

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

5 結語

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

參考文獻

[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]鄧乃揚，田英杰.數據挖掘中的新方法-支持向量機[M].2版.北京：科學出版社，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.