田 勛，汪西莉

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

1 引言

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

半監(jiān)督分類是指利用大量無標記樣本信息來幫助訓練，調(diào)整使用少量類別標簽信息訓練得到的分類器，使分類的準確度提高。一般假設(shè)樣本xi∈Rm(i=1，2，3，…，n) ，其中m是樣本的維數(shù)，n是樣本的個數(shù)，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)，在傳統(tǒng)的支持向量機 SVM(Support Vector Machine)基礎(chǔ)上，對無標記樣本引入松弛項，表示對于無標記樣本錯分的懲罰。同年，Vapnik和Sterin提出了直推式支持向量機TSVM(Transductive SVM)，TSVM利用線性預測函數(shù)f(x)=wTx+b作為整個樣本空間上的分類邊界，其目標函數(shù)為:

其中，w∈Rm，‖w‖是支持向量到分類超平面的距離，V(yi，f(xi))是損失函數(shù)，l和u分別為有類別標簽信息樣本和無標記樣本的數(shù)量，C1與C2是有類別標簽信息樣本和無標記樣本損失權(quán)值，用于調(diào)整有類別標簽信息樣本和無標記樣本在目標函數(shù)中的重要性。隨后科研人員不斷提出新的半監(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)。對比傳統(tǒng)的半監(jiān)督支持向量機，meanS3VM算法并不直接使用每一個無標記樣本的估計標簽來訓練分類器，而是使用無標記樣本估計標簽均值來訓練分類器。對比半監(jiān)督SVM方法，meanS3VM算法僅僅使用樣本估計標簽均值訓練分類器，減少了訓練分類器的約束條件，減少算法運行時間。

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

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

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

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

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

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

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

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

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

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

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

本文的算法流程如下:

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

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

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

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

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

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

通過算法流程可以得出本文算法的時間復雜度和空間復雜度，由于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是無標記樣本的個數(shù)。

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

4 實驗結(jié)果及分析

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

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

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

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

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

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

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

4．1 Hourse數(shù)據(jù)集實驗結(jié)果

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

Table 2 Algorithm parameters表2 算法參數(shù)

監(jiān)督SVM算法、meanS3VM算法與本文算法的分類結(jié)果如圖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算法只使用標記樣本來訓練分類器，隨機選取無標記樣本不會影響算法的分類結(jié)果。所以，僅僅對比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數(shù)據(jù)集上各方法分類正確率和時間效率

4．2 Flower數(shù)據(jù)集分類結(jié)果

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

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

5 結(jié)束語

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

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