克服双重约束的面目标位置聚类方法

doi:10.11947/j.AGCS.2016.20150491

测绘学报 ›› 2016, Vol. 45 ›› Issue (10): 1250-1259.doi: 10.11947/j.AGCS.2016.20150491

克服双重约束的面目标位置聚类方法

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

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

收稿日期:2015-09-23 修回日期:2016-07-08 出版日期:2016-10-20 发布日期:2016-11-08
通讯作者: 甘淑 E-mail:n1480@qq.com
作者简介:余莉(1987-),女,博士生,主要研究方向为空间数据挖掘、建模与分析。E-mail:woshiyuli@126.com
基金资助:
国家自然科学基金（41561083；41261092；41561082）；云南省自然科学基金（2015FA016）

Position Clustering for Polygon Object under Dual-constrains

YU Li, GAN Shu, YUAN Xiping, LI Jiatian

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

Received:2015-09-23 Revised:2016-07-08 Online:2016-10-20 Published:2016-11-08
Supported by:
The National Natural Science Foundation of China(Nos.41561083;41261092;41561082);The Natural Science Foundation of Yunnan Province(No.2015FA016)

摘要/Abstract

摘要：

面目标的聚集模式识别是空间聚类研究的重要方向之一，但因多边形几何信息和空间障碍阻隔的双重约束，目标的位置相似性难以快速而准确地计算。扩展点目标多尺度聚类方法，通过构建面目标的强度函数计算目标与邻近目标的位置聚集程度，提出了有效作用于双重约束下的面目标位置聚类法，并以判断相邻尺度下同一面目标类的强度函数阈值相等作为算法的收敛条件。经试验分析与比较发现，算法无须自定义参数，能够识别密度不均、任意形状分布，以及“桥”链接的面目标集群，同时能够准确判断障碍约束对面目标簇的阻隔和划分。

关键词: 面目标, 位置聚类, Voronoi图, 空间障碍, 评价指数

Abstract:

It is a vital research direction for spatial clustering to recognize polygon cluster, but due to the dual-constrains by geometric information of polygons and obstacles, the position similarity of polygon is difficult to calculate accurately and quickly.A polygon clustering algorithm under dual-constrains is proposed by extending the algorithm of multi-scale spatial clustering, and constructing an intensity function to express position aggregation between object and its adjacent object. For further discuss, it takes the same thresholds of intensity function in adjacent scales as convergence condition. Simulated polygons and real data are chosen to perform clustering in experiments to verify the validity of our algorithm. Results show that without predefined parameters, this algorithm can identify variety polygon clusters with different densities, arbitrary shape, bridge and obstacle.

Key words: polygon, position clustering, Voronoi diagram, spatial obstacle, assessment index

中图分类号:

P208

余莉, 甘淑, 袁希平, 李佳田. 克服双重约束的面目标位置聚类方法[J]. 测绘学报, 2016, 45(10): 1250-1259.

YU Li, GAN Shu, YUAN Xiping, LI Jiatian. Position Clustering for Polygon Object under Dual-constrains[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(10): 1250-1259.

参考文献

[1] 辜寄蓉, 陈先伟, 杨海龙. 城市功能区划分空间聚类算法研究[J]. 测绘科学, 2011, 36(5):65-67. GU Jirong, CHEN Xianwei, YANG Hailong. Spatial Clustering Algorithm on Urban Function Oriented Zone[J]. Science of Surveying and Mapping, 2011, 36(5):65-67.
[2] CAO Zechun, WANG Sujing, FORESTIER G, et al. Analyzing the Composition of Cities Using Spatial Clustering[C]//Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing. New York:ACM, 2013:14.
[3] STEINHAUER J H, WIESE T, FREKSA C, et al. Recognition of Abstract Regions in Cartographic Maps[M]//MONTELLO D R. Spatial Information Theory. Berlin Heidelberg:Springer, 2001:306-321.
[4] YAN Haowen, WEIBEL R, YANG Bisheng. A Multi-Parameter Approach to Automated Building Grouping and Generalization[J]. Geoinformatica, 2008, 12(1):73-89.
[5] 邓敏, 孙前虎, 文小岳, 等. 建筑物层次空间聚类方法研究[J]. 计算机工程与应用, 2011, 47(28):120-123. DENG Min, SUN Qianhu, WEN Xiaoyue, et al. Hierarchical Spatial Clustering of Buildings[J]. Computer Engineering and Applications, 2011, 47(28):120-123.
[6] 马利邦, 郭晓东, 张启媛. 甘谷县乡村聚落时空布局特征及格局优化[J]. 农业工程学报, 2012, 28(13):217-225. MA Libang, GUO Xiaodong, ZHANG Qiyuan. Spatio-Temporal Distribution and Optimization of Rural Settlements in Gangu County of Loess Hilly Area[J]. Transactions of the Chinese Society of Agricultural Engineering, 2012, 28(13):217-225.
[7] 艾廷华, 郭仁忠. 基于格式塔识别原则挖掘空间分布模式[J]. 测绘学报, 2007, 36(3):302-308. DOI:10.3321/j.issn:1001-1595.2007.03.011. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):302-308. DOI:10.3321/j.issn:1001-1595.2007.03.011.
[8] 闫浩文, 应申, 李霖. 多因子影响的地图居民地自动聚群与综合研究[J]. 武汉大学学报(信息科学版), 2008, 33(1):51-54. YAN Haowen, YING Shen, LI Lin. An Approach for Automated Building Grouping and Generalization Considering Multiple Parameters[J]. Geomatics and Information Science of Wuhan University, 2008, 33(1):51-54.
[9] 邓敏, 刘启亮, 李光强, 等. 空间聚类分析及应用[M]. 北京:科学出版社, 2011. DENG Min, LIU Qiliang, LI Guangqiang, et al. Analysis and Application of Spatial Clustering[M]. Beijing:Science Press, 2011.
[10] BARRAULT M, REGNAULD N, DUCHENE C, et al. Integrating Multi-agent, Object-oriented, and Algorithmic Techniques for Improved Automated Map Generalization[C]//Proceedings of 20th International Cartographic Conference. Beijing:Publishing House of Surveying and Mapping, 2001:2110-2116.
[11] 杨春成, 何列松, 谢鹏, 等. 顾及距离与形状相似性的面状地理实体聚类[J]. 武汉大学学报(信息科学版), 2009, 34(3):335-338. YANG Chuncheng, HE Liesong, XIE Peng, et al. Clustering Analysis of Geographical Area Entities Considering Distance and Shape Similarity[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3):335-338.
[12] ZHANG Xiang, AI Tinghua, STOTER J S, et al. Building Pattern Recognition in Topographic Data:Examples on Collinear and Curvilinear Alignments[J]. Geoinformatica, 2013, 17(1):1-33.
[13] ALT H, BEHRENDS B, BLÖMER J. Approximate Matching of Polygonal Shapes[J]. Annals of Mathematics and Artificial Intelligence, 1995, 13(3-4):251-265.
[14] WANG Sujing, CHEN Chunsheng, RINSURONGKAWONG V, et al. A Polygon-based Methodology for Mining Related Spatial Datasets[C]//Proceedings of the 1st ACM SIGSPATIAL International Workshop on Data Mining for Geoinformatics. New York:ACM, 2010:1-8.
[15] DAVIS E. Representations of Commonsense Knowledge[M]. San Mateo:Morgan Kaufmann, 1990.
[16] DENG Min, LI Zhilin, CHEN Xiaoyong. Extended Hausdorff Distance for Spatial Objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4):459-475.
[17] JOSHI D, SAMAL A K, SOH L K. Density-based Clustering of Polygons[C]//Proceedings of the CIDM'09 IEEE Symposium on Computational Intelligence and Data Mining. Nashville, TN:IEEE, 2009:171-178.
[18] HUH Y, KIM J, LEE J, et al. Identification of Multi-Scale Corresponding Object-Set Pairs between Two Polygon Datasets with Hierarchical Co-Clustering[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 88:60-68.
[19] 耿协鹏, 杜晓初, 胡鹏. 基于栅格距离变换的扩展对象空间聚类方法[J]. 测绘学报, 2009, 38(2):162-167, 174. DOI:10.3321/j.issn:1001-1595.2009.02.012. GENG Xiepeng, DU Xiaochu, HU Peng. Spatial Clustering Method Based on Raster Distance Transform for Extended Objects[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2):162-167, 174. DOI:10.3321/j.issn:1001-1595.2009.02.012.
[20] HALKIDI M, VAZIRGIANNIS M. NPClu:An Approach for Clustering Spatially Extended Objects[J]. Intelligent Data Analysis, 2008, 12(6):587-606.
[21] SANDER J, ESTER M, KRIRGEL H P, et al. Density-based Clustering in Spatial Databases:The Algorithm GDBSCAN and Its Applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2):169-194.
[22] 黎韶光, 周巨锁, 谢玉波, 等. 一种面向扩展空间对象的密度聚类算法[J]. 计算机工程与应用, 2011, 47(13):166-168. LI Shaoguang, ZHOU Jusuo, XIE Yubo, et al. Density-based Clustering Algorithm for Extended Spatial Objects[J]. Computer Engineering and Applications, 2011, 47(13):166-168.
[23] 张丽, 吉根林. 基于点面包含关系的GML空间聚类算法[J]. 小型微型计算机系统, 2010, 31(4):702-705. ZHANG Li, JI Genlin. Algorithm for Spatial Clustering in GML Data Based on Point-Region Spatial Inclusion Relation[J]. Journal of Chinese Computer Systems, 2010, 31(4):702-705.
[24] 余莉, 甘淑, 袁希平, 等. 综合线面特征分布的点目标多尺度聚类方法[J]. 测绘学报, 2015, 44(10):1152-1159. DOI:10.11947/j.AGCS.2015.20150136. YU Li, GAN Shu, YUAN Xiping, et al. Multi-Scale Clustering of Points Synthetically Considering Lines and Polygons Distribution[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10):1152-1159. DOI:10.11947/j.AGCS.2015.20150136.
[25] 王中辉, 闫浩文. 基于方向Voronoi图模型的群组目标空间方向关系计算[J]. 小型微型计算机系统, 2013, 38(5):584-588. WANG Zhonghui, YAN Haowen. Computation of Direction Relations between Object Groups Based on Direction Voronoi Diagram Model[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5):584-588.
[26] TOBLER W R. A Computer Movie Simulating Urban Growth in the Detroit Region[J]. Economic Geography, 1970, 46(S1):234-240.
[27] 王新生, 刘纪远, 庄大方, 等. 基于GIS的任意发生元Voronoi图逼近方法[J]. 地理科学进展, 2004, 23(4):97-102. WANG Xinsheng, LIU Jiyuan, ZHUANG Dafang, et al. GIS-based Approximation Algorithm for Constructing Voronoi Diagrams with General Generators[J]. Progress in Geography, 2004, 23(4):97-102.
[28] 李佳田, 杨琪莉, 罗富丽, 等. 线/面Voronoi图的分解合并生成算法[J]. 武汉大学学报(信息科学版), 2015, 40(11):1545-1550. LI Jiatian, YANG Qili, LUO Fuli, et al. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11):1545-1550.
[29] BERRY M J A, LINOFF G S. Data Mining Techniques:For Marketing, Sales, and Customer Support[M]. New York:John Wiley &Sons, 1997.
[30] 刘启亮, 邓敏, 石岩, 等. 一种基于多约束的空间聚类方法[J]. 测绘学报, 2011, 40(4):509-516. LIU Qiliang, DENG Min, SHI Yan, et al. A Novel Spatial Clustering Method Based on Multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4):509-516.

克服双重约束的面目标位置聚类方法

Position Clustering for Polygon Object under Dual-constrains

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价

[1]	刘青平, 赵学胜, 王磊, 孙文彬. 横-纵扫描的Voronoi图栅格生成算法[J]. 测绘学报, 2019, 48(3): 393-399.
[2]	余莉, 甘淑, 袁希平, 杨明龙. 综合线面特征分布的点目标多尺度聚类方法[J]. 测绘学报, 2015, 44(10): 1152-1159.
[3]	李佳田, 康顺, 罗富丽. 利用层次Voronoi图进行点群综合[J]. 测绘学报, 2014, 43(12): 1300-1306.
[4]	涂伟李清泉方志祥. 基于网络Voronoi图的大规模多仓库物流配送路径优化[J]. 测绘学报, 2014, 43(10): 1075-1082.
[5]	李霖毛凯谭永滨. 基于分层地标的多粒度路径导引描述方法[J]. 测绘学报, 2014, 43(1): 105-112.
[6]	艾廷华禹文豪. 基于水流扩展思想的网络空间Voronoi图生成[J]. , 2013, 42(5): 760-766.
[7]	刘小凤吴艳兰胡海. 面状要素的多层次骨架线提取[J]. , 2013, 42(4): 0-0.
[8]	周启艾廷华张翔. 面向多重空间冲突解决的移位场模型[J]. , 2013, 42(4): 0-0.
[9]	刘万增,陈军,闫超德,赵仁亮,赵勇,孙文彬. 平面离散点集拓扑邻近稳定区域计算模型[J]. 测绘学报, 2012, 41(1): 127-0.
[10]	谢顺平,冯学智,鲁伟. 基于道路网络分析的Voronoi面域图构建算法[J]. 测绘学报, 2010, 39(1): 0-82.