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

基于近邻传播分布式数据流聚类算法 　　摘要： 　　针对分布式数据流聚类算法存在的聚类质量不高、通信代价大的问题，提出了密度和代表点聚类思想相结合的分布式数据流聚类算法。该算法的局部站点采用近邻传播聚类，引入了类簇代表点的概念来描述局部分布的概要信息，全局站点采用基于改进的密度聚类算法合并局部站点上传的概要数据结构进而获得全局模型。仿真实验结果表明，所提算法能明显提高分布式环境下数据流的聚类质量，同时算法使用类簇代表点能够发现不同形状的聚簇并显著降低数据传输量。 　　关键词：数据挖掘；分布式聚类；数据流；近邻传播；基于密度聚类 　　中图分类号：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 时间段内到达的数据， 窗口位置在时间轴上随着数据流不断滑动，窗口之外的数据不再处理，不必一次性将所有数据载入内存，只