Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2017, Vol. 57 Issue (8): 884-891    DOI: 10.16511/j.cnki.qhdxxb.2017.22.055
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
基于密度的不确定数据流聚类算法
韩东红, 宋明, 张宏亮, 王佳茜, 王嘉兴, 王国仁
东北大学 计算机科学与工程学院, 沈阳 110819
Algorithm for clustering uncertain data streams based on density
HAN Donghong, SONG Ming, ZHANG Hongliang, WANG Jiaxi, WANG Jiaxing, WANG Guoren
School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
全文: PDF(1171 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 不确定性的出现使传统算法无法直接用于聚类不确定数据流。该文提出一种不确定数据流环境下基于密度的聚类算法,其中提出不确定度的概念以衡量不确定数据的分布信息,并在改进面向确定数据的聚类算法DENCLUE的基础上,提出一种可处理数据不确定度的UDENCLUE算法,以降低数据的不确定性对聚类结果产生的影响;提出滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE,通过聚类特征指数直方图技术实现快速剪枝,可以高效处理噪音数据、演化数据流并生成任意形状的簇;采用真实数据集及人工合成数据集对USDENCLUE与CluStream聚类算法进行比较,实验结果表明了所提出算法的高效性和有效性。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
韩东红
宋明
张宏亮
王佳茜
王嘉兴
王国仁
关键词 不确定数据流聚类密度滑动窗口    
Abstract:Uncertainties make it impossible to cluster uncertain data streams using traditional clustering algorithms. This paper presents a density-based clustering algorithms for uncertain data stream environments. An uncertainty metric is used to measure the distribution information in the uncertain data. The uncertain data streams DENCLUE algorithm (USDENCLUE) is then modified to deal with uncertainty data to minimize the impact of the data uncertainty on the clustering results. A density-based clustering algorithm is then given for uncertain data streams with a sliding window to rapidly prune the clusters using an exponential histogram of the cluster features. This algorithm can efficiently handle noisy data in evolving data streams to generate arbitrary clusters to improve the clustering quality. Comparisons of this algorithm with the CluStream clustering algorithm on real and synthetic data sets show the efficiency and effectiveness of this algorithm.
Key wordsuncertain data streams    clustering    density    sliding window
收稿日期: 2016-09-27      出版日期: 2017-08-15
ZTFLH:  TP301.6  
引用本文:   
韩东红, 宋明, 张宏亮, 王佳茜, 王嘉兴, 王国仁. 基于密度的不确定数据流聚类算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 884-891.
HAN Donghong, SONG Ming, ZHANG Hongliang, WANG Jiaxi, WANG Jiaxing, WANG Guoren. Algorithm for clustering uncertain data streams based on density. Journal of Tsinghua University(Science and Technology), 2017, 57(8): 884-891.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2017.22.055  或          http://jst.tsinghuajournals.com/CN/Y2017/V57/I8/884
  图1 不确定元组实例
  图2 获取不确定元组密度吸引点算法getDensityAttractor
  图3 基于密度的不确定数据聚类算法UDENCLUE
  图4 更新簇结构Update
  图5 滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE
  表1 相关实验参数设置
  图6 两种算法在真实网络数据集上的查准率和查全率
  图7 两种算法在人工合成数据集上的查准率和查全率
  图8 两种算法性能随元组不确定度的变化
  图9 两种算法处理噪音效果比较
  图10 两种算法处理演化数据流的查准率对比
[1] 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. New York, USA:ACM Press, 2004:588-599.
[2] GU Yu, YU Ge, ZHANG Tiancheng. RFID complex event processing techniques[J]. Journal of Frontiers of Computer Science and Technology, 2007, 1(3):255-267.
[3] Jeffery S R, Garofalakis M N, Frwanklin M J. Adaptive cleaning for RFID data streams[C]//Proceeding of the 32nd International Conference on Very Large Data Bases. New York, USA:ACM Press, 2006:163-174.
[4] ZHOU Aoying, JIN Cheqing, WANG Guoren, et al. A survey on the management of uncertain data[J]. Chinese Journal of Computers, 2009, 32(1):1-16.
[5] Aggarwal C C, Han J, Wang J, et al. A framework for clustering evolving data streams[C]//Proceeding of the 29th International Conference on Very Large Data Bases. New York, USA:ACM Press, 2003:81-92.
[6] Aggarwal C C, Yu P S. A framework for clustering uncertain data streams[C]//Proceeding of the 24th International Conference on Data Engineering. Cancún, México, 2008:150-159.
[7] Aggarwal C C. On high dimensional projected clustering of uncertain data streams[C]//Proceeding of the 25th International Conference on Data Engineering. Shanghai, 2009:1152-1154.
[8] 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, Korea, 2009:173-177.
[9] ZHANG Chen, JIN Cheqing, ZHOU Aoying. Clustering algorithm over uncertain data streams[J]. Journal of Software, 2010, 21(9):2173-2182.
[10] CAO Keyan, WANG Guoren, HAN Donghong, 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.
[11] YANG Yue, LIU Zhuo, ZHANG Jianpei, et al. Dynamic density-based clustering algorithm over uncertain data streams[C]//Proceeding of the 20129th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). Chongqing, 2012:2664-2670.
[12] JIN Cheqing, Yu J X, ZHOU Aoying, et al. Efficient clustering of uncertain data streams[J]. Knowledge and Information Systems, 2014, 40(3):509-539.
[13] Dallachiesa M, Jacques-Silva G, Gedik B, et al. Sliding windows over uncertain data streams[J]. Knowledge and Information Systems, 2015, 45(1):159-190.
[14] Hinneburg A, Keim D A. An efficient approach to clustering in large multimedia databases with noise[C]//Proceeding of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2010:58-65.
[1] 靳旭红, 黄飞, 程晓丽, 王强, 王兵. 超低地球轨道卫星大气阻力预测与影响因素分析[J]. 清华大学学报(自然科学版), 2020, 60(3): 219-226.
[2] 郭红仙, 李东润, 马瑞男, 程晓辉. MICP拌和固化钙质砂一维固结试验[J]. 清华大学学报(自然科学版), 2019, 59(8): 593-600.
[3] 肖熙, 徐晨. 基于声学状态似然值得分模型及监督状态模型的语音识别特征融合算法[J]. 清华大学学报(自然科学版), 2019, 59(6): 476-481.
[4] 张继文, 宋立滨, 许君杰, 石循磊, 刘莉. 仿人足球机器人的非预定义足球检测算法[J]. 清华大学学报(自然科学版), 2019, 59(4): 298-305.
[5] 骆歆远, 陈欣, 寿黎但, 陈珂, 吴妍静. 面向室内空间的语义轨迹提取框架[J]. 清华大学学报(自然科学版), 2019, 59(3): 186-193.
[6] 孙岚, 康健, 吴英杰, 张立群. 异方差加噪下差分隐私流数据发布一致性优化算法[J]. 清华大学学报(自然科学版), 2019, 59(3): 203-210.
[7] 李子浩, 田向亮, 黎忠文, 周炜, 周志杰, 钟茂华. 基于客流规律的地铁车站客流风险分析[J]. 清华大学学报(自然科学版), 2019, 59(10): 854-860.
[8] 马锐, 高浩然, 窦伯文, 王夏菁, 胡昌振. 基于改进GN算法的程序控制流图划分方法[J]. 清华大学学报(自然科学版), 2019, 59(1): 15-22.
[9] 索明亮, 周鼎, 安若铭, 李顺利. 邻域密度网格聚类算法及应用[J]. 清华大学学报(自然科学版), 2018, 58(8): 732-739.
[10] 吕江伟, 周凯. 高力密度直线开关磁阻电机的最佳极宽比[J]. 清华大学学报(自然科学版), 2018, 58(5): 469-476.
[11] 穆锡金, 李华安, 白宝明. 构造速率兼容多元LDPC码的扩展方法[J]. 清华大学学报(自然科学版), 2018, 58(3): 243-248.
[12] 陈晓方, 钱荧灿, 王雅琳, 阳春华. 基于主元导数特征聚类的加氢裂化动态调整区间识别[J]. 清华大学学报(自然科学版), 2018, 58(1): 81-86.
[13] 肖熙, 周路. 基于k均值和基于归一化类内方差的语音识别自适应聚类特征提取算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 857-861.
[14] 吕振华, 孙靖譞. 轴向变密度铝泡沫件的动态和静态压缩实验与有限元模拟分析[J]. 清华大学学报(自然科学版), 2017, 57(7): 753-762.
[15] 裴继升, 叶晓俊. 基于语法推导的溯源依赖关系路径模式挖掘算法[J]. 清华大学学报(自然科学版), 2017, 57(6): 561-568.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn