基于空间邻近的点目标聚类方法

doi:10.11772/j.issn.1001-9081.2016.05.1267

计算机应用 ›› 2016, Vol. 36 ›› Issue (5): 1267-1272.DOI: 10.11772/j.issn.1001-9081.2016.05.1267

基于空间邻近的点目标聚类方法

余莉, 甘淑, 袁希平, 李佳田

昆明理工大学国土资源工程学院, 昆明 650093

收稿日期:2015-09-09 修回日期:2015-12-29 出版日期:2016-05-10 发布日期:2016-05-09
通讯作者: 甘淑
作者简介:余莉(1987-),女,云南开远人,博士研究生,主要研究方向:数据挖掘、空间数据聚类;甘淑(1964-),女,云南腾冲人,教授,博士,主要研究方向:遥感、空间分析、数据建模;袁希平(1965-),男,湖北鄂城人,教授,博士,主要研究方向:摄影测量与遥感、土地资源管理;李佳田(1975-),男,黑龙江佳木斯人,副教授,博士,主要研究方向:动态空间关系计算。
基金资助:
国家自然科学基金资助项目(41561083,41261092,41561082);云南省自然科学基金资助项目(2015FA016)。

Clustering for point objects based on spatial proximity

YU Li, GAN Shu, YUAN Xiping, LI Jiatian

Faculty of Land and Resource Engineering, Kunming University of Science and Technology, Kunming Yunnan 650093, China

Received:2015-09-09 Revised:2015-12-29 Online:2016-05-10 Published:2016-05-09
Supported by:
This work is partially supported by the National Natural Science Foundation of China (41561083, 41261092,41561082), the Natural Science Foundation of Yunnan Province (2015FA016).

摘要/Abstract

摘要： 空间聚类是空间数据挖掘和知识发现领域的主要研究方向之一,但点目标空间分布密度的不均匀、分布形状的多样化,以及"多桥"链接问题的存在,使得基于距离和密度的聚类算法不能高效且有效地识别聚集性高的点目标。提出了基于空间邻近的点目标聚类方法,通过Voronoi建模识别点目标间的空间邻近关系,并以Voronoi势力范围来定义相似度准则,最终构建树结构以实现点目标的聚集模式识别。实验将所提算法与K-means、具有噪声的基于密度的聚类(DBSCAN)算法进行比较分析,结果表明算法能够发现密度不均且任意形状分布的点目标集群,同时准确划分"桥"链接的簇,适用于空间点目标异质分布下的聚集模式识别。

关键词: 空间聚类, Voronoi图, 空间邻近, 桥链接

Abstract: Spatial clustering is one of the vital research directions in spatial data mining and knowledge discovery. However, constrained by the complex distribution of uneven density, various shapes and multi-bridge connection of points, most clustering algorithms based on distance or density cannot identify high aggregative point sets efficiently and effectively. A point clustering method based on spatial proximity was proposed. According to the structure of point Voronoi diagram, adjacent relationships among points were recognized. The similarity criteria was defined by region of Voronoi, a tree structure was built to recognize point-target clusters. The comparison experiments were conducted on the proposed algorithm, K-means algorithm and Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm. Results show that the proposed algorithm is capable for identifying clusters in arbitrary shapes, with different densities and connected only at bridges or chains, meanwhile also suitable for aggregative pattern recognition in heterogeneous space.

Key words: spatial clustering, Voronoi diagram, spatial proximity, bridge connection

中图分类号:

TP181

余莉, 甘淑, 袁希平, 李佳田. 基于空间邻近的点目标聚类方法[J]. 计算机应用, 2016, 36(5): 1267-1272.

YU Li, GAN Shu, YUAN Xiping, LI Jiatian. Clustering for point objects based on spatial proximity[J]. Journal of Computer Applications, 2016, 36(5): 1267-1272.

参考文献

[1] ESTIVILL-CASTRO V, LEE I. Argument free clustering for large spatial point-data sets via boundary extraction from Delaunay diagram[J]. Computers, Environment and Urban Systems, 2002, 26(4):315-334.
[2] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Chicago:University of Chicago Press, 1967, 1:281-297.
[3] KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data:an Introduction to Cluster Analysis[M]. New York:John Wiley & Sons, 1990:38-42.
[4] RAYMOND T N, HAN J W. Efficient and effective clustering methods for spatial data mining[C]//Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann Publishers, 1994:144-155.
[5] ESTER M, KRIEGEL H P, XU X. Knowledge discovery in large spatial databases:Focusing techniques for efficient class identification[C]//Proceedings of the 4th International Symposium on Large Spatial Databases. Berlin:Springer-Verlag, 1995:67-82.
[6] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH:an efficient data clustering method for very large databases[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York:ACM, 1996:103-114.
[7] GUHA S, RASTOGI R, SHIM K. CURE:an efficient clustering algorithm for large databases[C]//Proceedings of the 1998 ACM-SIGMOD International Conference on Management of Data. New York:ACM, 1998:73-84.
[8] GUHA S, RASTOGI R, SHIM K. ROCK:A robust clustering algorithm for categorical attributes[C]//Proceedings of the 15th International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 1999:512-521.
[9] DASH M, LIU H, SCHEUERMANN P, et al. Fast hierarchical clustering and its validation[J]. Data & Knowledge Engineering, 2003, 44(1):109-138.
[10] HANDL J, KNOWLES J, DORIGO M. Ant-based clustering and topographic mapping[J]. Artificial Life, 2006, 12(1):35-61.
[11] LUMER E D, FAIETA B. Diversity and adaptation in populations of clustering ants[C]//Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior:from Animals to Animats 3. Cambridge:MIT Press, 1994, 1:501-508.
[12] MONMARCHÉ N, SLIMANE M, VENTURINI G. On improving Clustering in Numerical Databases with Artificial Ants[M]. Berlin:Springer, 1999:626-635.
[13] YANG Y, KAMEL M S. An aggregated clustering approach using multi-ant colonies algorithms[J]. Pattern Recognition, 2006, 39(7):1278-1289.
[14] TAN S C, TING K M, TENG S W. A general stochastic clustering method for automatic cluster discovery[J]. Pattern Recognition, 2011, 44(10):2786-2799.
[15] CARPENTER G A, and GROSSBERG S. ART2:self-organization of stable category recognition codes for analog input patterns[J]. Applied Optics, 1987, 26(23):4919-4930.
[16] KOHONEN T. Self-Organization and Associative Memory[M]. Berlin:Springer-Verlag, 1989:119-157.
[17] 余莉, 李佳田, 李佳, 等. 二维空间聚类的树ART2模型[J]. 计算机应用, 2011, 31(5):1328-1330. (YU L, LI J T, LI J, et al. Tree-ART2 model for clustering spatial data in two-dimensional space[J]. Journal of Computer Applications, 2011, 31(5):1328-1330.)
[18] HSU A L, HALGAMUGE S K. Enhancement of topology preservation and hierarchical dynamic self-organising maps for data visualization[J]. International Journal of Approximate Reasoning, 2003, 32(2/3):259-279.
[19] 王莉, 王正欧. TGSOM:一种用于数据聚类的动态自组织映射神经网络[J]. 电子与信息学报, 2003, 25(3):313-319. (WANG L, WANG Z O. TGSOM:a new dynamic self-organizing maps for data clustering[J]. Journal of Electronics and Information Technology, 2003, 25(3):313-319.)
[20] HINNEBURG A, KEIM D A. An efficient approach to clustering in large multimedia databases with noise[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining. Berlin:Springer-Verlag, 1998, 98:58-65.
[21] 淦文燕, 李德毅, 王建民. 一种基于数据场的层次聚类方法[J]. 电子学报, 2006, 34(2):258-262. (GAN W Y, LI D Y, WANG J M. A hierarchical clustering method based on data fields[J]. Acta Electronica Sinica, 2006, 34(2):258-262.)
[22] NOSOVSKIY G V, LIU D, SOURINA O. Automatic clustering and boundary detection algorithm based on adaptive influence function[J]. Pattern Recognition, 2008, 41(9):2757-2776.
[23] 邓敏, 彭东亮, 刘启亮, 等. 一种基于场论的层次空间聚类算法[J]. 武汉大学学报(信息科学版), 2011, 36(7):847-852. (DENG M, PENG D L, LIU Q L, et al. A hierarchical spatial clustering algorithm based on field theory[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7):847-852.)
[24] ESTIVILL-CASTRO V, LEE I. AMOEBA:hierarchical clustering based on spatial proximity using Delaunay diagram[C]//Proceedings of the 9th International Symposium on Spatial Data Handling. Berlin:Springer-Verlag, 2000, 26-41.
[25] ESTIVILL-CASTRO V, LEE I. Multilevel clustering and its visualization for exploratory data analysis[J]. GeoInformatica, 2002, 6(2):123-152.
[26] LIU D, NOSOVSKIY G V, SOURINA O. Effective clustering and boundary detection algorithm based on Delaunay triangulation[J]. Pattern Recognition Letters, 2008, 29(9):1261-1273.
[27] ESTER M, KRIEGEL H P, SANDER J, et al. 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. Menlo Park, California:AAAI Press, 1996:226-231.
[28] PARKER J K, DOWNS J A. Footprint generation using fuzzy-neighborhood clustering[J]. GeoInformatica, 2013, 17(2):285-299.
[29] 武佳薇, 李雄飞, 孙涛, 等. 邻域平衡密度聚类算法[J]. 计算机研究与发展, 2010, 47(6):1044-1052. (WU J W, LI X F, SUN T, et al. A density-based clustering algorithm concerning neighborhood balance[J]. Journal of Computer Research and Development, 2010, 47(6):1044-1052.)
[30] WANG W, YANG J, MUNTZ R. STING:a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Databases. San Francisco, CA:Morgan Kaufmann Publishers Inc, 1997:186-195.
[31] AGRAWAL R, GEHRKE J, GUNOPULOS D, et al. Automatic subspace clustering of high dimensional data[J]. Data Mining and Knowledge Discovery, 2005, 11(1):5-33.
[32] GOLD C M. Problems with handling spatial data-the Voronoi approach[J]. CISM Journal, 1991, 45(1):65-80.
[33] 陈军, 赵仁亮. Voronoi动态空间数据模型[M]. 北京:测绘出版社, 2002:24-47. (CHEN J, ZHAO R L. Voronoi Dynamic Spatial Data Model[M]. Beijing:Surveying and Mapping Press, 2002:24-47.)

基于空间邻近的点目标聚类方法

Clustering for point objects based on spatial proximity

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	朱玉娜, 张玉涛, 闫少阁, 范钰丹, 陈韩托. 基于半监督子空间聚类的协议识别方法[J]. 计算机应用, 2021, 41(10): 2900-2904.
[2]	王丽娟, 陈少敏, 尹明, 许跃颖, 郝志峰, 蔡瑞初, 温雯. 基于近邻图改进的块对角子空间聚类算法[J]. 计算机应用, 2021, 41(1): 36-42.
[3]	史佳琦, 谭励, 唐小江, 连晓峰, 王浩宇. 基于小结构体的无线传感器网络部署算法[J]. 计算机应用, 2020, 40(7): 2033-2037.
[4]	曾梦, 宁彬, 蔡之华, 谷琼. 使用深度对抗子空间聚类实现高光谱波段选择[J]. 计算机应用, 2020, 40(2): 381-385.
[5]	黄东晋, 段思文, 雷雪, 梁景坤. 基于Voronoi图的群体队形控制方法[J]. 计算机应用, 2019, 39(6): 1799-1803.
[6]	赵星宇, 赵志宏, 王业沛, 陈松宇. 基于聚类分析的微博广告发布者识别[J]. 计算机应用, 2018, 38(5): 1267-1271.
[7]	党小超, 黑毅力, 郝占军, 李芬芳. 基于动态近邻反馈修正的室内定位算法[J]. 计算机应用, 2018, 38(2): 516-521.
[8]	张海涛, 周欢, 张国楠. 基于空间邻近搜索的移动轨迹相对时间模式挖掘方法[J]. 计算机应用, 2018, 38(11): 3326-3331.
[9]	车迪, 牛强. 面向非完全序列的水下三维传感网定位算法[J]. 计算机应用, 2018, 38(1): 31-37.
[10]	王保全, 蒋同海, 周喜, 马博, 赵凡. 类自动车牌识别轨迹数据的伴随车辆组挖掘[J]. 计算机应用, 2017, 37(11): 3064-3068.
[11]	程铃钫, 杨天鹏, 陈黎飞. 不平衡数据的软子空间聚类算法[J]. 计算机应用, 2017, 37(10): 2952-2957.
[12]	吴杰祺, 李晓宇, 袁晓彤, 刘青山. 利用坐标下降实现并行稀疏子空间聚类[J]. 计算机应用, 2016, 36(2): 372-376.
[13]	王磊, 王鹏飞, 赵学胜, 卢立托. 基于图形处理器的球面Voronoi图生成算法优化[J]. 计算机应用, 2015, 35(6): 1564-1566.
[14]	戴国勇, 陈麓屹, 周斌彬, 徐萍. 基于Voronoi图的无线传感器网络覆盖空洞检测算法[J]. 计算机应用, 2015, 35(3): 620-623.
[15]	支晓斌, 许朝晖. 鲁棒的特征权重自调节软子空间聚类算法[J]. 计算机应用, 2015, 35(3): 770-774.