基于L21范數(shù)和回歸正則項(xiàng)的半監(jiān)督聚類算法

朱恒東，馬盈倉，張 要，張 寧

(西安工程大學(xué) 理學(xué)院 陜西 西安 710048)

0 引言

傳統(tǒng)的機(jī)器學(xué)習(xí)方法一般分為監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)[1]。傳統(tǒng)的監(jiān)督學(xué)習(xí)，通常需要大量良好標(biāo)記樣本對(duì)模型進(jìn)行訓(xùn)練，而傳統(tǒng)的無監(jiān)督學(xué)習(xí)的整個(gè)過程不借助監(jiān)督信息[2]。然而在現(xiàn)實(shí)應(yīng)用中，通常只有小部分?jǐn)?shù)據(jù)帶有監(jiān)督信息，這些數(shù)據(jù)難以支撐傳統(tǒng)監(jiān)督學(xué)習(xí)，若繼續(xù)使用傳統(tǒng)無監(jiān)督學(xué)習(xí)，會(huì)浪費(fèi)這些監(jiān)督信息[3]。

為了更好地處理監(jiān)督信息與數(shù)據(jù)之間的關(guān)系，有學(xué)者提出了半監(jiān)督學(xué)習(xí)[4-5]。按照學(xué)習(xí)場景的不同，半監(jiān)督學(xué)習(xí)通?？梢苑譃榘氡O(jiān)督聚類和半監(jiān)督分類[6]。本文主要研究的半監(jiān)督聚類是通過對(duì)有標(biāo)簽數(shù)據(jù)樣本(監(jiān)督信息)的分析來輔助指導(dǎo)整個(gè)聚類過程。根據(jù)監(jiān)督信息形式的不同，半監(jiān)督聚類分為基于成對(duì)約束和基于標(biāo)簽信息的半監(jiān)督聚類。

成對(duì)約束信息一般判斷兩個(gè)數(shù)據(jù)點(diǎn)是否同屬一類[7]。文獻(xiàn)[8]提出了一種基于成對(duì)約束對(duì)的半監(jiān)督核K-means聚類的圖像分割算法，該算法利用隨機(jī)產(chǎn)生的must-link約束對(duì)來初始化中心，結(jié)合核K-means聚類的思想，使該算法能對(duì)圖像進(jìn)行較為準(zhǔn)確的分割。文獻(xiàn)[9]提出了基于成對(duì)約束的交叉熵半監(jiān)督模糊聚類算法，這種方法利用樣本的交叉熵來表達(dá)成對(duì)約束信息，能夠在成對(duì)約束信息較少的情況下實(shí)現(xiàn)快速聚類和獲得較優(yōu)的結(jié)果。文獻(xiàn)[10]提出一種基于密度自適應(yīng)鄰域相似圖的半監(jiān)督譜聚類算法，利用成對(duì)約束信息調(diào)整譜聚類中相似矩陣，可以從數(shù)據(jù)全局尋求最優(yōu)解。

然而相較于成對(duì)約束信息，標(biāo)簽信息可以直接判斷數(shù)據(jù)點(diǎn)的類別[11]。文獻(xiàn)[11]提出了seeded-K-means算法，將標(biāo)記樣本引入K-means中，其中標(biāo)記樣本作為seeds集，但是難以處理高維數(shù)據(jù)。文獻(xiàn)[12]認(rèn)為基于線性嵌入的回歸模型難以捕獲數(shù)據(jù)流形結(jié)構(gòu)，提出利用Lδ正則項(xiàng)放寬線性約束，使之可以更好學(xué)習(xí)數(shù)據(jù)的流形結(jié)構(gòu)，但是增加了Lδ的調(diào)參負(fù)擔(dān)。文獻(xiàn)[13]在文獻(xiàn)[12]的基礎(chǔ)上通過增加對(duì)標(biāo)簽矩陣的拉普拉斯正則項(xiàng)放寬線性約束，去除Lδ的調(diào)參負(fù)擔(dān)，但是過多的正則項(xiàng)使得模型的計(jì)算量也隨之增加。文獻(xiàn)[14]提出了一種半監(jiān)督迭代多任務(wù)回歸。通過聯(lián)合考慮已標(biāo)記和未標(biāo)記的數(shù)據(jù)來學(xué)習(xí)低維子空間，并通過兩個(gè)回歸任務(wù)來連接已學(xué)習(xí)的子空間，但是算法時(shí)間復(fù)雜度較高。

半監(jiān)督聚類算法研究至今，在機(jī)器學(xué)習(xí)[15-16]、圖像處理[17-18]、計(jì)算機(jī)視覺[19]以及系統(tǒng)辨識(shí)[20]等領(lǐng)域都有著廣泛的應(yīng)用。針對(duì)半監(jiān)督學(xué)習(xí)中基于線性嵌入的回歸模型難以捕獲數(shù)據(jù)流形結(jié)構(gòu)的問題，本文提出新的算法:首先通過L21正則項(xiàng)構(gòu)造標(biāo)簽矩陣F的彈性嵌入回歸模型；進(jìn)而借助圖正則化思想，利用拉普拉斯正則項(xiàng)調(diào)整模型，約束原始空間的數(shù)據(jù)X與低維空間的數(shù)據(jù)F流形結(jié)構(gòu)一致；最后通過L21范數(shù)的魯棒性學(xué)習(xí)得到數(shù)據(jù)點(diǎn)的相似矩陣，與L2范數(shù)和Lδ范數(shù)相比，L21范數(shù)能很好地消除離群點(diǎn)的影響且沒有調(diào)參的負(fù)擔(dān)。因此提出基于L21范數(shù)和回歸正則項(xiàng)的半監(jiān)督聚類算法(semi-supervised clustering algorithm based onL21norm and regression regular term,SSLC)。

1 相關(guān)工作

1.1 半監(jiān)督學(xué)習(xí)

給定數(shù)據(jù)集X={x1,x2,…,xn}∈Rd×n，在半監(jiān)督學(xué)習(xí)中，訓(xùn)練數(shù)據(jù)集中只有少量數(shù)據(jù)被標(biāo)記，假設(shè)有l(wèi)個(gè)數(shù)據(jù)點(diǎn)為標(biāo)記點(diǎn)，記為Xl={x1,x2,…,xl}，未標(biāo)記點(diǎn)記為Xu={xl+1,xl+2,…,xn}，對(duì)于每個(gè)數(shù)據(jù)i，都有對(duì)應(yīng)的標(biāo)簽yi∈{0,1}，其中數(shù)據(jù)集Xl對(duì)應(yīng)的標(biāo)簽向量為yl∈Rl×1，定義f=[f(l),f(l)]T為預(yù)測標(biāo)簽，其中f(l)∈Rl×1和f(u)∈Ru×1，因此我們得到經(jīng)典半監(jiān)督學(xué)習(xí)函數(shù)

(1)

其中：W是投影向量；b為偏置向量；1為所有元素為1的向量；α和β為常數(shù)。從式(1)可以看出，約束預(yù)測的標(biāo)簽f與線性模型XTW+1b完全相等，在實(shí)踐中，為了減少參數(shù)調(diào)整的負(fù)擔(dān)，使用了式(2)來避免過擬合，

(2)

1.2L21范數(shù)的引入

使用L2范數(shù)的平方作為損失函數(shù)對(duì)較小的異常值不敏感，但對(duì)較大的異常值敏感；使用L1范數(shù)作為損失函數(shù)對(duì)較大的異常值不敏感，對(duì)較小的異常值敏感；而使用Lδ范數(shù)作為損失函數(shù)時(shí)，可以通過調(diào)整參數(shù)δ使其介于L2范數(shù)和L1范數(shù)之間，則無論異常值是大是小，L2和L1范數(shù)的魯棒性均被利用，但是增加了調(diào)整參數(shù)δ的負(fù)擔(dān)。為了解決上述問題，通過L21范數(shù)[21]，使得聚類模型更好地處理異常值和減少調(diào)參的負(fù)擔(dān)，起到彈性嵌入的作用，且沒有Lδ范數(shù)的調(diào)參負(fù)擔(dān)。L21范數(shù)為

其中:m是行數(shù);n是列數(shù)。

1.3 構(gòu)造初始相似矩陣

本文為了更好地學(xué)習(xí)相似矩陣，基于K共享近鄰和已知標(biāo)簽矩陣F(l)給出初始相似矩陣A的構(gòu)造方法如下。

定義1(K近鄰[22]) 樣本點(diǎn)xi∈X的K近鄰為該點(diǎn)到其他樣本點(diǎn)的距離中最近的K個(gè)點(diǎn)，定義為

KNN(i)={j∈X|index_dist(i,j)≤K}，

(3)

其中：index_dist(i,j)表示樣本點(diǎn)xi到其他樣本點(diǎn)的距離升序排序后的索引值；dist(i,j)表示兩點(diǎn)之間的歐氏距離。

定義2(K共享近鄰[23]) 假設(shè)樣本點(diǎn)xi、xj∈X，KNN(i)為樣本點(diǎn)xi的K近鄰集，KNN(j)為樣本點(diǎn)xj的K近鄰集，則樣本點(diǎn)xi和xj的K共享近鄰集定義為

SKNN(i,j)={KNN(i)∩KNN(j)}。

(4)

根據(jù)定義1和定義2，得到初始相似矩陣A的定義為

(5)

其中：Num是SKNN(i,j)中的元素個(gè)數(shù)；∑dist(xi,SKNN(i,j))是樣本點(diǎn)xi到SKNN(i,j)中元素的距離之和。

根據(jù)已知標(biāo)簽矩陣F(l)構(gòu)造約束矩陣為

(6)

其中：若標(biāo)簽Fi和Fj相等，說明xi和xj屬于同類，反之亦成立。根據(jù)cons矩陣和式(5)，得到最終的初始相似矩陣A為

(7)

2 模型的建立及求解

2.1 模型建立

由于線性函數(shù)XTW+1b是通過標(biāo)簽矩陣F學(xué)習(xí)得到的，考慮到標(biāo)簽矩陣F與學(xué)習(xí)到的線性模型XTW+1b存在距離，為了更好地學(xué)習(xí)數(shù)據(jù)的流形結(jié)構(gòu)，借助L21范數(shù)的彈性嵌入作用，建立彈性半監(jiān)督學(xué)習(xí)函數(shù)

(8)

考慮到算法最后要對(duì)F進(jìn)行聚類，為了約束原始空間的數(shù)據(jù)X與映射到低維空間的數(shù)據(jù)F幾何結(jié)構(gòu)不變，基于圖正則化思想，選擇拉普拉斯正則項(xiàng)來調(diào)整式(8)，建立目標(biāo)函數(shù)

(9)

其中：拉普拉斯矩陣LS是由給定的相似矩陣A得到的，考慮到隨著預(yù)測的標(biāo)簽矩陣F(u)的更新，為了保持拉普拉斯正則項(xiàng)的約束不變，與標(biāo)簽矩陣F對(duì)應(yīng)的LS也應(yīng)該更新。而相似矩陣S可以通過學(xué)習(xí)初始相似矩陣A得到，由于學(xué)習(xí)的相似矩陣S與給定的初始相似矩陣A存在距離，通過L21范數(shù)的魯棒性學(xué)習(xí)一個(gè)最優(yōu)的相似矩陣并完成對(duì)LS的更新，調(diào)整式(9)為最終目標(biāo)函數(shù)

(10)

2.2 模型求解

關(guān)于2.1節(jié)中目標(biāo)函數(shù)式(10)，采用交替迭代優(yōu)化算法來求解。

① 固定F、W和b，求解S，式(10)就轉(zhuǎn)為

(11)

關(guān)于式(11)，根據(jù)文獻(xiàn)[24]，已知存在fi∈Rc×1，使得式(12)成立，

(12)

(13)

② 根據(jù)文獻(xiàn)[13]，分別得到b、W、F的更新式為

b=FTU1/1TU1-WTXU1/1TU1，

(14)

W=(XNXT)-1XNF，

(15)

(16)

2.3 算法流程

根據(jù)2.2模型求解，SSLC算法流程如下。

輸入：X為數(shù)據(jù)集，F(xiàn)(l)為已知標(biāo)簽矩陣，λ和γ為參數(shù)，A為初始相似矩陣。

輸出：相似矩陣S，降維后新數(shù)據(jù)矩陣F，聚類結(jié)果y。

1) while 不收斂 do

2) 初始化LS，N；

3) 根據(jù)式(16)更新F；

4) 利用更新后的F，根據(jù)式(13)求解出S，更新LS；

5) 利用更新后的F，根據(jù)式(14)更新W；

6) 利用更新后的F和W，根據(jù)式(15)更新b；

7) 利用更新后的F，W，b，更新U；

8) end while

9) 對(duì)F進(jìn)行K-means，完成聚類。

2.4 收斂性證明

定理1算法中的目標(biāo)函數(shù)

minγ‖XTW+1bT-F‖2,1+2λTr(FTLSF)+‖S-A‖2,1，

在固定F、W和b時(shí)，交替迭代更新S過程中，目標(biāo)函數(shù)值逐步減小。

(17)

(18)

文獻(xiàn)[21]已證明式(19)成立，任意非零向量x,y∈Rc，有

(19)

根據(jù)式(19)知

(20)

將式(18)和式(20)相加可得

(21)

將式(21)中的每個(gè)i相加可得

(22)

由1.2節(jié)的定義可得

γ‖XTW+1bT-F‖2,1+2λTr(FTLSnewF)+‖Snew-A‖2,1≤γ‖XTW+1bT-F‖2,1+

2λTr(FTLSoldF)+‖Sold-A‖2,1。

(23)

因此，該算法收斂。

3 實(shí)驗(yàn)分析

3.1 相關(guān)算法及參數(shù)設(shè)置

接下來本文提出的SSLC算法將分別與DAN-SSC算法[7]、SSDC算法[26]、SS-Kernel-Kmeans算法[27]進(jìn)行比較，以上三個(gè)對(duì)比算法為半監(jiān)督聚類算法。使用聚類準(zhǔn)確率(accuracy，acc)和蘭德指數(shù)(rand index，RI)對(duì)聚類性能進(jìn)行評(píng)價(jià)。測試數(shù)據(jù)集分別為人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。其中人造數(shù)據(jù)集選用了具有代表性的Cdata9和Cdata04數(shù)據(jù)集說明SSLC算法的有效性，真實(shí)數(shù)據(jù)集采用ecoli-uni、vowel、dnatest和isolet_uni數(shù)據(jù)集進(jìn)行對(duì)比。

其中DAN-SSC算法的參數(shù)k為目標(biāo)聚類數(shù)。SSDC算法根據(jù)文獻(xiàn)[21]建議，取percent=50，D=1。SS-Kernel-Kmeans算法根據(jù)文獻(xiàn)[22]建議，參數(shù)k為目標(biāo)聚類數(shù)，最大迭代次數(shù)取120。SSLC算法，參數(shù)c為目標(biāo)聚類數(shù)，k=10，參數(shù)λ=0.1，γ=1。

表1 兩種人造數(shù)據(jù)集Table 1 Two kinds of artificial data sets

3.2 人造數(shù)據(jù)集測試及分析

本節(jié)選用Cdata04數(shù)據(jù)集和Cdata9數(shù)據(jù)集來說明SSLC算法的有效性。這兩種不同的人造數(shù)據(jù)集詳細(xì)信息如表1所示。圖1和圖2是測試的結(jié)果圖。測試中已知標(biāo)簽信息的數(shù)據(jù)量取值為40%。

圖1 Cdata04數(shù)據(jù)集測試結(jié)果Figure 1 Experimental results of Cdata04 dataset

圖2 Cdata9數(shù)據(jù)集測試結(jié)果Figure 2 Experimental results of Cdata9 dataset

圖1(a)代表原始的Cdata04數(shù)據(jù)集，是由4個(gè)環(huán)型簇組成，形狀如四葉草，葉子交匯的地方，表示數(shù)據(jù)之間聯(lián)系緊密，因此給聚類分析帶來了一定的難度。圖1(b)是以最終求解出的相似矩陣S為權(quán)重，將數(shù)據(jù)重新連接，雖然相似矩陣類內(nèi)的相似度保留略多，但是類間的相似度為0。圖1(c)是相似矩陣S的直觀表示，從圖中可以發(fā)現(xiàn)，相似度矩陣具有精確塊對(duì)角矩陣的結(jié)構(gòu)。圖1(d)是聚類結(jié)果圖，數(shù)據(jù)集劃分很好。

圖2(a)代表原始的Cdata9數(shù)據(jù)集，是由7個(gè)環(huán)型簇組成，簇與簇交匯的地方表示數(shù)據(jù)之間聯(lián)系緊密，因此給聚類分析帶來了一定的難度。圖2(b)是以最終求解出的相似矩陣S為權(quán)重，將數(shù)據(jù)重新連接，雖然相似矩陣類內(nèi)的相似度保留略多，但是類間的相似度為0。圖2(c)是相似矩陣S的直觀表示，相似度矩陣具有精確塊對(duì)角矩陣的結(jié)構(gòu)。圖2(d)是聚類結(jié)果圖，數(shù)據(jù)集被很好地劃分。

3.3 評(píng)價(jià)指標(biāo)

在真實(shí)數(shù)據(jù)集測試中，本文將分別采用acc指標(biāo)和RI指標(biāo)來評(píng)價(jià)SSLC算法、DAN-SSC算法、SSDC算法、SS-Kernel-Kmeans算法的效果。

RI:是一種用排列組合原理來對(duì)聚類進(jìn)行評(píng)價(jià)的方法。計(jì)算公式為RI=2(a+d)/n(n+1)，其中：n為樣本個(gè)數(shù)；a表示在真實(shí)類別si的數(shù)據(jù)也隸屬于聚類算法結(jié)果ri的個(gè)數(shù)；d表示不在真實(shí)類別si的數(shù)據(jù)也隸屬于聚類算法結(jié)果ri的個(gè)數(shù)。RI的結(jié)果值在[0,1]之間，值越大越好。

表2 4個(gè)UCI數(shù)據(jù)集Table 2 Four UCI datasets

3.4 真實(shí)數(shù)據(jù)集測試及分析

為了驗(yàn)證算法在真實(shí)數(shù)據(jù)集上的效果，判斷算法是否具有實(shí)際意義，本節(jié)分別采用了UCI數(shù)據(jù)庫中的ecoli-uni、vowel、dnatest和isolet_uni共4個(gè)數(shù)據(jù)集進(jìn)行測試，它們的詳細(xì)信息如表2所示。其中4個(gè)算法所使用的已知標(biāo)簽信息的數(shù)據(jù)量取值范圍分別為10%、20%、30%、40%、50%、60%。

圖3是基于acc指標(biāo)對(duì)聚類算法性能關(guān)于UCI真實(shí)數(shù)據(jù)集的評(píng)價(jià)結(jié)果，從圖3的(a)、(b)和(c)可以看出，本文提出的SSLC算法是明顯好于其他3個(gè)聚類算法，圖3(d)中SSLC算法初始精度雖然低于SS-Kernel-Kmeans算法，但是隨著已知標(biāo)簽數(shù)據(jù)量的增多，SSLC算法和DAN-SSC算法精度在不斷提升，最終在60%處，SSLC算法精度高于SS-Kernel-Kmeans算法。

圖3 acc指標(biāo)對(duì)聚類算法性能的評(píng)價(jià)結(jié)果Figure 3 Evaluation results of acc on the performance of clustering algorithm

圖4是基于RI指標(biāo)對(duì)聚類算法性能關(guān)于UCI真實(shí)數(shù)據(jù)集的評(píng)價(jià)結(jié)果，大體上與圖3結(jié)果相近，但也略有不同。在dnatest數(shù)據(jù)集中，SSDC算法相對(duì)于DAN-SSC算法和SS-Kernel-Kmeans算法的RI指標(biāo)結(jié)果好于acc指標(biāo)結(jié)果；在isolet_uni數(shù)據(jù)集上，SSLC算法的RI指標(biāo)性能提升的速度高于acc指標(biāo)。

圖4 RI指標(biāo)對(duì)聚類算法性能的評(píng)價(jià)結(jié)果Figure 4 Evaluation result of RI index on the performance of clustering algorithm

綜上所述，本文提出的SSLC算法隨著已知標(biāo)簽數(shù)據(jù)量的增多，性能也會(huì)提高，最后得到很好的聚類結(jié)果。實(shí)驗(yàn)結(jié)果說明本文提出的半監(jiān)督聚類算法合理，L21范數(shù)彈性約束可以使得SSLC更好地學(xué)習(xí)數(shù)據(jù)的流形結(jié)構(gòu)，從而構(gòu)造合理的相似矩陣，最終得到更好的聚類結(jié)果。

4 結(jié)論和展望

本文概述了半監(jiān)督學(xué)習(xí)和半監(jiān)督聚類的相關(guān)研究，一方面借助L21正則項(xiàng)構(gòu)造半監(jiān)督回歸模型；另一方面利用L21范數(shù)的魯棒性學(xué)習(xí)合理的相似矩陣，從而改善聚類效果。本文分別在人工數(shù)據(jù)集上進(jìn)行試驗(yàn)和真實(shí)數(shù)據(jù)集上進(jìn)行算法對(duì)比試驗(yàn)，結(jié)果進(jìn)一步驗(yàn)證了本文提出的SSLC算法的有效性。SSLC算法的后續(xù)研究可考慮在降低已知標(biāo)簽數(shù)據(jù)量的同時(shí)，如何保證其良好的性能及如何與其他聚類算法相結(jié)合。