李璐明等

摘要：為了快速挖掘大規(guī)?？臻g數(shù)據(jù)的聚集特性，在cluster_dp密度聚類算法基礎(chǔ)上，提出了一種基于彈性分布數(shù)據(jù)集的并行密度聚類方法PClusterdp.首先，設(shè)計一種能平衡工作負(fù)載彈性分布數(shù)據(jù)集分區(qū)方法，根據(jù)數(shù)據(jù)在空間的分布情況，自動劃分網(wǎng)格并分配數(shù)據(jù)，使得網(wǎng)格內(nèi)數(shù)據(jù)量相對均衡，達(dá)到平衡運算節(jié)點負(fù)載的目的；接著，提出一種適用于并行計算的局部密度定義，并改進(jìn)聚類中心的計算方式，解決了原始算法需要通過繪制決策圖判斷聚類中心對象的缺陷；最后，通過網(wǎng)格內(nèi)及網(wǎng)格間聚簇合并等優(yōu)化策略，實現(xiàn)了大規(guī)?？臻g數(shù)據(jù)的快速聚類處理.實驗結(jié)果表明，借助Spark數(shù)據(jù)處理平臺編程實現(xiàn)算法，本方法可以有效實現(xiàn)大規(guī)?？臻g數(shù)據(jù)的快速聚類，與傳統(tǒng)的密度聚類方法相比具有較高的精確度與更好的系統(tǒng)處理性能.

關(guān)鍵詞：空間數(shù)據(jù)；聚類算法；彈性分布式數(shù)據(jù)集；Spark

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A

Density Based Clustering on Large Scale Spatial

Data Using Resilient Distributed Dataset

LI Luming1， 2， JIANG Xinhua1， 3， LIAO Lyuchao1， 3

（1.School of Information Science and Engineering， CentralSouth Univ， Changsha，Hunan410075， China；

2.Hunan Key Laboratory for Special Road Environment， Changsha Univ of Science and Technology， Changsha，Hunan410004，China；

3.Fujian Key Laboratory for Automotive Electronics and Electric Drive ， Fujian Univ of Technology， Fuzhou，F(xiàn)ujian350108，China）

Abstract：This paper proposed a density based parallel clustering algorithm to mine the feature of large scale spatial data. The proposed PClusterdp algorithm is based on the clusterdp algorithm. First， we introduced a data object count based RDD partition algorithm for balancing the working load of each compute node in computing cluster. Second， we redefined the local density for each data point to suit the parallel computing. Meanwhile， in order to get rid of original algorithm's decision graph， we proposed a method to automatically determine the center point for each cluster. Finally， we discussed the cluster merge stratagem to combine the partially clustered data together to generate the final clustering result. We implemented our Resilient Distributed Dataset （RDD） based algorithm on Spark. The experiment result shows that the proposed algorithm can cluster large scale spatial data effectively， and meanwhile， the method has better performance than the traditional density clustering methods and can achieve the rapid clustering of massive spatial data.

Key words：spatial data； clustering algorithm； resilient distributed dataset； Spark

作為數(shù)據(jù)分析的重要手段之一，聚類分析在空間數(shù)據(jù)挖掘中扮演重要的角色.空間聚類分析將空間數(shù)據(jù)按其聚集特性分成若干聚簇，使得位于同一聚簇的數(shù)據(jù)具有較大的相似性，而位于不同聚簇的數(shù)據(jù)具有較大的差異性[1].根據(jù)不同的指導(dǎo)思想，可將聚類算法分為基于劃分的聚類[2]、基于層次的聚類[3]、基于密度的聚類[4]、基于網(wǎng)格的聚類[5]以及基于特定模型的聚類[6].

經(jīng)典劃分式算法kmeans[7]與其改進(jìn)算法kmedoids[8]，kmeans++[9]，通過多次迭代來確定聚簇中心并將數(shù)據(jù)歸類.算法實現(xiàn)簡單，但對噪音敏感，對非球形的聚簇的處理效果較差.

層次聚類算法BIRCH[10]遵循自頂向下原則，將數(shù)據(jù)集分層并用樹形結(jié)構(gòu)表示.利用CF樹作為索引，BIRCH在對數(shù)據(jù)進(jìn)行壓縮的同時，盡可能保留了數(shù)據(jù)的聚集特性并減小I/O操作.但CF樹的構(gòu)造策略將較大地影響運算效率，而壓縮數(shù)據(jù)導(dǎo)致BIRCH算法不易發(fā)現(xiàn)稀疏數(shù)據(jù)間的相互關(guān)系，無法得到全局最優(yōu)解.

密度聚類算法DBSCAN[11]通過計算數(shù)據(jù)對象間的距離，獲取每個數(shù)據(jù)對象的鄰域內(nèi)鄰居的聚集特性，根據(jù)鄰域內(nèi)的對象數(shù)目定義核心點、密度可達(dá)、密度相連等相關(guān)概念.進(jìn)而，通過密度可達(dá)與密度相聯(lián)過濾數(shù)據(jù)稀疏的區(qū)域，發(fā)現(xiàn)稠密點.基于DBSCAN算法的聚類質(zhì)量較好，可以較好地避免“噪聲”數(shù)據(jù)的干擾，發(fā)現(xiàn)任意形狀的聚簇.但DBSCAN的效果依賴領(lǐng)域半徑與最小核心點數(shù)的選擇，算法調(diào)試?yán)щy.OPTICS[12]算法能減少輸入?yún)?shù)對聚類結(jié)果的影響，對輸入不敏感，其輸出為包含聚簇信息的數(shù)據(jù)對象的排序，可從中提取出聚簇.由于需計算每對數(shù)據(jù)對象間的距離，密度聚類算法的效率較低.

網(wǎng)格聚類算法STING將原始聚類空間劃分為若干相等大小的網(wǎng)格，通過統(tǒng)計分析獲取網(wǎng)格特性，以網(wǎng)格為對象進(jìn)行聚類.此方法可以大幅度降低計算量，獲得較高的處理效率.但用網(wǎng)格代替數(shù)據(jù)對象本身，將會喪失部分?jǐn)?shù)據(jù)對象的聚集特性，影響聚類結(jié)果的精確度.

經(jīng)典聚類算法缺乏對聚簇中心的明確定義.針對該缺陷，Rodriguez等人提出了一種基于密度的聚簇中心的描述并設(shè)計cluster_dp[13]算法.算法計算空間數(shù)據(jù)對象的局部密度與最小高密度距離，兩者皆高的數(shù)據(jù)對象即為聚簇中心.同時，算法比較局部密度與聚簇平均邊界密度，將聚簇成員標(biāo)記為核心成員（cluster core）與光暈（cluster halo）.但算法尚未完全做到聚簇中心的自動判別，算法運行過程中需繪制決策圖，靠人工經(jīng)驗輔助判斷.

隨著數(shù)據(jù)規(guī)模的激增，傳統(tǒng)的聚類算法往往由于數(shù)據(jù)量過大而無法運行，迫切需要高速、有效、高伸縮的海量數(shù)據(jù)聚類算法.面向計算機(jī)集群GFS[14]，BigTable[15]和MapReduce[16]技術(shù)為海量數(shù)據(jù)的聚類分析提供了思路.作為上述技術(shù)的開源實現(xiàn)，Hadoop并行計算框架在聚類分析領(lǐng)域被廣泛應(yīng)用[17].Lv對kmeans進(jìn)行改進(jìn)，提出了基于Hadoop的Parallel Kmeans[18].Ferreira提出了一種基于Hadoop MapReduce的高緯度數(shù)據(jù)聚類分析方法[19].由于追求高吞吐量，基于HadoopMapReduce框架的并行聚類算法需要多次讀寫磁盤以存取中間結(jié)果，導(dǎo)致算法 I/O開銷較大，具有較高的延遲，無法用于實時聚類.

為提高集群并行計算的效率，Matei Zaharia等人提出了彈性分布數(shù)據(jù)集（Resilient Distributed Dataset，RDD ）抽象，并在RDD上擴(kuò)展MapReduce編程接口，架構(gòu)了通用大數(shù)據(jù)并行計算平臺Spark[20].Spark具有高于Hadoop 近百倍的運算性能，能應(yīng)對實時大規(guī)?？臻g數(shù)據(jù)的快速聚類分析.基于Spark框架，實現(xiàn)了分布式kmeans II[21]，但與傳統(tǒng)kmeans算法相同，算法無法發(fā)現(xiàn)非球形簇.

針對傳統(tǒng)密度聚類算法無法分析海量、高維空間數(shù)據(jù)的缺陷，在算法cluster_dp的基礎(chǔ)上提出一種基于彈性分布數(shù)據(jù)集的聚類方法PClusterdp.主要工作如下：

1） 提出基于自適應(yīng)網(wǎng)格的RDD分區(qū)算法，用于平衡計算集群內(nèi)工作節(jié)點的負(fù)載，減少計算等待時間，降低計算節(jié)點間通訊開銷.

2） 改進(jìn)局部密度的計算方式以適應(yīng)并行計算，降低RDD分區(qū)內(nèi)計算量，提高算法運行效率.

3） 構(gòu)建輔助函數(shù)自動確定聚簇中心，消除聚類過程中的人工干預(yù).

4） 設(shè)計聚簇合并算法歸并局部聚類結(jié)果，消除RDD分區(qū)產(chǎn)生的影響，提高聚類分析結(jié)果的準(zhǔn)確度.

1問題描述與相關(guān)概念

2PClusterdp算法設(shè)計與實現(xiàn)

2.1彈性分布式數(shù)據(jù)集介紹

彈性分布式數(shù)據(jù)集的本質(zhì)是一種只讀的可并行記錄集合.RDD基于內(nèi)存計算設(shè)計，數(shù)據(jù)常駐內(nèi)存， I/O 開銷少.RDD自帶分區(qū)列表，分區(qū) （Partition） 分布在各計算節(jié)點的內(nèi)存上，以實現(xiàn)并行.創(chuàng)建KeyValue 型RDD可控制數(shù)據(jù)的分區(qū)，優(yōu)化計算過程.RDD自帶兩類API接口操作數(shù)據(jù)：轉(zhuǎn)換 （Transformation） 在現(xiàn)有RDD基礎(chǔ)上變化生成新的RDD；動作 （Action） 通過RDD來計算并反回結(jié)果[20].

在cluster_dp算法的基礎(chǔ)上，利用RDD模型設(shè)計密度聚類算法PClusterdp.借助集群并行，在保證準(zhǔn)確率的前提下提高密度聚類算法的吞吐量和計算效率.算法的主要特點如下：

1） 準(zhǔn)確性：算法有原始算法80%以上的準(zhǔn)確率.

2） 高吞吐：并行集群能處理千萬級以上數(shù)據(jù).

3） 高效率：算法效率較原始算法有數(shù)倍提升.

2.2PClusterdp總體框架

PClusterdp利用RDD存儲數(shù)據(jù)，基于“RDD分區(qū)內(nèi)并行計算合并局部結(jié)果”思想設(shè)計，借助分割S實現(xiàn)RDD分區(qū)與并行.算法總體框架如表1所示：

映射數(shù)據(jù)對象到分割后的空間網(wǎng)格G，生成基于網(wǎng)格編號的KeyValue RDD.利用MapPartition接口，根據(jù)網(wǎng)格編號劃分RDD，分配同區(qū)的數(shù)據(jù)對象到相同計算節(jié)點.各節(jié)點獨立運行密度聚類算法得到基于網(wǎng)格分區(qū)的局部簇.隨后，合并相鄰網(wǎng)格中局部簇，生成最終聚類結(jié)果.

2.3基于數(shù)據(jù)對象數(shù)目的RDD分區(qū)算法

PClusterdp算法借助分割計算空間實現(xiàn)RDD分區(qū).傳統(tǒng)的空間分割算法通常將計算空間劃分為大小均勻的網(wǎng)格.然而，在聚類分析中，數(shù)據(jù)對象在計算空間中呈現(xiàn)不均勻分布.基于均勻網(wǎng)格的RDD分區(qū)策略將導(dǎo)致分區(qū)內(nèi)數(shù)據(jù)量差異大，使得計算節(jié)點負(fù)載失衡，影響計算效率.為平衡各計算節(jié)點的負(fù)載，避免數(shù)據(jù)丟失，并使RDD的分區(qū)過程可控，PClusterdp采用一種基于數(shù)據(jù)對象數(shù)目的空間劃分策略.算法引入空間網(wǎng)格索引，保證網(wǎng)格內(nèi)數(shù)據(jù)量相對均衡.RDD依照網(wǎng)格編號分區(qū)并分配數(shù)據(jù)到計算節(jié)點，可平衡各計算節(jié)點的負(fù)載，提高算法的效率.為說明空間劃分原理，設(shè)網(wǎng)格中數(shù)據(jù)對象的數(shù)目上限為10，基于數(shù)據(jù)對象數(shù)目的空間劃分結(jié)果如圖1所示.

得到完整索引結(jié)構(gòu)后，遍歷索引，查找數(shù)據(jù)量小于給定值的最大網(wǎng)格，一旦找到則停止繼續(xù)往下遍歷，得到空間劃分的結(jié)果.據(jù)此結(jié)果映射數(shù)據(jù)對象，生成基于網(wǎng)格編號的KeyValue RDD.利用KeyValue RDD的MapPartitionWithIndex函數(shù)接口，自動生成基于網(wǎng)格RDD分區(qū).

2.4改進(jìn)的分區(qū)內(nèi)聚類算法

RDD分區(qū)后，在各分區(qū)上并行地運行cluster_dp算法，得出基于網(wǎng)格分區(qū)的局部簇.在此修改cluster_dp算法，使其能適應(yīng)并行計算.算法細(xì)節(jié)如表3所示：

2.4.1改進(jìn)的的局部密度定義

局部密度的計算方法決定了聚類的效果， cluster_dp算法利用局部定義與最小高密度距離判斷聚簇中心.數(shù)據(jù)對象的局部密度差異越大，越能捕捉聚簇中心對象的特性，聚類效果越好.公式（1）為局部密度原始定義，該定義僅考慮數(shù)據(jù)對象dc鄰域內(nèi)的數(shù)據(jù)量，導(dǎo)致多數(shù)數(shù)據(jù)對象具有相同的局部密度，從而影響最小高密度距離的計算，影響聚簇中心對象的判斷.文獻(xiàn)[13]提供了一種基于高斯核函數(shù)的局部密度定義，使用該定義計算局部密度需要遍歷整個數(shù)據(jù)集，不適用于并行計算.為平衡運算速度與計算結(jié)果精度，實現(xiàn)并行計算，定義如下改進(jìn)的局部密度計算方式.

如圖2所示，ρ′1>ρ′7 .同時，將局部密度的計算限制在數(shù)據(jù)對象的領(lǐng)域之內(nèi)，計算局部密度時只考慮數(shù)據(jù)對象所在網(wǎng)格分區(qū)以及其鄰接網(wǎng)格分區(qū)的對象，避免遍歷整個數(shù)據(jù)集，降低計算節(jié)點的工作開銷.

2.4.2改進(jìn)的聚簇中心確定策略

原始cluster_dp在確定聚簇中心時，需繪制決策圖，并通過人機(jī)交互進(jìn)行判斷.為擺脫算法對決策圖的依賴和人為干預(yù)，設(shè)計輔助函數(shù)γ自動判定聚簇中心.

已知數(shù)據(jù)對象的局部密度為ρi，其最小高密度距離為δi，則設(shè)：

其中，max（ρ）*max（δ）為網(wǎng)格內(nèi)最大局部密度與最小高密度值的乘積.由于局部密度與最小高密度距離具有不同的尺度，因此借助網(wǎng)格內(nèi)局部密度與最小高密度距離的最大值進(jìn)行簡單歸一化操作.將γi限定在 [0，1]后，將其降序排列，其結(jié)果如圖3所示.

可以看出非聚簇中心對象γ趨近0，聚簇中心對象的γ值離散分布且遠(yuǎn)離原點.由此，可通過預(yù)設(shè)閥值確定聚簇的中心候選對象.預(yù)設(shè)值的選取依賴實際應(yīng)用環(huán)境，選擇γ>0.2的數(shù)據(jù)對象作為聚簇中心候選對象生成局部簇，可得到較為理想的聚類結(jié)果.得到聚簇中心候選對象后，即可確定聚簇的數(shù)目，進(jìn)而將網(wǎng)格內(nèi)數(shù)據(jù)歸類到對應(yīng)的局部簇中.

2.5局部聚簇的合并策略

生成分區(qū)內(nèi)局部簇后，需對局部簇的成員進(jìn)行合并與調(diào)整，得到全局聚類結(jié)果.局部簇合并分為如下兩種情況：

2.5.1分區(qū)內(nèi)聚簇合并策略

改進(jìn)后的局部密度定義雖在一定程度上提高了局部密度的差異性，然而局部密度相等的情況無法完全避免，特殊情況下聚類結(jié)果仍將產(chǎn)生偏差.

如圖4所示，簇1中數(shù)據(jù)對象均勻且對稱分布.其中，兩鄰近數(shù)據(jù)對象1和6擁有相同的局部密度.根據(jù)聚類中心的選擇方法數(shù)據(jù)對象1和數(shù)據(jù)對象6可能同時被認(rèn)定為聚類中心，從而導(dǎo)致一個簇被拆分成兩個.分區(qū)內(nèi)聚簇合并用來解決上述問題，如果兩聚簇中心之間的距離小于預(yù)設(shè)閥值ε，則合并兩個聚簇中心所對應(yīng)的簇.

2.5.2分區(qū)間聚簇合并策略

每個RDD分區(qū)對應(yīng)一空間網(wǎng)格，對于靠近網(wǎng)格邊界的數(shù)據(jù)對象，需要在相鄰網(wǎng)格之間再次評估其聚集特性，避免由于劃分RDD造成的歸類錯誤.原始算法通過計算兩個簇間的平均局部密度，將聚簇成員標(biāo)記為核心成員（cluster core）與光暈（cluster halo） .其中，核心成員為聚簇的中心部分，由高密度點組成，是穩(wěn)定的數(shù)據(jù)對象聚集；而光暈對應(yīng)聚簇外圍，包含低密度數(shù)據(jù)點，是聚簇的非穩(wěn)定部分?jǐn)?shù)據(jù)的聚集.利用核心與光暈的概念，提出網(wǎng)格間聚簇的合并方法.如果鄰接網(wǎng)格中靠近網(wǎng)格邊界的數(shù)據(jù)對象分布存在如下情況，則需調(diào)整數(shù)據(jù)對象所屬聚簇.

〖STHZ〗情況1〖HT〗〖ST〗相鄰網(wǎng)格中近邊界處存在聚簇核心對象，并且核心對象相互靠近.如圖5所示，數(shù)據(jù)對象1與6是兩個簇的核心對象，且其距離小于ε.由于網(wǎng)格的存在，將原本應(yīng)歸為同一聚簇的數(shù)據(jù)對象分配到了不同的聚簇中.此情況下合并兩個聚簇.

在光暈對象所在網(wǎng)格的鄰接網(wǎng)格中查找密度高于光暈對象的數(shù)據(jù)對象，并計算滿足條件的數(shù)據(jù)對象到光暈點的距離.若計算得出的最小距離小于當(dāng)前光暈對象的最小高密度距離，則更新光暈點的最近高密度鄰居與最小高密度距離，并根據(jù)更新后的最近高密度鄰居將光暈對象分配到新的聚簇中.

3實驗及結(jié)果分析

3.1實驗環(huán)境搭建

為了進(jìn)行對比測試，將測試平臺分成偽集群測試平臺與真小型集群測試平臺兩部分.前者基于小型工作站搭建，其配置為：Intel（R） Core（TM） i53470 3.2GHz 4核CPU，1TB硬盤，4GB內(nèi)存.在平臺上搭建Spark V 1.1.0偽集群，可模擬4個計算節(jié)點.

后者由20臺測試機(jī)組成，各服務(wù)器硬件配置為：Inter（R） Xeon（R） CPU E52650 V2 2.6GHz，內(nèi)存8G，硬盤200G，網(wǎng)絡(luò)帶寬1000Mbps.機(jī)群搭載Spark V 1.1.0.兩平臺上運行相同的PClusterdp算法，代碼采用Scala語言編寫.

3.2實驗內(nèi)容與結(jié)果分析

3.2.1準(zhǔn)確率對比測試

準(zhǔn)確率對比測試在偽集群測試平臺上進(jìn)行.測試數(shù)據(jù)集選用標(biāo)準(zhǔn)密度聚類測試數(shù)據(jù)集：Mars，F(xiàn)lame，Spiral[22-24]與Jain[25].測試比對PClusterdp算法與傳統(tǒng)cluster_dp算法的聚類效果.原始cluster_dp算法分別采用傳統(tǒng)密度定義即公式（1）與全局高斯核公式計算局部密度并判定聚類中心.PClusterdp算法采用公式（3）配合公式（4）判定聚類中心.設(shè)被正確歸類的數(shù)據(jù)對象數(shù)目為Cr，實驗使用如下評價函數(shù)評價聚類效果：

效率測試對比cluster_dp算法與PClusterdp算法處理海量數(shù)據(jù)集所需時間.實驗從福州市2014年12月16日運營車輛1.2億條定位數(shù)據(jù)中分別抽取1萬，10萬，100萬，1000萬，1億個數(shù)據(jù)對象，分成4組進(jìn)行對比測試.其所消耗的時間如圖9所示：

3.2.3實驗結(jié)果分析

準(zhǔn)確率測試結(jié)果表明，使用全局高斯核密度的cluster_dp算法具有最高的準(zhǔn)確率.PClusterdp算法使用的基于鄰域半徑的高斯核局部密度定義，綜合考慮領(lǐng)域范圍內(nèi)數(shù)據(jù)點數(shù)目與領(lǐng)域范圍內(nèi)數(shù)據(jù)點距離.配合網(wǎng)格內(nèi)聚簇合并策略，PClusterdp算法能夠較好地把握數(shù)據(jù)的聚集特征.經(jīng)多個數(shù)據(jù)集測試，PClusterdp算法的評價函數(shù)值均達(dá)到85%以上，說明算法的聚類中心確定策略配合改進(jìn)的局部密度定義使用是可行的，算法具備一定的魯棒性.由聚類效果圖可以看出，PClusterdp算法可以發(fā)現(xiàn)任何形狀的簇.而使用傳統(tǒng)密度定義（公式1）的cluster_dp算法，計算出的局部密度差異度較小，導(dǎo)致聚類的精確度最低，且不同數(shù)據(jù)集使用之間差異較大，魯棒性較差.

cluster_dp算法需遍歷整個數(shù)據(jù)集計算數(shù)據(jù)對象的局部密度，算法時間復(fù)雜度為O（n2）.PClusterdp算法通過空間網(wǎng)格減少局部密度的計算量，計算密度時僅需遍歷對象所在網(wǎng)格分區(qū)及其相鄰的8個網(wǎng)格分區(qū)內(nèi)的數(shù)據(jù).設(shè)單個網(wǎng)格分區(qū)內(nèi)數(shù)據(jù)量為m，PClusterdp算法的時間復(fù)雜度為O（81*m2），由于m遠(yuǎn)小于n， PClusterdp算法的時間復(fù)雜度大幅降低.由算法效率對比測試結(jié)果看出，原始cluster_dp算法無需分割數(shù)據(jù)集，在數(shù)據(jù)集規(guī)模小時花費時間少.但當(dāng)數(shù)據(jù)規(guī)模增長時，cluster_dp算法花費時間呈指數(shù)集上升，數(shù)據(jù)規(guī)模上億時，使用cluster_dp算法聚類需花費數(shù)小時，算法伸縮性差.PClusterdp算法在分割數(shù)據(jù)集與集群通訊上需花費少量時間，數(shù)據(jù)規(guī)模較小時，算法效率不及原始cluster_dp算法.但當(dāng)數(shù)據(jù)集規(guī)模上升時，PClusterdp算法時間的增長相對平緩，算法的可伸縮性較強(qiáng).能在30 min內(nèi)處理上億條數(shù)據(jù)，PClusterdp算法具備一定的吞吐量，基本能滿足實時計算的要求.

4結(jié)論

針對傳統(tǒng)密度聚類算法效率不高、伸縮性不強(qiáng)無法適用于海量、高維數(shù)據(jù)的特點.提出了一種基于cluster_dp算法的改進(jìn)分布式密度聚類算法PClusterdp.算法重新定義了局部密度的計算方式，通過設(shè)計基于局部密度與最小距離的函數(shù)的輔助分析函數(shù)，解決了原始算法需依靠決策圖人工干預(yù)聚類中心問題.改進(jìn)后的算法能夠自動計算聚類中心并發(fā)現(xiàn)任意形狀的聚簇.該算法還引入空間網(wǎng)格和彈性可分布數(shù)據(jù)集對待處理數(shù)據(jù)進(jìn)行分區(qū)，利用Spark實現(xiàn)了算法的并行處理，使傳統(tǒng)的聚類分析算法能夠適用于海量、高維數(shù)據(jù)的分析處理.

實驗結(jié)果表明，該算法具有較強(qiáng)的魯棒性，能適用于不同類型的數(shù)據(jù)集.算法的聚類結(jié)果較為穩(wěn)定，能夠有效揭示數(shù)據(jù)聚集模式.同時，算法具有較強(qiáng)的伸縮性，可應(yīng)用于海量數(shù)據(jù)的挖掘分析.

參考文獻(xiàn)

HAN J， KAMBER M， PEI J. Data mining： concepts and techniques [M]. Third Edition. Singapore： Elsevier Pte Ltd， 2012.

[2]TVRDIK J， KIV I. Differential evolution with competing strategies applied to partitional clustering [J]. Swarm and Evolutionary Computation， 2012， 7269（4）： 136-144.

[3]CARVALHO， A X Y， ALBUQUERQUE P， et al. Spatial hierarchical clustering [J]. Revista Brasileira de Biometria， 2009， 27（3）： 411-442.

[4]SANDER J， ESTER M， HANS P， et al. Densitybased clustering in spatial databases： The algorithm gdbscan and its applications [J]. Data Mining and Knowledge Discovery， 1998， 2（2）： 169-194.

[5]WANG S， CHEN Y. HASTA： A Hierarchicalgrid clustering algorithm with data field [J]. International Journal of Data Warehousing and Mining， 2014， 10 （2）： 39-54.

[6]BOUVEYRON C C， BRUNETSAUMARD. Modelbased clustering of highdimensional data： a review [J]. Computational Statistics & Data Analysis， 2014， 71 （6）： 52-78.

[7]KIRI W， CLAIREl C， SETH R， et al. Constrained kmeans clustering with background knowledge [C]//Proceedings of the Eighteenth International Conference on Machine Learning. USA， 2001： 577-584.

[8]PARK HAESANG， CHIHYUCK JUN. A simple and fast algorithm for Kmedoids clustering [J]. Expert Systems with Applications， 2009， 36 （2）： 3336-3341.

[9]ARTHUR D， SERGEI V. kmeans++： The advantages of careful seeding [C]//Proceedings of the Eighteenth Annual ACMSIAM Symposium on Discrete Algorithms. USA， 2007： 1027-1035.

[10]ZHANG Tian， RAGHU R， MIRON L. BIRCH： A new data clustering algorithm and its applications [J]. Data Mining and Knowledge Discovery， 1997， 1 （2）： 141-182.

[11]ESTER， MARTIN， et al. A densitybased algorithm for discovering clusters in large spatial databases with noise [C]//Proceedings of the Second International Conference on Knowledge Discovery and Data Mining （KDD96）. USA， 1996： 226-231.

[12]ANKERST M， et al. Optics： ordering points to identify the clustering structure [C]//SIGMOD '99 Proceedings of the 1999 ACM SIGMOD international conference on Management of data. USA， 1999： 49-60.

[13]RODRIGUEZ A， ALESSANDRO L. Clustering by fast search and find of density peaks [J]. Science， 2014， 334 （6191）： 1492-1496.

[14]GHEMAWAT S， GOBIOFF H， LEUNG S.T. The Google file system [C]//SOSP '03 Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles. USA， 2003： 29-43.

[15]FAY C， JEFFERY D， SANJAY G， et al. Bigtable： a distributed storage system for structured data [J]. ACM Transactions on Computer Systems， 2008， 26（2）： 4-18.

[16]LEE D， J.S K， SEUNGRYOUL M， Largescale incremental processing with MapReduce [J]. Future Generation Computer Systems， 2014， 36（6）： 66-79.

[17]SHVACHKO K， HAIRONG K， RADIA S， et al. The hadoop distributed file system[C]//Mass Storage Systems and Technologies （MSST）. USA， 2010： 1-10.

[18]LV Z， HU Y， ZHONG H， et al. Parallel PKmeans clustering of remote sensing images based on MapReduce [J]. Web Information Systems and Mining， 2012， 6318 （2010）： 139-142.

[19]ROBSON L F， CORDEIRO， CAETANO T J， et al. Clustering very large multidimensional datasets with MapReduce[C]//KDD '11 Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. USA， 2011： 690-698.

[20]ZAHARIA M， CHOWDHURY M， DAS T， et al. Resilient distributed datasets： a faulttolerant abstraction for inmemory cluster computing [C]//NSDI'12 Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. USA， 2012： 2.

[21]BAHMANI B， MOSELEY B， VATTANI A， et al. Scalable kmeans++ [J]. Proceedings of the VLDB Endowment， 2012， 5（7）： 622-633.

[22]GIONIS A， MANNILA H， TSAPARAS P. Clustering aggregation [J]. ACM Transactions on Knowledge Discovery from Data， 2007， 1 （1）： 4.

[23]FU L， MEDICO E. FLAME. A novel fuzzy clustering method for the analysis of DNA microarray data [J]. BMC Bioinformatics， 2007， 8（1）： 3.

[24]CHANG H， YEUNG D.Y. Robust pathbased spectral clustering [J]. Pattern Recognition， 2008， 41（1）： 191-203.

[25]DUBES R， JAIN A K. Clustering techniques： the user's dilemma [J]. Pattern Recognition， 1976， 8（4）： 247-260.〖ZK）〗