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

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

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

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 algorithm, 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.