韩东红¹, 王坤¹, 邵崇雷², 马畅¹
1.东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;
2.沈阳理工大学 机械工程学院, 辽宁 沈阳 110159
收稿日期: 2015-08-28
基金项目: 国家自然科学基金资助项目(61173029, 61332006, 61672144)。
作者简介: 韩东红(1968-), 女, 河北平山人, 东北大学副教授。

摘要: 作为大数据的重要组成, 产生于传感器、移动电话设备、社交网络等的不确定流数据因其具有流速可变、规模宏大、单遍扫描及不确定性等特点, 传统聚类算法不能满足用户高效实时的查询要求.首先利用MBR (minimum bounding rectangle)描述不确定元组的分布特性, 并提出一种基于期望距离的不确定数据流聚类算法, 计算期望距离范围的上下界剪枝距离较远的簇以减少计算量；其次针对簇内元组的分布特征提出了簇MBR的概念, 提出一种基于空间位置关系的聚类算法, 根据不确定元组MBR和簇MBR的空间位置关系排除距离不确定元组较远的簇, 从而提高聚类算法效率；最后在合成数据集和真实数据集进行实验, 结果验证了所提出算法的有效性和高效性.
关键词：不确定数据流聚类大数据数据挖掘最小边界矩形
A Cluster Algorithm for Uncertain Data Stream
HAN Dong-hong¹, WANG Kun¹, SHAO Chong-lei², MA Chang¹
1.School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2.School of Mechanical Engineering, Shenyang Ligong University, Shenyang 110159, China
Corresponding author: HAN Dong-hong, E-mail: handonghong@cse.neu.edu.cn
Abstract: As an important component of big data generated in the sensor, mobile phone devices, social networks etc., uncertain streaming data have many characteristics, such as variable rate, large-scale, single-pass scanning, and uncertainty. Traditional clustering algorithms cannot meet efficient real-time inquiry requirements for the users. Firstly, MBR (minimum bounding rectangle) was used to describe the distribution characteristics of uncertain tuples. And then, a clustering algorithm based on expected distance was proposed for uncertain data stream. The bounds of expected distance range to filter the clusters with far distance can be calculated. Secondly, cluster MBR concept based on the distribution of the tuples in a cluster was presented. Then, a clustering algorithm was given, which excludes the clusters far from the uncertain tuple by the spatial location relationship between uncertainty tuple MBR and clusters MBR, thereby increasing the efficiency of clustering algorithm. Finally, experiments running on synthetic datasets and real datasets verify that the proposed algorithms are effective and efficient.
Key Words: uncertain data streamclusterbig datadata miningMBR (minimum bounding rectangle)
近年来, 社交网络、移动电话应用、电子商务网站等产生的数据呈指数级增长, 面向大数据的分析和处理技术的研究方兴未艾.作为大数据的一种数据模型, 广泛存在于实时监控系统、基于位置的服务(LBS)^[1]、传感器网络^[2]、射频识别电子标签(RFID)^[3-4]等的不确定数据流, 因其具有数据量规模宏大、高速、单遍扫描及不确定性等特征, 需设计高效实时的增量算法对其进行聚类分析.
数据的不确定性是由数据采集及传输、数据集成等原因产生的, 可分为元组级不确定性和属性级不确定性^[5-6].数据流环境下聚类分析面临的主要挑战是对源源不断到来的数据进行实时高效处理, 不确定性的引入增加了解决这一挑战的难度.
Aggarwal等^[7]提出了最早的聚类演化数据流的双层框架结构--CluStream算法, 将聚类过程分为在线聚类和离线聚类两部分.Aggarwal等在2008年提出了UMicro算法^[8]以解决属性级不确定数据流的聚类问题.文献[9]提出一种基于投影空间的不确定数据流聚类算法UPStream.针对离散概率模型中的元组级不确定性问题, 文献[10]提出基于信息熵的不确定数据流聚类算法LuMicro.文献[11]提出通过利用不确定聚类特征的指数直方图来获取最新数据的分布特征的方法, 采用双层架构模型对不确定数据流进行聚类.文献[12]考虑不确定元组期望值和不确定性, 提出基于Voronoi图的聚类算法以减少滑动窗口中期望距离计算量.文献[13]引入动态更新以适应数据变化的免疫模型, 提出对元组级不确定流数据进行聚类的IUMicro算法.文献[14]提出UIDMicro聚类算法, 分别用标准差和区间数来表示不确定流数据, 同时采用two-layer聚类窗口模型和动态聚类模型更新策略对不确定数据流聚类.文献[15]提出UDSSC算法使用滑动窗口机制接收新数据, 引入子空间簇生成策略和新型离群点机制.文献[16]提出基于不确定数据流聚类的动态通信距离评估方法.
本文侧重研究离散概率模型表示的元组级不确定数据流的聚类算法, 旨在提高算法执行效率.
1 不确定数据流聚类算法1.1 基于期望距离的不确定数据流聚类算法1.1.1 相关定义定义1 ?不确定数据流.若干随时间变化的d维不确定元组构成不确定数据流S, S={(X₁, t₁), (X₂, t₂), …, (X_i, t_i), …}, 其中X_i是一个d维的元组, 由k_i个可能的实例组成, X_i=( < x_i1, p_i1 > , < x_i2, p_i2 > , …, < x_iki, p_iki > ), p_ij表示第j个实例出现的概率, 且0 < p_ij≤1, =1, t_i表示元组X_i到达的时间戳.
定义2 ?期望距离.X_i和簇心c_j的期望距离为X_i内所有可能实例到c_j距离的期望之和, 即

(1)

定义3 ?不确定元组的MBR.即包含元组内所有可能实例的最小边界矩形, 用以下d维向量分别表示MBR的下界和上界:
lower=(min (x_i⁽¹⁾), min (x_i⁽²⁾), …, min (x_i^(d))),
upper=(max (x_i⁽¹⁾), max (x_i⁽²⁾), …, max (x_i^(d))).
其中：min (x_i^(j))表示X_i在第j维上的最小值; max (x_i^(j))表示X_i在第j维上的最大值.
定义4 ?微簇的聚类特征结构.包含d维的X_i的微簇聚类特征结构用(2×d+2)元组(CF₁, CF₂,t, n)表示, 其中CF₁是d维向量, 为每个不确定元组期望值的线性和, 第q项存储内容为, k_i是第i个不确定元组内实例数目；CF₂是d维向量, 为不确定元组期望值平方和；t表示微簇最后更新时间；n表示微簇内不确定元组个数.
引理1 ?当微簇C加入新不确定元组 < X_i, t > , 微簇聚类特征结构的各项均可增量更新(证明略).
定理1 ?不确定元组X_i的MBR内至少存在一个确定点x', 使得x'到簇心c_j的距离与X_i到簇心c_j的期望距离相等, 即d(x′, c_j)=ED (X_i, c_j).
定理2 ?若y_i为X_i的MBR的几何中心, 对角线长度为2r, ED (X_i, c_j)为X_i到点c_j的期望距离, 则

(2)

1.1.2 算法描述本文提出聚类不确定数据流的EDMicro算法, 使用定义4的聚类特征结构在线维护微簇, 并使用算法1作为在线聚类的处理流程, 其在线微簇作为输出参与后续的离线宏聚类.行7中, 若不确定元组X_i到c_j的期望距离小于Threshold, 则当前点属于该微簇, 否则X_i属于一个新微簇或是离群点, Threshold的设置方法同文献[10].若X_i属于一个新微簇或为离群点, 则为其建立一个新微簇.如果当前微簇的个数小于n_micro, 直接新建微簇, 否则删除当前微簇集中最久未更新的微簇.EDMicro算法的伪代码见算法2.
算法1 ?不确定数据流在线聚类算法
输入：最大微簇数目n_micro, 不确定数据流S
输出：微簇的集合C
1. REPEAT
2.从S中读入新元组 < X_i, t_i > ；
3. IF X_i是第一个元组
4. ???直接为X_i创建一个新的微簇；
5. ELSE
6. ???CALL某种算法找到距离X_i最近的微簇c_j；
7. ???IF ED (X_i, c_j)≤Threshold
8. ????X_i属于簇C_j并更新微簇的概要信息；
9. ???ELSE
10.????IF (|C|≥n_micro)
11. ?????将最久未更新的微簇删除；
12. ?????对应X_i创建一个新微簇；
13. ???ELSE
14. ?????直接创建一个以X_i为中心的新微簇；
15. ????ENDIF
16. ??ENDIF
17. ?ENDIF
18. UNTIL stream end
算法2 ?基于期望距离的EDMicro算法
输入：微簇集合C及不确定流数据X_i
输出：距离X_i最近的微簇
1.初始化候选簇集合Q；
2. Q←C；
3.计算不确定流数据X_i的MBR的对角线一半值；
4. FOR k=1 to |Q|
5.计算该元组MBR的中心点和与C_k簇心c_k的距离；
6.计算X_i和C_k的期望距离ED的上界及下界；
7. IF (upper_ED < min_upper_ED)
8. ??min_upper_ED=upper_ED；
9. ENDIF
10. ENDFOR
11. FOR k=1 to |Q|
12. IF (lower_ED (X_i, C_k) > min_upper_ED)
13. ??将C_k从候选簇集合Q中删除；
14. ?ENDIF
15. ENDFOR
16. FOR k=1 to |Q|
17. ?计算X_i和候选集合Q中剩余微簇的期望距离；
18. ENDFOR
19. RETURN具有最小期望距离的微簇.
1.2 基于空间位置关系的不确定数据流聚类算法1.2.1 相关定义定义5 ?微簇的MBR.包含微簇内所有不确定元组期望值的最小边界矩形, 以两个d维向量分别表示MBR的下界和上界：
lower=(min (x_i⁽¹⁾), min (x_i⁽²⁾), …, min (x_i^(d))),
upper=(max (x_i⁽¹⁾), max (x_i⁽²⁾), …, max (x_i^(d))).
其中：min (x_i^(j))表示MBR在第j维上的最小值; max (x_i^(j))表示MBR在第j维上的最大值.
定义6 ?含MBR的微簇聚类特征结构.包含d维不确定元组的微簇可用(4×d+2)的元组(CF₁, CF₂, lower, upper, t, n)表示特征结构, 其中：CF₁表示各不确定元组期望值的线性和, 即每一维存储不确定元组对应维的期望值的和, 它是d维向量; CF₂也是d维向量, 表示各不确定元组期望值的平方和；lower是d维向量, 表示微簇的MBR的下界, 其第q项为min (x_i^(q))；upper是d维向量, 表示微簇的MBR的上界, 其第q项为max (x^(q))；t表示微簇最后更新的时间；n为微簇内不确定元组的个数.
引理2 ?当新的不确定元组加入微簇, 包含MBR信息的微簇聚类特征结构的各项均可增量更新.
1.2.2 MBR的空间位置关系以二维数据为例, 不确定元组X_i的MBR和微簇MBR的位置关系包括：
包含X_i的MBR和微簇的MBR, 其中一个落在另一个内部；
相交X_i的MBR和微簇的MBR的空间位置部分重合但无包含关系；
相离X_i的MBR和所有微簇的MBR都没有共同区域.意味着X_i距离所有微簇均较远, 需计算X_i和所有微簇的期望距离.
1.2.3 边界情况的优化通常与X_i相交或者包含X_i的微簇都是距离X_i较近的微簇, 与X_i相离的微簇都与之较远.但某些特殊情况下, 与X_i相离的微簇也可能距离X_i更近.本文给出一种启发式解决方法, 即对X_i的MBR放大以便能够与距其较近的微簇相交或者包含.可以看出, 放大后的MBR与其较近范围内微簇的MBR均有相交或包含的关系.参数τ控制X_i的MBR的放大倍数, 其合理取值本文将在实验部分给出.
1.2.4 算法描述聚类过程同样使用算法1的处理流程, SRMicro算法描述见算法3, 集合Q₁, Q₂, Q₃分别存放包含、相交、相离的微簇索引.
算法3 ?SRMicro算法
输入：微簇集合C, 不确定元组X_i
输出：距离X_i最近的微簇
1.创建3个候选簇集合Q₁, Q₂, Q₃；
2. Q₁←NULL, Q₂←NULL, Q₃←NULL；
3. FOR k=1 to |C|
4. ??判断微簇C_k的MBR和X_i的MBR之间的位置关系；
5. ??SWITCH
6. ??{CASE包含：C_k加入到候选集合Q₁中；BREAK；
7. ??CASE相交：C_k加入到候选集合Q₂中；BREAK；
8. ??CASE相离：C_k加入到候选集合Q₃中；BREAK；}
9. ENDFOR
10. IF (|Q₁|≥1)
11. ?FOR j=1 to |Q₁|
12. ???计算X_i和Q₁中所有微簇的期望距离ED (X_i, c_j)；
13. ?ENDFOR
14. ?Return argmin_CED (X_i, c_j)；
15. ELSE IF (|Q₂|≥1)
16. FOR j=1 to |Q₂|
17. ??计算X_i和Q₂中所有微簇的期望距离ED (X_i, c_j)；
18. ENDFOR
19. Return argmin_CED (X_i, c_j)；
20. ELSE
21. ??FOR j=1 to |Q₃|
22. ???计算X_i和Q₃中所有微簇的期望距离ED (X_i, c_j)；
23. ??ENDFOR
24. ?? argmin_CED (X_i, c_j)；
25. ENDIF
26. ENDIF
2 实验结果分析对本文提出的算法与LuMicro算法^[10]进行比较.实验所用计算机内存2 GB DDRII, CPU为Intel (R) Core (TM)2 Duo E8400 @3.00 GHz, 操作系统采用Microsoft Windows XP SP3, 开发环境为Microsoft Visual Studio 2010, 编程语言选择C++.
2.1 数据集及参数设置为评估算法性能, 采用两个真实数据集分别是KDD-CUP’99网络入侵检测数据集和美国联邦森林数据集(Forest CoverType), 合成数据集采用人工的方式生成.算法中使用的默认参数设置如表 1所示.
表 1(Table 1)

表 1 默认参数设置Table 1 Default parameter setting 参数 默认值 含义 N 500 000 数据流最大尺寸 d 0 元组维度 α 3 半径阈值 τ 1 MBR放大倍数 β 10 不确定元组内的最大实例数目 nmicro 500 微簇最大个数

表 1 默认参数设置 Table 1 Default parameter setting

2.2 算法性能分析2.2.1 效率和有效性图 1给出三种算法在不同数据集上的聚类时间, EDMicro算法运行时间要远低于LuMicro算法.图 2给出了三种算法以纯度表示的实验结果, 本文所提出算法的聚类纯度均高于LuMicro算法.
图 1(Fig. 1)

图 1 聚类时间Fig.1 Clustering time (a)-合成数据集；(b)-网络入侵数据集；(c)-森林数据集.

图 2(Fig. 2)

图 2 聚类纯度Fig.2 Purity of clustering

2.2.2 参数影响图 3给出了β分别取10, 20, 30, 40时, 本文所提出算法与LuMicro算法执行时间的对比.算法执行时间都随着β值的增长而增加, EDMicro算法时间增长要慢于LuMicro算法, SRMicro算法的执行时间缓慢增长, 这是因为比较的代价要远小于浮点运算的代价.
图 3(Fig. 3)

图 3 不同实例数量对执行时间的影响Fig.3 Influence on running time with different numbers of instances

图 4显示了参数τ对聚类结果的影响.本文通过放大不确定元组的MBR, 使其尽量与距离较近的微簇有交集, 以保证算法的准确度.参数α表示半径阈值, 图 5显示了α在不同值的情况下, 算法的聚类纯度与时间.
图 4(Fig. 4)

图 4 不同τ值对聚类结果的影响Fig.4 Influence on cluster purity with different τ

图 5(Fig. 5)

图 5 α的影响Fig.5 Influence of parameter α

2.2.3 可扩展性图 6显示了本文提出算法和SRMicro算法随维度变化时的聚类处理时间.可以看出维数增加, EDMicro算法的聚类时间随之线性增长, 并且EDMicro算法与SRMicro算法的差别随之增大.图 7显示出改变微簇数目时, EDMicro算法和SRMicro算法的聚类时间对比.
图 6(Fig. 6)

图 6 维度扩展Fig.6 Dimension expansion

图 7(Fig. 7)

图 7 不同微簇个数对执行时间的影响Fig.7 Influence on execution time with different numbers of micro-clusters

3 结论本文提出两种不确定数据流聚类的EDMicro算法和SRMicro算法.前一种算法中实例分布特征用不确定元组MBR表示, 不确定元组和簇心期望距离的取值范围通过计算期望距离进行推导, 过滤距离不确定元组较远的微簇从而减少计算代价.后者提出簇的MBR的概念, 从不确定元组MBR和簇的MBR的空间位置关系, 将距离待处理的不确定元组较远的簇过滤.大量实验验证了本文提出算法的有效性和高效性, 并具有良好的可扩展性.
参考文献

[1]	Liu L.From data privacy to location privacy:models and algorithms[C]//Proceeding of the 33rd International Conference on Very Large Data Bases.Vienna, 2007:1429-1430.
[2]	Deshpande A, Guestrin C, Madden S, et al.Model-driven data acquisition in sensor networks[C]// Proceeding of the 30th International Conference on Very Large Data Bases.Toronto, 2004:588-599.
[3]	Gu Y, Yu G, Zhang T C. RFID complex event processing techniques[J].Journal of Frontiers of Computer Science and Technology, 2007, 1(3) : 255–267.
[4]	Jeffery S R, Garofalakis M N, Franklin M J.Adaptive cleaning for RFID data streams[C]//Proceeding of the 32nd International Conference on Very Large Data Bases.Seoul, 2006:163-174.
[5]	周傲英, 金澈清, 王国仁, 等. 不确定性数据管理技术研究综述[J].计算机学报, 2009, 32(1) : 1–16. ( Zhou Ao-ying, Jin Che-qing, Wang Guo-ren, et al. Summary of research on uncertain data management technology[J].Chinese Journal of Computers, 2009, 32(1) : 1–16.DOI:10.3724/SP.J.1016.2009.00001)
[6]	Sarma A D, Benjelloun O, Halevy A Y, et al.Working models for uncertain data[C]//Proceeding of the 22nd International Conference on Data Engineering.Washington DC, 2006:145-157.
[7]	Aggarwal C C, Han J W, Wang J, et al. A framework for clustering evolving data streams[C]//Proceeding of the 29th International Conference on Very Large Data Bases.Berlin, 2003:81-92.
[8]	Aggarwal C C, Yu P S.A framework for clustering uncertain data streams[C]//Proceeding of the 24th International Conference on Data Engineering.Cancun, 2008:150-159.
[9]	Aggarwal C C.On high dimensional projected clustering of uncertain data streams[C]//Proceedings of the 25th International Conference on Data Engineering.Shanghai, 2009:1152-1154.
[10]	Zhang C, Gao M, Zhou A Y.Tracking high quality clusters over uncertain data streams[C] //Proceeding of the 25th International Conference on Data Engineering.Shanghai, 2009:1641-1648.
[11]	Huang G Y, Liang D P, Ren J D, et al.An algorithm for clustering uncertain data streams over sliding windows[C]// Proceeding of the 6th International Conference on Digital Content, Multimedia Technology and Its Applications.Seoul, 2009:173-177.
[12]	Cao K Y, Wang G R, Han D H, et al.A framework for high-quality clustering uncertain data stream over sliding windows[C]// Proceeding of the 13th International Conference on Web-Age Information Management.Harbin, 2012:308-313.
[13]	肖丹萍, 叶东毅. 基于免疫原理的不确定数据流聚类算法[J].模式识别与人工智能, 2012, 25(5) : 826–834. ( Xiao Dan-ping, Ye Dong-yi. An algorithm of uncertain data stream cluster based on immune principle[J].Pattern Recognition and Artificial Intelligence, 2012, 25(5) : 826–834.)
[14]	罗清华, 彭宇, 彭喜元. 一种多维不确定数据流聚类算法[J].仪器仪表学报, 2013, 34(6) : 1330–1337. ( Luo Qing-hua, Peng Yu, Peng Xi-yuan. Multi-dimensional uncertain data stream clustering algorithm[J].Chinese Journal of Scientific Instrument, 2013, 34(6) : 1330–1337.)
[15]	胡德敏, 余星. 一种不确定数据流子空间聚类算法[J].计算机应用研究, 2014, 31(9) : 2606–2608. ( Hu De-min, Yu Xing. Subspace clustering algorithm for uncertain data stream[J].Application Research of Computers, 2014, 31(9) : 2606–2608.)
[16]	Luo Q H, Yan X Z, Li J B, et al. A dynamic distance estimation using uncertain data stream clustering in mobile wireless sensor networks[J].Measurement, 2014, 55(9) : 423–433.