面向大數(shù)據(jù)的并行聚類算法

劉解放，張志輝

(1.湖北交通職業(yè)技術(shù)學(xué)院 交通信息學(xué)院，湖北 武漢 430079； 2.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

0 引 言

大數(shù)據(jù)對社會(huì)具有潛在價(jià)值，它正在推動(dòng)行業(yè)研究人員重新思考計(jì)算方案來獲取有用信息。但由于高計(jì)算成本，使得分析和檢索操作非常耗時(shí)。因此，高性能計(jì)算，如并行計(jì)算[1]、分布式計(jì)算[2]、云計(jì)算[3]和網(wǎng)格計(jì)算[4]等無疑是未來解決上述問題的重要手段。

聚類本質(zhì)上是一種典型的“無監(jiān)督”數(shù)據(jù)分析方法，但到目前為止，已提出的所有經(jīng)典算法都需要用戶的大量指導(dǎo)，例如K-means需要預(yù)先指定聚類個(gè)數(shù)和終止條件。最近提出的CLUBS[5]，是一種非常有效的聚類算法，無需用戶任何指導(dǎo)，通過4個(gè)階段的不斷完善，自動(dòng)完成聚類任務(wù)。它不但能夠容忍一定程度的過度分割，而且能夠處理異常點(diǎn)的檢測及橢圓簇的生成。遺憾的是，該算法針對大數(shù)據(jù)應(yīng)用場景無能為力。

本文結(jié)合高性能計(jì)算提出了CLUBS的并行版本，稱為CLUBS‖，類似CLUBS，CLUBS‖時(shí)間復(fù)雜度關(guān)于數(shù)據(jù)集大小線性縮放，并基于Ad-hoc消息傳遞實(shí)現(xiàn)了所提聚類算法。實(shí)驗(yàn)結(jié)果表明，隨著越來越多的并行節(jié)點(diǎn)加入運(yùn)算，加速比幾乎是線性的。CLUBS‖的特性使它可以有效聚類大規(guī)模數(shù)據(jù)，且不要求節(jié)點(diǎn)間交換原始數(shù)據(jù)，僅需交換摘要信息。

1 相關(guān)工作

大數(shù)據(jù)的出現(xiàn)重新激發(fā)了研究人員對數(shù)據(jù)挖掘基礎(chǔ)工具的興趣，例如聚類。為克服聚類的計(jì)算復(fù)雜度，研究人員已經(jīng)提出許多方法，無論是單機(jī)還是聯(lián)機(jī)方案。

單機(jī)版的大數(shù)據(jù)聚類經(jīng)典方法大都基于采樣、降維和分塊技術(shù)，例如，文獻(xiàn)[6]提出了一種基于加速比和勢分布的采樣方法，通過使用采樣技術(shù)減少求解搜索空間，極大地提高了大數(shù)據(jù)處理的性能；文獻(xiàn)[7]基于隨機(jī)投影技術(shù)降低數(shù)據(jù)維度提出了一種聚類方法WOMP-GS-FIS，該方法盡可能保持了樣本點(diǎn)間的距離；文獻(xiàn)[8]通過將貝葉斯模糊聚類與分塊技術(shù)相結(jié)合，提出了一種面向大規(guī)模數(shù)據(jù)的快速單趟貝葉斯模糊聚類算法SPBFC。

盡管以上方法顯著減少了大規(guī)模數(shù)據(jù)聚類的計(jì)算時(shí)間，但是，在給定的時(shí)間內(nèi)，數(shù)據(jù)量的增長遠(yuǎn)遠(yuǎn)快于單機(jī)處理能力的增長。這使得必須使用并行技術(shù)，但是，并行技術(shù)由于某些關(guān)鍵因素而帶來極大挑戰(zhàn)，例如協(xié)同工作、網(wǎng)絡(luò)通信、資源共享和容錯(cuò)能力等，實(shí)現(xiàn)難度較大。目前，有些經(jīng)典算法被改寫實(shí)現(xiàn)了并行化，其中K-means‖[9]是一個(gè)非常成功的案例，它采用播種算法，即使在單機(jī)上運(yùn)行，也優(yōu)于K-means。

2 CLUBS

最近提出的CLUBS[5]是一種基于快速分層的無參數(shù)中心聚類算法。它融合了分裂和凝聚兩種優(yōu)點(diǎn)。首先，使用二叉空間分割技術(shù)對數(shù)據(jù)集進(jìn)行定義，并生成一系列的初始簇，其次，對生成的簇進(jìn)行調(diào)整，然后，對簇進(jìn)行凝聚，最后再完善。在完善階段，異常點(diǎn)被標(biāo)記，其余的點(diǎn)被分配到最近的簇。圖1展示了CLUBS在二維數(shù)據(jù)上的執(zhí)行過程，圖1(a)為原始圖，圖1(b)～圖1(e)為各步驟的執(zhí)行結(jié)果。下面簡要介紹它4個(gè)核心步驟。

圖1 CLUBS在二維數(shù)據(jù)上的執(zhí)行過程

2.1 分裂階段

CLUBS采用自頂向下二叉空間分割技術(shù)將數(shù)據(jù)集分割成為一系列的超矩形塊，使得各塊內(nèi)部點(diǎn)盡可能靠近，這等價(jià)于最小化簇內(nèi)平方和(WCSS)。CLUBS要求分割的超平面正交與坐標(biāo)軸，并使用貪婪準(zhǔn)則，塊被迭代分割為成對的簇。

給定一個(gè)數(shù)據(jù)集，該算法將其作為一個(gè)簇S，S進(jìn)入優(yōu)先級(jí)隊(duì)列Q，Q包含所有迭代分割的塊。如果Q非空，從中出隊(duì)一個(gè)塊B， 并將其劃分為一對塊，如果劃分有效，該對塊替代B并進(jìn)入隊(duì)列，否則，B成為最終的塊。

將所有屬于塊B， 且第i維坐標(biāo)值等于x的點(diǎn)p求和，該函數(shù)可以表示為圖或數(shù)組。文獻(xiàn)[5]表明最小化WCSS的分割可以通過圖或數(shù)組的線性掃描產(chǎn)生。

該階段選擇了CH指標(biāo)[10]評(píng)估聚類質(zhì)量。每次分割之后，都會(huì)重新計(jì)算CH值，如果CH值增加，則分裂階段有效并繼續(xù)，若降低到70%以下，則停止本次分割。

2.2 調(diào)整階段

分裂階段結(jié)束后，整個(gè)數(shù)據(jù)空間被分割為兩類塊：一類是每塊僅含有一個(gè)簇，另一類是每塊僅含噪聲。調(diào)整階段，CLUBS力求實(shí)現(xiàn)兩個(gè)任務(wù)：①將含有簇的塊分離出來；②將分離出來的塊生成一個(gè)橢圓簇。

因僅含有噪聲塊的密度較低，因此可以通過觀察實(shí)施第一個(gè)任務(wù)。CLUBS首先基于密度對所有塊進(jìn)行遞增排序，并檢測相鄰塊間的密度跳躍，從而確定噪聲塊的候選子集。然后，測試候選子集，例如，在塊的中心生成一個(gè)較小的超立方體，如果超立方體的密度明顯大于整個(gè)塊的密度，則表明該塊屬于異常塊，否則屬于簇塊。例如，圖1中J、K、L和M都是異常塊。

2.3 凝聚階段

凝聚階段，通過合并上一階段產(chǎn)生的簇，改進(jìn)聚類質(zhì)量。如果合并一對簇導(dǎo)致WCSS較小增加，而CH指標(biāo)顯著增加，實(shí)施合并，并將合并后的簇替代原有的兩個(gè)簇。如果合并導(dǎo)致CH指標(biāo)嚴(yán)重降低，則取消，凝聚階段結(jié)束。實(shí)際上，僅有相鄰簇才考慮是否合并，因?yàn)橄噜彺氐暮喜⒉庞锌赡軐?dǎo)致WCSS較小增加和CH指標(biāo)顯著增加。圖1(d) 展示了簇B是由圖1(c)中簇B和簇I合并而成。

2.4 完善階段

由于前期采用了近似和貪婪準(zhǔn)則，凝聚階段通常會(huì)產(chǎn)生形狀稍不規(guī)則的簇。例如，圖1(d)中簇B，它是由圖1(c) 中簇B和簇I合并而成。由于調(diào)整階段，圖1(b)中塊K被認(rèn)定為異常塊，其左上角的點(diǎn)被塊B和I非對稱吸附，因此導(dǎo)致明顯不對稱。完善階段重構(gòu)橢圓簇，不僅提高了聚類質(zhì)量，并且還確定了最終異常點(diǎn)。

3 CLUBS‖∶CLUBS的并行化

假設(shè)有N個(gè)從節(jié)點(diǎn)，它們都具有相同的硬件特性，并具有本地存儲(chǔ)和計(jì)算能力，數(shù)據(jù)分布在從節(jié)點(diǎn)上，能存儲(chǔ)在分布式文件系統(tǒng)上或本地文件系統(tǒng)上。

多個(gè)從節(jié)點(diǎn)高效運(yùn)行的關(guān)鍵問題是如何協(xié)同訪問數(shù)據(jù)，其中包括：①分裂階段邊緣分布的計(jì)算；②調(diào)整階段候選離群塊的局部密度計(jì)算；③完善階段將點(diǎn)分配給最近簇計(jì)算。

下面將重點(diǎn)分析上述3個(gè)關(guān)鍵計(jì)算的并行化，關(guān)于其它計(jì)算，如摘要信息的計(jì)算，則使用CLUBS原有方法通過主節(jié)點(diǎn)處理。

3.1 邊緣分布的并行計(jì)算

邊緣分布的并行計(jì)算，也即是向量C和S的計(jì)算，它們是分裂階段唯一需要訪問數(shù)據(jù)的計(jì)算。由于計(jì)數(shù)運(yùn)算和求和運(yùn)算的結(jié)合性和可交換性，該計(jì)算可高效地并行執(zhí)行。因此，給定一個(gè)數(shù)據(jù)集的塊劃分 {B1,…,Bk}， 可獨(dú)立計(jì)算各塊Bk上C和S向量，最終，求和各塊上的向量得到數(shù)據(jù)集的全局向量。根據(jù)MapReduce范式，各塊Bk被映射為一系列向量對，表示各塊每個(gè)維度的C和S， 通過求和相同維度的向量，這些向量隨后被約簡。

3.2 塊局部密度的并行計(jì)算

為實(shí)現(xiàn)調(diào)整階段第一個(gè)任務(wù)，需計(jì)算塊的局部密度。在分裂階段，主節(jié)點(diǎn)獲得所有劃分塊的信息，因此，主節(jié)點(diǎn)可以獲得各塊的全局密度和范圍。為檢查塊質(zhì)心附近的局部密度是否明顯高于全局密度，需要計(jì)算質(zhì)心附近小范圍內(nèi)的局部密度(例如，整塊的1/10)，然后并行計(jì)算落入“受限”范圍內(nèi)的點(diǎn)數(shù)。盡管在這種情況下，該計(jì)算涉及到的唯一數(shù)學(xué)運(yùn)算是求和，因此，計(jì)算完全可并行化。實(shí)際上，對于數(shù)據(jù)塊的各個(gè)部分，都可以獨(dú)立計(jì)算點(diǎn)數(shù)，然后，將各部分的點(diǎn)數(shù)相加求和即可得到總的點(diǎn)數(shù)。因此，主節(jié)點(diǎn)可以計(jì)算局部密度。

3.3 點(diǎn)到簇的并行分配計(jì)算

將點(diǎn)分配給最近的簇或者將其作為異常點(diǎn)，每一個(gè)從節(jié)點(diǎn)在調(diào)整和完善階段都可以獨(dú)立執(zhí)行該操作。首先主節(jié)點(diǎn)將關(guān)于簇的摘要信息發(fā)送給每一個(gè)從節(jié)點(diǎn)，并要求它們計(jì)算點(diǎn)到簇的距離。至此，每個(gè)從節(jié)點(diǎn)都能計(jì)算摘要信息，然后，綜合來自從節(jié)點(diǎn)的所有數(shù)據(jù)，主節(jié)點(diǎn)即可獲得簇中心的全局值、各簇的點(diǎn)個(gè)數(shù)、簇的半徑，并更新簇的信息。

下面，針對所提并行算法CLUBS‖，提出一種基于Ad-hoc消息傳遞的實(shí)現(xiàn)。

4 基于Ad-hoc消息傳遞實(shí)現(xiàn)CLUBS‖

本節(jié)基于Ad-hoc消息傳遞實(shí)現(xiàn)了CLUBS‖算法，并基于標(biāo)準(zhǔn)Java套接字的信息交換實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)間的通信。

該算法實(shí)現(xiàn)如下：

步驟1 聚類開始時(shí)，主節(jié)點(diǎn)向從節(jié)點(diǎn)發(fā)送LoadDataSetRequest，為加載的數(shù)據(jù)集指定標(biāo)識(shí)符。各從節(jié)點(diǎn)將數(shù)據(jù)加載到內(nèi)存中，并通過LoadDataSetResponse答復(fù)主節(jié)點(diǎn)，該響應(yīng)消息包含自身加載數(shù)據(jù)的范圍。當(dāng)主節(jié)點(diǎn)收到所有從節(jié)點(diǎn)的答復(fù)時(shí)，即可計(jì)算全局?jǐn)?shù)據(jù)集的范圍。

步驟2 主節(jié)點(diǎn)向從節(jié)點(diǎn)發(fā)送InitRootRequest，指定全局域。每個(gè)從節(jié)點(diǎn)計(jì)算本地?cái)?shù)據(jù)邊緣分布，并通過InitRoo-tResponse答復(fù)主節(jié)點(diǎn)，該消息包含本地?cái)?shù)據(jù)的C和S。 主節(jié)點(diǎn)即可計(jì)算全局?jǐn)?shù)據(jù)集的C和S， 以及WCSS，從而實(shí)現(xiàn)塊的分割，并將塊初始化劃隊(duì)列。當(dāng)隊(duì)列非空時(shí)，出隊(duì)一個(gè)塊，開始計(jì)算它的全局邊緣分布。通過將所有節(jié)點(diǎn)本地邊緣分布分別相加求和即可獲得全局邊緣分布。

首先，假設(shè)全局邊緣分布在N個(gè)從節(jié)點(diǎn)間傳遞。主節(jié)點(diǎn)選擇一半的從節(jié)點(diǎn)發(fā)送它的邊緣分布給其余從節(jié)點(diǎn)，然后迭代累加邊緣分布。當(dāng)全局邊緣分布被傳遞到N/2個(gè)從節(jié)點(diǎn)上，主節(jié)點(diǎn)再次選擇一半的從節(jié)點(diǎn)發(fā)送邊緣分布給其余從節(jié)點(diǎn)。這個(gè)操作被重復(fù)，直到整個(gè)邊緣分布被存儲(chǔ)在一個(gè)節(jié)點(diǎn)上。圖2展示了邊緣分布的計(jì)算過程，圖2(a)每個(gè)從節(jié)點(diǎn)wi計(jì)算它本地的邊緣分布mi； 圖2(b)從節(jié)點(diǎn)w2發(fā)送m2到從節(jié)點(diǎn)w1， 從節(jié)點(diǎn)w4發(fā)送m4到從節(jié)點(diǎn)w3； 圖2(c)w1和w3分別將收到的邊緣分布和自身的邊緣分布相加，然后，w3發(fā)送m3+m4到w1上；圖2(d)w1再次將收到的邊緣分布和自身當(dāng)前的邊緣分布相加，從而獲取了全局邊緣分布。

圖2 邊緣分布計(jì)算過程

為了平衡負(fù)載，將分別計(jì)算各維度的邊緣分布，統(tǒng)籌各維度，整體考慮各節(jié)點(diǎn)的負(fù)載。該過程形式化如下，假設(shè) (w1,w2,…,wN) 是一組從節(jié)點(diǎn)，對于第i維，從i-1的位置左旋轉(zhuǎn)初始化從節(jié)點(diǎn)。因此，對于第i維，從節(jié)點(diǎn)的列表可表示為li=(wi,…,wN,w1,…,wi-1)。

然后，主節(jié)點(diǎn)發(fā)送ComputeBestSplitRequest給節(jié)點(diǎn)wi， 該節(jié)點(diǎn)通過掃描第i維的邊緣分布，即可獨(dú)立計(jì)算出第i維最好的分割。節(jié)點(diǎn)wi通過ComputeBestSplitResponse答復(fù)主節(jié)點(diǎn)，消息中包含分割位置和WCSS下降值。

當(dāng)主節(jié)點(diǎn)獲取各維度ComputeBestSplitResponse后，即可優(yōu)選全局分割。此時(shí)，通過CH指標(biāo)判斷分割是否有效，如果有效，則主節(jié)點(diǎn)發(fā)送SplitRequest到每個(gè)從節(jié)點(diǎn)，含有劃分維度和位置；當(dāng)從節(jié)點(diǎn)收到SplitRequest時(shí)，生成兩個(gè)新塊，相應(yīng)的數(shù)據(jù)也被劃分到兩個(gè)塊中，然后，計(jì)算邊緣分布，并向主節(jié)點(diǎn)發(fā)送SplitResponse，該消息含有兩個(gè)新塊的C和S， 當(dāng)主節(jié)點(diǎn)收到了SplitResponse，計(jì)算兩個(gè)塊的WCSS，并將其加入隊(duì)列；如果無效，將該塊添加到最終塊列表中。然后，再從隊(duì)列中移出一塊，開始計(jì)算其全局邊緣分布。如果隊(duì)列為空，開始調(diào)整階段。

步驟3 此時(shí)主節(jié)點(diǎn)有一個(gè)列表，其含有劃分好的塊和塊的摘要信息。主節(jié)點(diǎn)存有每塊的范圍和包含的點(diǎn)數(shù)，因此，能夠計(jì)算塊的密度，通過密度即可檢測出候選異常塊。對于這些塊，需計(jì)算受限密度。為此，一個(gè)包含候選受限塊標(biāo)識(shí)、相應(yīng)受限范圍的RestrictedCountRequest發(fā)送給所有從節(jié)點(diǎn)，從節(jié)點(diǎn)在指定塊中掃描本地?cái)?shù)據(jù)，并計(jì)算每個(gè)受限范圍的點(diǎn)數(shù)，然后將計(jì)算結(jié)果通過RestrictedCountResponse發(fā)送給主節(jié)點(diǎn)。

當(dāng)主節(jié)點(diǎn)收到所有從節(jié)點(diǎn)發(fā)來的RestrictedCountResponse，即可確定哪些是異常塊。然后，主節(jié)點(diǎn)向從節(jié)點(diǎn)發(fā)送RefinementRequest，它包含簇的中心和半徑。從節(jié)點(diǎn)掃描所有樣本點(diǎn)，并將其分配到最近的簇中，否則，標(biāo)記異常點(diǎn)。同時(shí)更新每個(gè)簇的C和S，并將結(jié)果通過RefinementResponse發(fā)送給主節(jié)點(diǎn)。

步驟4 當(dāng)主節(jié)點(diǎn)收到所有從節(jié)點(diǎn)發(fā)來RefinementResponse后，即可計(jì)算全局C和S。此消息為凝聚階段奠定基礎(chǔ)，合并形成新簇。

步驟5 然后，主節(jié)點(diǎn)向從節(jié)點(diǎn)發(fā)送PerfectRequest消息，并包含新簇的中心和半徑。完善階段，每個(gè)從節(jié)點(diǎn)進(jìn)行再調(diào)整處理，類似首次調(diào)整階段，通過PerfectResponse向主節(jié)點(diǎn)發(fā)送更新后的C和S。 當(dāng)主節(jié)點(diǎn)收到來自從節(jié)點(diǎn)的所有消息后，聚類完成。

5 實(shí)驗(yàn)與分析

由于CLUBS‖和CLUBS采用了相同的理念，因此，CLUBS‖的精度等同于CLUBS。CLUBS的精度已經(jīng)驗(yàn)證比現(xiàn)有的聚類方法優(yōu)越，因此，這里不展示精度，而是重點(diǎn)驗(yàn)證并行聚類算法CLUBS‖應(yīng)用于大數(shù)據(jù)場景的有效性。

5.1 數(shù)據(jù)集及參數(shù)設(shè)置

實(shí)驗(yàn)采用了3個(gè)合成數(shù)據(jù)集，其數(shù)據(jù)點(diǎn)個(gè)數(shù)分別為107，108和109，維度在 [2,4,…,12] 范圍內(nèi)，簇?cái)?shù)在 [20,21,…,25] 范圍內(nèi)。各數(shù)據(jù)集根據(jù)域?qū)?如2000)、維度和簇?cái)?shù)隨機(jī)生成符合高斯分布的簇；為了測試算法的魯棒性，數(shù)據(jù)集隨機(jī)添加了噪聲點(diǎn)，數(shù)量在總點(diǎn)數(shù)的0至0.1倍。實(shí)驗(yàn)運(yùn)行環(huán)境包含16個(gè)計(jì)算機(jī)節(jié)點(diǎn)，節(jié)點(diǎn)配置為Intel Xeon 6230*2顆2.1 GHz CPU，64 GB內(nèi)存。

實(shí)驗(yàn)每次僅改變一個(gè)參數(shù)，測試使用1、2、4、8或16個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間。為了便于展示，在每次實(shí)驗(yàn)中，非變化參數(shù)默認(rèn)設(shè)置為：總點(diǎn)數(shù)為108，維度為16，簇?cái)?shù)為32，噪聲比率為0.1，因?yàn)樵撛O(shè)置被驗(yàn)證是最嚴(yán)格的測試。

5.2 參數(shù)敏感性及性能分析

圖3展示了CLUBS‖算法的運(yùn)行時(shí)間。正如預(yù)期，運(yùn)行時(shí)間隨著節(jié)點(diǎn)個(gè)數(shù)的增加而顯著減少，并且加速比幾乎與節(jié)點(diǎn)個(gè)數(shù)成線性關(guān)系，如運(yùn)行時(shí)間曲線所示。

圖3(a)展示了針對大規(guī)模數(shù)據(jù)，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，加速比幾乎保持恒定。實(shí)際上，采用1至2個(gè)節(jié)點(diǎn)是無法運(yùn)行109數(shù)據(jù)集，但是，在108規(guī)模上的結(jié)果清楚地表明了該算法針對相對較多的點(diǎn)具有很好的擴(kuò)展性，相反，如果數(shù)據(jù)點(diǎn)不太多(例如107)，相比本地計(jì)算，網(wǎng)絡(luò)通信對總開銷的影響更大，因此，節(jié)點(diǎn)從8到16，加速比降低。

圖3 CLUBS‖的敏感性測試

圖3(b)表明隨著節(jié)點(diǎn)個(gè)數(shù)的增加，加速比不受數(shù)據(jù)維度的影響，因?yàn)椴煌S度的曲線斜率幾乎相同。但是，運(yùn)行時(shí)間隨著維數(shù)的增加而增加，這也符CLUBS算法，與現(xiàn)存許多其它聚類算法一樣，計(jì)算成本隨著維度線性增加。

圖3(c)表明隨著節(jié)點(diǎn)個(gè)數(shù)的增加，簇?cái)?shù)對加速比影響不大。具體來說，簇?cái)?shù)少的數(shù)據(jù)集，加速比效果稍好，這是因?yàn)榇財(cái)?shù)多的數(shù)據(jù)集在分裂階段將花費(fèi)更多時(shí)間，此外，分裂階段也是節(jié)點(diǎn)間通信最多的階段。因此，雖然節(jié)點(diǎn)的本地工作負(fù)載沒有變化，但隨著簇?cái)?shù)的增加，交換邊緣分布所需時(shí)間增加，因?yàn)楸仨氝M(jìn)行更多的分割。此外，運(yùn)行時(shí)間也隨著簇?cái)?shù)的增加而增加。

圖3(d)展示了算法的抗噪能力非常優(yōu)秀，且運(yùn)行時(shí)間和加速比都對不同比例的噪聲不敏感。這是因?yàn)榧铀俦戎饕芄?jié)點(diǎn)間的通信影響，而節(jié)點(diǎn)間不需要交換數(shù)據(jù)，僅交換摘要信息(邊緣分布)，因此，加速比不依賴于處理的數(shù)據(jù)(噪聲或簇)。

5.3 CLUBS‖、K-means‖和Spark PIC的對比分析

為進(jìn)一步驗(yàn)證CLUBS‖的性能，實(shí)驗(yàn)將其與經(jīng)典的K-means 并行版K-means‖[9]和PIC的并行版Spark PIC[11]進(jìn)行了比較分析。圖4展示了3種算法處理大小不同數(shù)據(jù)集時(shí)的加速比。3個(gè)數(shù)據(jù)集均為16維，32簇，噪聲比為0.1。

圖4 CLUBS‖、K-means‖和Spark PIC的性能對比

如圖4所示，CLUBS‖的擴(kuò)展性更好，隨著節(jié)點(diǎn)個(gè)數(shù)的增加其運(yùn)行時(shí)間縮短得更快，也即加速比更大，尤其針對大數(shù)據(jù)集；并且CLUBS‖的表現(xiàn)總是優(yōu)于K-means‖和Spark PIC。這主要因?yàn)镃LUBS‖是基于Ad-hoc消息傳遞的算法，它通過使用針對該算法量身定制的協(xié)議，可以充分利用分布式計(jì)算資源。測試結(jié)果符合我們的理論目標(biāo)。

6 結(jié)束語

由于現(xiàn)實(shí)世界的需求和并行計(jì)算的盛行，傳統(tǒng)經(jīng)典的單機(jī)版聚類算法已無法適應(yīng)大數(shù)據(jù)時(shí)代的需要。因此，為了使得許多優(yōu)秀的聚類算法可擴(kuò)展并利用，本文基于并行計(jì)算和CLUBS算法提出了一種面向大數(shù)據(jù)的并行聚類算法CLUBS‖，并基于Ad-hoc消息傳遞給出了實(shí)現(xiàn)。結(jié)果表明所提改進(jìn)算法具有很好的擴(kuò)展性和魯棒性。同時(shí)，它的改進(jìn)超越經(jīng)典的并行聚類算法K-means‖和Spark PIC。作為未來的一項(xiàng)工作，我們計(jì)劃測試其它的高性能計(jì)算策略，以便進(jìn)一步改善算法的性能。