DEN-Stream：一种分布式数据流聚类方法

李长路　王劲林　郭志川　韩　锐

1(中国科学院大学　北京 100190)2(中国科学院声学研究所国家网络新媒体工程技术研究中心　北京 100190)



DEN-Stream：一种分布式数据流聚类方法

李长路1,2王劲林2郭志川2韩锐2

1(中国科学院大学北京 100190)2(中国科学院声学研究所国家网络新媒体工程技术研究中心北京 100190)

摘要现有的数据流聚类方法很难兼顾数据稀疏和子空间聚类等高维数据难题，而分布式数据流对数据流聚类提出包括在线计算效率、通信开销以及多路数据的融合等更多挑战。提出分布式数据流聚类方法，采用全局统一的网格划分和衰退时间以支持多路数据流融合，并周期性检查和删除过期网格来控制概要规模。通过对多路高维数据流的一遍扫描，发现高维数据流子空间任意形状的聚类，并反映数据分布随时间的演化。在线组件效率高开销低，概要信息简洁，通信代价低。实验表明，该方法能够对分布式数据流正确聚类并演进，在线组件效率高，概要规模小。

关键词分布式数据流子空间聚类网格聚类高维数据

0引言

网络技术、互联网应用生态以及包括智能终端、传感器等各种数据采集设备的发展，使得分布式数据流作为一种广泛存在的数据组织形式[1,2]。数据流聚类挖掘技术已经成为一个重要研究领域，并广泛应用于电子商务、物理世界监测。数据流给传统聚类技术带来的主要挑战包括快速的数据吞吐、潜在无限、数据高维、只能执行一遍时序扫描、高效的存储需求以及反映数据分布的时间演进等[1]。实际的数据流大都来自分布式环境下的多个数据采集终端，除前述挑战外，还必须面临数据采集终端的资源约束、多路数据流正确融合[2]以及持续的数据通信带来的带宽占用。

著名的数据流聚类算法CluStream[3]首先提出的“在线—离线”二元组件结构。其中在线部分负责扫描数据流，形成关于数据分布的概要信息；离线部分采用基于距离的传统聚类算法k-means，利用在线部分提供概要信息挖掘产生聚类。CluStream还提出了金字塔形时间衰减结构来优化历史概要数据的储存。然而CluStream无力处理噪声、高维数据等数据流常见问题，同其他基于距离公式的方法一样，不能发现任意形状聚簇。后续的研究普遍继承了和发展了二元组件结构和高效存储思想，并针对性地发展了克服某些前述数据流难题，但很难同时解决现有挑战。

基于密度[4,5]和网格[6-9]的聚类方法普遍具有计算速度快，能够以便扫描数据发现任意形状聚类，因而成为数据流聚类的一类基本方法。而子空间聚类[10]也是数据流聚类的一个重要课题。D-Stream[6]基于密度网格方法，理论上能够发现任意形状任意数量的聚类，同时将新数据到达时概要信息更新复杂度降低。Li等人于2009年提出对D-Stream的改进版本[11]，引入“网格引力”概念，提高了聚类质量，但其概要信息更复杂，计算复杂度更高。这两种方法都只能发现摘要空间的聚类，不能对高维数据流进行子空间聚类；且在分布式多路数据流环境下，其关于网格密度上限、阈值的定理不再成立。文献[7,12]针对高维空间数据作了改进，但仍不是子空间聚类，且牺牲了计算效率。DS_CABOSFV[8]将静态高维数据聚类算法应用于数据流聚类，同样无法发现任意形状的子空间聚类。IGDCL[13]提出不规则网格划分的方法降低网格尺寸和边界带来的负面影响，该方法概要信息量大，网格维护复杂度高，在线部分资源占用过大，不规则的网格划分导致无法实现多路数据流的融合。

本文提出的数据流聚类方法DEN-Stream，采用主流的在线—离线二元结构设计，其离线核心算法采用密度意识子空间聚类算法DENCOS[14]。在线部分维护高维数据流全空间的网格概要信息，采用规则网格划分，特征向量简洁，更新效率高。离线部分采用基于密度网格的算法DENCOS[14]，发现任意形状的子空间聚类，并能有效克服高维数据的稀疏性，采用衰退因子反映全局统一的时间进化。由于在满空间存在大量空白网格，只在线维护非空白的有效网格以提高存储和通信资源使用效率。在分布式多路数据流上，网格密度上限定理不再成立，通过统计所有网格密度之和来计算后续挖掘过程中的参数，同时避免删除稀疏网格带来聚类误差。

1分布式数据流聚类方法研究

1.1网格划分

S=A1×A2×…×Ad表示d数据流的满空间，A1,A2,…,Ad为S的各个维度属性。其中Ai取值范围为[Mini,Maxi)，维向量L=(l1,l2,…,ld)存储响应维度的取值区间长度：

li=Maxi-Mini

(1)

每个维度被均匀分为k个间隔，则分辨率为：

(2)

数据流的d维全空间被划分为kd个矩形单元组成的网格。

1.2特征向量

d维空间网格结构中每一个网格由一个特征向量描述，其定义为(id,D,tg)。其中tg为该网格最后一个数据点到达时间，D为该网格的密度在最后一个数据点到达时更新的结果，空网格置零。若在时刻t一个新的数据点x到达，其对应网格密度更新为：

D(g,t)=1+D(g,tg)×λ(t-tg)

(3)

任何数据对网格密度的贡献随着时间延伸而减弱，后到达数据对网格密度具有更大的贡献。λ(λ∈(0,1))为网格密度的时间衰退因子。

id为识别网格的编号，为了便于将数据点x=(x1,x2,…,xd)映射到对应的网格，定义id为：

(4)

所有网格的编号为1至kd的正整数。由于全局统一的网格划分以及网格标识，使得分布在多个数据流中的数据在摘要中影响了相同标识的网格密度，多路数据流网格密度计算空间上保持全局一致。

1.3时间度量与多路融合

D-Stream[5]模型中的时间实际上是单独数据流中数据抵达顺序编号。在分布式多路数据流环境下，融合时拿到的是概要信息，是无法对来自不同子数据流的数据进行顺序编号。即使在单独数据流中，如果数据不是按均匀的时间间隔采集，这种衰退方法也无法准确反映聚类随着时间的演化。简单的相加可能导致不同子数据流中的两组数据，在时间上先到达的数据，对网格密度的贡献大于时间上后到达的数据。

本文采用实际时间作为聚类演化的依据，统一各路数据流的时间，从而使多路数据流融合成为可能。总共m路数据流，对于网格g，在当前时间刻度t的密度融合计算公式为：

(5)

根据式(5)，不同子数据流的网格密度根据其更新时间，计算出当前时间的衰减后密度，相加得到多路数据流总的网格密度。不同数据流的数据点在融合时都以相同的时间度量衰减，与同一子数据流内数据处理相同，分布在多个路数据流中的数据衰退情况与同一个数据流中的衰退一致。时间衰退的全局一致与空间密度计算的全局一致，确保本文方法具有很好的可扩展性，理论上其工作性能不受数据采集终端数量限制。

1.4概要信息的在线维护

gridlist为存储子数据流概要信息的链表，其成员为非空网格的特征向量，按网格id顺序排列。由于引入时间衰退因子来反映流中数据分布的演化，所有网格的密度都随着时间变化。对于没有新数据到来的网格g，其任意时间的密度为：

D(g,t)=D(g,tg)×λ(t-tg)

(6)

根据式(6)，只需要知道其特征向量，即可计算出当前时刻密度。因此，没有必要不断更新gridlist中所有网格的特征向量，只需根据式(3)更新新到达数据点所在网格即可。这有效提升了在线算法的时间效率。

如果新到达数据对应的网格当前是空的，则gridlist中不存在该网格的特征向量，需要网格特征向量插入gridlist中响应位置。随着时间推移，gridlist中的网格会越来越多，在高维数据空间，进行较高精度的网格划分时，gridlist中网格数量上限kd很大。gridlist中网格过多，会降低在线算法的时间空间效率，同时增加与远端离线部分的通信开销。因此有必要定期删除过期网格。

过期网格是这样的网格：这些网格在很久之前曾经有数据到达，但当前相当一段时间无数据点到达。随着时间推移，这些网格密度衰退，以至于远小于致密网格的阈值。无论考察其时间相关性还是密度值的大小，这类网格对于当前时刻的数据分布影响甚微，可以忽略不计。为了避免这类网格带来的资源负担，每次提交概要之前检查网格最后更新时间，距离当前时刻超过阈值to的视为过期网格删除。当to足够大时，提交的概要信息为真实统计信息的近似值，不影响聚类结果。

1.5离线聚类生成

对于融合多路数据流融合后的概要信息gridlist-sum，根据式(5)其每个网格的密度为当前时刻的密度，则当前d维空间所有网格总重量等于所有n个非空网格的密度和：

(7)

由于任意子空间的网格密度可以通过d维全空间投影得到，因此gridlist-sum提供了DENCOS[14]发现任意子空间聚类的完整信息，S的任一p维子空间Sp每个网格的平均密度为：

(8)

如果一个p维致密网格的密度不小于该子空间阈值，则认定为致密网格,阈值为：

(9)

根据式(4)可以得到每一个网格id对应的频繁模式向量表示g=(v1,v2,…,vd)，其中vi与[(xi-Mini),εi]一一对应，为第i维上第[(xi-Mini),εi]+1个间隔区间。DENCOS根据以上信息，找出所有子空间聚类并输出。

1.6确定gap及t0的策略

在线部分按周期gap删除过期网格并提交概要信息。gap取值的约束条件包括离线部分聚类的速度和网格密度衰退的速度。周期过短，频繁地提交并聚类运算，造成过多的资源负担，而实际聚类又没有明显变化因而没有意义；周期过长，则可能无法捕捉数据流分布的演进。

由式(9)可知，d维满空间的阈值最小，且维度数相差1的子空间阈值间存在k倍关系。可以认为一个没有新数据到达的网格其密度衰退k倍，即是数据分布发生明显改变的关键时间点。则：

λgap=k

(10)

用k作为基准来决定周期的另一个好处是，随着k增大，网格衰退的和离线计算两个约束条件都变慢，反之都变快，便于决定周期取值。

确定过期网格是为了避免gridlist随着时间单调递增带来的开销负担，其约束条件主要是数据采集终端资源，以及过期网格的密度衰退至足够小，以至不对聚类结果造成影响。因此在终端资源允许的情况下，to应取值尽量大，以满足：

to≫lnλ(τd)

(11)

2分布式数据流聚类算法设计

2.1在线算法

除待处理的数据流外，在线部分的算法需要用户提供若干参数，包括数据流的维数d,以及划分网格需要的参数k和L，用以建立网格结构。L为一个向量，依次代表每个维度取值范围，在网格划分过程中将每个维度划分为等长的k个间隔。gridlist为存储非空网格特征向量列表,存储数据在整个网格空间分布的概要信息，初始为空。数据流中新的数据x=(x1,x2,…,xd)到达，首先计算其对应的密度网格g的id。如果之前没有数据到达该网格或该网格数据由于过于陈旧被清除，则需要向gridlist中插入该网格的特征向量，否则直接更新该网格特征向量。在线部分以gap为时间周期，移除过期网格，提交gridlist至离线部分，离线部分依据多路数据流的概要信息生成类。在线部分算法如下：

1procedure DEN-Stream-online

//input d,k,L

2gridlist=grid-partition;

3while data stream is active do

4read record x=(x1,x2,…,xd);

5compute the id of density grid g which contains x;

6if g not in gridlist then insert g to gridlist;

7update the characteristic vector of g;

8if t mod gap==0 then

9remove grids out of date;

10commit gridlist;

//offline clusters with it

11end if

12end while

13end_procedure

2.2离线算法

多路数据流概要信息在离线部分被融合，gridlist-sum存储多路数据流融合后的概要信息。融合的过程遍历每一个子数据流提交的概要信息，求出每个网格总的密度。离线部分算法如下：

1procedure DEN-Stream-offline

//input d,k,α

2gridlist-sum=grid-partition;

3for each substream

4for each member vector g of gridlist

5if g not in gridlist-sum then insert g to gridlist-sum;

6translate grid to vector presentation;

7update the characteristic vector of g in gridlist-sum;

8end for

9end for

10Compute the total weight W of all grid in gridlist-sum;

11call method DENCOS(d,k,W,α, gridlist-sum);

12end_procedure

根据聚类DENCOS[14]模型，需要将id指代的网格转换为d维向量描述作为后期挖掘的频繁项，网格的密度将会在聚类生成过程中作为网格向量的频繁计数。

在开始聚类过程之前，需要计算gridlist-sum中所有网格的密度之和，亦即总的“重量”W，结合用户指定的参数α[14]，DENCOS子空间聚类过程中的密度阈值得以确定。

3测试评估与分析

3.1测试数据集

为了验证方法反映数据分布随着时间演进的性能，采用合成二维数据集DS1，所有16 000个数据点均匀分布在x轴100～900之间，y轴400～600之间，长800，宽200。数据集包含每个数据点到达时刻心系，时序上x=100处数据最先到达，数据点以均匀的速率在时间T内从x=100开始匀速移动至x=900覆盖整个区域。在后续验证方法效率和形成概要规模时，采用从加州大学欧文分校提供的用于机器学习的数据库(http://archive.ics.uci.edu/ml/)选取的真实数据集DS2。

3.2实验结果与分析

(1) 衰退与演进

为了验证分布式多路数据流环境下正确反映数据分布演进的能力，将DS1分为不均等三路数据流，数据点比例为5:2:1。数据点在各自子数据流中的到达时间为DS1中到达时刻相同，即每个子数据流中数据点到达不均匀，速率不相等。在数据持续时间T内，四个不同时刻输出的聚类结果如图1所示。可以看出，方法任意时刻的聚类输出能够随着数据分布规律的变化演进，反映当前时刻及最近一段时间内到达数据的分布规律，而较早到达的数据随着时间推移衰退殆尽，不影响当前聚类效果。

图1　不同时刻聚类结果的演进

图2反映了不同衰减因子下较早到达的数据对聚类结果的影响。选择t=T时刻，即所有数据完全到达时刻，分别选择四个不同的衰退因子取值。聚类结果表明方法能够在多路环境下正确反映较早数据及其分布规律在聚类结果中的渐进衰退。衰退因子越小，衰退越迅速。

图2　不同衰退因子下历史聚类的衰退

(2) 在线效率

从数据集DS2随机选取一个5维空间，共60 000数据点的数据集，使其按时间顺序均匀到达，形成一个稳定数据流。分别用本文方法在线算法和D-Stream[5]算法的在线算法处理该数据流，两种算法都在每个在线周期内吸收100个数据点，维护在线概要并提交。对比两种算法处理每个gap内数据所需时间如图3所示。

图3　在线算法时间效率对比

由图3可知，两个算法在启动阶段，由于要不断向空的概要信息中插入新的网格，会导致较大的时间开销，之后逐渐趋于稳定。本文算法在第100个gap和第470个gap附近有数次时间开销的峰值，原因在于此时数据分布随着时间发生迁移，生成的聚类发生明显改变。这个过程中新旧聚类的网格同时存在于概要信息中，增加了在线算法的时间空间开销。聚类迁移完成，数据分布稳定在新的聚类区域后，本算法概要信息中只存在新聚类的网格，而早前聚类网格作为过期网格被删除，在线算法的时间、空间开销恢复稳定。400gap之后本文算法比对比算法时间效率高85%～208%。

对比算法在每次数据流聚类迁移之后时间开销就会经历一次增长。原因在于按照密度阈值抛弃过期网格，在较高维度空间需要更长的时间。高维数据空间存在大量的空白网格，仅少数网格存在数据，聚类区域的密度会远大于整个高维空间的平均密度。因此，即使没有新的数据点到达，聚类区域网格的密度要衰减到平均密度以下也是一个漫长的过程。在概要信息中保留旧聚类网格不仅降低在线算法的效率，增加开销，还会在当前时间输出早期聚类，形成错误聚类结果。

(3) 概要规模

与在线算法时间效率对比相同的实验相同方法，对比两个算法在每个gap形成的概要信息规模。如图4所示，实验结果与时间效率对比实验的结果相符。本文算法由于及时抛弃过期网格，能够在每次数据分布改变之后迅速将概要信息规模恢复至合理范围，压缩需要通信的概要规模73.5%～82.1%，节约通信带宽。而对比算法D-Stream在相当长时间内不能抛弃过期网格，在数据分布改变数次之后仍保留最早期的概要网格，导致概要信息不断累积，造成资源浪费的同时引入早期聚类结果，不能正确反映数据分布随时间的演进。

图4　概要信息规模对比

4结语

本文提出的分布式数据流聚类方法，采用全局统一的网格划分和密度衰退，使得多路数据流概要信息融合的过程简洁、意义明确、准确性高。通过适当的过期网格抛弃策略将概要信息规模维持在合理水平，提高了在线算法运行的时间、空间效率并降低概要信息提交过程中的通信开销。尤其在高维数据流处理过程中，本文算法与对比算法相比，优势更加明显。实验表明，本算法能在分布式多路数据流环境下找出正确聚类，并根据数据分布随时间的迁移，演进聚类结果；同时，本文算法具有更高的在线效率和更小的概要规模以节省带宽资源。

参考文献

[1] 张建朋,陈福才,李邵梅,等.基于仿射传播的进化数据流在线聚类算法[J].模式识别与人工智能,2014,27(5):443-451.

[2] 郭昆,张岐山.基于灰关联分析的多数据流聚类[J].模式识别与人工智能,2011,24(6):769-775.

[3] Aggarwal C C,Han J,Wang J,et al.A framework for clustering evolving data streams[C]//Proceedings of the 29th international conference on Very large data bases-Volume 29.VLDB Endowment,2003:81-92.

[4] 于彦伟,王沁,邝俊,等.一种基于密度的空间数据流在线聚类算法[J].自动化学报,2012,38(6):1051-1059.

[5] Amini A,Saboohi H,Wah T Y.A Multi Density-Based Clustering Algorithm for Data Stream with Noise[C]//Data Mining Workshops,IEEE International Conference on.IEEE,2013:1105-1112.

[6] Chen Y,Tu L.Density-based clustering for real-time stream data[C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM,2007:133-142.

[7] Ren J,Cai B,Hu C.Clustering over data streams based on grid density and index tree[J].Journal of Convergence Information Technology,2011,6(1):83-93.

[8] Pan J.DS_CABOSFV clustering algorithm for high dimensional data stream[C]//2012 4th International Conference on Awareness Science and Technology (iCAST),IEEE,2012:16-19.

[9] Zhang D,Tian H,Sang Y.A Clustering Algorithm Based on Density-Grid for Stream Data[C]//Parallel and Distributed Computing,Applications and Technologies,International Conference on.IEEE,2012:398-403.

[10] 于翔,印桂生,许宪东,等.一种基于区域划分的数据流子空间聚类方法[J].计算机研究与发展,2014(1):88-95.

[11] Tu L,Chen Y.Stream data clustering based on grid density and attraction[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2009,3(3):167-176.

[12] Chairukwattana R,Kangkachit T,Rakthanmanon T,et al.Efficient evolution-based clustering of high dimensional data streams with dimension projection[C]//Computer Science and Engineering Conference (ICSEC),2013 International.IEEE,2013:185-190.

[13] Hou G B,Yao R X,Ren J D,et al.Irregular Grid-based Clustering Over High-Dimensional Data Streams[C]//2010 First International Conference on Pervasive Computing Signal Processing and Applications (PCSPA),IEEE,2010:783-786.

[14] Chu Y H,Huang J W,Chuang K T,et al.Density conscious subspace clustering for high-dimensional data[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(1):16-30.

收稿日期：2014-12-03。国家科技支撑计划项目(2012BAH73 F01)；国家高技术研究发展计划项目(2011AA01A102)；中科院先导专项课题(XDA06040301)。李长路，博士生，主研领域：数据挖掘，用户兴趣建模。王劲林，研究员。郭志川，副研究员。韩锐，副研究员。

中图分类号TP3

文献标识码A

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

DEN-STREAM：A DISTRIBUTED DATA STREAM CLUSTERING METHOD

Li Changlu1,2Wang Jinlin2Guo Zhichuan2Han Rui2

1(UniversityofChineseAcademyofSciences,Beijing100190,China)2(NationalNetworkNewMediaEngineeringResearchCenter,InstituteofAcoustics,ChineseAcademyofSciences,Beijing100190,China)

AbstractCurrent data stream clustering methods are difficult to take into account the high-dimensional data problems including data sparsity and subspace clustering, etc., while the distributed data stream raises more challenges on data stream clustering, such as online computational efficiency, communication overhead and the integration of multi-channel data. The distributed data stream clustering method proposed in this paper uses globally uniform meshing and declining time to support the integration of multi-channel data streams, and controls the summary size by periodically checking and removing outdated grids. By scanning multi-channel high-dimensional data stream once, the method finds the clusters with arbitrary shapes in subspace of high-dimensional data stream, and they reflect the evolution of data distribution over time. The online component in the paper has high efficiency and low overhead, succinct summary information and low communication cost. Experiment shows that the proposed method can correctly cluster the distributed data streams and evolve them, the efficiency of online component is high, and the summary size is small as well.

KeywordsDistributed data streamSubspace clusteringGrid-based clusteringHigh-dimensional data