CPM-MCHM:一种基于极大团和哈希表的空间并置模式挖掘算法

• 作者: 张绍雪 王丽珍 陈文和
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 空间数据挖掘 空间并置模式 两阶段挖掘框架 极大团 哈希表
• 年，卷（期）: 2022,（3）
• 页码范围: 526-541
• 页数: 16页
• 分类号: TP18
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2022.0526

摘要

空间并置(co-location)模式挖掘是指在大量的空间数据中发现一组空间特征的子集,这些特征的实例在地理空间中频繁并置出现.传统的空间并置模式挖掘算法通常采用逐阶递增的挖掘框架,从低阶模式开始生成候选模式并计算其参与度(空间并置模式的频繁性度量指标).虽然这种挖掘框架可以得到正确和完整的结果,但是带来的时间和空间开销非常大.此外传统方法对于空间并置模式的最小频繁性阈值较为敏感,当最小频繁性阈值改变时整个挖掘过程需要重新进行.因此,本文提出一种基于极大团和哈希表的空间并置模式挖掘算法CPM-MCHM(Co-location Pattern Mining based on Maximal Clique and Hash Map)来发现完整并且正确的频繁空间并置模式.CPM-MCHM算法不仅避免逐阶候选-测试框架带来的巨大开销问题,还降低了算法对最小频繁性阈值的敏感.首先,采用基于位运算的分区Bron–Kerbosch算法生成给定空间数据集的所有极大团,并将其存储在哈希表中.然后,提出一种两阶段挖掘框架计算所有模式的参与度并过滤所有频繁空间并置模式.最后,在真实和合成数据集上进行了大量的对比实验.与经典的传统算法和近两年内学者提出的两种算法相比,当实验数据的规模达到20万实例数时,本文提出的CPM-MCHM算法的挖掘时间和空间耗费分别降低了90％和70％以上,当实验数据量进一步加大时CPM-MCHM算法的优势更加明显.