李璐明等

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

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

中圖分類號：TP301.6 文獻標識碼：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ù)不同的指導思想，可將聚類算法分為基于劃分的聚類[2]、基于層次的聚類[3]、基于密度的聚類[4]、基于網(wǎng)格的聚類[5]以及基于特定模型的聚類[6].

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

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

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

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

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

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

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

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

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

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

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

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

1問題描述與相關概念

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

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

彈性分布式數(shù)據(jù)集的本質(zhì)是一種只讀的可并行記錄集合.RDD基于內(nèi)存計算設計，數(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基礎上變化生成新的RDD；動作 （Action） 通過RDD來計算并反回結果[20].

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

1） 準確性：算法有原始算法80%以上的準確率.

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

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

2.2PClusterdp總體框架

PClusterdp利用RDD存儲數(shù)據(jù)，基于“RDD分區(qū)內(nèi)并行計算合并局部結果”思想設計，借助分割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)格中局部簇，生成最終聚類結果.

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

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

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

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

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

2.4.1改進的的局部密度定義

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

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

2.4.2改進的聚簇中心確定策略

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

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

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

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

2.5局部聚簇的合并策略

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

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

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

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

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

每個RDD分區(qū)對應一空間網(wǎng)格，對于靠近網(wǎng)格邊界的數(shù)據(jù)對象，需要在相鄰網(wǎng)格之間再次評估其聚集特性，避免由于劃分RDD造成的歸類錯誤.原始算法通過計算兩個簇間的平均局部密度，將聚簇成員標記為核心成員（cluster core）與光暈（cluster halo） .其中，核心成員為聚簇的中心部分，由高密度點組成，是穩(wěn)定的數(shù)據(jù)對象聚集；而光暈對應聚簇外圍，包含低密度數(shù)據(jù)點，是聚簇的非穩(wě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)格的存在，將原本應歸為同一聚簇的數(shù)據(jù)對象分配到了不同的聚簇中.此情況下合并兩個聚簇.

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

3實驗及結果分析

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

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

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

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

3.2.1準確率對比測試

準確率對比測試在偽集群測試平臺上進行.測試數(shù)據(jù)集選用標準密度聚類測試數(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ù)據(jù)對象數(shù)目為Cr，實驗使用如下評價函數(shù)評價聚類效果：

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

3.2.3實驗結果分析

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

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

4結論

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

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

參考文獻

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）〗