dGridTopk-FCPM: A top-k spatial co-location pattern mining algorithm based on fuzzy theory and d-grids

LI Junyi; WANG Lizhen; CHEN Hongmei

doi:10.16511/j.cnki.qhdxxb.2020.26.034

PDF(1680 KB)

Journal of Tsinghua University(Science and Technology) ›› 2021, Vol. 61 ›› Issue (9) : 943-952. DOI: 10.16511/j.cnki.qhdxxb.2020.26.034

DATABASE

dGridTopk-FCPM: A top-k spatial co-location pattern mining algorithm based on fuzzy theory and d-grids

{{article.zuoZhe_EN}}

Author information +

History +

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.

Key words

spatial data mining / spatial co-location pattern / Top-k / fuzzy theory / d-grid

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

LI Junyi, WANG Lizhen, CHEN Hongmei. dGridTopk-FCPM: A top-k spatial co-location pattern mining algorithm based on fuzzy theory and d-grids[J]. Journal of Tsinghua University(Science and Technology). 2021, 61(9): 943-952 https://doi.org/10.16511/j.cnki.qhdxxb.2020.26.034

References

[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)