基于Voronoi图和距离衰减效应的模糊实例空间并置模式挖掘算法

Fuzzy Instance Space Co-Location Pattern Mining Algorithm Based on Voronoi Graph and Distance Attenuation Effect

摘要: 空间并置模式挖掘用于发现一组空间特征，它们的实例在空间中频繁地相互邻近。传统的空间并置模式挖掘过程中，将空间实例抽象成点对象，每个实例对应一个确定位置。然而，规模较大的空间实例有多个重要位置点(如医院、公园入口)，其空间位置因对其入口的认知不同而存在差异，具有模糊性。对于这些模糊实例，本文考虑其重要位置点对该实例规模的贡献，重新定义实例间的邻近度。此外，传统的并置模式挖掘方法忽略了特征实例的空间分布密度以及邻近实例间的邻近程度，采用静态的距离阈值来识别邻近实例。本文考虑特征的分布密度，用Voronoi图自适应提取不同特征的邻近实例，结合邻近实例的距离衰减函数，更加科学地描述实例间的邻近度。提出一种同时考虑模糊实例规模和距离衰减效应的空间并置模式挖掘方法，为实现快速挖掘，设计了极大团和哈希表搜索参与实例的挖掘框架。在真实数据集和合成数据集上进行实验，验证本文的算法可以发现传统空间并置模式挖掘方法所忽略的有意义模式。

Abstract: Space co-location pattern mining is used to discover a set of spatial features whose instances are frequently adjacent to each other in space. In the process of traditional space co-location pattern mining, spatial instances are abstracted into point objects, and each instance corresponds to a definite location. However, large spatial examples have multiple important location points (such as hospital, and park entrance), and their spatial locations are different due to different cognition of their entrances, which is fuzzy. For these fuzzy instances, this paper considers the contribution of important location points to the instance scale, and redefines the proximity between the instances. In addition, the traditional collocation pattern mining method ignores the spatial distribution density of feature instances and the proximity degree between neighboring instances, and uses static distance threshold to identify neighboring instances. In this paper, considering the distribution density of features, Voronoi diagram is used to adaptively extract adjacent instances with different features, and the proximity of adjacent instances is described more scientifically by combining the distance decay function of adjacent instances. In this paper, a space co-location pattern mining method is proposed, which takes into account both the fuzzy instance size and distance attenuation effects. In order to realize fast mining, a mining framework for the participating instances of maximal clique and hash table search is designed. Experiments are carried out on real data sets and synthetic data sets to verify that the proposed algorithm can find meaningful patterns ignored by traditional space co-location pattern mining methods.

1. 引言

空间并置模式挖掘是空间数据挖掘的一个重要分支。从空间数据集中发现频繁空间并置模式就是发现一组空间特征，其实例频繁地相互邻近。例如，在一个城市的兴趣点(POI)数据集中，通过使用频繁空间并置模式挖掘技术，我们发现银行、超市和汽车站这3个特征的实例经常在邻近区域内一起出现，我们就称{银行、超市、汽车站}是一个频繁空间并置模式。频繁空间并置模式挖掘技术可以发现空间数据集中特征之间的内在联系，该技术已经广泛应用于诸多领域，如公共安全、城市规划、商业、交通等基于位置的服务。

传统的空间并置模式挖掘方法将空间实例抽象成点对象，但规模较大的空间实例覆盖面积可能跨越很多实例的邻域，例如医院和花店、药店。因此，对于医院这样具有较大覆盖面积的实例，使用多个入口共同表示此实例更加准确。实际生活中，实例的位置因人们对其入口的认知而不同，具有模糊性。在生活实践中模糊数据普遍存在，数据的边界或概念的定义具有模糊性。比如，“高”和“矮”、“胖”和“瘦”、“远”和“近”等。现有的基于模糊集的空间并置模式挖掘方法用模糊隶属度来表示模糊数据 [1] 。本文使用隶属度集对多个入口隶属于同一模糊实例这一现象给出客观的度量方式，隶属度集为模糊实例不同入口处人流量大小的比例，以此来表示不同位置属于该实例的概率。

此外，传统的空间并置模式挖掘算法需要一个预定义的距离阈值来识别相互邻近的实例。此静态距离阈值方法操作简单，但如果要得到令用户满意的效果，需要用户根据主观经验和数据分布来反复实验寻找合适的阈值。因为不同特征空间分布密度存在差异，以及相同特征在不同区域也可能有不同的空间分布密度。“邻近”是一个相对的概念。例如，同样是位于3000米处的居民，对沃尔玛(空间分布密度小)而言是邻近，而对小区便利店(空间分布密度大)却很远。并且，现有算法忽略了邻近实例间的紧密程度，邻近实例在候选模式上的权重被平等看待，无法挖掘高精度的并置模式。比如距离阈值为100米时，100米处的实例和50米处的实例对于模式的贡献是一样的，这显然是不合理的。

本文综合考虑了模糊实例规模、特征分布密度、邻近实例间的邻近度等因素对空间并置模式的影响，提出了基于Voronoi图和距离衰减效应的模糊实例空间并置模式挖掘方法。本文主要贡献如下：

1) 针对模糊实例规模对空间并置模式影响的问题，运用模糊理论中的隶属度度量同一实例不同入口对该实例位置的贡献，用各入口的隶属度计算实例规模，并将其融入实例间的邻近度计算中。

2) 针对邻近实例间的邻近度对并置模式影响的问题，首先，通过Voronoi图来识别邻近实例；然后，利用距离衰减函数对邻近实例间的邻近度进行更准确的计算。

3) 在真实数据集和合成数据集上实验验证本文的算法可以发现传统空间并置模式挖掘方法所未发现的有意义模式。

本文第二节给出相关工作，第三节介绍相关定义和性质，第四节分析算法流程和详细步骤，第五节展示实验结果和分析，第六节总结全文并讨论下一步工作方向。

2. 相关工作

空间并置模式挖掘算法最初由Shekhar和Huang [2] 提出，是一种使用Apriori策略的基于连接的算法。随后，许多研究人员开发了各种改进算法，并取得了令人满意的结果。其中一些算法，如部分连接算法 [3] 、无连接算法 [4] 、密度聚类算法 [5] 、基于顺序团的算法 [6] 、SGCT算法 [7] 、杨培忠等提出的基于列计算的空间并置模式挖掘方法 [8] 和张绍雪等提出的避免逐阶挖掘的算法 [9] ，专注于提高效率。此后，学者们还提出了带稀有特征数据 [10] 、不确定数据 [11] 、核模式 [12] 和高效用 [13] 的空间并置模式挖掘算法，拓展了数据类型和挖掘目标。

由于空间实例位置及距离远近标定的模糊性，近年来，一些学者致力于模糊数据的空间并置模式挖掘的研究，提出了模糊对象的空间并置模式挖掘方法。文献 [1] 将模糊集与空间并置模式挖掘相结合，提出了模糊对象空间并置模式挖掘的相关定义和定理，并给出具体的算法和相应的剪枝策略。文献 [14] 将模糊实例位置的概念融入到空间并置模式挖掘中，并采用基于网格的距离计算方法来提高挖掘效率。文献 [15] 提出了一种挖掘模糊对象最大并置模式的Mevent-Tree算法。文献 [16] 提出了一种基于非均匀模糊空间对象的层次化并置模式挖掘方法，使得各层数据分布均匀，并将挖掘出的结果分成多层。

传统的空间并置模式挖掘过程中，空间实例被抽象成点对象，每个实例对应一个确定位置。然而，规模较大的空间实例有多个重要位置点(如医院、公园入口)，其空间位置因对其重要位置点的认知不同而存在差异，具有模糊性。对于这些模糊实例，本文考虑其重要位置点对该实例规模的贡献，将实例规模对空间并置模式挖掘中实例间的邻近程度的影响考虑了进来。

以上这些算法都基于静态的距离阈值来获取实例间邻近关系，过于依赖用户经验来寻找合适阈值。为了解决这一问题，一些学者提出了新的方法。例如，Wang和Zhou [17] 提出了一种基于k-最近特征的并置模式算法，其中实例之间的邻居关系取决于最近对象的数量和k值。然而，这些算法在实现之前仍然需要了解接近标准，例如k阈值。为了解决这一限制，已经开发了一些不需要邻近标准的自适应算法。例如，Sundaram等人 [18] 使用Delaunay三角测量来寻找邻近实例。该方法将三角形边连接的节点视为邻居。Qian等人 [19] 提出了一个迭代框架来发现频繁的并置模式。该方法迭代选择有信息的边来构建邻居关系图，直到每个重要的模式都有足够的置信度。基于绝对和相对频繁度，Qian等人 [20] 探索了一种采用k近邻图代替距离阈值发现区域并置模式的分层并置算法。

随着空间并置模式挖掘研究的不断深入，关于距离衰减效应对空间并置模式挖掘的影响得到关注。文献 [21] 指出实例对空间并置模式挖掘的影响会随着距离的增大而不断减少，并且提出一种考虑密度加权距离阈值的挖掘方法。文献 [21] 使用近邻的方法来识别邻近实例，考虑了实例的空间分布特点，但未对特征分布密度加以考虑。文献 [22] 通过Voronoi图对空间数据集的邻近关系进行识别，虽然考虑了特征分布密度，但对实例邻近程度的表达缺乏进一步的划分。本文考虑了实例位置的模糊性，结合Voronoi图与距离衰减函数，共同刻画邻近实例的邻近度，提出了基于Voronoi图和距离衰减效应的模糊空间并置模式挖掘算法。

3. 相关定义和性质

3.1. 相关工作定义和性质

本节介绍空间并置模式挖掘的相关定义和性质。空间特征是指空间中的事物(例如，医院，药店等)。空间特征集是空间中事物的集合，记为 $F=\left\{f_1,f_2,\cdots ,f_n\right\}$ 。空间实例是空间特征在空间中具体位置的表示，记为 $S=\left\{I_1,\cdots ,I_n\right\}$ 。 $I_t$ 是特征 $f_t$ 的空间实例集合， $1\le t\le n$ ，实例表示为〈实例ID，所属特征，实例位置〉。如果两个实例 $o_i$ 和 $o_j$ 之间的距离不大于用户给定的距离阈值d，则称实例 $o_i$ 和 $o_j$ 满足邻近关系R，即 $R\left(o_i,o_j\right)\iff \rho \left(o_i,o_j\right)\le d$ ， $\rho$ 为实例间的欧式空间距离。 $NR\left(o_i\right)=\left\{o_j|R\left(o_i,o_j\right)\wedge f\left(o_i\right)\ne f\left(o_j\right)\right\}$ 是满足邻近关系R的实例 $o_i$ 的邻居集。 $cl=\left(o_1,o_2,\cdots ,o_k\right)$ 为空间中的一组实例，当cl中任意两个空间实例均满足空间邻近关系R时，称cl是一个空间团。当一个空间团不为任意空间团的子集时，称该空间团为一个极大空间团。

Figure 1. Example of a spatial data set

图1. 空间数据集示例

空间并置模式c是空间特征集F的一个子集， $c=\left\{f_1,\cdots ,f_k\right\}\subseteq F$ 。c中的特征数k称为c的阶。一个空间团cl包含了c中所有空间特征，且cl中任意两实例的特征互不相同，则称cl为c的一个行实例，c的所有行实例构成了表实例 $T\left(c\right)$ 。参与率 $PR\left(c,f_i\right)$ 用来衡量特征 $f_i\left(1\le i\le k\right)$ 在模式c中的参与情况， $PR\left(c,f_i\right)=\left|f_i在T\left(c\right)中的不重复实例的个数\right|/\left|f_i的实例总数\right|$ 。空间并置模式c的所有空间特征中参与率的最小值为c的参与度 $PI\left(c\right)$ ，即 $PI\left(c\right)={\min }_{f_i\in c}\left\{PR\left(c,f_i\right)\right\}$ 。当 $PI\left(c\right)$ 不小于给定的频繁性阈值 $\min \text{\_}prev$ 时，称空间并置模式c是一个频繁空间并置模式。

例1. 图1为一个空间数据集示例，该数据集有A、B、C、D四个特征，其实例数分别为3、5、3、2。图中将具有空间邻近关系的实例由实线连接。以模式{A, B, C}为例，其计算过程如下。表实例为 $\left\{\left\{\text{A}.1,\text{B}.3,\text{C}.2\right\},\left\{\text{A}.2,\text{B}.2,\text{C}.3\right\}\right\}$ ， $PR\left\{\left\{\text{A},\text{B},\text{C}\right\},\text{A}\right\}=\left|\left\{\text{A}.1,\text{A}.2\right\}\right|/\left|\left\{\text{A}.1,\text{A}.2,\text{A}.3\right\}\right|=2/3$ ， $PR\left\{\left\{\text{A},\text{B},\text{C}\right\},\text{B}\right\}=\left|\left\{\text{B}.2,\text{B}.3\right\}\right|/\left|\left\{\text{B}.1,\text{B}.2,\text{B}.3,\text{B}.4,\text{B}.5\right\}\right|=2/5$ ， $PR\left\{\left\{\text{A},\text{B},\text{C}\right\},\text{C}\right\}=\left|\left\{\text{C}.2,\text{C}.3\right\}\right|/\left|\left\{\text{C}.1,\text{C}.2,\text{C}.3\right\}\right|=2/3$ ， $PI\left(\left\{\text{A},\text{B},\text{C}\right\}\right)=\min \left\{PR\left\{\left\{\text{A},\text{B},\text{C}\right\},\text{A}\right\},PR\left\{\left\{\text{A},\text{B},\text{C}\right\},\text{B}\right\},PR\left\{\left\{\text{A},\text{B},\text{C}\right\},\text{C}\right\}\right\}=0.4$ 。如果 $\min \_prev$ 小于或等于0.4，则模式{A, B, C}是一个频繁空间并置模式。

为了更合理地度量空间并置模式挖掘中的距离衰减效应，考虑了特征实例分布密度，结合Voronoi图划分的邻近区域来定义一种距离衰减邻近度，细化了邻近实例间的邻近程度。Voronoi图叫泰森多边形或维诺图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形。以空间数据集中某特征的各个实例为生成元构造泰森多边形，所得即为其他特征实例关于该特征实例的Voronoi图。在构造的Voronoi图各个分块区域中的其他特征实例都和该分块区域生成元的特征实例具有邻近关系。

空间实例集I关于特征f的Voronoi划分 $V\left(f\right)$ 是以特征f的实例集为生成元生成Voronoi图，由生成的Voronoi图对空间实例集I的划分称为空间实例集I关于特征f的Voronoi划分 $V\left(f\right)$ 。生成的Voronoi图中各块区域称为Voronoi块。每一Voronoi块中其他特征的实例都与该Voronoi块生成元的特征实例具有邻近关系。Voronoi块中关于该生成元特征f的邻近实例对集为 $P\left(f\right)$ 。

(a) 以特征C的实例为生成元的Voronoi图(b) 以特征D的实例为生成元的Voronoi图

Figure 2. Example of Voronoi partitioning of features

图2. 特征的Voronoi划分示例

例2. 图2(a)是根据所给空间实例集I得到的关于空间特征C的Voronoi划分示例，以特征C的实例集为生成元，生成Voronoi图，得到3个Voronoi块，每个Voronoi块内的其他特征的实例和生成元实例具有邻近关系。Voronoi块中关于生成元特征C的邻近实例对集 $P\left(\text{C}\right)=\left\{\left(\text{C}.1,\text{B}.4\right),\left(\text{C}.2,\text{A}.1\right),\left(\text{C}.2,\text{B}.3\right),\cdots ,\left(\text{C}.3,\text{D}.2\right)\right\}$ 。图2(b)是空间实例集I中关于空间特征D的Voronoi划分示例，以特征D的实例集为生成元得到2个Voronoi块， $P\left(\text{D}\right)=\left\{\left(\text{D}.1,\text{A}.2\right),\left(\text{D}.1,\text{A}.3\right),\cdots ,\left(\text{D}.2,\text{B}.1\right),\left(\text{D}.2,\text{B}.3\right)\right\}$ 。

3.2. 本文工作定义和性质

定义1. 实例间距离衰减邻近度设 $\left(o_i,o_j\right)$ 为具有邻近关系的实例对，该实例对 $\left(o_i,o_j\right)$ 的距离衰减邻近度定义如下：

$D\left(o_i,o_j\right)={\text{e}}^{-\frac{dis{\left(o_i,o_j\right)}^2}{2\left(\max {\left(d\right)}^2\right)}}$ (1)

$dis\left(o_i,o_j\right)$ 表示两实例之间的欧式距离， $\max \left(d\right)$ 表示Voronoi图划分邻近关系基础上邻近实例对的最大距离。 $D\left(o_i,o_j\right)$ 的值域为(0, 1)，两实例越邻近， $D\left(o_i,o_j\right)$ 的值越接近于1。

传统的空间并置模式挖掘过程中，将空间实例抽象成点对象，每个实例对应一个确定位置。然而，规模较大的空间实例有多个重要位置点(如医院、公园入口)，其空间位置因对其入口的认知不同而存在差异，具有模糊性。对于这些模糊实例，本文结合模糊理论使用隶属度集综合考虑隶属于该实例的多个重要位置点对该实例规模的贡献，重新定义实例间的邻近度。隶属度集为模糊实例不同重要位置点处人流量大小的比例，以此来表示不同位置隶属于该实例的概率。

定义2. 模糊实例规模模糊实例表示为一个四元组〈实例ID，所属特征，实例位置，隶属度集〉，其中隶属度集为模糊实例不同入口处人流量大小的比例。给定一个模糊实例 $o_m$ 的隶属度集 $b\left(m\right)=\left(i_1,i_2,\cdots ,i_t\right)$ ，其模糊实例规模定义如下：

$S\left(o_m\right)=t\times \left(1-\frac{\min \left(b\left(m\right)\right)}{\max \left(b\left(m\right)\right)}\right)+0.01$ (2)

其中， $b\left(m\right)=\left(i_1,i_2,\cdots ,i_t\right)$ 中的 $i_j\left(1\le j\le t\right)$ 为第j处入口隶属于模糊实例的概率，其值为该入口人流量占该实例总人流量的比值，t为模糊实例的入口数量。

在实际空间数据集中，入口数量t越多，实例规模往往越大。而具有多个入口的大规模实例，其各入口的人流量往往难以做到非常平均，即 $\min \left(b\left(m\right)\right)$ 和 $\max \left(b\left(m\right)\right)$ 相差较大，此时 $1-\frac{\min \left(b\left(m\right)\right)}{\max b\left(\left(m\right)\right)}$ 较大。0.01为避免当实例只有一个入口或 $\min \left(b\left(m\right)\right)=\max \left(b\left(m\right)\right)$ 时 $S\left(o_m\right)=0$ 。

定义3. 模糊邻近实例对的效用度设 $\left(o_i,o_j\right)$ 为具有邻近关系的模糊实例对，则该模糊实例对 $\left(o_i,o_j\right)$ 的效用度为二者的模糊实例规模均值与距离衰减邻近度的乘积，定义如下：

$SD\left(o_i,o_j\right)=avg\left\{S\left(o_i\right),S\left(o_j\right)\right\}\times D\left(o_i,o_j\right)$ (3)

定义4. 模式行实例中每个实例的效用度给定模式c的一个行实例 $cl\left(c\right)$ ，设 $o_i\in cl\left(c\right)$ ，为特征 $f_i$ 的实例，则空间并置模式c中特征 $f_i$ 的实例 $o_i$ 的效用度为 $SD\left(c,o_i\right)$ 。

$SD\left(c,o_i\right)={\displaystyle \underset{\begin{array}{c}{o}_i,o_j\in cl\left(c\right)\\ o_j.feture=f_j\wedge f_j\in c\backslash \left\{f_i\right\}\end{array}}{\sum }SD\left(o_i,o_j\right)}$ (4)

定义5. 实例规模距离衰减参与率空间特征 $f_i$ 在空间并置模式c上实例规模距离衰减参与率 $SDPR\left(c,f_i\right)$ 表示为特征 $f_i$ 在c的表实例上不重复出现实例的效用度的和与 $f_i$ 所有模糊实例规模和的比。

$SDPR\left(c,f_i\right)=\frac{{{\displaystyle \sum }}_{j=1}^{\left|f_j\right|}\left(SD\left(c,o_j\right)\right)}{S\left(f_i\right)}$ (5)

$\left|f_j\right|$ 表示特征 $f_i$ 在c的表实例上不重复出现实例个数， $S\left(f_i\right)$ 表示特征 $f_i$ 所有实例规模的和， $S\left(f_i\right)={{{\displaystyle \sum }}^{\text{}}}_{i=1}^{\left|f_i\right|}S\left(o_i\right)$ ， $o_i\in f_i$ ， $\left|f_i\right|$ 表示特征 $f_i$ 的总实例个数。

定义6. 实例规模距离衰减参与度空间并置模式 $c=\left\{f_1,f_2,\cdots ,f_n\right\}$ 上的实例规模距离衰减参与度 $SDPI\left(c\right)$ 表示为空间并置模式c上的最小的实例规模距离衰减参与率。

$SDPI\left(c\right)={\min }_{i=1}^n\left\{SDPR\left(c,f_i\right)\right\}$ (6)

例3. 对图1的空间数据集利用Voronoi图重新划分邻近关系得到实例间新的空间邻近关系如图3所示。以空间数据集中不同特征的各个实例为生成元构造多重泰森多边形，所得Voronoi图各个分块区域中的其他特征实例都和该分块区域生成元的特征实例具有邻近关系，利用Voronoi图对原数据集邻近关系进行了重新划分，将多重泰森多边形重新划分后的邻近关系进行取交集操作，即为最终结果。

Figure 3. The proximity relationship of the spatial data set in Figure 1 was divided based on Voronoi diagram

图3. 基于Voronoi图划分图1空间数据集邻近关系

表1为图3中各模糊实例的隶属度集，表2为根据图1中模糊实例的隶属度集利用定义2计算得到各模糊实例规模。表3为实例间距离及根据定义1得到实例间距离衰减邻近度和根据定义3得到邻近实例对的效用度的值。

Table 1. Membership degree set of fuzzy instance in Figure 3

表1. 图3中模糊实例的隶属度集

Table 2. Size of the fuzzy instance in Figure 3

表2. 图3中模糊实例的规模

Table 3. The distance between fuzzy instances, distance attenuation proximity and utility are shown in Figure 3

表3. 图3中模糊实例间距离、距离衰减邻近度及效用度

根据表2、表3所给信息，利用定义5计算实例规模距离衰减参与率 $SDPR\left(c,f_i\right)$ 。候选并置模式 $c_1=\left\{\text{B},\text{C}\right\}$ 中， $SDPR\left(c_1,\text{B}\right)=\left(0.47+0.21+0.34\right)/\left(0.31+0.79+0.35+0.31+0.57\right)=0.43$ ， $SDPR\left(c_1,\text{C}\right)=\left(0.47+0.21+0.34\right)/\left(0.76+0.35+0.79\right)=0.53$ ，那么 $SDPI\left(c_1=\left\{\text{B},\text{C}\right\}\right)=\min \left\{SDPR\left(c_1,\text{B}\right),SDPR\left(c_1,\text{C}\right)\right\}=0.43$ 。同理，二阶模式 $c_2=\left\{\text{A},\text{B}\right\}$ 中的 $SDPI\left(c_2=\left\{\text{A},\text{B}\right\}\right)=\text{min}\left\{SDPR\left(c_2,\text{A}\right),SDPR\left(c_2,\text{B}\right)\right\}=0.49$ ，对于三阶候选模式 $c_3=\left\{\text{A},\text{B},\text{C}\right\}$ ， $SDPI\left(c_3=\left\{\text{A},\text{B},\text{C}\right\}\right)=\min \left\{SDPR\left(c_3,\text{A}\right),SDPR\left(c_3,\text{B}\right),SDPR\left(c_3,\text{C}\right)\right\}=0.62$ 。候选模式 $c_3=\left\{\text{A},\text{B},\text{C}\right\}$ 的实例规模距离衰减参与度为0.62，候选模式 $c_3=\left\{\text{A},\text{B},\text{C}\right\}$ 的传统空间并置模式频繁度量方法使用模式在空间数据集中出现的频率作为参与度，计算其参与度为0.4，说明本文所提算法能够挖掘到传统挖掘方法所忽略的将实例个体规模对于模式参与度的贡献考虑进来后的有意义模式。

引理1. 实例规模距离衰减参与度不满足向下闭合性。

证明：在例3中，二阶模式{B, C}的实例规模距离衰减参与度 $SDPI\left(\left\{\text{B},\text{C}\right\}\right)$ 为0.43，二阶模式{A, B}的实例规模距离衰减参与度为0.49，三阶模式{A, B, C}的实例规模距离衰减参与度 $SDPI\left(\left\{\text{A},\text{B},\text{C}\right\}\right)$ 为0.62。若频繁阈值为0.5，那么模式{B, C}、模式{A, B}不频繁，模式{A, B, C}频繁。低阶模式不频繁而高阶模式频繁，故不满足向下闭合性。

4. 基于极大团和哈希表的挖掘框架

基于引理1，由于本文参与度度量方式不具有向下闭合性质，如果采用逐级搜索挖掘框架，不必要的候选模式不能被有效地剪枝，挖掘效率极低，特别是在数据集密集的情况下。此外，挖掘频繁并置模式的关键是收集模式的行实例，而这一步是最耗时的。因此，缩小候选搜索空间和快速收集行实例是提高挖掘算法效率的关键。本文使用极大团和哈希表的挖掘框架，基于空间实例的邻近关系搜索极大团，存储于双层哈希表中，快速获取模式的参与实例。避免了在生成–测试候选挖掘框架中对每个行实例的邻近关系进行验证。参与实例即出现在模式表实例中各特征的实例。

4.1. 搜索极大团步骤

从空间数据集中生成极大团是NP难问题，需要一种快捷的算法来生成空间数据集中的所有极大团，Bron-Kerbosch算法 [23] 在用于枚举极大团方面效果良好。Eppstein提供了Bron-Kerbosch算法的另一种改进算法 [24] ，该算法对于低退化度的图获得了接近最优的最坏情况的时间耗费。先计算图的退化序列，然后Eppstein递归算法按退化序列顺序选择递归调用中的顶点v，最后对于顺序中的每个顶点v依次计算极大团。所以本文选择该时间耗费更优的算法来获得极大团。

引理2. 如果空间极大团cl是空间并置模式c的一条行实例，则从cl中可以得到模式c及其所有子集的行实例。

证明：假设有空间并置模式c和子集 $c^{\prime }$ ， $c^{\prime }\subseteq c$ 。若极大团cl是c的一条行实例，因cl中任意两实例均邻近，则cl中包含 $c^{\prime }$ 特征的子团 $c{l}^{\prime }$ 是 $c^{\prime }$ 的一条行实例。

由引理2可知，一个模式的行实例，可从它及其超集对应的极大团中获得。模式表实例的计算不再像传统空间并置模式挖掘算法那样，依赖低阶模式的表实例逐阶生成候选并测试。

4.2. 双层哈希表挖掘空间并置模式步骤

本文使用双层哈希表来储存极大团，其形式为 $\left(ke{y}_1,\left(ke{y}_2,valu{e}_2\right)\right)$ ， $ke{y}_1$ 是极大团中实例的空间特征的集合， $ke{y}_2$ 是极大团中每个实例的空间特征， $valu{e}_2$ 是极大团中实例自身。所有极大团中属于相同特征集的实例被分到双层哈希表中的同一个 $valu{e}_2$ 中。给定一个极大团，先检查哈希表中某个 $ke{y}_1$ 与极大团特征组是否相同，若相同则将极大团的特征和实例放入该哈希表的 $\left(ke{y}_2,valu{e}_2\right)$ 中。若不相同，则新建一个节点，将极大团的特征组作为该节点的 $ke{y}_1$ ，极大团的各特征及实例作为该节点的 $\left(ke{y}_2,valu{e}_2\right)$ 。

例4. 图4是基于图1数据集中极大团构建是双层哈希表CIHash的示例，空间极大团 $\left\{\text{A}.2,\text{B}.2,\text{C}.3,\text{D}.1\right\}$ 的键 $ke{y}_1$ 为{A, B, C, D}，值 $valu{e}_1$ 为 $\left\{\langle \text{A},\text{A}.2\rangle ,\langle \text{B},\text{B}.2\rangle ,\langle \text{C},\text{C}.3\rangle ,\langle \text{D},\text{D}.1\rangle \right\}$ ，值 $valu{e}_1$ 中的键 $ke{y}_2$ 分别为{A}、{B}、{C}、{D}，值 $valu{e}_2$ 分别为{A.2}、{B.2}、{C.3}、{D.1}。

Figure 4. Build a two-layer hash table CIHash example based on the maximal clique of the data set in Figure 1

图4. 基于图1数据集中极大团构建双层哈希表CIHash示例

双层哈希表中存储了极大团，如何从哈希表结构中快速查找参与每个模式的参与实例呢？首先，由双层哈希表中的键得到候选模式(即团候选)，然后从并置实例哈希表的值获得候选模式中特征的参与实例，计算参与度。

引理3. 给定一个并置模式c，从c及其超集的键 $ke{y}_1$ 对应的双层哈希表的值 $valu{e}_2$ 中可以搜集到参与c的表实例中每个特征的参与实例。

证明：根据双层哈希表的定义， $valu{e}_2$ 是在模式 $ke{y}_1$ 中属于特征 $ke{y}_2$ 的一组参与实例集。如果模式c恒等于 $ke{y}_1$ ，那么可以从 $valu{e}_2$ 直接获得模式c的参与实例。如果模式c的参与实例是用双层哈希表储存极大团的子集，则模式c的参与实例可以通过查找模式c的超集的键对应的值来获得。

4.3. 算法描述

算法过程：首先调用基于退化的Bron-Kerbosch算法来获取极大团，再将计算得到的极大团放进双层哈希表中存储(Step 1~2)，然后获取双层哈希表中的所有键即候选模式，并将它们存储在集合keyset中(Step 3)。算法执行while循环对候选模式进行检验。在循环中，将keyset按模式大小降序排序(Step 4~5)，取出来第一个键作为并置模式c (Step 6)。查询键为c及其超集的哈希表节点(Step 8)，获取其值放入c的表实例中(Step 9)。然后计算c的实例规模距离衰减效用度(Step 12)。如果c参与度大于给定频繁阈值，将其放在频繁并置模式结果集上(Step 13~14)，生成c的子集并进keyset集(Step 16~17)。最后，将一组频繁并置模式集返回给用户(Step 19)。

4.4. 算法分析

4.4.1. 时间复杂度

算法时间复杂度主要包含极大团物化，候选模式过滤等部分。有学者研究 [24] 表明，顶点个数为n的无向图G中，带轴Bron-Kerbosch算法的最坏运行时间为 $O\left(3^{n/3}\right)$ ，所以基于退化度的极大团挖掘的时间复杂度为 $O\left(km{3}^{k/3}\right)$ 。k为二阶频繁并置模式的退化度，m是特征的数量。用双层哈希表储存极大团的时间复杂度为 $O\left(\left|MC\right|\right)$ ( $\left|MC\right|$ 为极大团集合)。候选模式过滤的时间复杂度为 $O\left(l\times m_{avg}\times 2^m\right)$ ，l是候选模式的数量， $m_{avg}$ 是候选模式的平均长度。

4.4.2. 空间复杂度

本文提出的算法主要空间耗费为哈希结构CIHash和候选模式参与实例的存储。设 $w_{avg}$ 为极大团的平均长度，极大团数量为 $\left|MC\right|$ ，那么哈希结构的存储耗费约为 $O\left(w_{avg}\times \left|MC\right|\right)$ 。所有团候选参与实例的存储耗费约为 $O\left(v_{avg}\times w_{avg}\times \left|MC\right|\right)$ ， $v_{avg}$ 是团候选中参与实例的平均长度。所以本文提出算法的空间耗费约为 $O\left(v_{avg}\times w_{avg}\times \left|MC\right|\right)$ 。

4.4.3. 完备性和正确性

完备性：因为空间实例的邻近关系被极大团完整保存，双层哈希表不会遗漏邻近关系。算法1计算了所有模式的参与度，引理2，引理3确保了算法1完备性，所以本文算法能挖掘到所有频繁空间并置模式。

正确性：由引理3可知，从双层哈希表中可以正确计算模式参与度，算法1可以保证计算的空间并置模式只有参与度满足频繁阈值才被放进结果，所以本文算法挖掘的均为满足频繁阈值的模式。

5. 实验

为了验证本文算法的实际效果和运行效率，将本文提出的算法(算法1)和文献 [4] 提出的传统算法Joinless算法(算法2)在挖掘到的频繁模式数量和运行时间上进行了对比实验。通过实验结果可以得到，我们的算法相比较传统挖掘算法能够挖掘到更多数量的频繁模式且运行时间更短，可以发现传统空间并置模式挖掘方法所忽略的将实例个体规模对于模式参与度的贡献考虑进来后的有意义模式。

本实验算法均使用Python编写，在电脑配置为Win10系统、4GB内存的实验环境上运行获得结果。

5.1. 真实数据集

本实验所使用的真实数据为云南某地区的植被分布数据，该数据集包含9种植物种类，实例数量共有28,783个。在基于频繁阈值和距离阈值变化的情形下，进行对比实验比较两种算法在挖掘到的频繁模式数量和运行时间的结果。图中，蓝色实线表示算法1的运行结果，橙色虚线表示算法2的运行结果。

5.1.1. 频繁阈值min_prev的变化

本节实验参数为在距离阈值d为15 m的情形下，最小频繁阈值在0.45到0.65之间以步长为0.05进行变化的对比实验，比较二者挖掘到的频繁模式数量及运行时间。

图5展示了在距离阈值不变，最小频繁阈值不断增大的情形下，算法1和算法2所能挖掘到的频繁模式数量不断下降，算法1挖掘到的频繁模式数量明显多于算法2，其中在频繁阈值为0.5时差距最为明显。图6展示了在距离阈值不变，最小频繁阈值不断增大的情形下，两算法进行频繁模式挖掘所需要的时间不断减少。频繁阈值影响模式数量的多少，模式的行实例增多，算法2查找表实例耗费时间长，算法1查找参与实例耗费时间短。从图中也可以看出算法1的运行时间明显小于算法2，其中频繁阈值为0.45时差距最为明显。

5.1.2. 距离阈值d的变化

本节实验参数为在最小频繁阈值为0.6的情形下，距离阈值在14 m到18 m之间以步长为1 m进行变化对比实验，比较二者挖掘到的频繁模式数量及运行时间。

图7展示了不同距离阈值下两种算法挖掘到的频繁模式数量的折线图。从图中可以得到在距离阈值为14 m处挖掘到的频繁模式数量相近，随着距离阈值增大，两种算法挖掘到的模式数量不断增多，模式数量差异逐渐增大。图8展示了不同距离阈值下两种算法挖掘算法运行时间的折线图。在距离阈值为14 m处二者运行时间接近，随着距离阈值的增大，邻近实例和极大团的数量增多，两算法的运行时间耗费增大，在距离阈值16 m处之后差距明显。

Figure 5. The effect of frequency threshold on the number of patterns in real data

图5. 真实数据中频繁阈值对模式数量的影响

Figure 6. The effect of frequency threshold on run time in real data

图6. 真实数据中频繁阈对运行时间的影响

Figure 7. The influence of distance threshold on the number of modes in real data

图7. 真实数据中距离阈值对模式数量的影响

Figure 8. The influence of distance threshold on running time in real data

图8. 真实数据中距离阈值对运行时间的影响

5.2. 合成数据集

本节实验使用合成数据的特征数量为10，实例数量总数设定为59,994个，各个特征下的实例数量随机生成。实验对比结果和变化参数如下。

频繁阈值和距离阈值的变化

图9展示了两个算法在频繁阈值逐渐增大的情形下所能挖掘到的频繁模式数量的变化趋势。从图中可以得到，在距离阈值为0.6到0.7时二者的变化趋势都较为平稳，二者的挖掘结果差距明显。随着频繁阈值的增大，挖掘到的模式数量均减少。图10展示了两个算法在距离阈值逐渐增大的情形下所能挖掘到的频繁模式数量的变化趋势。从图中可以得到，在距离阈值为13、14 m处时，两个算法挖掘的模式数量差距相对稳定，而随着距离阈值的增大，算法1挖掘到的模式数量增速明显，而算法2增速缓慢。

Figure 9. The effect of frequency threshold on the number of patterns in synthetic data

图9. 合成数据中频繁阈值对模式数量的影响

Figure 10. The influence of distance threshold on the number of patterns in synthetic data

图10. 合成数据中距离阈值对模式数量的影响

通过本节的实验，可以得到本文的算法相比较传统挖掘算法能够挖掘到传统空间并置模式挖掘方法所忽略的将实例个体规模对于模式参与度的贡献考虑进来后的有意义模式且运行时间更短，在实验结果的折线图上有了清晰的展示。

6. 结束语

本文考虑空间实例的重要位置点(例如公园、医院不同入口)对该实例规模的贡献，重新定义实例间的邻近度。此外，考虑了空间特征分布密度，结合维诺图和距离衰减函数，自适应地确定邻近关系并刻画邻近实例间的邻近度。提出基于维诺图和距离衰减效应的模糊实例空间并置模式挖掘方法。为实现快速挖掘，设计了极大团和哈希表搜索参与实例的挖掘框架。在真实数据集和合成数据集上进行实验，验证本文的算法可以发现传统空间并置模式挖掘方法所忽略的有意义模式。