基于近邻传播的分布式数据流聚类算法

摘要：

针对分布式数据流聚类算法存在的聚类质量不高、通信代价大的问题，提出了密度和代表点聚类思想相结合的分布式数据流聚类算法。该算法的局部站点采用近邻传播聚类，引入了类簇代表点的概念来描述局部分布的概要信息，全局站点采用基于改进的密度聚类算法合并局部站点上传的概要数据结构进而获得全局模型。仿真实验结果表明，所提算法能明显提高分布式环境下数据流的聚类质量，同时算法使用类簇代表点能够发现不同形状的聚簇并显著降低数据传输量。

关键词：数据挖掘；分布式聚类；数据流；近邻传播；基于密度聚类

中图分类号：TP181自动推理、机器学习

文献标志码：A

0引言

随着传感器网络、通信技术以及分布式计算的发展，在Web网站访问流量分析、互联网流量监测、传感器网络中的入侵监测等应用中，大量的数据都是以流的形式产生的，这些数据流的特点是海量的、时序的、快速变化的和潜在无限的[1-3]。随着流量的日益增大，数据处理结构呈现出一种分布式特征，面向分布式数据流的聚类近年来一直是研究的热点[4-6]。

聚类数量巨大而且分布在不同站点的数据流， 需解决关键通信链路负载过重、中央站点存储和计算时间有限的问题。文献[7]算法采用层次聚类的方法将各个局部站点数据生成树状图，再由中心站点重组所有局部站点上传的树状图充分统计量，得到全局树状图描述。Januzaj等[8-9]相继提出了DBDC（DensityBased Distributed Clustering）及其改进算法SDBDC（Scalable DBDC）。算法在各站点执行DBSCAN（DensityBased Spatial Clustering of Applications with Noise）算法，将相对简洁的聚类描述传递到中心站点，中心站点进行全集聚类生成全局聚类模型。以上方法的缺点是不适合连续聚类问题，对数据流处理需要不停地交换局部模型，导致通信代价过大。Zhou等[10]提出基于EM混合高斯模型的CluDistream算法，通过为不同簇分配不同隶属度的方式解决分布式数据流中数据簇的交叠问题，该算法的局限是EM算法本身的复杂度且要求数据符合模型分布，不能很好地处理噪声数据，在典型算法基础上，国内研究学者在处理分布式的数据流方面做出了贡献[4-6，11]。

针对现有数据流聚类算法存在的聚类质量不高、通信代价大的问题，提出了密度和代表点聚类思想相结合的分布式数据流聚类（Density and Affinity Propagation Based Distributed Clustering， DAPDC）算法。局部站点通过近邻传播算法得到的微簇代表点的概念来描述数据流的分布概况，一定程度上弥补了DBDC算法在精度和效率上的不足，微簇代表点信息很好地反映了局部站点的概要结构，通信数据量远小于DBDC所产生的核心对象，全局站点则采用密度融合聚类的方式合并局部站点上传的概要数据结构进而获得全局模型。仿真实验结果表明，DAPDC能明显提高分布式环境下数据流的聚类质量，同时算法使用类簇代表点能够发现不同形状的聚簇并显著降低数据传输量。

1问题描述和相关概念

1.1近邻传播算法（Affinity Propagation）

1.2分布式数据流网络结构

本文的分布式数据流网络结构如图1所示，它由n个局部站点与一个中心站点形成。为了降低该网络结构的通信量，数据流流入各个局部站点后，局部站点应将数据流的统计模型传送给中心站点，而不是传送数据流中所有的数据信息。中心站点对各数据流的处理也是对局部站点传送的模型进行聚类操作，得到全局模型，并向局部站点广播全局模型，使局部站点的模型列表得到更新[6]。当中心站点接收到用户挖掘请求（User Mining Request）时，将挖掘结果（Mining Results）也就是全局模型发送给用户。同时，局部站点也可以接收用户挖掘请求，将最近一次收到的广播全局模型列表发送给用户。分布式数据流网络结构的信息交互方式是：每个局部站点仅需与中心站点进行信息交换，因为中心站点在得到全局模型的同时，通过广播最新的全局模型，可以让局部站点i获得其他任意局部站点j的聚类信息（j≠i），所以不同局部站点之间不用进行直接的通信。该信息交互方式能够达到降低分布式数据流网络结构通信代价的目的，并能提高局部站点模型列表的实时性和准确性。

2.1算法的基本思想

DAPDC算法可分为三个部分：

1）局部站点接收数据采用滑动时间窗口模型[11]。滑动窗口模型只包含当前w 时间段内到达的数据， 窗口位置在时间轴上随着数据流不断滑动，窗口之外的数据不再处理，不必一次性将所有数据载入内存，只需保存当前时间窗口内的数据即可，从而节省了内存的开销。

2）微簇在线维护。局部站点针对衰减窗口内的数据流进行处理，根据窗口周期、权重阈值、半径大小、误差因子和衰减系数等参数来计算数据的权重，并存储数据流中数据所包含的信息，动态地更新维护数据流的概要数据结构，在线生成微簇。

3）局部数据上传至中心站点，在中心站点根据用户请求用密度融合的方式完成全局聚类。

其中，局部站点采用近邻传播聚类算法，这样做可以保证局部站点的挖掘精度和挖掘效率，生成快速生成类代表点的概要结构，同时保证数据在到达时可以被及时地处理而不至于被丢弃；在局部站点采用了滑动窗口技术，即当滑动窗口收集足够的数据后，所有的数据都被获取并进行统一的处理，滑动窗口则进行新数据的再收集，同时将该概要结构表示上传与中心站点。中心站点采用的是基于改进的密度聚类算法综合处理，得到全局聚类模型并将该列表广播给局部站点。为了保证聚类后得到的模型具有同步性，假设整个分布式数据流网络结构具有全局时间。

2.2局部站点生成代表点算法

代表点的选取按如下两个步骤进行：1）生成候选代表点集合；2）根据阈值大小过滤代表点集。过滤候选中心点集需要对其进行一次单遍扫描。局部站点聚类 （Generate Exemplar Base on Affinity Propagation， GEBAP）算法描述如下。

局部站点聚类结束之后，要将聚类概要数据结构传至中心站点形成全局最优的簇结构，将已存在的模式与当前新增数据进行融合来不断地更新生成最新的全局模式。中心站点使用t-1时刻的模式加上t时刻收集到的新数据，通过增量式的聚类算法形成t时刻的全局聚类模式，对中心站点的聚类模式进行动态更新。本文中全局聚类采用改进的DBSCAN算法实现全局聚类算法描述如下。

3.2.1局部站点聚类质量

为了评价DAPDC的局部站点聚类质量，在界标窗口下数据流聚类质量的比较结果如图2所示。连续监控了多个时间窗口，选定特定的5个代表性时间戳，图2显示DAPDC具有相当优良的聚类质量。它的聚类质量总体优于其他两种算法，是因为DAPDC通过局部代表点生成算法更加准确地描述了局部概要信息，可以有效地将具有不同分布的数据划分到所属的数据模型中。

另外由于中心站点有广播中心模型列表的机制，随着各局部站点不断上传局部站点模型列表，中心站点通过合并机制得到中心模型列表，并将列表进行广播，使得局部站点的模型列表信息不断更新，不同局部站点的模型列表信息实现了相互传递。广播中心模型列表机制克服了局部结果的不完整性，能够让局部站点得到更全面的模型列表，也就是更精准的数据流聚类信息，从而也提高了局部站点数据流聚类质量。

3.2.2中心站点聚类质量

4结语

本文在深入研究目前典型的分布式聚类算法的基础上，提出了适合分布式环境下的数据流聚类算法——DAPDC算法。该算法首先在各子站点生成局部模型，主要步骤是在各子站点生成局部核心微簇特征向量；然后，将子站点的局部模型传递至主站点，主站点根据收集到的局部核心信息，再次扫描生成全局核心对象，经过筛选和融合，得到全局核心对象聚类的结果；最后，各子站点根据该结果对各个局部站点进行聚类更新。本文的主要贡献包括：1）在局部站点聚类上利用近邻传播聚类算法生成核心微簇代表点特征向量，用来反映局部站点各个时间段的微簇结构，设计了局部站点生成代表点（GEBAP）算法，降低了局部站点与中心站点间的通信代价；2）中心站点基于各个局部站点上传的概要结构，设计了改进的DBSCAN算法生成全局簇模型，充分考虑了各站点微簇的

分布情况，得到更为精确的全局结果；3）通过实验表明

DAPDC算法具有良好的聚类质量、较快的处理速度、较少的数据传输量，能够适应分布式流环境下的聚类要求。

参考文献：

[1]孙玉芬，卢炎生.流数据挖掘综述[J].计算机科学，2007，34（1）：15-11.

[2]胡仲义，郭超，王永炎，等.基于时间衰减和特征变量的数据流聚类算法[J].计算机研究与发展， 2012，49（S1）：155-162.

[3]NTOUTSI I， ZIMEK A， PALPANAS T， et al. Densitybased projected clustering over high dimensional data streams[C]// Proceedings of the 6th International Conference on Scalable Uncertainty Management， LNCS 7520. Piscataway， NJ： IEEE Press， 2012：311-324.

[4]GAO B， ZHANG J. Density based distribute data stream clustering algorithm[J]. Journal of Software， 2013， 8（2）： 435-442.

[5]HUANG J H， ZHANG J Y. Fuzzy Cmeans clustering algorithm with spatial constraints for distributed WSN data stream[J]. International Journal of Advancements in Computing Technology，2011，3（2）：165-175.

[6]刘力雄，郭云飞，康晶，等.分布式数据流聚类算法[J]. 计算机工程与设计，2011，32（8）：2708-2711.

[7]SAMATOVA N F， GEIST A， OSTROUCHOV G， et al. Parallel outofcore algorithm for genomescale enumeration of metabolic systemic pathways[C]// IPDPS 2002： Proceedings of the 16th International Parallel and Distributed Processing Symposium. Washington， DC： IEEE Computer Society， 2002： 249.

[8]JANUZAJ E， KRIEGEL H P， PFEIFLE M. DBDC： Density based distributed clustering[C]// Advances in Database TechnologyEDBT 2004. Berlin： Springer， 2004： 88-105.

[9]JANUZAJ E， KRIEGEL H P， PFEIFLE M. Scalable densitybased distributed clustering[C]// Knowledge Discovery in Databases： PKDD 2004. Berlin： Springer， 2004： 231-244.

[10]ZHOU A， CAO F， YAN Y， et al. Distributed data stream clustering： a fast EMbased approach[C]// ICDE 2007： Proceedings of the 23rd IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2007：736-745.

[11]倪巍伟，陈耿，吴英杰，等.一种基于局部密度的分布式聚类挖掘算法[J].软件学报， 2008，19（9）： 2339-2348.

[12]FREY B J， DUECK D. Clustering by passing messages between data points[J].Science，2007，315（5814）：972-976.

[13]ZHANG X， FURTLEHNER C， SEBAG M. Data streaming with affinity propagation[C]// ECML PKDD 2008： Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases， Part II. New York： ACM Press， 2008：628-643.

[14]KRANEN P， KREMER H， JANSEN T， et al. Stream data mining using the MOA framework[C]// DASFAA 2012： Proceedings of the 17th International Conference on Database Systems for Advanced Applications， LNCS 7239. Berlin： Springer， 2012： 309-313.