葉 茂 劉文芬

?

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

葉 茂*劉文芬

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

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

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

1 引言

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

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

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

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

2 基礎(chǔ)知識(shí)

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

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

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

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

表1 LSC算法

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

2.3 近似SVD算法

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

表2 近似SVD算法

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

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

成立。

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

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

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

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

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

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

表3 近似SVD的抽樣算法

成立。

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

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

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

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

成立。

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

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

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

(3)

而由性質(zhì)1可知

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5 不同聚類算法的性能對(duì)比

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

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

[1] 何清, 李寧, 羅文娟, 等. 大數(shù)據(jù)下的機(jī)器學(xué)習(xí)算法綜述[J]. 模式識(shí)別與人工智能, 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é)報(bào), 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

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

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

葉 茂： 男，1988年生，博士生，研究方向?yàn)閿?shù)據(jù)挖掘.

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