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

昌鑫 芦俊丽 陈书健 段鹏

摘 要：空间并置（co-location）模式挖掘旨在发现空间特征间的关联关系，是空间数据挖掘的重要研究方向。基于列计算的空间并置模式挖掘方法（CPM-Col算法）避开挖掘过程中最耗时的表实例生成操作，直接搜索模式的参与实例，成为当前高效的方法之一。然而，回溯法搜索参与实例仍是该方法的瓶颈，尤其在稠密数据和长模式下。为加速参与实例的搜索，充分利用CPM-Col算法搜索参与实例时得到的行实例，在不增加额外计算的前提下对CPM-Col算法进行两点改进。首先，将CPM-Col算法搜索到的行实例存储为部分表实例，利用子模式的部分表实例快速确定参与实例，避免了大量实例的回溯计算。其次，在CPM-Col算法获得一条行实例后，利用行实例的子团反作用于第一个特征，得到第一个特征的参与实例，避免了这些实例的回溯搜索。由此，提出了基于改进列计算的空间并置模式挖掘算法（CPM-iCol算法），并讨论了算法的复杂度、正确性和完备性。在合成数据和真实数据集上进行了实验，与经典的传统算法join-less和CPM-Col进行对比，CPM-iCol算法明显缩短了挖掘的时间，减少了回溯的次数。实验结果表明，该算法比CPM-Col具有更好的性能和可扩展性，特别在稠密数据集中效果更加明显。

关键词：空间数据挖掘；空间并置模式；列计算；回溯搜索

中图分类号：TP391   文献标志码：A    文章编号：1001-3695（2024）05-014-1374-07

doi： 10.19734/j.issn.1001-3695.2023.09.0448

Method for co-location pattern mining based on improved column calculation

Abstract：Spatial co-location pattern mining aims to discover the association between spatial features and has been an important research direction in spatial data mining. Spatial co-location pattern mining method based on column calculation（CPM-Col algorithm） avoids the most time-consuming operation of generating table instances and directly searches for participating instances. This method has become one of the most efficient approaches. However， backtracking search for participating instances remains a bottleneck， especially in dense datasets and long pattern mining. To accelerate the search for participating instances， this paper proposed two improvements to the CPM-Col algorithm with less extra computations. Firstly， the row instances found by CPM-Col algorithm were stored as partial table instances， for avoiding backtracking calculations of many instances. Secondly， after successfully finding a row instance， some instances of the first feature were obtained by the sub-clique reaction of the row instance. Based on these improvements， this paper proposed a co-location pattern mining method based on improved column calculation （CPM-iCol algorithm） and discussed complexity， correctness， and completeness. Experiments were conducted on synthetic and real datasets. Comparing to a classical algorithm join-less and CPM-Col， the CPM-iCol algorithm significantly reduces mining time and backtracking times. The results show that the proposed algorithm has better performance and scalability than CPM-Col algorithm， especially in dense datasets.

Key words：spatial data mining; spatial co-location pattern; column calculation; backtracking search

0 引言

空間并置模式挖掘是空间数据挖掘研究的一个重要分支，旨在发现空间特征（事物）之间的关联关系。空间并置模式是空间特征集的子集，这些特征的实例在地理空间中频繁地并置出现［1］。例如，社区附近经常伴随超市，植物茂盛的地方有蚊虫聚集等。空间并置模式挖掘是提取海量的空间数据有用信息和有价值知识的有力工具，在许多应用领域中具有重要作用。在公共卫生方面［2］，空间并置模式可以研究病例与污染物排放间的关联关系；在公共安全方面［3～4］，可以发现城市设施对犯罪发生的影响；在城市建设方面［5～6］，可以对居民区和工厂等合理选址布局提供指导；其他应用领域还包括城市交通规划优化［7］、生态学［8～9］、商业［10］、环境科学［11～12］、农业［13］等。

CPM-Col算法［14］采用逐阶候选-测试框架挖掘空间并置模式。给定空间数据集、距离阈值、频繁度阈值，CPM-Col包括四个步骤（图1）：①基于k-1阶频繁并置模式生成k阶候选模式；②回溯法搜索每个候选模式各个特征的参与实例集；③通过给定的频繁度阈值来测试候选模式是否为频繁模式；④通过迭代生成所有阶频繁的空间并置模式。

尽管通过上述挖掘框架可以正确地生成所有频繁的空间并置模式，但是第②步回溯法搜索模式的参与实例步骤仍非常耗时，尤其在稠密数据集或长模式挖掘中。一般来说，每个候选实例均要启用回溯法搜索行实例来确定其为参与实例，这一过程较耗时，CPM-Col算法提出了实例排序优化策略，剪掉一部分待启用回溯法的候选实例，但是做得不够充分。其利用耗时的回溯法搜索到行实例后，存储这些实例为参与实例就退出搜索，未能物尽其用。

针对上述CPM-Col算法在稠密数据中存在的问题，本文在其算法的两个阶段提出改进：保留CPM-Col在k-1阶搜索到的部分表实例，利用保留的 k-1 阶表实例得出k阶参与实例，减少k阶搜索的次数；利用CPM-Col在k阶搜索到的k个行实例，用行实例的k-1个实例为k阶搜索加速，减少搜索次数。在稠密数据中形成的团实例是极其紧凑的，利用上述改进主要解决了CPM-Col在搜索时每搜索一次k阶实例就要重新启用回溯策略的不足，有效地减少了CPM-Col的搜索次数，因此改进是有效的。

本文的主要贡献如下：

a）存储CPM-Col算法在生成参与实例时搜索到的部分表实例，利用子模式的部分表实例快速得到参与实例，剪掉大量待回溯搜索的候选实例。

b）每搜索完一条完整的行实例后，利用行实例的子团反作用于第一个特征，得到第一个特征的参与实例，避免了这些实例的回溯搜索。

c）在真实数据集和合成数据集上进行了全面的实验，以证明技术的有效性、高效率和可扩展性。

1 相关工作

文献［15］首次提出空间并置模式挖掘的概念，被认为是该领域的第一项工作，提出的join-based算法发现了完整的并置模式集合，但由于采用了全连接操作来收集和验证候选模式的实例，影响了效率。文献［16］提出了部分连接（partial-join）和无连接（join-less）的空间并置模式挖掘算法，partial-join基于团关系划分模型物化邻近关系减少连接的计算，但需要存储被团切断的邻近关系。join-less采用星型邻居划分模型，用实例查找代替实例连接操作，但星型实例不一定满足团关系，还需对团关系进行检查。文献［17］对无连接的空间并置模式进一步研究，提出CPI-tree结构物化邻居关系，深度优先遍历所有模式的表实例，不需要团关系检查，但存储CPI-tree需要大量内存。随后文献［18］改进了CPI-tree算法，以宽度优先遍集区域的实例。Lin等人［19］提出基于行实例扩展的NCA算法，借助每条行实例的邻居结构，将k阶模式的行实例扩展成k+1阶模式的行实例，但该方法需要大量的存储空间。文献［20］提出基于团的并置模式挖掘方法，该方法将搜索到的完备团用C-hash表压缩存储，通过C-hash计算并置模式的频繁度，但完备团的计算是耗时的。文献［21］提出基于极大团划分的方法，将空间数据划分为重叠的极大团，通过组合获得所有候选模式和表实例。基于团的算法虽然避免了逐阶递增候选模式的生成，但需要占用大量空间。文献［22］提出基于网格的空间并置模式算法，将空间分为许多个单元，利用并行编程改进效率，每个进程包含几个小单元的计算任务，但是单元的大小很难设置。文献［23］提出一种利用GPU基于网格的并置模式挖掘算法。文献［24］提出在MapReduce框架上并行挖掘空间并置模式的算法，能有效地处理大量数据，但对环境要求较高。尽管上述工作可以提升表实例生成的效率，但本质上表实例的生成仍然是耗时的。Zou等人［25］引入实例对之间在步长I内相互可达的邻居关系，提出I-可达并置模式，研究了空间数据的最大I-可达并置模式。用［I/2］-可达邻居列表，以二进制的搜索方式快速计算最大I-可达并置模式的參与度。Zhang等人［26］提出了单元关系操作框架，通过对单元的特征进行计数并计算单元的特征重叠率以生成并置模式，突破了传统空间并置模式挖掘以点为实例挖掘的限制。Tran ［27］用元频繁并置模式解决了传统并置模式挖掘中低频繁性阈值挖掘过多冗余模式的问题，设计了基于查询的挖掘算法，在不生成候选的情况下挖掘元频繁并置模式，并且不收集和保留每个模式的实例。文献［28］设计了两级过滤机制，通过特征过滤和相邻实例过滤，将空间实例划分为一组重叠的团，每个团也是并置模式的实例，用并置模式哈希图结构存储表实例，当频繁性阈值改变时，不需要重新收集表实例快速挖掘并置模式。文献［14］提出一种基于列计算的并置模式挖掘算法，它是一种高效的回溯算法，将表实例问题转换为参与实例问题，通过搜索模式的参与实例挖掘并置模式。

本文提出基于列计算的改进算法，利用部分表实例辅助加速参与实例的搜索，快速得到模式中特征的参与实例。

2 相关概念

在空间数据集中，一个空间特征表示一个地理对象类型，特征的空间实例是一个具有位置信息的地理对象。F={f1， f2，…， fm}表示不同特征的集合，每个特征有对应的实例，O={o1，o2，…，on}为所有实例的集合，其中每个实例由一个〈实例编号，特征类型，位置〉三元信息构成。如果用欧氏距离度量两实例间的邻近关系R，则R（o，o′）distance（o，o′），其中distance（o，o′）是两实例间的距离，d是用户给定的距离阈值，可用欧几里德距离。对于实例o，o的邻居集是与o有邻近关系的所有实例集合，记为Neighbor（o）={o′|o′∈O，R（o，o′）}。在o的邻居集中，相同特征f的实例集合称为o在f下的分组邻居集［14］，记为groupN（o，f）={o′|o′∈Neighbor（o），o′.t=f}。如图2（a）中，对于实例A.1，有Neighbor（A.1）={B.3，B.4，C.4}，groupN（A.1，B）={B.3，B.4}。

空间并置模式是一组空间特征F的子集，C={f1，f2，…，fk}，k≥2，CF，C的阶为C中特征的数量［14］。实例集合RI={o1，o2，…，ok}被称为C的行实例，如果：a）RI中任意两个实例满足邻近关系R，也就是RI中的实例形成团关系；b）RI中的实例数量与C的阶数相等，并且RI中的实例覆盖C中的所有特征［14］。模式C的行实例集合称为表实例，表示为table_instance（C）［14］。为了更好地评价并置模式的频繁性，文献［1］提出了参与率和参与度。给定空间并置模式C={f1，f2，…，fk}，C中特征fi的参与率PR定义如下：

其中：N（fi）表示在空间数据集中fi的实例集合；Πfi（table_instance （C））是带冗余消除的投影操作，用于找到表实例中fi不重复实例的集合；||表示集合中元素的个数。参与度即为模式C中各特征参与率的最小值，记为

PI（C）=minki=1（PR（C，fi））（2）

例1 图2（a）中，{A.1，B.3，C.4}是模式{A，B，C}的行实例，因两两满足邻近关系R，且{A.1，B.3，C.4}的实例数量等于模式{A，B，C}的阶数，并且覆盖了模式{A，B，C}的所有特征。

给定一个并置模式C，当PI（C）大于等于给定的最小频繁度阈值min_prev时，称并置模式C是一个频繁并置模式。

例2 图2（a）中，{A，B，C}是一个三阶并置模式，实例集合{A.1，B.3，C.4}是{A，B，C}的一条行实例，模式{A，B，C}的表实例在图2（b）中完整列出，计算了该模式下各个特征的参与率及模式的参与度，PI（{A，B，C}）=3/5=0.6。如果0.6≥min_prev，则{A，B，C}是一个频繁空间并置模式。空间并置模式挖掘旨在发现空间数据集中的所有频繁并置模式。文献［1］已经证明模式的参与度满足反单调性，即对模式C及其超模式C′，CC′，不等式PI（C）≥PI（C′）恒成立。由反单调性得出模式的向下闭合性质可用于模式剪枝，即一个不频繁模式的超模式均不频繁，一个频繁模式的子模式均频繁。

3 改进策略

定义1 参与实例。给定并置模式C，实例o（o.t=f）在C的任一行实例中，则o是C中特征f的参与实例。f在C中的所有参与实例集合称为f在C中的参与实例集，表示为Obj（C，f）［14］。

定义2 候选参与实例集。特征f在k（k>2）阶并置模式C中的候选参与实例集是模式C中所有包含f的k-1阶子模式f的参与实例的交集［14］，记为

定义3 部分表实例。给定一个空间并置模式C，CPM-Col算法搜索到的行实例称为C的部分表实例，记为PT（C）。

例3 图3中，模式{A，B，C}的部分参与实例可以通过其子模式{A，B}的部分表实例得到。利用引理2，S1=groupN（A.2，C）∩groupN（B.1，C）=C.3，S2=groupN（A.3，C）∩groupN（B.2，C）=C.5，S2=groupN（A.4，C）∩groupN（B.2，C）=C.1，由此可确定{A.2，A.3，A.4}、{B.1，B.2}、{C.1，C.3，C.5}分别为模式{A，B，C}中特征A、B、C的参与实例。

由例3可以看出，模式{A，B，C}的子模式有{A，B}，{B，C}，{A，C}，但{A，B}形成的部分表实例最少最精简。因此，在使用引理2时，选用部分表实例数最少的子模式，用更少的代价快速确定参与实例。

CPM-iCol在搜索参与实例时，将模式的特征按参与率上界降序排列，引理3只针对第一个特征求解，因为参与率上界高的特征更有可能与其他特征形成行实例。

例4 图2（a）中，{A.4，B.2，C.3}为模式C={A，B，C}的一条行实例，S=groupN（B.2，A）∩groupN（C.3，A）={A.2，A.4}，可知{A.2，B.2，C.3}是模式C的一条行实例，所以A.2是模式{A，B，C}特征A的参与实例。

實际应用中，实例是错综复杂的，引理3可以通过已知的一条行实例生成多个参与实例。

4 算法及分析

4.1 算法描述

基于引理2、3，本文对CPM-Col算法进行改进，提出CPM-iCol算法（算法1）。第1行计算实例间的邻近关系，物化每个实例在不同特征下的分组邻居集。第2行初始化一阶频繁并置模式。第3～12行从二阶开始，逐阶生成候选模式并判断每个候选模式的频繁性，直到没有频繁模式被找到，最终返回所有的频繁并置模式。第6行isPrevalent（C）是算法的核心。

算法1 CPM-iCol算法

在isPrevalent（C） （算法2）过程中，第1～6行与CPM-Col的剪枝策略一致，计算候选模式C中每个特征参与率的上界，并根据参与率上界（引理1）进行剪枝。如果C不能被剪枝，则第7、8行对C中的特征按照参与率上界降序排序，并初始化每个特征的参与实例集和部分表实例为空，找出包含最少部分表实例的子模式C′。第9行调用SearchPI（C，C′，PT（C′））过程利用子模式C′的部分表实例PT（C′），根据引理2提前确定C的部分候选实例。第10～28行按照排序后的次序遍历每个特征的候选参与实例集CObj（C，f）。对于CObj（C，f）中的实例o，如果o已经在参与实例集Obj（C，f）中，则不需要再验证；否则调用searchRI（o，C）搜索一条包含o和C的行实例RI。如果RI不为空，第15行将RI加入C的部分表实例中，第16行利用RI，根据引理3求得C的第一个特征的参与实例，第17、18行将RI中的每个实例按照特征类型保存到各自的参与实例集中。在搜索完一个特征的所有参与实例后，第25～28行计算该特征的参与率，如果不满足min_prev，则模式C不频繁，并且停止搜索其他特征。如果搜索完C中的所有特征，没有任何特征的参与率小于min_prev，则C是频繁并置模式，isPrevalent（C）返回true。

第13行searchRI（o，C）过程与文献［14］描述一致，使用回溯算法找寻一条包含候选实例o的模式C的行实例，这里不再赘述。下面主要介紹本文的两点改进，即第9行的SearchPI （C，C′，PT（C′））过程和第16行的interact （o，C，RI）过程。

算法2 isPrevalent（C）

算法3使用引理2找寻模式C的各个特征的参与实例。其中，第1行先找出模式C和子集C′相差的特征f′。第2～6行将RI中每个实例在特征f下的分组邻居取交集，第7～9行将实例RI以及S的实例分别加入对应特征的Obj（C， f）中。

算法2第13行已找出实例o在模式C中的一条行实例RI。算法4利用引理3，借助RI找出C的第一个特征f1更多地参与实例。第1、2行先判断o是不是第一个特征f1的参与实例，如果是，第3～9行对RI中除第一个特征f1外的实例o′，取其在f1下分组邻居集groupN（o′， f1）的交集S，则S中的实例为f1在C中的参与实例，将S加入Obj（C， f1）中。

算法3 SearchPI （C，C′，PT（C′））

4.2 算法分析

a）时间复杂度。在算法1中，计算空间邻近关系使用平面扫描等技术，其复杂度小于O（n2）。第3～12行从二阶开始进行挖掘，在第k-1（k≥2）次迭代中，需要搜索的候选模式数量为|Ck|，复杂度即为O（|Ck|）。对于每个候选模式C，调用算法2判断模式的频繁性，isPrevalent（C）算法中，第9～27行是最耗时的，最坏的情况需要遍历所有特征的候选参与实例，复杂度为O（k×（n1）），n1为候选参与实例集CObj（C，f）的最大长度，其中第9行调用SearchPI（C，C′，PT（C′）），需要遍历子模式中具有最小长度的部分表实例PT（C′），复杂度为O（（k－1）×n2），n2是PT（C′）的长度。对每个候选参与实例，第13行调用searchRI（o，C）搜索包含实例o的模式C的一条行实例，最坏情况下需要搜索其他特征实例的所有组合，复杂度为O（nk－13），n3是Oss（o，f，C）的最大长度［14］。第16行interact （o，C，RI），只需要将RI中k-1个实例的分组邻居集取交集，时间复杂度为O（k－1）。借助SearchPI（C，C′，PT（C′））和interact（o，C，RI）的作用，调用searchRI（o，C）实际搜索的组合数将远小于O（nk－13）。综上所述，判断候选模式C频繁性的时间复杂度为O（k×n11×（k－1）×n2+k×n12×nk－13+k×n13×（k－1））。其中n11+n12+n13=n1，n1个候选参与实例中分别有n11、n12、n13个，由SearchPI （C，C′，PT（C′））、searchRI （o，C）、interact （o，C，RI）识别。每轮迭代中k为常数，由于距离阈值和频繁性阈值的约束，需要搜索的模式阶数k不会无限制增长。

b）空间复杂度。CPM-iCol空间耗费主要来自三个方面：（a）每个实例的分组邻居集groupN（o，f），空间耗费为O（|n|×|F|×m1），其中m1为groupN（o，f）的最大长度，保存邻近关系的空间消耗在并置模式挖掘算法中普遍存在；（b）在挖掘k阶模式时，保存k阶频繁并置模式的参与实例集，用来计算候选参与实例集，空间消耗为O（|Pk|×k×m2），Pk是k阶频繁并置模式的数量，m2为参与实例集Obj（C，f）的最大长度；（c）搜索k+1阶模式的参与实例时，需要保存每个k阶模式的部分表实例用于辅助k+1阶模式的参与实例搜索，空间消耗为O（|Pk|×k×m3），其中m3为k阶模式部分表实例的最大长度。k+1阶候选模式搜索完成后，k阶频繁并置模式的参与实例和k阶部分表实例都将被释放。

c）完备性。完备性表示CPM-iCol算法能挖掘到所有的频繁并置模式。算法从二阶开始逐阶测试候选模式的频繁性，生成候选模式的完备性由参与度的向下闭合性保证，因此CPM-iCol算法一定能搜索到所有的频繁并置模式。

d）正确性。算法2分成两阶段计算模式的参与实例，第9行未能识别的参与实例，会在第13、16行中识别，所以没有遗漏任何参与实例的搜索。引理2、3也可以保证正确性。

5 实验结果与分析

5.1 对比算法以及实验环境

实验的对比算法选取了CPM-Col［14］算法和Join-less［16］。CPM-Col采用了回溯算法验证模式中的参与实例，解决了表实例所产生的开销问题，是目前逐阶候选-测试框架中的最优算法。Join-less是应用最广泛的经典算法之一。

本文CPM-iCol和对比算法均使用Python语言编写，实验环境为：Intel CoreTM i5-6300HQ CPU2.30 GHz，16 GB内存，Windows10操作系统。

5.2 实验数据集

本文采用合成数据集和真实数据集。合成数据集实例的坐标范围均为1000×1000，根据需要的特征数量，在坐标范围内不重复地随机生成点，直至满足需要的实例数量。真实数据集采用北京市兴趣点（PoI）数据集（Beijing-PoI）和上海市兴趣点（PoI）数据集（Shanghai-PoI），真实数据集均从谷歌地图中爬取。上述数据集的具体参数如表1所示，其中data-set表示合成数据集。

5.3 实验评估

本文从以下四个方面评估提出的算法：

a）可伸缩性，测试算法在不同数据集和参数上的适应性；

b）空间耗用，测试算法在不同阈值下的空间消耗情况；

c）改进算法效率分析，测试算法的两个改进效果及各个阶段挖掘团关系的情况；

d）算法剖析，测试算法每个步骤的性能。

5.4 可伸缩性

本节测试了实例数量、特征数量、距离阈值、频繁性阈值对CPM-Col、CPM-iCol和Join-less的影响，来验证算法的可伸缩性。前两个实验使用合成数据集测试了实例数量和特征数量对算法的影响。后两个实验使用Beijing-PoI和Shanghai-PoI来测试距离阈值和频繁性阈值对算法的影响。

5.4.1 实例数量的影响

本实验测试了不同实例数量对算法的影响。使用了四个合成数据集data-set1～data-set4进行实验对比，实验数据设置：范围为1k×1k，特征数量为10，距离阈值为25，频繁度阈值为0.8。如图4所示，当实例数量从20k到50k时，可以看出，三种算法的运行时间都随着实例数量的增加而增加，但是CPM-iCol算法运行时间的增长速度小于CPM-Col和Join-less算法，且Join-less算法在实例数量为30 k时，运行时间已经超出了900 s。实验证明在同一个空间范围、不同实例数量下，CPM-iCol算法能有效提高CPM-Col挖掘并置模式的效率。

5.4.2 特征数量的影响

本实验测试了不同特征数量对算法的影响。使用了四个合成数据集data-set5～data-set8进行实验，实验数据设置：范围为1k×1k，实例数量为30k，距离阈值为25，频繁性阈值为0.5。如图5所示：a）当特征数量从10到25时，CPM-iCol和CPM-Col的变化都不明显，CPM-iCol的运行时间小于CPM-Col，因为实例数量较大，Join-less的运行时间超过600 s，就不在图中显示；b）随着特征数量增多，频繁模式的长度和数量与之增加，两个算法时间都呈增加趋势。由于CPM-iCol算法避免了一部分回溯时间，所以运行时间小于CPM-Col。

5.4.3 距离阈值的影响

本实验测试了不同距离阈值下对算法的影响，使用Beijing-PoI和Shanghai-PoI两个真实数据进行实验，频繁性阈值都设置为0.7。图6和7显示了三种算法在Beijing-PoI和Shanghai-PoI两个真实数据集中随距离阈值变化的运行时间。从图中可以看出，CPM-Col和CPM-iCol明显优于Join-less算法；CPM-Col和CPM-iCol两种算法的运行时间都随着距离阈值的增加而增长，当距离阈值较小时，两者運行时间相当，当距离阈值达到400后，CPM-iCol优于CPM-Col，距离阈值越大，能够满足的团关系就越多越紧密，利用引理2、3的效果明显提升。

5.4.4 频繁性阈值的影响

本实验测试了不同频繁性阈值对算法的影响，使用Beijing-PoI和Shanghai-PoI进行实验，距离阈值都设置为400。图8显示了三种算法的运行时间，因Join-less算法在Shanghai-PoI数据中运行时间都超过了1 000 s，所以在图9中不显示Join-less的折线图。显然，CPM-Col、CPM-iCol和Join-less的运行时间随着频繁性阈值的增加而减少。

频繁性阈值决定了频繁并置模式的数量，当阈值较小时，满足条件的模式更多。从图中可以看出，在频繁性阈值同为0.4时，CPM-Col在Beijing-PoI的效果优于本文算法。这是因为在北京PoI的各个特征的实例是比较分散的，参与实例的团关系不紧密，而上海PoI的实例比较密集，参与实例的团关系紧密，利用引理2、3的效果好，所以本文算法更倾向于使用密集的数据。随着频繁性阈值增加，频繁并置模式的数量减少，算法的时间减少是自然的。

5.5 改进算法效率分析

本节分别验证引理2、3的挖掘效率。引理2、3在搜索模式的参与实例时，分别通过子模式的部分表实例和获得的每条行实例快速计算得到参与实例，避免这些实例启动耗时的回溯法搜索。那么，引理2、3能够确定的参与实例越多，搜索过程提速就会越快。本实验在data-set3数据集上运行，距离阈值设置为25。图10分别统计在频繁性阈值min_prev改变时，CPM-iCol算法由回溯法（SearchRI）、 引理2（SearchPI）及引理3（interact）确定的参与实例数占总实例数的比率。

从图10可以看出，引理2（SearchPI）确定的参与实例数大于回溯法，而引理3（interact） 确定的参与实例数与回溯法相当。故引理2的提速效果非常明显，引理3也具有一定程度的提速。

为进一步验证上述结论，继续检验CPM-Col、 CPM-pCol（CPM-Col算法中只引入引理2）和CPM-iCol（CPM-Col算法中引入两个引理）随min_prev变化时的性能，如图11所示。从图中可以看出，相对CPM-Col，CPM-pCol算法性能提升非常大，CPM-iCol算法在此基础上也有较为明显的性能提升。

5.6 算法剖析

本实验测试了CPM-Col和本文CPM-iCol在data-set3上各个步骤的执行时间。参数设置：距离阈值为25，频繁性阈值为0.7。

表2中列出的各个步骤的含义如下：

a）T_gen_neighbor是物化邻近关系所用时间；

b）T_gen_candidates是生成候选模式所用时间；

c）T_gen_partial_table是部分表实例获取参与实例所用时间；

d）T_ gen_obj是回溯法搜索参与实例所用时间；

e）T_interaction是利用回溯法搜索到的行实例快速获取参与实例所用时间；

f）T_total是算法的总运行时间。

两种算法都挖掘出了相同且正确的模式，从表2可以看出，CPM-iCol算法虽然空间耗费上高于CPM-Col，时间上是少于CPM-Col的。CPM-Col是一种回溯搜索算法，使用参与实例机制避免了所有实例的团关系检查，所以CPM-Col的运行时间主要耗费在回溯法搜索参与实例，即表2中第5步。CPM-iCol算法避免所有候选实例都启用回溯法来生成参与实例进行两处改进，体现在表2中的第3、4步。从表2可以看出，CPM-iCol算法第4步的运行时间可以忽略不计，第3、5步的总运行时间之和远小于CPM-Col算法的第5步运行时间。

5.7 實验结果分析

从前面分析已知，每个候选实例均要启用回溯法搜索行实例来确定其为参与实例，这一过程较耗时，回溯搜索行实例是CPM-Col算法最耗时的步骤，尤其当数据集比较稠密时。CPM-iCol算法的两个改进策略正是为避免实例的回溯搜索而提出的。

本节分析两个算法对同一模式{Ad，Ai，Am，As}启用的回溯搜索次数。使用Beijing-PoI数据进行实验对比，实验参数设置：距离阈值为400，频繁度阈值为0.5。对于每个候选实例，确定其为参与实例而启动的行实例回溯搜索的回溯次数往往是不一样的。图12横轴为回溯次数，纵轴为启动此回溯次数的实例数，将每个回溯次数下的实例数求和即为算法在此模式中启动的总回溯次数。本文统计到CPM-Col算法在这个模式中总计启用回溯搜索283次，而CPM-iCol算法在这个模式中总计启用回溯搜索了47次。因此图12表明在此模式中，大量实例由改进策略搜索到，避免了回溯搜索，表明本文方法是有效的。

6 结束语

空间并置模式挖掘因其可以发现空间特征间关联关系而被广泛应用。本文分析了现有CPM-Col算法的效率问题，提出了基于部分表实例和行实例间相互作用的改进措施，加速了参与实例的搜索，并在此基础上提出了CPM-iCol算法。实验结果证明，相对于CPM-Col，CPM-iCol空间占用略高，但具有更好的时间性能。在未来的工作中，考虑根据先验知识保存部分表实例，以优化时空性能。

参考文献：

［1］Huang Yan，Shekhar S，Xiong Hui. Discovering colocation patterns from spatial data sets： a general approach［J］. IEEE Trans on Knowledge & Data Engineering，2004，16（12）： 1472-1485.

［2］Li Jundong，Adilmagambetov A，Jabbar M，et al. On discovering co-location patterns in datasets： a case study of pollutants and child cancers［J］. Geoinformatica，2016，20： 651-692.

［3］He Zhanjun，Deng Min，Xie Zhong，et al. Discovering the joint influence of urban facilities on crime occurrence using spatial co-location pattern mining［J］. Cities，2020，99： 102612.

［4］Li Yan，Shekhar S. Local co-location pattern detection： a summary of results［C］// Proc of the 10th International Conference on Geographic Information Science. 2018： 1-10.

［5］Yao Xiaojing，Jiang Xufeng，Wang Dacheng，et al. Efficiently mining maximal co-locations in a spatial continuous field under directed road networks［J］. Information Sciences，2021，542： 357-379.

［6］Yu Wenhao. Spatial co-location pattern mining for location-based services in road networks［J］. Expert Systems with Applications，2016，46： 324-335.

［7］Cai Jiannan，Deng Min，Guo Yiwen，et al. Discovering regions of anomalous spatial co-locations［J］. International Journal of Geographical Information Science，2021，35（5）： 974-998.

［8］Cai Jiannan，Liu Qiliang，Deng Min，et al. Adaptive detection of statistically significant regional spatial co-location patterns［J］. Computers，Environment and Urban Systems，2018，68： 53-63.

［9］Deng Min，Cai Jiannan，Liu Qiliang，et al. Multi-level method for discovery of regional co-location patterns［J］. International Journal of Geographical Information Science，2017，31（9）： 1846-1870.

［10］Tran V，Wang Lizhen，Chen Hongmei，et al. MCHT： a maximal clique and hash table-based maximal prevalent co-location pattern mining algorithm［J］. Expert Systems with Applications，2021，175： 114830.

［11］Akbari M，Samadzadegan F，Weibel R. A generic regional spatio-temporal co-occurrence pattern mining model： a case study for air pollution［J］. Journal of Geographical Systems，2015，17： 249-274.

［12］Hu Zisong，Wang Lizhen，Tran V，et al. Efficiently mining spatial co-location patterns utilizing fuzzy grid cliques［J］. Information Sciences，2022，592： 361-388.

［13］Liu Qiliang，Liu Wenkai，Deng Min，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.

［14］楊培忠，王丽珍，王晓璇，等. 一种基于列计算的空间并置模式挖掘方法［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］. Science in China： Information Sciences，2022，52（6）： 1053-1068.）

［15］Huang Yan，Shekhar S，Xiong Hui. Discovering colocation patterns from spatial data sets： a general approach［J］. IEEE Trans on Knowledge and Data Engineering，2004，16（12）： 1472-1485.

［16］Yoo J S，Shekhar S，Celik M. A join-less approach for co-location pattern mining： a summary of results［C］// Proc of the 5th IEEE International Conference on Data Mining. Piscataway，NJ： IEEE Press，2005： 4.

［17］Wang Lizhen，Bao Yuzhen，Lu J，et al. A new join-less approach for co-location pattern mining［C］// Proc of the 8th IEEE International Conference on Computer and Information Technology. Piscataway，NJ： IEEE Press，2008： 197-202.

［18］Wang Lizhen，Bao Yuzhen，Lu Zhongyu. Efficient discovery of spatial co-location patterns using the iCPI-tree［J］. The Open Information Systems Journal，2009，3（2）： 69-80.

［19］Lin Zhongshan，Lim S. Fast spatial co-location mining without cliqueness checking［C］// Proc of the 17th ACM Conference on Information and Knowledge Management. New York： ACM Press，2008： 1461-1462.

［20］Bao Xuguang，Wang Lizhen. A clique-based approach for co-location pattern mining［J］. Information Sciences，2019，490： 244-264.

［21］Tran V，Wang Lizhen，Zhou Lihua. Mining spatial co-location patterns based on overlap maximal clique partitioning［C］// Proc of the 20th IEEE International Conference on Mobile Data Management. Pisca-taway，NJ： IEEE Press，2019： 467-47.

［22］He Fei，Deng Xuemin，Fang Jinyun. A fast approach for spatial co-location pattern mining［C］// Proc of IEEE International Geoscience and Remote Sensing Symposium. Piscataway，NJ： IEEE Press，2013： 3654-3657.

［23］Sainju A M，Aghajarian D，Jiang Zhe，et al. Parallel grid-based co-location mining algorithms on GPUs for big spatial event data［J］. IEEE Trans on Big Data，2020，6（1）： 107-118.

［24］Yang Peizhong，Wang Lizhen，Wang Xiaoxuan. A MapReduce approach for spatial co-location pattern mining via ordered-clique-growth［J］. Distributed and Parallel Databases，2020，38： 531-560.

［25］Zou Muquan，Wang Lizhen，Wu Pingping. Efficiently mining maximal L-reachability co-location patterns from spatial data sets［J］. Intelligent Data Analysis，2023，27（1）： 269-295.

［26］Zhang Jinpeng，Wang Lizhen，Tran V. Spatial co-location pattern mining over extended objects based on cell-relation operations［J］. Expert Systems with Applications，2023，213： 119253.

［27］Tran V. Meta-PCP： a concise representation of prevalent co-location patterns discovered from spatial data［J］. Expert Systems with Applications，2023，213： 119255.

［28］Tran V，Wang Lizhen，Zhou Lihua. A spatial co-location pattern mining framework insensitive to prevalence thresholds based on overlapping cliques［J］. Distributed Parallel Databases，2023，41： 511-548.