孟 巖，汪云云

(南京郵電大學 計算機學院/軟件學院，江蘇 南京 210000)

典型半監(jiān)督分類算法的研究分析

孟 巖，汪云云

(南京郵電大學 計算機學院/軟件學院，江蘇 南京 210000)

近年來，大量半監(jiān)督分類算法被提出。然而在真實的學習任務中，研究者很難決定究竟選擇哪一種半監(jiān)督分類算法，而在這方面并沒有任何指導。半監(jiān)督分類算法可通過數據分布假設進行分類。為此，在對比分析采用不同假設的半監(jiān)督分類典型算法的基礎上，以最小二乘方法(Least Squares，LS)為基準，研究比較了基于聚類假設的轉導支持向量機(Transductive Support Vector Machine，TSVM)和基于流行假設的正則化最小二乘法(Laplacian Regularized Least Squares Classification，LapRLSC)，并同時利用兩種假設的SemiBoost以及無任何假設的蘊含限制最小二乘法(Implicitly Constrained Least Squares，ICLS)的分類效果。得出的結論為，在已知數據樣本分布的情況下，利用相應假設的方法可保證較高的分類正確率；在對數據分布沒有任何先驗知識且樣本數量有限的情況下，TSVM能夠達到較高的分類精度；在較難獲得樣本標記而又強調分類安全性時，宜選擇ICLS，而LapRLSC也是較好的選項之一。

半監(jiān)督分類；數據分布；聚類假設；流行假設

1 概 述

傳統(tǒng)的機器學習技術分為兩類：監(jiān)督學習和無監(jiān)督學習。監(jiān)督學習只利用標記的樣本集進行學習，而無監(jiān)督學習只利用未標記的樣本集進行學習，但在很多實際問題中，有標記樣本通常很難收集，而無標記樣本很容易得到。例如，在垃圾郵件檢測中，可以自動收集大量的郵件，卻只有少量是標記的垃圾郵件；在生物學中，大量的未標記數據很容易得到，而對某種蛋白質的結構分析或者功能鑒定，可能會花上生物學家很多年的時間。因此，同時利用標記樣本和未標記樣本的半監(jiān)督學習技術在近些年發(fā)展迅速[1-4]。

半監(jiān)督分類算法利用大量的無標記樣本與有標記樣本一同訓練，以增強分類效果。為了更加有效地利用有標記樣本，提出了一些數據分布假設，常見的有兩種：一種是聚類假設，分類邊界穿過數據低密度區(qū)域，把數據分為幾簇聚類，在一簇中的樣本具有相同的標簽；另一種是流行假設，充分利用數據在低維空間上的流行分布，并通過拉普拉斯圖構造數據流行內在的幾何結構，從而在這個圖中相似的樣本具有相同的標簽。

幾乎所有的半監(jiān)督分類算法都顯式或隱式地利用了這兩種假設[1,4]。例如，轉導支持向量機(TSVM)[5]和其他擴展方法[6-8]都利用了聚類假設。而那些基于圖的半監(jiān)督分類方法(graph cuts[9],label propagation[10-11])和流行正則化最小二乘法(LapRLSC)[12]都利用了流行假設。除此之外，有的方法同時利用這兩種假設來增強分類效果。半監(jiān)督Boosting[13-14]就是一種同時利用兩種假設，并利用迭代的boosting算法[15]來增強分類效果的半監(jiān)督分類方法。另一種相關的算法是正則化Boosting算法[16]，它同時利用boosting框架和結合了平滑性的以上兩種常用假設。上述方法都顯式地利用了一種或者兩種假設。后來，Jesse提出了一種不利用任何顯式假設的奇異的半監(jiān)督分類方法—蘊含限制的最小二乘法(ICLS)[17]。ICLS在多維情況下比全監(jiān)督最小二乘法(LS)分類更加準確，且在一維情況下分類精度不會低于全監(jiān)督最小二乘法。

在已提出的大量的半監(jiān)督分類方法中，既有利用聚類假設和流行假設中的一種的方法，也有同時利用兩種的方法，甚至不利用任何假設的方法。但是很難在真實的半監(jiān)督學習任務中決定采用哪種方法或假設，先前研究者們都致力于研究能夠提高分類精度的新方法[18-19]，幾乎沒有把精力用于比較各個方法的分類效果[20-21]。針對真實的學習任務中選擇何種半監(jiān)督分類方法這一問題，對典型半監(jiān)督分類方法進行了比較。由于半監(jiān)督分類方法可以通過數據分布假設來劃分種類，因此，比較了幾種較典型的應用不同假設的方法。以LS為基準，比較了TSVM、LapRLSC，同時利用兩種假設的半監(jiān)督Boosting算法，以及ICLS在真實數據集上的分類效果。

2 半監(jiān)督分類方法

2.1轉導支持向量機

聚類假設是兩種常見的半監(jiān)督分類假設中的一種，它假設在同一簇聚類中的樣本具有相同的標簽，分類邊界穿過低密度區(qū)域來劃分不同的簇。因此，聚類假設也被稱作低密度分離假設。TSVM是利用聚類假設的半監(jiān)督算法的典型代表。

(1)

TSVM首先通過歸納式SVM在訓練集上訓練得到初始分類器，然后把無標記樣本分為正類或負類，再根據目標函數的下降程度，轉換無標記樣本的類別標簽，最后通過迭代的策略解決最優(yōu)化問題(1)。

2.2流行正則化

另一種半監(jiān)督分類學習中常用的假設是流行假設，該假設設想數據在低維服從流行分布。這個數據流行內在的幾何結構通常由拉普拉斯圖表示，圖中的頂點代表樣本，圖中的邊權值代表樣本間的相似度。根據流行假設可知，圖中相似的節(jié)點具有相同的標簽。流行正則化[12,22]是基于流行假設的經典算法，該算法充分利用流行分布的幾何結構，并且將數據的幾何結構與數據間的相似度約束相結合，作為附加的正則化項添加到目標函數中。

LapRLSC求解一個帶有最小二乘損失函數的最優(yōu)化問題：

(2)

選擇最小二乘損失作為損失函數，因此，正則化最小二乘法的目標函數可以寫為：

(3)

(4)

其中，α=[α1,α1,…,αn]∈RC×n為拉格朗日乘子矩陣；K為n×n的核矩陣；J=diag(1,…,1,0,…,0)為對角矩陣。

對目標函數求導，即可求得最優(yōu)解。

2.3半監(jiān)督Boosting

SemiBoost是一種同時利用聚類假設和流行假設，并且利用boosting框架訓練分類器的半監(jiān)督分類算法。用戶可以選擇一個偏愛的全監(jiān)督分類器，然后吸收無標記樣本來提升分類器的表現。對于每個無標記樣本xj，分別計算對其分類為正類或為負類的置信因子，其中被當前分類器賦予置信因子最高的無標記樣本標簽叫做“偽標簽”。在循環(huán)過程中，將這些帶有偽標簽的樣本和有標記樣本一同加入訓練集來訓練分類器，經歷一定次數的循環(huán)后，形成最終的分類器。SemiBoost模型可以定義如下：

s.t.h(xi)=yi,i=1,2,…,l

(5)

該優(yōu)化問題可以近似寫成：

(6)

為了最小化該目標函數，將選取樣本xi賦予的最優(yōu)類別標記為zi=sign(pi-qi)，選取樣本的權重為|pi-qi|，并且參數α的取值應為：

(7)

初始化H(x)=0，每次迭代由全監(jiān)督分類算法(LS)學習得到h(x)，并且更新分類器H(x)=H(x)+αtht(x)。

2.4蘊含限制的最小二乘法

不同于以上利用一種或兩種數據分布假設的半監(jiān)督分類算法，ICLS不利用任何明確的假設，只利用已經存在于全監(jiān)督最小二乘分類器中蘊含的假設。ICLS通過最小化一個常規(guī)的全監(jiān)督分類的損失來得到最優(yōu)分類器，其中全監(jiān)督損失由未標記樣本的所有可能標簽來定義。ICLS的目標函數可以寫為：

(8)

ICLS實際利用無標記樣本來最小化全監(jiān)督的損失函數。問題(8)的解可以看作是由全監(jiān)督子集β到半監(jiān)督子集Cβ的映射，可以寫成如下形式：

(9)

(10)

最終，可得到關于無標記樣本的最優(yōu)解。ICLS在多維情況下比全監(jiān)督最小二乘法分類更加準確，并且在一維情況下分類精度不會低于全監(jiān)督最小二乘法。

3 實驗及結果分析

3.1數據集和實驗設置

數據描述：真實數據集包含了13個UCI數據集和6個基準數據集，具體描述見表1。

對于真實數據集，同樣利用PCA[23]將其映射到2維空間，發(fā)現一些數據集的數據分布滿足聚類假設，例如Australian、Ionosphere。還有一些數據集滿足流行假設，如Digit1。另外，還有一些數據集同時滿足以上兩種假設，如WDBC、USPS。然而，大部分數據集的數據分布并不明確，比如Heart、Bupa、House等。

實驗設置：實驗中采用高斯核函數，其中高斯核的參數通過所有樣本點的平均距離決定。正則化參數rA和rI固定為1和0.1，設置半監(jiān)督Boosting的迭代次數為12次。

對于真實數據集的實驗，采用十字交叉驗證方法[24]，將每個數據集隨機分割為10等份，然后循環(huán)地以一組作為測試集，其余作為訓練集。訓練集中的有標記樣本個數的選取策略與ICLS[17]相同，其中有標記樣本是隨機選擇的，并且個數為l=max{m+5,20},m為樣本特征數。將做10次十字交叉驗證實驗，取其平均值作為結果，實驗結果見表2。

表1 真實數據集的數據分布

表2 分類錯誤率比較

3.2真實數據集的實驗結果比較

表2列出了真實數據集上的實驗結果。

根據表2，可以得出以下結論：

(1)在已知數據集的數據分布，或者能夠通過PCA降維得到相應數據分布的情況下，基于相應假設的半監(jiān)督分類方法表現出眾。例如，對于滿足聚類假設的數據集，TSVM分類效果最好，對滿足流行假設的數據集，LapRLSC分類錯誤率最低。另外，LapRLSC在同時滿足兩種假設的數據集上同樣有較低的錯誤率。

(2)當給定數據集不滿足任何數據分布假設，并且強調分類安全性時，ICLS會是明智的選擇。原因是ICLS分類精度不會低于全監(jiān)督最小二乘法，ICLS對于無標記樣本的使用不會惡化分類效果。同時，ICLS在Heart,Vehicle和Pima數據集上的分類精度是所有半監(jiān)督分類算法中最高的，而LapRLSC在這些數據集上的分類精度低于全監(jiān)督LS，TSVM和SemiBoost同樣不能保證分類效果優(yōu)于全監(jiān)督算法。

(3)SemiBoost同時利用流行假設和聚類假設，并采用迭代的Boosting算法框架，但是分類效果并沒有期望的出色。因此，需要在未來的工作中尋找更有效的算法來結合這些假設，并發(fā)揮它們的長處。

3.3健壯性比較

從真實數據集中選擇5個數據集，在賦予不同有標記樣本個數的情況下比較不同算法的健壯性。對于每個數據集，每次在訓練集中隨機選取5,10,20,50,100個樣本賦予標記，并且采用十字交叉驗證的實驗設置，每組實驗重復10次，取其平均值作為結果，實驗結果見表3。

表3 健壯性比較

根據表3可以看出：TSVM最穩(wěn)定，健壯性最好。尤其在有標記樣本數目較少的情況下，TSVM是分類精度最高的算法，但其精度并沒有隨著有標記樣本數目的增加而增加。因此，TSVM適用于給定有標記樣本數目有限的情況；ICLS和LapRLSC的分類精度明顯地隨著有標記樣本的個數的改變而改變。當有標記樣本數目較少時，無論是ICLS還是LapRLSC都沒有TSVM的分類精度高，但它們的分類精度隨著有標記樣本數目的增長而明顯增長。所以，ICLS和LapRLSC適用于給定有標記樣本較充裕的情況；SemiBoost無論是健壯性還是分類精度，表現都相對一般。

3.4分析討論

觀察以上實驗結果，可得到一些發(fā)現，并期望給選擇哪種半監(jiān)督分類算法做出一些指導。

(1)在可以明確數據集的數據分布的情況下，利用相應假設的半監(jiān)督分類算法能保證最好的分類效果。但在現實應用中很難得知數據的內在分布信息。

(2)若對于數據的真實分布沒有任何先驗知識，將很難判斷哪種半監(jiān)督分類算法比較適合目前的學習任務。從以上實驗結果可知，在有標記樣本數目較少的情況下，TSVM是分類精度最高的算法。因此，TSVM適用于給定有標記樣本數目有限的情況，即使其精度并沒有隨著有標記樣本數目的增加而明顯增加。

(3)ICLS是不利用任何假設的半監(jiān)督分類算法。研究者們已經證明了在假設不正確或有誤差時，無標記樣本有可能降低分類精度，而ICLS的分類精度卻從不低于全監(jiān)督LS。因此，若能獲取一定量的有標記樣本，并強調分類的安全性，盡管ICLS相對于全監(jiān)督算法的精度提升不是那么明顯(尤其是在基準數據集上)，仍然是最合適的算法。

(4)LapRLSC在滿足流行假設，甚至滿足聚類假設的數據集上的分類效果比較令人滿意。即使在某些情況下，LapRLSC的分類精度低于全監(jiān)督算法，但從總體上看，LapRLSC的分類效果最好。所以當有標記樣本不那么稀缺時，LapRLSC是一個不錯的選擇。

(5)盡管SemiBoost同時利用流行假設和聚類假設，但在以上的實驗中，SemiBoost并沒有令人印象深刻的表現。因此，其他更有效地利用多種假設的策略仍然值得研究。

4 結束語

大量的半監(jiān)督分類方法在理論上取得了長足進展，既有利用聚類假設或流行假設其中之一的數據分布假設的方法，也有利用兩種數據分布假設的方法，還有不利用任何假設的方法。因此，在真實的半監(jiān)督學習任務中，采用哪種方法或者假設確實是一個難題。文中比較了利用聚類假設的TSVM，利用流行假設的LapRLSC，同時利用以上兩種假設的半監(jiān)督Boosting算法，以及不利用任何假設的ICLS在真實數據集上的分類效果。

實驗結果表明，在已知數據分布的情況下，應該選擇利用相應假設的半監(jiān)督分類算法來保證獲得較高的分類精度；若事先不知道樣本的數據分布，并且給定的已標記樣本數量有限，可以優(yōu)先選擇TSVM；若具有一定數量的有標記樣本，并且強調分類的安全性，不利用任何假設的ICLS是比較合適的算法；另外，LapRLSC也是一個不錯的選擇。在真實的應用中還存在一些滿足多種數據分布的數據集，將在未來的工作中尋找一種將多種假設結合的更有效的算法。

[1] Fujino A,Ueda N,Nagata M.Adaptive semi-supervised learning on labeled and unlabeled data with different distributions[J].Knowledge and Information Systems,2013,37(1):129-154.

[2] Sun S,Hussain Z,Shawe-Taylor J.Manifold-preserving graph reduction for sparse semi-supervised learning[J].Neurocomputing,2014,124(2):13-21.

[3] 梁吉業(yè),高嘉偉,常 瑜.半監(jiān)督學習研究進展[J].山西大學學報:自然科學版,2009,32(4):528-534.

[4] Zhu S P,Huang H Z,Li Y,et al.Probabilistic modeling of damage accumulation for time-dependent fatigue reliability analysis of railway axle steels[J].Journal of Rail and Rapid Transit,2015,229(1):23-33.

[5] Joachims T.Transductive inference for text classification using support vector machines[C]//Proceedings of the 16th international conference on machine learning.Bled,Slovenia:[s.n.],1999:200-209.

[6] Wang Y,Chen S,Zhou Z H.New semi-supervised classification method based on modified cluster assumption[J].IEEE Transactions on Neural Networks and Learning Systems,2012,23(5):689-702.

[7] 高 瀅,劉大有,齊 紅,等.一種半監(jiān)督K均值多關系數據聚類算法[J].軟件學報,2008,19(11):2814-2821.

[8] 李昆侖,曹 錚,曹麗蘋,等.半監(jiān)督聚類的若干新進展[J].模式識別與人工智能,2009,22(5):735-742.

[9] Subramanya A,Talukdar P P.Graph-based semi-supervised learning[C]//Synthesis lectures on artificial intelligence and machine learning.[s.l.]:[s.n.],2014.

[10] Ugander J,Backstrom L.Balanced label propagation for partitioning massive graphs[C]//Proceedings of the sixth ACM international conference on web search and data mining.[s.l.]:ACM,2013:507-516.

[11] 肖 宇,于 劍.基于近鄰傳播算法的半監(jiān)督聚類[J].軟件學報,2008,19(11):2803-2813.

[12] Belkin M,Niyogi P,Sindhwani V.Manifold regularization:a geometric framework for learning from labeled and unlabeled examples[J].Journal of Machine Learning Research,2006,7:2399-2434.

[13] Mallapragada P K,Jin R,Jain A K,et al.Semiboost:boosting for semi-supervised learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(11):2000-2014.

[14] 侯 杰,茅耀斌,孫金生.一種最大化樣本可分性半監(jiān)督Boosting算法[J].南京理工大學學報:自然科學版,2014,38(5):675-681.

[15] Freund Y.Experiments with a new boosting algorithm[C]//Thirteenth international conference on machine learning.[s.l.]:[s.n.],1996:148-156.

[16] Chen K,Wang S.Semi-supervised learning via regularized boosting working on multiple semi-supervised assumptions[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(1):129-143.

[17] Krijthe J H,Loog M.Implicitly constrained semi-supervised least squares classification[C]//International symposium on intelligent data analysis.[s.l.]:Springer International Publishing,2015:158-169.

[18] 李亞娥,汪西莉.一種自適應的半監(jiān)督圖像分類算法[J].計算機技術與發(fā)展,2013,23(2):112-114.

[19] 皋 軍,王士同,鄧趙紅.基于全局和局部保持的半監(jiān)督支持向量機[J].電子學報,2010,38(7):1626-1633.

[20] Corollary A.A comparative study:globality versus locality for graph construction in discriminant analysis[J].Journal of Applied Mathematics,2014,2014:1-12.

[21] Qiao L,Zhang L,Chen S.An empirical study of two typical locality preserving linear discriminant analysis methods[J].Neurocomputing,2010,73(10-12):1587-1594.

[22] 柯 圣.基于樣本先驗信息的正則化型分類器設計研究[D].上海:華東理工大學,2014.

[23] Turk M,Pentland A.Eigenfaces for recognition. J Cogn Neurosci[J].Journal of Cognitive Neuroscience,1991,3(1):71-86.

[24] Refaeilzadeh P,Tang L,Liu H.Cross-validation[M]//Liu L,Zsu M T.Encyclopedia of database systems.New York:Springer,2009:532-538.

ResearchandAnalysisofTypicalSemi-supervisedClassificationAlgorithm

MENG Yan,WANG Yun-yun

(School of Computer and Software,Nanjing University of Posts & Telecommunications,Nanjing 210000,China)

Large amounts of semi-supervised classification algorithms have been proposed recently,however,it is really hard to decide which one to use in real learning tasks,and further there is no related guidance in literature.Therefore,empirical comparisons of several typical algorithms have been performed to provide some useful suggestions.In fact,semi-supervised classification algorithms can be categorized by the data distribution assumption.Therefore,typical algorithms with different assumption adoptions have been contrasted.Specifically,they are Transductive Support Vector Machine (TSVM) using the cluster assumption,Laplacian Regularized Least Squares Classification (LapRLSC) using the manifold assumption,and SemiBoost using both assumptions,and Implicitly Constrained Least Squares (ICLS) without any assumption,with the supervised least Squares Classification (LS) as the base line.Eventually it is concluded that when data distribution is given,the semi-supervised classification algorithm that adopts corresponding assumption can lead to the best performance;without any prior knowledge about data distribution,TSVM can be a good choice when the given labeled samples are extremely limited;when the labeled samples are not so scarce,and meanwhile if learning safety is emphasized,ICLS is proposed,and LapRLSC is another good choice.

semi-supervised classification;data distribution;cluster assumption;manifold assumption

TP301.6

A

1673-629X(2017)10-0043-06

2016-10-13

2017-01-19 < class="emphasis_bold">網絡出版時間

時間：2017-07-11

國家自然科學基金資助項目(61300165)；高等學校博士學科點專項科研基金新教師類(20133223120009)；南京郵電大學引進人才基金(NY213033)

孟 巖(1992-)，男，碩士研究生，研究方向為模式識別與機器學習；汪云云，博士，副教授，研究方向為模式識別、機器學習、神經計算等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1455.054.html

10.3969/j.issn.1673-629X.2017.10.010