李钧毅, 王丽珍, 陈红梅
云南大学 信息学院, 昆明 650500
收稿日期：2020-09-08
基金项目：国家自然科学基金项目（61966036，61662086）；云南省创新团队项目（2018HC019）
作者简介：李钧毅(1993-), 男, 硕士研究生
通讯作者：王丽珍, 教授, E-mail: lzhwang@ynu.edu.cn

摘要：空间co-location模式是指在空间中相互邻近且频繁出现的空间特征的集合。由于传统的co-location模式挖掘使用单一的距离阈值来定义空间邻近关系，忽略了距离变化对空间邻近关系带来的影响，并且最小频繁度阈值的设定对于没有数据相关专业知识的用户来说存在一定的困难。针对上述问题，该文提出了一种基于模糊理论和d-网格的邻近隶属度计算方法，该方法可以避免计算Euclid距离并且可以利用d-网格快速找到满足模糊邻近关系的极大团，然后结合Top-k思想，挖掘出频繁度最大的k个空间co-location模式。实验结果表明：该方法具有更高效的性能和更细致的计算结果，并且通过比较召回率，发现该方法得到的频繁度最大的k个模式与传统co-location模式挖掘算法得到的频繁度最大的k个模式大部分相同，说明提出的模糊度量和挖掘算法具有较大的实用价值。
关键词：空间数据挖掘空间co-location模式Top-k模糊理论d-网格
dGridTopk-FCPM: A top-k spatial co-location pattern mining algorithm based on fuzzy theory and d-grids
LI Junyi, WANG Lizhen, CHEN Hongmei
School of Information Science and Engineering, Yunnan University, Kunming 650500, China

Abstract: A spatial co-location pattern is a set of spatial features that are frequently observed together in space. Traditional co-location pattern mining uses a single distance threshold to define neighbor relationships while ignoring the impact of distance differences, but the minimum prevalence threshold is difficult to determine for inexperienced users. This paper presents a method for calculating the neighborhood membership degree based on fuzzy theory and d-grids. This method does not calculate the Euclidean distance and quickly finds the maximal cliques that satisfy the fuzzy neighborhood relationship by using the d-grid. The results was then combined with the Top-k algorithm to find the k most prevalent co-location patterns. Tests show that this method is more efficient and gives more detailed results. The recall rate shows that the k most prevalent patterns obtained by this method agree well with those obtained by the traditional co-location pattern mining algorithm, which shows the effectiveness of this fuzzy measurement and mining algorithm.
Key words: spatial data miningspatial co-location patternTop-kfuzzy theoryd-grid
随着科学技术的不断发展，空间数据越来越容易被观测和记录，到了今天，空间数据迅速增长，海量的空间数据等待着被挖掘。空间数据挖掘技术就是在空间数据中发现有趣或潜在有用的模式，而其中一个重要研究方向就是空间co-location模式挖掘。空间co-location模式是一个空间特征的集合，这些特征在空间中相互邻近并且频繁地出现^[1]。比如，车祸现场总是能见到交警。
目前衡量一个co-location模式是否是频繁的，需要用户给定一个最小频繁度阈值。然而对于一些用户来说，可能会因缺乏某些领域的专业知识而对阈值如何设置感到困惑。为了解决这个问题，文[2]给出了一个解决思路，通过返回频繁度最大的k个co-location模式从而让用户不需要设置最小频繁度阈值。
传统的co-location挖掘算法通过一个距离阈值d来定义空间邻近关系，两个物体间的Euclid距离如果≤d，那么它们是邻近的，反之则不然。然而，现实生活中的很多概念是无法精确定义的，而是一个模糊的概念。对于邻近关系这个概念来说，模糊化的度量更为合理。文[3]中模糊邻近关系的提出为这一问题提供了解决思路，运用隶属度将邻近关系模糊化，在距离阈值附近，随着距离的增加而减小实例间的邻近程度，让物体在阈值附近达到一个逐渐脱离关系的效果。模糊化的邻近关系可以使得事物之间的联系更加具有弹性，从而在很多场景中能挖掘出有意义的结果。例如，挖掘不同种类植物之间的共生关系。
本文结合上述内容，提出一种基于网格的模糊邻近关系的计算方法，并利用网格寻找满足模糊邻近关系的极大团来挖掘频繁度最大的k个co-location模式。该方法运用了网格划分的思想，虽然仍需要用户给定一个距离阈值d，但是不同于传统的挖掘算法，本文方法并不是直接依靠d来判断邻近关系，而是进一步利用网格的特点，结合模糊理论，定义了一个邻近隶属度的计算方式。这不但避免了传统挖掘算法在某一个距离处直接切断物体间联系的问题，而且还避免了Euclid距离的计算，提升了挖掘效率。实验结果表明，本文的方法与传统挖掘方法的结果大部分相同，并且有较好的效率。
1 相关工作最早在2001年，文[4]提到了co-location模式的概念，并且给出了最小参与度的概念来度量co-location模式的频繁性，并提出了Join-based算法。自此之后，不断有****对这一研究方向进行了深入研究并提出了各种挖掘算法。文[1]提出了基于星型邻居的无连接算法(Join-less)。文[5]是基于团来挖掘co-location实例，并且提出的方法可以更容易找到理想的频繁性阈值。文[6]提出了一种不需要距离阈值挖掘co-location模式方法。文[7]提出了基于投影的co-location模式挖掘算法，此算法中应用到了FP增长算法求频繁co-location模式，FP增长算法是由Han等^[7]提出的。文[8]提出了一种新的无连接挖掘算法，它是基于CPI-tree的co-location挖掘算法。文[9]提出了iCPI-tree的前缀树结构，加快了co-location表实例的计算。文[10]提出了多种前缀树结构，并讨论了基于有序团的极大频繁co-location模式的挖掘方法。文[2]提出了Top-k闭co-location模式概念和相应的挖掘算法。文[11]提出了一种新的度量方法，该方法不仅能够捕获所有可能的实例，还能够处理实例重叠的情况。文[12]结合了文[9]中提出的iCPI-tree，利用GPU对动态数据库进行co-location模式挖掘。文[13]利用网络距离来取代传统的Euclid距离重新定义邻居关系，并在建立的邻居关系图上挖掘co-location模式。文[14]使用了一种新的方法，利用POI(points of interest)表征城市功能或并置活动模式的城市内部规模结构，并在MapReduce系统上实现并行分布式挖掘。文[15]提出了一种新的兴趣度量方法，用于挖掘空间数据库中的稀有特征。文[16]提出了一种新的方法可以利用多个GPU来提升挖掘co-location的效率。
关于co-location模式挖掘的模糊技术，文[17-18]讨论了模糊对象的空间co-location模式挖掘。文[19]考虑到邻近关系是一个模糊概念，将模糊理论引入co-location模式挖掘中，提出了一种实例之间的模糊空间邻近关系度量方法和一种空间特征之间的特征邻近度量方法。文[20]研究了基于模糊邻近关系的co-location模式挖掘。
本文提出的方法与已有的相关工作不同之处在于：无需计算实例之间Euclid距离，文[19]中需要用户指定两个距离阈值，而本文的方法只需要用户指定一个阈值，文[20]虽然只需要指定一个距离阈值，但是需要用户给定其余更多的参数设定，例如，模糊频繁度阈值和隶属度阈值，并且需要计算Euclid距离，而本文利用Top-k的思想无需用户指定额外的阈值。
2 定义及相关性质本文用到的主要符号的定义见表 1。
表 1 符号定义表

参数	定义
d	用户给定的距离阈值
O	空间实例的集合
o	O中的一个空间实例
o′	O中不同于o的一个空间实例
R	传统邻近关系
F	O中所有实例特征的集合
f	F中的一个特征
I(f)	特征为f的实例的集合
S	O的一个子集
c	一个co-location模式
$\frac{{\sqrt 2 }}{2}d - {\rm{GP}} $	$\frac{\sqrt{2}}{2} d- $网格邻近关系
d-GP	d-网格邻近关系
${{\mathop{\rm grid}\nolimits} _{\frac{{\sqrt 2 }}{2}d}} $	$ \frac{\sqrt{2}}{2} d \times \frac{\sqrt{2}}{2} d$的网格
gridd	d×d的网格
d-SN	d-网格星型邻居
d-CL	d-网格团
d-MC	d-网格极大团

表选项






定义1 ??$\left(\frac{\sqrt{2}}{2} d-\text { 网格邻近关系 }\right) $??如果o和o^′能被$\frac{\sqrt{2}}{2} d \times \frac{\sqrt{2}}{2} d $的网格${\rm{gri}}{{\rm{d}}_{\frac{{\sqrt 2 }}{2}d}}$所包围，那么称它们之间满足$\frac{\sqrt{2}}{2} d- $网格邻近关系$\frac{{\sqrt 2 }}{2}d - {\rm{GP}} $，记为$\frac{\sqrt{2}}{2} d-\mathrm{GP} $(o，o^′)。
例如，图 1中的两个实线正方形都是$ \frac{\sqrt{2}}{2} d \times \frac{\sqrt{2}}{2} d$的网格，被它们所包围的{A1，B1}，{A1，C1}，{B1，C1}，{A3，C3}均满足$\frac{\sqrt{2}}{2} d- $网格邻近关系。

图 1 $\frac{\sqrt{2}}{2} d- $网格邻近和d-网格邻近示例

图选项

定义2?? (d-网格邻近关系)?? 如果o和o^′能被d×d的网格grid_d所包围，那么称它们之间满足d-网格邻近关系d-GP，记为d-GP(o，o^′)。
例如，图 1中的3个虚线正方形都是d×d的网格，{A1，B1}，{A1，C1}，{A1，B2}，{B1，C1}，{B1，B2}，{B2，C1}，{A2，B3}，{A3，B2}，{A3，C3}均满足d-网格邻近关系。注意，虽然{A3，C3}并未在图中用grid_d包围起来，但是它们依然满足d-网格邻近关系，原因是{A3，C3}已经满足了$\frac{\sqrt{2}}{2} d- $网格邻近关系，所以{A3，C3}可以被$ {{\mathop{\rm grid}\nolimits} _{\frac{{\sqrt 2 }}{2}d}}$所包围，那么{A3，C3}也一定可以被grid_d所包围，即{A3，C3}满足d-网格邻近关系。
引理1?? 如果o和o^′不满足d-GP，那么它们也一定不满足$\frac{\sqrt{2}}{2} d- $GP。
证明： (反证法)假设空间实例o和o^′不满足d-GP，但是满足$\frac{\sqrt{2}}{2} d- $GP。由于$ {{\mathop{\rm grid}\nolimits} _{\frac{{\sqrt 2 }}{2}d}}$的边长小于d，因此${{\mathop{\rm grid}\nolimits} _{\frac{{\sqrt 2 }}{2}d}} $能被grid_d所包围。根据假设，因为o和o^′满足$\frac{\sqrt{2}}{2} d- $GP，所以o和o^′能被${{\mathop{\rm grid}\nolimits} _{\frac{{\sqrt 2 }}{2}d}} $所包围，所以o和o^′也能被grid_d所包围，即o和o^′满足d-GP，故与假设矛盾，证毕。
在传统的co-location模式的挖掘中，是通过一个距离阈值d来判断两个实例是否满足邻近关系R，如果o和o^′之间的距离≤d，那么这两个实例满足邻近关系R，记为R(o，o^′)。
引理2?? 如果o和o^′满足$\frac{\sqrt{2}}{2} d- $GP(o，o^′)，那么它们也一定满足R(o，o^′)。
证明：对于${{\mathop{\rm grid}\nolimits} _{\frac{{\sqrt 2 }}{2}d}} $，它的边长为$ \frac{{\sqrt 2 }}{2}d$，在满足$\frac{\sqrt{2}}{2} d- $GP(o，o^′)的条件下，o和o^′之间的最大距离是对角线的距离，即$ \sqrt{\left(\frac{\sqrt{2}}{2} d\right)^{2}+\left(\frac{\sqrt{2}}{2} d\right)^{2}}=d$，因此在该网格内o和o^′之间的距离≤d，所以满足$\frac{\sqrt{2}}{2} d- $GP的两个空间实例也一定满足R，证毕。
引理3 ?? 如果o和o^′不满足d-GP(o，o^′)，那么它们也一定不满足R(o，o^′)。
证明：对于grid_d，它的边长为d，如果两个实例之间不满足d-GP(o，o^′)，o和o^′之间的最小距离必须大于d，所以不满足d-GP的两个空间实例一定也不满足R，证毕。
为了判断是否满足邻近关系, 需要计算它们之间的Euclid距离，这一步是非常耗时的。本文结合模糊理论的概念，再根据定义1、定义2、引理1、引理2和引理3，提出一种不需要计算Euclid距离的邻近隶属度(即实例间邻近程度的度量)计算方法，可以快速计算出两个空间实例之间的邻近隶属度，从而用邻近隶属度来表示它们之间的模糊邻近程度。定义3给出了两个实例间的邻近隶属度的计算函数。
定义3?? (邻近隶属度) 任意两个实例o和o^′之间的邻近隶属度定义为

$\operatorname{PMD}\left(o, o^{\prime}\right)= \begin{cases}\frac{2 d-\Delta x-\Delta y}{(2-\sqrt{2}) d}, & \max \mathit{Δ} <d ; \\ 0, & \max \mathit{Δ} \geqslant d .\end{cases} $

(1)

其中：$\Delta x=\max \left(\left|o . x-o^{\prime} . x\right|, \frac{\sqrt{2}}{2} d\right), \Delta y=\max $$\left(\left|o . y-o^{\prime} . y\right|, \frac{\sqrt{2}}{2} d\right), \max \mathit{Δ} =\max (\Delta x, \Delta y) $。
根据定义3，当满足$\frac{\sqrt{2}}{2} d- $GP时，两个实例间的邻近隶属度是1；不满足d-GP时，两个实例间的邻近隶属度为0。而介于之间的邻近隶属度和两个实例的横坐标(或纵坐标)的差值是负相关的。
邻近隶属度的引入使得实例间的邻近程度与传统co-location模式挖掘中定义的不同(大于d为0，小于或等于d为1)，把实例间的关系在某个阈值d上直接切断，而是在阈值附近，随着距离的增加而减小实例间的邻近程度。
定义4 ??(d-网格星型邻居) 实例o的d-网格星型邻居被定义为$ d-\mathrm{SN}(o)=\left\{\forall o^{\prime} \in O \mid d-\mathrm{GP}\left(o, o^{\prime}\right)\right.$$ \left.\wedge o . f>o^{\prime} \cdot f\right\}$。
其中：o.f和o^′.f表示实例o和o^′的特征；“>”表示特征名的字典序，该条件是为避免星型邻居被重复记录。
显然，对于一个实例o，要得到它的d-网格星型邻居，只需在以实例o为中心，边长为2d的网格grid_2d内搜寻即可，因为grid_2d外的实例与o一定不满足d-网格邻近关系。
例如，图 2中A1位于grid_2d的中心点，{B1，B3，C1}是A1的d-网格星型邻居，即d-SN(A1)={B1, B3, C1}。

图 2 d-网格星型邻居和极大团

图选项

给定一个空间特征f，它的实例集为I(f)，那么特征f的所有实例的d-网格星型邻居可以用 < key, value>的数据结构来记录：

$F - d - {\rm{SN}}(f) = \bigcup\limits_{o \in I(f)} {\langle o,d - {\rm{SN}}(o)\rangle } . $

(2)

定义5 ?? (d-网格团) 如果存在一个O的子集S，并且S中的任意两个实例之间都满足d-GP，则称S是一个d-网格团，记为d-CL(S)。
例如，图 2中{A1，B1，B3}就是一个d-网格团。
定义6 ??(d-网格极大团) 设S是一个d-网格团，如果不存在实例o^′使得S∪{o^′}可以形成d-CL(S∪{o^′})，那么S就是一个d-网格极大团，记为d-MC(S)。
例如，图 2中边长为d的正方形所包围的{A1，B1，B3}就是一个d-网格极大团，但是{A1，B1}不是d-网格极大团，因为存在{A1, B1}∪{B3}可以形成d-网格团。
引理4 ?? 对于任何一个空间实例o∈O，在d-SN(o)内形成的所有d-网格极大团都包含o。
证明：因为在d-SN(o)内的所有实例(除o以外)都与o满足d-网格邻近关系，所以任何一个可以形成d-网格团的集合$S(S \subseteq d-\mathrm{SN}(o)) $中的所有实例都与o满足d-网格邻近关系，所以S∪{o}也是一个d-网格团，也就是说，想要在d-SN(o)内形成一个d-网格极大团，一定包含o，证毕。
定义7?? (模糊参与率) 给定一个k阶的co-location模式c={f₁, f₂, …, f_k}，特征f_i∈c在c中的模糊参与率定义为

$\begin{array}{*{20}{c}}{\mathop{\rm FPR}\nolimits} \left( {c,{f_i}} \right) = \mathop {\min }\limits_{{f_j} \in r - \left\{ {{f_i}} \right\}} \\\left( {\frac{{\mathop \sum \limits_{k = 1}^{\left| {I\left( {{f_i}} \right)} \right|} \left( {\mathop {\max }\limits_{{o^\prime } \in I\left( {{f_j}} \right) \wedge \left\{ {{o_k},{o^\prime }} \right\} \in {\rm{mc}} \wedge {\rm{mc}} \in d \subset - {\rm{MC}}(c)} \left( {{\rm{PMD}}\left( {{o_k},{o^\prime }} \right)} \right)} \right)}}{{\left| {I\left( {{f_i}} \right)} \right|}}} \right). \end{array} $

(3)

其中：I(f_i)和I(f_j)分别为特征f_i和特征f_j的实例集，∣I(f_i)∣表示实例集I(f_i)的实例个数。d-c-MC(c)表示包含模式c的所有d-网格极大团，它是由所有实例特征集包含c的d-网格极大团组成的集合。注意，mc中可能包含某个特征的多个实例。例如模式c={A, B, C}，假设mc={A1, B1, B2, C1, C3}是一个d-网格极大团，那么mc∈d-c-MC(c)，其中mc包含了特征B的两个实例B1与B2。
定义8?? (模糊参与度) 给定一个k阶的co-location模式c={f₁, f₂, …, f_k}，模式c的模糊参与度定义为

${\mathop{\rm FPI}\nolimits} (c) = \mathop {\min }\limits_{{f_i} \in c} \left( {{\rm{FPR}}\left( {c,{f_i}} \right)} \right) $

(4)

为了更直观地说明FPI的计算过程，下面举一个例子。在图 2中，假设I(A)={A1}, I(B)={B1, B2, B3}, I(C)={C1, C2}，特征A与特征B各自空间实例的位置坐标分别为A1(0, 0)，B1(-1, 3)，B2(8, 3)，B3(1, 2)，阈值距离d=5。那么FPI({A, B})=min(FPR({A, B}, A), FPR({A, B}, B))，其中d-c-MC({A, B})={A1, B1, B3}，由于B2距离特征A的空间实例A1太远，无法满足d-GP(A1，B2)，因此不存在包含B2的d-网格极大团。因此，

$\begin{gathered}\operatorname{FPR}(\{A, B\}, A)= \\\min \left(\frac{\max (\mathrm{PMD}(A 1, B 1), \operatorname{PMD}(A 1, B 3))}{|I(A)|}\right)= \\\min \left(\frac{\max (1,1)}{1}\right)=1, \\\operatorname{FPR}(\{A, B\}, B)= \\\min \left(\frac{\max (\operatorname{PMD}(B 1, A 1))+\max (\mathrm{PMD}(B 3, A 1))}{|I(B)|}\right)=\frac{2}{3} 。\end{gathered}$

因此，$\operatorname{FPI}(\{A, B\})=\frac{2}{3} $。
引理5 ??假设模式c^′是模式c的非空真子集，那么FPI(c)≤FPI(c^′)。
证明：因为模式c的d-网格极大团一定存在真子集能对应模式c^′，而模式c^′的d-网格极大团不一定能包含于模式c对应的d-网格极大团，所以模糊参与率是随着模式阶的增大而单调递减的，模糊参与度是取参与率的最小值，也是单调递减的，所以，FPI(c)≤FPI(c^′)，证毕。
定义9?? (Top-k co-location模式) 假设L是一个包含了所有模式的列表，该列表满足：
1) L中的模式按FPI的值降序排序。
2) L中FPI值相同的任何两个模式，如果这两个模式的阶数不同并且存在包含关系，则L中保留阶数大的模式。那么Top-k co-location模式就是L中的前k个模式的集合。
定理1 ??如果低阶模式不在Top-k co-location模式中，那么包含它的高阶模式也不会在Top-k co-location模式中。
证明：?? 根据引理5，定理1显然成立。
3 算法根据定理1，本文采取的思路是先挖掘基于模糊参与度由高至低的2阶Top-k co-location模式，并生成d-网格星型邻居(算法1)，利用得到的d-网格星型邻居搜寻d-网格极大团(算法2)，最后利用d-网格极大团挖掘出包含高阶的Top-k co-location模式(算法3)。
算法1?? L2-Topk-and-d-SN(二阶Top-k co-location模式挖掘与d-网格星型邻居生成算法)。
输入：空间特征集F，距离阈值d，用户给定的模式数量k。
输出： 2阶Top-k co-location模式集L2-Topk和所有特征f∈F的d-网格邻居F-d-SN(f)。
步骤如下：
1. FOR EACH f∈F
??1.1 FOR EACH f^′>f, f^′∈{F－{f}}
??1.1.1计算pi=FPI({f, f^′})；
??1.1.2如果∣L2-Topk ∣ < k，则把{f，f^′}加入到L2-Topk；否则如果pi大于L2-Topk中最小模糊参与度的模式minC，那么用{f，f^′}替换minC；
2. FOR EACH f∈F
??2.1在由特征集$N=\left\{f^{\prime} \mid \forall\left\{f, f^{\prime}\right\} \in \mathrm{L} 2-\right. $$ \text { Topk, } \left.f <f^{\prime}\right\}$中所有特征的实例集共同组成的集合${{\mathop{\rm Ins}\nolimits} _N} = \bigcup\limits_{{f^\prime } \in N} I \left( {{f^\prime }} \right)$中找到F-d-SN(f)；
3. 输出L2-Topk和所有特征f∈F的d-网格邻居F-d-SN(f)。
算法1中，计算FPI({f，f^′})时，可以把公式(3)中的条件$\left\{ {{o_k},{o^\prime }} \right\} \in {\rm{mc}} \wedge {\rm{mc}} \in d - c - {\rm{MC}}(c) $替换成o^′∈d-SN(o)，o和o^′依然满足{o, o^′}∈d-c-MC(c)(第1.1.1步)。对于模式{f，f^′}是否加入到L2-Topk中和L2-Topk的模式数量有关，如果未达到k，那么可以把{f，f^′}直接加入到L2-Topk中；如果达到了k，那么需要判断模糊参与度，如果{f，f^′}的模糊参与度比L2-Topk中模糊参与度最小的模式minC大，则可以用{f，f^′}替换minC(第1.1.2步)。这样循环重复计算后可以得到最大的前k个(可能会小于k)2阶co-location模式。然后根据生成的L2-Topk(因为定理1)，对特征集F中的每一个特征生成d-网格星型邻居(第2步)。
算法2将描述如何在d-SN(o)中寻找全部d-网格极大团。为了便于描述算法2，本文先给出几个定义。
定义10 ??(搜寻行) 如图 3a所示，2d×d的灰色区域(包括边界)就是搜寻行，该搜寻行始终位于以实例o为中心，边长为2d的网格grid_2d内。

图 3 搜寻解释

图选项

定义11?? (判定区及其行搜寻路径) 如图 3b所示，位于搜寻行内的d×d白色正方形区域(包括边界)就是判定区，判定区沿箭头所指的方向就是行搜寻路径。
规定搜寻行下边界的纵坐标是小于上边界的。判定区左边界的横坐标是小于右边界的。
算法2?? Search-d-MC(d-网格极大团搜寻算法)。
输入：需要搜寻的实例o，实例o的d-网格星型邻居d-SN(o)，距离阈值d。
输出：关于实例o的所有d-网格极大团d-MC(o)。
步骤如下：
1. 搜寻行下边界=min{o^′.y∣o^′∈d-SN(o)}, hasNextLine=true；
2. 把集合{o^′∣o^′∈d-SN(o)∧o^′.y≤搜寻行下边界+d}内的实例都加入到newInsList；
3. WHILE hasNextLine==true
??3.1判定区左边界=max(min{o^′.x∣o^′∈newInsList}－d, o.x－d)；
??3.2 $ \mathrm{mc}=\{o\} \cup\left\{o^{\prime} \mid o^{\prime} \in \text { newInsList } \wedge o^{\prime} . x \geqslant\right.$判定区左边界∧o^′.x≤判定区左边界+d}；
??3.3 d-MC (o).add(mc)；
??3.4 WHILE判定区左边界+d≤min(max{o^′.x∣o^′∈newInsList}+d, o.x+d)；
????3.4.1 left=min{o^′.x∣o^′∈newInsList∧o.x≥判定区左边界}；right=min{o^′.x∣o^′∈newInsList∧o.x≥判定区左边界+d}；
????3.4.1.1如果left==right，则把mc={o}∪{o^′∣o^′∈newInsList∧o^′.x≥判定区左边界∧o^′.x≤判定区左边界+d}作为一个d-网格极大团加入到d-MC (o)并把addFlag赋值为false；
????3.4.1.2如果left>right，则把addFlag赋值为true；
????3.4.1.3如果left < right，并且addFlag等于true，则把mc={o}∪{o^′∣o^′∈ newInsList∧o^′.x≥判定区左边界∧o^′.x≤判定区左边界+d}作为一个d-网格极大团加入到d-MC(o)；
??3.5如果addFlag等于true，则把mc＝{o}∪{o^′∣o^′∈newInsList∧o^′.x≥判定区左边界∧o^′.x≤判定区左边界+d}作为一个d-网格极大团加入到d-MC (o)；
??3.6把newInsList赋值为null；
??3.7如果“存在下一个搜寻行nextLine”，则把hasNextLine赋值为true并把新进入到nextLine的所有实例加入到newInsList；否则hasNextLine赋值为false；
4. 输出关于o的d-网格大团d-MC(o)。
算法2中，第1步将d-SN(o)中所有实例纵坐标的最小值作为搜寻行下边界的纵坐标初始值。第2步把搜寻行内实例都加入到newInsList。第3.1步中设置左边界起始位置，是为了减少搜索范围，避免重复搜寻。第3.7步，判断“存在下一个搜寻行nextLine”没有在算法中给出具体的描述，但是可以结合第3.4.1步的思路，把搜寻行所处的区域看作一个纵向判定区，把实例到达纵向判定区的条件对应的换成上边界与下边界，把2d×2d的区域看作搜寻列，向上进行搜寻，如果能满足第3.4.1.1步或第3.4.1.3步中的判断条件，则说明找到了下一个搜寻行的位置，那么赋值hasNextLine为true并停止向上搜索，该纵向判定区就是下一个搜寻行，其中从纵向判定区上边界处进入到纵向判定区的所有实例就是“新进入到nextLine的所有实例”。
注意，这里虽然在图 3a中标出了中心点o，但是实际上算法是基于d-SN(o)来搜寻的，也就是说并不包含实例o在内，所以需要加上o(第3.2步、第3.4.1.1步和第3.4.1.3步)，而第3.7步中的判断过程不需要考虑o。
引理6?? Search-d-MC算法没有丢失在输入的d-SN(o)中能够形成的任何d-网格极大团。
证明：对于任何一个在d-SN(o)中形成的d-网格极大团mc来说，根据算法Search-d-MC中的限制条件，mc-定是位于某一个搜寻行内。假设实例o^′是mc中横坐标值最大的实例，并且mc-{o^′}的这些实例已经位于判定区右边界的左侧(即，在判定区内)。当判定区向右移动直到右边界与o^′重合时(这时的mc位于判定区内)，满足Search-d-MC中的第3.4.1.2步，把addFlag赋值为true；当判定区继续向右移动直到左边界与mc中横坐标值最小的实例重合时，满足Search-d-MC中的第3.4.1.3步，这时该mc被作为一个d-网格极大团被记录下来。如果有多个实例同时到达边界并不影响结果，因为这里讨论的只是横向的位置关系。所以Search-d-MC算法没有丢失在输入的d-SN(o)中能够形成的任何d-网格极大团，证毕。
本文运用Search-d-MC算法对特征f的所有实例o(o∈I(f))的d-SN(o)进行搜寻，得到了关于特征f的所有d-网格极大团，即

${\rm{F}} - d - {\rm{MC}}(f) = \bigcup\limits_{o \in I(f)} d - {\rm{MC}}(o). $

(5)

根据得到的d-网格极大团，便可用算法3挖掘高阶的co-location模式。算法3中需要把所有极大团中对模式c的实例投影进行统计，一个极大团mc对某个模式的投影记为mc_c。假设有一个极大团mc，它的特征集为{A，B，C，D}，表实例如表 2所示，则它对模式c={A, C, D}的实例的投影为阴影部分，记为$ {\rm{m}}{{\rm{c}}_{\{ A,C,D\} }}$。
表 2 极大团的投影

A1	B1	C2	D1
	B2		B3
	C3	D2	D3

表选项






算法3 ??Top-k-Co(Top-k co-location查找算法)。
输入： 2阶Top-k co-location模式集L2-Topk，$ \forall f \in F$的d-网格极大团F-d-MC(f)，特征集F，用户给定的模式数量k。
输出：?? Top-k co-location模式集Top-k-Ps。
步骤如下：
1. prePs=L2-Topk；
??1.1 WHILE ∣prePs∣>0
????1.1.1 canPs=gen-can-pattern(prePs)
????1.1.2清空prePs；
????1.1.3 FOR EACH c∈canPs；
??????1.1.3.1 f_i=c中字典序最小的特征；
??????1.1.3.2 FOR EACH mc∈F-d-MC(f_i)
????????1.1.3.2.1如果c是mc的特征集的子集，则把mc_c加入d-c-MC(c)中；
??????1.1.3.3利用d-c-MC(c)计算pi=FPI(c)；
??????1.1.3.4如果|Top-k-Ps| < k，则把c加入到Top-k-Ps和prePs中；否则如果pi大于Top-k-Ps中最小模糊参与度的模式minC，那么用c替换minC和把c加入到prePs，并且如果prePs中存在minC，则把minC从prePs中删去；
2. 输出Top-k-Ps。
算法3中，用gen-can-pattern()产生更高一阶的候选co-location模式(第1.1.1步)，该方法与Join-less^[1]中由k-阶频繁模式产生(k+1)-阶候选模式的方法相同。然后在关于特征f_i的所有d-网格极大团中寻找模式c的d-c-MC(c)(第1.1.3.2步)。对于模式c是否加入到Top-k-Ps中，判断的情况与算法1中类似，不同在于某些情况下还需要把c加入到prePs中以备后续更高阶的计算(第1.1.3.4步)。
算法复杂性分析：假设用户指定的Top-k co-location模式的数量为k，特征集F的大小是c，总实例数为n。
对于算法1，第1步的时间复杂度为O(n²)，第2步的时间复杂度为O(kn)，所以算法1的时间复杂度$T_{\text {L2-Topk-and-d-SN }}=O\left(n^{2}+k n\right) $。对于数据量大的时候，n $ \gg $k，时间复杂度$ T_{\text {L2-Topk-and-d-SN }} \approx O\left(n^{2}\right)$。
对于算法2，假设一种最坏的情况，即所有的实例都集中在了很小的范围内，例如2d×2d的网格内。那么时间复杂度${T_{{\rm{Search - d}} - {\rm{MC}}}} = O\left( {{n^2}} \right) $，如果对所有点都用算法2计算一遍，算法时间复杂度为O(n³)。但是，实际上数据的分布远远要比假设的稀疏，所以算法2在实际运行的情况下要远比假设的耗时要少。
对于算法3，如果按照算法2假设的最坏情况来分析，算法中最费时的步骤为第1.1.3.3步，即计算FPI，其时间复杂度为O(n⁵)，但是实际上的时间复杂度要小很多，所以$ T_{\text {Top-k-Co }} \ll O\left(n^{5}\right)$。
4 实验在本节实验中，将本文提出的方法与传统的挖掘算法Join-less^[1]和算法Fraction-Score^[11]作比较(Join-less算法是传统的挖掘算法中公认效率最好的算法，Fraction-Score算法采用了不同于传统算法的新度量方式)，由于本文是挖掘Top-k频繁度由高到低的co-location模式，为了便于比较，本文将Join-less算法和Fraction-Score算法改成适应Top-k挖掘的算法Joinless-topk和算法FraSco-topk，本文的算法命名为d-网格Top-k模糊co-location模式挖掘算法(dGridTopk-FCPM)。实验中的硬件环境为2.5 GHz Intel Core i7 CPU、16 GB内存；运行的操作系统为Linux；实验中的算法使用Java实现。
4.1 实验数据集本文的实验采用了真实数据集与合成数据集。其中，真实数据集来源于2018年全国高校数据驱动创新研究大赛，该数据集源自高德地图，由国家信息中心合作企业北京国信宏数科技有限责任公司提供^[21]。由于该数据集的数据量过于庞大，本文提取了2个城市(上海市和昆明市)中的部分POI数据作为实验的真实数据集，数据特征为：{实例的特征，实例的id，实例的位置坐标}，具体的信息如表 3所示。其中，ShanghaiPOI是上海市的POI数据，KunmingPOI是昆明市的POI数据。为验证提出算法的可扩展性，采用与文[1]类似的方法合成了实验数据集，两组合成数据集的数据特征为：{实例的特征，实例的id，实例的位置坐标}。合成数据集组1的相关参数为：空间大小是10 000×10 000，特征数为20，邻近距离阈值取50，频繁阈值取0.3，clumpy=1，overlap=0，然后基于上述参数分别生成实例数为20、40、60、80、100万的合成数据集；合成数据集组2的相关参数：空间大小10 000×10 000，特征数为20，邻近距离阈值取50，频繁阈值取0.3，实例数为30万，overlap=0，然后基于上述参数分别生成clumpy为5、10、15、20和25的合成数据集。这里的clumpy指的是邻近范围内的数据密度。
表 3 真实数据集信息

数据集	特征数	实例个数
ShanghaiPOI	23	218 800
KunmingPOI	23	298 851

表选项






本文用到的所有数据集可以通过网页(https://github.com/stykel/dGridTopk-FCPM)获取。
4.2 挖掘结果比较表 4—6分别是Joinless-topk、FraSco-topk和dGridTopk-FCPM在上海POI数据中当d=50 m，k=30情况下挖掘得到的30个结果中的前5个。可以看到Joinless-topk、FraSco-topk和dGridTopk-FCPM的频繁度最大的3个模式是一样的(顺序上有稍许不同)，在Joinless-topk的结果中频繁度最大的两个模式{生活服务，购物服务}与{购物服务，餐饮服务}在dGridTopk-FCPM中顺序相反，造成这个结果的原因是两个算法的度量方式不同，从而导致挖掘到的结果也不同，而事实上模糊化的度量更为合理。
表 4 Joinless-topk频繁度排序(前5)

模式	频繁度
生活服务，购物服务	0.469
购物服务，餐饮服务	0.467
生活服务，餐饮服务	0.404
交通设施服务，购物服务	0.270
购物服务，通行服务	0.258

表选项






表 5 FraSco-topk频繁度排序(前5)

模式	频繁度
购物服务，餐饮服务	0.267
生活服务，购物服务	0.245
生活服务，餐饮服务	0.162
交通设施服务，购物服务	0.138
地名地址信息，购物服务	0.113

表选项






表 6 dGridTopk-FCPM频繁度排序(前5)

模式	频繁度
购物服务，餐饮服务	0.404
生活服务，购物服务	0.398
生活服务，餐饮服务	0.343
公司企业，金融保险服务	0.226
生活服务，购物服务，餐饮服务	0.214

表选项






4.3 Top-k召回率本文的Top-k召回率是指dGridTopk-FCPM挖掘到的k个模式中与Joinless-topk挖掘到的k个模式中相同的数量除以k。
图 4和5分别是昆明市和上海市的Top-k召回率，k的取值范围是[10, 30, 30, 40]，从两张图中可以看到，无论是在昆明市还是上海市，召回率都在80%以上，并且大部分处于90%以上，通过改变阈值距离d，发现召回率也依然相对稳定，说明d对召回率的影响不大，高召回率也表明：尽管模糊度量细化了邻近关系和参与度，但没有改变高频繁性模式的地位。

图 4 昆明市Top-k召回率

图选项

图 5 上海市Top-k召回率

图选项

4.4 k与时间性能本文采用昆明市POI来分析k和运行时间的关系，图 6是当d分别取40 m和60 m的时候，Joinless-topk算法、dGridTopk-FCPM算法和FraSco-topk算法的运行时间。从图中可以看到，当k值逐渐增大时，3个算法的运行时间也随之增加，但是在距离阈值相同的情况下，dGridTopk-FCPM运行时间最少。该结论在d等于50、70和80 m的时候也适用，并且在上海市的POI数据集上实验得到的结论也是相同的。

图 6 Top-k与运行时间

图选项

4.5 d与时间性能根据图 6中得到实验结果，可以知道k越大的时候运行时间的差距会越大，所以为了得到更明显的对比结果，这里k取40。图 7描述了3个算法在Top-40的时候，距离d与运行时间的变化关系。从图中可以看到，随着d的不断增加，Joinless-topk的运行时间增长速度要明显快于FraSco-topk和dGridTopk-FCPM，并且dGridTopk-FCPM的耗时要少于FraSco-topk。本文方法更快的原因在于：1) 不需要计算Euclid距离，减少了计算复杂性；2) 利用网格可以更为快速地判断实例间是否是一个团(本文定义的团关系)。

图 7 d与运行时间

图选项

4.6 可扩展性本文对Joinless-topk算法、dGridTopk-FCPM算法和FraSco-topk算法进行了可扩展性的实验。
首先是实例数和时间性能的实验，数据使用合成数据集组1，实验结果如图 8所示。可以看到随着实例数的不断增长，运行时间也在不断地增加。其中，随着实例数的增长，FraSco-topk的增速是最快的，dGridTopk-FCPM的耗时比Joinless-topk和FraSco-topk都要少。造成FraSco-topk耗时比Joinless-topk要多的原因是：1) FraSco-topk算法中计算分数部分的耗时要高于Joinless-topk寻找星型邻居的耗时；2) 由于实验对比的结果是Top-k，并且它们都满足向下闭合的性质，因此结果绝大部分都是2阶模式，从而避免了高阶模式的查找，而这也恰好避开了Joinless-topk最耗时的部分。

图 8 实例数与运行时间

图选项

其次是clumpy和时间性能的实验，数据使用合成数据集组2，实验结果如图 9所示。可以看到3个算法受clumpy的影响较小，但仔细分析可以发现，Joinless-topk的受clumpy的影响程度最大，运行时间随着clumpy的增加而小幅度的增加，FraSco-topk受clumpy的影响程度比Joinless-topk要小，而dGridTopk-FCPM受clumpy的影响程度最小。

图 9 clumpy与运行时间

图选项

本文的方法模糊化了邻近关系，比传统的度量方式更为精细，用较为严格的参与率计算方式得到了近似于传统方法的结果。在如今的数据暴增时代，追求在海量数据中挖掘有趣的模式，是需要提高算法效率的，本文的方法为挖掘co-location提供了一种方法。
5 结论由于传统co-location挖掘算法需要计算Euclid距离和生成表实例，会造成大量的时间开销。而本文结合模糊理论，避免了Euclid距离的计算并且利用d-网格快速寻找d-网格极大团，从而挖掘出Top-k co-location模式，从实验中的召回率普遍高于90%和运行时间上的优势综合来看本文提出的模糊度量和挖掘算法有较大的实用价值。在下一步工作中将会继续研究空间模式的更为合理的频繁性度量和更高性能的挖掘算法。

参考文献

[1]	YOO J S, SHEKHAR S, CELIK M. A join-less approach for co-location pattern mining: A summary of results[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1323-1337. DOI:10.1109/TKDE.2006.150
[2]	YOO J S, BOW M. Mining top-k closed co-location patterns[C]//Proceedings of the IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services. Fuzhou, China: IEEE, 2011: 100-105.
[3]	ZADEH L A. Fuzzy sets[J]. Information and Control, 1965, 8(3): 338-353. DOI:10.1016/S0019-9958(65)90241-X
[4]	HUANG Y, SHEKHAR S, XIONG H. Discovering co-location patterns from spatial data sets: A general approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472-1485. DOI:10.1109/TKDE.2004.90
[5]	BAO X G, WANG L Z. A clique-based approach for co-location pattern mining[J]. Information Sciences, 2019, 490: 244-264. DOI:10.1016/j.ins.2019.03.072
[6]	TRAN V, WANG L Z. Delaunay triangulation-based spatial colocation pattern mining without distance thresholds[J]. Statistical Analysis Data Mining: The ASA Data Science Journal, 2020, 13(3): 282-304. DOI:10.1002/sam.11457
[7]	HAN J W, PEI J, YIN Y W, et al. Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas, USA: ACM, 2000: 1-12.
[8]	WANG L Z, BAO Y Z, LU J, et al. A new join-less approach for co-location pattern mining[C]//Proceedings of the 8th IEEE International Conference on Computer and Information Technology. Sydney, Australia: IEEE, 2008: 197-202.
[9]	WANG L Z, BAO Y Z, LU Z Y. Efficient discovery of spatial co-location patterns using the iCPI-tree[J]. The Open Information Systems Journal, 2009, 3(1): 69-80.
[10]	WANG L Z, ZHOU L H, LU J, et al. An order clique based approach for mining maximal co-locations[J]. Information Sciences, 2009, 179(19): 3370-3382. DOI:10.1016/j.ins.2009.05.023
[11]	CHAN H K, LONG C, YAN D, et al. Fraction-score: A new support measure for co-location pattern mining[C]//35th International Conference on Data Engineering. Macao, China: IEEE, 2019: 1514-1525.
[12]	ANDRZEJEWSKI W, BOINSKI P. Parallel approach to incremental co-location pattern mining[J]. Information Sciences, 2019, 496: 485-505. DOI:10.1016/j.ins.2018.09.016
[13]	YU W H. Spatial co-location pattern mining for location-based services in road networks[J]. Expert Systems with Applications, 2016, 46: 324-335. DOI:10.1016/j.eswa.2015.10.010
[14]	MASRUR A, THAKUR G, SPARKS K, et al. Co-location pattern mining of geosocial data to characterize urban functional spaces[C]//2019 IEEE International Conference on Big Data. Los Angeles, USA: IEEE, 2019: 4099-4102.
[15]	YANG P Z, WANG L Z, WANG X X, et al. An effective approach on mining co-location patterns from spatial databases with rare features[C]//20th IEEE International Conference on Mobile Data Management. Hong Kong, China: IEEE, 2019: 53-62.
[16]	ANDRZEJEWSKI W, BOINSKI P. Efficient spatial co-location pattern mining on multiple GPUs[J]. Expert Systems with Applications, 2018, 93: 465-483. DOI:10.1016/j.eswa.2017.10.025
[17]	欧阳志平, 王丽珍, 陈红梅. 模糊对象的空间co-location模式挖掘研究[J]. 计算机学报, 2011, 34(10): 1947-1955. OUYANG Z P, WANG L Z, CHEN H M. Research on spatial co-location pattern mining of fuzzy objects[J]. Chinese Journal of Computers, 2011, 34(10): 1947-1955. (in Chinese)
[18]	OUYANG Z P, WANG L Z, WU P P. Spatial co-location pattern discovery from fuzzy objects[J]. International Journal on Artificial Intelligence Tools, 2017, 26(2): 1750003. DOI:10.1142/S0218213017500038
[19]	LEI L, WANG L Z, WANG X X. Mining spatial co-location patterns by fuzzy technology[C]//Proceedings of the 2019 IEEE International Conference on Big Knowledge. Beijing, China: IEEE, 2019: 129-136.
[20]	WANG M J, WANG L Z, ZHAO L H. Spatial co-location pattern mining based on fuzzy neighbor relationship[J]. Journal of Information Science and Engineering, 2019, 35(6): 1343-1363.
[21]	国家信息中心. 高德地图兴趣点POI (Point of Interest)数据[DS/OL]. (2018-11-16). https://doi.org/10.18170/DVN/WSXCNM. State Information Center. Map POI (Point of Interest) data[DS/OL]. (2018-11-16). https://doi.org/10.18170/DVN/WSXCNM. (in Chinese)