基于L2,1-范數(shù)距離的約束相似矩陣的聚類算法

張 要，馬盈倉(cāng)，楊小飛，朱恒東，楊 婷

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

0 引 言

在過去的幾十年中，大量的聚類方法得到了廣泛的發(fā)展，并取得了令人矚目的成就[1,2]。文獻(xiàn)[3,4]將聚類分析的方法分為以下幾類：基于密度的聚類、劃分法聚類、基于網(wǎng)格的聚類、基于模型的聚類、層次法聚類、基于圖論的聚類。

近些年來，聚類算法得到廣泛的研究。學(xué)者們也發(fā)現(xiàn)：在聚類算法中相似度矩陣的構(gòu)建是重要而基礎(chǔ)的，對(duì)聚類結(jié)果起決定性作用[5]。所以學(xué)者們紛紛圍繞如何構(gòu)建更好的相似度矩陣展開研究。

經(jīng)典譜聚類[6]算法使用了傳統(tǒng)的高斯核函數(shù)來構(gòu)造相似矩陣；文獻(xiàn)[7]為消除噪聲的影響，從數(shù)據(jù)自身特性出發(fā)來構(gòu)造相似度矩陣，提出了一種基于自然最近鄰相似圖的譜聚類算法(NSG-SC)；文獻(xiàn)[8]利用歐式距離將數(shù)據(jù)集劃分為若干個(gè)子集，計(jì)算其協(xié)方差，并利用設(shè)定閾值來剔除交叉點(diǎn)，用剔除交叉點(diǎn)后的新數(shù)據(jù)集來學(xué)習(xí)相似度矩陣，最后用K-Means對(duì)特征分解后的相似度矩陣進(jìn)行聚類，提出了基于局部協(xié)方差矩陣的譜聚類算法。文獻(xiàn)[9]在經(jīng)典譜聚類的基礎(chǔ)上進(jìn)行改進(jìn)，在無向圖數(shù)據(jù)構(gòu)成鄰接矩陣的基礎(chǔ)上，利用SimRank計(jì)算數(shù)據(jù)集的相似度矩陣，提出了一種基于SimRank的譜聚類算法；文獻(xiàn)[10]提出了一種自適應(yīng)模糊聚類算法(AFCM)，AFCM算法中構(gòu)造的觀察矩陣、判斷矩陣和集合劃分可以自動(dòng)確定合適的聚類數(shù)，為得到更好的圖像分割效果，采用核距離作為相似性度量；文獻(xiàn)[11]提出了區(qū)間模糊譜聚類圖像分割方法，該方法通過區(qū)間模糊隸屬度構(gòu)造的區(qū)間模糊相似性測(cè)度來學(xué)習(xí)相似度矩陣，并通過規(guī)范切圖譜劃分準(zhǔn)則對(duì)圖像進(jìn)行劃分，得到最終的圖像分割結(jié)果；文獻(xiàn)[12,13]提出構(gòu)建一種無參數(shù)相似圖，即密度自適應(yīng)鄰域(DAN)，它結(jié)合了距離、密度和連通性信息，反映了數(shù)據(jù)集的局部特征。

文獻(xiàn)[14]利用距離指數(shù)變換函數(shù)和稀疏化算法構(gòu)建了分塊對(duì)角矩陣以重新解釋樣本之間的相似度；文獻(xiàn)[15]根據(jù)核參數(shù)和共享近鄰點(diǎn)的個(gè)數(shù)計(jì)算所有樣本點(diǎn)之間的相似度并進(jìn)行聚類。文獻(xiàn)[16]通過改進(jìn)傳統(tǒng)譜聚類中的度量方式，用基于傳遞距離的度量方式度量樣本間相似性；文獻(xiàn)[17]利用密度差來調(diào)整樣本點(diǎn)之間的相似度構(gòu)造新的相似矩陣函數(shù)；文獻(xiàn)[18]運(yùn)用共享近鄰來度量不同數(shù)據(jù)之間的相似程度，并利用兩數(shù)據(jù)點(diǎn)間的主動(dòng)約束信息找到他們的關(guān)系；文獻(xiàn)[19]利用有向連接矩陣作為新的相似性度量方法；文獻(xiàn)[20]提出一種以HowNet語(yǔ)義詞庫(kù)和BTM主題建模為基礎(chǔ)的相似度計(jì)算方法，將兩者進(jìn)行線性組合，綜合考察文本的相似性。文獻(xiàn)[21]運(yùn)用冪高斯核函數(shù)來求解不同數(shù)據(jù)點(diǎn)間的相似性，但該算法比較依賴先驗(yàn)信息，沒有先驗(yàn)信息的話，就難以找到合適的參數(shù)來調(diào)節(jié)鄰域尺度。

然而，許多改進(jìn)后的算法仍是基于平方歐式距離來學(xué)習(xí)相似度矩陣的，如Fuzzy K-Means(FKM)[22]、CLR_W[23]、CAN[24]等。眾所周知，雖然使用平方歐式距離較為方便，但卻不如L2,1-范數(shù)距離更具有魯棒性[25]。二次損失函數(shù)對(duì)異常值不具有魯棒性。為了克服這個(gè)缺點(diǎn)，應(yīng)該用一個(gè)對(duì)異常值不敏感的二次損失函數(shù)來代替，例如L2,1-范數(shù)。

關(guān)于算法的魯棒性問題，CSCA算法使用了基于L2,1-范數(shù)距離的目標(biāo)函數(shù)?；凇癓2,1-范數(shù)”距離，它不是平方的，通常用于誘導(dǎo)稀疏性，與平方歐式距離相比，離群值對(duì)聚類結(jié)果帶來的影響更小?？紤]到用L2,1-范數(shù)距離代替平方歐式距離可以減小離群值對(duì)聚類結(jié)果帶來的影響，但同時(shí)也對(duì)噪聲比較不敏感。所以，本文對(duì)相似度矩陣的施加平方的約束。并且本文在優(yōu)化算法上采用K鄰近法來消減噪聲帶來的影響。最后在學(xué)習(xí)相似度矩陣的過程中，約束相似度矩陣的拉普拉斯矩陣的秩，因?yàn)檫@種約束，所以也能起到直接聚類的效果。并且本文對(duì)合成數(shù)據(jù)集和一些真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)證研究，來驗(yàn)證本文提出的方法。本文所希望的實(shí)驗(yàn)結(jié)果是——本文給出的通過約束基于L2,1-范數(shù)距離的相似度矩陣的聚類方法，在大多數(shù)情況下都優(yōu)于其它相關(guān)的聚類方法。

1 新模型的建立與求解

1.1 已有模型

經(jīng)典譜聚類算法[26]的基本思想是，距離較遠(yuǎn)的兩個(gè)點(diǎn)之間的邊權(quán)重值較低，而距離較近的兩個(gè)點(diǎn)之間的邊權(quán)重值較高，不過這僅僅是定性，而譜聚類則需要定量的權(quán)重值。所以，譜聚類利用樣本點(diǎn)間的距離得到的相似度矩陣S來學(xué)習(xí)鄰接矩陣W。關(guān)系式是使用廣泛使用的自調(diào)高斯方法來構(gòu)造親和矩陣(σ的值是自調(diào)的)[26]

(1)

在學(xué)得鄰接矩陣W后，經(jīng)典譜聚類算法會(huì)通過解決問題(2)來進(jìn)行數(shù)據(jù)處理

minTr(FTLWF)s.t.FTF=I

(2)

最后，大多數(shù)譜聚類算法[27]通過在F上運(yùn)行K-Means算法，來獲得最終的聚類結(jié)果。但K-Means對(duì)F要求很高，這使得聚類性能不穩(wěn)定。

在文獻(xiàn)[23]中給出了CLR_W的初始數(shù)據(jù)圖的學(xué)習(xí)方法，目標(biāo)函數(shù)為

(3)

文獻(xiàn)[28]是學(xué)習(xí)一個(gè)數(shù)據(jù)-錨點(diǎn)二部圖(其中邊的權(quán)重表示對(duì)應(yīng)的數(shù)據(jù)與錨點(diǎn)的相似度)，并基于二部圖完成快速聚類的。其目標(biāo)函數(shù)為

(4)

可以發(fā)現(xiàn)，無論譜聚類、CLR_W、CAN，還是K-Means都是基于平方歐式距離的聚類，從而會(huì)出現(xiàn)不夠魯棒性的問題。本文為了減小離群值對(duì)聚類結(jié)果帶來的影響，采用更具有魯棒性的L2,1-范數(shù)距離來進(jìn)行初始數(shù)據(jù)圖的學(xué)習(xí)。

1.2 L2,1-范數(shù)

關(guān)于矩陣的L2,1-范數(shù)在文獻(xiàn)[29]中作為旋轉(zhuǎn)不變的L1-范數(shù)首次引入，并給出了L2,1-范數(shù)的定義。L2,1-范數(shù)也被用于多標(biāo)簽特征選擇[30]和Group Lasso[31]。

在文獻(xiàn)[32]中指出，L2,1-范數(shù)對(duì)于行來說具有旋轉(zhuǎn)不變性，其中R是任意的旋轉(zhuǎn)矩陣。并將L2,1-范數(shù)推廣到Lr,p-范數(shù)

(5)

式中：M∈Rn×m；mi表示矩陣M的第i行向量；mij表示矩陣M的第i行，第j列的元素。

而對(duì)于向量mi來說

(6)

1.3 確立相似度矩陣

考慮到利用相似度矩陣的平方，來約束相似度矩陣，可以放大不同數(shù)據(jù)點(diǎn)間的相似度差異；同時(shí)，采用K鄰近法，也可以一定程度上消減噪聲對(duì)聚類結(jié)果的影響。

圖1 是否加平方約束對(duì)相似度差異的影響

從圖1中可以看出，實(shí)線始終在虛線的線上方，這說明對(duì)相似度矩陣加以平方的約束，可以放大不同數(shù)據(jù)點(diǎn)間相似度的差異，從而能夠更好的對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類。

(7)

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

由于該算法學(xué)得的相似度矩陣S是非負(fù)的，所以如果可以直接學(xué)習(xí)到恰好具有c個(gè)連接分量的結(jié)構(gòu)化圖，就可以不使用離散化步驟。在文獻(xiàn)[28]指出，若相似度矩陣S是非負(fù)的，則歸一化拉普拉斯矩陣LS有如定理1所示的重要性質(zhì)。

定理1[28]歸一化拉普拉斯矩陣LS的特征值為0的重?cái)?shù)等于與S所對(duì)應(yīng)的圖中連通分量的數(shù)目。

所以，本文對(duì)學(xué)得的相似度矩陣的拉普拉斯矩陣施加約束條件：rank(LS)=n-c，從而得到聚類算法的目標(biāo)函數(shù)

(8)

式中：LS表示S的拉普拉斯矩陣，且LS∈Rn×n。

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

(9)

根據(jù)Ky Fan定理[33]，可得

(10)

所以式(9)可以寫成

(11)

相對(duì)于式(8)而言，式(11)較容易解決。如果固定S，那么式(11)等價(jià)于

min2λTr(FTLSF)s.t.FTF=I

(12)

這里F的符合約束條件的F的最優(yōu)解，就是LS矩陣的前c個(gè)最小特征值組成的特征向量。當(dāng)然，在這可以用K-Means去處理F的最優(yōu)解，這樣也能得到聚類結(jié)果。

根據(jù)拉普拉斯矩陣的性質(zhì)

(13)

式中：fi與fj分別表示F的第i行與第j行的向量。

如果F被固定，那么式(11)可以轉(zhuǎn)化為

(14)

(15)

由于式(15)對(duì)于不同的i之間是相互獨(dú)立的，所以對(duì)于每個(gè)i，式(15)都可以寫成

(16)

式中：vi是矩陣V的第i行向量，di是距離矩陣D的第i行向量寫成的對(duì)角矩陣，即

(17)

利用拉格朗日乘子法，可以將式(16)寫成

(18)

式中：α與βi均是拉格朗日因子，且有α≥0、βij≥0。

關(guān)于式(18)，對(duì)Si求偏導(dǎo)，并令導(dǎo)函數(shù)的值為0，可得

(19)

對(duì)每個(gè)i而言，可以將式(19)寫成

(20)

根據(jù)KKT條件[34]可知Sijβij=0，所以式(20)可以寫成

(21)

從而計(jì)算出

(22)

其中

(23)

從而，可以定義函數(shù)gi(α)

(24)

gi(α)=0

(25)

因此，α的值是函數(shù)gi(α) 的根。需要注意的是，gi(α) 是一個(gè)分段線性單調(diào)遞增的函數(shù)，因此用牛頓迭代法可以很容易地求出根。計(jì)算α后，由式(22)得到式(14)的最優(yōu)解。

CSCA具體算法如下：

輸入： 特征矩陣F，聚類數(shù)c，足夠大的λ，近鄰參數(shù)k。

輸出： 聚類結(jié)果y。

(1)計(jì)算數(shù)據(jù)點(diǎn)間的距離矩陣D。

(2)初始化特征矩陣F。

(3)對(duì)距離矩陣D的每行排序。

(4)設(shè)置迭代。

for j=1,2,…,n do

定義相似度矩陣S∈Rn×n。

(5)更新新相似度矩陣S。

for i=1,2,…,n do

找出，第i個(gè)數(shù)據(jù)點(diǎn)的k近鄰。

找出，k近鄰所對(duì)應(yīng)的vij。

對(duì)每個(gè)i，根據(jù)求解式(16)來更新相似度矩陣的Si。

end for

(6)更新特征矩陣F。

(7)設(shè)置跳出迭代條件，并用二分法調(diào)節(jié)參數(shù)λ的值。

(8)通過求圖的連通分支直接得到聚類結(jié)果y。

end for

2 實(shí)驗(yàn)與結(jié)果

為體現(xiàn)本文所提出的聚類算法CSCA的可行性，選取了經(jīng)典聚類算法：K-Means算法、RCut算法、NCut算法；經(jīng)典子空間聚類算法：SR算法、LRR算法；以及經(jīng)學(xué)者改進(jìn)的算法：CLR_W算法、CAN算法，作為對(duì)比算法。并且采用準(zhǔn)確率(Accuracy，ACC)、標(biāo)準(zhǔn)化互信(norma-lized mutual information，NMI)[35]等多種評(píng)價(jià)指標(biāo)對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。

在參數(shù)方面，由于K-Means算法的不穩(wěn)定性，對(duì)于 K-Means 算法、SR算法、LRR算法，采用運(yùn)行10次取最大值的方法。對(duì)于RCut算法和NCut算法，實(shí)驗(yàn)使用了廣泛使用的自調(diào)高斯方法來構(gòu)造親和矩陣(σ的值是自調(diào)的)。對(duì)于CLR_W算法與 CAN算法，實(shí)驗(yàn)使用了文獻(xiàn)[23]中給出的初始數(shù)據(jù)圖的學(xué)習(xí)方法，而CLR_W算法與CAN算法中的參數(shù)λ是自調(diào)的。對(duì)于CSCA算法中的參數(shù)λ與近鄰參數(shù)K，其中參數(shù)λ是自調(diào)的，近鄰參數(shù)K的取值為3～10。

在實(shí)驗(yàn)環(huán)境方面，本文所有的實(shí)驗(yàn)相關(guān)環(huán)境為：Microsoft Windows7系統(tǒng)，處理器為：Intel(R) Core(TM) i5-4210U CUP @ 1.70 GHz 2.40 GHz，內(nèi)存：4.00 GB，采用編程軟件為：Matlab R2016a。

2.1 人工數(shù)據(jù)集實(shí)驗(yàn)

在人工數(shù)據(jù)集的實(shí)驗(yàn)上，采用人工雙月數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。人工雙月數(shù)據(jù)集是由2個(gè)集群構(gòu)成的數(shù)據(jù)集，其中每個(gè)集群包含200個(gè)2維數(shù)據(jù)點(diǎn)為樣本。雙月構(gòu)成的圖形如圖2(a)所示。噪聲百分比設(shè)置為0.1。近鄰參數(shù)K設(shè)置為9。實(shí)驗(yàn)的目標(biāo)是在學(xué)習(xí)相似矩陣的同時(shí)，通過約束相似矩陣的拉普拉斯矩陣的秩，使相似矩陣中剛好有2個(gè)連通分量。用CSCA進(jìn)行了測(cè)試，取得了較好的效果。在圖2(a)中，數(shù)據(jù)的原始圖呈現(xiàn)雙月狀，讓連線的寬度表示兩個(gè)對(duì)應(yīng)點(diǎn)的親和力。從圖2(b)中可以很容易地觀察到本文提出的聚類算法CSCA的有效性。

圖2 雙月數(shù)據(jù)原始圖像與聚類結(jié)果

此外，實(shí)驗(yàn)還采用人工螺旋數(shù)據(jù)集Spiral進(jìn)行實(shí)驗(yàn)。人工數(shù)據(jù)集Spiral是由3個(gè)集群構(gòu)成的數(shù)據(jù)集，其中每個(gè)集群包含104個(gè)2維數(shù)據(jù)點(diǎn)為樣本。Spiral構(gòu)成的圖形如圖3(a) 所示。噪聲百分比設(shè)置為0.1。近鄰參數(shù)K設(shè)置為3～8。在圖3(a)中，可以看出數(shù)據(jù)呈現(xiàn)螺旋狀，由3條點(diǎn)線螺旋組成，每條線為一個(gè)集群。圖3(b)則是聚類算法CSCA的聚類結(jié)果。

圖3 Spiral原始數(shù)據(jù)與聚類結(jié)果

同時(shí)本文還分析了，在雙月數(shù)據(jù)集與Spiral數(shù)據(jù)集上，近鄰參數(shù)K的取值對(duì)準(zhǔn)確率的影響。結(jié)果如圖4、圖5所示。從圖中可以看出，近鄰參數(shù)K的取值只有在一定范圍時(shí)，聚類效果才能達(dá)到最好。一般為3～8。

圖4 CSCA算法下近鄰參數(shù)K對(duì)雙月數(shù)據(jù)聚類結(jié)果的影響

圖5 CSCA算法下近鄰參數(shù)K對(duì)Spiral 數(shù)據(jù)聚類結(jié)果的影響

2.2 人臉數(shù)據(jù)庫(kù)(ORL)聚類

ORL包含40個(gè)不同人的面部圖片，每一個(gè)都有10張不同的圖片。這些照片是在不同的時(shí)間拍攝的，并改變了光線、面部表情和面部細(xì)節(jié)。所有的圖片都是在暗色均勻的背景下拍攝的，支架處于直立、正面的位置(可以容忍一些側(cè)面的運(yùn)動(dòng))。每個(gè)圖片的分辨率大小為92×112。

實(shí)驗(yàn)使用了ORL人臉數(shù)據(jù)庫(kù)中的前20個(gè)人的人臉圖片，共200張圖片，并把每張圖片轉(zhuǎn)換為10 304維的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖6所示，并給出CLR_W的結(jié)果，如圖7所示，可以發(fā)現(xiàn)CSCA的實(shí)驗(yàn)結(jié)果明顯優(yōu)于CLR_W。

圖6 CSCA對(duì)人臉數(shù)據(jù)集的聚類結(jié)果(ACC=88.50%)

圖7 CLR_W對(duì)人臉數(shù)據(jù)集的聚類結(jié)果(ACC=77.00%)

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

在針對(duì)真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)中，采用了6個(gè)真實(shí)數(shù)據(jù)集Yeast、Abalone、MSRA25、USPSdata20(http://www.pudn.com /Download/item/id/3945155.html)、Iris、Lung上進(jìn)行實(shí)驗(yàn)，前兩個(gè)是UCI機(jī)器學(xué)習(xí)庫(kù)中的生物信息學(xué)數(shù)據(jù)集。它們含蓋了高維與低維、多樣本與少樣本以及多類別與少類別等各種真實(shí)數(shù)據(jù)集的特點(diǎn)。6個(gè)真實(shí)數(shù)據(jù)集的參數(shù)見表1。

在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果見表2、表3，其中加粗的數(shù)據(jù)表示結(jié)果最好，加下劃線的次之。表2顯示的是各數(shù)據(jù)集下不同算法的ACC對(duì)比；表3顯示的是各數(shù)據(jù)集下不同算法的NMI對(duì)比。在真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果上顯示，對(duì)于不同的真實(shí)數(shù)據(jù)集，聚類算法CSCA在大多數(shù)情況下是優(yōu)于其它算法的。所以，這也驗(yàn)證了聚類算法CSCA的有效性。

表1 真實(shí)數(shù)據(jù)集信息

表2 各數(shù)據(jù)集下不同算法的ACC對(duì)比

表3 各數(shù)據(jù)集下不同算法的NMI對(duì)比

3 結(jié)束語(yǔ)

CSCA算法是L2,1-范數(shù)距離來學(xué)習(xí)相似度矩陣的，從而增加聚類算法的魯棒性，引導(dǎo)相似度矩陣的稀疏性；并用平方約束相似度矩陣；通過對(duì)相似度矩陣的拉普拉斯矩陣施加秩的約束，來實(shí)現(xiàn)聚類的。也可以利用K-Means對(duì)F進(jìn)行聚類，得到聚類結(jié)果。該算法與對(duì)比算法相比，在大多數(shù)情況下，結(jié)果是優(yōu)于對(duì)比算法的，該算法在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果也能說明這一點(diǎn)。但是由于近鄰參數(shù)K值的選取，是人為選取的，且對(duì)含有噪聲的數(shù)據(jù)集的聚類結(jié)果影響較大。從而使得該算法具有一定的局限性，所以接下來本文將對(duì)于如何消減噪聲的影響做進(jìn)一步的改進(jìn)。一方面，可以用其它消減噪聲的影響的方法來代替K近鄰，或者進(jìn)一步的改進(jìn)近鄰參數(shù)K值的選取方法，使其在實(shí)驗(yàn)不同的數(shù)據(jù)集時(shí)使其能夠自動(dòng)調(diào)整；另一方面，可以選取合適的正則項(xiàng)，對(duì)相似度矩陣施加正則化，或者引入合適的半監(jiān)督學(xué)習(xí)方法，來學(xué)得更好的相似度矩陣。