基于变化参与实例的空间并置模式增量挖掘方法  

Incremental mining method of spatial co-location patterns based on changed participating instances

作　　者：芦俊丽 昌鑫 罗浩瑜 刘士虎[1] Lu Junli;Chang Xin;Luo Haoyu;Liu Shihu(Dept.of Mathematics&Computer Science,Yunnan Minzu University,Kunming 650500,China)

机构地区：[1]云南民族大学数学与计算机科学学院,昆明650500

出　　处：《计算机应用研究》2025年第2期431-440,共10页Application Research of Computers

基　　金：国家自然科学基金资助项目(61966039);兴滇英才青年拔尖人才项目(XDYC-QNRC-2022-0518)。

摘　　要：空间并置模式是一组空间特征的子集,它们的实例在空间中频繁关联。空间并置模式挖掘是空间数据挖掘的一个重要分支。然而,空间数据库随时间不断变化,高效的空间并置模式增量挖掘显得尤为重要。提出基于变化参与实例的空间并置模式增量挖掘方法,相比传统的增量挖掘算法,不进行耗时的变化表实例生成操作,直接搜索变化参与实例。为加速变化参与实例搜索过程,提出了实例级搜索优化策略、启发式模式剪枝技术,进而提出了IMCP-CPI,讨论了算法的复杂度、正确性和完备性。在真实和模拟数据集上进行了大量实验验证IMCP-CPI的性能。结果表明IMCP-CPI远优于当前已知的5个空间并置模式增量挖掘算法,其效率提升数倍甚至数个量级。在变化数据占比为原数据集5%的新数据集中,当距离阈值d很大或者参与度阈值min_prev很小时,IMCP-CPI的性能比当前并置模式挖掘较优算法CPM-Col及改进算法CPM-iCol提升2~3倍。此外,当变化数据占比分别小于等于原数据集的25%和50%时,无论在参数变化还是可扩展性方面,IMCP-CPI均优于CPM-iCol和CPM-Col,这对具体实践中的方法选取给与了参考意见。A spatial co-location pattern corresponds to a subset of spatial features,whose instances are frequently located in spatial neighborhoods.Spatial co-location pattern mining is an important direction of spatial data mining.However,spatial database is changing continually,efficient spatial co-location pattern incremental mining is vital.This paper presented an incremental mining method of spatial co-location patterns based on changed participating instances,which directly searched for changed participating instances without performing time-consuming operations of generating change table instances.Furthermore,to speed up the search of changed participating instances,this paper designed an instance searching optimization strategy and a heuristic pattern pruning technique.On this basis,this paper introduced incremental mining method of spatial co-location patterns based on changed participating instances(IMCP-CPI),and comprehensively analyzed its complexity,correctness,and completeness.The extensive experiments on real and synthetic datasets validated the efficiency of IMCP-CPI algorithm.The results show that IMCP-CPI is much better than 5 known incremental mining algorithms of spatial co-location patterns,especially with a performance gain of several times or even orders of magnitude.In a new dataset where the proportion of changed data accounts for 5%of the original dataset,when the distance threshold d is very large or the participation threshold min_prev is very small,the performance of the IMCP-CPI is 2~3 times better than the current optimal algorithm for co-location pattern mining,CPM-Col,and its improved version CPM-iCol.Furthermore,when the proportion of changed data is less than or equal to 25%and 50%of the original dataset,respectively,IMCP-CPI outperforms both CPM-iCol and CPM-Col in terms of parameter variations and scalability.This provides valuable reference insights for method selection in practical applications.

关 键 词：空间并置模式挖掘 增量挖掘 变化参与实例 实例搜索空间 模式剪枝技术 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]