Abstract：A spatial co-location pattern is a set of spatial features that are frequently observed together in space. Traditional co-location pattern mining uses a single distance threshold to define neighbor relationships while ignoring the impact of distance differences, but the minimum prevalence threshold is difficult to determine for inexperienced users. This paper presents a method for calculating the neighborhood membership degree based on fuzzy theory and d-grids. This method does not calculate the Euclidean distance and quickly finds the maximal cliques that satisfy the fuzzy neighborhood relationship by using the d-grid. The results was then combined with the Top-k algorithm to find the k most prevalent co-location patterns. Tests show that this method is more efficient and gives more detailed results. The recall rate shows that the k most prevalent patterns obtained by this method agree well with those obtained by the traditional co-location pattern mining algorithm, which shows the effectiveness of this fuzzy measurement and mining algorithm.
李钧毅, 王丽珍, 陈红梅. dGridTopk-FCPM：一种基于模糊理论和d-网格的Top-k空间co-location模式挖掘方法[J]. 清华大学学报（自然科学版）, 2021, 61(9): 943-952.
LI Junyi, WANG Lizhen, CHEN Hongmei. dGridTopk-FCPM: A top-k spatial co-location pattern mining algorithm based on fuzzy theory and d-grids. Journal of Tsinghua University(Science and Technology), 2021, 61(9): 943-952.
[1] YOO J S, SHEKHAR S, CELIK M. A join-less approach for co-location pattern mining: A summary of results[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1323-1337. [2] YOO J S, BOW M. Mining top-k closed co-location patterns[C]//Proceedings of the IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services. Fuzhou, China: IEEE, 2011: 100-105. [3] ZADEH L A. Fuzzy sets[J]. Information and Control, 1965, 8(3): 338-353. [4] HUANG Y, SHEKHAR S, XIONG H. Discovering co-location patterns from spatial data sets: A general approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472-1485. [5] BAO X G, WANG L Z. A clique-based approach for co-location pattern mining[J]. Information Sciences, 2019, 490: 244-264. [6] TRAN V, WANG L Z. Delaunay triangulation-based spatial colocation pattern mining without distance thresholds[J]. Statistical Analysis Data Mining: The ASA Data Science Journal, 2020, 13(3): 282-304. [7] HAN J W, PEI J, YIN Y W, et al. Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas, USA: ACM, 2000： 1-12. [8] WANG L Z, BAO Y Z, LU J, et al. A new join-less approach for co-location pattern mining[C]//Proceedings of the 8th IEEE International Conference on Computer and Information Technology. Sydney, Australia: IEEE, 2008: 197-202. [9] WANG L Z, BAO Y Z, LU Z Y. Efficient discovery of spatial co-location patterns using the iCPI-tree[J]. The Open Information Systems Journal, 2009, 3(1): 69-80. [10] WANG L Z, ZHOU L H, LU J, et al. An order clique based approach for mining maximal co-locations[J]. Information Sciences, 2009, 179(19): 3370-3382. [11] CHAN H K, LONG C, YAN D, et al. Fraction-score: A new support measure for co-location pattern mining[C]//35th International Conference on Data Engineering. Macao, China: IEEE, 2019: 1514-1525. [12] ANDRZEJEWSKI W, BOINSKI P. Parallel approach to incremental co-location pattern mining[J]. Information Sciences, 2019, 496: 485-505. [13] YU W H. Spatial co-location pattern mining for location-based services in road networks[J]. Expert Systems with Applications, 2016, 46: 324-335. [14] MASRUR A, THAKUR G, SPARKS K, et al. Co-location pattern mining of geosocial data to characterize urban functional spaces[C]//2019 IEEE International Conference on Big Data. Los Angeles, USA: IEEE, 2019: 4099-4102. [15] YANG P Z, WANG L Z, WANG X X, et al. An effective approach on mining co-location patterns from spatial databases with rare features[C]//20th IEEE International Conference on Mobile Data Management. Hong Kong, China: IEEE, 2019: 53-62. [16] ANDRZEJEWSKI W, BOINSKI P. Efficient spatial co-location pattern mining on multiple GPUs[J]. Expert Systems with Applications, 2018, 93: 465-483. [17] 欧阳志平, 王丽珍, 陈红梅. 模糊对象的空间co-location模式挖掘研究[J]. 计算机学报, 2011, 34(10): 1947-1955. OUYANG Z P, WANG L Z, CHEN H M. Research on spatial co-location pattern mining of fuzzy objects[J]. Chinese Journal of Computers, 2011, 34(10): 1947-1955. (in Chinese) [18] OUYANG Z P, WANG L Z, WU P P. Spatial co-location pattern discovery from fuzzy objects[J]. International Journal on Artificial Intelligence Tools, 2017, 26(2): 1750003. [19] LEI L, WANG L Z, WANG X X. Mining spatial co-location patterns by fuzzy technology[C]//Proceedings of the 2019 IEEE International Conference on Big Knowledge. Beijing, China: IEEE, 2019: 129-136. [20] WANG M J, WANG L Z, ZHAO L H. Spatial co-location pattern mining based on fuzzy neighbor relationship[J]. Journal of Information Science and Engineering, 2019, 35(6): 1343-1363. [21] 国家信息中心. 高德地图兴趣点POI (Point of Interest)数据[DS/OL]. (2018-11-16). https://doi.org/10.18170/DVN/WSXCNM. State Information Center. Map POI (Point of Interest) data[DS/OL]. (2018-11-16). https://doi.org/10.18170/DVN/WSXCNM. (in Chinese)
2021, Vol. 61 
