Discovery of co-location patterns based on natural neighborhood

doi:10.11947/j.AGCS.2019.20170653

Abstract

Abstract:

Discovery of co-location patterns is crucial to understanding the interaction among different spatial features. The construction of neighborhood relationship among spatial features plays a key role in co-location pattern mining, however, existing methods are difficult to construct appropriate neighborhood relationship when the spatial features distribute unevenly.This limitation is very likely to make the omission and/or misjudgment of co-location patterns.To address this issue, a co-location pattern mining method based on natural neighborhood is proposed in this study.After removing the randomly distributed spatial features,natural neighborhood relationship among different spatial features is adaptively constructed on basis of three principles, i.e. geographic proximity, the consistency of density and compactness of neighboring relationship. The multi-level co-location patterns are discovered based on the delaunay triangulation network. The experimental results showed that the proposed method could discover the co-location patterns among unevenly distributed spatial features completely and accurately, and no user-specified parameters are required for the construction of natural neighborhood.

Key words: co-location pattern, natural neighborhood, delaunay triangulation network, adaptive

CLC Number:

P208

LIU Wenkai, LIU Qiliang, CAI Jiannan. Discovery of co-location patterns based on natural neighborhood[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(1): 95-105.

References

[1] 王香红, 栾兆擎, 闫丹丹, 等. 洪河沼泽湿地17种植物的生态位[J]. 湿地科学, 2015, 13(1):49-54. WANG Xianghong, LUAN Zhaoqing, YAN Dandan, et al. Niche of 17 kinds of plants in marshes in Honghe[J]. Wetland Science, 2015, 13(1):49-54.
[2] WANG Fahui, HU Yujie, WANG Shuai, et al. Local indicator of colocation quotient with a statistical significance test:examining spatial association of crime and facilities[J]. The Professional Geographer, 2017, 69(1):22-31.
[3] YU Wenhao, AI Tinghua, HE Yakun, et al. Spatial co-location pattern mining of facility points-of-interest improved by network neighborhood and distance decay effects[J]. International Journal of Geographical Information Science, 2017, 31(2):280-296.
[4] WANG Junmei, HSU W, LEE M L. A framework for mining topological patterns in spatio-temporal databases[C]//Proceedings of the 14th ACM International Conference on Information and Knowledge Management. Bremen, Germany:ACM, 2005:429-436.
[5] HUANG Y, SHEKHAR S, XIONG H. Discovering colocation patterns from spatial data sets:a general approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12):1472-1485.
[6] YOO J S, SHEKHAR S, SMITH J, et al. A partial join approach for mining co-location patterns[C]//Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems. Washington DC:ACM, 2004:241-249.
[7] YOO J S, SHEKHAR S. A joinless approach for mining spatial colocation patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10):1323-1337.
[8] XIAO Xiangye, XIE Xing, LUO Qiong, et al. Density based co-location pattern discovery[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Irvine, California:ACM, 2008:102-114. DOI:10.1145/1463434.1463471.
[9] YOO J S, BOW M. Mining spatial colocation patterns:a different framework[J]. Data Mining and Knowledge Discovery, 2012, 24(1):159-194.
[10] QIAN Feng, HE Qinming, CHIEW K, et al. Spatial co-location pattern discovery without thresholds[J]. Knowledge and Information Systems, 2012, 33(2):419-445.
[11] DENG Min, HE Zhanjun, LIU Qiliang, et al. Multi-scale approach to mining significant spatial co-location patterns[J]. Transactions in GIS, 2017, 21(5):1023-1039.
[12] BARUA S, SANDER J. Mining statistically significant co-location and segregation patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5):1185-1199.
[13] QIAN Feng, CHIEW K, HE Qinming, et al. Mining regional co-location patterns with kNNG[J]. Journal of Intelligent Information Systems, 2014, 42(3):485-505.
[14] CELIK M, KANG J M, SHEKHAR S. Zonal co-location pattern discovery with dynamic parameters[C]//Proceedings of the 7th IEEE International Conference on Data Mining. Omaha:IEEE, 2007:433-438.
[15] DING Wei, EICK C F, YUAN Xiaojing, et al. A framework for regional association rule mining and scoping in spatial datasets[J]. Geoinformatica, 2011, 15(1):1-28.
[16] MOHAN P, SHEKHAR S, SHINE J A, et al. A neighborhood graph based approach to regional co-location pattern discovery:a summary of results[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago, Illinois:ACM, 2011:122-132.
[17] 蔡建南, 刘启亮, 徐枫, 等. 多层次空间同位模式自适应挖掘方法[J]. 测绘学报, 2016, 45(4):475-485. DOI:10.11947/j.AGCS.2016.20150337. CAI Jiannan, LIU Qiliang, XU Feng, et al. An adaptive method for mining hierarchical spatial co-location patterns[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4):475-485. DOI:10.11947/j.AGCS.2016.20150337.
[18] 边馥苓, 万幼. k-邻近空间关系下的空间同位模式挖掘算法[J]. 武汉大学学报(信息科学版), 2009, 34(3):331-334. BIAN Fuling, WAN You. A novel spatial co-location pattern mining algorithm based on k-nearest feature relationship[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3):331-334.
[19] BEMBENIK R, RYBIИSKI H. FARICS:A method of mining spatial association rules and collocations using clustering and delaunay diagrams[J]. Journal of Intelligent Information Systems, 2009, 33(1):41-64.
[20] SUNDARAM V M, THNAGAVELU A, PANEER P. Discovering co-location patterns from spatial domain using a delaunay approach[J]. Procedia Engineering, 2012, 38(12):2832-2845.
[21] FORTIN M J, DALE M R T. Spatial analysis:a guide for ecologists[M]. Cambridge:Cambridge University Press, 2005.
[22] CAI Jiannan, DENG Min, LIU Qiliang, et al. Nonparametric significance test for discovery of network-constrained spatial co-location patterns[J]. Geographical Analysis, 2018, 65(9):126-137.
[23] BUYONG T. Spatial data analysis for geographic information science[M]. Kuala Lumpur, Malaysia:Penerbit UTM, 2007.
[24] CLARK P J, EVANS F C. Distance to nearest neighbor as a measure of spatial relationships in populations[J]. Ecology, 1954, 35(4):445-453.
[25] INKAYA T, KAYALIGIL S, ÖZDEMIREL N E. An adaptive neighbourhood construction algorithm based on density and connectivity[J]. Pattern Recognition Letters, 2015, 52(1):17-24.
[26] 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.
[27] 龙冬平, 柳林, 冯嘉欣, 等. 社区环境对入室盗窃和室外盗窃影响的对比分析——以ZG市ZH半岛为例[J]. 地理学报, 2017, 72(2):341-355. LONG Dongping, LIU Lin, FENG Jiaxin, et al. Comparisons of the community environment effects on burglary and outdoor-theft:a case study of ZH peninsula in ZG city[J]. Acta Geographica Sinica, 2017, 72(2):341-355.