調整聚類假設聯合成對約束半監(jiān)督分類方法

黃 華，鄭佳敏，錢鵬江

(江南大學 數字媒體學院，江蘇 無錫 214122)(*通信作者電子郵箱qianpjiang@126.com)

0 引言

近些年來，隨著互聯網的快速發(fā)展，在網頁推薦、商品個性化推薦、垃圾郵件識別等日常生活應用中存在著大量的無標記樣本，而少量標記樣本往往需要通過成本較高的手工標記等方式獲取。如何通過利用少量標記樣本和大量未標記樣本來訓練模型的半監(jiān)督方法，便成為眾多學者共同努力研究的問題[1-4]。

在半監(jiān)督應用的熱潮下，學者們提出了許多半監(jiān)督分類方法[5-8], 然而有研究表明，某些情況下半監(jiān)督方法可能產生比與之對立的監(jiān)督方法更差的效果[9-10], 這主要是由于以下兩類原因造成的：

1)使用了從不可靠的未標記樣本中挖掘出的數據分布信息，其錯誤地指導了分類邊界的形成；

2)采用的數據分布假設可能本身就不符合數據的真實分布情況。

本文希望提出一種半監(jiān)督分類方法解決上述問題，使其性能不會明顯差于僅利用少量有標記樣本的監(jiān)督分類方法。

Li等[11]和Wang等[12-13]為解決這方面所存在的問題作出了相應的貢獻?；谀承┪礃擞洏颖咎峁┑姆植夹畔⒖赡艽嬖阱e誤甚至誤導分類面生成的猜想，Li等[11]提出了us型半監(jiān)督支持向量機(Semi-Supervised Support Vector Machine us，S3VM-us)方法，通過層次聚類的方式從未標記樣本中選取置信度較高的樣本來挖掘數據分布信息，從而避免了不可靠的未標記樣本對模型的錯誤指導；此外，還猜想半監(jiān)督支持向量機(Semi-Supervised Support Vector Machine, S3VM)對一個數據集可能存在多個低密度劃分面，在領域知識不夠充分時，算法可能會選取一個錯誤的低密度劃分面，因此導致了性能的嚴重下降。針對此猜想，Li等提出了安全半監(jiān)督支持向量機(Safe Semi-Supervised Support Vector Machine, S4VM)方法[11]，該方法會構造多個候選低密度劃分面，然后在最壞情況下選取最優(yōu)的劃分面以最大化性能提升。Wang等[12]提出的基于類隸屬度的半監(jiān)督分類方法(Semi-Supervised Classification method based on Class Memberships, SSCCM)和調整聚類假設半監(jiān)督分類方法(Semi-Supervised Support Vector Machine by Adjusting Cluster Assumption, ACA-S3VM)[13]，可以有效緩解當不同類別的樣本嚴重重疊在真實分類邊界時，基于聚類假設的算法將會錯誤地引導模型生成的分類邊界通過低密度區(qū)域的不安全學習情形(此類情況下真實分類邊界不在低密度區(qū)域)。前者通過引入類似模糊隸屬度的方式，提升了算法對邊界交叉數據的劃分能力；后者通過將每個未標記樣本到類簇邊界的距離融入到模型的學習中，使得在類簇邊界的樣本也會被劃分到分類邊界，模型便會指導分類邊界通過類簇邊界(真實分類邊界)而不是低密度區(qū)域。

值得注意的是，Li等[11]和Wang等[12-13]提出的安全半監(jiān)督分類方法旨在對未標記樣本的深耕利用，而忽略了對標記樣本所蘊含的監(jiān)督信息的利用。鑒于此，本文以ACA-S3VM為基礎分類器，將成對約束信息與之結合，提出了調整聚類假設聯合成對約束半監(jiān)督分類方法(Adjusted Cluster Assumption and Pairwise Constraints Jointly based Semi-Supervised Classification Method, ACA-JPC-S3VM)，它不僅能夠有效利用標記樣本知識(監(jiān)督信息)，而且能夠合理運用未標記樣本所蘊含的內在信息，具有以下優(yōu)點：

1)充分利用了標記樣本所蘊含的監(jiān)督信息；

2)繼承了調整聚類假設所具備的優(yōu)勢，能夠對邊界重疊樣本有效劃分。

1 相關工作

1.1 調整聚類假設

(1)

觀察優(yōu)化問題能夠發(fā)現，當Vj接近于0時，未標記樣本xj就很可能位于類簇邊界附近，那么根據式(1), 它的預測值f(xj)就被限制到接近0，于是樣本xj將會被劃分到分類邊界附近的區(qū)域；相反的，當Vj較大時，未標記樣本xj就會離類簇邊界較遠，那么根據式(1),樣本xj將會被劃分到分類邊界較遠的區(qū)域。

ACA-S3VM方法對未標記樣本同時尋找決策函數和分類標記。在問題求解方面，可以通過交替迭代策略分別得到決策函數和預測類標，且迭代過程中的每一步都會產生一個閉合解。

1.2 成對約束

本文方法對標記樣本的利用是將數據標簽轉換而來的成對約束項融入算法的損失函數。成對約束[14-17]是一種常見的監(jiān)督類型信息，它通過將樣本的類標簽轉化為成對約束項來提升模型對標記樣本所蘊含信息的利用。一般而言，在訓練半監(jiān)督分類模型時，對于每個標記樣本，會給出相應的類標記; 而在一些現實應用中，可能只獲得了部分樣本類標簽的關系，這時就可以將這些類標簽關系轉化為成對約束信息，將其視為標記樣本信息進行半監(jiān)督模型的訓練。

具體而言，如果兩個標記樣本的類標記相同，則它們是一對必須關聯約束，這樣的約束對組成了必須關聯集MS；相應的，如果兩個標記樣本的類標記不同，則它們是一對不可能關聯約束，這樣的約束對組成了不可能關聯集CS。假設分類決策函數為f(x)，那么對所有樣本的預測值可以表示為f=[f1,f2,…,fn]T∈R1×n，于是成對約束可以表示為以下形式：

(2)

其中:i、j、p、q∈[1,n]是樣本集里的樣本序號；〈i,j〉表示MS集合中的任意一對必須關聯約束，同樣的，〈p,q〉表示CS集合中的任意一對不可能關聯約束；|·|表示MS集合或CS集合中成對約束的數目。

定義1 定義矩陣Qn×n元素如下：

(3)

于是可以得到式(2)的矩陣表示如下：

(4)

U=H-Q

(5)

H=diag(QL)

(6)

式(6)中L是n×1向量且元素全為1。

2 調整聚類假設聯合成對約束方法

文獻[13]方法主要研究以聚類假設為基礎的半監(jiān)督分類方法，如何避免當不同類別樣本重疊在類簇邊界時可能形成的不安全學習情形。雖然其通過引入調整聚類假設，有效緩解了這些樣本對模型的錯誤指導，但值得注意的是，該算法沒有對標記樣本所蘊含的監(jiān)督信息進行更深一步的挖掘。本文關注于對標記樣本的有效利用，將成對約束監(jiān)督信息與之結合，提出了ACA-JPC-S3VM。

2.1 模型描述

前文介紹了調整聚類假設框架以及成對約束項對監(jiān)督信息的挖掘利用?，F本文將兩者結合，提出了ACA-JPC-S3VM方法，該方法不僅能夠有效利用標記樣本所蘊含的監(jiān)督信息，而且能夠合理挖掘出未標記樣本的內在信息，提高算法的性能。

(7)

將式(7)與調整聚類假設框架相結合，即可得到ACA-JPC-S3VM的優(yōu)化問題：

(8)

其中：第一項主要控制著分類器的復雜性；第二項是對標記樣本的利用，由平方損失項和成對約束正則化項共同組成，而參數τ控制著它們之間的平衡，值得注意的是，當參數τ=1 時，算法即退化為ACA-S3VM；第三項是調整聚類假設對未標記樣本的探索，用來挖掘數據的內在信息；C1、C2作為正則化參數分別控制著對應正則化項的復雜性。

2.2 問題求解

(9)

基于表示定理[18]，對式(9)的最小化具有以下形式：

那么，可以得到式(9)的矩陣表示形式：

(10)

由拉格朗日乘子法，將J對α的偏導數取0，解得：

α=(K+C1(τKlTKl+ (1-τ)KUK)+

(11)

(12)

2.3 算法步驟

在本文算法的求解方面，初始化的Yu是由支持向量機(Support Vector Machine, SVM)得到的；迭代終止條件是|Mk-Mk-1|<ε或k>Maxiter，其中Mk表示第k次迭代的目標函數值，ε是一個預設的終止閾值，Maxiter是最大迭代次數。ACA-JPC-S3VM的算法步驟如下所示：

輸入：標記樣本與未標記樣本Xl、Xu，標記樣本的類標Yl，正則化參數C1、C2、τ，迭代終止閾值ε，最大迭代次數Maxiter。

1)通過FCM獲得初始聚類中心，然后計算向量V。

2)設置初始化的目標函數值M0=INF。

3)通過式(11)更新α，然后根據表示定理以α更新f(x)。

推論1 ACA-JPC-S3VM使用交替迭代策略得到的序列{J(αk,yk)}是收斂的。

證明 首先證明目標函數是單調遞減的。由文獻[19]可知，目標函數J(α,y)是關于(α,y)雙凸的，那么當yk被固定時，目標函數關于α就是凸的，因此可以通過最小化{J(α,yk)}得到最優(yōu)的α*，即最優(yōu)化式(9)。由交替迭代策略可得αk+1=α*，于是J(αk+1,yk)=J(α*,yk)≤J(αk,yk)；同理，此時固定αk+1，目標函數關于y就是凸的，因此可以通過最小化{J(αk+1,y)}得到最優(yōu)的y*，即最優(yōu)化式(12)。由交替迭代策略可得yk+1=y*，于是J(αk+1,yk+1)=J(αk+1,y*)≤J(αk+1,yk)，?k∈N。因此，序列{J(αk,yk)}是單調遞減的。又因為目標函數J(α,y)是非負且有下界的，所以序列{J(αk,yk)}是收斂的。

3 實驗與結果分析

為了驗證本文算法的有效性，本文將其與監(jiān)督分類方法SVM、半監(jiān)督分類方法TSVM、Laplacian SVM[7]、Laplacian RLSC(Laplacian Regularized Least Squares Classification)[7]、meanS3VM-iter[6]、meanS3VM-mkl[6]以及ACA-S3VM在UCI數據集以及圖像分類數據集[20-21]上進行性能比較。最后，還進行了時間復雜度分析以及參數魯棒性分析的實驗。

特別需要說明的是，對于每個原始數據集，本文都將其隨機劃分為訓練集和測試集。在訓練集上，會隨機選取部分數量的樣本作為標記樣本，其余的作為未標記樣本參與模型的訓練，這樣的預處理操作將會被重復10次，最終以模型在測試集上的平均準確率和方差作為實驗指標評估每個算法的性

能。此外，所有算法的高斯核參數均設置為樣本數據的平均距離。本文算法在優(yōu)化求解中，最大迭代次數M=200,收斂閾值ε=10-3。

3.1 UCI數據集實驗結果與分析

本文在UCI數據集上做了大量實驗，其數據集的詳細構成見表1。為了體現出標記樣本數量對半監(jiān)督分類算法性能的影響，本文特地在訓練集上分別隨機選取了10、20、30、40、50個標記樣本來訓練模型，最終得出不同標記樣本數量對算法性能影響的趨勢圖。此外，表2和表3分別給出了標記樣本為10和50時，8種算法的實驗結果。

表1 UCI數據集結構

表2 10個標記樣本點上8種算法分類結果 %

注：括號中的數字代表該算法在當前數據集上的性能排名；

本文算法右上角的W/T分別表示在ttest測試中與ACA-S3VM算法相比更好/持平。

觀察表2與表3，可以發(fā)現：

首先，當標記樣本數量為10時，ACA-S3VM在3個數據集上的效果都要比經典半監(jiān)督分類方法TSVM的效果差，而ACA-JPC-S3VM有2個; 當標記樣本數量為50時，ACA-S3VM仍舊有在3個數據集上的性能比SVM或TSVM更差，而ACA-JPC-S3VM在所有8個數據集上的性能都優(yōu)于監(jiān)督分類方法。更進一步還發(fā)現，無論標記樣本數量是10還是50，ACA-S3VM在breast和wdbc數據集上的表現都比TSVM差，而ACA-JPC-S3VM在標記樣本數量為50時，性能已經反超了TSVM。這體現了ACA-JPC-S3VM不僅繼承了ACA-S3VM在安全半監(jiān)督分類方面的優(yōu)勢，而且在融入了標記樣本的知識后，成為了一種更加安全的半監(jiān)督分類方法。

其次，當標記樣本數量為10時，ACA-JPC-S3VM算法在6個數據集上獲得了最優(yōu)性能，僅在其余兩個數據集上的性能稍弱于TSVM。而當標記樣本數量為50時，ACA-JPC-S3VM在所有8個數據集上的性能都取得了最優(yōu)，且在8個數據集上的平均準確率遠高于其余對比算法。這表明，ACA-JPC-S3VM在保持對邊界重疊樣本正確分類的同時，隨著標記樣本的增加，還能對監(jiān)督信息進行更深一步的挖掘利用，從而在兩方面對知識進行極大化利用，最終提升了算法的性能。

表3 50個標記樣本點上8種算法分類結果 %

最后，不難發(fā)現在所有8個數據集上，無論標記樣本的數量是10還是50，基于ACA-S3VM進行改進的ACA-JPC-S3VM的平均準確率都是優(yōu)于ACA-S3VM的，這意味著算法的改進是有效、可行的。但就平均準確率這個性能指標而言，有時ACA-JPC-S3VM相較于ACA-S3VM的提升甚微，這只表明了算法在整體上更加穩(wěn)定。為了更進一步體現算法在改進后的性能優(yōu)勢，本文對這兩個算法進行了ttest檢驗。在標記樣本數量為10時，ACA-JPC-S3VM在4個數據集上的性能是優(yōu)于ACA-S3VM的，在其余4個數據集上持平；在標記樣本數量為50時，ACA-JPC-S3VM在5個數據集上的性能是優(yōu)于ACA-S3VM的，在其余3個數據集上持平，且在兩種標記量的情況下，ACA-JPC-S3VM都沒有出現改進后性能下降的情況。

觀察圖1，可以得到如下結論：

就圖1(a)中的clean1數據集而言，可以看出當標記樣本數量大于10后，Laplacian SVM和meanS3VM-mkl這兩種半監(jiān)督分類方法的性能會弱于SVM以及TSVM，而其他幾種算法則不會。這可能是由于隨著標記樣本的增加，未標記樣本的數量在減少，能夠選取的可靠性高的未標記樣本的數量就減少了，亦或是算法選取了不可靠的未標記樣本參與了模型的訓練，形成了不安全的半監(jiān)督學習。ACA-JPC-S3VM在保持始終合理利用未標記樣本的同時，通過有效挖掘標記樣本信息，使其保持了較高的分類性能，這再次證明了ACA-JPC-S3VM是一種更加有效的安全半監(jiān)督分類方法。

就圖1(b)中的spectfheart數據集而言，Laplacian SVM的性能與其他幾種對比算法相差較大。這可能是由于Laplacian SVM方法假設數據分布在由拉普拉斯圖表示的低維流形上，根據圖的結構來生成模型，而這樣的流形假設可能本身就不符合這個數據集的真實數據分布，再次導致了其不安全的半監(jiān)督學習。

就圖1(c)中的vehicle數據集而言，所有半監(jiān)督分類方法的性能都優(yōu)于監(jiān)督分類方法SVM，而且它們的性能都很接近，ACA-JPC-S3VM的性能也沒有與其他算法拉開明顯的差距。這可能是因為在這個數據集上，未標記樣本已經能夠很好地反映出數據的真實分布情況，且這些方法都能合理地利用這些數據的內在信息，使得模型都能夠正確預測未見樣本。雖然不同于其他幾種半監(jiān)督分類方法，ACA-JPC-S3VM高效利用了標記樣本所蘊含的監(jiān)督信息，但由于半監(jiān)督分類方法的核心在于對未標記樣本的內在信息進行合理的利用，而在對監(jiān)督信息的利用效果方面相對而言沒有對無監(jiān)督信息的利用效果大，所以ACA-JPC-S3VM的效果只是稍好于其他幾種半監(jiān)督分類方法。

就圖1(d)中的wdbc數據集而言，在標記樣本數量為10時，包括ACA-JPC-S3VM在內的幾種半監(jiān)督分類方法的性能都比監(jiān)督分類方法差，而當標記樣本大于10時，除了ACA-JPC-S3VM以外，其余半監(jiān)督分類方法的性能仍舊沒有超過監(jiān)督分類方法。雖然，ACA-S3VM能夠通過調整聚類來緩解不安全的半監(jiān)督分類學習，使得它的性能好于除了ACA-JPC-S3VM以外的半監(jiān)督分類方法，但它依然沒能超過TSVM或SVM。而隨著標記樣本的增加，結合對標記樣本進行利用的ACA-JPC-S3VM在性能上超越了監(jiān)督分類方法，這不僅證明了對監(jiān)督信息的合理利用可以有效提升半監(jiān)督分類方法的性能，同時也驗證了ACA-JPC-S3VM的安全性與正確性。此外，圖(e)、圖(g)以及圖(h)中，ACA-JPC-S3VM都具有很好的性能；在圖(f)中，仍可以觀察到一些半監(jiān)督分類方法出現了不安全的學習，而ACA-JPC-S3VM的性能依然呈現出穩(wěn)步提升的趨勢。

圖1 不同數據集上8種算法分類性能比較

3.2 圖像分類實驗結果與分析

本文圖像分類數據集[20-21]包括沙漠、山、海洋、日落、樹木共5類2 000張自然景觀的圖像，其結構見表4。

表4 圖像分類數據集結構

觀察表5，可以得到如下結論：

ACA-JPC-S3VM在4個圖像分類數據集上取得了最優(yōu)性能，而Laplacian SVM和meanS3VM-iter分別在desert VS mountains和mountains VS trees數據集上取得了第一。另外，在desert VS trees、sea VS desert以及sea VS sunset數據集上，一些半監(jiān)督分類方法出現了不安全的學習情況，其中ACA-S3VM較為嚴重，在這三個數據集上的表現都不好，而基于它改進的ACA-JPC-S3VM則表現出了很強的競爭力，且在與ACA-S3VM的ttest測試中取得了優(yōu)秀的表現，這再次強有力地證明了ACA-JPC-S3VM改進的合理性與有效性。

值得注意的是，ACA-S3VM在圖像分類實驗中的整體表現不是很好，盡管ACA-S3VM在針對聚類假設中的不同類別樣本嚴重重疊在分類邊界時的情況進行了專門的優(yōu)化，但可能由于這些數據的分布本身不符合聚類假設，致使算法不能獲得較好的效果。而基于ACA-S3VM進行改進的ACA-JPC-S3VM卻獲得了較好的結果，歸根結底可以歸結為其對標記樣本所蘊含的監(jiān)督信息的有效挖掘與利用，不僅填補了ACA-S3VM在對標記樣本利用方面的空缺，而且彌補了這種情況下半監(jiān)督學習基本假設帶來的負面影響，最終合理有效地利用了標記樣本與未標記樣本的知識，形成了一種更加安全有效的半監(jiān)督分類方法。

表5 圖像分類數據集結果 %

3.3 時間復雜度結果與分析

為了討論實際應用中的情況，本文在圖像分類數據集上對比了ACA-JPC-S3VM與ACA-S3VM模型訓練平均用時, 其結果見圖2。

圖2 模型平均訓練用時的比較

從圖2中容易看出，本文算法經過對ACA-S3VM的改進后，其訓練時長在大部分情況下相對較長，其主要原因是由于成對約束正則化項的加入，使得優(yōu)化問題的求解中需要調整對應參數對模型的作用，一定程度上影響了算法的收斂速度。

3.4 參數魯棒性分析

為了體現成對約束正則化參數τ的作用，本文仍舊以圖像分類數據集為例，對參數τ進行了魯棒性分析實驗。參數C1、C2的值固定為每個數據集上的最優(yōu)模型所對應的值，實驗結果見圖3。

觀察圖3可以發(fā)現：

1)參數τ對算法準確率的影響很明顯, 這體現出其對算法模型的重要性。

2)在sea VS sunset數據集上，當τ=0.95時，算法的預測準確率達到了0.87，相較于其他值有了較大的提升。這表明，若對τ進行精心調校，可以得到令人滿意的效果。

3)成對約束信息的加入，可以提升算法的正確率，彌補了算法對監(jiān)督信息利用方面的缺失。

圖3 參數τ對準確率的影響

4 結語

本文針對不安全的半監(jiān)督分類問題，通過有效利用標記樣本所蘊含的監(jiān)督信息與合理運用未標記樣本的分布信息，提出了ACA-JPC-S3VM方法。該方法不僅繼承了ACA-S3VM緩解不同樣本嚴重重疊在分類邊界時可能造成的不安全學習情形的能力，而且在將成對約束信息融入模型之后，能夠一定程度上彌補不安全學習對分類器造成的性能損失。在UCI數據集上的實驗，表明了本文方法對標記樣本所蘊含的監(jiān)督信息的有效利用，算法性能隨著標記樣本的增加而逐步上升；在圖像分類數據集上的實驗，表明了本文方法在不安全的學習情形下，通過對監(jiān)督信息的運用，一定程度上彌補了算法性能的損失, 最終驗證了本文方法的安全性與有效性。

由于加入了成對約束正則化項，需要調整對應參數對模型的作用占比，使得模型的訓練時長相對于改進前的ACA-S3VM方法而言更高，如何通過一些啟發(fā)式的方法來解決此問題將會是以后研究工作的重點。