基于相關(guān)熵的快速聚類算法

李中衡,楊奔,張勁節(jié),劉銀川,張雪濤,王飛

(西安交通大學視覺信息處理與應用國家工程實驗室,710049,西安)

聚類[1-13]也稱為無監(jiān)督學習,可以將無標簽數(shù)據(jù)自動劃分為確定的類別,廣泛應用于數(shù)據(jù)挖掘[14]、計算機視覺[15]和模式識別[16]等領(lǐng)域。早期聚類算法研究的熱點是如何提高聚類的性能,針對這一問題,研究人員提出了許多聚類算法,如基于矩陣分解的算法[11,12,17-19]、基于k均值的算法[1-3,13,20]以及基于譜聚類(SC)的算法[4-6,15,21],這些算法均有效地推動了早期聚類研究的發(fā)展。其中,由于基于譜聚類的聚類方法具有不受樣本空間形狀限制的優(yōu)點,使得越來越多的研究者開始聚焦于這一領(lǐng)域。

隨著近年來數(shù)據(jù)的爆炸式增長,傳統(tǒng)的聚類算法在處理這些大規(guī)模數(shù)據(jù)時已經(jīng)很難滿足人們的需求。例如,譜聚類的計算復雜度為O(n2d+n3)[15](n為樣本數(shù),d為特征維數(shù)),其中O(n2d)是構(gòu)造n×n的相似度矩陣所需的計算復雜度,O(n3)是對相似度矩陣進行特征分解所需的計算復雜度。當樣本數(shù)或者樣本特征維度急劇增加時,譜聚類的效率會顯著降低。特別是當樣本數(shù)增加到某一臨界值時,由于計算機內(nèi)存的限制,譜聚類將崩潰。因此,如何有效地對大規(guī)模數(shù)據(jù)聚類已逐漸進入大眾的視野,并逐漸占據(jù)了重要的地位。

對于大規(guī)模的無標簽數(shù)據(jù),特別是多樣本點數(shù)據(jù)或高特征維度數(shù)據(jù),研究人員提出了許多快速的聚類算法。例如,基于矩陣分解的方法中,非負矩陣互分解算法[22](FNMTF)和局部保留非負矩陣互分解算法[22](LPFNMTF)直接將因子矩陣約束為聚類指示矩陣,模型的優(yōu)化部分為只需少量矩陣乘法的快速更新規(guī)則,從而可有效降低處理大規(guī)模數(shù)據(jù)時的計算復雜度。類似地,雙邊k均值算法[23](BKM)作為一種基于k均值的加速方法,受到FNMTF的啟發(fā),并在其基礎(chǔ)上將吸收因子約束為對角矩陣,進一步提高了對大規(guī)模數(shù)據(jù)的聚類效率。同時,在過去的一段時間里,各種加速譜聚類算法也被陸續(xù)提出,如基于二分圖的大規(guī)模多視圖譜聚類算法[9](LMVSCB)、大規(guī)模譜聚類算法[24](LSC)、針對大規(guī)模數(shù)據(jù)的譜聚類算法[25](SCLD)、分布式系統(tǒng)中的并行譜聚類算法[26](PSCD)等,這類算法常常通過優(yōu)化建圖模塊(采用不同的映射或采樣方法)或特征分解模塊來降低計算復雜度。盡管這些嘗試都能在一定程度上提高大規(guī)模數(shù)據(jù)的聚類效率,但它們?nèi)源嬖谧陨淼娜毕荨＠?當數(shù)據(jù)維數(shù)變大時,基于矩陣分解方法的效率顯著降低,而基于加速譜聚類的方法在處理大規(guī)模數(shù)據(jù)時,由于對特征分解的需求,仍然非常耗時。因此,如何進一步提高大規(guī)模數(shù)據(jù)的聚類效率仍然是一個亟待解決的問題。

另一方面,真實世界數(shù)據(jù)中存在大量不同分布的噪聲和離群點,特別是在高維數(shù)據(jù)[27-28]中,它們往往對聚類算法的性能有很大影響。如何抑制這些噪聲和離群點對聚類性能的影響也是當前的一個熱點問題。目前,主流的方法是用L1范數(shù)[10]或L2-1范數(shù)[29]代替?zhèn)鹘y(tǒng)的均方誤差(MSE),提高聚類的魯棒性,這在許多應用中已經(jīng)被證明是有效的。但是,它們僅能有效地抑制線性或高斯分布的噪聲,對大量非線性和非高斯分布的噪聲及離群點的抑制效果是非常有限的。針對這個問題,GCCF[12](基于相關(guān)熵的圖正則概念分解算法)將相關(guān)熵[30-33]引入到聚類模型中,利用相關(guān)熵對非線性和非高斯分布的噪聲以及離群點良好的抑制功能,有效地提高了聚類算法的性能,但由于其具有O((n2c+ndc+n2d)t)(c是聚類數(shù),t是迭代次數(shù))的計算復雜度,很難被應用于大規(guī)模數(shù)據(jù)的聚類中。

針對上述問題,本文提出了一種基于相關(guān)熵的快速聚類方法(FCC)。在圖正則約束的條件下,最小化k均值得到的類別標簽與圖聚類得到的類別標簽之間的誤差。由于本文方法兼顧了k均值與圖聚類的聚類結(jié)果,故此也繼承了二者各自的優(yōu)點,可進一步提高聚類的性能。另一方面,由于本文方法最小化兩種聚類算法的聚類指示陣(n×c),與數(shù)據(jù)矩陣(n×d)或相似度矩陣(n×n)相比,更適合于處理大規(guī)模數(shù)據(jù),特別是大規(guī)模高維度的數(shù)據(jù)。此外,受GCCF的啟發(fā),FCC采用相關(guān)熵來度量誤差,提高了算法對非線性、非高斯噪聲和離群點的抑制能力,從而有效地提高了聚類性能。

本文的主要貢獻如下:

(1)提出了一種基于相關(guān)熵的快速聚類算法,該算法能有效地對真實世界數(shù)據(jù)(包含大量非線性和非高斯分布的噪聲以及離群點)進行聚類。特別是在面對高維數(shù)據(jù)時,FCC的效率遠遠高于現(xiàn)有的快速性方法。

(2)由于引入了相關(guān)熵,FCC的目標函數(shù)變?yōu)殡y以直接求解的非凸函數(shù)。本文提出了一種基于半二次(HQ)極小化技術(shù)的優(yōu)化策略,可以通過較少的迭代次數(shù)提高求解效率。此外,本文還分析了FCC的計算復雜度和參數(shù)敏感性。

(3)本文在4個不同的真實大規(guī)模數(shù)據(jù)集(包含兩個多樣本點數(shù)據(jù)集和兩個高特征維度數(shù)據(jù)集)上進行了大量的實驗,結(jié)果表明,與目前主流的快速聚類算法相比,FCC能夠更快地獲得比這些算法更好的聚類性能。

1 相關(guān)工作

1.1 相關(guān)熵

在信息論學習(ITL)中,為了抑制信號中非線性和非高斯分布的噪聲以及離群點引起的不可預測的誤差,研究人員提出了相關(guān)熵[30]的概念,它可以根據(jù)兩個隨機變量X和Y定義為

V(X,Y)=E[κ(X,Y)]=∑κ(x,y)dFXY(x,y)

(1)

式中:E[·]表示期望算子;κ(x,y)是移位不變Mercer核;FXY(x,y)表示(X,Y)的聯(lián)合分布函數(shù)。本文采用的核函數(shù)為

κ(x,y)=G(x-y)=exp(-(x-y)2/2δ2)

(2)

式中:δ>0表示高斯核的核帶寬參數(shù)。在實際中,由于能獲得的樣本數(shù)量有限,聯(lián)合分布函數(shù)往往是未知的。因此,相關(guān)熵通常表示為以下形式

(3)

1.2 半二次技術(shù)

半二次(HQ)技術(shù)[27,32-33]由于能夠求解ITL中的非線性和非凸損失函數(shù),在圖像處理、模式識別和魯棒估計中得到了廣泛的應用。對于隨機向量x∈Rn,x的潛在損失函數(shù)f(x)可定義如下

(4)

式中:xi表示x的第i個元素。引入xi的輔助向量z,可以將式(4)的增強函數(shù)定義為

(5)

式中:zi僅依賴于f(xi);g(zi)是f(xi)的雙勢函數(shù);Z(xi,zi)表示HQ函數(shù)。本文利用了廣泛使用的HQ函數(shù)的乘法形式,表示如下

(6)

式中:z=[z1,…,zn]是輔助量。結(jié)合式(5)和式(6),勢函數(shù)的向量形式如下

(7)

2 FCC模型

本文提出的算法能夠有效地處理包含噪聲(特別是非線性和非高斯分布的噪聲)以及離群點的大規(guī)模數(shù)據(jù)。FCC主要由兩步組成:利用k均值生成粗聚類標簽,并將其作為真值輸入到第二步;利用第一步輸入的標簽矩陣,在圖正則約束的條件下完成基于錨點圖的聚類。因此,FCC不僅繼承了k均值和圖聚類的優(yōu)點,而且大大降低了計算復雜度。此外,引入相關(guān)熵可以有效地抑制真實數(shù)據(jù)中的噪聲和離群點對性能的影響,從而有效提高聚類算法的性能。

假設(shè)X=[x1,x2,…,xn]T∈Rn×d是一組包含c類的無標簽大規(guī)模數(shù)據(jù)。在FCC的第一步中,需要使用k均值為每個樣本生成粗類別。更準確地說,這一步需要生成一個指示矩陣C∈Rn×c,它的每一行只有一個元素1,其余元素都是0。因此,在后續(xù)的圖聚類過程中,FCC還可以繼承k均值得到的原始數(shù)據(jù)的內(nèi)部結(jié)構(gòu)。此外,得到的指示矩陣C代替原始數(shù)據(jù)矩陣X作為第二步聚類的輸入,可以大大降低需要處理的數(shù)據(jù)規(guī)模,從而提高對大規(guī)模數(shù)據(jù)聚類的效率。

FCC的第二步需要在原始數(shù)據(jù)和它們的錨點之間構(gòu)造一個錨點圖[34],然后利用錨點圖的拉普拉斯矩陣作為正則約束來完成圖聚類過程。該步驟繼承了圖聚類不受樣本空間形狀的限制以及具有良好的數(shù)學框架的優(yōu)點。同時,錨點圖的構(gòu)造大大降低了數(shù)據(jù)的維度,保證了處理大規(guī)模數(shù)據(jù)時的高效性。

在構(gòu)造錨點圖之前,首先需要生成錨點。目前,主流的錨點生成方法主要有隨機采樣法和k均值兩種。實踐證明,使用隨機采樣和k均值生成相同數(shù)量的錨點,由k均值生成的錨點往往能在后續(xù)聚類過程中獲得更高的聚類性能,因此本文采用k均值生成錨點。

設(shè)U=[u1,u2,…,um]T∈Rn×d為用k均值生成的X的錨點,錨點圖矩陣可用下式表示

(8)

式中:H為原始數(shù)據(jù)與其錨點之間的錨點圖矩陣;xi和uj分別為X和U中的第i行和第j行;Δi表示{1,2,…,m}的一個子集,{1,2,…,m}為U中xi的k近鄰的個數(shù);ψ(a,b)可以表示為

(9)

其中σ是一個名為高斯核帶寬(GKB)的自由參數(shù),它決定著式(9)的魯棒性。

此時,數(shù)據(jù)X與其錨點之間的錨點圖矩陣對應的相似度矩陣W可表示為

W=HHT

(10)

(11)

(12)

因此,與L的p個最小特征向量相對應的W的p個最大特征向量Σp可以按如下公式計算

(13)

式中:Λp是Λ的前p列;Πp是集合(ε1,ε2,…,εp)對應的對角矩陣。

結(jié)合第一步得到的粗標簽C和本部分基于圖約束的聚類方法,可以定義如下聚類公式

(14)

式中:Zp=Rp×c是輔助變量矩陣。

此外,為了處理大量的各種分布的噪聲,特別是各種非線性和非高斯的噪聲以及實際數(shù)據(jù)中的離群點,在式(14)中引入相關(guān)熵,即可得到FCC的目標函數(shù)如下

(15)

當式(15)達到最大值時,ΣpZp和C之間的誤差最小。此時,可以直接從ΣpZp獲得最終的數(shù)據(jù)類別。

3 優(yōu)化與分析

為了求解FCC的目標函數(shù),本節(jié)提出了一種新的交互式迭代求解策略。在優(yōu)化之前,首先需要利用半二次最小化技術(shù)將式(15)轉(zhuǎn)化為凸函數(shù)如下

(16)

式中:ei是HQ技術(shù)的輔助量。由于式(16)是一個凸函數(shù),故可直接優(yōu)化求解。具體來說,式(16)需要在固定Zp的條件下最大。此時,ei可通過以下公式獲得

(17)

式中:σ是影響相關(guān)熵魯棒性的自由參數(shù),表示為

(18)

此時,式(16)可以表示為如下形式

(19)

等價于以下優(yōu)化問題

(20)

式中:ri=-ei/σ2。在此基礎(chǔ)上,式(15)的優(yōu)化問題轉(zhuǎn)化為只需交互迭代求解R=diag(r1,r2,…,rn)T和Zp,使式(20)最小化。

更新R:R是對角矩陣,對角線元素為Rii=ri,其中ri可表示為

(21)

更新Zp:為了求解Zp,式(20)可以重新寫成如下矩陣形式,其中Y=ΣpZp

(22)

根據(jù)矩陣跡的性質(zhì),如tr(AB)=tr(BA)和tr(AT)=tr(A),式(22)可變換為以下形式

λtr(YTLY)

(23)

對應的拉格朗日函數(shù)可定義為

L=tr(YTRY)-2tr)CTRY)+tr(CTRC)+

λtr(YTLY)+tr(φYT)

(24)

式中:Φ=[Φ]ij∈Rn×c是拉格朗日乘數(shù)。然后,可以導出拉格朗日函數(shù)的偏導數(shù)

(25)

轉(zhuǎn)換如下

2(RY)ijYij-2(RTC)ijYij+2λ(LY)ijYij+

ΦijYij=0

(26)

利用KKT條件(如ΦijYij=0),式(26)可轉(zhuǎn)化為

2(RY)ijYij-2(RTC)ijYij+2λ(LY)ijyij=0

(27)

因此,可得到如下更新規(guī)則

(28)

由于Y=ΣpZp,Zp可通過下式計算

(29)

此外,Zp可按照以下規(guī)則進行歸一化

(30)

利用以上更新規(guī)則迭代更新R和Zp,直到目標函數(shù)收斂,完成聚類的全過程。此時,樣本的類別可以直接從Y中得到。詳細的FCC算法如下。

算法:基于相關(guān)熵的快速聚類算法(FCC)

輸入:原始數(shù)據(jù)X、錨點數(shù)量m、前p個引導特征向量、類的數(shù)量c和參數(shù)λ。

輸出:所有樣本的聚類類別Y。

1:使用k均值生成m個錨點。

2:利用式(8)構(gòu)造錨點圖。

3:計算度矩陣D和拉普拉斯矩陣L。

4:設(shè)Zp∈Rp×c為隨機正矩陣,σ由式(18)得到。

5:while不收斂do

6:通過解式(21)更新R。

7:通過解式(28)、式(29)和式(30)更新Zp。

8:end while

9:由Y直接獲取樣本類別。

FCC的計算復雜度主要由生成錨點、構(gòu)造錨點圖和迭代優(yōu)化幾個部分組成。這些部分的復雜性分別如下。

(1)利用k均值從n個樣本中生成m個錨點,需要O(nmdt1)的復雜度,其中d是樣本的特征維數(shù),t1是k均值的迭代次數(shù)。

(2)利用式(8)在n個樣本和m個錨點之間構(gòu)建錨點圖時,需要O(nmd)的復雜度。

(3)優(yōu)化時需要的復雜度為O((nc2+npc)t2)。準確地說,求解R需要O(nc2)的復雜度,更新Zp需要O(npc)的復雜度,t2是目標函數(shù)收斂時的迭代次數(shù)。

因此,FCC的總體計算復雜度為O(nmd(t1+1)+(nc2+npc)t2)。由于在處理大規(guī)模數(shù)據(jù)時m、d、p、c、t1和t2比n小得多,因此FCC的復雜度可以近似為O(n)。特別是當數(shù)據(jù)的維數(shù)較高時,FCC在求解目標函數(shù)時與數(shù)據(jù)維數(shù)無關(guān),因而仍能保持較低的計算復雜度。

4 實 驗

4.1 數(shù)據(jù)集

本文使用WebKB[35]、TDT2[12]、Mnist[36]和Cora[37]4個常用的真實數(shù)據(jù)集測試了FCC和其他典型算法的聚類性能。其中,WebKB是一種廣泛應用于聚類算法的真實文本數(shù)據(jù)集,本文采用隨機采樣得到827個樣本點共7類數(shù)據(jù),組成新的WebKB數(shù)據(jù)集來測試所有算法的性能;TDT2包含了11 201個主題文檔,本文刪去了少于30個文檔的那些類別,組成了新的包含9 394個文檔共30類的新的TDT2數(shù)據(jù)集;Mnist是一個包含60 000個訓練樣本和10 000個測試樣本的手寫體數(shù)字數(shù)據(jù)集,本文在訓練集中針對每一類隨機采樣,組成了具有6 996個樣本共10類的新的Mnist數(shù)據(jù)集;Cora數(shù)據(jù)集為計算機科學領(lǐng)域的研究論文集,類似地,我們利用隨機采樣得到了包含7 511個樣本共10類的新的Cora數(shù)據(jù)集作為本文中所使用的算法的測試數(shù)據(jù)。各數(shù)據(jù)集具體情況見表1。

表1 數(shù)據(jù)集描述Table 1 Description of all datasets

4.2 對比方法

為了驗證FCC的性能,本文選取了幾種典型的快速以及魯棒的聚類算法FNMTF、BKM、LPNMTF、LSSC和KMM作為對比,對比算法的詳細情況總結(jié)如下。

FNMTF[22]:一種基于矩陣分解的快速聚類算法,它將因子矩陣直接約束為聚類指示矩陣,并提出了一種只包含少量矩陣乘法的優(yōu)化算法。

BKM[23]:一種快速的雙邊k均值算法,在約束因子矩陣為聚類指示矩陣的基礎(chǔ)上,進一步將吸收因子矩陣限制為對角矩陣。

LPFNMTF[22]:一種新的局部保留正則化的FNMTF方法,該方法通過增加流形正則化來實現(xiàn)對兩個分解因子矩陣的幾何約束。

LSSC[10]:一種稀疏的魯棒大規(guī)模聚類算法,由于L1范數(shù)的稀疏性和魯棒性,該模型利用了L1范數(shù)約束帶有圖正則的聚類模型。

KMM[13]:一種最新的高精度擴展k均值方法,它將問題形式化為一個優(yōu)化問題,這些子問題采用交替優(yōu)化策略分別求解。

4.3 評估指標

(1)聚類精度[38]:衡量簇與類之間的一一對應關(guān)系,可以表示為

(31)

式中:xi為第i個樣本的真實標簽;yi為相應的習得標簽;map(yi)為使用Kuhn-Munkres算法[39]從學習標簽到真值標簽的轉(zhuǎn)換,f(x,y)取值如下

(32)

(2)歸一化互信息[40]:通常用于度量聚類結(jié)果的相似度,其定義如下

(33)

式中:I(xi,yi)表示互信息;E(·)表示信息熵。歸一化互信息也可以表示為

(34)

(3)聚類純度[41]:正確聚類的樣本百分比通常用聚類純度表示,定義為

(35)

4.4 結(jié)果

所有算法均在256 GB的3.50 GHz Intel(R)Xeon(R)CPU E5-1620 v3和Matlab 2019a(64位)平臺上運行,聚類結(jié)果和計算時間分別如表2和表3所示。其中“—”表示計算時間超過5 h,由于其他算法均能在幾千秒甚至幾十秒內(nèi)完成聚類全過程,故此計算時間超過5 h后我們不再關(guān)注該算法的性能。結(jié)合表2和表3可以看到,與這些算法相比,FCC不僅可以獲得更好的聚類性能,而且可以保持最短的計算時間。特別地,由于這些數(shù)據(jù)集都是真實世界的數(shù)據(jù),因此包含了大量不同分布的噪聲和離群點。FCC通過引入相關(guān)熵可以有效地抑制非線性和非高斯分布的噪聲以及離群點對聚類性能的影響,從而可以更快地處理包含大量噪聲和離群點的大規(guī)模真實世界數(shù)據(jù)。

表2 所有方法在不同數(shù)據(jù)集上的聚類結(jié)果Table 2 Clustering results comparison of all methods on different datasets

表3 所有方法在不同數(shù)據(jù)集上的聚類時間Table 3 Computational time comparison of all methods on different datasets

4.5 參數(shù)分析

兩個參數(shù)主要影響FCC的性能和效率,分別是錨點數(shù)m和正則項系數(shù)λ。本文選取錨點集合為[c+1,c+3,c+5,c+7,c+9,50],圖1給出了FCC在不同錨點數(shù)的WebKB和Cora上運行的實驗結(jié)果。可以看出,當錨點數(shù)較少時, 隨著錨點數(shù)的增加,聚類性能逐漸提高。當錨點數(shù)增加到一定程度時,聚類性能相對穩(wěn)定,不再大幅度增加。同時,隨著錨點數(shù)量的不斷增加,計算時間也在不斷增加。因此,選擇合適數(shù)量的錨對聚類性能和效率有很大的影響。

(a)不同錨點數(shù)在WebKB上對應的聚類結(jié)果

圖2展示了具有不同λ的FCC的聚類結(jié)果和計算時間,其中λ屬于[100,101,102,103,104,105]集合。可以看出,總體來說,當λ變化時,聚類精度和聚類純度相對穩(wěn)定,最大互信息波動較大。另外,計算時間隨著λ的增加總體保持穩(wěn)定波動。因此,合適的λ往往會帶來較好的聚類性能和短的計算時間。

(a)不同λ在WebKB上對應的聚類結(jié)果

4.6 魯棒性分析

為了進一步驗證本算法對噪聲(特別是非線性和非高斯噪聲)的抑制效果,本文以WebKB和Cora數(shù)據(jù)集為例,對其分別加入10%和20%的隨機噪聲和泊松噪聲,構(gòu)成含噪數(shù)據(jù)集作為魯棒性測試的數(shù)據(jù)集。圖3給出了不同算法在不同噪聲條件下的聚類精度對比,從中可以看到,相對于其他對比算法,特別是魯棒的算法LSSC和KMM,本文方法均可在各種噪聲條件下達到優(yōu)于它們的聚類精度且性能幾乎不隨噪聲程度的增加明顯變化,故此本文算法是一種能夠高效處理含噪真實數(shù)據(jù)的魯棒性算法。

(a)隨機噪聲腐蝕狀態(tài)下算法在WebKB上的聚類精度

5 結(jié) 論

本文提出了一種基于相關(guān)熵的快速聚類算法(FCC),以k均值生成的標簽矩陣代替原始數(shù)據(jù)作為圖聚類的輸入,以錨點圖代替?zhèn)鹘y(tǒng)圖,降低了數(shù)據(jù)的維數(shù),可以有效處理大規(guī)模的真實數(shù)據(jù)。同時,通過相關(guān)熵有效降低了實際數(shù)據(jù)中的噪聲以及離群點對算法性能的影響,極大地提高了聚類算法的性能。在真實世界大規(guī)模數(shù)據(jù)集上的實驗表明,相對于那些典型的聚類算法,FCC能夠在最短時間內(nèi)達到良好的聚類性能。