Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2018, Vol. 58 Issue (8): 732-739    DOI: 10.16511/j.cnki.qhdxxb.2018.22.025
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
邻域密度网格聚类算法及应用
索明亮, 周鼎, 安若铭, 李顺利
哈尔滨工业大学 航天学院, 哈尔滨 150001
Neighborhood density grid clustering and its applications
SUO Mingliang, ZHOU Ding, AN Ruoming, LI Shunli
School of Astronautics, Harbin Institute of Technology, Harbin 150001, China
全文: PDF(4356 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 聚类作为数据分析的工具之一,已在模式识别、文献计量及故障诊断等领域中发挥了重要作用。该文基于邻域关系、局部密度和空间网格划分提出了一种聚类方法。该方法主要利用空间网格降低计算复杂度,利用邻域关系在网格空间中以密度为依据搜索聚类元素,并根据最大相对距离和最大相对密度原则自动寻找聚类中心。基于人工数据的实验结果表明,所提邻域密度网格聚类方法可有效处理任意形状数据并自主完成聚类。基于区域识别的对比实验表明,所提方法更适用于处理奇异形状且分布复杂的数据。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
索明亮
周鼎
安若铭
李顺利
关键词 聚类网格划分邻域密度任意形状区域识别    
Abstract:The clustering data analysis tool plays a significant role in various fields such as pattern recognition, bibliometrics and fault diagnosis. This paper describes a clustering approach based on neighborhood relationships, local densities and spatial grid partitions. The time complexity of this algorithm is reduced using a spatial grid with the clustering elements searched using neighborhood density relationships in the grid space. Cluster centers are then selected automatically using the maximum relative distance and the maximum relative local density. Tests on artificial data indicate that neighborhood density grid clustering can automatically cluster data and effectively process data with arbitrary shapes. Comparisons using regional recognition datasets demonstrate that this method is more suitable for clustering complex data with unusual shapes.
Key wordsclustering    grid partition    neighborhood    density    arbitrary shape    region recognition
收稿日期: 2017-12-26      出版日期: 2018-08-15
基金资助:哈尔滨工业大学科研创新基金(HIT.NSRIF.2014033)
通讯作者: 李顺利,教授,E-mail:lishunli@hit.edu.cn     E-mail: lishunli@hit.edu.cn
引用本文:   
索明亮, 周鼎, 安若铭, 李顺利. 邻域密度网格聚类算法及应用[J]. 清华大学学报(自然科学版), 2018, 58(8): 732-739.
SUO Mingliang, ZHOU Ding, AN Ruoming, LI Shunli. Neighborhood density grid clustering and its applications. Journal of Tsinghua University(Science and Technology), 2018, 58(8): 732-739.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2018.22.025  或          http://jst.tsinghuajournals.com/CN/Y2018/V58/I8/732
  图1 二维空间正态分布数据
  图2 (网络版彩图)局部密度分布图
  图3 (网络版彩图)聚类步骤示意
  图4 NDGC聚类算法
  图5 (网络版彩图)Normal数据聚类结果
  图6 (网络版彩图)K4Far2数据聚类结果
  图7 (网络版彩图)Eyes数据聚类结果
  图8 (网络版彩图)Clouds数据聚类结果
  图9 (网络版彩图)Aggregation数据聚类结果
  图10 (网络版彩图)Flame数据聚类结果
  图11 (网络版彩图)Finland地图上的用户定位数据
  图12 (网络版彩图)Finland数据KGmeans聚类结果
  图13 (网络版彩图)Finland数据 DBSCAN 聚类结果
  图14 (网络版彩图)Finland数据 FCM 聚类结果
  图15 (网络版彩图)Finland数据 WC聚类结果
  图16 (网络版彩图)Finland数据 NDGC聚类结果
  图17 (网络版彩图)Joensuu地图上的用户定位数据
  图18 (网络版彩图)Joensuu数据KGmeans聚类结果
  图19 (网络版彩图)Joensuu数据 DBSCAN 聚类结果
  图20 (网络版彩图)Joensuu数据 FCM 聚类结果
  图21 (网络版彩图)Joensuu数据 WC聚类结果
  图22 (网络版彩图)Joensuu数据 NDGC聚类结果
[1] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.
[2] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, USA:University of California Press, 1967:281-297.
[3] PARK H S, JUN C H. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2):3336-3341.
[4] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH:An efficient data clustering method for very large databases[J]. ACM SIGMOD Record, 1996, 25(2):103-114.
[5] BEZDEK J C, EHRLICH R, FULL W. FCM:The fuzzy c-means clustering algorithm[J]. Computers & Geosciences, 1984, 10(2-3):191-203.
[6] BABUKA R, VAN DER VEEN P J, KAYMAK U. Improved covariance estimation for Gustafson-Kessel clustering[C]//Proceedings of the 2002 IEEE International Conference on Fuzzy Systems. Honolulu, USA, 2002:1081-1085.
[7] BERCHTOLD M, RIEDEL T, DECKER C, et al. Gath-Geva specification and genetic generalization of Takagi-Sugeno-Kang fuzzy models[C]//Proceedings of the 2008 IEEE International Conference on Systems, Man and Cybernetics. Singapore, 2008:595-600.
[8] JIANG B, PEI J, TAO Y F, et al. Clustering uncertain data based on probability distribution similarity[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4):751-763.
[9] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland, USA, 1996:226-231.
[10] ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS:Ordering points to identify the clustering structure[J]. ACM SIGMOD Record, 1999, 28(2):49-60.
[11] WANG W, YANG J, MUNTZ R R. STING:A statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Data Bases. Athens, Greece:Morgan Kaufmann Publishers, 1997:186-195.
[12] SHEIKHOLESLAMI G, CHATTERJEE S, ZHANG A D. WaveCluster:A multi-resolution clustering approach for very large spatial databases[C]//Proceedings of the 24th International Conference on Very Large Data Bases. New York, USA:Morgan Kaufmann Publishers, 1998:428-439.
[13] LIU H P, SUN J, WU H, et al. High resolution sonar image segmentation by PSO based fuzzy cluster method[C]//Proceedings of the 4th International Conference on Genetic and Evolutionary Computing. Shenzhen, China, 2010:18-21.
[14] XU D K, TIAN Y J. A comprehensive survey of clustering algorithms[J]. Annals of Data Science, 2015, 2(2):165-193.
[15] MOPSI. Mopsi data:Locations[DB/OL]. (2012-03-07)[2017-12-25]. http://cs.uef.fi/mopsi/data/.
[16] SUO M L, ZHU B L, ZHOU D, et al. Neighborhood grid clustering and its application in fault diagnosis of satellite power system[J]. Proceedings of the Institution of Mechanical Engineers, Part G:Journal of Aerospace Engineering, 2018. DOI:10.1177/0954410017751991.
[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(10): 854-860.
[7] 何良, 李华, 赵原, 刘立业, 曹勤剑, 李君利. 基于辐射场梯度变化的变权重网格划分方法[J]. 清华大学学报(自然科学版), 2019, 59(10): 861-865.
[8] 马锐, 高浩然, 窦伯文, 王夏菁, 胡昌振. 基于改进GN算法的程序控制流图划分方法[J]. 清华大学学报(自然科学版), 2019, 59(1): 15-22.
[9] 吕江伟, 周凯. 高力密度直线开关磁阻电机的最佳极宽比[J]. 清华大学学报(自然科学版), 2018, 58(5): 469-476.
[10] 穆锡金, 李华安, 白宝明. 构造速率兼容多元LDPC码的扩展方法[J]. 清华大学学报(自然科学版), 2018, 58(3): 243-248.
[11] 陈晓方, 钱荧灿, 王雅琳, 阳春华. 基于主元导数特征聚类的加氢裂化动态调整区间识别[J]. 清华大学学报(自然科学版), 2018, 58(1): 81-86.
[12] 肖熙, 周路. 基于k均值和基于归一化类内方差的语音识别自适应聚类特征提取算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 857-861.
[13] 韩东红, 宋明, 张宏亮, 王佳茜, 王嘉兴, 王国仁. 基于密度的不确定数据流聚类算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 884-891.
[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