胡 健，徐鍇濱，毛伊敏+

1.江西理工大學(xué)信息工程學(xué)院，江西贛州341000

2.江西理工大學(xué)應(yīng)用科學(xué)學(xué)院信息工程系，江西贛州341000

1 引言

聚類算法是一種無(wú)監(jiān)督的學(xué)習(xí)算法，能夠根據(jù)數(shù)據(jù)對(duì)象的相關(guān)特征，將相似的對(duì)象歸為一類，而差別較大的數(shù)據(jù)對(duì)象則劃分到不同類中，因此聚類算法可以從樣本數(shù)據(jù)中發(fā)現(xiàn)潛在的分布模式，被廣泛應(yīng)用于文本分析、生物學(xué)、醫(yī)學(xué)、衛(wèi)星圖像分析等各種領(lǐng)域[1]。在聚類算法中，基于密度的聚類算法，如DBSCAN[2]（density-based spatial clustering of applications with noise）和OPTICS[3]算法，可以發(fā)現(xiàn)任意形狀的簇且對(duì)噪聲不敏感，受到人們的廣泛關(guān)注[4-6]。

隨著互聯(lián)網(wǎng)信息技術(shù)的不斷發(fā)展以及大數(shù)據(jù)時(shí)代的到來(lái)，使得大數(shù)據(jù)相較于傳統(tǒng)數(shù)據(jù)，具有了4V特性[7]——Volume（數(shù)量大）、Variety（種類多）、Velocity（速度快）、Value（價(jià)值密度低）。但是傳統(tǒng)的密度聚類算法所需的時(shí)間復(fù)雜度較高，只適用于較小規(guī)模的數(shù)據(jù)集，而在處理大數(shù)據(jù)時(shí)無(wú)疑會(huì)產(chǎn)生更龐大的計(jì)算復(fù)雜度[8]。因此，如何降低密度聚類算法的計(jì)算復(fù)雜度，將其應(yīng)用到大數(shù)據(jù)上，是個(gè)具有挑戰(zhàn)性的難題。

隨著Google開(kāi)發(fā)的MapReduce架構(gòu)的廣泛應(yīng)用，以Hadoop、Spark為代表的分布式計(jì)算架構(gòu)受到了越來(lái)越多的關(guān)注[9-10]。為了能進(jìn)一步降低密度聚類算法的計(jì)算復(fù)雜度，通過(guò)改進(jìn)傳統(tǒng)的密度聚類算法，并與分布式計(jì)算架構(gòu)相結(jié)合成為目前密度聚類算法研究的主要方向[11-14]。Li等人[15]首先提出了基于Map-Reduce下的并行DBSCAN算法，其使用MapReduce計(jì)算架構(gòu)，將數(shù)據(jù)分片后并行執(zhí)行DBSCAN算法形成局部簇，再通過(guò)增量的方式合并得到全局簇，實(shí)現(xiàn)了DBSCAN算法的并行化，然而該算法沒(méi)有提出有效方法來(lái)劃分?jǐn)?shù)據(jù)，合并局部簇的計(jì)算復(fù)雜度較高。Silva等人[16]提出了MapReduce下的分布式DBSCAN算法，根據(jù)特定場(chǎng)景劃分?jǐn)?shù)據(jù)，聚類簇的合并采用增量的方式，算法的時(shí)間復(fù)雜度較高，算法總體并行化效率較低。文獻(xiàn)[17-18]分別提出了基于Hadoop和基于Spark下的并行密度聚類算法，有效降低密度聚類算法的計(jì)算復(fù)雜度，同時(shí)分別給出了基于Hadoop和Spark下的數(shù)據(jù)劃分方案，但算法對(duì)數(shù)據(jù)進(jìn)行分區(qū)處理時(shí)未具體考慮數(shù)據(jù)特性，也沒(méi)有給出有效的局部簇合并生成全局簇的方法。

如何有效地劃分?jǐn)?shù)據(jù)，合并局部簇一直是密度聚類算法并行化的重要研究?jī)?nèi)容[19]。由于數(shù)據(jù)網(wǎng)格化能將空間數(shù)據(jù)劃分為有限數(shù)目的單元，落入同一網(wǎng)格的點(diǎn)可以被看作一個(gè)對(duì)象進(jìn)行處理，可以很好地解決數(shù)據(jù)劃分的問(wèn)題[20]。因此，He等人[21]提出MRDBSCAN（efficient parallel density-based clustering algorithm using MapReduce）算法，采用均勻劃分網(wǎng)格的方式將數(shù)據(jù)網(wǎng)格化，以網(wǎng)格單元作為對(duì)象并行執(zhí)行DBSCAN算法，最后合并這些網(wǎng)格對(duì)象得到全局簇。然而算法明顯存在兩個(gè)問(wèn)題：均勻劃分網(wǎng)格時(shí)，網(wǎng)格單元的大小實(shí)際難以確定，算法的聚類效果受網(wǎng)格單元大小的影響較大，導(dǎo)致算法的聚類效果不佳；另外，算法在合并局部簇時(shí)采用增量的方式，計(jì)算效率仍然較低。在此基礎(chǔ)上，文獻(xiàn)[22-23]分別提出了基于Hadoop下的H-DBSCAN算法和基于Spark下的S-DBSCAN算法，同樣是采用均分網(wǎng)格的方法來(lái)劃分?jǐn)?shù)據(jù)，不同的是它們通過(guò)加入網(wǎng)格邊界的擴(kuò)展，以此來(lái)提高聚類結(jié)果的精確度和局部簇的合并效率。為了能更有效地劃分網(wǎng)格，以及進(jìn)一步加快合并局部簇的效率，王興等人[24]提出增量并行化快速聚類算法IP-DBSCAN（incremental parallelization of fast clustering based on DBSCAN algorithm）。該算法主要分為三個(gè)階段：首先通過(guò)二分法和貪心算法對(duì)空間數(shù)據(jù)進(jìn)行合理網(wǎng)格化；其次進(jìn)行本地局部聚類，獲得局部簇候選集；最后使用R*-tree索引策略進(jìn)一步提高局部簇的合并速度。相較于其他按網(wǎng)格劃分?jǐn)?shù)據(jù)的并行密度聚類算法，IP-DBSCAN算法能更加合理地對(duì)數(shù)據(jù)進(jìn)行劃分，且在合并局部簇時(shí)加快了收斂速度，從而進(jìn)一步加快了算法的并行化效率。然而該算法仍存在兩個(gè)明顯的不足：一方面，算法采用二分法劃分?jǐn)?shù)據(jù)時(shí)，仍需要輸入網(wǎng)格邊長(zhǎng)閾值，閾值的不同會(huì)影響算法的聚類結(jié)果準(zhǔn)確度，導(dǎo)致聚類結(jié)果的準(zhǔn)確度不高；另一方面，在進(jìn)行本地局部聚類時(shí)計(jì)算復(fù)雜度較高，在合并局部簇時(shí)沒(méi)有采用并行化的思想，算法總體并行化效率有待進(jìn)一步提升。針對(duì)上述算法存在的問(wèn)題，本文主要做了以下幾方面工作：（1）在數(shù)據(jù)劃分階段，根據(jù)空間中數(shù)據(jù)點(diǎn)的分布狀況，提出ADG（adaptive division grid）策略來(lái)自適應(yīng)劃分網(wǎng)格。（2）在完成數(shù)據(jù)劃分之后，為提高局部聚類效果，針對(duì)每個(gè)數(shù)據(jù)分區(qū)，提出NE（neighboring expand）策略構(gòu)建其加權(quán)網(wǎng)格用于加強(qiáng)網(wǎng)格之間的關(guān)聯(lián)性；同時(shí)提出WGIE（weighted grid and information entropy）策略來(lái)計(jì)算網(wǎng)格密度以及密度聚類算法的ε鄰域和核心對(duì)象，使密度聚類算法更適用于加權(quán)網(wǎng)格；最后為解決并行密度聚類算法對(duì)局部簇的計(jì)算效率較低的問(wèn)題，提出基于MapReduce的并行局部簇聚類算法COMCORE-MR（core clusters computing algorithm based on MapReduce）。（3）在局部聚類完成后，為進(jìn)一步加快局部簇合并的收斂速度，提出了基于并查集的局部簇合并算法MECORE（merge core cluster）；接著結(jié)合MapReduce計(jì)算模型，提出了基于MapReduce的并行化合并局部簇算法MECORE-MR（merge core cluster by using MapReduce），實(shí)現(xiàn)并行化合并局部簇，從而進(jìn)一步提升算法總體并行化效率，更快地獲取聚類結(jié)果的全局簇，提升了并行密度聚類算法對(duì)局部簇合并效率。

2 算法及相關(guān)概念介紹

2.1 加權(quán)網(wǎng)格

加權(quán)網(wǎng)格[20]表示為WG=(G,N(G),W)，其中G=gi表示一個(gè)網(wǎng)格單元，N(G)=N(gi)表示與網(wǎng)格單元gi相關(guān)聯(lián)的其余網(wǎng)格單元集合，W=w(gi,N(gi))表示網(wǎng)格單元gi與其余網(wǎng)格單元的權(quán)值。

2.2 均勻網(wǎng)格劃分

均勻網(wǎng)格劃分[25]的思想是：對(duì)于給定的數(shù)據(jù)空間，其維度為D，則將每一維的數(shù)據(jù)分成n個(gè)具有相同大小且互不相交的區(qū)間，因此D維數(shù)據(jù)空間就被劃分為nd個(gè)相等的網(wǎng)格單元。如圖1所示，若D=2，n=3，則該二維數(shù)據(jù)空間被劃分為9個(gè)相等的網(wǎng)格單元。

Fig.1 Uniform grid division圖1 均勻網(wǎng)格劃分

2.3 信息熵

對(duì)于一個(gè)離散型的變量X，其信息熵[26]公式為：

其中，p(x)為離散變量X在系統(tǒng)事件中出現(xiàn)的概率。

2.4 并查集

并查集[27]用一棵單獨(dú)的樹(shù)表示每一個(gè)集合，樹(shù)的根節(jié)點(diǎn)表示該集合的代表，樹(shù)的每個(gè)葉子節(jié)點(diǎn)表示集合中的一個(gè)元素。對(duì)于一組不相交的動(dòng)態(tài)集合X={x1,x2,…,xn}和Y={y1,y2,…,yn}，利用并查集對(duì)其進(jìn)行合并一般分為三個(gè)步驟：

makeset(X,Y)階段：分別將集合X和集合Y建立一個(gè)新的并查集，其中包含n個(gè)單元素集合。

find(x)階段：返回元素x所在集合的代表。

unionset(x,y)階段：若元素x和元素y所在的集合不相交，則合并x和y所在的集合。

3 DBWGIE-MR算法

3.1 算法思想

DBWGIE-MR（density-based clustering algorithm by using weighted grid and information entropy based on MapReduce）算法的思想是：（1）根據(jù)數(shù)據(jù)點(diǎn)空間分布狀況，提出ADG策略來(lái)自適應(yīng)劃分網(wǎng)格。（2）對(duì)每個(gè)數(shù)據(jù)分區(qū)，提出NE策略構(gòu)建其加權(quán)網(wǎng)格用于加強(qiáng)網(wǎng)格之間的關(guān)聯(lián)性，以此提高聚類效果；同時(shí)提出WGIE策略來(lái)計(jì)算網(wǎng)格密度以及密度聚類算法的ε鄰域和核心對(duì)象，使密度聚類算法更適用于加權(quán)網(wǎng)格；最后結(jié)合MapReduce計(jì)算模型，提出并行的局部簇聚類算法COMCORE-MR，解決并行密度聚類算法對(duì)局部簇的計(jì)算效率較低的問(wèn)題，從而提升算法的總體并行化效率。（3）在局部簇生成后，基于并查集的合并方法，提出了基于并查集的局部簇合并算法MECORE，用于加快合并局部簇的收斂速度；接著結(jié)合MapReduce計(jì)算模型，提出了基于MapReduce的并行化合并局部簇算法MECORE-MR，實(shí)現(xiàn)并行化合并局部簇，從而進(jìn)一步提升算法總體并行化效率，實(shí)現(xiàn)了并行化地合并局部簇，從而更快地得到聚類結(jié)果的全局簇，提升了基于密度的聚類算法對(duì)局部簇合并的效率。

3.2 數(shù)據(jù)劃分

目前基于網(wǎng)格劃分?jǐn)?shù)據(jù)的并行化密度聚類算法中，對(duì)于網(wǎng)格的劃分往往是采用均勻劃分的方式，即在數(shù)據(jù)的某一維度上進(jìn)行等分，這種劃分方式存在兩個(gè)缺陷：（1）網(wǎng)格邊長(zhǎng)選取的不確定性，即劃分?jǐn)?shù)據(jù)時(shí)網(wǎng)格的初始邊長(zhǎng)難以確定，邊長(zhǎng)大小的選取對(duì)于聚類效果的影響較大；（2）網(wǎng)格數(shù)據(jù)密度不一致性，即在數(shù)據(jù)網(wǎng)格化時(shí)未考慮大數(shù)據(jù)環(huán)境下數(shù)據(jù)的分布特性，導(dǎo)致劃分后的網(wǎng)格數(shù)據(jù)密度存在不均勻的情況。針對(duì)這些問(wèn)題，本文提出了ADG策略用于將數(shù)據(jù)自適應(yīng)地劃分為網(wǎng)格。ADG策略的描述如下：

先將d維數(shù)據(jù)空間等分為2d個(gè)初始網(wǎng)格單元，再根據(jù)網(wǎng)格中數(shù)據(jù)點(diǎn)之間分布狀況來(lái)計(jì)算網(wǎng)格邊長(zhǎng)的劃分閾值φ。當(dāng)所有網(wǎng)格滿足非空且當(dāng)前邊長(zhǎng)大于劃分閾值時(shí)，則停止網(wǎng)格劃分。網(wǎng)格邊長(zhǎng)劃分閾值φ的取值需要根據(jù)當(dāng)前最小網(wǎng)格中的點(diǎn)個(gè)數(shù)和數(shù)據(jù)點(diǎn)分布的緊密程度，當(dāng)網(wǎng)格單元中的數(shù)據(jù)點(diǎn)個(gè)數(shù)過(guò)多或者分布過(guò)于稀疏，則需要進(jìn)一步劃分網(wǎng)格，而數(shù)據(jù)點(diǎn)之間的最小平均距離可以體現(xiàn)當(dāng)前網(wǎng)格中整體數(shù)據(jù)分布的狀況，故閾值φ的計(jì)算公式如下：

其中，pi和pj分別為d維空間中的任意兩個(gè)數(shù)據(jù)點(diǎn)，μ為當(dāng)前最小網(wǎng)格單元中的點(diǎn)個(gè)數(shù)。

ADG策略首先將整體空間劃分為大小相同的數(shù)據(jù)網(wǎng)格，再對(duì)每一個(gè)網(wǎng)格做進(jìn)一步細(xì)分，故其特點(diǎn)是將均勻網(wǎng)格劃分與自適應(yīng)網(wǎng)格劃分相結(jié)合，從全局上數(shù)據(jù)網(wǎng)格的劃分是非均勻的，而從局部上數(shù)據(jù)網(wǎng)格呈現(xiàn)的是均勻劃分的狀態(tài)。此外，由于ADG策略綜合考慮了每個(gè)網(wǎng)格單元的數(shù)據(jù)點(diǎn)的數(shù)量及其分布特性，通過(guò)計(jì)算密度閾值，能對(duì)數(shù)據(jù)點(diǎn)較多的網(wǎng)格單元做進(jìn)一步的細(xì)分，直到每個(gè)數(shù)據(jù)網(wǎng)格均滿足密度閾值才會(huì)停止劃分，因此最后得到的網(wǎng)格單元密度較為均勻，這樣保證了算法計(jì)算節(jié)點(diǎn)的負(fù)載平衡，也為局部聚類的算法穩(wěn)定性提供了保障。

3.3 局部簇形成

目前基于網(wǎng)格劃分的并行化密度聚類算法中，局部簇的形成是通過(guò)在每個(gè)網(wǎng)格對(duì)象中并行執(zhí)行聚類算法獲得的，這種方式存在兩個(gè)問(wèn)題：一是在聚類過(guò)程中未能充分考慮到相鄰網(wǎng)格之間數(shù)據(jù)的關(guān)聯(lián)性，導(dǎo)數(shù)聚類效果不好；二是算法的計(jì)算復(fù)雜度較高，對(duì)局部簇的計(jì)算效率較低。針對(duì)這些問(wèn)題，本文首先基于鄰居網(wǎng)格和網(wǎng)格邊界擴(kuò)展原理，提出NE策略來(lái)構(gòu)建每個(gè)數(shù)據(jù)分區(qū)的加權(quán)網(wǎng)格，加強(qiáng)網(wǎng)格之間的關(guān)聯(lián)性，以此來(lái)提高聚類效果；同時(shí)，提出WGIE策略來(lái)計(jì)算網(wǎng)格對(duì)象的密度值，并重定義ε鄰域和核心對(duì)象，使密度聚類算法更適用于加權(quán)網(wǎng)格；最后結(jié)合MapReduce計(jì)算模型，提出并行的局部簇聚類算法COMCORE-MR，解決并行密度聚類算法對(duì)局部簇的計(jì)算效率較低的問(wèn)題，以此來(lái)提升算法的總體并行化效率。

3.3.1 加權(quán)網(wǎng)格構(gòu)建

在對(duì)數(shù)據(jù)進(jìn)行網(wǎng)格化處理后，為了能在聚類過(guò)程中考慮到相鄰網(wǎng)格之間數(shù)據(jù)的關(guān)聯(lián)性，進(jìn)一步提升聚類效果，本文提出了NE策略來(lái)構(gòu)建每個(gè)數(shù)據(jù)分區(qū)的加權(quán)網(wǎng)格，加強(qiáng)網(wǎng)格之間的關(guān)聯(lián)性，以此來(lái)提高聚類效果。NE策略的描述如下：

首先對(duì)加權(quán)網(wǎng)格的作用范圍進(jìn)行設(shè)置。為更好地確定加權(quán)網(wǎng)格的作用范圍，基于網(wǎng)格對(duì)象的鄰居網(wǎng)格[28]，加權(quán)網(wǎng)格的作用范圍定義如下：

NE策略通過(guò)構(gòu)建每個(gè)網(wǎng)格對(duì)象的加權(quán)網(wǎng)格，使得算法在對(duì)每個(gè)網(wǎng)格對(duì)象進(jìn)行局部聚類的過(guò)程中，不再是單一地考慮每個(gè)網(wǎng)格對(duì)象內(nèi)部的數(shù)據(jù)關(guān)系，而是能根據(jù)每個(gè)網(wǎng)格對(duì)象的加權(quán)網(wǎng)格，綜合考慮了相鄰網(wǎng)格簇之間的連通關(guān)系以及權(quán)重關(guān)系。這樣既避免了算法容易陷入局部最優(yōu)，同時(shí)提高了聚類結(jié)果的精確度。

例1如圖2所示，在該數(shù)據(jù)網(wǎng)格中有16個(gè)網(wǎng)格單元，數(shù)據(jù)的維度為2。

Fig.2 Construction of weighted grid圖2 加權(quán)網(wǎng)格的構(gòu)建

3.3.2 網(wǎng)格密度的計(jì)算

目前基于網(wǎng)格劃分的并行化密度聚類算法中，網(wǎng)格密度的計(jì)算是使用網(wǎng)格中的數(shù)據(jù)點(diǎn)個(gè)數(shù)作為該網(wǎng)格對(duì)象的密度值，雖然這種密度表示方法在大多數(shù)基于密度的聚類問(wèn)題中取得了較好效果，但在基于加權(quán)網(wǎng)格的密度聚類問(wèn)題中，由于不同網(wǎng)格對(duì)象之間存在著關(guān)聯(lián)性，因此直接使用網(wǎng)格中的數(shù)據(jù)點(diǎn)個(gè)數(shù)來(lái)計(jì)算加權(quán)網(wǎng)格中的網(wǎng)格密度，有失合理性。在構(gòu)建好網(wǎng)格對(duì)象的加權(quán)網(wǎng)格之后，為使密度聚類算法能更好地應(yīng)用于加權(quán)網(wǎng)格，本文提出WGIE（加權(quán)網(wǎng)格信息熵）策略用于計(jì)算網(wǎng)格單元的密度，并重新定義密度聚類算法的ε鄰域和核心對(duì)象。WGIE策略定義如下：

其中，t表示數(shù)據(jù)網(wǎng)格化后的某一非空網(wǎng)格單元的密度，即以該網(wǎng)格單元為中心構(gòu)成的加權(quán)網(wǎng)格中的所有數(shù)據(jù)點(diǎn)個(gè)數(shù)；x表示該密度取值下的網(wǎng)格單元數(shù)量；P(t)是網(wǎng)格單元密度為t所出現(xiàn)的概率；count(t)表示網(wǎng)格單元中網(wǎng)格密度為t的網(wǎng)格單元個(gè)數(shù)；count(n)表示劃分后的非空網(wǎng)格單元總數(shù)。

證明（1）單調(diào)性：對(duì)于?t1,t2且t1-t2＞0，P(t1)-P(t2)＞0，則H′(P(t1))-H′(P(t2))＜0。

（2）非負(fù)性：因?yàn)? ＜P(t)，lbP(t)＜0，所以0 ＜，即H′(X)＞0。

（3）累加性：對(duì)于?t1,t2∈t，H′(P(t))=H′(P(t1,t2))=H′(P(t1)×P(t2))=H′(P(t1))+H′(P(t2))。

因此公式滿足信息熵定義的基本條件，是系統(tǒng)穩(wěn)定程度的度量公式。□

為使密度聚類算法更好地應(yīng)用于加權(quán)網(wǎng)格，根據(jù)加權(quán)網(wǎng)格的作用范圍和加權(quán)網(wǎng)格信息熵策略來(lái)重定義ε鄰域和核心對(duì)象。核心對(duì)象與網(wǎng)格單元的密度值密切相關(guān)，采用加權(quán)網(wǎng)格與信息熵策略能有效刻畫(huà)加權(quán)網(wǎng)格中網(wǎng)格對(duì)象的密度值，當(dāng)網(wǎng)格單元的密度H′(X)小于給定的密度閾值μ時(shí)，則說(shuō)明以該網(wǎng)格單元為中心的加權(quán)網(wǎng)格中的數(shù)據(jù)是比較有序的，因此執(zhí)行聚類算法的過(guò)程中以該網(wǎng)格單元作為中心效果會(huì)更好，該網(wǎng)格單元中成為核心對(duì)象的概率越大。ε鄰域和核心對(duì)象定義如下：

定義1（加權(quán)網(wǎng)格的ε鄰域）對(duì)于一個(gè)網(wǎng)格對(duì)象gi，以該網(wǎng)格對(duì)象為中心構(gòu)建加權(quán)網(wǎng)格后，加權(quán)網(wǎng)格范圍內(nèi)的所有網(wǎng)格對(duì)象為網(wǎng)格對(duì)象gi的ε鄰域。

定義2（加權(quán)網(wǎng)格的核心對(duì)象）對(duì)于一個(gè)網(wǎng)格對(duì)象gi，若其密度滿足H′(X)≤μ（即加權(quán)網(wǎng)格信息熵小于給定的閾值），則該網(wǎng)格對(duì)象為核心網(wǎng)格對(duì)象。包含在核心網(wǎng)格內(nèi)的任一點(diǎn)均為核心對(duì)象。

3.3.3 局部聚類

在提出了網(wǎng)格對(duì)象的密度計(jì)算方法之后，為了能更快地進(jìn)行局部聚類，進(jìn)一步加快算法的總體并行化效率，本文提出基于MapReduce的并行化計(jì)算局部簇的COMCORE-MR算法。該算法主要分為兩個(gè)階段，并行計(jì)算網(wǎng)格密度階段和并行計(jì)算局部簇階段。

先在并行計(jì)算網(wǎng)格密度階段，需要輸入網(wǎng)格對(duì)象g以及網(wǎng)格中的點(diǎn)pi；接著，執(zhí)行map函數(shù)計(jì)算出以網(wǎng)格對(duì)象g為中心的加權(quán)網(wǎng)格中點(diǎn)的數(shù)量Ci[g]，并輸出Key-value值＜g,Ci[g]＞。之后，執(zhí)行reduce函數(shù)合并map函數(shù)的結(jié)果，并使用WGIE策略計(jì)算出每個(gè)網(wǎng)格對(duì)象的網(wǎng)格密度hi，最后輸出Key-value值＜(g,N(gi)),hi＞傳入下一個(gè)階段。如圖3（a）所示。

接著在并行計(jì)算局部簇階段，需要輸入數(shù)據(jù)集D中的點(diǎn)pi以及上個(gè)階段計(jì)算出的Key-value值＜(g,N(gi)),hi＞；之后，調(diào)用map函數(shù)對(duì)數(shù)據(jù)進(jìn)行計(jì)算，如果輸入的數(shù)據(jù)為數(shù)據(jù)點(diǎn)pi，則map函數(shù)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)所對(duì)應(yīng)的網(wǎng)格對(duì)象g并輸出Key-value值＜g,pi＞，如果輸入的數(shù)據(jù)為Key-value值＜(g,N(gi)),hi＞，則map函數(shù)根據(jù)定義2計(jì)算當(dāng)前網(wǎng)格對(duì)象g是否為核心網(wǎng)格，如果hi≤μ，則當(dāng)前網(wǎng)格對(duì)象g為核心網(wǎng)格，輸出Key-value值＜g,N(gi)＞，如果hi＞μ，則不輸出任何結(jié)果；最后執(zhí)行reduce函數(shù)，合并map函數(shù)的結(jié)果，輸出Key-value值＜(g,N(gi)),N(pi)＞。最終得到的結(jié)果便是核心簇的序列集合，即聚類結(jié)果的局部簇。如圖3（b）所示。

Fig.3 Process of COMCORE-MR algorithm圖3 COMCORE-MR算法的計(jì)算過(guò)程

3.4 局部簇的合并

目前基于網(wǎng)格劃分的密度聚類算法中，對(duì)局部簇的合并通常是采取增量的方式，并且沒(méi)采取并行化思想，導(dǎo)致算法在合并局部簇時(shí)計(jì)算復(fù)雜度較高，算法總體并行化效率較低。針對(duì)這些問(wèn)題，本文首先提出了基于并查集的局部簇合并算法（MECORE），用于加快合并局部簇的收斂速度；接著結(jié)合MapReduce計(jì)算模型，提出了基于MapReduce的并行化合并局部簇算法（MECORE-MR），實(shí)現(xiàn)并行化合并局部簇，從而進(jìn)一步提升算法總體并行化效率。

3.4.1 局部簇的合并

為進(jìn)一步加快合并局部簇的收斂速度，本文提出了基于并查集的合并局部簇算法（MECORE），該算法首先基于并查集對(duì)兩個(gè)不相交集的合并方法，提出了基于并查集的合并不同網(wǎng)格對(duì)象的3個(gè)方法：Makeset、Find、Unionset。Makeset方法先將每個(gè)不同的網(wǎng)格對(duì)象單獨(dú)處理為一個(gè)樹(shù)葉節(jié)點(diǎn)；Find方法將處于同一局部簇中的網(wǎng)格對(duì)象節(jié)點(diǎn)相連接，返回一棵以根節(jié)點(diǎn)為代表的樹(shù)，簇的核心網(wǎng)格對(duì)象作為根節(jié)點(diǎn)，而局部簇中的其他網(wǎng)格對(duì)象作為葉節(jié)點(diǎn)，所有的葉節(jié)點(diǎn)都與根節(jié)點(diǎn)連接；Unionset方法是將兩個(gè)不同的局部簇進(jìn)行合并，尋找共同的葉子節(jié)點(diǎn)，將其中一棵樹(shù)的根節(jié)點(diǎn)轉(zhuǎn)換為另一棵樹(shù)的葉子節(jié)點(diǎn)。接著使用這3個(gè)方法對(duì)局部簇進(jìn)行合并。算法的總體步驟如下：

對(duì)于所有的局部簇對(duì)象，將這些局部簇對(duì)象所構(gòu)成的表R作為合并局部簇算法的輸入，表的每一項(xiàng)都是核心網(wǎng)格對(duì)象g以及核心網(wǎng)格的鄰域N(g)。首先，算法初始化每一個(gè)非空網(wǎng)格對(duì)象g∈G，將其看作一個(gè)單獨(dú)的簇，每一個(gè)網(wǎng)格對(duì)象的狀態(tài)都被初始化為unvisited，并且在算法執(zhí)行之后每個(gè)網(wǎng)格對(duì)象的狀態(tài)將變?yōu)閡nvisited、non-core和core這3個(gè)狀態(tài)之一。接著，在輸入局部簇所構(gòu)成的表后，算法檢索每一個(gè)核心網(wǎng)格對(duì)象g的Key-value值＜g,N(gi)＞，將其狀態(tài)由unvisited更改為core，之后要對(duì)其鄰域內(nèi)的網(wǎng)格對(duì)象N(g)的狀態(tài)進(jìn)行設(shè)置，分為以下幾種情況：

如果在N(g) 中的一個(gè)網(wǎng)格對(duì)象gi的狀態(tài)為non-core，則表示當(dāng)前的網(wǎng)格對(duì)象gi已經(jīng)分配到了另一個(gè)簇中，因此網(wǎng)格對(duì)象gi的狀態(tài)保持不變。

如果在N(g)中的一個(gè)網(wǎng)格對(duì)象gi的狀態(tài)為core，則將以gi為核心的局部簇合并到g的局部簇中。

如果在N(g) 中的一個(gè)網(wǎng)格對(duì)象gi的狀態(tài)為unvisited，則將其加入到以g為核心的局部簇中，并將gi的狀態(tài)變更為non-core。

最后，在算法執(zhí)行完之后，根據(jù)數(shù)據(jù)點(diǎn)和網(wǎng)格ID的相對(duì)應(yīng)，便能得到聚類的全局簇，而被標(biāo)記為unvisited的網(wǎng)格對(duì)象中的數(shù)據(jù)點(diǎn)便是離群點(diǎn)(outlier)。

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

3.4.2 局部簇的并行化合并

基于并查集的局部簇合并算法可以很好地對(duì)局部簇進(jìn)行合并得到聚類的全局簇。為了進(jìn)一步提高合并局部簇的效率，解決基于密度的并行化聚類算法中沒(méi)有并行化合并局部簇的問(wèn)題，本文提出了基于MapReduce的并行化合并局部簇的MECORE-MR算法。MECORE-MR算法的步驟如下：

算法需要將網(wǎng)格對(duì)象集G、數(shù)據(jù)集D以及表R作為輸入，其中表R中的數(shù)據(jù)是COMCORE-MR算法計(jì)算出的局部簇?cái)?shù)據(jù)。該算法首先隨機(jī)地將網(wǎng)格對(duì)象集合G劃分為數(shù)量相近的k個(gè)部分G1,G2,…,Gk，同時(shí)將表R也劃分為k個(gè)部分R1,R2,…,Rk，其中k的值對(duì)應(yīng)了執(zhí)行算法所需要的并行節(jié)點(diǎn)數(shù)；接著，執(zhí)行map函數(shù)，如果map函數(shù)輸入的數(shù)據(jù)為數(shù)據(jù)點(diǎn)pi∈D，則map函數(shù)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)所對(duì)應(yīng)的網(wǎng)格對(duì)象g并輸出Key-value值＜g,pi＞；如果輸入的數(shù)據(jù)為表R中的局部簇?cái)?shù)據(jù)，則檢索該局部簇的核心網(wǎng)格對(duì)象的Key-value值＜g,N(gi)＞,根據(jù)Key值g在G1,G2,…,Gk中進(jìn)行索引，得到相應(yīng)的k值，將此核心網(wǎng)格對(duì)象的Key-value值分配到相應(yīng)的Rk中，并輸出Key-value值＜Mi,(g,N(gi))＞傳遞到reduce函數(shù)中去；最后執(zhí)行reduce函數(shù)，對(duì)于每個(gè)Mi，并行化執(zhí)行MECORE算法，將得到的k個(gè)合并結(jié)果最后執(zhí)行一次局部簇合并算法，再與＜g,pi＞進(jìn)行結(jié)合得到聚類全局簇。

在MECORE-MR算法中，通過(guò)并查集結(jié)構(gòu)對(duì)局部簇進(jìn)行合并的時(shí)間復(fù)雜度為O(i×n)，其中n為數(shù)據(jù)點(diǎn)個(gè)數(shù)，i為核心網(wǎng)格對(duì)象中點(diǎn)的極大值，因此其時(shí)間復(fù)雜度趨近于常量?？紤]到大數(shù)據(jù)環(huán)境下，n的值較大，通過(guò)結(jié)合MapReduce可以進(jìn)一步降低其時(shí)間復(fù)雜度，有效提升對(duì)局部簇的合并效率。

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

3.5 DBWGIE-MR算法的步驟

DBWGIE-MR算法具體實(shí)現(xiàn)步驟如下所示：

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

4.1 實(shí)驗(yàn)環(huán)境

為驗(yàn)證DBWGIE-MR算法的性能，本文設(shè)計(jì)了相關(guān)實(shí)驗(yàn)。實(shí)驗(yàn)的硬件設(shè)備為Master主機(jī)1臺(tái)和Slaver機(jī)3臺(tái)，共4個(gè)節(jié)點(diǎn)。每一臺(tái)硬件設(shè)備的處理器均為Intel?CoreTMi5-9400H CPU@2.9 GHz，內(nèi)存16 GB。實(shí)驗(yàn)的軟件編程環(huán)境均為python3.5.2；操作系統(tǒng)均為Ubuntu 16.04；MapReduce架構(gòu)均為Apache Hadoop3.2版本。

4.2 數(shù)據(jù)來(lái)源

DBWGIE-MR算法實(shí)驗(yàn)數(shù)據(jù)為4個(gè)人工合成的類簇，分別是Flame、Compound、Aggregation和D31。Flame[29]是一個(gè)包含凸數(shù)據(jù)集和凹數(shù)據(jù)集的密度簇，包含240個(gè)樣本點(diǎn)，如圖4（a）所示；Compound[30]是一個(gè)擁有6個(gè)不同形狀的復(fù)雜結(jié)構(gòu)密度簇，共有399個(gè)樣本點(diǎn)，這些簇之間存在著相連、內(nèi)嵌、包含和不同密度重疊的情況，如圖4（b）所示；Aggregation[31]擁有7個(gè)不同形狀的非高斯分布的密度簇，共有788個(gè)樣本點(diǎn)，如圖4（c）所示；D31[32]則擁有31個(gè)高斯密度簇，如圖4（d）所示。

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

為驗(yàn)證DBWGIE-MR算法對(duì)數(shù)據(jù)集的聚類精確度，采用F-measure對(duì)聚類算法的結(jié)果進(jìn)行評(píng)價(jià)，F(xiàn)measure是正確率(precision)和召回率(recall)的加權(quán)平均值，計(jì)算方法如下：

通常情況下，參數(shù)λ設(shè)置為1，F(xiàn)-measure綜合考慮了聚類結(jié)果的正確率（precision）和召回率（recall）的情況，能夠較為準(zhǔn)確地評(píng)價(jià)聚類算法的結(jié)果，當(dāng)Fmeasure的值較高時(shí)，說(shuō)明聚類結(jié)果更為準(zhǔn)確合理。

4.4 參數(shù)選取

DBWGIE-MR算法通過(guò)使用ADG策略，自適應(yīng)劃分?jǐn)?shù)據(jù)空間，并且使用NE策略和WGIE策略來(lái)計(jì)算網(wǎng)格對(duì)象的密度值，但對(duì)于密度閾值μ來(lái)說(shuō)，仍需要指定具體的值。為了使DBWGIE-MR算法能獲得更加準(zhǔn)確的聚類結(jié)果，需要對(duì)密度閾值μ的取值進(jìn)行合理的設(shè)置，本文在基于Flame數(shù)據(jù)集下，保證其他參數(shù)不變，將密度閾值μ的取值設(shè)置為[1,12]，獨(dú)立運(yùn)行10次，取10次的F-measure均值進(jìn)行分析。從圖5中可以看出，密度閾值μ的值給定得太小或者太大都會(huì)影響聚類結(jié)果的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，在μ的值取5的時(shí)候，能得到較為準(zhǔn)確的聚類結(jié)果。

4.5 NE策略和WGIE策略的有效性分析

Fig.4 Dataset of experiment圖4 實(shí)驗(yàn)數(shù)據(jù)集

Fig.5 Selection of density value圖5 密度閾值的選取

為驗(yàn)證NE策略和WGIE策略進(jìn)行局部聚類的有效性，實(shí)驗(yàn)中利用本文算法DBWGIE-MR，分別采用不同的局部聚類方式，比較在不同聚類數(shù)目下的Fmeasure值的變化。將MR-DBSCAN[21]、H-DBSCAN[22]算法中的局部聚類方法與本文的基于NE策略和WGIE策略的局部聚類方式進(jìn)行對(duì)比實(shí)驗(yàn)，圖6為運(yùn)行次數(shù)在[0,10]范圍內(nèi)變化時(shí)，分別采用3種不同的局部聚類方式的聚類效果。

Fig.6 Comparison of results in different local cluster algorithms圖6 不同局部聚類方式下的聚類效果比較

從圖6中可以看出，本文通過(guò)NE策略和WGIE策略，以加權(quán)網(wǎng)格的方式進(jìn)行局部聚類的效果明顯優(yōu)于采用MR-DBSCAN和H-DBSCAN算法的局部聚類方式。當(dāng)采用這3種不同的局部聚類方式的聚類效果相差最大時(shí)，DBWGIE-MR算法使用基于NE策略和WGIE策略的方式進(jìn)行聚類時(shí)，F(xiàn)-measure要比采用MR-DBSCAN和H-DBSCAN算法的局部聚類方式分別高出17.8%和8.3%。由于MR-DBSCAN的局部聚類過(guò)程是在單一的網(wǎng)格單元中進(jìn)行，使得聚類過(guò)程僅考慮到網(wǎng)格對(duì)象內(nèi)部的數(shù)據(jù)關(guān)系，而孤立了不同網(wǎng)格中的數(shù)據(jù)關(guān)系，這種局部聚類方式考慮得不夠全面，比較單一，容易使算法陷入局部最優(yōu)，因此其F-measure值相對(duì)較低。H-DBSCAN算法的局部聚類方式是建立在MR-DBSCAN基礎(chǔ)上，在單一的網(wǎng)格單元中進(jìn)行局部聚類之后，再根據(jù)網(wǎng)格之間的共同邊界點(diǎn)，對(duì)網(wǎng)格邊界進(jìn)行二次擴(kuò)展，考慮了相鄰網(wǎng)格簇之間的連通關(guān)系，因此其F-measure值優(yōu)于MR-DBSCAN。但是這種改進(jìn)方式是在每個(gè)網(wǎng)格單元完成局部聚類之后再進(jìn)行重聚類，其聚類效果有待進(jìn)一步提升。而DBWGIE-MR算法采用NE策略和WGIE策略，構(gòu)建了每個(gè)網(wǎng)格對(duì)象的加權(quán)網(wǎng)格，并以加權(quán)網(wǎng)格的聚類方式，在局部聚類的整個(gè)過(guò)程中綜合考慮了相鄰網(wǎng)格簇之間的連通關(guān)系以及權(quán)重關(guān)系，對(duì)網(wǎng)格簇之間的關(guān)系分析得較為全面，因此采用NE策略和WGIE策略進(jìn)行聚類的效果較好。

4.6 聚類結(jié)果的比較分析

為驗(yàn)證DBWGIE-MR算法聚類結(jié)果的精準(zhǔn)度，本文在基于Flame、Compound、Aggregation和D31的數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)，根據(jù)聚類結(jié)果的最優(yōu)值、精確度、方差和運(yùn)行時(shí)間，分別與MR-DBSCAN[21]算法和H-DBSCAN[22]算法的性能進(jìn)行綜合比較。聚類結(jié)果的最優(yōu)值能夠反映算法尋優(yōu)能力的強(qiáng)弱程度，值越小表示尋找局部簇的能力越強(qiáng)；精確度可直觀地反映算法聚類結(jié)果的好壞程度；運(yùn)行算法20次得到聚類結(jié)果的方差能夠表示算法的穩(wěn)定程度，值越小表示算法越穩(wěn)定；運(yùn)行時(shí)間表示得到聚類結(jié)果所花費(fèi)的時(shí)間。實(shí)驗(yàn)結(jié)果如表1所示。

從表1中可以看出，MR-DBSCAN算法的聚類效果較差，而H-DBSCAN算法的聚類效果比MRDBSCAN算法的聚類效果更好，尤其是在Flame數(shù)據(jù)集上精確度提升了0.046。因?yàn)槠湓跀?shù)據(jù)網(wǎng)格化的基礎(chǔ)上加入了對(duì)網(wǎng)格邊界點(diǎn)的處理，在一定程度上克服了MR-DBSCAN算法沒(méi)有考慮網(wǎng)格之間關(guān)聯(lián)性的缺陷，具有一定的尋優(yōu)能力。但由于采用的是均分網(wǎng)格的數(shù)據(jù)網(wǎng)格化方法，沒(méi)有考慮到數(shù)據(jù)點(diǎn)的分布狀況，因此H-DBSCAN算法的穩(wěn)定性均不佳。而DBWGIE-MR算法在穩(wěn)定性的表現(xiàn)上比MR-DBSCAN和H-DBSCAN算法更佳，說(shuō)明DBWGIE-MR克服了以上算法的缺陷，采用ADG策略自適應(yīng)地將數(shù)據(jù)劃分為密度較為均勻的網(wǎng)格單元，保證了數(shù)據(jù)網(wǎng)格化的合理性，對(duì)算法計(jì)算節(jié)點(diǎn)的負(fù)載平衡起到一定的幫助，算法聚類過(guò)程的波動(dòng)性較低，因此算法穩(wěn)定性更好，DBWGIE-MR算法的方差較低；與此同時(shí)，通過(guò)采用NE策略以及WGIE策略構(gòu)建加權(quán)網(wǎng)格以及形成加權(quán)網(wǎng)格的局部聚類方式，使得局部聚類的過(guò)程中能綜合考慮到不同網(wǎng)格對(duì)象之間的關(guān)聯(lián)度，避免了算法陷入局部最優(yōu)，使得DBWGIE-MR算法具有較強(qiáng)的尋優(yōu)能力，因此DBWGIE-MR算法的最優(yōu)值最?。淮送?，DBWGIE-MR算法的運(yùn)行時(shí)間比起MRDBSCAN和H-DBSCAN算法，在Flame數(shù)據(jù)集上分別降低了0.47 s和0.89 s，原因是DBWGIE-MR算法采用了并行化合并局部簇算法MECORE-MR算法，加快了合并局部簇的收斂速度，因此DBWGIE-MR算法對(duì)聚類過(guò)程的執(zhí)行速度得到提升。

Table 1 Comparison of results in different clustering algorithms表1 各算法的聚類結(jié)果比較分析

4.7 算法性能的比較分析

為驗(yàn)證DBWGIE-MR算法在大數(shù)據(jù)環(huán)境下的運(yùn)行性能，實(shí)驗(yàn)數(shù)據(jù)在基于D31數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)，首先將D31數(shù)據(jù)集中的點(diǎn)數(shù)量進(jìn)行擴(kuò)充，構(gòu)造成行數(shù)為300萬(wàn)行（0.6 GB）、500萬(wàn)行（1 GB）、1 100萬(wàn)行（2 GB）、1 600萬(wàn)行（3 GB）的大數(shù)據(jù)集。同時(shí)，為驗(yàn)證算法在Hadoop并行化框架下的計(jì)算能力，采用算法的加速比進(jìn)行衡量。算法的加速比是指通過(guò)并行化計(jì)算使得算法的運(yùn)行時(shí)間降低從而得到的性能提升，加速比通常被作為檢驗(yàn)并行化算法性能的重要指標(biāo)。在不同數(shù)據(jù)集規(guī)模下，DBWGIE-MR算法的實(shí)驗(yàn)結(jié)果如圖7所示。

Fig.7 Acceleration rate of algorithm on different computing nodes圖7 算法在不同計(jì)算節(jié)點(diǎn)下的加速比

從圖7中可以看出，DBWGIE-MR算法在處理大數(shù)據(jù)集上具有很好的加速比。在一開(kāi)始數(shù)據(jù)集較小時(shí)，如圖中的0.6 GB數(shù)據(jù)量所示，隨著計(jì)算節(jié)點(diǎn)數(shù)量的增加，加速比趨近于1.0，甚至在節(jié)點(diǎn)4時(shí)，出現(xiàn)了下降的趨勢(shì)，加速比降低了0.2，這是由于在數(shù)據(jù)集的規(guī)模較小時(shí)，數(shù)據(jù)量遠(yuǎn)小于集群所處理的數(shù)據(jù)量，將數(shù)據(jù)分散到不同的計(jì)算節(jié)點(diǎn)中產(chǎn)生了不同的時(shí)間開(kāi)銷，包括集群運(yùn)行時(shí)間、任務(wù)調(diào)度時(shí)間、節(jié)點(diǎn)存儲(chǔ)時(shí)間等，這些開(kāi)銷降低了算法的計(jì)算速度，因此在這種情況下的并行效果是較低的；而在數(shù)據(jù)規(guī)模達(dá)到3.0 GB時(shí)，算法在4個(gè)節(jié)點(diǎn)下計(jì)算的加速比為4.6，比在1個(gè)節(jié)點(diǎn)下計(jì)算提高了3.6，原因是隨著數(shù)據(jù)集規(guī)模的逐步增加，算法的能夠并行化計(jì)算局部簇和合并局部簇的優(yōu)點(diǎn)逐漸被放大，使得算法在計(jì)算節(jié)點(diǎn)增加的同時(shí)，加速比呈線性的增長(zhǎng)，算法的并行化效果得到很大的提升。這也表明DBWGIE-MR算法適用于處理較大規(guī)模的數(shù)據(jù)集，并且隨著計(jì)算節(jié)點(diǎn)的增長(zhǎng)，并行化的效果更佳。

為進(jìn)一步驗(yàn)證DBWGIE-MR算法在大數(shù)據(jù)下的并行化性能，將DBWGIE-MR算法的運(yùn)行時(shí)間分別與MR-DBSCAN[21]、IP-DBSCAN[24]算法進(jìn)行比較，所有的算法都是基于擴(kuò)充后的D31數(shù)據(jù)集以及相同的并行計(jì)算節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果如圖8所示。

Fig.8 Running time of algorithm in different data sets圖8 算法在不同數(shù)據(jù)集規(guī)模下的運(yùn)行時(shí)間

從圖8中可以看出，在數(shù)據(jù)集規(guī)模較小時(shí)，即數(shù)據(jù)點(diǎn)的數(shù)量在3×106左右時(shí)，MR-DBSCAN算法完成聚類所需的時(shí)間最少，運(yùn)行時(shí)間比IP-DBSCAN算法和DBWGIE-MR算法分別減少102 s和95 s，DBWGIEMR算法執(zhí)行時(shí)間則相對(duì)較長(zhǎng)，原因是在數(shù)據(jù)集規(guī)模較小的階段，DBWGIE-MR算法需要采用ADG策略和WGIE策略自適應(yīng)地劃分?jǐn)?shù)據(jù)空間以及計(jì)算每個(gè)網(wǎng)格單元的密度，增加了算法處理數(shù)據(jù)集的時(shí)間。然而，隨著數(shù)據(jù)集的規(guī)模提升，數(shù)據(jù)集的規(guī)模為11×106時(shí)，可以明顯看到，IP-DBSCAN算法和DBWGIEMR算法的運(yùn)行時(shí)間分別比MR-DBSCAN算法減少了160 s和400 s，原因在于在大規(guī)模數(shù)據(jù)集下，聚類過(guò)程中產(chǎn)生的局部簇的數(shù)量明顯增加，而相較于MR-DBSCAN算法，IP-DBSCAN算法采用了并查集對(duì)局部簇進(jìn)行合并，加快了局部簇的收斂，因此在合并局部簇上所需的計(jì)算時(shí)間有所減少，DBWGIE-MR算法更是在并查集合并局部簇的基礎(chǔ)上，提出并行化合并局部簇，更進(jìn)一步加快了對(duì)局部簇的合并計(jì)算，因此DBWGIE-MR算法的運(yùn)行時(shí)間要少于IPDBSCAN算法；當(dāng)數(shù)據(jù)規(guī)模為16×106時(shí)，DBWGIEMR算法的運(yùn)行時(shí)間明顯要少于MR-DBSCAN和IPDBSCAN算法，分別降低了400 s和700 s，這也更加表明了在數(shù)據(jù)規(guī)模較大的情況下，DBWGIE-MR算法能更快地對(duì)數(shù)據(jù)進(jìn)行處理得到結(jié)果，并行化效果更佳。

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

為解決大數(shù)據(jù)下基于密度的聚類算法中的數(shù)據(jù)網(wǎng)格化劃分不合理，提高聚類結(jié)果的精確度以及在大規(guī)模數(shù)據(jù)集下的并行化效率，本文提出了基于MapReduce和加權(quán)網(wǎng)格信息熵策略的DBWGIE-MR算法。該算法首先根據(jù)數(shù)據(jù)點(diǎn)空間分布狀況，提出ADG策略，自適應(yīng)劃分網(wǎng)格單元；其次為了提高聚類效果，針對(duì)每個(gè)數(shù)據(jù)分區(qū)，提出NE策略構(gòu)建其加權(quán)網(wǎng)格用于加強(qiáng)網(wǎng)格之間的關(guān)聯(lián)性；同時(shí)提出WGIE策略來(lái)計(jì)算網(wǎng)格密度以及密度聚類算法的ε鄰域和核心對(duì)象，使密度聚類算法更適用于加權(quán)網(wǎng)格；接著結(jié)合MapReduce計(jì)算模型，提出并行計(jì)算局部簇算法COMCORE-MR，從而提升算法的總體并行化效率；最后提出了基于并查集的局部簇合并算法MECORE，用于加快合并局部簇的收斂速度，并結(jié)合MapReduce計(jì)算模型，提出了并行合并局部簇算法MECORE-MR，實(shí)現(xiàn)了并行化地合并局部簇，從而更快地得到聚類結(jié)果的全局簇，提升了基于密度的聚類算法對(duì)局部簇合并的效率。與其他并行化密度聚類算法相比，該算法能根據(jù)數(shù)據(jù)之間的分布狀況來(lái)自適應(yīng)確定網(wǎng)格劃分邊長(zhǎng)，以及構(gòu)建加權(quán)網(wǎng)格來(lái)加強(qiáng)網(wǎng)格單元之間的聯(lián)系，利用該算法的獨(dú)特優(yōu)勢(shì)來(lái)實(shí)現(xiàn)聚類。實(shí)驗(yàn)在四個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行對(duì)比分析，結(jié)果表明DBWGIE-MR算法在聚類精度、尋優(yōu)能力和算法穩(wěn)定性上都有顯著的提高。此外，在擴(kuò)充后的大規(guī)模數(shù)據(jù)集的實(shí)驗(yàn)中，也驗(yàn)證了DBWGIE-MR算法具有較好的并行化效果。結(jié)果也表明，相比MR-DBSCAN算法和IP-DBSCAN算法，DBWGIE-MR算法在面對(duì)大規(guī)模的數(shù)據(jù)集下的并行化效率更強(qiáng)。雖然改進(jìn)后算法的聚類精度有所提升，但仍存在提升空間，并且本文并未解決網(wǎng)格單元密度閾值的設(shè)置問(wèn)題，算法并行化性能還有待進(jìn)一步提高，以上這些將是下一步的研究工作。