An aggregation index clustering method of natural polygon features for spatial knowledge mining

doi:10.11947/j.AGCS.2021.20200297

Abstract

Abstract: Spatial clustering is one of the important methods to mining spatial knowledge. Existing methods fail to cluster natural polygon features with great differences in geometry and distribution. Hence an aggregation index is proposed to measure distribution density, and a new natural polygon feature clustering method is designed. First, the formula of aggregation index is designed and its effectiveness is verified. Then, on basis of aggregation index and the shortest distance, the affiliation relationship of adjacent polygon features is established to identify the clustering center. Thus, initial clustering group is constructed. Finally, border feature detection principle and adjacent group merging model are provided to obtain better clustering results. Experiments show that compared with MST and MSSCP, the method proposed can take the complexity of geometric and distribution characteristics into account and effectively improve the clustering results of natural polygon features.

Key words: cartographic generalization, natural polygon features, spatial clustering, distribution density, aggregation index

CLC Number:

P208

LIU Chengyi, WU Fang, GONG Xianyong, XING Ruixing, DU Jiawei. An aggregation index clustering method of natural polygon features for spatial knowledge mining[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(4): 544-555.

References

[1] 国家测绘局. GB 12343-901:25 000、1:50 000地形图编绘规范[S]. 北京:中国标准出版社, 1990. State Bureau of Surveying and Mapping. Compilation specifications for 1:25 000, 1:50 000 topographic maps[S]. Beijing:China Standard Press, 1990.
[2] 王家耀, 张天时. 制图综合[M]. 北京:星球地图出版社, 2016. WANG Jiayao, ZHANG Tianshi. Cartographic generalization[M]. Beijing:Star Map Press, 2016.
[3] 郭庆胜. 空间推理与渐进式地图综合[M]. 武汉:武汉大学出版社, 2007. GUO Qingsheng. Spatial reasoning and progressive map synthesis[M]. Wuhan:Wuhan University Press, 2007.
[4] 李志林, 刘启亮, 唐建波. 尺度驱动的空间聚类理论[J]. 测绘学报, 2017, 46(10):1534-1548. DOI:10.11947/j.AGCS.2017.20170275. LI Zhilin, LIU Qiliang, TANG Jianbo. Towards a scale-driven theory for spatial clustering[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1534-1548. DOI:10.11947/j.AGCS.2017.20170275.
[5] JAIN A K. Data clustering:50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8):651-666. DOI:10.1016/j.patrec.2009.09.011.
[6] 程博艳, 刘强, 李小文. 一种建筑物群智能聚类法[J]. 测绘学报, 2013, 42(2):290-294, 303. CHENG Boyan, LIU Qiang, LI Xiaowen. Intelligent building grouping using a self-organizing map[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2):290-294, 303.
[7] REGNAULD N. Contextual building typification in automated map generalization[J]. Algorithmica, 2001, 30(2):312-333. DOI:10.1007/s00453-001-0008-8.
[8] DENG Min, LIU Qiliang, CHENG Tao, et al. An adaptive spatial clustering algorithm based on delaunay triangulation[J]. Computers, Environment and Urban Systems, 2011, 35(4):320-332. DOI:10.1016/j.compenvurbsys.2011.02.003.
[9] VÍDISSON B. Automated detection and explicit modelling of structural relations for the generalisation of island groups[D]. Dresden:Technische University Dresden, 2015.
[10] STEINIGER S, WEIBEL R, BURGHARDT D. Recognition of large island structures for map generalization[C]//Proceedings of 2006 ACM-GIS'06. Arlington, Virginia:ACM, 2006.
[11] 孙前虎. 基于多约束的建筑群聚类方法研究[D]. 长沙:中南大学, 2011. SUN Qianhu. Research on buildings clustering methods based on multi-constraints[D]. Changsha:Central South University, 2011.
[12] ZHANG Xiang, AI Tinghua, STOTER J, et al. Building pattern recognition in topographic data:examples on collinear and curvilinear alignments[J]. GeoInformatica, 2013, 17(1):1-33. DOI:10.1007/s10707-011-0146-3.
[13] 晏雄锋. 深度卷积学习支持下的建筑物模式分析[D]. 武汉:武汉大学, 2019. YAN Xiongfeng. Building pattern analysis supported by deep convolutional learning[D]. Wuhan:Wuhan University, 2019.
[14] 余莉, 甘淑, 袁希平, 等. 克服双重约束的面目标位置聚类方法[J]. 测绘学报, 2016, 45(10):1250-1259. DOI:10.11947/j.AGCS.2016.20150491. YU Li, GAN Shu, YUAN Xiping, et al. Position clustering for polygon object under dual-constrains[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(10):1250-1259. DOI:10.11947/j.AGCS.2016.20150491.
[15] 段佩祥, 钱海忠, 何海威, 等. 一种基于动态多尺度聚类的湖泊选取方法[J]. 武汉大学学报(信息科学版), 2019, 44(10):1567-1574. DOI:10.13203/j.whugis20170316. DUAN Peixiang, QIAN Haizhong, HE Haiwei, et al. A lake selection method based on dynamic multi-scale clustering[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10):1567-1574. DOI:10.13203/j.whugis20170316.
[16] BIRANT D, KUT A. ST-DBSCAN:an algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering, 2007, 60(1):208-221. DOI:10.1016/j.datak.2006.01.013.
[17] 邓敏, 刘启亮, 李光强, 等. 一种基于似最小生成树的空间聚类算法[J]. 武汉大学学报(信息科学版), 2010, 35(11):1360-1364. DENG Min, LIU Qiliang, LI Guangqiang, et al. A spatial clustering algorithm based on minimum spanning tree-like[J]. Geomatics and Information Science of Wuhan University, 2010, 35(11):1360-1364.
[18] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496. DOI:10.1126/science.1242072.
[19] 王培晓, 张恒才, 王海波, 等. ST-CFSFDP:快速搜索密度峰值的时空聚类算法[J]. 测绘学报, 2019, 48(11):1380-1390. DOI:10.11947/j.AGCS.2019.20180538. WANG Peixiao, ZHANG Hengcai, WANG Haibo, et al. Spatial-temporal clustering by fast search and find of density peaks[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11):1380-1390. DOI:10.11947/j.AGCS.2019.20180538.
[20] 王光霞, 游雄. 地图设计与编绘[M]. 北京:中国测绘出版社, 2011. WANG Guangxia, YOU Xiong. Map design and compilation[M]. Beijing:Surveying and Mapping Press, 2011.
[21] YAN Haowen, WEIBEL R, YANG Bisheng. A multi-parameter approach to automated building grouping and generalization[J]. Geoinformatica, 2008, 12(1):73-89. DOI:10.1007/s10707-007-0020-5.
[22] LI Zhilin, YAN Haowen, AI Tinghua, et al. Automated building generalization based on urban morphology and gestalt theory[J]. International Journal of Geographical Information Science, 2004, 18(5):514-534. DOI:10.1080/13658810410001702021.
[23] 高凯, 杨敏, 张跃鹏. 保持空间分布特征的散列式居民地综合选取方法[J]. 测绘科学技术学报, 2015, 32(6):626-630. DOI:10.3969/j.issn.1673-6338.2015.06.016. GAO Kai, YANG Min, ZHANG Yuepeng. A method of automatic selection of hash-style habitation with spatial distribution characteristics preserved[J]. Journal of Geomatics Science and Technology, 2015, 32(6):626-630. DOI:103969/j.issn.1673-6338.2015.06.016.
[24] 刘呈熠, 武芳, 巩现勇, 等. 规则池塘群的复杂直线模式识别[J]. 测绘学报, 2020, 49(2):256-266. DOI:10.11947/j.AGCS.2020.20190030. LIU Chengyi, WU Fang, GONG Xianyong, et al. Complex linear pattern recognition for regular pond groups[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(2):256-266. DOI:10.11947/j.AGCS.2020.20190030.
[25] FAHAD A, ALSHATRI N, TARI Z, et al. A survey of clustering algorithms for big data:taxonomy and empirical analysis[J]. IEEE Transactions on Emerging Topics in Computing, 2014, 3(2):267-279. DOI:10.1109/TETC.2014.2330519.
[26] 周志华. 机器学习[M]. 北京:清华大学出版社, 2016. ZHOU Zhihua. Machine learning[M]. Beijing:Tsinghua University Press, 2016.