局部相似性優(yōu)化的p-譜聚類算法*

胡乾坤，丁世飛

中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116

1 引言

聚類是數(shù)據(jù)挖掘領(lǐng)域中熱門的研究課題之一，其研究目的是根據(jù)相似性的大小把數(shù)據(jù)分到不同的簇中，使得簇內(nèi)數(shù)據(jù)之間的相似性盡可能大，簇間數(shù)據(jù)之間的相似性盡可能小。目前，很多聚類算法已經(jīng)被提出，例如層次聚類[1]、k-means聚類[2]、支持向量機(jī)[3]、初始化獨(dú)立聚類[4]、多視圖聚類[5]等算法。近幾年來(lái)，譜聚類算法逐漸發(fā)展成為較重要的聚類算法之一，原因是其具有較強(qiáng)的概括性、有效性和豐富的理論基礎(chǔ)[6]。譜聚類算法的理論基礎(chǔ)包括平衡圖切判據(jù)、隨機(jī)游走和擾動(dòng)理論[7]。譜聚類算法的核心思想是把樣本空間的聚類問(wèn)題轉(zhuǎn)化無(wú)向圖G的圖劃分問(wèn)題。數(shù)據(jù)樣本視作無(wú)向圖G上的頂點(diǎn)，數(shù)據(jù)樣本對(duì)之間的相似性視作頂點(diǎn)之間邊的權(quán)重。一般譜聚類算法包含以下3個(gè)步驟：第一，根據(jù)所給的樣本數(shù)據(jù)集，定義一個(gè)相似性矩陣來(lái)描述數(shù)據(jù)之間的相似性；第二，進(jìn)一步構(gòu)建拉普拉斯矩陣并計(jì)算其特征值和對(duì)應(yīng)特征向量；第三，選擇合適的特征向量，使用傳統(tǒng)聚類算法對(duì)數(shù)據(jù)樣本進(jìn)行聚類[8]。

最近，在譜聚類中引入p-Laplacian算子，引起了研究者的廣泛關(guān)注。它使得算法可以獲得較好的圖切判據(jù)，即Cheeger cut（Ccut或者齊格切）[9]。Ccut旨在尋求一種簇內(nèi)數(shù)據(jù)樣本之間的相似性盡量大，簇間數(shù)據(jù)樣本之間的相似性盡量小，同時(shí)可以獲得更具有平衡性的劃分效果。研究表明，通過(guò)計(jì)算p-Laplacian矩陣的第二小特征向量，使用圖劃分標(biāo)準(zhǔn)Ccut能夠獲得更具有平衡性的聚類效果。但是，原p-譜聚類算法的相似性計(jì)算方法很難構(gòu)造一個(gè)高質(zhì)量的相似性矩陣來(lái)描述數(shù)據(jù)之間的內(nèi)在關(guān)系，聚類效果對(duì)相似性計(jì)算方法是非常敏感的；再者，算法中相似性計(jì)算的方法與數(shù)據(jù)聚類的方法分別在兩個(gè)不同的步驟中實(shí)現(xiàn)，故相似矩陣并不一定是適合此聚類方法的，從而有可能得不到最優(yōu)的聚類效果[10]。

本文從一種新的視角出發(fā)來(lái)解決上述聚類問(wèn)題。首先，通過(guò)數(shù)據(jù)樣本與最優(yōu)近鄰之間的局部距離來(lái)優(yōu)化相似性計(jì)算的方法，從而得到高質(zhì)量的相似性矩陣[11]。假設(shè)數(shù)據(jù)樣本之間距離越小，兩者之間的相似性越大。再者，通過(guò)對(duì)p-Laplacian矩陣進(jìn)行秩約束獲得較為理想的近鄰分配，可以實(shí)現(xiàn)在最終矩陣中連通分量的數(shù)目等同于聚類數(shù)目，即每一個(gè)連通分量對(duì)應(yīng)一個(gè)簇。本文提出的基于局部相似性優(yōu)化的p-譜聚類算法，能夠同時(shí)實(shí)現(xiàn)相似性矩陣的計(jì)算以及對(duì)數(shù)據(jù)樣本的聚類兩個(gè)步驟，從而得出較優(yōu)的聚類結(jié)果[12]。本文使用此聚類算法分別對(duì)人工數(shù)據(jù)集和UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明，基于局部相似性優(yōu)化的p-譜聚類算法可以獲得較好的更加具有平衡性的聚類效果。

本文組織結(jié)構(gòu)如下：第2章介紹了p-Laplacian矩陣的概念，分析了p-Laplacian矩陣與齊格切之間的關(guān)系；第3章描述了局部相似性優(yōu)化方法的理論基礎(chǔ)，并提出了基于局部相似性優(yōu)化的p-譜聚類算法；第4章通過(guò)實(shí)驗(yàn)驗(yàn)證了基于局部相似性優(yōu)化的p-譜聚類算法的效果；最后對(duì)全文進(jìn)行總結(jié)并討論研究前景。

2 p-譜聚類

譜聚類的思想源于譜圖劃分理論。對(duì)于一個(gè)數(shù)據(jù)集，可以構(gòu)造一個(gè)無(wú)向加權(quán)圖G=(V,E)，其中頂點(diǎn)集合V表示數(shù)據(jù)樣本，權(quán)值集合E表示數(shù)據(jù)之間的相似性。假設(shè)A是頂點(diǎn)集合V的子集，則A的補(bǔ)集可以定義為對(duì)于A和Aˉ之間的圖劃分目標(biāo)函數(shù)可以表示如下[13]：

其中，wij表示頂點(diǎn)i和j之間的親和度。

為了產(chǎn)生更加均勻的聚類效果，Shi和Malik在此基礎(chǔ)上，進(jìn)一步提出圖劃分標(biāo)準(zhǔn)規(guī)范切（normalized cut，Ncut），表達(dá)式如下[14]：

對(duì)該目標(biāo)函數(shù)最小化意味著對(duì)類間數(shù)據(jù)樣本相似度最小化，同時(shí)，最大化類內(nèi)數(shù)據(jù)樣本的相似度，故此圖劃分標(biāo)準(zhǔn)能夠產(chǎn)生具有較好均衡性的劃分結(jié)果。但此目標(biāo)函數(shù)是投影矩陣的非線性函數(shù)，可能會(huì)存在局部極小值的問(wèn)題。

為了進(jìn)一步得到更具有平衡性的聚類效果，Cheeger等人提出齊格切圖劃分標(biāo)準(zhǔn)，Ccut的表達(dá)式如下[15]：

其中，|A|表示集合A中數(shù)據(jù)樣本的數(shù)目。齊格切通過(guò)最小化表達(dá)式（3）的值來(lái)得到無(wú)向圖的最優(yōu)圖劃分結(jié)果，即簇內(nèi)數(shù)據(jù)樣本之間的相似度最大，簇間數(shù)據(jù)樣本之間的相似度最小。但是根據(jù)Rayleigh商原則，計(jì)算無(wú)向圖齊格切的最優(yōu)劃分結(jié)果是一個(gè)NP-難題[16]。接下來(lái)，將通過(guò)在譜聚類算法中引入p-Laplacian算子來(lái)近似得到齊格切的最優(yōu)劃分結(jié)果。

Heigh等人定義了p-Laplacian算子的內(nèi)積形式，其表達(dá)式如下：

其中，p∈(1,2]；f是p-Laplacian矩陣的特征向量。

定理1對(duì)于任意p＞1以及頂點(diǎn)集合V的每一劃分A和Aˉ，都存在一個(gè)與p-Laplacian矩陣相關(guān)的函數(shù)Fp(f,A)滿足[17]：

表達(dá)式（5）可以被看作一個(gè)具有較強(qiáng)平衡性的圖劃分標(biāo)準(zhǔn)，并且可以進(jìn)一步得到：

由定理1可得，利用p-Laplacian算子，齊格切的最優(yōu)劃分可以在多項(xiàng)式時(shí)間內(nèi)被計(jì)算得到。因此Fp(f)的解決方法是齊格切的一個(gè)近似最優(yōu)解，以及最優(yōu)解可以通過(guò)p-Laplacian矩陣的譜分解獲得。

其中，λp是特征向量f對(duì)應(yīng)的特征值。

特別的，通過(guò)p-Laplacian矩陣的第二小特征向量以及設(shè)定合適的閾值，可以對(duì)無(wú)向圖進(jìn)行二路劃分。選擇最優(yōu)的閾值是能夠最小化對(duì)應(yīng)齊格切目標(biāo)函數(shù)值的。對(duì)于p-Laplacian矩陣的第二小特征向量，其閾值應(yīng)該滿足：

3 局部相似性優(yōu)化的p-譜聚類算法

3.1 局部相似性測(cè)度的優(yōu)化

聚類算法中，對(duì)數(shù)據(jù)樣本之間局部相似性的求解是一個(gè)復(fù)雜的過(guò)程。根據(jù)數(shù)據(jù)樣本集合X={x1,x2,…,xn}，首先定義一個(gè)數(shù)據(jù)樣本矩陣X∈Rn×d，然后對(duì)每個(gè)數(shù)據(jù)樣本確定其第k近鄰點(diǎn)。本文首先把數(shù)據(jù)樣本集合X中的數(shù)據(jù)樣本均看作xi的近鄰點(diǎn)，并使用歐氏距離來(lái)表示相似性[18]，局部相似性用sij表示。通常，如果兩個(gè)數(shù)據(jù)樣本之間的歐氏距離較小，則表示兩者之間具有較大的相似性另外，每個(gè)數(shù)據(jù)樣本均可看作數(shù)據(jù)樣本xi的相鄰點(diǎn)，且具有相同的局部相似性可看作每個(gè)數(shù)據(jù)樣本進(jìn)行近鄰分配的預(yù)操作。因此存在一種表示數(shù)據(jù)樣本之間局部相似性的方法，滿足下述表達(dá)式：

其中，si∈Rn×1表示向量，si的第j個(gè)元素表示數(shù)據(jù)樣本i和j之間的局部相似性sij；γ是正則化參數(shù)；定義是特征向量，的第j個(gè)元素表示然后表達(dá)式（9）可被進(jìn)一步轉(zhuǎn)化為向量形式，其描述如下：

對(duì)于每個(gè)數(shù)據(jù)樣本xi，可以使用表達(dá)式（9）為其分配近鄰點(diǎn)。因此，可以通過(guò)表達(dá)式（11），為所有數(shù)據(jù)樣本分配近鄰點(diǎn)：

在理想情況下對(duì)數(shù)據(jù)樣本進(jìn)行近鄰分配時(shí)，可以得到無(wú)向圖G中連通分量的數(shù)目精確地等于聚類數(shù)目c。然而，通常情況下在使用表達(dá)式（11）進(jìn)行近鄰分配時(shí)，對(duì)于任意的γ值，很難實(shí)現(xiàn)都能在理想情況下進(jìn)行分配。并且在大多數(shù)情況下，數(shù)據(jù)樣本集合中所有數(shù)據(jù)樣本只組成一個(gè)連通分量。為了實(shí)現(xiàn)在理想情況下進(jìn)行近鄰分配，表達(dá)式（11）的局部相似性應(yīng)該被約束，以便于近鄰分配能夠變成一個(gè)數(shù)據(jù)樣本自適應(yīng)的過(guò)程，使得連通分量的數(shù)目精確地等于聚類數(shù)目c。因?yàn)檫@種對(duì)局部相似性的結(jié)構(gòu)約束是根本性的難題，而且操作起來(lái)也是十分困難的，所以實(shí)現(xiàn)這種約束看起來(lái)像是一個(gè)不可實(shí)現(xiàn)的目標(biāo)。本文將提出一個(gè)新穎而又簡(jiǎn)單的算法來(lái)實(shí)現(xiàn)這個(gè)目標(biāo)。

近鄰分配后，S∈Rn×n被定義為相似性矩陣。假設(shè)每個(gè)頂點(diǎn)用函數(shù)fi∈Rc×1表示，則下述等式是正確的：

其中，F(xiàn)∈Rn×c，第i行等于fi。在圖論中被定義為拉普拉斯矩陣，Ds∈Rn×n被定義為度矩陣，其第i行對(duì)角元素等于

如果相似性矩陣S是非負(fù)的，則對(duì)應(yīng)拉普拉斯矩陣具有下述主要特性[20]。

定理2拉普拉斯矩陣Ls中，其特征值為0的數(shù)目c等于對(duì)應(yīng)無(wú)向圖G中連通分量的數(shù)目。

根據(jù)上述定理如果rank(Ls)=n-c，則表明近鄰分配可在理想情況下進(jìn)行，同時(shí)根據(jù)相似矩陣S能夠成功把數(shù)據(jù)樣本劃分到c個(gè)簇中，并且在聚類過(guò)程中沒(méi)有使用到k-means以及其他聚類算法。由定理2可知，可以把rank(Ls)=n-c看作約束條件添加到表達(dá)式（11）所描述的問(wèn)題中來(lái)實(shí)現(xiàn)理想情況下的近鄰分配。因此本文聚類算法可以解決下述表達(dá)式（13）需要解決的問(wèn)題，表達(dá)式描述如下：

假設(shè)σi(Ls)表示拉普拉斯矩陣Ls的第i小特征值，由于Ls是半正定矩陣，故σi(Ls)≥0。對(duì)于一個(gè)足夠大的數(shù)值λ，表達(dá)式（15）描述的問(wèn)題可用表達(dá)式（14）表示：

當(dāng)λ的值足夠大時(shí)，已知σi(Ls)≥0，表達(dá)式（14）只要使趨于零就可以得到最優(yōu)解S。

根據(jù)Ky Fan的理論分析[21]，有：

因此表達(dá)式（14）可以進(jìn)一步轉(zhuǎn)化為表達(dá)式（15），描述如下：

相對(duì)于原始表達(dá)式（13），表達(dá)式（15）更容易去解決。本文可以從下述選擇一種最優(yōu)的方法來(lái)解決問(wèn)題。

當(dāng)相似矩陣S不變時(shí)，則表達(dá)式（15）描述如下：

當(dāng)F不變時(shí)，則表達(dá)式（15）描述如下：

根據(jù)表達(dá)式（11），表達(dá)式（17）可轉(zhuǎn)化為：

在表達(dá)式（18）中，每一個(gè)i都是相互獨(dú)立的，因此對(duì)于i，可得下述表達(dá)式（19），描述如下：

由上述分析可知，得到相似矩陣S的算法1如下。

算法1計(jì)算相似矩陣S

輸入：數(shù)據(jù)樣本矩陣X∈Rn×d，聚類數(shù)目c，正則化參數(shù)γ，一個(gè)足夠大的數(shù)值λ。

輸出：具有c個(gè)連接部分的相似矩陣S∈Rn×n。

使用表達(dá)式（11）的最優(yōu)解對(duì)S進(jìn)行初始化；

如果不收斂，則：

（1）更新F。F由拉普拉斯矩陣的前c個(gè)最小特征值對(duì)應(yīng)的特征向量組成；

（2）對(duì)于每個(gè)i，使用表達(dá)式（19）的最優(yōu)解來(lái)更新相似矩陣S的第i行，其中di∈Rn×1為特征向量，其第j行元素等于

終止。

3.2 確定正則化參數(shù)γ的值

在實(shí)際情況下，由于正則化參數(shù)的取值范圍是從零到無(wú)窮大，故對(duì)其進(jìn)行訓(xùn)練確定值大小是非常困難的。本文提出一種有效的方法來(lái)間接確定正則化參數(shù)γ的值。

對(duì)于每個(gè)樣本數(shù)據(jù)i，表達(dá)式（13）中的目標(biāo)函數(shù)等價(jià)于表達(dá)式（10）中的目標(biāo)函數(shù)，表達(dá)式（10）的拉格朗日函數(shù)表達(dá)式（21）描述如下：

其中，η和βi≥0是拉格朗日乘子。

根據(jù)KKT條件[22]，可以證實(shí)最優(yōu)解si的表達(dá)式（22）可描述如下：

當(dāng)實(shí)際算法運(yùn)行時(shí)，如果進(jìn)一步考慮數(shù)據(jù)樣本的局部相似性，將會(huì)獲得較好的聚類效果。因此，一般情況下更傾向于只考慮xi的k個(gè)最近鄰，從而可以得到稀疏矩陣si；另一方面，聚類算法中使用稀疏矩陣還可以緩解設(shè)備的運(yùn)算負(fù)擔(dān)。

根據(jù)等式（22）和約束條件sTi1=1，有：

因此根據(jù)等式（23）和（24）可得關(guān)于γi的不等式如下：

在已知表達(dá)式（9）具有k個(gè)非零值的情況下，為了得到最優(yōu)解si，γi可以用表達(dá)式（26）表示，描述如下：

對(duì)于γ的值等于γ1,γ2,…,γn的平均值，也就是說(shuō)，γ可以用下述表達(dá)式（27）表示：

由于近鄰數(shù)k是一個(gè)整數(shù)并且具有明確的實(shí)際意義，相對(duì)于γ，k是更容易通過(guò)訓(xùn)練得到的。

3.3 局部相似性優(yōu)化的p-譜聚類算法

算法通過(guò)計(jì)算數(shù)據(jù)樣本與最優(yōu)近鄰之間的局部距離來(lái)優(yōu)化相似性矩陣，同時(shí)利用p-Laplacian矩陣的秩約束條件，使最終得到的矩陣中連通部分的數(shù)目精確等于聚類數(shù)目，從而進(jìn)一步實(shí)現(xiàn)聚類效果的優(yōu)化。它的主要思想是：首先根據(jù)優(yōu)化后的局部相似性測(cè)度方法來(lái)計(jì)算數(shù)據(jù)樣本之間的相似度，得到相似矩陣；接著計(jì)算p-Laplacian矩陣的特征值和特征向量，并遞歸地使用二分法進(jìn)行劃分來(lái)最優(yōu)化目標(biāo)函數(shù)；最終獲得更好的聚類結(jié)果。

算法2優(yōu)化的p-譜聚類算法

輸入：數(shù)據(jù)樣本集合X∈Rn×d，聚類數(shù)目c，正則化參數(shù)γ，一個(gè)足夠大的數(shù)值λ。

輸出：c個(gè)類C1,C2,…,Cc。

（1）根據(jù)算法1可得相似性矩陣S；

（2）初始化聚類C1=V,聚類數(shù)目s=1；

（3）重復(fù)步驟（3）～（7）；

（4）對(duì)每個(gè)類Ci(i=1,2,…,s)，最小化目標(biāo)函數(shù)Fp(f)；

（5）對(duì)非規(guī)范化矩陣或規(guī)范化矩陣求解最優(yōu)邊值，從而得到圖劃分標(biāo)準(zhǔn)齊格切判據(jù)的近似解；

（6）利用圖切判據(jù)的最小目標(biāo)函數(shù)對(duì)Ci(i=1,2,…,s)進(jìn)行分割；

（7）s?s+1；

（8）s==c時(shí)，循環(huán)結(jié)束，并輸出聚類結(jié)果；

（9）利用聚類結(jié)果進(jìn)一步得出衡量算法優(yōu)越性的Ncut值。

4 實(shí)驗(yàn)仿真與結(jié)果分析

本文為了分析基于局部相似性優(yōu)化的p-譜聚類算法的聚類效果，分別選取了4個(gè)人工數(shù)據(jù)集和兩個(gè)模式識(shí)別測(cè)試數(shù)據(jù)集（簡(jiǎn)稱UCI）進(jìn)行實(shí)驗(yàn)，并與原p-譜聚類算法的聚類效果進(jìn)行對(duì)比，從而體現(xiàn)基于局部相似性優(yōu)化的p-譜聚類算法的優(yōu)越性。實(shí)驗(yàn)過(guò)程中為了方便分析算法的優(yōu)越性，p值始終保持不變。實(shí)驗(yàn)的計(jì)算機(jī)環(huán)境為：Intel Core i5-2450M 2.5 GHz CPU，內(nèi)存6 GB,Windows 8.1 64位操作系統(tǒng)，運(yùn)行平臺(tái)為Matlab R2014a。

人工數(shù)據(jù)集是根據(jù)聚類需要進(jìn)行人工合成的，一般情況下都具有相對(duì)復(fù)雜或者較為獨(dú)特的數(shù)據(jù)結(jié)構(gòu)，例如凸形結(jié)構(gòu)、流形結(jié)構(gòu)和多維結(jié)構(gòu)等。一般的聚類算法往往都只能解決其中的少數(shù)問(wèn)題，人工數(shù)據(jù)集對(duì)算法的要求非常嚴(yán)格，具有較強(qiáng)的挑戰(zhàn)性。因此，可以通過(guò)對(duì)比原p-譜聚類算法和基于局部相似性優(yōu)化的p-譜聚類算法在人工數(shù)據(jù)集上的聚類效果來(lái)分析后者的優(yōu)越性與有效性。本文選取的4個(gè)人工數(shù)據(jù)集為Twomoon、Threecircle、Smile、Fourline，其特征如表1所示，其可視化分布如圖1所示。

Table 1 Characteristics of artificial data sets表1 人工數(shù)據(jù)集及其數(shù)據(jù)特征

為了進(jìn)一步驗(yàn)證基于局部相似性優(yōu)化的p-譜聚類算法的優(yōu)越性，從UCI數(shù)據(jù)集庫(kù)選擇兩個(gè)真實(shí)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。本文選取的兩個(gè)數(shù)據(jù)集都是具有明確分類結(jié)果的，其具體特征如表2所示。

Table 2 Characteristics of UCI data sets表2 UCI數(shù)據(jù)集及數(shù)據(jù)特征

以上分別對(duì)4個(gè)人工數(shù)據(jù)集Twomoon、Threecircle、Smile、Fourline和兩個(gè)UCI數(shù)據(jù)集Wine和USPS進(jìn)行了描述和分析。接下來(lái)，分別使用原p-譜聚類算法和基于局部相似性優(yōu)化的p-譜聚類算法對(duì)人工數(shù)據(jù)集和UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。為了驗(yàn)證算法的一般性，首先對(duì)4個(gè)人工數(shù)據(jù)集進(jìn)行聚類，兩種聚類算法的效果如圖2所示，（a）表示數(shù)據(jù)集Twomoon的聚類效果，（b）表示數(shù)據(jù)集Threecircle的聚類效果，（c）表示數(shù)據(jù)集Smile的聚類效果，（d）表示數(shù)據(jù)集Fourline的數(shù)據(jù)效果。

從圖2中可以看出，對(duì)于人工數(shù)據(jù)集，相對(duì)原p-譜聚類算法，基于局部相似性優(yōu)化的p-譜聚類算法可以獲得更好的聚類效果。

Fig.1 Distribution of artificial data sets圖1 人工數(shù)據(jù)集的分布

Table 3 Ncutvalue of two algorithms on artificial data sets表3 兩種算法在人工數(shù)據(jù)集得出的Ncut值

在本文實(shí)驗(yàn)中，根據(jù)第2章中圖劃分標(biāo)準(zhǔn)規(guī)范切和最終的聚類結(jié)果可以得出Ncut值，其大小能夠作為衡量算法優(yōu)越性的標(biāo)準(zhǔn)，即Ncut值越小，則算法越具有優(yōu)越性、有效性。表3給出了兩種聚類算法分別在4個(gè)人工數(shù)據(jù)集Twomoon、Threecircle、Smile、Fourline的Ncut值。

表3中，第一行數(shù)據(jù)表示原p-譜聚類算法在4個(gè)人工數(shù)據(jù)集上聚類后，得出的Ncut值，第二行數(shù)據(jù)表示基于局部相似性優(yōu)化的p-譜聚類算法在4個(gè)人工數(shù)據(jù)集上聚類后，得出的Ncut值。從表中可以看出，對(duì)于人工數(shù)據(jù)集，后者的Ncut值明顯小于前者，故基于局部相似性優(yōu)化的p-譜聚類算法產(chǎn)生更好的聚類效果。

通過(guò)上述對(duì)人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)與分析，驗(yàn)證了本文的譜聚類算法的有效性。接下來(lái)，將使用兩種聚類算法進(jìn)一步對(duì)兩個(gè)UCI數(shù)據(jù)集Wine和USPS進(jìn)行聚類。

表4給出了兩種聚類算法分別在兩個(gè)UCI數(shù)據(jù)集Wine和USPS上的Ncut值。

Table 4 Ncutvalue of two algorithms on UCI data sets表4 兩種算法在UCI數(shù)據(jù)集得出的Ncut值

Fig.2 Clustering results of two algorithms on artificial data sets圖2 兩種聚類算法在人工數(shù)據(jù)集的聚類效果

表4中，第一行數(shù)據(jù)表示原p-譜聚類算法在兩個(gè)UCI數(shù)據(jù)集上聚類后，得出的Ncut值，第二行數(shù)據(jù)表示基于局部相似性優(yōu)化的p-譜聚類算法在兩個(gè)UCI數(shù)據(jù)集上聚類后，得出的Ncut值。從表中可以看出，對(duì)于UCI數(shù)據(jù)集，后者的Ncut值明顯小于前者，故基于局部相似性優(yōu)化的p-譜聚類算法產(chǎn)生更好的聚類效果。

經(jīng)過(guò)上述實(shí)驗(yàn)仿真和結(jié)果分析可知，基于局部相似性優(yōu)化的p-譜聚類算法具有更好的優(yōu)越性和有效性。

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

本文提出了一種基于局部相似性優(yōu)化的p-譜聚類算法。該算法通過(guò)數(shù)據(jù)樣本的自適應(yīng)和最優(yōu)近鄰之間的局部距離來(lái)優(yōu)化相似性測(cè)度的計(jì)算方法，同時(shí)通過(guò)引入p-Laplacian矩陣的秩約束，可以得到聚類過(guò)程中無(wú)向圖G中連通分量的數(shù)目精確地等于聚類數(shù)目，從而有效地解決了原p-譜聚類算法中不能充分挖掘數(shù)據(jù)集的局部結(jié)構(gòu)信息和相似性矩陣的計(jì)算與數(shù)據(jù)樣本的聚類分別在兩個(gè)不同的步驟中實(shí)現(xiàn)，導(dǎo)致有可能得不到最優(yōu)聚類效果的問(wèn)題。為了驗(yàn)證基于局部相似性優(yōu)化的p-譜聚類算法的優(yōu)越性和有效性，在本文實(shí)驗(yàn)中，采用了4個(gè)人工數(shù)據(jù)集和兩個(gè)UCI數(shù)據(jù)集分別進(jìn)行實(shí)驗(yàn)，并且將聚類效果與原p-譜聚類算法的聚類效果進(jìn)行了對(duì)比。從實(shí)驗(yàn)仿真與結(jié)果分析中可知，基于局部相似性優(yōu)化的p-譜聚類算法具有更好的優(yōu)越性和有效性。接下來(lái)的工作是通過(guò)分析研究特征向量的結(jié)構(gòu)信息來(lái)自動(dòng)確定數(shù)據(jù)集的聚類數(shù)目，從而獲得更好的聚類效果。

[1]Johnson S C.Hierarchical clustering schemes[J].Psychometrika,1967,32(3):241-254.

[2]MacQueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability,Berkeley,1965.Berkeley:University of California Press,1967:281-297.

[3]Benhur A.Support vector clustering[J].Journal of Machine Learning Research,2002,2(2):125-137.

[4]Nie Feiping,Xu Dong,Li Xuelong.Initialization independent clustering with actively self-training method[J].IEEE Transactions on Systems,Man and Cybernetics:Part B,2012,42(1):17-27.

[5]Cai Xiao,Nie Feiping,Huang Heng.Multi-viewK-means clustering on big data[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence,Beijing,Aug 3-9,2013.Menlo Park:AAAI,2013:2598-2604.

[6]Jia Hongjie,Ding Shifei,Xu Xinzheng,et al.The latest research progress on spectral clustering[J].Neural Computing&Applications,2014,24(7/8):1477-1486

[7]Zhang Xianchao,You Quanzeng.An improved spectral clustering algorithm based on random walk[J].Frontiers of Computer Science in China,2011,5(3):268-278.

[8]Jia Hongjie,Ding Shifei,Meng Lingheng,et al.A densityadaptive affinity propagation clustering algorithm based on spectral dimension reduction[J].Neural Computing&Applications,2014,25(7/8):1557-1567.

[9]Bühler T,Hein M.Spectral clustering based on the graphp-Laplacian[C]//Proceedings of the 26th Annual International Conference on Machine Learning,Montreal,Jun 14-18,2009.New York:ACM,2009:81-88.

[10]Zelnik-Manor L,Perona P.Self-tuning spectral clustering[C]//Proceedings of the 2004 Conference on Neural Information Processing Systems,Vancouver,Dec 13-18,2004:1601-1608.

[11]Jia Hongjie,Ding Shifei,Du Mingjing.Self-tuningp-spectral clustering based on shared nearest neighbors[J].Cognitive Computation,2015,7(5):622-632.

[12]Nie Feiping,Wang Xiaoqian,Huang Heng.Clustering and projected clustering with adaptive neighbors[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,Aug 24-27,2014.New York:ACM,2014:977-986.

[13]Donath W E,Hoffman A J.Lower bounds for the partitioning of graphs[J].IBM Journal of Research&Development,1973,17(5):420-425.

[14]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2000,22(8):888-905.

[15]Amghibech S.Bounds for the largestp-Laplacian eigenvalue for graphs[J].Discrete Mathematics,2006,306(21):2762-2771.

[16]Ding Shifei,Jia Hongjie,Zhang Liwen,et al.Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J].Neural Computing&Applications,2014,24(1):211-219.

[17]Hagen L,Kahng A.Fast spectral methods for ratio cut partitioning and clustering[C]//Proceedings of the 1991 International Conference on Computer-Aided Design,Santa Clara,Nov 11-14,1991.Piscataway:IEEE,1991:10-13.

[18]Ding Shifei,Jia Hongjie,Du Mingjing,et al.p-spectral clustering based on neighborhood attribute granulation[C]//Proceedings of the 9th IFIP TC 12 International Conference on Intelligent Information Processing,Melbourne,Nov 18-21,2016.Berlin,Heidelberg:Springer,2016:50-58.

[19]Shi Jianbo,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[20]Hein M,Audibert J Y,Luxburg U V.Graph Laplacians and their convergence on random neighborhood graphs[J].Journal of Machine Learning Research,2007,8(9):1325-1370.

[21]Ding Shifei,Qi Bingjuan,Jia Hongjie,et al.Research of semi-supervised spectral clustering based on constraints expansion[J].Neural Computing&Applications,2012,22(1):405-410.

[22]Boyd S,Vandenberghe L.Convex optimization[M].Cambridge:Cambridge University Press,2004.