基于云计算平台的动态增量密度算法研究

孟海东　任敬佩

(内蒙古科技大学信息工程学院　内蒙古 包头014010)



基于云计算平台的动态增量密度算法研究

孟海东任敬佩

(内蒙古科技大学信息工程学院内蒙古 包头014010)

摘要针对传统密度聚类算法处理海量数据时间复杂度高且不适合处理动态数据等问题，提出一种利用参考点和MapReduce模型进行动态增量聚类的密度算法。其创新点在于，该算法实现了一种能够处理海量动态数据的聚类算法,保证了增量聚类与重新聚类结果的一致性,并具有可扩展性的特点。实验结果证明：该算法降低了参数敏感性，提高了密度算法的聚类效率和资源利用率，适合大数据分析。

关键词参考点增量聚类MapReduce动态密度算法

0引言

目前对于传统密度聚类算法改进的研究主要用包括数据场[1]、网格[2,3]、增量[4-6]、并行[7]和MapReduce等方法。其中研究最多的是基于MapReduce模型的并行密度聚类算法来提高算法的聚类效率和资源利用率。由于随着数据量的增长，利用云计算处理大数据进行聚类已成为热点。文献[8]提出了一种基于MapReduce层次的密度聚类算法HDBSCAN，降低了参数的敏感性，提高了算法的效率；文献[9]利用MapReduce模型与粒子群优化方法提出了DPDPSO算法，降低了内存的依赖，同时也提高了DBSCAN算法的运行时间；文献[10]利用MapReduce机制，实现区域查询和候选队列处理，提高了算法的聚类效率；文献[11-14]通过Hadoop平台实现了DBSCAN算法的改进，提高了算法的加速比和可伸缩性；文献[15，16]利用云计算平台提出了增量DBSCAN聚类算法，实现局部挖掘知识与原先整体挖掘知识进行类簇相似性合并，形成最终的挖掘知识。

以上都是基于静态密度聚类，因而本文提出一种利用参考点作为初始中心点并使用MapReduce模型进行并行计算的动态DBSCAN算法DICURDA(Dynamic and Incremental Clustering Using References and Density Algorithm)。DICURDA算法基于MapReduce模型实现了并行密度算法。利用虚拟的参考点反应了数据空间的点分布特征，并在增量聚类过程中利用参考点和密度算法实现了动态聚类，降低了在增量聚类过程中参数的敏感和时间复杂度，以及对核心点的I/O次数。

1DICURDA聚类算法

1.1概念

设在云计算平台处理的大数据中，原始数据集为V(v1,v2,…,vn)，聚类中心点为Ci(i=1,2,…,k)；增量数据集为△V(△v1,△v2,…,△vn)，增量中心点△Ci(i=1,2,…,k)。

定义1(点的密度)在集群的各个节点中，对空间中的任意点p，给定区域半径R，如果点p到其他点pi(i=1,2,…,n)距离dppi小于等于R的个数为ρp，则称点p的密度为ρp，记作ρp(p,R)。

ρp=∑χ(dppi-R)

(1)

定义2(点密度距离)给定密度阈值T，设密度点距离δp，则：

(2)

如果ρp≥T，则称为高密度点，记作H(ρp,δp)；反之，称为稀疏密度点，记作L(ρp,δp)。

定义3(参考点)给定一个距离阈值D，根据定义2可知，若某点为稀疏密度点H(ρp,δp)且δp

定义4(核心点)给定一个距离阈值D，根据定义2可知，高密度点H(ρp,δp)，如果δp>D，则称点p为核心点。

定义5(直接密度可达)在给定的对象集V中，由定义2可知，高密度点H(ρp,δp)与H(ρq,δq)，如果δq

定义6(密度可达)在给定的对象集V中，存在点pi(i=1,2,…,n)，由定义2可知，稀疏密度点L(ρpi,δpi)，高度密度点H(ρq,δq)，如果δq

定义7(噪声点)在给定的对象集V中，由定义2可知，稀疏密度点L(ρp,δp)，如果δp>D，则p为噪声点。

定义8V(v1,v2,…,vn)初始聚类过程中对象簇Ci(i=1,2,…,k)设为全局参数，则Ci(i=1,2,…,k)是△V(△v1,△v2,…,△vn)的聚类的参考点(核心点)。

参考点即是核心点，因为在初始聚类结果中获得的参考点都是符合定义4的点的集合。

定义9(簇合并)设参考点p和q所属簇分别为Cp和Cq，如果点p到点q的距离小于或等于R，即：

Dis(p,q)≤R

(3)

则Cp和Cq合并为簇Cpq。

证明：设点p与点q为参考点，由定义2和定义3可知，如果ρp>T且δp>D，p则为核心点，当Dis(p,q)≤R时，则q属于ρp(p,R)内的密度点；由定义5和定义6可知，如果点q是H(ρq,δq)，则对象q到p是直接密度可达；如果点q是L(ρpi,δpi)，则对象q到p是密度可达；因此，簇Cp和Cq可以合并为簇Cpq。

例如：设点的区域半径R=10，密度阈值T=5，距离阈值D=9，P(p1,p2,…,pn)是二维空间中任意数据点如图1所示,则：

图1　二维空间数据点分布

根据定义1可从图1与图2中看出，p1、p2、p3、p4、p5的密度点分别为ρp1(9,10)、ρp2(11,10)、ρp3(4,10)、ρp4(1,10)、ρp5(7,10)，具体如图2所示；根据定义2，由于p1、p2、p4的密度大于T=7，则p1、p2、p5是高密度的点，分别记作H(9,8.93)、H(11,8.97)、H(7,9.21)；反之，p3、p4为稀疏密度点，分别记作L(4,3.23)、L(1,22.92)，具体如图2所示。根据定义3和定义4可知，p1、p2、p5为高密度点，δp1、δp2为参考点，δp5大于D=9，则为参考点且为核心点；p3、p4为稀疏点，且δp39，则根据定义7可知，p4为噪声点，具体如图1、图2所示；根据定义5和定义6可知，δp1<9和δp2<9，且H(ρp2,δp2)∈NH(ρp1,δp1)，则p2到p1直接密度可达；δp3<9且L(ρp3,δp3)∈NH(ρp2,δp2)，则p3到p2密度可达。由图1所示，Dis(p1,p2)=8.93

图2 　二维数据点的Pi(ρpi,δpi)分布　　图3　DICURDA算法的簇合并

1.2DICURDA算法设计

根据1.1节中概念定义的叙述，DICURDA算法的聚类过程中，设噪声点对象簇为Oi(i=0,1,…)，增量噪声点对象簇为△Oi(i=0,1,…)；根据上述中定义，在数据集V可以实现对象簇Ci(i=1,2,…,k)。随着数据集的动态的增长，当增量数据集为△V时，实现增量数据集△V的聚类过程，聚类结果新簇为△Ci(i=1,2,…,k)。ICURD算法的实现过程主要分为以下两个过程：

(1) 初始聚类过程

① 对于数据集V(v1,v2,…,vn)中的每个数据点，根据定义1计算出每个点的密度ρvi(vi,R)(i=1,2,…,n)。

② 根据定义2，计算出每个数据点的δvi(i=1,2,…,n)。

③ 根据定义3，判断每个数据点是否为参考点的条件如下：根据定义4判断该点是否是核心点，如果是，则标记为单标记的簇，同时，密度范围内的点标记为同样的簇标识；如果不是核心点，则根据定义5和定义6，判断是否满足直接密度可达和密度可达条件，如果符合条件，则把该密度范围内的点标记为符合该条件的分配给相应的簇中。

④ 直到数据集V(v1,v2,…,vn)中的每个数据点全部被标识后，根据定义7，判断是否存在噪声点，若存在，则标记为Oi(i=0,1,…)。

⑤ 把各个簇内各维坐标值累计求均值，结果输出Ci(i=1,2,…,k)。

(2) 增量聚类过程

① 设原始数据中心点(根据定义8)Ci(i=1,2,…,k)为△V(△v1,△v2,…,△vn)进行聚类的参考点(设为全局变量。

② 计算△V(△v1,△v2,…,△vn)中△v1的ρ(△v1,R)，如果是参考点，则计算该点到每个Ci(i=1，2，…，k)的距离，根据“就近原则”(到给定参考点最短距离)分配给相应的簇；如果不是参考点，根据初始聚类的过程进行聚类，实现新的簇△Ci(i=k+1,k+2,…)。

③ 根据定义7，判断△Ci(i=k+1,k+2,…)中是否存在噪声点，若存在，生成△Oi(i=0,1,…)；反之，生成新簇。

④ 对于其它的增量△vi(i=2,3,…,n)，依次循环执行②、③。

⑤ 结果输出聚类簇△Ci(i=1,2,…,k)。

当前强化信息化手段在农村经济管理中的应用，是农村经济管理现状的现实性要求，也是农村经济大繁荣大发展的必然性选择，更是农村经济管理者提升自身管理能力和管理水平的工作创新。只有农村经济管理者站在信息化时代视域推进信息化手段与管理工作的高度融合，才能提高农村经济管理工作的水平和效率，从而更好地引导广大农民发家致富。

2DICURDA算法MapReduce的实现

设初始数据集V(v1,v2,…,vn)，增量数据集为△V(△v1,△v2,…,△vn)，则ICURD算法MapReduce的实现如下：

① 将数据集V(v1,v2,…,vn)进行分割，划分为p(节点个数)块数据子集，并分配给p个子节点。

② 在各个子节点中，根据初始聚类过程计算出Ci(i=2,3,…,n)。

③ 在Reduce过程中，根据定义9，把Ci(i=2,3,…,n)中符合条件的簇进行合并；并根据定义7判断是否存在噪声点，若存在，则删除。

④ 把各个簇内各维坐标值累加求均值，结果输出Ci′(i = 2,3,…,n)。

⑥ 在各个节点中，根据增量的聚类过程计算出△Ci(i=1,2,…,k)。

⑦ 在Reduce过程中，根据定义9，把△Ci(i=1,2,…,k)中符合条件的簇进行合并；并根据定义7判断是否存在噪声点，若存在，则删除。

⑧ 把各个簇内各维坐标值累计求均值，结果输出。

3实验结果分析

3.1实验平台、测试数据集和评价指标

本文所有实验环境搭建的平台的组成为：2台2GHz Intel Xeon CPU、2 GB内存和4台2 GHz Intel Xeon CPU、1 GB内存的PC构成的。操作系统均为Ubuntu Linux 10.10，Hadoop版本选用1.1.2；Java开发包为JDK1.7版本，程序开发工具为Eclipse-standard-kepler-SR1-linux，算法使用Java实现。

实验数据集采用了UCI数据集下Synthetic_Control，分别构造了原始数据集为0.5、1、2、4、8、16 GB与增量为0.1、0.2、0.3、0.4、0.5 GB的60维不同大小的数据集来验证算法的可扩展性与时效性。为了验证算法的有效性，通过Iris数据集(数据对象150，属性4)，Wine(数据对象178，属性13)数据集，Libras数据集(数据对象360，属性90)，Diabetes(数据对象768，属性8)进行了实验，同时利用节点个数的不同验证了算法的可伸缩性。

在实验中，为了测试DICURDA算法的性能，本文采用了以下评价指标:时效性、可伸缩性和有效性。

3.2实验结果

3.2.1DICURDA算法的时效性

为了验证DICURDA算法在实际应用中的效果，在实验中，根据已给定的上述数据集，设原始数据集V为：0.5、1、2、4、8、16 GB，则增量数据集为△V为(0.1、0.2、0.3、0.4、0.5GB；根据给定数据集中结果聚类的个数，设R=42.25，T=10，D=42.23，则对增量△V利用DBSCAN与DICURDA算法进行了比较，如图4所示。

图4　DBSCAN算法与DICURDA算法的时效性对比

从图4可以看出，在获得同样正确的聚类个数的条件下，DICURDA算法比DICURDA算法的时效性高；其主要原因为：1)DICURDA算法在进行增量的聚类过程中已经获得了参考点，节省计算每个点密度的时间；2)当数据点不符合增量聚类过程时，重新初始聚类过程的数据点是少量的。所以，DICURDA算法的时效性比DBSCAN算法较高。

3.2.2DICURDA算法的有效性

为了进一步验证算法的有效性，文章根据不同的数据集，在已给定正确聚类个数的情况下，设不同类型的数据集作为是原始数据集与增量数据集；根据不同类型的数据集，设置了不同R、T与D不同的参数值进行了实验，具体如表1、表2所示。

表1　DBSCAN算法运行结果

表2　DICURDA算法运行结果

由表1与表2对比可知，DBSCAN算法参数设置比DICURDA算法的参数少，噪声点的个数也相对于DICURDA算法比较少。然而，DICURDA算法的正确率比较高，运行时间快；其主要原因为：1)DICURDA算法参数设置降低了云计算过程中由于数据分片不均匀导致分类错误的概率；2)在云计算动态的增量聚类规约过程中，参数D提高聚类的效率与精度；3)DICURDA算法的初始过程为下面的动态聚类提供了参考点，同时降低了增量聚类参数的敏感性。

3.2.3DICURDA算法的可伸缩性

为了更一步测试DICURDA算法的性能，算法采用原始数据集分别测试了不同节点下算法的运行时间，进一步验证了算法的可伸缩性，具体如图5所示。

图5　DICURDA算法的可伸缩性

从图5可以发现，算法的时效性不仅与数据集的大小有关，而且还与实验平台的数据节点密切系相关。当数据节点较少时，时效性呈现出线性变化的特点；当随着数据节点的不断增多，算法的执行效率变化越快。同时证明，该算法适合于大数据的处理。

3.2.4聚类效果比较

DICURD算法的参数R、D与T与DBSCAN算法的参数R与T有着相似的特点，并具有该算法的优越性；并且DICURD算法虽然初始参数同样难以确定。但是，对于DICURD算法来讲，一旦初始参数决定在以后的增量聚类过程中，则降低了参数的敏感性。同时该算法是一个不断的学习过程，对未知样本的分析提高了精度，具有接近线性的时间复杂性，能够动态地处理产生的新数据，并保持了前后聚类结果的一致性。整体来讲，DICURD算法优于DBSCAN算法。

4结语

DICURDA算法是基于密度的一种算法。本文利用云计算平台实现了DICURDA算法，无需保留原始数据就可以在增量过程中进行数据挖掘，节省了时间。本文从时效性、有效性与可伸缩性等不同角度分析了该算法可行性。然而，由于在初始聚类过程中仍然需要输入参数，所以，对于参数的设定仍需要进一步研究。

参考文献

[1] 杨静,高嘉伟,梁吉业.基于数据场的改进DBSCAN聚类算法[J].计算机科学与探索,2012,51(6):903-911.

[2] Loh W K,Moon Y S.Fast Density-Based Clustering Using Graphics Processing Units[J].Ieice Transactions on Information and Systems,2014,97(7):1349-1352.

[3] Wu Minghui,Zhang Hongxi,Jing Canghon.Cluster Algorithm Based on Edge Density Distance[J].Computer Science,2014,24(6),245-249.

[4] Li Hui Pi Dechang,Jiang Min.An incremen tal density clustering algorithm for cha otic time series[J].International Journal of Applied Mathematics and Statistics,2013,47(4):380-389.

[5] 孟静,吴锡生.一种基于聚类和快速计算的异常数据挖掘算法[J].计算机工程,2013(8):60-63,68.

[6] Singh Sumeet Awekar,Amit.Incremental shared nearest neighbor density-based clustering[C]//International Conference on Information and Knowledge Management,Proceedings.San Francisco,CA,United states.2013,31(2):1533-1536.

[7] Li Lingjuan,Xi Yang.Research on clustering algorithm and its parallelization strategy[C]//Proceedings-2011 International Conference on Computational and Information Sciences.Chengdu,Sichuan,China.2011,5(2):325-328.

[8] 郗洋.基于云计算的并行聚类算法研究[D].南京邮电大学,2011.

[9] 虞倩倩.基于数据划分的DBSCAN算法研究[D].江南大学,2013.

[10] Xie YongHong,Ma Ya Hui,Zhou Fang.PDBSCAN:Parallel DBSCAN for Large-Scale Clustering Applications[J].Journal of Donghua University (English Edition),2012,7(4):76-79.

[11] Fu Xiufen,Hu Shanshan.Research of parallel DBSCAN clustering algorithm based on Map Reduce[J].International Journal of Database Theory and Application,2014,7(2):41-48.

[12] Dai BiRu,Lin IChang.Efficient map/reduce-based DBSCAN algorithm with optimized data partition[C]//Proceedings 2012 IEEE 5th International Conference on Cloud Computing,CLOUD 2012.Honolulu,HI,United states.2012,4(2):59-66.

[13] Kim Y,Shim K,Kim M S.DBCURE-MR:An efficient density-based clustering algorithm for large data using MapReduce[J].Information Systems,2014,12(4):15-35.

[14] He Y B,Tan H Y,Luo W M.MR-DBSCAN:a scalable MapReduce-based DBSCAN algorithm for heavily skewed data[J].Frontier Sof Computer Science,2014,32(8):83-89.

[15] Fu XiuFeng,Wang Yaguang.Research andapplication of DBSCAN algorithm based on Hadoop platform[J].Lecture Notes in Computer Science,2014,83(5):73-87.

[16] Goyal Navneet Goyal Poonam,Mohta Mayank P.A multi-purpose density based clustering framework[J].Communications in Computer and Information Science,2011,168(3):538-540.

RESEARCH ON DYNAMIC AND INCREMENTAL DENSITY ALGORITHM BASED ON CLOUD COMPUTING PLATFORM

Meng HaidongRen Jingpei

(School of Information Engineering，Inner Mongolia University of Science and Technology，Baotou 014010,Inner Mongolia,China)

AbstractFor the problem of traditional density clustering algorithm that it is highly time complex and is not suitable for processing dynamic data when processing massive data,we proposed a density algorithm which uses reference points and MapReduce model for dynamic and incremental clustering.The creativity of it relies on that the algorithm realises a clustering algorithm capable of processing massive dynamic data,it guarantees the consistency of incremental clustering and re-clustering results,and has the characteristic of scalability as well.Experimental results demonstrated that the algorithm decreased the sensitivity of the parameter,improved the clustering efficiency and resource utilisation of density algorithm,and was suitable for big data analysis.

KeywordsReference pointsIncremental clusteringMapReduceDynamic density algorithm

收稿日期：2014-12-11。内蒙古自然科学基金项目(2012MS0611)。孟海东，教授，主研领域：数据挖掘技术，矿业系统工程。任敬佩，硕士生。

中图分类号TP311

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.004