一种基于列计算的空间并置模式挖掘方法  

A spatial co-location pattern mining approach based on column calculation

作　　者：杨培忠[1] 王丽珍[1] 王晓璇 周丽华[1] Peizhong YANG;Lizhen WANG;Xiaoxuan WANG;Lihua ZHOU(School of Information Science and Engineering,Yunnan University,Kunming 650504,China)

机构地区：[1]云南大学信息学院,昆明650504

出　　处：《中国科学：信息科学》2022年第6期1053-1068,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:62062066,61966036,61662086,61762090);云南省创新团队(批准号:2018HC019)项目资助。

摘　　要：空间并置(co-location)模式挖掘旨在发现空间特征间的关联关系.一个并置模式是空间特征集合的子集,它们的实例在空间中频繁并置出现.传统的并置模式挖掘方法大多基于表实例计算模式的并置程度,但表实例的生成和存储将导致巨大的时间、空间消耗.针对这一问题,本文提出了一种基于列计算的空间并置模式挖掘方法,不再生成表实例,只需要搜索模式的参与实例.为了加速参与实例搜索,设计了实例搜索空间剪枝、候选参与实例验证、频繁性提前感知等优化策略.在此基础上,提出了CPM-Col算法,讨论了算法的复杂度、正确性和完备性.在真实和模拟数据集上进行了大量实验,实验结果表明,本文提出的算法比其他7个baseline算法具有更好的性能和可扩展性,特别地,CPM-Col算法的效率提升达到数倍至数个量级.此外,实验验证了本文提出的优化策略的有效性.Spatial co-location pattern mining aims to discover correlations between spatial features.A colocation pattern corresponds to a subset of spatial features whose instances are frequently located in spatial neighborhoods.Most co-location pattern mining approaches calculate the prevalence based on table instances,but the time and space costs of generating table instances are enormous.To address this problem,this paper presents a novel co-location pattern mining approach based on column calculation,which only searches for participating instances of features in a pattern without having to generate the table instance.Furthermore,this paper designs the instance search space pruning,the candidate participating instance verification,and the prevalence beforehand awareness technologies to speed up the search of participating instances.The CPM-Col method is proposed on this basis,and its complexity,accuracy,and completeness are addressed.Extensive experiments are conducted on real and synthetic datasets,and experimental results show that the CPM-Col algorithm has better performance and scalability than seven other baseline algorithms,especially with a performance gain of several times or even orders of magnitude.Moreover,the effectiveness of the proposed optimization strategies is verified experimentally.

关 键 词：空间数据挖掘 并置模式 列计算 搜索算法 剪枝技术 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]