徐航帆,劉 叢,唐堅(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í)間空間成本和聚類精度上取得較好的平衡。
給定數(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ù)集上的加速譜聚類的算法。
基于地標(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í)間和空間。
地標(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ù)雜度。
給定數(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)。
圖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。
本節(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ù)雜度總和最小。
為了驗(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)比較。
為了驗(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類。
為了評(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é)果越精確。
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ù)量變化
本文針對(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)一步提高算法效率。