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]. 清华大学学报(自然科学版), 2018, 58(5): 469-476.
[2] 穆锡金, 李华安, 白宝明. 构造速率兼容多元LDPC码的扩展方法[J]. 清华大学学报(自然科学版), 2018, 58(3): 243-248.
[3] 陈晓方, 钱荧灿, 王雅琳, 阳春华. 基于主元导数特征聚类的加氢裂化动态调整区间识别[J]. 清华大学学报(自然科学版), 2018, 58(1): 81-86.
[4] 韩东红, 宋明, 张宏亮, 王佳茜, 王嘉兴, 王国仁. 基于密度的不确定数据流聚类算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 884-891.
[5] 肖熙, 周路. 基于k均值和基于归一化类内方差的语音识别自适应聚类特征提取算法[J]. 清华大学学报(自然科学版), 2017, 57(8): 857-861.
[6] 吕振华, 孙靖譞. 轴向变密度铝泡沫件的动态和静态压缩实验与有限元模拟分析[J]. 清华大学学报(自然科学版), 2017, 57(7): 753-762.
[7] 方勇, 刘道胜, 黄诚. 基于层次聚类的虚假用户检测[J]. 清华大学学报(自然科学版), 2017, 57(6): 620-624.
[8] 裴继升, 叶晓俊. 基于语法推导的溯源依赖关系路径模式挖掘算法[J]. 清华大学学报(自然科学版), 2017, 57(6): 561-568.
[9] 裴玉奎, 索婉萍. 卫星高速数传系统相位噪声迭代补偿算法[J]. 清华大学学报(自然科学版), 2017, 57(4): 388-392,398.
[10] 胡满江, 徐彪, 秦洪懋, 徐成, 丁可, 王建强. 基于MPC的多车纵向协同避撞算法[J]. 清华大学学报(自然科学版), 2017, 57(12): 1280-1286.
[11] 刘书明, 吴以朋, 王晓婷, 刘友飞, 李佳杰. 应用聚类算法识别供水管网爆管事故[J]. 清华大学学报(自然科学版), 2017, 57(10): 1096-1101.
[12] 李煦, 屠明, 吴超, 国雁萌, 纳跃跃, 付强, 颜永红. 基于NMF和FCRF的单通道语音分离[J]. 清华大学学报(自然科学版), 2017, 57(1): 84-88.
[13] 刘杰, 王生进. 融合聚类与排序的图像显著区域检测[J]. 清华大学学报(自然科学版), 2016, 56(9): 913-919.
[14] 葛广君, 殷柳国. 卫星高速数传系统多码率融合LDPC编码器设计[J]. 清华大学学报(自然科学版), 2016, 56(6): 656-660.
[15] 王志如, 苏国锋, 梁作论. 基于信息传递效率的地铁网络小世界特性评价[J]. 清华大学学报(自然科学版), 2016, 56(4): 411-416.
Viewed
Full text


Abstract

Cited

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