李璐明等

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：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ù)歸類.算法實(shí)現(xiàn)簡(jiǎn)單，但對(duì)噪音敏感，對(duì)非球形的聚簇的處理效果較差.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2PClusterdp總體框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5局部聚簇的合并策略

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

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

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

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

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

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

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

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

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

3.1實(shí)驗(yàn)環(huán)境搭建

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

后者由20臺(tái)測(cè)試機(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.兩平臺(tái)上運(yùn)行相同的PClusterdp算法，代碼采用Scala語言編寫.

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

3.2.1準(zhǔn)確率對(duì)比測(cè)試

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

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

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

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

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

4結(jié)論

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

實(shí)驗(yàn)結(jié)果表明，該算法具有較強(qiáng)的魯棒性，能適用于不同類型的數(shù)據(jù)集.算法的聚類結(jié)果較為穩(wěn)定，能夠有效揭示數(shù)據(jù)聚集模式.同時(shí)，算法具有較強(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）〗