基于快速地標(biāo)采樣的大規(guī)模譜聚類算法

葉 茂 劉文芬

?

基于快速地標(biāo)采樣的大規(guī)模譜聚類算法

葉 茂*劉文芬

(解放軍信息工程大學(xué) 鄭州 450002) (數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室 鄭州 450002)

為避免傳統(tǒng)譜聚類算法高復(fù)雜度的應(yīng)用局限，基于地標(biāo)表示的譜聚類算法利用地標(biāo)點與數(shù)據(jù)集各點間的相似度矩陣，有效降低了譜嵌入的計算復(fù)雜度。在大數(shù)據(jù)集情況下，現(xiàn)有的隨機抽取地標(biāo)點的方法會影響聚類結(jié)果的穩(wěn)定性，均值中心點方法面臨收斂時間未知、反復(fù)讀取數(shù)據(jù)的問題。該文將近似奇異值分解應(yīng)用于基于地標(biāo)點的譜聚類，設(shè)計了一種快速地標(biāo)點采樣算法。該算法利用由近似奇異向量矩陣行向量的長度計算的抽樣概率來進(jìn)行抽樣，同隨機抽樣策略相比，保證了聚類結(jié)果的穩(wěn)定性和精度，同均值中心點策略相比降低了算法復(fù)雜度。同時從理論上分析了抽樣結(jié)果對原始數(shù)據(jù)的信息保持性，并對算法的性能進(jìn)行了實驗驗證。

地標(biāo)點采樣；大數(shù)據(jù)；譜聚類；近似奇異值分解

1 引言

聚類分析可將數(shù)據(jù)集按照相似性分成子集，使得人們能根據(jù)分類結(jié)果找出數(shù)據(jù)的內(nèi)在聯(lián)系，是模式識別、數(shù)據(jù)挖掘的主要方法之一[1]。傳統(tǒng)聚類算法(如均值等)在非凸數(shù)據(jù)集上效果不佳，這使得適用于非凸數(shù)據(jù)集和能檢測線性不可分簇的譜聚類算法[2,3]成為了聚類分析中的研究熱點。但是，傳統(tǒng)的譜聚類算法涉及構(gòu)造相似度矩陣和對相應(yīng)的拉普拉斯矩陣特征分解，需要的空間復(fù)雜度和的時間復(fù)雜度，這對于大規(guī)模數(shù)據(jù)集來說是難以承受的計算負(fù)擔(dān)。

為提升譜聚類算法的擴展性，一個自然的想法就是設(shè)計可以減少特征分解復(fù)雜度的算法。2004年，F(xiàn)owlkes等人[4]改進(jìn)Nystr?m方法并將其用于譜聚類，實現(xiàn)了快速近似特征分解。隨后，Li等人[5,6]又用近似奇異值分解(Singular Value Decomposition, SVD)方法提升了Nystr?m方法中特征分解的效率。而丁世飛等人[7]則設(shè)計了一種自適應(yīng)采樣的方法，改進(jìn)了Nystr?m譜聚類的聚類效果。此外，Yan等人[8]還提出了一個快速近似譜聚類的框架：先選擇代表點，然后對代表點進(jìn)行譜聚類，并將分類關(guān)系擴展到與代表點關(guān)聯(lián)的其他點上。

2011年，Chen等人[9]提出了基于地標(biāo)點的譜聚類(Landmark-based Spectral Clustering, LSC)算法，指出該方法適用于大規(guī)模數(shù)據(jù)集，并且性能要比Nystr?m方法和Yan的方法[8]好，并在隨后給出了相關(guān)理論分析[10]。LSC算法通過數(shù)據(jù)集點與地標(biāo)點之間的相似度矩陣的乘積來近似得到整體的相似度矩陣，然后利用近似性質(zhì)實現(xiàn)快速特征分解。但該方法用隨機采樣確定地標(biāo)點，抽樣結(jié)果不穩(wěn)定，在大數(shù)據(jù)集時容易出現(xiàn)樣本點集中于某一區(qū)域的情況。

當(dāng)前，隨機映射由于可在降低數(shù)據(jù)規(guī)模的同時保持大部分原始信息而被廣泛用于聚類算法中。本文利用隨機映射得到近似SVD算法，然后由分解得到的近似奇異向量矩陣的行向量長度確定各點在數(shù)據(jù)集中的權(quán)重并計算抽樣概率，以此得到快速抽樣算法。通過理論分析，得出該抽樣算法的抽樣誤差被限制在一個較小的界內(nèi)，保證了抽樣結(jié)果對原始數(shù)據(jù)的信息保持性。實驗結(jié)果表明基于該抽樣方法的LSC算法聚類結(jié)果要比基于隨機抽樣的算法穩(wěn)定且聚類精度更高，比基于均值中心點的方法運行速度快，從而驗證了新方法的性能。

2 基礎(chǔ)知識

本節(jié)先給出本文所用的一些矩陣相關(guān)符號，然后簡述LSC算法和應(yīng)用于快速采樣的近似SVD算法。

2.1 矩陣的相關(guān)符號

2.2 基于地標(biāo)表示的譜聚類算法

LSC算法[9]主要思想是通過地標(biāo)點來實現(xiàn)相似度矩陣的快速構(gòu)造和特征分解。具體算法流程如表1的算法1所示。

表1 LSC算法

從算法流程可以看出，步驟3實現(xiàn)了相似度矩陣的近似構(gòu)造：對計算右奇異向量矩陣，此過程等價于對矩陣進(jìn)行特征分解得到特征向量。由于，所以相似度矩陣分解的時間復(fù)雜度從的特征分解時間減少到了的SVD時間，空間復(fù)雜度從存儲所需的減少到了存儲所需的，時間、空間復(fù)雜度均比原始譜聚類算法顯著減少。

2.3 近似SVD算法

基于矩陣重構(gòu)的采樣始于1988年Frieze等人[14]的開創(chuàng)性成果：給定矩陣，通過與列向量歐幾里得長度平方成比例的概率抽樣少的列，可快速得到原始矩陣的低秩近似。隨后，文獻(xiàn)[15,16]以與奇異向量矩陣的整行長度成比例的概率抽樣矩陣的列，使得近似效果得到明顯提升。2014年，Boutsidis等人[17]通過基于隨機映射的近似SVD算法[18]來改進(jìn)抽樣算法效率，并得到了漸近最優(yōu)抽樣算法。本文所用的快速采樣算法就是基于近似SVD算法得到的，SVD具體流程如表2的算法2所示。

表2 近似SVD算法

算法2的思想在于用隨機映射對數(shù)據(jù)進(jìn)行壓縮，并使得在降低矩陣規(guī)模后仍保持原始矩陣的主要信息。Sarlos[19]指出，經(jīng)過隨機映射壓縮數(shù)據(jù)，若壓縮后數(shù)據(jù)規(guī)模滿足特定參數(shù)，則該近似SVD算法所得到的近似奇異向量在最優(yōu)低秩近似上能保持與精確的奇異向量接近的效果。

引理1[19]令,是在2.1節(jié)定義的投影算子。如果,，其中是滿足算法2所要求的矩陣，且，則至少以的概率，有

成立。

3 基于快速地標(biāo)采樣的大規(guī)模譜聚類算法

相比于傳統(tǒng)譜聚類算法，LSC算法在時間和空間復(fù)雜度上均有很大優(yōu)勢，并且在聚類效果上也令人滿意。作為算法的關(guān)鍵，地標(biāo)點的選取在很大程度上影響了聚類效果。常用的方式是均勻隨機采樣，在大規(guī)模數(shù)據(jù)集上隨機抽樣的不穩(wěn)定性很可能會導(dǎo)致所抽樣本點集中于某一區(qū)域，這將使得算法聚類效果變差。

LSC算法的思想是通過地標(biāo)點的線性組合來實現(xiàn)所有數(shù)據(jù)點的表示，然后通過地標(biāo)點與數(shù)據(jù)點的相似性度量來給出各個數(shù)據(jù)點之間的相似性度量，因此地標(biāo)點的特征在于“代表性”。文獻(xiàn)[15,16]提出了一種可抽取具有“代表性”數(shù)據(jù)點的方法：采用以與奇異向量矩陣整行長度平方成比例的概率抽樣數(shù)據(jù)，使得較少數(shù)量的樣本可以構(gòu)造原始數(shù)據(jù)矩陣的一個低秩近似。在此基礎(chǔ)上，本文采用近似SVD算法，在降低采樣過程時間復(fù)雜度的同時，得到與精確SVD相近的采樣結(jié)果，產(chǎn)生有“代表性”的點。本節(jié)首先給出基于近似SVD的快速采樣算法，然后分析通過該算法得到的數(shù)據(jù)樣本點在形成原始數(shù)據(jù)矩陣低秩近似時的誤差，最后給出完整的基于快速地標(biāo)點采樣的譜聚類算法。

3.1 基于近似SVD的快速采樣算法及誤差分析

根據(jù)矩陣SVD分解結(jié)果進(jìn)行抽樣的相關(guān)理論分析已由文獻(xiàn)[15]給出，而雖然文獻(xiàn)[17,19]指出基于近似SVD分解結(jié)果進(jìn)行抽樣可使矩陣低秩近似的誤差保持在小的界內(nèi)，但并沒有給出嚴(yán)格證明，本小節(jié)給出一個簡潔的證明。

首先給出基于近似SVD的抽樣算法3如表3所示。

表3 近似SVD的抽樣算法

成立。

從定理1可知，對于通過算法3所得到的矩陣的行樣本，其所能得到的最優(yōu)原始矩陣近似誤差與相差一個較小的因子，保持了原始矩陣的大部分信息。在證明定理前，先給出兩個相關(guān)的引理：

引理2[20]令,且,是由算法3依據(jù)產(chǎn)生的抽樣矩陣。若抽樣個數(shù)，則對于，至少以的概率，有

引理2指出，如果抽樣規(guī)模足夠，算法3通過列正交矩陣產(chǎn)生的抽樣矩陣，作用于原矩陣后仍得到奇異值接近于1的矩陣，即將一個列正交矩陣抽樣為一個近似的列正交矩陣。

引理3[11]令，任意是算法3步驟1所需的矩陣，對于算法3所產(chǎn)生的抽樣矩陣，對于任意，任意，至少以的概率，有

成立。

引理3說明根據(jù)算法3的抽樣方法，對任意矩陣抽樣并適當(dāng)調(diào)整樣本尺寸后，所產(chǎn)生的矩陣與原始矩陣在Frobenius范數(shù)平方上接近，即該抽樣算法對矩陣的Frobenius范數(shù)沒有產(chǎn)生太大的影響。

利用上述引理，給出定理1的證明：

利用矩陣的近似奇異向量矩陣，將其分解為：，則有

(3)

而由性質(zhì)1可知

(5)

定理1表明，采用基于近似SVD的抽樣可以保證抽樣誤差在特定的界內(nèi)，這使得采樣的樣本具有較好的代表性。因此，利用該方法所得到的采樣樣本，其與數(shù)據(jù)點形成的相似度矩陣能較好地描述數(shù)據(jù)之間的關(guān)系。

3.2 基于快速地標(biāo)點采樣的譜聚類算法

3.1節(jié)從矩陣低秩近似誤差的角度在理論上分析了基于近似SVD的抽樣樣本的代表性，根據(jù)3.1節(jié)結(jié)論，我們提出了使用基于近似SVD的抽樣方法來采樣地標(biāo)點的LSC算法，稱為基于快速地標(biāo)點采樣的譜聚類算法(Landmark-based Spectral Clustering with Fast Sampling, LSC-FS)，該算法的具體流程如表4所示。

LSC-FS算法主要分為地標(biāo)點采樣和基于地標(biāo)點的譜聚類兩部分，因為基于地標(biāo)點的譜聚類算法復(fù)雜度已經(jīng)在2.2節(jié)給出，所以我們主要對地標(biāo)點采樣部分進(jìn)行算法復(fù)雜度分析。

表4 基于快速地標(biāo)點采樣的譜聚類算法(LSC-FS)

對于抽樣過程，第1步是計算矩陣的近似奇異向量。根據(jù)算法2的計算流程，計算近似奇異向量的時間為，其中算法2步驟2矩陣乘積需的時間，步驟3列標(biāo)準(zhǔn)正交化需，步驟4矩陣乘積和SVD需。抽樣算法剩余步驟為確定抽樣概率并進(jìn)行抽樣，計算復(fù)雜度為。由于在實際中常出現(xiàn)且，所以本文所設(shè)計的新算法在采樣階段的計算復(fù)雜度為。

地標(biāo)點的生成方法常見的是隨機采樣，而另外一種地標(biāo)點的生成方法是用均值的中心點代替。如果用均值的中心點作為地標(biāo)點，其生成過程計算復(fù)雜度為，其中為迭代次數(shù)。由定理1的要求可知，，所以新算法的采樣過程計算量通常要比基于均值的采樣過程要小(當(dāng)時)。并且當(dāng)數(shù)據(jù)規(guī)模極大，超出系統(tǒng)的內(nèi)存時，均值聚類算法需要不斷地執(zhí)行數(shù)據(jù)讀取操作，而新算法的抽樣過程對數(shù)據(jù)的讀取次數(shù)至多需要3次，更高效。

4 實驗結(jié)果與分析

本節(jié)進(jìn)行實驗分析，對算法的有效性和運行時間兩類指標(biāo)進(jìn)行評估。

我們對兩個較大數(shù)據(jù)集進(jìn)行實驗。第1個被稱為MNIST，是一個手寫數(shù)字的數(shù)據(jù)集1)MNIST數(shù)據(jù)可從http://yann.lecun.com/exdb/mnist/上下載。該數(shù)據(jù)集共有70000個對象，每個對象是像素的屬于數(shù)字0到9的圖像，其中每個像素是從中取出的整數(shù)。實驗時，我們將每個對象視為784維的向量。第2個被稱為RCV1，是路透社的新聞文檔集。為方便實驗對比，我們采用與文獻(xiàn)[21]一致的處理方式，對其中的103類共計193844個有47236個特征的文檔進(jìn)行聚類分析。實驗算法在英特爾Core i7-4790 @ 3.60 GHz CPU, 16 GB內(nèi)存的計算機上運行，實驗代碼在MATLAB環(huán)境下編寫。

為驗證新算法的聚類有效性和效率，本文對原始譜聚類(記為SC), Nystr?m近似譜聚類(記為Nystr?m)、基于隨機采樣的地標(biāo)點譜聚類(記為LSC-R)和基于均值中心的地標(biāo)點譜聚類(記為LSC-K)與本文算法(記為LSC-FS)進(jìn)行實驗比較。對于Nystr?m算法，我們采用文獻(xiàn)[21]給出的帶正交化的MATLAB代碼，對于LSC算法，我們采用文獻(xiàn)[9]給出的實現(xiàn)代碼。

在實驗過程中，通過改變抽樣個數(shù)來比較不同個數(shù)的采樣點對實驗結(jié)果的影響。為避免算法中隨機化過程對實驗結(jié)果的影響，對每一個采樣點數(shù)，各個算法都獨立進(jìn)行20次并取平均值作為算法結(jié)果；為比較的公平性，所有相似度矩陣構(gòu)造過程中的近鄰個數(shù)都選為5。

4.1 評價指標(biāo)

算法有效性描述的是聚類算法對數(shù)據(jù)進(jìn)行劃分的正確程度，通過對算法聚類結(jié)果和預(yù)定義的類標(biāo)簽進(jìn)行相似性比對得出。本文用聚類精確性(Cluster Accuracy, CA)[22]和標(biāo)準(zhǔn)化互信息(Normalized Mutual Information, NMI)[23]兩種指標(biāo)。

CA度量了聚類結(jié)果中被正確劃分到預(yù)定義類標(biāo)簽的數(shù)據(jù)點的比例，按式(7)計算：

其中，是聚類結(jié)果中簇的個數(shù)，是數(shù)據(jù)量，是第個簇，表示聚類結(jié)果中第個簇中標(biāo)簽所對應(yīng)的樣本點個數(shù)的最大值。從CA定義可知CA越大，聚類效果越好，CA最大值為1。

NMI也評估了聚類算法的劃分質(zhì)量。將各個簇所占數(shù)據(jù)總量的比率視為隨機變量取值該簇標(biāo)簽的概率，那么可得到兩個概率分布，NMI度量的是兩個概率分布之間共享的信息量。將兩個隨機變量分別記為和，按式(8)來計算NMI：

4.2 實驗結(jié)果

4種快速譜聚類算法加上原始譜聚類算法在兩個數(shù)據(jù)集上的性能表現(xiàn)如表5所示，從左往右依次從運行時間(s), CA(%)，NMI(%)3個方面進(jìn)行對比。為便于比較，4種快速算法的抽樣個數(shù)均設(shè)為1000。需要指出的是，由于原始譜聚類算法在RCV1上運行時間太久，所以只運行了兩次，不求方差。

從表5可以看出，在聚類有效性方面，本文算法的聚類精度要比LSC-R算法和Nystr?m近似算法要高，比LSC-K算法低；在算法效率方面，新算法比LSC-K算法運行時間明顯少，并且隨著數(shù)據(jù)集及數(shù)據(jù)維數(shù)的增大，運行時間并沒有比LSC-R算法差別很大。對算法有效性和效率綜合考慮，雖然LSC-K算法在聚類效果上來講表現(xiàn)很好，但隨著數(shù)據(jù)集及其維數(shù)的增大，該算法將會越來越慢；從表中的方差項中可以看出新算法通常比LSC-R算法要更為穩(wěn)定。因此，從聚類效果、算法效率及穩(wěn)定性方面均衡考慮，本文算法有優(yōu)勢。從算法流程可以看出，算法還可以較好地實現(xiàn)并行化處理，這使得新算法更有吸引力。

為了研究抽樣個數(shù)對各個快速譜聚類方法的影響，我們在MNIST數(shù)據(jù)集上固定其他參數(shù)，令抽樣個數(shù)從100到1100每隔100進(jìn)行變化，實驗結(jié)果如圖1-圖3所示。

從圖1，圖2中可以看出，不同于Nystr?m近似算法有效性指標(biāo)變化不大的情況，本文算法的聚類效果隨著抽樣個數(shù)的增多而變好。這說明地標(biāo)點個數(shù)也是新算法的重要參數(shù)之一，地標(biāo)點個數(shù)越多，本文算法能獲得更多的數(shù)據(jù)點間的關(guān)系信息，聚類效果越好。再結(jié)合圖3可知，在保持運行時間相差不大的情況下，本文算法比LSC-R算法的聚類效果要好；雖然聚類效果沒有LSC-K算法好，但新算法的運行時間要短得多。因此新算法在效率和聚類效果上取得了較好的平衡。

表5 不同聚類算法的性能對比

5 結(jié)束語

基于地標(biāo)表示的譜聚類算法可通過地標(biāo)點快速實現(xiàn)相似度矩陣的構(gòu)造和相應(yīng)拉普拉斯矩陣的分解，是一種適用于大數(shù)據(jù)集的譜聚類算法。針對隨機抽樣地標(biāo)點效果不穩(wěn)定，用均值中心作為地標(biāo)點運行時間長的問題，本文設(shè)計了一種快速地標(biāo)點采樣算法。本文算法基于近似奇異值分解，可使每個地標(biāo)點的抽樣概率對應(yīng)于其在數(shù)據(jù)集中的權(quán)重。本文不僅從理論上分析了該抽樣算法結(jié)果對原始信息的保持性，還從公開數(shù)據(jù)集上驗證了新算法在效率和有效性上的優(yōu)勢。

[1] 何清, 李寧, 羅文娟, 等. 大數(shù)據(jù)下的機器學(xué)習(xí)算法綜述[J]. 模式識別與人工智能, 2014, 27(4): 327-336.

HE Qing, LI Ning, LUO Wenjuan,. A survey of machine learning algorithms for big data[J]., 2014, 27(4): 327-336.

[2] DING S, JIA H, ZHANG L,. Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J]., 2014, 24(1): 211-219. doi: 10.1007/s00521-012-1207-8.

[3] NG A Y, JORDAN M I, and WEISS Y. On spectral clustering: Analysis and an algorithm[C]. Neural Information Processing Systems: Natural and Synthetic, Vancouver, Canada, 2001: 849-856.

[4] FOWLKES C, BELONGIE S, CHUNG F,. Spectral grouping using the Nystrom method[J]., 2004, 26(2): 214-225. doi: 10.1109/TPAMI.2004.1262185.

[5] LI M, KWOK J T, and LU B L. Making large-scale Nystr?m approximation possible[C]. Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010: 631-638.

[6] LI M, BI W, KWORK J T,. Large-scale Nystr?m kernel matrix approximation using randomized SVD[J]., 2015, 26(1): 152-164. doi: 10.1109/TNNLS.2014.2359798.

[7] 丁世飛, 賈洪杰, 史忠植. 基于自適應(yīng)Nystr?m 采樣的大數(shù)據(jù)譜聚類算法[J]. 軟件學(xué)報, 2014, 25(9): 2037-2049. doi: 10.13328/j.cnki.jos.004643.

DING Shifei, JIA Hongjie, and SHI Zhongzhi. Spectral clustering algorithm based on adaptive Nystr?m sampling for big data analysis[J]., 2014, 25(9): 2037-2049.doi: 10.13328/j.cnki.jos.004643.

[8] YAN D, HUANG L, and JORDAN M I. Fast approximate spectral clustering[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 907-916. doi: 10.1145/1557019.1557118.

[9] CHEN X and CAI D. Large scale spectral clustering with landmark-based representation[C]. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 313-318.

[10] CAI D and CHEN X. Large scale spectral clustering via landmark-based sparse representation[J]., 2015, 45(8): 1669-1680. doi: 10.1109/TCYB. 2014.2358564.

[11] BOUTSIDIS C, ZOUZIAS A, MAHONEY M W,. Randomized dimensionality reduction for-means clustering[J]., 2015, 61(2): 1045-1062. doi: 10.1109/TIT.2014.2375327.

[12] COHEN M, ELDER S, MUSCO C,. Dimensionality reduction for-means clustering and low rank approximation[C]. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, OR, USA, 2015: 163-172. doi: 10.1145/2746539.2746569.

[13] KHOA N L D and CHAWLA S. A scalable approach to spectral clustering with SDD solvers[J]., 2015, 44(2): 289-308. doi: 10.1007/ s10844-013-0285-0.

[14] FRIEZE A, KANNAN R, and VEMPALA S. Fast Monte-Carlo algorithms for finding low-rank approximations[C]. Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 1998: 370-378. doi: 10.1109/SFCS. 1998.743487.

[15] DRINEAS P, MAHONEY M W, and MUTHUKRISHNAN S. Sampling algorithms for l2 regression and applications[C]. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, Miami, Florida, USA, 2006: 1127-1136.

[16] DRINES P, MAHONEY M W, and MUTHUKRISHNAN S. Subspace sampling and relative-error matrix approximation: Column-based methods[C]. 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 10th International Workshop on Randomization and Computation, Barcelona, Spain, 2006: 316-326. doi: 10.1007/11830924_30.

[17] BOUTSIDIS C, DRINEAS P, and MAGDON-ISMAIL M. Near-optimal column-based matrix reconstruction [J]., 2014, 43(2): 687-717. doi: 10.1137/12086755X.

[18] HALKO N, MARTINSSON P G, and TROPP J A. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions[J]., 2011, 53(2): 217-288. doi: 10.1137/090771806.

[19] SARLOIS T. Improved approximation algorithms for large matrices via random projections[C]. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, USA, 2006: 143-152. doi: 10.1109/FOCS.2006.37.

[20] MAGDON-ISMAIL M. Row sampling for matrix algorithms via a non-commutative Bernstein bound[OL]. http:// arxiv.org/ abs/1008.0587, 2015.10.

[21] CHEN W Y, SONG Y, BAI H,. Parallel spectral clustering in distributed systems[J]., 2011, 33(3): 568-586. doi: 10.1109/TPAMI.2010.88.

[22] AFAHAD A, ALSHATRI N, TARI Z,. A survey of clustering algorithms for big data: Taxonomy and empirical analysis[J]., 2014, 2(3): 267-279. doi: 10.1109/TETC. 2014.2330519.

[23] STREHL A and GHOSH J. Cluster ensemblesA knowledge reuse framework for combining multiple partitions[J]., 2003, 3: 583-617. doi: 10.1162/153244303321897735.

Large Scale Spectral Clustering Based on Fast Landmark Sampling

YE Mao LIU Wenfen

(,450002,) (,450002,)

The applicability of traditional spectral clustering is limited by its high complexity in large-scale data sets. Through construction of affinity matrix between landmark points and data points, the Landmark-based Spectral Clustering (LSC) algorithm can significantly reduce the computational complexity of spectral embedding. It is vital for clustering results to apply the suitable strategies of the generation of landmark points. While considering big data problems, the existing generation strategies of landmark points face some deficiencies: the unstable results of random sampling, along with the unknown convergence time and the repeatability of data reading in-means centers method. In this paper, a rapid landmark-sampling spectral clustering algorithm based on the approximate singular value decomposition is designed, which makes the sampling probability of each landmark point decided by the row norm of the approximate singular vector matrix. Compared with LSC algorithm based on random sampling, the clustering result of new algorithm is more stable and accurate; compared with LSC algorithm based on-means centers, the new algorithm reduces the computational complexity. Moreover, the preservation of information in original data is analyzed for the landmark-sampling results theoretically. At the same time, the performance of new approach is verified by the experiments in some public data sets.

Landmark sampling; Big data; Spectral clustering; Approximate singular value decomposition

TP181

A

1009-5896(2017)02-0278-07

10.11999/JEIT160260

2016-03-21；改回日期：2016-07-18，

2016-09-30

葉茂 yemaoxxgc@163.com

國家973計劃(2012CB315905)，國家自然科學(xué)基金(61502527, 61379150)

The National 973 Program of China (2012CB315905), The National Natural Science Foundation of China (61502527, 61379150)

葉 茂： 男，1988年生，博士生，研究方向為數(shù)據(jù)挖掘.

劉文芬： 女，1965 年生，教授，博士生導(dǎo)師，研究方向包括概率統(tǒng)計、網(wǎng)絡(luò)通信、信息安全.