云南大学信息学院，云南 昆明

收稿日期：2020年12月27日；录用日期：2021年1月21日；发布日期：2021年1月28日

摘要

空间并置(co-location)模式挖掘旨在发现空间中频繁在一起出现的空间特征的子集。空间并置模式中有一类模式其特征的地位是不平等，发现含主导特征的并置模式可以为实际应用提供更为精准的决策支持。由于单一的邻近距离阈值判定两个空间实例间的邻近性会导致邻近关系的缺失，因此，本文首先定义空间实例间的模糊邻近关系，然后定义模式中特征的模糊影响度和模糊影响比识别含主导特征的并置模式；其次，提出基于模糊邻近关系的含主导特征的并置模式挖掘算法及算法优化策略；最后，在合成数据集和真实数据集上验证了算法的正确性和有效性，并在真实数据集上对挖掘结果的实用性进行了比较和分析。

关键词

空间数据挖掘，空间并置模式，模糊邻近关系，主导特征，主导特征模式

Mining Spatial Collocation Patterns with Dominant Features Based on Fuzzy Neighborhood Relationship

Shi Feng, Lizhen Wang, Yuan Fang

School of Information, Yunnan University, Kunming Yunnan

Received: Dec. 27^th, 2020; accepted: Jan. 21^st, 2021; published: Jan. 28^th, 2021

ABSTRACT

Spatial co-location pattern mining aims at mining the collection of spatial features that are frequently occurring together in a space. There is a kind of pattern in spatial co-location patterns whose feature position is inequality. Finding co-location patterns with dominant features can provide more accurate decision support for practical applications. A single distance threshold determines the neighborhood relationship between two spatial instances could lead to a lack of the neighborhood relationship. So, firstly, a fuzzy neighbor relation between spatial instances is defined, and then the fuzzy influence degree and influence ratio of the features in a co-location pattern are defined to identify the co-location pattern with dominant features. Secondly, based on fuzzy neighborhood relationship, a mining algorithm and an optimization strategy of co-location patterns with dominant features are proposed. Finally, the correctness and effectiveness of the algorithm are verified on the synthetic and real data sets, and the practicability of mining results on the real data sets is compared and analyzed.

Keywords:Spatial Data Mining, Spatial Co-Location Pattern, Fuzzy Neighborhood Relationship, Dominant Feature, Dominant Feature Pattern

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着基于位置服务(LBS)、全球定位系统和移动电子设备的快速发展，带有空间位置信息的数据急速增长，产生了大量的空间数据 [1]。空间数据挖掘旨在从海量、高维的空间数据中挖掘潜在有用的和有价值的信息 [2]。空间并置(co-location)模式挖掘作为空间数据挖掘的一个重要研究方向，在环境保护 [3]、城市计算 [4]、公共交通 [5] 等领域具有重要和广泛的应用。空间并置模式是一组空间特征的子集，它们的实例在邻域内频繁并置出现。例如，医院附近往往存在药店和花店，根瘤菌往往长在豆科植物旁等等。

传统的空间并置模式挖掘一般采用最小参与率(参与度)度量，即用一组空间特征的实例在邻域中共同出现的频率衡量其模式的有趣程度 [6]。然而，基于参与度的频繁并置模式挖掘框架无法得到模式中特征的主导关系。识别空间并置模式中特征之间的主导关系，可以更好地为空间并置模式挖掘的实际应用提供决策支持。例如在植被数据上挖掘出的{松树，杉树，松茸}是一个频繁空间并置模式，其参与度可以很好地反映出该特征 [7] 组共现的强度，但参与度信息不能体现“松茸”的生存受到“松树”和“杉树”的影响，即在这个模式中“松树”和“杉树”是这个模式的主导特征。在植物分布分析和应用研究中，尽管挖掘出的频繁并置模式可以发现共生的植物物种关系，但是为了进一步研究植物群落和分布的结构和特征，挖掘出含主导特征的空间并置模式可以为植物学家提供更丰富的信息。另外，含主导特征的并置模式挖掘也可以为商业选址和主导设施的建立提供重要的方向和信息。然而，目前提出的含主导特征的空间并置模式挖掘方法没有考虑到空间特征实例的邻近关系是一个模糊的概念，用单一的邻近距离阈值确定两个空间实例的邻近关系会造成邻近关系的缺失；另外，在定义模式中特征贡献度和影响度时也没有考虑到贡献和影响程度的模糊性。

基于以上思考，本文将实例的邻近关系作为模糊概念定义了模糊邻近关系，基于此定义了实例的模糊行实例贡献度、实例的模式贡献度、模糊影响度和模糊影响比等重要概念，提出基于模糊邻近关系的含主导特征的空间并置模式挖掘问题。并针对以下两方面的挑战：1) 如何将模糊邻近关系引入到空间并置模式中并度量特征间主导关系；2) 如何基于模糊邻近关系提出高效地挖掘含有主导特征的空间并置模式算法，进行研究。主要贡献包括：

1) 基于模糊集理论给出模糊邻近关系的定义，分析所给出的模糊邻近关系具有的性质。

2) 定义实例的模糊贡献度以度量实例在模式中的贡献程度，并基于此定义模糊影响度和模糊影响比以度量特征在模式中的影响(主导)程度。

3) 设计了含主导特征的空间并置模式挖掘算法DFMAFPR和优化算法DFMAFPR-Improved，并在合成数据集和真实数据集上进行大量的实验，验证算法的有效性。

2. 相关工作

空间并置模式挖掘在Huang [8] 等人的文献中针对确定数据提出了一个基于完全连接的经典算法(称为join-based算法)。为提高挖掘效率，各种改进算法如基于星型邻居物化的Join-less算法 [9]、基于前缀树物化的CPI-tree算法 [10] 和iCPI-tree算法 [11]、基于有序团物化的order-clique-based算法 [12] 等相继被提出。针对不确定数据，Wang等提出了概率频繁空间并置模式挖掘算法 [13] [14]，区间数据上的空间并置模式挖掘算法 [15]。针对模糊数据，文献 [16] 提出了模糊参与率和模糊参与度概念，设计了有效的模糊空间并置模式挖掘算法；文献 [17] 通过将模糊理论和密度峰值聚类算法相结合，通过聚类对空间数据进行分类，并采用模糊团的概念挖掘并置模式；文献 [18] 基于模糊理论定义了特征邻近度并采用模糊聚类算法挖掘并置模式。针对带约束的空间数据，文献 [19] 提出了最大参与率概念并设计了maxPrune算法挖掘带有稀有特征的并置模式；文献 [20] 针对maxPrune算法的问题提出了最小加权参与率更有效地挖掘带稀有特征的并置模式。针对含主导特征的空间并置模式挖掘问题，文献 [21] 通过计算模式特征在频繁模式及其子模式的特征参与率变化来判断特征在模式中的影响程度 [22]，并根据模式中特征之间的影响度差异定义了特征差异度作为特征在模式中的主导程度的度量指标来识别含主导特征的co-location模式及其主导特征。然而，现有的主导特征模式挖掘算法没有考虑到空间邻近关系的模糊性 [23]，主导特征模式在挖掘实际交通中交通堵塞问题 [24] 时会造成邻近关系的缺失 [25]，在计算频繁并置模式时会丢失一些有价值的模式，继而在挖掘主导特征时挖掘不到一些有参考价值的特征。

本文在传统并置模式主导特征挖掘方法基础上，考虑空间特征实例间的模糊邻近关系，研究了基于模糊邻近关系的含主导特征并置模式挖掘问题。

3. 相关定义

空间并置模式 [1]：给定一个空间特征集 $O=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_n\right\}$，对应空间实例集合 $S=S_{\text{1}}\cup S_{\text{2}}\cup \cdots \cup S_n$，其中S_i是特征o_i (1 ≤ i ≤ n)的实例集合，以及距离阈值d。如果两个实例s_i, s_j Î S的欧几里得距离小于等于距离阈值d，则称两个实例满足邻近关系R，即R(s_i, s_j)。一个空间特征集O的k阶子集 $c=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$ ( $c\subseteq O$,$k=\left|c\right|$ )称为k阶并置模式。为衡量c的频繁程度，引入模式的行实例和表实例：若实例集 $I=\left\{s_{\text{1}},s_{\text{2}},\cdots ,s_k\right\}$ ( $I\subseteq S$ )包含c中所有特征且I中的任一子集都不包含c的所有特征，并且I在邻近关系R下形成团关系，则称I为c的一个行实例，记为R(c)，c的所有行实例组成c的表实例，记为T(c)。

在空间并置模式中特征的参与率PR(c, o_u)定义为模式c中特征o_u的实例在c的表实例中不重复出现的个数与o_u总实例个数之比，即

$PR\left(c,o_u\right)=\frac{\left|{\pi }_{o_u}\left(T\left(c\right)\right)\right|}{\left|T\left(o_u\right)\right|}$ (1)

其中p是关系的投影操作。

模式c的参与度PI(c)定义为模式c中所有特征参与率的最小值，即

$PI\left(c\right)={\min }_{u=1}^k\left\{PR\left(c,o_u\right)\right\}$ (2)

给定参与度阈值min_prev，当PI(c) ≥ min_prev，则称模式c为频繁并置模式。

如图1所示，图中有三个空间特征A、B和C，设距离阈值d = 100，参与度阈值min_prev = 0.3，则实例A₁和B₁满足邻近关系R(A₁, B₁)，模式{A, B, C}的表实例 $T\left(\left\{\text{A},\text{B},\text{C}\right\}\right)=\left\{\left\{{\text{A}}_{\text{1}},{\text{B}}_{\text{1}},{\text{C}}_{\text{2}}\right\},\left\{{\text{A}}_{\text{3}},{\text{B}}_{\text{2}},{\text{C}}_{\text{3}}\right\},\left\{{\text{A}}_{\text{4}},{\text{B}}_{\text{4}},{\text{C}}_{\text{2}}\right\}\right\}$，模式{A, B, C}的参与度为 $PI\left(\left\{\text{A},\text{B},\text{C}\right\}\right)=\text{min}\left(0.\text{43},0.\text{5},0.\text{5}\right)=0.\text{42}$，则模式{A, B, C}是一个频繁并置模式。

定义1 模糊邻近关系(FNR)：以空间实例集S中两两实例间的欧氏距离D作为论域 $D=\left[0,\infty \right)$，模糊邻近关系(FNR)是基于距离D的邻近关系的集合。空间任意两个实例s_i和s_j间的欧氏距离记为d，给定下面映射关系：FNR: D  [0, 1], d  µ(s_i, s_j)，则称µ确定了D上的一个模糊子集FNR，µ为FNR的隶属函数，µ(s_i, s_j)为距离d对FNR的隶属度，也称邻近度。空间实例集S中的任意两个实例s_i和s_j的模糊邻近关系FNR表示为：

$\text{FNR}=\left\{\mu \left(s_i,s_j\right)|s_i,s_j\in S\right\}$ (3)

给定用户自定义距离阈值d₁, d₂，其中µ(s_i, s_j)定义为：

$\mu \left(s_i,s_j\right)=\{\begin{array}{ll}1,\hfill & d\le d_1\hfill \\ 1-\frac{d-d_1}{d_2-d_1},\hfill & d_1<d\le d_2\hfill \\ 0,\hfill & d>d_2\hfill \end{array}$ (4)

例1：空间特征A、B和C的实例分布如图1所示，给定距离阈值d₁ = 100, d₂ = 300，选取任意两个空间实例A₁和B₁，假设A₁和B₁的欧式距离dist(A₁, B₁) = 140，则A₁和B₁的模糊邻近度µ(A₁, B₁) = 0.8。

图1. 空间特征及其实例分布

定义2 FNR的α-截集：给定用户自定义的邻近度阈值α，模糊邻近关系FNR的α-截集FNR_α定义为实例s_i和s_j邻近度µ (s_i, s_j)不小于α的FNR的子集，即

${\text{FNR}}_{\alpha }=\left\{\mu \left(s_i,s_j\right)|s_i,s_j\in S,\mu \left(s_i,s_j\right)\ge \alpha \right\}$ (5)

其中µ(s_i, s_j) ≥ α表示为实例s_i和s_j满足α邻近关系，也可表示为µ_α (s_i, s_j)。

例2：给定邻近度阈值α = 0.1, A₁和B₁的邻近度为0.8，那么空间实例A₁和B₁满足α邻近关系，即µ_0.1(A₁, B₁)。

基于模糊邻近关系的并置模式c的一个模糊行实例FR是空间实例集，即FR Í S。FR具备以下特征：1) 在a邻近关系下形成团；2) FR包含了模式c中的所有特征；3) 没有任意一个FR的子集可以包含c中所有的特征。模式c的模糊表实例是所有模糊行实例的集合，记为 $FT\left(c\right)=\left\{F{R}_{\text{1}},F{R}_{\text{2}},\cdots ,F{R}_m\right\}$。

例3：如图1空间实例集中，{A₁, B₁, C₂}是并置模式{A, B, C}的一个模糊行实例，模式{A, B, C}的模糊表实例为 $\text{FT}\left(\left\{\text{A},\text{B},\text{C}\right\}\right)=\left\{\left\{{\text{A}}_{\text{1}},{\text{B}}_{\text{1}},{\text{C}}_{\text{2}}\right\},\left\{{\text{A}}_{\text{3}},{\text{B}}_{\text{2}},{\text{C}}_{\text{3}}\right\},\left\{{\text{A}}_{\text{4}},{\text{B}}_{\text{4}},{\text{C}}_{\text{2}}\right\}\right\}$。

定义3 模糊星型邻居(FSN)：给定一个度量实例模糊邻近关系的隶属函数m，一个空间实例s，它的特征类型是 $o\in O$，实例s的模糊星型邻居定义为它本身和其所有特征类型大于它的模糊邻居的邻近度大于等于α的空间实例的集合，即

$\text{FSN}\left(s\right)=\left\{\left(s_i|=s\vee \mu \left(s,s_i\right)\ge \alpha \right)\right\}$ (6)

其中，s称为中心实例。

根据图1中空间实例分布及实例间模糊邻近度，可以列出如图2的空间特征A和B的实例的模糊星型邻居集。

图2. 图1中特征A, B的星型邻居集

传统并置模式挖掘中，使用模式中特征参与率的最小值作为模式的参与度，进而来衡量模式的频繁性。在频繁模式的一个行实例中两两实例都满足距离阈值d，某一个特征的一个实例在模式中的参与率的贡献为“1”。没有出现在行实例中的实例贡献为“0”。但是实际中，实例对于特征参与率的贡献是一个模糊的概念，为此，引入下面实例的模糊行实例贡献度和实例的模式贡献度概念。

定义4 实例的模糊行实例贡献度：给定一个k阶并置模式c，及其模糊表实例 $FT\left(c\right)=\left\{F{R}_{\text{1}},F{R}_{\text{2}},\cdots ,F{R}_m\right\}$，其任一模糊行实例 $FR=\left\{s_{\text{1}},s_{\text{2}},\cdots ,s_k\right\}$ ( $FR\in FT\left(c\right)$ )，对于FR中的任一实例 $s_i\in FR$，s_i在模糊行实例FR中的贡献定义为s_i与FR中其它实例之间的模糊邻近度的最小值，即

$FR\text{\_Contri}\left(FR\text{,}{s}_i\right)=\underset{s_j\in FR,i\ne j}{\text{Min}}\left(\mu \left(s_i,s_j\right)\right)$ (7)

由于空间的连续性，相同的实例往往会参与在不同的行实例中，因此出现在多个模糊行实例中的同一实例将出现多个贡献度，为此，我们给出实例的模式贡献度。

定义5 实例的模式贡献度：给定一个k阶并置模式c及其模糊表实例 $FT\left(c\right)=\left\{F{R}_{\text{1}},F{R}_{\text{2}},\cdots ,F{R}_m\right\}$，对任一实例 $s_i\in FT\left(c\right)$，s_i在 $FT\left(c\right)$ 中所属行实例集定义为 $FT\_s_i\left(c\right)=\left\{F{R}_1,F{R}_2,\cdots ,F{R}_h\right\}$ ( $m\le h$,$FT\_s_i\left(c\right)\subseteq FT\left(c\right)$ )，则s_i对模式的贡献度定义为s_i对其所属模糊行实例的贡献的最大值，即：

$Contri\left(FT\left(c\right),s_i\right)=\underset{FR\in FT\_s_i\left(c\right)}{\text{Max}}\left(FR\_Contri\left(FR,s_i\right)\right)$ (8)

例4：图1中并置模式{A, B, C}的模糊行实例{A₁, B₁, C₂}中实例C₂的模糊行实例贡献度为 $FR\_Contri\left(\left\{{\text{A}}_1,{\text{B}}_1,{\text{C}}_2\right\},{\text{C}}_2\right)=\min \left\{m\left({\text{A}}_1,{\text{C}}_2\right),m\left({\text{B}}_1,{\text{C}}_2\right)\right\}=\min \left\{0.8,1\right\}=0.8$。实例C₂的模式贡献度为 $Contri\left(\left\{\left\{{\text{A}}_{\text{1}},{\text{B}}_{\text{1}},{\text{C}}_{\text{2}}\right\},\left\{{\text{A}}_{\text{4}},{\text{B}}_{\text{4}},{\text{C}}_{\text{2}}\right\}\right\},{\text{C}}_{\text{2}}\right)=\text{Max}\left\{0.\text{8},0.\text{5}\right\}=0.\text{8}$。

相对于传统并置模式的参与率和参与度，基于实例在模糊行实例中的贡献定义模糊参与率和模糊参与度以衡量模式的频繁性。

定义6 模糊参与率(FPR)和模糊参与度(FPI)：给定一个并置模式 $c=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$，其空间特征 $o_i\in c$ (1 ≤ i ≤ k)的模糊参与率定义为o_i参与在c中的所有实例对模式的贡献度之和与其总实例个数的比率，即

$FPR\left(c,o_i\right)=\frac{{\displaystyle \sum Contri\left(FT\left(c\right),s_i\right)}}{\left|FT\left(\left\{o_i\right\}\right)\right|},\left(s_i\in FT\left(c\right)\right)$ (9)

模式 $c=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$ 的模糊参与度(FPI)是模式c中所有特征的模糊参与率最小值，即

$FPI\left(c\right)=\underset{1\le i\le k}{\text{min}}\left\{FPR\left(c,o_i\right)\right\}$ (10)

给定一个用户自定义的最小模糊参与度阈值min_fprev，对于任何一个模式c，如果FPI(c) ≥ min_fprev，则模式c是一个模糊频繁并置模式。

例5：图1通过计算特征A, B, C在模式{A, B, C}中的模糊参与率分别为： $FPR\left(\left\{\text{A},\text{B},\text{C}\right\},\text{A}\right)=\left(0.\text{8}+0.\text{8}+0.\text{5}\right)/\text{7}=0.\text{3}$,$FPR\left(\left\{\text{A},\text{B},\text{C}\right\},\text{B}\right)=0.\text{37}$,$FPR\left(\left\{\text{A},\text{B},\text{C}\right\},\text{C}\right)=0.\text{4}$，所以模式 $FPI\left(\left\{\text{A},\text{B},\text{C}\right\}\right)=\text{min}\left(0.\text{33},0.\text{37},0.\text{58}\right)=0.\text{3}$。

定义7 模糊损失率(FLR)与模糊损失度(FLI)：给定一个频繁并置模式 $c_k=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$ (k > 2)及其c_k的一个k − 1阶子模式c_k−1，对于c_k−1及c_k中的任意一个特征o_i (o_i Î c_k−1 & o_i Î c_k)，o_i由c_k−1到c_k的模糊损失率定义为：

$FLR\left(c_{k-\text{1}}\text{,}{c}_k\text{,}{o}_i\right)=FPR\left(c_{k-1},o_i\right)-FPR\left(c_k,o_i\right)$ (11)

模式由c_k−1到c_k的模糊损失度是c_k−1中的特征到c_k的模糊损失率的最小值

$FLI\left(c_{k-\text{1}}\text{,}{c}_k\right)=\text{min}\left\{FLR\left(c{}_{k-\text{1}}\text{,}{c}_k\text{,}{o}_i\right)\right\}\text{,}{o}_i\in c_{k-1}$ (12)

模式c_k−1到c_k的模糊损失度 $FLI\left(c_k{}_{-\text{1}},c_k\right)$ 表示模式c_k−1中不与特征 $o_k\left(o_k=c_k-c_k{}_{-\text{1}}\right)$ 的实例满足邻近度阈值α的团实例的数量，当特征 $o_k\left(o_k=c_k-c_k{}_{-\text{1}}\right)$ 加入到模式c_k−1中形成高阶模式c_k时，模式c_k−1所损失的实例贡献度；损失的实例贡献度越高，特征o_k对模式c_k−1的影响程度越低，特征o_k对模式c_k−1中特征的主导性越差。由此，给出特征影响度的定义。

定义8 模糊影响度(FII)：给定一个频繁co-location模式 $c_k=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$ (k > 2)，特征 $o_i\left(o_i\in c_k,\text{1}\le i\le k\right)$，c_k的一个k − 1阶子模式 $c_k{}_{-\text{1}}\left(o_i\notin c_k{}_{-\text{1}}\right)$，则o_i在模式c_k中的模糊影响度定义为1减模式c_k−1到c_k模糊损失度，即

$FII\left(c_k\text{,}{o}_i\right)=\text{1}-FLI\left(c_{k-\text{1}}\text{,}{c}_k\right)$ (13)

其中 $o_i=c_k-c_k{}_{-\text{1}}$，特征模糊影响度 $FII\left(c_k,o_i\right)$ 代表了特征o_i对频繁模式c_k中其它特征的影响， $FII\left(c_k,o_i\right)$ 越大，越多c_k中的特征实例被特征o_i的实例主导。

例6：给定a = 0.1，则特征A从{A, B}到{A, B, C}的模糊损失率为： $FLR\left(\left\{\text{A},\text{B}\right\},\left\{\text{A},\text{B},\text{C}\right\},\text{A}\right)=0.\text{1}$，$FLR\left(\left\{\text{A},\text{B}\right\},\left\{\text{A},\text{B},\text{C}\right\},\text{B}\right)=0.0\text{3}$，则{A, B}到{A, B, C}的模糊损失度为： $FLI\left(\left\{\text{A},\text{B}\right\},\left\{\text{A},\text{B},\text{C}\right\}\right)=0.0\text{3}$。同样的 $FLI\left(\left\{\text{A},\text{C}\right\},\left\{\text{A},\text{B},\text{C}\right\}\right)=0.\text{5}$,$FLI\left(\left\{\text{B},\text{C}\right\},\left\{\text{A},\text{B},\text{C}\right\}\right)=0.\text{225}$。则在频繁co-location模式{A, B, C}中，特征A, B, C对模式的模糊影响度分别为： $FII\left(\left\{\text{A},\text{B},\text{C}\right\},\text{A}\right)=\text{1}-0.\text{225}=0.\text{775}$,$FII\left(\left\{\text{A},\text{B},\text{C}\right\},\text{B}\right)=\text{1}-0.\text{5}=0.\text{5}$,$FII\left(\left\{\text{A},\text{B},\text{C}\right\},\text{C}\right)=\text{1}-0.0\text{3}=0.\text{97}$。

定义9 模糊影响比(FIR)：给定一个k (k > 2)阶频繁co-location模式 $c_k=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$，特征o_i， $o_j\left(o_i,o_j\in c_k\right)$ 满足FII(c_k, o_i) ≥ FII(c_k, o_j)，则o_i对o_j的模糊影响比定义为1减去两个特征的模糊影响度的比值，即

$FIR\left(o_i\text{,}{o}_j\right)=\text{1}-\frac{FII\left(c_k\text{,}{o}_j\right)}{FII\left(c_k\text{,}{o}_i\right)}$ (14)

传统主导特征挖掘算法是计算模式中两两特征差异度并设置差异度阈值来度量特征间的差异，但是本文通过模糊实例间的邻近关系，计算特征的差异度值很小，不能有效且明显的看出特征间的影响差异，所以提出了模糊影响比将特征间影响度的差异关系更为明显的表示出来。即模糊影响比指数更好地度量了模式中特征间的影响差异，模糊影响比指数FIR(o_i, o_j)越大，特征o_i对特征o_j主导性越强。

例7：在图1中模式{A, B, C}中特征C对特征A的影响比 $FIR\left(\text{C},\text{A}\right)=\text{1}-0.\text{775}/0.\text{97}=0.\text{2}$。特征C对特征 B的影响比 $FIR\left(\text{C},\text{B}\right)=\text{1}-0.\text{5}/0.\text{97}=0.\text{49}$。

定义10 主导特征和含主导特征的并置模式：给定一个k (k > 2)阶频繁并置模式 $c_k=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$，最小模糊参与度阈值min_fprev和模糊影响比阈值min_fir，对于o_i, o_j Î c_k如果同时满足以下条件：1) FII (c_k, o_i) ≥ FII (c_k, o_j), 2) FIR (o_i, o_j) ≥ min_fir，那么在频繁并置模式中称特征o_i主导特征o_j，且o_i是模式c_k的一个主导特征。对于并置模式c_k如果满足FPI (c_k) ≥ min_fprev，则c_k是一个含主导特征并置模式。

例8：给定模糊影响比阈值min_fir = 0.1，通过计算模式{A, B, C}是含主导特征的并置模式，主导特征为C，可以计算出特征C主导特征A和B的并置。

引理1 反单调性。模糊参与率和模糊参与度随着模式阶的增大而单调非递增。

证明：设有k阶并置模式 $c_k=\left\{o_{\text{1}},o_{\text{2}},\cdots ,o_k\right\}$ 和k + 1阶模式c_k+1 = c_k + o_k+1，对于o_i Î c_k，如果o_i的某个实例含在c_k+1的模糊行实例中，那么该实例也一定包含在c_k的模糊行实例中，反之不然。由于实例的模糊行实例贡献度是指与其它实例间的最小邻近度，实例的模式贡献度是取某个实例重复出现在多个行实例时贡献度的最大值并参与特征的模糊参与率计算，因此o_i的某个实例对o_i在c_k+1中的计算模糊参与率时贡献度值一定不大于该实例对o_i在模式c_k中参与模糊参与率计算的贡献值。因此，模糊参与率随着模式阶的增大而单调非递增。因为模糊参与度是取模式中所有特征模糊参与率的最小值，所以模糊参与率也随着模式阶的增大而单调非递增。即证。

定理1 向下闭合性。在基于模糊邻近关系(FNR)的并置模式挖掘中，如果一个并置模式c是频繁的，则它的所有子模式c' Ì c都是频繁的；相反的，如果一个并置模式c是非频繁的，则它的所有超模式c' É c也都是非频繁的。

证明：由引理1可知，并置模式c的模糊参与度不大于其所有子模式的模糊参与度，不小于其超模式的模糊参与度，所以如果并置模式c是频繁的，则其所有子模式一定都是频繁的；如果并置模式c是非频繁的，则其所有超集也一定都是非频繁的。即证。

3. 挖掘算法

本节给出了挖掘含主导特征的空间并置模式的基本算法DFMAFPR和优化算法DFMAFPR-Improved。

3.1. DFMAFPR算法

根据用户给定的邻近度阈值α和最小影响比阈值min_fir，首先挖掘出所有模糊频繁的并置模式，计算特征的模糊损失率和模式的模糊损失度，最后通过特征间的模糊影响比挖掘出含有主导特征的频繁并置模式。具体见算法1：

算法1. DFMAFPR

第1、2行根据给定模糊邻近关系的隶属函数，使用网格划分技术，计算空间数据集的模糊邻近关系，获取满足邻近度阈值a的模糊邻近对，并生成模糊星型邻居集。第3~5行生成k阶候选模式集，第6~7行计算候选模式的模糊参与度。对于满足模糊参与度阈值的模式，第8~11行计算该模式的k − 1阶子模式集合计算模糊损失度并得到每个特征的模糊影响度。第12~15行取出模式中所有特征的特征模糊影响度，并计算模式中两两特征模糊影响度的特征模糊影响比是否满足特征模糊影响比阈值min_fir，将满足阈值的特征o_i放入主导特征集合DF_set(c)。第17~19行存储DFCP及其主导特征集集合中。第4~22行被重复执行，用于逐阶输出所有DFCP及其主导特征集。

算法1分析：DFMAFPR算法的时间复杂度分析可以分为四个部分，由于DFMAFPR算法是由Joinless算法改进得到，所以前三个部分和Joinless相似，第一部分复杂度为T_{f_star_neib}，区别于Joinless进一步将实例距离模糊化后转化为邻近度。第二部分复杂度是T(2)生成二阶频繁模式消耗的时间，第三部分复杂

度是 ${\displaystyle \underset{k=2}{\overset{h}{\sum }}T\left(k\right)}$，表示生成高阶频繁模式消耗的时间，其中h表示迭代时co-location模式的最高阶数。第四

部分复杂度是T_{DF_set}，表示在频繁模式中挖掘主导特征消耗的时间。由于DFMAFPR算法考虑了实例间的邻近程度，在生成相同数量的候选co-location模式情况下，时间复杂度比Joinless算法更高一些。相比于同样改进Joinless算法后的主导特征模式挖掘算法ADFSPTCM [21]，本文所提出的DFMAFPR算法复杂度也会更高一些，当相关参数一致的情况下DFMAFPR算法挖掘出的主导特征模式比ADFSPTCM算法更有价值。

3.2. 优化算法DFMAFPR-Improved

该算法是在算法1基础上进一步优化主导特征的挖掘过程，在筛选出的频繁模式中计算最大特征影响度和最小特征影响度后，计算最大特征影响比，当最大特征影响比满足给定阈值时，保留该频繁模式进行主导特征挖掘计算，可以在计算特征影响比之前对频繁模式进行剪枝，进一步提高挖掘效率。

算法2. DFMAFPR-Improved

第1行判断初始频繁并置模式集合非空；第2行取模式中最小特征模糊影响度和最大特征模糊影响度；第3行计算最大特征模糊影响比并验证是否满足最大特征模糊影响比阈值；第4行将满足阈值的频繁并置模式放入集合。

算法2分析：根据相关定义，在含主导特征的并置模式挖掘过程中，对于一个模糊频繁并置模式c_k需要计算所有特征两两之间的特征影响比，直至确认该模式中没有任何一对特征满足特征影响比阈值，才认为不含主导特征。DFMAFPR-Improved为了优化挖掘过程，提取模式中最大特征模糊影响度和最小特征模糊影响度来判断模式中是否含有主导特征，通过k次比较完成。即这一阶段的计算复杂度仅为模式长度k，该过程大大加速了挖掘速度。所以DFMAFPR-Improved的时间复杂度在第四部分大大减少了计算时间。

4. 实验结果与分析

本节基于合成数据集和真实数据集，对于我们所提出的基于模糊邻近关系的含主导特征的并置模式挖掘算法(DFMAFPR)和优化算法(DFMAFPR-Improved)做实验评价。主要目的是：1) 在合成数据集上，我们评估不同实验参数对算法效率的影响以及算法的可伸缩性；2) 在合成数据集和真实数据集上，对比DFMAFPR和DFMAFPR-Improved算法和传统主导特征模式挖掘算法(ADFCPM) [21] 挖掘结果的差异；3) 在真实数据集上，给出含主导特征的并置模式挖掘结果实例，进一步说明基于模糊邻近关系的含主导特征并置模式挖掘算法在实际应用中的意义。

运行环境：所有算法采用python语言实现，并运行于具有AMD Ryzen 7 1700X Eight-Core Processor 3.40 GHz处理器，16 GB内存、Windows 10及pycharm 2020的PC机上。参数设置：所提主导特征模式挖掘算法ADFSPTCM、DFMAFPR-Improved在各个数据集上的实验参数默认设置如表2所示。

4.1. 实验数据集

实验数据集：实验采用了3个合成数据集和2个真实数据集，数据集相关信息如表1所示，其中，Plant-Data是一个包含31种植物类型(特征)共356棵植物(实例)的“三江并流”区域珍稀植物数据集。北京POI是一个包含16种类型(特征)共2305个POI (实例)的北京市POI数据集。合成数据集采用与文献 [21] 提出的数据生成器类似的方法根据泊松分布函数分别在500 × 500、1000 × 1000的范围内生成合成数据。

表1. 实验数据集参数

表2. 实验默认说明

4.2. 不同参数对算法性能的影响

本文所提算法所用距离阈值d₂ = 80，我们在3个不同规模的合成数据集上分析不同参数设置对所提主导特征模式挖掘算法DFMAFPR、优化算法DFMAFPR-Improved进行比较。目的是观察在不同实例数量和特征数量下，参数变化对算法造成的不同影响。

4.2.1. 距离阈值d对算法性能的影响

图3~5分别显示两个算法在d₁取20、30、40和50四个不同的距离阈值时在3个合成数据集上的性能表现，其它参数取表2中默认值。在每个数据集上，随着距离阈值的增大，算法运行时间逐渐增加，并且随着数据集的规模增大，运行时间也逐渐增加。距离阈值较大时，对算法性能的影响较为明显，这说明算法性能受到数据稠密性的影响。合成数据集1比合成数据集2分布更稠密，邻近度阈值的影响较明显，并且运行时间也相对较长。合成数据3的特征数量和实例数量最多，所以运行时间最长。算法DFMAFPR-Improved表现比基础算法DFMAFPR更好，是因为在计算主导特征时有效的对模式进行剪枝。

图3. 不同距离阈值性能比较(合成数据集1)

图4. 不同距离阈值性能比较(合成数据集2)

图5. 不同距离阈值性能比较(合成数据集3)

4.2.2. (模糊)参与度阈值对算法性能的影响

图6~8分别显示在(模糊)参与度阈值分别取0.3，0.4，0.5和0.6时两个算法在3个合成数据集上的性能表现，其它参数取表2中默认值。随着数据规模的增加和(模糊)参与度阈值的增加，运行时间逐渐减少。合成数据集1比合成数据集2分布更稠密，同一范围内实例数量增加，满足成团的实例增多，对(模糊)表实例的运算耗费影响了算法性能，(模糊)参与度阈值变化对算法效率的影响较为明显，其中合成数据集3的运行时间最长。

4.2.3. 特征影响比阈值对算法性能的影响

图9~11分别显示DFMAFPR算法、DFMAFPR-Improved算法在3个合成数据集上的性能，其它参数取表2中默认值。特征模糊影响比阈值min_fir分别取0.3、0.4、0.5和0.6，随着特征模糊影响比阈值的变化，算法运行时间逐渐减。因为随着阈值的升高，需要计算的频繁模式表实例减少，阈值的变化对于稠密数据集上算法性能的影响更为明显。

图6. 不同参与度阈值性能比较(合成数据集1)

图7. 不同参与度阈值性能比较(合成数据集2)

图8. 不同参与度阈值性能比较(合成数据集3)

图9. 不同影响比阈值性能比较(合成数据集1)

图10. 不同影响比阈值性能比较(合成数据集2)

图11. 不同影响比阈值性能比较(合成数据集3)

通过本文所提两种算法和传统主导特征模式挖掘算法在2个合成数据集上的比较，优化后的DFMAFPR-Improved算法在基础算法上消耗时间更少，在挖掘主导特征过程中减少大量的计算。

4.3. DFMAFPR算法的挖掘结果分析

我们在2个真实数据集上，比较分析所提基于模糊邻近关系主导特征模式挖掘算法DFMAFPR与传统频繁模式挖掘算法JoinLess、传统含主导特征模式挖掘算法AMDFCP的挖掘结果。

4.3.1. 在“三江并流”区域珍稀植物数据集上的结果比较

在“三江并流”区域珍稀植物数据集上，三个算法在不同(模糊)参与度阈值下挖掘得到的模式数量如图12所示，其中DFMAFPR算法两个距离阈值d₁ = 5000和d₂ = 15000，Joinless算法和AMDFCP算法所用距离阈值d = 5000，其它参数取表2中默认值。从图中可以看出DFMAFPR挖掘的主导特征模式数量大约为Joinless算法挖掘的频繁模式数量的50%，这是因为DFMAFPR有效去除了不含主导特征的频繁模式。我们提出的算法挖出的含主导特征模式比AMDFCP算法的含主导特征模式数量多，是因为AMDFCP算法是基于单一邻近阈值判断实例间邻近关系，实例在形成团关系时会造成邻近关系缺失。

三个算法在不同距离阈值d下挖掘得到的模式数量如图13所示。随着距离阈值d的增大，三个算法挖掘到的频繁模式的数量逐渐增加，其中Joinless模式数量增加趋势较为明显，这是因为在数据分布密度较高时，随着同一邻域内的实例数量和特征数量类型增多，候选模式的数量和团实例的数量都急剧增加；我们还可以看到三种主导特征模式挖掘算法产生的模式数量远远小于Joinless算法产生的模式数量，但是本文所提算法挖掘出的主导特征模式数量都比AMDFCP算法多。

图12. 植物数据集上不同(模糊)参与度阈值下的模式数量

图13. 植物数据集上不同距离阈值下的模式数量

4.3.2. 在北京POI数据集上的结果比较

在北京POI数据集上，三个算法在不同(模糊)参与度阈值、距离阈值下挖掘得到的模式数量分别如图14和图15所示，其中DFMAFPR算法两个距离阈值取d₁ = 50和d₂ = 150，Join Less算法和AMDFCP算法所用距离阈值d = 50，其它参数取表2中默认值。

图14. 北京POI数据集上不同(模糊)参与度阈值下的模式数量

图15. 北京POI数据集上不同距离阈值d下的模式数量

通过在两个真实数据集中的比较，本文所提出的算法DFMAFPR虽然受距离阈值d₁影响，但与传统挖掘算法AMDFCP相比，DFMAFPR挖掘出主导特征模式数量更多。真实数据集1中包含32个特征，但仅有335个实例，在挖掘主导特征时(模糊)表实例中的实例数量变化将导致特征(模糊)参与率的计算。

4.4. 真实数据集上的挖掘结果及应用实例分析

为了验证本文所提主导特征模式的实用性，我们对本文所提含主导特征模式挖掘算法和传统AMDFCP算法在2个真实数据集上挖掘得到的含主导特征模式进行实例分析。表3和表4分别列出了DFMAFPR算法和AMDFCP算法在植物数据集和北京POI数据集上的一些三阶模式。从表中我们可以看出在植物数据集挖掘出的模式{川八角莲，珙桐，冬虫夏草}、{松茸，丽江雪胆，长苞冷杉}和{松茸，三尖杉，穿心延子藨}是DFMAFPR和AMDFCP共有的主导特征模式，其中主导特征相同，而{松茸，三尖杉，长苞冷杉}和{云南榧木，三尖杉，红豆杉}是AMDFCP算法挖掘不到的主导特征模式。在北京POI数据集挖掘出{酒店，停车场，服装店}、{酒店，中餐馆，停车场}、{西餐厅，停车场，公交站}是DFMAFPR和AMDFCP共有的主导特征模式，其中主导特征相同，而{花园，停车场，咖啡厅}、{中餐厅，咖啡厅，招待所}是AMDFCP算法挖掘不到的主导特征模式。

表3. DFMAFPR和AMDFCP在三江并流植物数据上挖掘的结果比较

注：^*代表主导特征；-代表没有参数可挖掘到。

表4. DFMAFPR和AMDFCP在北京POI数据上挖掘的结果比较

注：^*代表主导特征；-代表没有参数可挖掘到。

首先，本文所提算法和AMDFCP算法在挖掘主导特征模式时都是从三阶频繁模式开始，但是AMDFCP算法局限于单一的邻近阈值，超出邻近阈值的实例对就判定为不邻近，这种单一截断的邻近关系判断会造成邻近关系的损失，并且AMDFCP算法在挖掘频繁模式时对于频繁性阈值非常敏感，当两两实例对于单一距离阈值判为不邻近时，就不参与实例特征参与率计算，但是DFMAFPR和DFMAFPR-Improved算法是使用模糊数学的方法去计算两两实例的邻近程度，首先在挖掘主导特征并置模式时计算实例对模式的模糊贡献度，其次通过模糊参与率和模糊参与度挖掘出更有参考价值的频繁并置模式，进而发掘模式中两两特征间的关系并挖掘出含有主导特征的并置模式。

在表3和表4中，通过比较2个真实数据集挖掘出来的结果发现，特征数量和实例数量较多的数据集能发现更多含有主导特征的模式，更好的揭示模式中特征的主导关系。通过实验分析，虽然DFMAFPR挖掘效果受两个距离阈值d₁和d₂影响，但与AMDFCP算法相比挖掘出的模式数量更多，本文所提算法挖掘出的主导特征模式更有价值和决策性，当d₁和d₂取值相近时两个算法挖掘模式数量几乎相同。通过本文所提两种算法和传统主导特征模式挖掘算法在3个合成数据集和2个真实数据集上的比较，优化后的DFMAFPR-Improved算法比基础算法消耗时间更少，由于算法在计算实例间的邻近度和模式中模糊参与率、模糊参与度时更耗费时间，所以DFMAFPR算法与传统AMDFCP算法比较时间效率相对较差，但是挖掘出的模式会更有价值，可以更好的应用在实际生活中。

5. 总结

主导关系体现的是中心事物对周边事物的吸引力或者周边事物对中心事物的依赖性，本文基于模糊空间实例邻近关系，研究空间频繁并置模式的主导特征挖掘，以更好地揭示空间特征间的主导关系。首先，本文在模糊邻近关系的基础上，给出实例对模糊行实例、模式的贡献、模糊参与率和模糊参与度等相关定义，并通过特征影响比指标度量特征的主导性。然后，提出了有效的含主导特征模式挖掘算法。最后，通过在合成数据集和真实数据集上的大量实验验证了本文所提算法能够挖掘出更多更有价值的含主导特征的并置模式。在未来的研究中，我们将设计高效的剪枝策略和挖掘方法，进一步提高算法的挖掘效率。

基金项目

国家自然科学基金项目(No.61966036, No.61662086)；云南省创新团队项目(No.2018HC019)。

文章引用

冯 时,王丽珍,方 圆. 基于模糊邻近关系挖掘含主导特征的空间并置模式
Mining Spatial Collocation Patterns with Dominant Features Based on Fuzzy Neighborhood Relationship[J]. 计算机科学与应用, 2021, 11(01): 176-194. https://doi.org/10.12677/CSA.2021.111019

参考文献