基于σ范數(shù)和秩約束的相似矩陣學(xué)習(xí)算法

楊 婷，楊小飛，馬盈倉，汪義瑞

(1.西安工程大學(xué) 理學(xué)院，陜西 西安 710048;2.安康學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 安康 725000)

0 引 言

聚類分析在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)領(lǐng)域都有至關(guān)重要的作用[1]。聚類是將數(shù)據(jù)集按照某個(gè)特定的標(biāo)準(zhǔn)劃分為多個(gè)簇，使得同一簇中的數(shù)據(jù)之間有較高的相似性，不同簇中的數(shù)據(jù)之間有較大的差異性[2]。聚類算法一般分為基于網(wǎng)格的聚類算法、基于密度的聚類算法、基于層次的聚類算法、基于圖論的聚類算法和基于劃分的聚類算法等[2]。

譜聚類是一種重要的基于圖論的聚類算法[3]。譜聚類算法能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解[4]。但是，該算法也存在一些問題，例如譜聚類的聚類結(jié)果一方面完全依賴于輸入的相似矩陣，另一方面由于數(shù)據(jù)的高維或稀疏等因素使得相似矩陣的構(gòu)造很困難，同時(shí)，譜聚類不能直接得到聚類結(jié)果，需借助K-means等算法進(jìn)行后處理。

近年來，許多學(xué)者對(duì)譜聚類算法做了進(jìn)一步的研究與改進(jìn)。為了得到較合理的相似矩陣，SHI等通過構(gòu)造高斯核函數(shù)求解相似矩陣[5];在文獻(xiàn)[5]的基礎(chǔ)上,XIE等利用樣本點(diǎn)的近鄰點(diǎn)和2個(gè)樣本點(diǎn)之間的歐氏距離作為局部標(biāo)準(zhǔn)差構(gòu)造相似矩陣[6]。NATALIANI等通過構(gòu)造冪高斯核函數(shù)求解相似矩陣[7];ZHANG等利用了2個(gè)數(shù)據(jù)點(diǎn)之間的局部密度得到相似度矩陣[8]。這些相似矩陣的構(gòu)造是固定的，因而不能很好地反應(yīng)數(shù)據(jù)的結(jié)構(gòu)。

從譜聚類中得到的結(jié)果需要進(jìn)行后處理才能得到最終的聚類。WU等利用K-means對(duì)該結(jié)果進(jìn)行后處理[9]，但K-means方法易受到初始化聚類中心的影響，造成聚類結(jié)果不穩(wěn)定。在文獻(xiàn)[9]的基礎(chǔ)上，XIE等提出了用方差優(yōu)化初始類中心的SD-K-medoids算法代替K-means算法，克服K-means算法的不穩(wěn)定性[10]。YU等利用分割的標(biāo)準(zhǔn)正交不變性對(duì)該結(jié)果進(jìn)行后處理[11]。在文獻(xiàn)[11]的基礎(chǔ)上，CHEN等提出一種改進(jìn)的譜旋轉(zhuǎn)方法，并得到較好的聚類結(jié)果[12]。與上述方法不同，NIE等利用圖論的知識(shí)，提出了拉普拉斯矩陣秩約束聚類算法(CLR)[13]。該算法通過對(duì)拉普拉斯矩陣施加秩約束，利用l2范數(shù)的平方與l1范數(shù)分別作為目標(biāo)函數(shù)，使得學(xué)習(xí)到的相似矩陣具有c個(gè)連通分支，從而直接得出聚類結(jié)果。由于l2范數(shù)的平方作為損失函數(shù)對(duì)較大的異常值比較敏感，而l1范數(shù)作為損失函數(shù)對(duì)較小的異常值比較敏感，所以得到的聚類結(jié)果不太理想。

為了求解更優(yōu)的相似矩陣同時(shí)也使聚類結(jié)果對(duì)離群點(diǎn)具有魯棒性，本文提出基于σ范數(shù)和秩約束的相似矩陣學(xué)習(xí)算法(RSC-lσ)。該算法利用具有魯棒性的σ正則項(xiàng)求解相似矩陣S，并對(duì)相似矩陣S的拉普拉斯矩陣施加秩約束，從而不需要進(jìn)行任何后處理便可直接得到聚類結(jié)果。該算法不僅可以更好地反應(yīng)數(shù)據(jù)的流行結(jié)構(gòu)，而且可以使聚類結(jié)果較為穩(wěn)定。

1 目標(biāo)函數(shù)

1.1 自適應(yīng)損失函數(shù)

使用l2范數(shù)的平方作為損失函數(shù)對(duì)較小的異常值不敏感，但對(duì)較大的異常值非常敏感；而使用l1范數(shù)作為損失函數(shù)對(duì)較大異常值不敏感，但對(duì)較小的異常值很敏感，對(duì)模型學(xué)習(xí)影響非常大。為了解決上述問題，引入自適應(yīng)損失函數(shù)[14]，即

(1)

式中：mi為矩陣M的第i行；σ為自適應(yīng)參數(shù)。

由文獻(xiàn)[14]可知，式(1)所定義的lσ范數(shù)介于l2范數(shù)和l1范數(shù)之間。這樣無論異常值是大是小，l2和l1等2個(gè)范數(shù)的魯棒性都被利用了。由式(1)所定義的損失函數(shù)具有如下性質(zhì):

ⅰ)‖M‖σ是二次可微的；

ⅲ)當(dāng)‖mi‖2?σ時(shí)，‖M‖σ→(1+σ)·‖M‖2,1;

ⅳ)當(dāng)σ→0時(shí)，‖M‖σ→‖M‖2,1;

ⅴ)當(dāng)σ→時(shí)，

1.2 譜聚類算法

譜聚類算法將數(shù)據(jù)集中的每個(gè)樣本點(diǎn)看作是圖的頂點(diǎn)V，將頂點(diǎn)間的相似度作為相應(yīng)頂點(diǎn)連接邊E的權(quán)值，這樣就得到一個(gè)基于相似度的無向加權(quán)圖G(V,E)，于是聚類問題就可以轉(zhuǎn)化為基于圖的劃分問題[15-16]?；趫D論的最優(yōu)劃分準(zhǔn)則就是使劃分成的子圖內(nèi)部相似度最大，子圖之間的相似度最小。具體算法如下[16]：

1)假設(shè)聚類的c個(gè)簇為A1,A2,…，Ac，滿足Ai∩Aj=?，A1∪A2∪…∪Ac=V。根據(jù)比例切割原則CR和切割原則C,斷開的都是一些權(quán)值小的邊，保證了相似度大的頂點(diǎn)被分到同一個(gè)簇內(nèi)。

2)根據(jù)上述原則，建立如下目標(biāo)函數(shù)：

(2)

式中：|Ai|為集合Ai中元素的個(gè)數(shù)。在式(2)中，分母的作用是尋求一種平衡，努力讓各個(gè)簇的大小相近，避免有的簇包含很多數(shù)據(jù)點(diǎn)，而有的簇僅包含一個(gè)或幾個(gè)數(shù)據(jù)點(diǎn)。

3)定義c個(gè)簇指示向量fj=(f1j,f2j,…，fnj)T，其中

(3)

式中:i=1,2,…,n;j=1,2,…，c;vi∈V。

4)將c個(gè)指示向量按列排成矩陣，則得到指示矩陣F∈Rn×c。根據(jù)前面給出的定義，可以推出F滿足

FTF=Ic

(4)

利用數(shù)據(jù)的拉普拉斯矩陣L和簇指示向量表示圖的切割問題(詳細(xì)證明見文獻(xiàn)[16])：

(5)

由式(4)和式(5)可得

(6)

傳統(tǒng)的譜聚類性能在很大程度上取決于相似矩陣的構(gòu)造。因此，建立一個(gè)合理的相似矩陣對(duì)于譜聚類算法而言至關(guān)重要。另外，譜聚類算法需要進(jìn)行后處理才可以得到最終的聚類結(jié)果。為了更好地解決這2個(gè)問題，本文提出一種新的基于σ范數(shù)和秩約束的相似矩陣學(xué)習(xí)算法。

1.3 目標(biāo)函數(shù)的確立

由于相似矩陣S是通過已給的親和矩陣A(具體構(gòu)造參見文獻(xiàn)[13])學(xué)習(xí)得到的，所以S最接近所給的親和矩陣A?？紤]到給定的親和矩陣A與學(xué)習(xí)得到的相似矩陣S存在距離，且σ范數(shù)的魯棒性更優(yōu)，本文借助于σ范數(shù)學(xué)得一個(gè)最優(yōu)的相似矩陣S。為了避免A的某些行都是0的情況，需要限制A的每一行的和均為1。為使學(xué)習(xí)得到的相似矩陣S具有c個(gè)連通分支，考慮對(duì)S的拉普拉斯矩陣LS加上秩約束，使得rank(LS)=n-c，從而S具有c個(gè)連通分支，即可以從S中直接得到聚類結(jié)果。根據(jù)以上分析提出如下目標(biāo)函數(shù)：

(7)

通過更新迭代可以求出最優(yōu)的S和F，從S中可以直接得到聚類結(jié)果，也可以從F中得到聚類結(jié)果。后續(xù)的實(shí)驗(yàn)結(jié)果表明，兩者的精度和互信息都相同。

2 目標(biāo)函數(shù)及算法流程

2.1 目標(biāo)函數(shù)的求解

利用交替優(yōu)化算法[13]求解式(7)。當(dāng)S被固定時(shí)，問題(7)可以轉(zhuǎn)化為

(8)

問題(8)的最優(yōu)解F為LS的前c個(gè)最小的特征值對(duì)應(yīng)的特征向量。

當(dāng)F被固定時(shí)，利用拉普拉斯矩陣的性質(zhì)[13]，問題(7)可以轉(zhuǎn)化為

(9)

(10)

式中：vi是一個(gè)列向量，其中vij是第j個(gè)元素；si為矩陣S中的第i行元素構(gòu)成的列向量；ai是矩陣A中第i行元素構(gòu)成列的向量；ui的取值[17]為

(11)

式(10)可以簡化為

(12)

(13)

利用拉格朗日乘子法求解問題(13)，得

(14)

式中：αi中的每個(gè)元素均大于等于0。

對(duì)sij求偏導(dǎo)并令其等于0，可得

uisij-pij-η-αij=0

(15)

根據(jù)KKT條件，式(15)可以轉(zhuǎn)化為

(16)

式中：(v)+=max(0,v)。

η求解如下：

(17)

gi(η)=0

(18)

式中：gi(η)是分段單調(diào)遞增函數(shù)，可以用牛頓迭代法求解。所求得的相似矩陣S具有c個(gè)連通分支，從而可直接得到聚類結(jié)果。

RSC-lσ算法流程如下：

輸入：親和矩陣A∈Rn×n及聚類個(gè)數(shù)c、λ、σ。

輸出：相似矩陣S∈Rn×n。

1)初始化U和F。其中U為I；F為

的前c個(gè)最小特征值對(duì)應(yīng)的特征向量。

2)進(jìn)行更新迭代:

①通過式(16)計(jì)算S。

3)算法收斂，輸出最終的S。

2.2 RSC-lσ算法的收斂性

引理1[17]對(duì)于任意的非負(fù)問量x,y∈Rc，有下列不等式成立:

(19)

結(jié)合本文算法中的目標(biāo)函數(shù)，給出如下定理：

定理1目標(biāo)函數(shù)

在固定F時(shí)，迭代更新S過程中目標(biāo)函數(shù)值一直在減小。

證明假設(shè)更新后的si為si,n，上一次的si為si,o。利用si,o,根據(jù)式(11)可以求解出ui，通過式(10)可以求解出si,n。因?yàn)閟i,n是式(10)的最小值的解，而si,o只是式(10)的一個(gè)解，所以

(20)

(21)

根據(jù)引理1知

(22)

將式(21)和(22)相加,可得

(23)

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

(24)

由‖M‖σ的定義

可得

2λtr(FTLSnF)+‖Sn-A‖σ≤

2λtr(FTLSoF)+‖So-A‖σ

(25)

2.3 算法時(shí)間復(fù)雜度分析

RSC-lσ算法的時(shí)間復(fù)雜度主要由2部分構(gòu)成：

1)構(gòu)造權(quán)重矩陣，需要根據(jù)每個(gè)樣本點(diǎn)的信息來確定其系數(shù)值，時(shí)間復(fù)雜度為O(n2)。

2)RSC-lσ算法流程主要是相似矩陣S和映射后的數(shù)據(jù)集F(即指示矩陣F對(duì)應(yīng)的集合)，交替迭代更新。對(duì)于S迭代更新的時(shí)間復(fù)雜度為O(dn2)，對(duì)于F迭代更新的時(shí)間復(fù)雜度為O(dcn)，其中n是數(shù)據(jù)個(gè)數(shù)，c為聚類數(shù)目，d為數(shù)據(jù)維度。若算法的迭代次數(shù)為t次，則時(shí)間復(fù)雜度為O(tdn2+tdcn)。因此，RSC-lσ算法的整體時(shí)間復(fù)雜度為O(tdn2+tdcn)。

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

為了驗(yàn)證RSC-lσ算法的有效性和合理性，分別在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了聚類實(shí)驗(yàn)。采用準(zhǔn)確率(accuracy，ACC)[18]及標(biāo)準(zhǔn)化互信息(normalized mutual information，NMI)[19]評(píng)價(jià)聚類結(jié)果，并與SC-KFCM算法[20]、譜聚類算法[7](相似矩陣采用本文中的親和矩陣A)、LRR算法[21]、SR算法[22]和CLR[13]算法相比較。

由于RSC-lσ算法即可以從S中得到聚類結(jié)果，也可以從F中得到聚類結(jié)果，故將算法分別命名為RSC-lσ-S和RSC-lσ-F。參數(shù)σ設(shè)置為10-4、10-3、0.01、0.1、1、10、100、103、104，λ=0.1。對(duì)于CLR算法，根據(jù)文獻(xiàn)[13]，設(shè)置參數(shù)λ=0.1；對(duì)于SR算法和LRR算法，參數(shù)λ的取值為10-4、10-3、0.01、0.1、1、10、100、103或104。

實(shí)驗(yàn)環(huán)境為Intel(R)Core(TM)i5-3210MCPU @ 2，50 GHz，內(nèi)存8 GB，操作系統(tǒng)Microsoft Windows 8，算法編寫環(huán)境為 Matlab R2015b。

3.1 參數(shù)的確定和算法收斂性實(shí)驗(yàn)

算法RSC-lσ-S和RSC-Lσ-F中的參數(shù)σ可以使得算法具有較好的魯棒性，參數(shù)λ可以控制拉普拉斯正則項(xiàng)，使得降維的數(shù)據(jù)集F與原始數(shù)據(jù)具有相同的幾何結(jié)構(gòu)。選取Lenses、Iris和Ecoli等3個(gè)經(jīng)典的真實(shí)數(shù)據(jù)集進(jìn)行參數(shù)確定實(shí)驗(yàn)，數(shù)據(jù)集信息如表1所示。

表1 人工數(shù)據(jù)集

圖1為Lenses、Iris和Ecoli數(shù)據(jù)集取不同參數(shù)時(shí)的實(shí)驗(yàn)結(jié)果。從圖1(a)可以看出,當(dāng)σ取10-4、10-3、0.01、0.1或1時(shí)聚類精度比較高。從圖1(b)可以看出,當(dāng)σ取10-4、10-3、0.01、0.1、1、10、100或104時(shí)聚類精度比較高;從圖1(c)可以看出,當(dāng)σ取103或104時(shí)聚類精度比較高。從圖1還可以看出，當(dāng)λ=0.1時(shí)，3個(gè)數(shù)據(jù)集的聚類精度均比較高。

(a)Lenses數(shù)據(jù)集

根據(jù)上述參數(shù)確定實(shí)驗(yàn)，選擇σ=0.1和λ=0.1進(jìn)行算法收斂性實(shí)驗(yàn)。算法RSC-lσ的迭代停止條件是前c個(gè)特征值的和c*趨近于0[13]。

圖2為Lenses、Iris和Ecoli數(shù)據(jù)集函數(shù)值變化圖。從圖2可以看出，隨著迭代步數(shù)的增加，前c個(gè)特征值的和c*逐漸趨近于0。因此,本文提出的算法RSC-lσ是收斂的。

3.2 穩(wěn)定性實(shí)驗(yàn)

選擇Iris、Zoo和Auto等3個(gè)比較經(jīng)典的真實(shí)數(shù)據(jù)集上進(jìn)行RSC-lσ算法穩(wěn)定性實(shí)驗(yàn)。數(shù)據(jù)集信息如表2所示。

表2 真實(shí)數(shù)據(jù)集

對(duì)于各數(shù)據(jù)集，在σ取不同值時(shí)計(jì)算出的準(zhǔn)確率，可直觀反映算法穩(wěn)定性。圖3為Iris、Zoo和Auto數(shù)據(jù)集算法穩(wěn)定性實(shí)驗(yàn)結(jié)果。從圖3可以看出，當(dāng)λ=0.1時(shí)，參數(shù)σ的取值對(duì)于算法的精度幾乎沒有影響，所以RSC-lσ算法是較為穩(wěn)定的。

(a)Iris數(shù)據(jù)集

3.3 塊對(duì)角人工數(shù)據(jù)集和人工數(shù)據(jù)集

3.3.1 塊對(duì)角人工數(shù)據(jù)集 塊對(duì)角人工數(shù)據(jù)集是由4個(gè)25×25的塊對(duì)角矩陣組成的100×100的塊對(duì)角人工數(shù)據(jù)集[13]。每個(gè)塊內(nèi)的數(shù)據(jù)表示1個(gè)簇中2個(gè)對(duì)應(yīng)點(diǎn)的親和度，而所有塊外的數(shù)據(jù)表示噪聲。每個(gè)塊內(nèi)的親和度數(shù)據(jù)在0～1范圍內(nèi)隨機(jī)產(chǎn)生，噪聲數(shù)據(jù)在0～p范圍內(nèi)隨機(jī)產(chǎn)生，這里p分別設(shè)置為0.7和0.8。此外，為了使得RSC-lσ算法聚類實(shí)驗(yàn)更具挑戰(zhàn)性，將隨機(jī)選取20個(gè)噪聲數(shù)據(jù)點(diǎn)，并將其值設(shè)置為1。

圖4為原始隨機(jī)矩陣和不同設(shè)置下3種算法的聚類結(jié)果。從圖4可以看出，RSC-lσ算法比CLR-l1、CLR-l2算法更具魯棒性,并可以更好地消除噪聲點(diǎn)對(duì)聚類結(jié)果的影響，在該實(shí)驗(yàn)中表現(xiàn)出良好的聚類性能。

3.3.2 人工數(shù)據(jù)集 選取Twoomoons和Cdata04等2個(gè)人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集信息如表3所示。

表3 人工數(shù)據(jù)集

隨機(jī)生成的Twomoons數(shù)據(jù)集中，有2個(gè)數(shù)據(jù)集群呈月狀分布；Cdata04數(shù)據(jù)集由4個(gè)環(huán)型簇組成，形如四葉草。圖5和圖6分別為2個(gè)數(shù)據(jù)集的原始聚類分布圖、初始權(quán)重連接圖以及RSC-lσ算法的聚類結(jié)果圖和相似矩陣直觀圖。圖5、6中，變量x,y用于刻畫圖的位置坐標(biāo)。

Twomoons和Cdata04權(quán)重連接圖(圖5(b)、圖6(b))將初始親和矩陣(具體構(gòu)造參考文獻(xiàn)[13])作為原始權(quán)重，將數(shù)據(jù)重新連接整理,即將數(shù)據(jù)聚類問題轉(zhuǎn)變?yōu)樽V聚類問題。

圖5(c)和圖6(c)分別為RSC-lσ算法的聚類結(jié)果圖。從圖5(c)和圖6(c)可以看出，不屬于同一類的2點(diǎn)之間完全斷開；屬于一類的2點(diǎn)之間連線更加密集。故該算法不僅能夠弱化類間的相似性，而且可以強(qiáng)化類內(nèi)相似性。

圖5(d)和圖6(d)分別是Twomoons和Cdata04數(shù)據(jù)集相似矩陣直觀圖。從圖5(d)和圖6(d)可以看出，RSC-lσ算法所構(gòu)造的相似矩陣不僅類似于塊對(duì)角結(jié)構(gòu)，而且恰好具有c個(gè)聯(lián)通分支。說明RSC-lσ算法所構(gòu)造的相似矩陣相似性較優(yōu)。

(a)原始聚類分布圖 (b)權(quán)重連接圖

(a)原始聚類分布圖 (b)權(quán)重連接圖

可見，RSC-lσ算法在上述各類數(shù)據(jù)集上都能正確劃分類簇?cái)?shù)并準(zhǔn)確聚類，說明RSC-lσ在任意形狀的人工數(shù)據(jù)集中聚類效果較好。

3.4 真實(shí)數(shù)據(jù)集

選取Balance、Lenses、Yeast、Iris、Abalone、Ecoli和Msra25等7個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集信息如表4所示。

表4 真實(shí)數(shù)據(jù)集

RSC-lσ算法、K-means算法、譜聚類算法(SC)、LRR-Ncut算法、SR-Ncut算法和CLR算法在真實(shí)數(shù)據(jù)集的聚類結(jié)果如表5和表6所示。表5為幾個(gè)算法準(zhǔn)確率(ACC)的聚類結(jié)果，表6為幾個(gè)算法標(biāo)準(zhǔn)化互信息(NMI)的聚類結(jié)果。由表5可知，按準(zhǔn)確率指標(biāo)度量，RSC-lσ算法的實(shí)驗(yàn)結(jié)果明顯優(yōu)于其他算法；由表6可知，用標(biāo)準(zhǔn)化互信息(NMI)指標(biāo)考查，除了在Balance數(shù)據(jù)集上LRR算法優(yōu)于RSC-lσ算法，其他均以RSC-lσ算法較優(yōu)。可見，RSC-lσ算法在真實(shí)數(shù)據(jù)集上的大部分聚類效果較優(yōu)。

表5 不同算法在多個(gè)數(shù)據(jù)集上的準(zhǔn)確率(ACC)

表6 不同算法在多個(gè)數(shù)據(jù)集上的標(biāo)準(zhǔn)化互信息(NMI)

綜上所述：RSC-lσ算法與親和矩陣A直接用譜聚類算法相比，聚類結(jié)果明顯更優(yōu);從S中直接得到聚類結(jié)果(RSC-lσ-S)和從F中得到聚類結(jié)果(RSC-lσ-F)，兩者的精度準(zhǔn)確率和互信息相同。

4 結(jié) 語

RSC-lσ算法是在譜聚類算法的基礎(chǔ)上學(xué)習(xí)相似矩陣，借助σ范數(shù)增加聚類結(jié)果的魯棒性；通過對(duì)學(xué)習(xí)得到的相似矩陣的拉普拉斯矩陣施加秩約束，直接得到聚類結(jié)果。多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均表明，該算法可以產(chǎn)生較好的聚類結(jié)果。但是，由于參數(shù)σ是人為選取的，使得該算法具有一定的局限性。參數(shù)σ如何自動(dòng)確定是下一步的研究方向。