Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2024, Vol. 58 Issue (5): 918-930    DOI: 10.3785/j.issn.1008-973X.2024.05.005
    
Multi-level co-location pattern mining algorithm based on grid spatial cliques
Yuqing LIU1(),Lizhen WANG2,*(),Peizhong YANG1,Lisha PIAO2
1. School of Information Science and Engineering, Yunnan University, Kunming 650504, China
2. Institute of Science and Technology, Dianchi College of Yunnan University, Kunming 650228 ,China
Download: HTML     PDF(2343KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A novel framework of reverse mining of multi-level co-location patterns was proposed aiming at the problems that traditional methods of multi-level co-location pattern mining did not consider the grid characteristics of the real data distribution, and the multi-level mining framework from global to regional led to the algorithm inefficiency. The regional co-location patterns were first mined, and the global co-location patterns were deduced based on the mined regional patterns. Some pruning strategies were proposed to enhance the mining efficiency. The grid characteristics of the data distribution in real datasets were considered, and the grid neighbor relationship between instances was defined. The concept of grid spatial cliques with a novel method for calculating grid spatial cliques was defined. An adaptive grid density peak clustering strategy for partitioning regions was proposed in the regional division stage, and clusters were assigned based on the similarity of two-size grid spatial cliques. Extensive experiments were conducted on both synthetic and real-world datasets. The experimental results validated the effectiveness, efficiency and scalability of the proposed method. A pruning rate of up to 78% was achieved on real datasets.



Key wordsspatial data mining      multi-level co-location pattern      grid spatial clique      density peak clustering (DPC)     
Received: 03 July 2023      Published: 26 April 2024
CLC:  TP 311  
Fund:  国家自然科学基金资助项目(62276227, 62306266, 62266050);云南省基础研究计划资助项目(202201AS070015,202401AT070450);云南省创新团队资助项目(2018HC019) ;云南省智能系统与计算重点实验室建设项目(202205AG070003).
Corresponding Authors: Lizhen WANG     E-mail: liuyuqing@mail.ynu.edu.cn;lzhwang@ynu.edu.cn
Cite this article:

Yuqing LIU,Lizhen WANG,Peizhong YANG,Lisha PIAO. Multi-level co-location pattern mining algorithm based on grid spatial cliques. Journal of ZheJiang University (Engineering Science), 2024, 58(5): 918-930.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2024.05.005     OR     https://www.zjujournals.com/eng/Y2024/V58/I5/918


基于网格空间团的多级同位模式挖掘方法

针对传统的多级同位模式挖掘方法未考虑到实际数据分布的网格特性,且从全局到区域的多级模式挖掘框架会导致算法效率低下的问题,提出逆向挖掘多级同位模式的新框架. 先挖掘区域同位模式,再由区域同位模式推导出全局同位模式,提出有效的剪枝策略提高挖掘效率. 考虑真实数据集中数据分布的网格特性,定义实例间的网格邻近关系,提出网格空间团及计算网格空间团的新颖方法. 在区域划分阶段,提出基于自适应网格密度峰值聚类的区域划分方法,基于2阶网格空间团的网格相似性来分配簇. 在合成和实际数据集上进行大量的实验,验证了提出方法的有效性、高效性和可扩展性,在真实数据集上的剪枝率可以达到78%.


关键词: 空间数据挖掘,  多级同位模式,  网格空间团,  密度峰值聚类(DPC) 
Fig.1 Example of regional data containing four spatial features A, B, C, D (left figure) and some examples of pattern participation instances (right figure)
Fig.2 Examples for illustrating grid similarity measure
Fig.3 Comparison of multi-level co-location pattern mining framework
Fig.4 Examples of candidate participating instances
Fig.5 Distribution of real datasets and their partition results
方法EI
深圳高黎贡山
S-ML0.98920.8771
S-ML-20.87830.6564
FDPC-RCPM0.65320.6401
Tab.1 EI values for different methods
Fig.6 Comparison of mined prevalent regions of regional co-location patterns
Fig.7 Distribution of global patterns identified by ML
Fig.8 Distribution of global patterns identified by proposed method
Fig.9 Comparison of running time under different prevalent thresholds
Fig.10 Comparison of number of regional patterns under different prevalent thresholds
Fig.11 Pruning rate of S-ML algorithm
Fig.12 Experimental contrasts on synthetic datasets
[1]   HE Z, DENG M, XIE Z, et al Discovering the joint influence of urban facilities on crime occurrence using spatial co-location pattern mining[J]. Cities, 2020, 99: 102612
doi: 10.1016/j.cities.2020.102612
[2]   LI J, ADILMAGAMBETOV A, MOHOMED JABBAR M S, et al On discovering co-location patterns in datasets: a case study of pollutants and child cancers[J]. Geo Informatica, 2016, 20 (4): 651- 692
[3]   LU J L, WANG L Z, FANG Y, et al Mining strong symbiotic patterns hidden in spatial prevalent co-location patterns[J]. Knowledge-Based Systems, 2018, 146: 190- 202
doi: 10.1016/j.knosys.2018.02.006
[4]   WEILER M, SCHMID K A, MAMOULIS N, et al. Geo-social co-location mining [C]// 2nd International ACM Workshop on Managing and Mining Enriched Geo-Spatial Data . Melbourne: ACM, 2015: 19-24.
[5]   CHEN Y M, CHEN X Y, LIU Z H, et al Understanding the spatial organization of urban functions based on co-location patterns mining: a comparative analysis for 25 Chinese cities[J]. Cities, 2020, 97: 102563
doi: 10.1016/j.cities.2019.102563
[6]   蒋希文, 王丽珍, TRAN V H 基于模糊密度峰值聚类的区域同位模式并行挖掘算法[J]. 中国科学:信息科学, 2023, 53 (7): 1281- 1298
JIANG Xiwen, WANG Lizhen, TRAN V H Parallel mining algorithm for regional co-location patterns based on fuzzy density peak clustering[J]. Scientia Sinica Informationis, 2023, 53 (7): 1281- 1298
[7]   刘新斌, 王丽珍, 周丽华 MLCPM-UC: 一种基于模式实例分布均匀系数的多级 co-location 模式挖掘算法[J]. 计算机科学, 2021, 48 (11): 208- 218
LIU Xinbin, WANG Lizhen, ZHOU Lihua MLCPM-UC: a multi-level co-location pattern mining algorithm based on uniform coefficient of pattern instance distribution[J]. Computer Science, 2021, 48 (11): 208- 218
doi: 10.11896/jsjkx.201000097
[8]   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
doi: 10.1109/TKDE.2004.90
[9]   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
doi: 10.1109/TKDE.2006.150
[10]   WANG L Z, ZHOU L H, LU J A, et al An order-clique-based approach for mining maximal co-locations[J]. Information Sciences, 2009, 179 (19): 3370- 3382
doi: 10.1016/j.ins.2009.05.023
[11]   张绍雪, 王丽珍, 陈文和 CPM-MCHM: 一种基于极大团和哈希表的空间并置模式挖掘算法[J]. 计算机学报, 2022, 45 (3): 526- 541
ZHANG Shaoxue, WANG Lizhen, TRAN V H An order-clique-based approach for mining maximal co-locations[J]. Chinese Journal of Computers, 2022, 45 (3): 526- 541
doi: 10.11897/SP.J.1016.2022.00526
[12]   EICK C F, PARMAR R, DING W, et al. Finding regional co-location patterns for sets of continuous variables in spatial datasets [C]// Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems . Irvine: ACM, 2008: 1-10.
[13]   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: ACM, 2011: 122-132.
[14]   DENG M, CAI J N, LIU Q L, et al Multi-level method for discovery of regional co-location patterns[J]. International Journal of Geographical Information Science, 2017, 31 (9): 1846- 1870
doi: 10.1080/13658816.2017.1334890
[15]   LIU Q L, LIU W K, DENG M, et al An adaptive detection of multilevel co-location patterns based on natural neighborhoods[J]. International Journal of Geographical Information Science, 2021, 35 (3): 556- 581
doi: 10.1080/13658816.2020.1775235
[16]   LIU W K, LIU Q L, DENG M, et al Discovery of statistically significant regional co-location patterns on urban road networks[J]. International Journal of Geographical Information Science, 2022, 36 (4): 749- 772
doi: 10.1080/13658816.2021.1981335
[17]   CELIK M, KANG J M, SHEKHAR S. Zonal co-location pattern discovery with dynamic parameters [C]// 7th IEEE International Conference on Data Mining . Omaha: IEEE, 2007: 433-438.
[18]   DING W, EICK C F, YUAN X, et al A framework for regional association rule mining and scoping in spatial datasets[J]. Geo-Informatica, 2011, 15: 1- 28
[19]   QIAN F, CHIEW K, HE Q M, et al Mining regional co-location patterns with kNNG[J]. Journal of Intelligent Information Systems, 2014, 42: 485- 505
doi: 10.1007/s10844-013-0280-5
[20]   WANG S, HUANG Y, WANG X S. Regional co-locations of arbitrary shapes [C]// Advances in Spatial and Temporal Databases: 13th International Symposium . Berlin: Springer, 2013: 19-37.
[21]   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
[22]   LIU Y H, MA Z M, YU F Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy[J]. Knowledge-Based Systems, 2017, 133: 208- 220
doi: 10.1016/j.knosys.2017.07.010
[23]   杨培忠, 王丽珍, 王晓璇, 等. 一种基于列计算的空间并置模式挖掘方法[J]. 中国科学: 信息科学, 2022, 52(6): 1053–1068.
YANG Peizhong, WANG Lizhen, WANG Xiaoxuan, et al. A spatial co-location pattern mining approach based on column calculation [J]. Scientia Sinica Informationis , 2022, 52(6): 1053–1068.
[1] Yue ZHAO,He ZHAO,Haibo TAN,Bin YU,Wangnian YU,Zhiyu MA. Improved method for blockchain Kademlia network based on small world theory[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(1): 1-9.
[2] Can CUI,Xiao-hu YANG,Wei-wei QIU,Fang-lei HUANG. GPU-based acceleration technology for signature verification of blockchain transactions[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(8): 1505-1515.
[3] Jin WANG,Bo-han LI,Jia-jun WU,Xin-yang SONG. Distributed consistency protocol supporting log submission out-of-order[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(2): 320-329.
[4] Liang SUN,Xiao-feng LI,He ZHAO,Bin YU,Tong ZHOU,Xi-ru LI. NFT-based method for assetization of physical assets on blockchain[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(10): 1900-1911.
[5] Shu-qin YANG,Yu-hao MA,Ming-yu FANG,Wei-xing QIAN,Jie-xuan CAI,Tong LIU. Lane detection method in complex environments based on instance segmentation[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(4): 809-815, 832.
[6] Tian-lun DAI,Bo-han LI,Ya-lei ZANG,Hua DAI,Zi-qiang YU,Gang CHEN. PORP: parallel optimization strategy of route planning for self-driving vehicles[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 329-337.
[7] Miao HE,Fen-hua BAI,Zhuo YU,Tao SHEN. Publicly verifiable secret sharing technology in blockchain[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 306-312.
[8] You-wei WANG,Li-zhou FENG. Improved AdaBoost algorithm using group degree and membership degree based noise detection and dynamic feature selection[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 367-376.
[9] Jia-hao LIAO,Zhi-wen YU,Yi-meng LIU,Bin GUO. Design and implementation of mobile crowdsensing platform[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(10): 1915-1922.
[10] Zi-long JI,Jun-zhong JI. Learning effective connectivity network structure based on parallel searching of double firefly populations[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(4): 694-703.
[11] Wan-liang WANG,Xiao-han YANG,Yan-wei ZHAO,Nan GAO,Chuang LV,Zhao-juan ZHANG. Image enhancement algorithm with convolutional auto-encoder network[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(9): 1728-1740.
[12] Zhi-yuan WAN,Jia-heng TAO,Jia-kun LIANG,Zhen-gong CAI,Cheng CHANG,Lin QIAO,Qiao-ni ZHOU. Large-scale empirical study on machine learning related questions on Stack Overflow[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(5): 819-828.
[13] Kai-long ZHU,YU-liang LU,Hui HUANG,Zhao-kun DENG,Yi-jie DENG. Construction approach for control flow graph from binaries using hybrid analysis[J]. Journal of ZheJiang University (Engineering Science), 2019, 53(5): 829-836.
[14] YUAN You-wei-, YU Jia, ZHENG Hong-sheng, WANG Jiao-jiao. Cloud workflow scheduling algorithm based on novelty ranking and multi-quality of service[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(6): 1190-1196.
[15] WANG Haiyan, CHENG Yan . Dual service selection method based on coefficient of variation[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(6): 1197-1204.