基于聚類標簽均值的半監(jiān)督支持向量機*

田 勛，汪西莉

(陜西師范大學計算機科學學院，陜西西安710062)

1 引言

圖像分類在社會生產與日常生活中變得日益重要，無論是國防安全、醫(yī)療檢測、遙感分析還是交通監(jiān)控等領域，都離不開圖像分類。目前圖像分類已經成為機器學習與模式識別的研究熱點之一。傳統的機器學習分為監(jiān)督學習與無監(jiān)督學習，而半監(jiān)督學習 SSL(Semi-Supervised Learning)［1］是監(jiān)督學習與無監(jiān)督學習相結合的一種學習方法，它兼顧了監(jiān)督學習與無監(jiān)督學習的優(yōu)點，往往在少量標記樣本與大量無標記樣本的情況下進行訓練和分類，并且得到比較好的分類結果。對于圖像分類，大量標記樣本會耗費大量人力與時間，是不實際的，但圖像的無標記樣本卻相對容易獲取，所以半監(jiān)督學習廣泛運用于圖像分類當中。

半監(jiān)督分類是指利用大量無標記樣本信息來幫助訓練，調整使用少量類別標簽信息訓練得到的分類器，使分類的準確度提高。一般假設樣本xi∈Rm(i=1，2，3，…，n) ，其中m是樣本的維數，n是樣本的個數，yi為其類別標記，L={(x1，y1)，(x2，y2)，…，(xl，yl)} 表示 l個有類別標簽信息的樣本，U={xl+1，xl+2，…，xl+u} 表示 u 個無標記樣本。通過大量無標記樣本提供的分布信息有效彌補了少量有類別標簽信息的不足，使分類器的訓練更加充分。半監(jiān)督分類有四個不同的分支:基于生成式模型算法、基于差異的半監(jiān)督分類算法、基于判別式的半監(jiān)督分類算法、基于圖的半監(jiān)督分類算法。本文主要研究基于判別式的半監(jiān)督分類算法。

基于判別式的半監(jiān)督學習算法也被稱作基于低密度劃分的半監(jiān)督學習算法，同時使用類別標簽信息與無標記樣本信息訓練分類器，使分類面在僅通過低密度樣本區(qū)域的情況下，樣本到分類面的距離間隔最大，如圖1所示。典型的基于判別式的半監(jiān)督學習算法就是半監(jiān)督支持向量機S3VM(Semi-Supervised Support Vector Machine)［2］。

1998年，Bennett等人提出了最初的半監(jiān)督支持向量機(S3VM)，在傳統的支持向量機 SVM(Support Vector Machine)基礎上，對無標記樣本引入松弛項，表示對于無標記樣本錯分的懲罰。同年，Vapnik和Sterin提出了直推式支持向量機TSVM(Transductive SVM)，TSVM利用線性預測函數f(x)=wTx+b作為整個樣本空間上的分類邊界，其目標函數為:

其中，w∈Rm，‖w‖是支持向量到分類超平面的距離，V(yi，f(xi))是損失函數，l和u分別為有類別標簽信息樣本和無標記樣本的數量，C1與C2是有類別標簽信息樣本和無標記樣本損失權值，用于調整有類別標簽信息樣本和無標記樣本在目標函數中的重要性。隨后科研人員不斷提出新的半監(jiān)督支持向量機:拉普拉斯支持向量機(LapSVM)［3-5］、基于高斯混合模型核的半監(jiān)督支持向量機、基于譜聚類核的半監(jiān)督支持向量機、基于隨機游走核的半監(jiān)督支持向量機。

式(1)是非凸的，很難直接求解全局最優(yōu)解，一般情況下使用半定規(guī)劃SDP(Semi-Definite Programming)、梯度下降(Gradient Descent)、連續(xù)優(yōu)化CT(Continuation Techniques)、分支界定BB(Branch and Bround)、確定性模擬退火算法DA(Deterministic Annealing)等方法來求解。

為了提升半監(jiān)督支持向量機算法效率，Li等人［6］提出標簽均值半監(jiān)督支持向量機meanS3VM(mean Semi-Supervised Support Vector Machine)。對比傳統的半監(jiān)督支持向量機，meanS3VM算法并不直接使用每一個無標記樣本的估計標簽來訓練分類器，而是使用無標記樣本估計標簽均值來訓練分類器。對比半監(jiān)督SVM方法，meanS3VM算法僅僅使用樣本估計標簽均值訓練分類器，減少了訓練分類器的約束條件，減少算法運行時間。

meanS3VM算法最初用于數據集分類，針對圖像的光譜特征［7］，將無標記樣本預分為兩類，使用無標記樣本的標簽均值來訓練分類器，對復雜圖像，類內光譜信息差異較大，兩類的標簽均值難以反映各類光譜信息的實際情況，而且對分類器的訓練除了標記樣本提供的信息外，只增加了無標記樣本的標簽均值信息，對訓練分類器提供的信息較少。并且meanS3VM算法是隨機選取無標記樣本的，所以無標記樣本的標簽均值會有很大的隨機性，影響算法的穩(wěn)定性。因此，本文提出聚類標簽均值，針對圖像分類既提高分類精度，又提高分類器的穩(wěn)定性。

本文提出基于聚類標簽均值的半監(jiān)督支持向量機算法，與傳統的半監(jiān)督支持向量機相比有很大優(yōu)勢，比如S3VM算法對應的是混合整數規(guī)劃問題，通常難以計算。TSVM雖然將規(guī)劃問題轉化成迭代求解，但是需要的迭代次數很多，算法運行時間較長。而LapSVM則需要計算一個n×n(n是標記樣本與無標記樣本數量之和)矩陣的逆，當n的值過大時，會造成內存溢出。本文算法有利于表達圖像多樣的光譜特征，針對圖像，利用光譜特征分類，將無標記樣本聚類成多類，利用多類的標簽均值和有標記樣本訓練分類器，一方面提供更多類別信息，一方面和meanS3VM一樣加快訓練速度，減小了求解難度。與meanS3VM相比，將標簽均值間隔最大化約束條件改為聚類后多類的標簽均值間隔最大化約束條件，是本文的創(chuàng)新點，在實驗中驗證了這種改進明顯提高了分類的正確率，而且聚類后多類的標簽均值比meanS3VM兩類標簽均值隨機性小，提高了算法的穩(wěn)定性。

2 標簽均值半監(jiān)督支持向量機

半監(jiān)督支持向量機結合了監(jiān)督學習和無監(jiān)督學習的優(yōu)點，使用有少量標記樣本和大量無標記樣本設計分類器。在半監(jiān)督支持向量機的訓練過程中，給定的訓練樣本為一組有標簽訓練樣本集:L={(x1，y1)，…，(xl，yl)}，xi∈ Rd，yi∈ {+1，－1}，和另一組無標記樣本集:U={xl+1，xl+2，…，xl+u}，其中l(wèi)和u分別為標記和未標記樣本數。半監(jiān)督支持向量機可以定義為形如式(2)的優(yōu)化問題:

其中，H 是再生核希爾伯特空間［8］; ξ={ξ1，ξ2，…，ξl+u}，{ξ1，ξ2，…，ξl} 是標記樣本的松弛變量，{ξl+1，ξl+2，…，ξl+u} 是無標記樣本的松弛變量;參數C1需要人為設置，如果選擇較小的值，表示對標記樣本錯分比較容忍而更強調對正確分類的樣本的樣本間隔，相反，C1取較大值，則更強調對錯分的懲罰;yi(w'φ(xi)+b) ≥1 － ξi，i=1，2，…，l是標記樣本的約束條件;l+1，l+2，…，l+μ是無標記樣本的約束條件;φ(xj)是將特征映射到高維空間的非線性映射函數;參數C2與參數C1類似，C2的取值較小表示對無標記樣本錯分比較容忍而更強調對正確分類的樣本的樣本間隔，相反則更強調對錯分的懲罰;最后一個約束條件是平衡約束條件，防止所有的無標記樣本分為一類;r表示無標記樣本中正類個數比負類個數多多少，根據具體情況設定r的值。

標簽均值半監(jiān)督支持向量機算法簡稱為meanS3VM算法，與傳統半監(jiān)督支持向量機(如式(2)所示)相比，它改變了無標記樣本懲罰項，以無標記樣本的估計標簽均值之間的間隔ρ最大化為目標，使用了標簽均值這一個簡單的統計量來訓練分類器，數學表達如式(3)所示:

3 基于聚類標簽均值的半監(jiān)督支持向量機

標簽均值支持向量機最初被設計用于普通數據集分類，若用于圖像分類，存在分類正確率較低的問題。圖像分類需要考慮圖像的光譜特征，但meanS3VM算法只將無標記樣本預分為兩類，計算兩類的預估標簽均值，以預估標簽均值間隔ρ最大化為目標訓練分類器。對于大量無標記樣本，meanS3VM算法只使用了均值信息。而且傳統無標記樣本的選取都是隨機的，無標記樣本標簽均值的隨機性比較大，顯然會影響算法的穩(wěn)定性。本文算法以如何增加有意義的標簽均值約束條件，并提高算法的穩(wěn)定性為出發(fā)點，提出一種改進的標簽均值支持向量機算法。該方法首先對所有無標記樣本進行聚類，假設聚類數為k，在每個類別中分別求取預估標簽均值，利用一個基于間隔的框架使每類的預估標簽均值之間的間隔最大化，使分類面到各個聚類中心的預估標簽均值間隔盡可能大，達到適應多類圖像分類任務，并提高分類精度和結果穩(wěn)定性的目的。這時問題定義為:

其中，V= ［V1，V2，…，Vk］是無標記樣本聚類的結果。uh+與uh－分別為聚類后第h類中正類個數和負類個數。對該問題本文采用交替迭代方法求解，首先原最優(yōu)化問題可以轉化成如下的對偶問題［9］:

針對式(5)，如果固定了d的取值，α的求解就是一個標準的二次規(guī)劃(Quadratic Programming)［10］問題。另一方面，如果固定 α的取值，使用KKT條件［11］可以求取w和b，并且式(5)被簡化成式(6):

所以，本文算法是通過交替迭代方法求解，首先對無標記樣本聚類;接著使用監(jiān)督SVM進行預分類得到無標記樣本的預分類標簽d;固定d的取值，通過聚類結果與預分類標簽d構建約束條件，求解式(5)得到乘子α的取值;接著固定α值求解式(6)得出參數w和b的取值，用w和b的值再估計新的無標記樣本的標簽d';如果d等于d'停止迭代，否則繼續(xù)固定標記樣本的標簽d'，通過聚類結果與預分類標簽d'構建約束條件，求解式(5)依次迭代。

本文的算法流程如下:

Step 1首先對u個無標記樣本進行K-means聚類，聚成k類。

Step 2使用SVM分類器對u個無標記樣本預分類，得到預估標簽d。

Step 3使用聚類信息與預估標簽信息，求出聚類簇的標簽均值，構建2k個約束條件。

Step 4使用二次規(guī)劃求解式(5)優(yōu)化問題，求得新的α值。通過KKT條件，求解w和b。

Step 5使用w和b估計u個無標記樣本新的標簽d'。如果d'=d，停止迭代，否則跳轉Step3。

Step 6使用最終訓練好的分類器對全圖分類，算法結束。

通過算法流程可以得出本文算法的時間復雜度和空間復雜度，由于K-means算法的時間復雜度為O(n)，空間復雜度為O(n)，二次規(guī)劃算法的時間復雜度為O(n2)，空間復雜度為O(n2)，又因為k＜＜n，本文提出的聚類標簽均值半監(jiān)督支持向量機的時間復雜度為:O(u)+O(n2) =O(n2)，空間復雜度為:O(u)+O(n2)=O(n2)，其中u是無標記樣本的個數。

meanS3VM算法的參數有:針對標記樣本的錯分懲罰參數C1和針對無標記樣本的錯分懲罰參數C2。C1的大小決定了標記樣本在訓練分類器過程的重要性，C2的大小決定了無標記樣本在訓練分類器過程的重要性。還有高斯核函數k(x，y)=exp(－gamma＊‖x－y‖2)的參數gamma。當gamma→0時，k(x，y)→1，只能得到一個近似于常函數的判決函數［12］，對目標與背景稍微復雜的圖像分類正確率較低。當gamma→∞ 時，k(x，y)→0，訓練好的分類器推廣能力較差，測試樣本錯分的情況比較普遍。參數ep是無標記樣本正類數目的估計值，其值對分類器的分類正確率影響較大。本文改進算法中，需要對無標記樣本聚類，聚類數k值減小，則每類樣本數增多，聚類標簽均值間隔約束條件減少。k值增大則相反，所以聚類數k的取值直接影響算法的性能。

4 實驗結果及分析

為了研究本文算法是否增加了有意義的標簽均值約束條件，并提高了算法的穩(wěn)定性，實驗對象選擇目標與背景復雜度不同的圖像，分別使用監(jiān)督SVM和半監(jiān)督meanS3VM以及本文算法進行分類，并對比分析分類結果。程序使用 Matlab R2011a編寫，運行在內存為 4 GB，CPU為 Intel(R)Core(TM)i5-2400頻率為3．10 GHz的機器上。實驗用圖都選自 Weizmann horse dataset［13］，并且可以利用 Weizmann horse dataset給出的理想分類結果進行對比評價。本文采用圖像分類中常用的像素分類正確率PCR(Pixel Classification Rate)來評價分類效果。

實驗中，監(jiān)督SVM方法隨機選擇20個標記樣本，其中正類與負類各10個來進行分類器的訓練，meanS3VM與本文算法在選好的20個標記樣本基礎上，再隨機選擇200個無標記樣本訓練分類器，最終用訓練好的分類器對全圖估計標簽，得到分類結果。

實驗中監(jiān)督SVM算法使用網上流行的工具包實現，版本號為 libsvm-mat-2．83-1［14］，核函數使用高斯核函數，其中gamma的取值采用網格搜索法在 gamma=［1．0E －04:0．2E －04:1．0E －03］中尋找最優(yōu)值，參數C采用經驗取值1。

實驗中meanS3VM算法的參數有C1與C2，C1的取值與監(jiān)督SVM算法的參數C的取值相同，C2采用經驗最優(yōu)值0．1。ep的選取:對無標記樣本標簽預估計，假設正類數目為u+，然后再用網格搜索在ep= {u+－10:1:u++10}中尋找最優(yōu)值。gamma的取值采用網格搜索法在gamma=［1.0E－ 04:0．2E － 04:1．0E － 03］中尋找最優(yōu)值。

本文的改進算法中，聚類數k采用對不同圖像多次實驗得到的一個經驗取值。在實驗中，每幅圖像選取20個標記樣本和200個無標記樣本，實驗中聚類數k的選取從2到8進行實驗。以實驗中的“Horse008”和“Horse109”為例，分類正確率如表1所示。

Table 1 Impact of clustering number on algorithm accuracy表1 聚類數k對算法的正確率影響

從表1可以看出在聚類數為4時分類準確率的值較高，所以實驗中聚類數k初始取值為4，然后采用網格搜索法在k={2:1:6}中選擇最優(yōu)值。ep的選取:對無標記樣本標簽預估計，假設正類數目為u+，然后再用網格搜索在ep={u+－10:1:u++10}中尋找最優(yōu)值。C1與 C2的取值與meanS3VM中的C1與C2取值相同。gamma的取值采用網格搜索法在gamma=［1．0E－04:0．2E－04:1．0E －03］中尋找最優(yōu)。

4．1 Hourse數據集實驗結果

實驗選取了有代表性的五幅圖作為結果展示，對于每幅圖像算法的參數尋優(yōu)后的結果如表2所示。

Table 2 Algorithm parameters表2 算法參數

監(jiān)督SVM算法、meanS3VM算法與本文算法的分類結果如圖2所示，各方法的運行時間與分類正確率如表3所示。各方法的正確率對比圖如圖3所示。從表3可看出，因為添加了無標記樣本信息，所以meanS3VM與本文算法的分類正確率都高于監(jiān)督SVM算法。Horse008的背景與目標都比較簡單，選取的20個標記樣本提供了大量的信息，而無標記樣本的標簽均值沒有提供額外的訓練信息，所以針對Horse008，meanS3VM算法分類正確率與監(jiān)督SVM算法分類正確率相當，本文算法的分類正確率高于前兩種算法。監(jiān)督SVM算法不使用無標記樣本，訓練分類器時間最短，本文算法需要對無標記樣本聚類再求聚類標簽均值，所以時間會略高于meanS3VM算法，但是相比于分類器正確率的提高，本文算法的時間開銷可以接受。從圖3可以看出，本文算法對不同類型的圖像分類正確率都優(yōu)于meanS3VM算法，因為對于圖像的光譜特征進行聚類后，通過聚類均值標簽間隔最大化約束，使得同一光譜特征的樣本點標簽一致，提高了算法的分類正確率。

因為監(jiān)督SVM算法只使用標記樣本來訓練分類器，隨機選取無標記樣本不會影響算法的分類結果。所以，僅僅對比meanS3VM算法與本文算法的穩(wěn)定性。先固定選取好的20個標記樣本，隨機選取200個無標記樣本進行實驗，對每幅圖像進行10次實驗，10次正確率的均值和方差如表4所示。meanS3VM算法與本文算法的穩(wěn)定性對比如圖4所示，從圖4可以看出，本文算法的穩(wěn)定性更優(yōu)。

Table 3 Classification accuracy and time efficiency of each method on horse dateset表3 Horse數據集上各方法分類正確率和時間效率

4．2 Flower數據集分類結果

在Flower數據集上的分類結果如圖5和表5所示，參數的尋優(yōu)過程與4．1節(jié)類似，因為篇幅的原因本文選取數據集中的三幅圖像進行展示。如圖5所示，其中第一列圖像是待分類圖像，第二列圖像是理想分類結果，第三列圖像是監(jiān)督SVM分類結果，第四列圖像是meanSVM分類結果，第五列是本文算法分類結果。因為聚類標簽均值約束利用了圖像的光譜特征訓練分類超平面，分類的結果更加符合光譜特性，即光譜特性相似的樣本標簽一致，這樣就會減少錯分，提升算法的正確率，表5是各算法分類的正確率與時間效率。

Table 4 Stability tests表4 穩(wěn)定性實驗

5 結束語

本文將meanS3VM算法的標簽均值修改為聚類標簽均值，并改變了原算法對無標記樣本的懲罰項的約束條件，在訓練分類器的過程中，首先對無標記樣本聚類，在聚好的每個類別中分別求取預估標簽均值，利用一個基于間隔的框架使每類的預估標簽均值之間的間隔最大化。實驗結果顯示，本文算法的分類正確率比meanS3VM算法的要高，而且在無標記樣本隨機選取的情況下，本文算法的穩(wěn)定性也遠遠高于meanS3VM。今后將研究針對不同的圖像，根據圖像的光譜特征自適應地得到聚類數k，以期可以適用于光譜特征更加復雜的遙感圖像分類中。

Table 5 Classification accuracy and time efficiency of each method on flower dataset表5 Flower數據集上各方法分類正確率和時間效率