改進(jìn)地標(biāo)點(diǎn)采樣的加速譜聚類算法

徐航帆，劉 叢，唐堅(jiān)剛，彭敦陸

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200082)

現(xiàn)今世界數(shù)據(jù)量爆炸增長(zhǎng)，對(duì)大數(shù)據(jù)進(jìn)行高效地分析將在各行各業(yè)起到關(guān)鍵性作用。聚類分析[1]是一種無(wú)監(jiān)督學(xué)習(xí)方法，也是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中一個(gè)重要的研究方向。聚類是指將數(shù)據(jù)在不需要先驗(yàn)知識(shí)的情況下根據(jù)某種相似度劃分為多個(gè)簇的過(guò)程。傳統(tǒng)的聚類算法，例如K-means算法[2]具有簡(jiǎn)單高效的特點(diǎn)，在球形結(jié)構(gòu)的數(shù)據(jù)上有著較高的聚類精確度。但是，其缺乏處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)的能力[3]。當(dāng)樣本空間為非凸時(shí)，K-means算法往往達(dá)不到理想的效果[4]。

為了能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解，研究人員開始研究新型的聚類算法，也被稱為譜聚類[5]算法(Spectral Clustering Algorithm，SC)。譜圖理論[6]是該算法的理論基礎(chǔ)，其本質(zhì)是將聚類問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題。近幾十年來(lái)，研究人員提出了多種譜聚類算法，例如Ratio Cut算法[7]和Normalized Cut算法[8]。這兩種算法將數(shù)據(jù)轉(zhuǎn)換為基于相似性的加權(quán)無(wú)向圖， 然后通過(guò)圖優(yōu)化算法進(jìn)行求解。文獻(xiàn)[9]提出了NJW算法，該算法是一種應(yīng)用比較廣泛的譜聚類算法。然而譜聚類算法在面對(duì)大規(guī)模數(shù)據(jù)集時(shí)，其構(gòu)建相似度矩陣所需的空間復(fù)雜度(O(n2))和拉普拉斯矩陣特征分解所需的時(shí)間復(fù)雜度(O(n3))十分龐大，產(chǎn)生的計(jì)算成本將難以承受。

為了克服譜聚類的在大數(shù)據(jù)集上的可擴(kuò)展性問(wèn)題，一些加速譜聚類的算法被提出來(lái)，其中最自然的想法就是降低拉普拉斯矩陣的特征分解時(shí)間。2004年，文獻(xiàn)[10]采用經(jīng)典的Nystr?m[11]方法有效地計(jì)算了特征分解的近似解，從原始數(shù)據(jù)集中隨機(jī)選取p個(gè)樣本，然后計(jì)算相似度矩陣W∈p×p，根據(jù)這個(gè)矩陣計(jì)算特征分解來(lái)近似表示原始相似度矩陣的特征分解。文獻(xiàn)[12]提出了可擴(kuò)展的Nystr?m方法，通過(guò)隨機(jī)低秩矩陣近似算法大大減少了算法的運(yùn)行時(shí)間。文獻(xiàn)[13]提出了一種自適應(yīng)采樣的方法，改進(jìn)了Nystr?m譜聚類算法的聚類效果。

后來(lái)，文獻(xiàn)[14]提出了一種通過(guò)地標(biāo)點(diǎn)表示的加速譜聚類算法(Landmark-based Spectral Clustering，LSC)，其效果優(yōu)于前述算法聚類。該算法中，需首先對(duì)原始數(shù)據(jù)進(jìn)行采樣，選取p個(gè)地標(biāo)點(diǎn)，通過(guò)p個(gè)點(diǎn)與原始n個(gè)數(shù)據(jù)點(diǎn)成對(duì)相似度來(lái)構(gòu)建相似度矩陣Z∈n×p。然后，利用稀疏編碼技術(shù)[15]調(diào)整矩陣Z，使其成為稀疏相似度矩陣[16]，從而將計(jì)算特征分解的時(shí)間復(fù)雜度降低為O(p3+p2n)。文獻(xiàn)[14]提出了兩種采樣算法：(1)隨機(jī)采樣選取地標(biāo)點(diǎn)；(2)K-means算法采樣選取聚類中心作為地標(biāo)點(diǎn)。經(jīng)實(shí)驗(yàn)證明，K-means采樣在大部分?jǐn)?shù)據(jù)集上的最終聚類精確度比隨機(jī)采樣要高，但K-means采樣選取的地標(biāo)點(diǎn)需重復(fù)讀取數(shù)據(jù)，時(shí)間復(fù)雜度大。隨機(jī)采樣選取地標(biāo)點(diǎn)隨機(jī)性較大，地標(biāo)點(diǎn)有時(shí)往往選取的不夠均勻，效果較差，文獻(xiàn)[17]提出了一種基于Pagerank算法選取地標(biāo)點(diǎn)的方法，通過(guò)構(gòu)建數(shù)據(jù)點(diǎn)之間成對(duì)相似度矩陣W∈p×p選取地標(biāo)點(diǎn)，并將該方法通過(guò)并行計(jì)算框架實(shí)現(xiàn)，有效減少了運(yùn)行時(shí)間，獲得了更好的聚類精度。但是該算法的空間復(fù)雜度(O(n2))較大，面對(duì)大型數(shù)據(jù)集時(shí)需要更多的計(jì)算節(jié)點(diǎn)，成本較大。文獻(xiàn)[18]提出了一種快速地標(biāo)點(diǎn)選取算法，有效保留了數(shù)據(jù)的原始信息，在聚類精度和時(shí)間復(fù)雜度之間取得較好的平衡，但該方法仍會(huì)受到離群地標(biāo)點(diǎn)的影響。

綜上所述，基于地標(biāo)點(diǎn)的加速譜聚類算法存在以下兩個(gè)問(wèn)題：(1)地標(biāo)點(diǎn)的選取難以在時(shí)間空間成本和最終聚類精度之間保持有效平衡；(2)聚類結(jié)果易受分布不均勻地標(biāo)點(diǎn)和離群地標(biāo)點(diǎn)的影響。

針對(duì)上述問(wèn)題，本文提出了改進(jìn)地標(biāo)點(diǎn)采樣(Improved Landmark Selection，ILS)的加速譜聚類算法(LSC-ILS)。該方法通過(guò)隨機(jī)多組待選地標(biāo)點(diǎn)集，根據(jù)地標(biāo)點(diǎn)之間相似度標(biāo)準(zhǔn)差信息，選擇分布最均勻的地標(biāo)點(diǎn)集，結(jié)合地標(biāo)點(diǎn)周圍原始數(shù)據(jù)點(diǎn)局部密度分布信息，去除周圍原始點(diǎn)局部密度分布較小的離群地標(biāo)點(diǎn)。實(shí)驗(yàn)證明此算法能用較少的時(shí)間成本獲得較高的聚類精確度,在時(shí)間空間成本和聚類精度上取得較好的平衡。

1 相關(guān)工作

1.1 譜聚類

給定數(shù)據(jù)集X={x1,x2,…,xn}∈m×n，其中n表示樣本個(gè)數(shù)，m表示數(shù)據(jù)維度。譜聚類首先根據(jù)數(shù)據(jù)點(diǎn)之間成對(duì)相似度矩陣W∈n×n構(gòu)造無(wú)向G=(V,E)，其中W中第i行第j個(gè)元素wij≥ 0表示點(diǎn)xi和點(diǎn)xj之間的相似度。X中的樣本點(diǎn)對(duì)應(yīng)V的頂點(diǎn)，任意兩點(diǎn)之間權(quán)重由W給出。度矩陣D是由相似度矩陣W的行和組成的對(duì)角線矩陣,如式(1)所示。

(1)

L=D-W被稱為拉普拉斯矩陣。然后譜聚類對(duì)拉普拉斯矩陣進(jìn)行特征分解，并對(duì)前k個(gè)最小特征值對(duì)應(yīng)的特征向量組成的點(diǎn)進(jìn)行聚類(一般利用K-means聚類算法)，作為最終聚類結(jié)果?；A(chǔ)譜聚類算法流程如下文所示。

輸入：n個(gè)數(shù)據(jù)點(diǎn)x1,x2,x3,…,xn∈m；聚類數(shù)目k。

輸出：聚類結(jié)果標(biāo)簽。

步驟1根據(jù)數(shù)據(jù)點(diǎn)之間相似度構(gòu)造相似度矩陣W∈n×n，根據(jù)式(2)計(jì)算度矩陣D∈n×n；

步驟2根據(jù)拉普拉斯矩陣L=D-1/2(D-W)D-1/2計(jì)算前k個(gè)最小特征值對(duì)應(yīng)的特征向量，組成點(diǎn)集Q={q1,q2,…,qk}；

步驟3Q的每一行視作一個(gè)點(diǎn)，通過(guò)K-means算法得到最終聚類結(jié)果。

由于傳統(tǒng)譜聚類算法空間復(fù)雜度(O(n2))和時(shí)間復(fù)雜度(O(n3))，很難將其擴(kuò)展到大規(guī)模數(shù)據(jù)集的應(yīng)用。因此本文提出了擴(kuò)展到大規(guī)模數(shù)據(jù)集上的加速譜聚類的算法。

1.2 基于地標(biāo)點(diǎn)的加速譜聚類算法

基于地標(biāo)點(diǎn)的加速譜聚類算法是一種在大規(guī)模數(shù)據(jù)集上加速譜聚類的方法。該算法通過(guò)矩陣分解技術(shù)找到一組點(diǎn)，通過(guò)這組點(diǎn)與原始點(diǎn)之間的關(guān)系來(lái)近似表示原始數(shù)據(jù)。X={x1,x2,…,xn}∈m×n是原始數(shù)據(jù)矩陣，矩陣分解技術(shù)就是找到p個(gè)m維的數(shù)據(jù)點(diǎn)集U∈m×p和與原始點(diǎn)的關(guān)系矩陣Z∈p×n，通過(guò)式(2)近似表示原始數(shù)據(jù)矩陣X。

X≈UZ

(2)

式中，矩陣U為地標(biāo)點(diǎn)集，每一列為每一個(gè)地標(biāo)點(diǎn)，這些地標(biāo)點(diǎn)為原始數(shù)據(jù)點(diǎn)的代表點(diǎn)。對(duì)于任意一個(gè)數(shù)據(jù)點(diǎn)xi∈X，它的近似點(diǎn)φi可以通過(guò)式(3)表示。

(3)

式中，uj是U中第j列向量，表示第j個(gè)地標(biāo)點(diǎn)；zji是矩陣Z中第j行第i列的元素。如果uj不在點(diǎn)xi最近的r(≤p)個(gè)鄰域中，則zji置為0，因此Z就變成了稀疏表示矩陣。通過(guò)U(i)∈m×r表示U的子矩陣，由xi的r個(gè)最近的地標(biāo)點(diǎn)組成。zji可由式(4)計(jì)算。

(4)

K(·)是和函數(shù)，通常使用高斯核函數(shù)

(5)

根據(jù)矩陣Z計(jì)算相似度矩陣W，如式(6)

W=(D-1/2Z)T(D-1/2Z)

(6)

其中，D是一個(gè)p×p對(duì)角矩陣，由Z的行和構(gòu)成。D-1/2Z的奇異值分解(Singular Value Decomposition，SVD)如下

D-1/2Z=AΣBT

(7)

其中，Σ=diag(?1,?2,…,?p)，?1≥?2≥…≥?p≥0是D-1/2Z的奇異值；A={a1,a2,…,ap}∈p×p是左奇異向量矩陣；B={b1,b2,…,bp}∈n×p是右奇異向量矩陣；?i2為特征值。很明顯，B的列向量為W的特征向量，A的列向量為(D-1/2Z)(D-1/2Z)T的特征向量。

由于矩陣(D-1/2Z)(D-1/2Z)T的維度是p×p，可以先計(jì)算A，只需要O(p3)，B因此可以由下式(8)計(jì)算。

BT=∑-1AT(D-1/2Z)

(8)

由于p?n，所以拉普拉斯矩陣的分解時(shí)間就從O(n3)減少到O(p3+p2n)，存儲(chǔ)空間由O(n2)減少到O(np)，大幅減少了譜聚類所需的時(shí)間和空間。

2 改進(jìn)地標(biāo)點(diǎn)采樣的加速譜聚類算法

地標(biāo)點(diǎn)的選取作為基于地標(biāo)點(diǎn)的加速譜聚類算法的最關(guān)鍵部分，在很大程度上決定了最后聚類結(jié)果。隨機(jī)采樣的方法在大規(guī)模數(shù)據(jù)上選取的地標(biāo)點(diǎn)易集中于某一局部區(qū)域，分布不均勻。K-means采樣算法存在著反復(fù)讀取數(shù)據(jù)，時(shí)間消耗較大的問(wèn)題；Pagerank采樣算法需先構(gòu)造數(shù)據(jù)點(diǎn)之間成對(duì)相似度矩陣，空間復(fù)雜度較大。此外，聚類結(jié)果也易受離群地標(biāo)點(diǎn)的影響。針對(duì)以上問(wèn)題，本文提出了改進(jìn)地標(biāo)點(diǎn)采樣的加速譜聚類算法。該算法首先多次隨機(jī)采樣選取多組地標(biāo)點(diǎn)集，計(jì)算各組地標(biāo)點(diǎn)之間相似度的標(biāo)準(zhǔn)差(Standard Deviation，SD)，通過(guò)標(biāo)準(zhǔn)差來(lái)衡量地標(biāo)點(diǎn)的均勻程度；然后計(jì)算地標(biāo)點(diǎn)周圍原始數(shù)據(jù)點(diǎn)密度分布來(lái)衡量地標(biāo)點(diǎn)的代表性，去除代表性較差的離群地標(biāo)點(diǎn)，進(jìn)一步在不影響聚類精度的情況下減少時(shí)間復(fù)雜度。

2.1 改進(jìn)的地標(biāo)點(diǎn)采樣算法

給定數(shù)據(jù)集X={x1,x2,…,xn}∈m×n，其中n表示樣本個(gè)數(shù)，m表示數(shù)據(jù)維度。首先通過(guò)均勻隨機(jī)采樣，從原始數(shù)據(jù)集中進(jìn)行c次地標(biāo)點(diǎn)采樣，每次采樣p個(gè)地標(biāo)點(diǎn)，形成c個(gè)地標(biāo)點(diǎn)集，其中第i個(gè)地標(biāo)點(diǎn)集表示為Ui={u1,u2,…,up}∈m×p。為了選擇最佳的地標(biāo)點(diǎn)集，通過(guò)地標(biāo)點(diǎn)集Ui中點(diǎn)之間成對(duì)相似度矩陣Si∈p×p的行標(biāo)準(zhǔn)差之和來(lái)衡量地標(biāo)點(diǎn)的分布均勻程度。其中，點(diǎn)uj與點(diǎn)ul之間相似度計(jì)算如式(9)所示。

(9)

其中，K(·)是核函數(shù)，通常由式(5)計(jì)算。

第j行的行標(biāo)準(zhǔn)差計(jì)算如下

(10)

(11)

各個(gè)地標(biāo)點(diǎn)集的行標(biāo)準(zhǔn)差之和即為SD={SD1,SD2,…,SDc},其中max(SD)對(duì)應(yīng)的地標(biāo)點(diǎn)集Ui={u1,u2,…,up}為最佳地標(biāo)點(diǎn)集。

接下來(lái)，計(jì)算各個(gè)地標(biāo)點(diǎn)的局部密度權(quán)重，通過(guò)局部密度權(quán)重反映地標(biāo)點(diǎn)周圍原始數(shù)據(jù)點(diǎn)的分布情況。局部密度權(quán)重越大表示地標(biāo)點(diǎn)周圍數(shù)據(jù)點(diǎn)分布越密集，地標(biāo)點(diǎn)就越重要，局部密度權(quán)重越小表示地標(biāo)點(diǎn)周圍數(shù)據(jù)點(diǎn)分布越稀疏，地標(biāo)點(diǎn)就越不重要；然后去除密度權(quán)重小于閾值γ的地標(biāo)點(diǎn)(Landmarks Reduction，LR)。具體步驟為：首先構(gòu)造地標(biāo)點(diǎn)與原始數(shù)據(jù)點(diǎn)之間的相似度矩陣Z′∈p×n,z′ji表示第j個(gè)地標(biāo)點(diǎn)與原始數(shù)據(jù)點(diǎn)xi之間的相似度，計(jì)算式為

(12)

其中，K(·)是核函數(shù)，通常由式(5)計(jì)算；然后計(jì)算每個(gè)地標(biāo)點(diǎn)的密度權(quán)重。地標(biāo)點(diǎn)uj權(quán)重dj計(jì)算如下

(13)

其中，count(z′ji>s,z′ji∈z′j)表示原始樣本中與地標(biāo)點(diǎn)uj相似度大于s(0～1)的數(shù)量；最后根據(jù)閾值γ(0～1)，選出權(quán)重dj>γ的p′個(gè)地標(biāo)點(diǎn)。

2.2 改進(jìn)地標(biāo)點(diǎn)采樣的加速譜聚類算法流程

圖1 LSC-ILS流程圖

圖1為改進(jìn)地標(biāo)點(diǎn)采樣的加速譜聚類算法流程，其具體流程如下文所示。

輸入：原始數(shù)據(jù)集X={x1,x2,…,xn}∈m×n，地標(biāo)點(diǎn)數(shù)量p；系數(shù)相似度矩陣近鄰個(gè)數(shù)r；地標(biāo)點(diǎn)集個(gè)數(shù)c；閾值s和γ；聚類數(shù)目k。

輸出：聚類結(jié)果標(biāo)簽。

步驟1對(duì)原始數(shù)據(jù)集進(jìn)行c次隨機(jī)采樣選取c個(gè)地標(biāo)點(diǎn)集U={U1,U2,U3,…,Ui,…,Uc}；

步驟2根據(jù)式(9)計(jì)算每個(gè)地標(biāo)點(diǎn)集的相似度矩陣Si；

步驟3根據(jù)式(10)和式(11)計(jì)算出每個(gè)地標(biāo)點(diǎn)集相似度矩陣的標(biāo)準(zhǔn)差SDi；

步驟4計(jì)算max(SD)，輸出其對(duì)應(yīng)的地標(biāo)點(diǎn)集；

步驟5根據(jù)式(12)計(jì)算地標(biāo)點(diǎn)密度權(quán)重dj；

步驟6選出閾值dj>γ的p′個(gè)地標(biāo)點(diǎn)；

步驟7根據(jù)式(5)計(jì)算地標(biāo)點(diǎn)與原始數(shù)據(jù)點(diǎn)之間的稀疏相似度矩陣Z；

步驟8計(jì)算(D-1/2Z)(D-1/2Z)T的前k個(gè)最小特征值對(duì)應(yīng)的特征向量A={a1,a2,…,ap′}；

步驟9根據(jù)式(7)計(jì)算B={b1,b2,…,bp′}；

步驟10B的每一行視作一個(gè)點(diǎn)，通過(guò)K-means算法得到最終聚類結(jié)果標(biāo)簽ri∈R。

2.3 時(shí)間復(fù)雜度和空間復(fù)雜度分析

本節(jié)是對(duì)本文算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。數(shù)據(jù)樣本數(shù)量為n，采樣次數(shù)為c次，每次采樣地標(biāo)點(diǎn)數(shù)量為p，最后輸出地標(biāo)點(diǎn)數(shù)量為d，其余算法采樣地標(biāo)點(diǎn)數(shù)量為p。

采用隨機(jī)采樣選取c組待選地標(biāo)點(diǎn)的時(shí)間復(fù)雜度可以忽略不記，構(gòu)建地標(biāo)點(diǎn)相似度矩陣需要O(cp2)的時(shí)間復(fù)雜度，需要O(cp2)空間復(fù)雜度。根據(jù)地標(biāo)點(diǎn)與原始點(diǎn)之間的相似度矩陣計(jì)算地標(biāo)點(diǎn)密度權(quán)重以及構(gòu)建稀疏相似度矩陣需要O(pn)時(shí)間復(fù)雜度。計(jì)算稀疏相似度矩陣需要O(pn2)，根據(jù)稀疏相似度矩陣計(jì)算左奇異向量需要O(d3)的時(shí)間復(fù)雜度，計(jì)算右奇異向量需要O(d2n)的時(shí)間復(fù)雜度。

表1 時(shí)間復(fù)雜度分析 (p?n,d

表1是4種算法的時(shí)間復(fù)雜度分析，由表1可以看出本文算法的時(shí)間復(fù)雜度總和最小。

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

為了驗(yàn)證本文算法的有效性，進(jìn)行實(shí)驗(yàn)分析，從算法的聚類精確度和運(yùn)行時(shí)間兩指標(biāo)進(jìn)行評(píng)估。本文選取原始譜聚類[5](記為SC)、Nystr?m 近似譜聚類[11](記為Nystr?m)、基于隨機(jī)采樣的地標(biāo)點(diǎn)譜聚類[13](記為L(zhǎng)SC-R)和基于K均值中心的地標(biāo)點(diǎn)譜聚類[13](記為 LSC-K)與本文算法(記為L(zhǎng)SC-ILS)進(jìn)行對(duì)比。為了證明本文提出的去除地標(biāo)點(diǎn)算法(LR)有效性，本文將LSC-R和LSC-K分別結(jié)合LR算法(記為L(zhǎng)SC-R-LR和LSC-K-LR)與原始LSC-R和LSC-K算法進(jìn)行實(shí)驗(yàn)比較。

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

為了驗(yàn)證本文算法面對(duì)大規(guī)模數(shù)據(jù)集的性能，選擇兩個(gè)大規(guī)模UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。第一個(gè)為MINIST，該數(shù)據(jù)集是一個(gè)手寫數(shù)字的數(shù)據(jù)集，共有70 000個(gè)樣本，共10類，每個(gè)樣本被視為784維數(shù)據(jù)。第二個(gè)為Pendigits，該數(shù)據(jù)集也是一個(gè)手寫數(shù)字的數(shù)據(jù)集，包含了44個(gè)作者寫的250個(gè)手寫樣例，經(jīng)過(guò)處理得到10 992個(gè)樣本，每個(gè)對(duì)象有16個(gè)屬性，共被分成10類。

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

為了評(píng)價(jià)聚類有效性(聚類算法對(duì)數(shù)據(jù)進(jìn)行劃分的正確程度)，本節(jié)采取了兩個(gè)指標(biāo)，即聚類精確性(Accuracy，ACC)[19]和標(biāo)準(zhǔn)化互信息(Normalized Mutual Information，NMI)[20]進(jìn)行數(shù)值分析。實(shí)驗(yàn)在英特爾Core i3-8100@3.6 GHz，8 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行，代碼在MATLAB環(huán)境下編寫。

給定數(shù)據(jù)點(diǎn)xi，令ri∈R和fi∈F分別為聚類結(jié)果標(biāo)簽和預(yù)定義標(biāo)簽，ACC定義如下

(14)

式中，n是樣本數(shù)量；δ(x,y)表示若x=y，為1，否則為0。map(ri)是聚類結(jié)果標(biāo)簽ri映射到數(shù)據(jù)語(yǔ)料庫(kù)中的真正標(biāo)簽，采用Kuhn-Munkres算法[21]可以找到最佳映射。

MI(R，F(xiàn))互信息表示為

(15)

式中，p(ri)和p(fj)是從數(shù)據(jù)集中任意選擇的樣本屬于標(biāo)簽ri和標(biāo)簽fj的概率；p(ri,fj)是從數(shù)據(jù)集中任意選擇的樣本屬于簇ri和fj的聯(lián)合概率。NMI標(biāo)準(zhǔn)化互信息計(jì)算如下

(16)

H(R)=-∑ri∈Rp(ri)logp(ri)

(17)

式中，H(R)是聚類結(jié)果R的熵，表示R中變量的混亂程度，R中變量越混亂，H(R)的值越接近1；反之H(R)的值越接近0。很明顯ACC指標(biāo)和NMI指標(biāo)取值范圍都是[0,1]，越接近1表示聚類結(jié)果越精確。

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

7種聚類算法在MINIST和Pendigits上的聚類結(jié)果如表2和表3所示，聚類指標(biāo)分別為聚類精確度(ACC)和標(biāo)準(zhǔn)化互信息(NMI)。為了比較的公平性，6種加速譜聚類算法的抽樣數(shù)均為1 000，基于地標(biāo)點(diǎn)的加速譜聚類算法稀疏相似度矩陣的最近鄰個(gè)數(shù)r為5。其中，本文算法中s參數(shù)，γ參數(shù)和c參數(shù)均為人工設(shè)定，選取較優(yōu)的值。

表2和表3分別表示MINIST數(shù)據(jù)集和Pendigits數(shù)據(jù)集熵算法的各項(xiàng)指標(biāo)對(duì)比。

表2 MINIST數(shù)據(jù)集上算法性能對(duì)比

表3 Pendigits數(shù)據(jù)集上算法性能對(duì)比

由表2和表3中可以看出，本文算法LSC-ILS聚類精度比Nystr?m和LSC-R算法高，比LSC-K算法低，運(yùn)行時(shí)間短于LSC-K算法和Nystr?m算法，與LSC-R算法運(yùn)行時(shí)間幾乎持平。LSC-R-LR算法和LSC-K-LR算法的聚類精度分別與LSC-R算法和LSC-K算法幾乎持平，但運(yùn)行時(shí)間有所減少。因此，綜合聚類精確度與運(yùn)行時(shí)間本文算法做到了更好的平衡，并且本文中LR算法可擴(kuò)展到其它算法中，在保持聚類精確度的情況下減少運(yùn)行時(shí)間。

為了驗(yàn)證地標(biāo)點(diǎn)個(gè)數(shù)對(duì)加速聚類算法的影響，將本文算法與其余3種加速譜算法在數(shù)據(jù)集MINIST上針對(duì)不同地標(biāo)點(diǎn)數(shù)量在3個(gè)指標(biāo)上進(jìn)行對(duì)比。地標(biāo)點(diǎn)數(shù)量從300開始，增量為300，到2 100結(jié)束，結(jié)果如圖2～圖4所示。

圖2 MINIST數(shù)據(jù)集上ACC指標(biāo)隨地標(biāo)點(diǎn)增長(zhǎng)變化

由圖2～圖4可以看出，除了Nystr?m算法，其余算法的聚類精確性均隨著地標(biāo)點(diǎn)個(gè)數(shù)增加而增加。本文算法聚類精確度始終保持在LSC-K與LSC-R之間，但運(yùn)行時(shí)間幾乎與LSC-R算法持平，遠(yuǎn)小于LSC-K算法，運(yùn)行時(shí)間增長(zhǎng)慢于LSC-K算法，并且隨著地標(biāo)點(diǎn)個(gè)數(shù)的增加，本文算法精確度增長(zhǎng)加快。

圖3 MINIST數(shù)據(jù)集上NMI指標(biāo)隨地標(biāo)點(diǎn)數(shù)量增長(zhǎng)變化

圖4 MINIST數(shù)據(jù)集上時(shí)間指標(biāo)隨地標(biāo)點(diǎn)數(shù)量增長(zhǎng)變化

為了進(jìn)一步驗(yàn)證本文中LR算法對(duì)LSC-R和LSC-K算法隨地標(biāo)點(diǎn)數(shù)量增長(zhǎng)的變化的影響，將LSC-R和LSC-K分別與LSC-R-LR和LSC-K-LR在數(shù)據(jù)集MINIST上針對(duì)不同地標(biāo)點(diǎn)數(shù)量在3個(gè)指標(biāo)上進(jìn)行對(duì)比。地標(biāo)點(diǎn)數(shù)量同樣從300開始，增量為300，到2 100結(jié)束。結(jié)果如圖5～圖10所示。

由圖5～圖10可以看出，LSC-R-LR算法和LSC-K-LR算法在不同的地標(biāo)點(diǎn)數(shù)量情況下的聚類精度幾乎與LSC-R算法和LSC-K算法持平，運(yùn)行時(shí)間有所減少，進(jìn)一步證明了本文LR算法的穩(wěn)定性和有效性。

圖5 ACC指標(biāo)隨地標(biāo)點(diǎn)數(shù)量變化

圖6 NMI指標(biāo)隨地標(biāo)點(diǎn)數(shù)量變化

圖7 Time指標(biāo)隨地標(biāo)點(diǎn)數(shù)量變化

圖8 ACC指標(biāo)隨地標(biāo)點(diǎn)數(shù)量變化

圖9 NMI指標(biāo)隨地標(biāo)點(diǎn)數(shù)量變化

圖10 Time指標(biāo)隨地標(biāo)點(diǎn)數(shù)量變化

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

本文針對(duì)傳統(tǒng)加速譜聚類算法存在的一些問(wèn)題提出了改進(jìn)地標(biāo)采樣的加速譜聚類算法。通過(guò)多次隨機(jī)采樣選取多組地標(biāo)點(diǎn)集，利用各個(gè)地標(biāo)點(diǎn)集內(nèi)地標(biāo)點(diǎn)之間相似度矩陣的行標(biāo)準(zhǔn)差和衡量地標(biāo)點(diǎn)的分布情況，選取最佳地標(biāo)點(diǎn)集，并根據(jù)地標(biāo)點(diǎn)的密度權(quán)重去除一些離群地標(biāo)點(diǎn)。本文從理論和實(shí)驗(yàn)分析證明了該算法的有效性。下一步計(jì)劃將本文算法擴(kuò)展到分布式計(jì)算框架上，進(jìn)一步提高算法效率。