空间亚频繁co-location模式的主导特征挖掘

马 董，陈红梅，王丽珍，肖 清

（云南大学信息学院，昆明650504）

0 引言

随着基于位置的服务（Location Based Services，LBS）和空间数据采集技术的快速发展，数据挖掘从事务型数据库扩展到了空间数据库。如何从海量、高维的空间数据中挖掘潜在、有趣的知识并指导决策变得尤其重要。空间co-location（并置）模式挖掘作为空间数据挖掘的重要研究方向，在环境保护［1］、城市计算［2］、公共交通［3］等领域具有广泛的应用。空间co-location模式是一组空间特征的子集，它们的实例在邻域内频繁并置出现。例如，火车站附近往往有旅馆；西尼罗河病毒往往发生在蚊子泛滥、饲养家禽的区域［4］。

通常，空间co-location 模式挖掘方法假设空间实例相互独立，并采用空间实例参与到模式实例的频繁性（参与率）度量其特征在模式中的重要性，采用空间特征的最小参与率（参与度）度量模式的有趣程度，忽略了空间特征间的某些重要关系（如主导关系）。例如，在co-location 模式｛药店，医院，花店｝中，各个特征的参与率分别为0.65、0.5和0.8。这一模式反映，药店、医院和花店频繁出现在一起，其中花店出现的频率最高，但是它不能揭示特征间的主导关系，即医院主导了花店和药店的出现，花店和药店依赖于医院而存在。挖掘co-lo⁃cation模式中的主导特征，可以揭示模式中的哪些特征具有主导地位，哪些特征受主导特征支配，进而为深入剖析模式中特征间的其他重要关系（如因果关系、共生关系、排斥关系）奠定基础，为基于co-location 模式的决策分析（如环境监测、城市规划、交通控制）提供支持。

现有主导特征co-location 模式挖掘方法是基于传统频繁模式及其团实例模型，通过计算特征在频繁模式及其子模式的参与率变化来识别主导特征及主导特征模式［5］，方法存在两方面的不足：1）仅考虑空间实例参与到模式实例的比重变化，没有考虑模式中空间特征间的相互影响；2）传统频繁模式的团实例模型要求模式中的所有空间实例两两邻近，然而主导关系反映的是主导对象与受支配对象间的关系，不强调受支配对象间的关系，也就是说，主导关系不要求空间实例形成团，因而团实例模型可能会忽略非团的空间特征间的主导关系。

为解决传统频繁模式及其团实例模型的不足，文献［6-7］提出了空间亚频繁co-location 模式及其星型实例模型，以挖掘具有更丰富空间关系的co-location 模式。亚频繁模式及其星型实例模型关注中心实例与其周边空间实例间的邻近关系，而不要求周边空间实例两两邻近，这与主导关系一致。因此，本文基于星型实例模型，研究空间亚频繁co-location 模式的主导特征挖掘，以更好地揭示空间特征间的主导关系，挖掘更有价值的主导特征模式。

本文主要面临两方面的挑战：1）在亚频繁co-location 模式及其星型实例模型下，如何合理地定义度量主导特征模式的指标；2）面对更大的亚频繁co-location 模式集合，如何高效地挖掘主导特征模式。本文主要工作包括：1）分析特征间的相互影响，定义了两个度量特征主导性的指标：特征贡献度和特征影响比指数。2）提出有效的主导特征co-location 模式挖掘算法。3）在合成数据集和真实数据集上进行大量实验，验证了所提算法的有效性以及主导特征模式的实用性。

1 相关工作

根据挖掘对象的不同，空间co-location 模式挖掘主要可以分为如下6类：

1）从确定空间数据中挖掘co-location 模式。这类模式挖掘主要以优化挖掘过程、提高挖掘效率为目标，如Join-based算法［8］、Partial-join 算法［9］、Join-less 算法［10］、CPI-tree（Co-location Pattern Instance tree）算 法［11］、iCPI-tree（improved CPI-tree）算法［12］、order-clique-based算法［13］。

2）从不确定性空间数据中挖掘co-location 模式。文献［14］研究了从区间数据中挖掘co-location 模式；文献［15］将Join-based 算法扩展为UJoin-based 算法，挖掘位置不确定空间数据中的co-location 模式；文献［16］通过对不确定性数据建模和处理，在分布式系统下定义了概率频繁co-location 模式，并设计了高效的并行挖掘算法。

3）从带约束的空间数据中挖掘co-location 模式。文献［17］针对传统模式挖掘算法在挖掘带有稀有特征的空间数据集时，可能丢失有趣模式的问题，提出了最大参与率概念，并设计了maxPrune 算法挖掘带稀有特征的co-location 模式；文献［18］针对maxPrune 算法会挖掘到不频繁模式的问题，提出了最小加权参与率概念，并设计了加权参与率WB（Weighted Basic）算法，挖掘带有稀有特征的co-location 模式，同时去除非频繁模式；文献［6-7］考虑传统团实例模型可能导致有趣模式丢失的问题，提出了星型实例模型及空间亚频繁co-location模式，并设计了PTBA（Prefix-Tree-Based Algorithm）和PBA（Partition-Based Algorithm）两个高效的挖掘算法。

4）从模糊空间数据中挖掘co-location 模式。文献［19］提出了模糊参与率和模糊参与度以挖掘模糊空间co-location 模式；文献［20］将密度峰值聚类算法和模糊理论相结合来实现实例对簇的模糊划分，并采用模糊团代替传统团以挖掘co-lo⁃cation 模式；文献［21］基于模糊理论定义了模糊邻近度，并利用模糊聚类算法进行co-location模式挖掘。

5）效用co-location 模式挖掘。这类模式挖掘考虑了不同空间特征或不同空间实例的效用差异，能提高模式的实用性。文献［22］考虑了不同空间实例的不同价值，将效用作为兴趣度量，提出了一种演化空间数据上的高效用模式增量挖掘方法；文献［23］将约束挖掘与制图可视化相结合，提出了一种领域驱动的co-location 挖掘算法；文献［24］基于效用数据集确定特征实际参与权重，采用特征效用率和模式效用度度量高效用co-location模式。

6）主导特征co-location 模式挖掘。这类模式挖掘由文献［5］提出，其基本思想是在基于团实例模型的传统频繁co-lo⁃cation模式基础上，进一步考虑空间特征参与到模式及其子模式中的比重变化，挖掘主导特征co-location 模式，以揭示模式中特征的不同重要性。

本文研究主导特征co-location 模式挖掘，但与文献［5］不同的是，本文针对团实例模型可能会忽略非团的空间特征间的主导关系，提出基于星型实例模型来挖掘亚频繁co-location模式中的主导特征及主导特征模式的方法。

2 基本概念及问题定义

2.1 传统co-location模式

给定一个空间特征集合F={f1，f2，…，fn}，对应的空间实例集合S=S1∪S2∪…∪Sn，其中Si(1 ≤i ≤n)是特征fi的实例集合，以及距离阈值d。通常，如果两个实例的欧几里德距离小于等于距离阈值，则称它们满足空间邻近关系R，即。对于一个k 阶空间co-location 模式c={f1，f2，…，fk}(c ⊆F，k=|c|)，以 及 实 例 集I={i1，i2，…，ik}(I ⊆S)，若I 包含c 所有特征的实例且I 中没有一个子集包含 c 所 有 特 征 的 实 例 ，并 且 I 形 成 团 ，即{R(ii，ij)|1 ≤i ≤k，1 ≤j ≤k}，则称I 为c 的一个行实例，c 的所有行实例构成c 的表实例，记为T（c）。如图1 所示，图中有3个空间特征A、B 和C，它们的实例数都为3，满足邻近关系的实例用实线连接，则co-location 模式{A，B，C}的表实例为：T({A，B，C})={A.1，B.1，C.1}。

图1 空间特征及其实例分布示例Fig.1 Example of spatial features and distribution of their instances

在传统co-location 模式中，特征fi在模式c 中的参与率定义为fi的实例在c 的表实例中不重复出现的个数与fi总实例个数的比率，即：

其中：π是关系投影操作，Si表示特征fi的所有实例集合。

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

给定参与度阈值min_prev，当PI(c)≥min_prev，则称模式c 为频繁co-location 模式。如图1 所示，设参与度阈值min_prev=0.3，模式｛A，B，C｝的参与度为：PI({A，B，C})=，则模式｛A，B，C｝是一个频繁colocation模式。

2.2 亚频繁co-location模式

传统co-location 模式基于团实例模型度量模式的有趣程度，然而，在实际应用中，严格的团实例要求，可能使得空间特征间的某些重要关系被忽略。例如，在图1 中，模式｛A，B，C｝仅 有｛A.1，B.1，C.1｝一 个 行 实 例，其 参 与 度 为，当参与度阈值为0.5 时，模式｛A，B，C｝不是频繁模式。但是，从图1中可以看出，在特征A、B和C中，每个特征分别有2个实例与其余2个特征的实例有邻近关系，即每个特征至少有2/3 的实例与模式中其他特征的实例有邻近关系，表明特征A、B、C 具有较高的空间相关性。基于上述观察，Wang 等［6-7］提出了星型实例模型及亚频繁co-location模式。

定义1星型邻居实例。给定空间实例ij和距离阈值d，实例ij的星型邻居实例集合SNsI(ij)定义为：

图1中，SNsI(A.2)={A.2，B.1，C.2}。

定义2星型参与实例。给定co-location模式c，特征fi在模式c 中的星型参与实例定义为特征fi的实例集合，其中每个实例的星型邻居实例集合包含了模式c 的所有特征的实例。

图1中，SPIns(A，{A，B，C})={A.1，A.2}。

定义3星型参与率和星型参与度。给定co-location 模式c，特征fi在模式c 中的星型参与率定义为特征fi的星型参与实例数与fi的实例个数的比率：SPR(fi，c)=模式c 的星型参与度SPI(c)定义为模式c中所有特征的星型参与率的最小值：SPI(c)=

给定星型参与度阈值min_sprev，当SPI(c)≥min_sprev，则称模式c为亚频繁模式。

例1 图1 中有3 个特征A、B 和C，它们的实例数都为3。设星型参与度阈值min_sprev=0.5，模式{A，B，C}的星型参与度：SPI({A，B，C})=min(0.67，0.67，0.67)=0.67，则模式｛A，B，C｝是一个亚频繁co-location模式。

2.3 主导特征co-location模式

与传统频繁co-location 模式相比，亚频繁co-location 模式可以发现更丰富的空间特征关系。但是，亚频繁模式也没有较好地区分模式中不同特征的不同重要性及不同特征对模式的不同贡献。于是，基于亚频繁模式及其星型实例模型，本文提出了新的主导特征co-location 模式。不同于基于传统频繁模式及其团实例模型的传统主导特征模式，该类模式仅考虑空间特征参与到模式及其子模式中的比重变化［5］，本文所提的主导特征模式利用特征贡献度度量特征对模式的影响，采用特征影响比指数度量模式中特征间的影响，从而发现更有价值的主导特征及主导特征模式。

定义4星型行实例。给定k 阶亚频繁co-location 模式c={f1，f2，…，fi，…，fk}及其实例集I={i1，i2，…，ii，…，ik}，其中ii(1 ≤i ≤k)是特征fi的实例。如果I 是特征fi的星型参与实例的星型邻居实例SNsI(ii)的子集，则称I是特征fi在模式c中的一个星型行实例。特征fi在模式c中的所有星型行实例记为，所有特征在模式c中的所有星型行实例构成模式c的星型表实例STIns(c)。

例2 空间实例分布如图2 所示，表1 给出了模式｛D，F，H｝的星型行实例。特征H的星型参与实例H.2的星型邻居实例为｛D.1，D.4，F.1，H.2｝，实例集｛D.1，F.1，H.2｝是特征H在模式｛D，F，H｝中的一个星型行实例，特征D 在模式｛D，F，H｝中的所有星型行实例SRIns(D，{D，F，H})为：{D.2，F.5，H.1}，{D.3，F.6，H.1}，{D.4，F.1，H.2}，表1 中的所有星型行实例即构成模式｛D，F，H｝的星型表实例STIns({D，F，H})。

图2 主导特征及主导特征模式示例Fig.2 Example of dominant features and patterns with dominant features

定义5特征贡献度。给定k 阶亚频繁co-location 模式c={f1，f2，…，fk}，特征fi对模式c的贡献度FCR(fi，c)定义为fi在c中的星型行实例数与c的星型行实例数的比率：

例3 模式{D，F，H}中各个特征的贡献度分别为：FCR(D，{D，F，H})=FCR(F，{D，F，H})=FCR(H，{D，F，H})=，所以特征H（医院）对模式{D，F，H}的贡献度最大。

特征fi对模式c 的贡献度表示的是以fi的实例为中心的星型行实例集在模式c 的星型行实例集的占比，用于度量特征对模式的影响，fi的贡献度越大，fi在模式中越重要。为了进一步度量模式中特征间的影响，下面引入特征影响比指数及相关概念。

定义6特征最大聚集数。给定k阶亚频繁co-location 模式c={f1，f2，…，fk}，特 征fi在 模 式c 中 的 最 大 聚 集 数MFG(fi，c)定义为c中的其余各个特征在fi的星型参与实例的星型邻居中的实例数之和的最大值与fi的星型参与实例数的比值：

表1 模式｛D，F，H｝的星型行实例Tab.1 Star row instances of pattern｛D，F，H｝

例4 对于图2 中的模式｛D，F，H｝，特征H 的最大聚集数为：MFG(H，{D，F，H})=max(7，6)/4=1.75。

特征最大聚集数反映了模式中某个特征实例对其余特征实例的影响程度，或其余特征实例对该特征实例的依赖程度。

定义7特征影响度。给定k 阶亚频繁co-location 模式c={f1，f2，…，fk}，特征fi对模式c 的影响度FIR(fi，c)定义为fi的最大聚集数与星型参与率的乘积：

例5 在图2 中，模式｛D，F，H｝中各个特征影响度分别为：FIR(D，{D，F，H})=1×0.43=0.43，FIR(F，{D，F，H})=1×0.5=0.5，FIR(H，{D，F，H})=1.75×1=1.75。

事实上，特征影响度是考虑了实例间相互影响的星型参与率，兼顾了模式中特征的重要性和频繁性。如图2 中实例H.1和D.2，都参与到模式｛D，F，H｝中，但是重要性不同。

定义8特征影响比指数。给定亚频繁co-location 模式c=(f1，f2，…，fk)，如 果 两 个 特 征fi，fj∈c 的 影 响 度 满 足那 么 特 征fi对 特 征fj的 影 响 比 指 数FIQI(fi，fj)定义为：

特征影响比指数度量了模式中特征间的影响差异，影响比指数FIQI(fi，fj)越大，特征fi对特征fj主导性越强。

例6在图2 中，模式｛D，F，H｝中特征H 对特征D 的影响比指数FIQI(H，D)=1-0.43/1.75=0.75。

定义9主导特征和主导特征模式。给定亚频繁co-location 模式c={f1，f2，…，fk}，特征贡献度阈值min_fcr 和影响比指数阈值min_fiqi。如果特征fi∈c满足以下条件，则fi为主导特征，模式c为主导特征模式。

1）FCR(fi，c)≥min_fcr；

2）FIQI(fi，fmin)≥min_fiqi；

例7 设min_fcr=0.4 和min_fiqi=0.4，模式{D，F，H}中各个特征的贡献度、影响度和影响比指数的计算结果如表2 所示。从表2 中可得出，模式｛D，F，H｝是主导特征模式，主导特征为H，也就是医院主导了药店和花店的共存。

表2 {D，F，H}中的特征指标Tab.2 Feature indicators of{D，F，H}

问题定义 给定空间特征集合F，空间实例集合S，距离阈值d，星型参与度阈值min_sprev，特征贡献度阈值min_fcr和影响比指数阈值min_fiqi，挖掘亚频繁co-location 模式中的所有主导特征及主导特征模式。

3 挖掘算法

需要强调的是，主导特征模式不满足反单调性。如图2中，特征H 在子模式｛F，H｝与超模式｛D，F，H｝的贡献度与影响比指数关系分别为：

所以，主导特征模式挖掘不能应用模式的反单调性进行剪枝。为了提高主导特征模式挖掘算法的效率，本文设计了亚频繁co-location 模式中的主导特征模式挖掘算法SDFMA（Sub-prevalent based Dominant-Feature Mining Algorithm）。首先，由于亚频繁模式满足反单调性，利用亚频繁模式的反单调性剪枝策略，逐阶生成亚频繁模式，同时基于生成的亚频繁模式，挖掘主导特征及主导特征模式；其次，在挖掘主导特征及主导特征模式的过程中，仅计算贡献度大于阈值的特征对最小影响度特征的影响比指数。

算法1 SDFMA。

输入 空间数据集S，空间特征集F，距离阈值d，星型参与度阈值min_sprev，贡献度阈值min_fcr，影响比指数阈值min_fiqi；

输出 主导特征co-location模式集SDFCP；

变量 表示co-location 模式阶数的k，表示k 阶co-location 亚频繁模式集的Pk。

第1）行根据空间数据集、空间特征集和距离阈值生成星型邻居集；第4）行根据算法PBTA［6-7］逐阶生成k 阶亚频繁co-location 模式；对每个亚频繁模式，第7）、8）行计算模式中每个特征的最大聚集数和影响度，第9）行得到模式中的最小影响度特征，第12）、13）行计算模式中每个特征的贡献度和影响比指数，如果它们均大于阈值，则该特征是模式的主导特征，将该特征放入模式的主导特征集（第14）行），如果模式有主导特征，则该模式是主导特征模式，该模式及其主导特征集放入结果集（第19）行）。

4 实验结果与分析

首先，生成3 个不同规模的合成数据集（Synthetic data 1～3），并在这3 个数据集上评估不同参数设置对本文提出的主导特征模式挖掘算法SDFMA 效率的影响。然后，在2 个真实数据集上比较分析了SDFMA 与基准算法的挖掘结果。选取的基准算法包括亚频繁模式挖掘算法PTBA［6-7］和传统主导特征模式挖掘算法AMDFCP（Algorithm of Dominant Feature Co-location Pattern Mining）［5］。PTBA 用于比较分析亚频繁模式与本文提出的主导特征模式（基于亚频繁模式及星型实例模型的主导特征模式）的异同；而AMDFCP 据我们了解是仅有的主导特征模式挖掘算法，用于比较分析基于传统频繁模式及团实例模型的主导特征模式与本文提出的主导特征模式的异同。最后，选取SDFMA 和AMDFCP 在2 个真实数据集上挖掘得出的主导特征模式进行实例分析，验证本文提出的主导特征模式的实用性。

4.1 实验设置

实验数据集的统计信息如表3 所示，其中：Plantdata 是一个包含31 种植物类型（特征）共356 棵植物（实例）的“三江并流”区域珍稀植物数据集，其分布呈图3 所示的带状分布；Beijing-POI 是一个包含16 种POI 类型（特征）共23 025 个POI（实例）的北京市POI数据集，其分布如图4所示。合成数据集分别在500×500、1 000×1 000、1 000×1 000的范围内根据泊松分布随机生成。

图3 Plantdata数据集分布图Fig.3 Distribution of Plantdata dataset

图4 Beijing-POI数据集分布图Fig.4 Distribution of Beijing-POI dataset

表3 实验数据集统计信息Tab.3 Experimental data set statistics

实验运行环境：所有算法采用python语言实现，并运行于具有Intel Core i7 CPU、8 GB 内存、Windows 10 及pycharm2017的PC上。

参数设置：本文提出的主导特征模式挖掘算法SDFMA 在各个数据集上的实验参数默认设置如表4所示。

4.2 不同参数设置对SDFMA的运行时间影响

首先在3 个不同规模的合成数据集上分析不同参数设置对SDFMA运行时间的影响。

4.2.1 距离阈值对算法运行时间的影响

距离阈值d 分别取10、15、20 和25 时的算法运行时间结果如图5 所示。在每个数据集上，随着距离阈值的增加，算法运行时间逐渐增加，并且随着数据集规模的增大，运行时间也逐渐增加。合成数据集1比合成数据集2分布稠密，距离阈值的影响较明显，并且运行时间也相对较长。

表4 SDFMA的实验参数默认值Tab.4 Default values of experimental parameters of SDFMA algorithm

图5 不同距离阈值d下的运行时间比较Fig.5 Comparison of running time at different d

4.2.2 星型参与度阈值对算法运行时间的影响

星型参与度阈值min_sprev 分别取0.3、0.4、0.5、0.6 和0.7时的算法运行时间结果如图6所示。在所有数据集上，随着星型参与度阈值增大，算法运行时间逐渐减少。合成数据集3 的数据量较大，阈值影响较为明显，合成数据集1 和合成数据集2 实例数和特征数一样，但是分布范围不同，合成数据集1 比合成数据集2 分布稠密，数据集1 的运行时间比数据集2的运行时间长。

图6 不同星型参与度阈值min_sprev下的运行时间比较Fig.6 Comparison of running time at different min_sprev

4.2.3 贡献度阈值对算法效率的影响

贡献度阈值min_fcr分别取0.2、0.3、0.4、0.5和0.6时的算法运行时间结果如图7 所示。算法运行时间不随贡献度阈值的变化而大幅波动，这是因为算法的主要开销是亚频繁模式挖掘。另外，贡献度阈值不满足反单调性，即使特征在模式中的贡献度小于阈值，特征在超模式中的贡献度也需要计算。算法运行时间在贡献度阈值介于0.5 到0.6 区间时有较大波动，这是因为二阶亚频繁模式中的特征贡献度都为0.5，当贡献度阈值大于0.5 时，所有这些二阶模式都不是主导特征模式。

4.2.4 影响比指数阈值对算法运行时间的影响

影响比指数阈值min_fiqi分别取0.2、0.3、0.4、0.5和0.6时的算法运行时间结果如图8 所示。随着影响比指数阈值的变化，算法运行时间基本不变。这也是因为影响比指数阈值不满足反单调性。合成数据集2 的运行效率优于合成数据集1，这是因为合成数据集1比合成数据集2稠密，容易形成较多的星型参与实例。

图7 不同贡献度阈值min_fcr下的运行时间对比Fig.7 Comparison of running time at different min_fcr

图8 不同影响比指数阈值min_fiqi下的运行时间对比Fig.8 Comparison of running time at different min_fiqi

4.3 SDFMA的挖掘结果分析

在2个真实数据集Plantdata和Beijing-POI上比较SDFMA与亚频繁模式挖掘算法PTBA、传统主导特征模式挖掘算法AMDFCP的挖掘结果。

4.3.1 在Plantdata数据集上的结果比较

在Plantdata 数据集上，三个算法在不同（星型）参与度阈值下挖掘得到的模式数量如图9（a）所示。从图中可以看出，SDFMA 挖掘的主导特征模式数量大约为PTBA 挖掘的亚频繁模式数量的60%，这是因为SDFMA 有效去除了不含主导特征的亚频繁模式。SDFMA 的主导特征模式明显比AMDFCP 的传统主导特征模式数量多，这是因为AMDFCP 忽略了大量不能形成团的主导特征模式，而SDFMA 找到了空间关系更丰富的主导特征模式。

三个算法在不同距离阈值下挖掘得到的模式数量如图9（b）所示。随着距离阈值的增大，对邻近关系的约束性变弱，频繁模式数量增多。从图9（b）中同样可以看到，SDFMA 的主导特征模式数量为PTBA 的亚频繁模式数量的60%左右，AMDFCP 的传统主导特征模式数量少于SDFMA 的主导特征模式数量。

图9 Plantdata数据集上不同（星型）参与度阈值和距离阈值下的模式数量对比Fig.9 Comparison of pattern number with different min_sprev or d on Plantdata dataset

4.3.2 在Beijing-POI数据集上的结果比较

在Beijing-POI 数据集上，三个算法在不同（星型）参与度阈值、距离阈值下挖掘得到的模式数量分别如图10（a）、（b）所示。从图中可以看出，SDFMA 的主导特征模式数量平均为PTBA 的亚频繁模式数量的60%，SDFMA 的主导特征模式数量多于AMDFCP 的传统主导特征的模式数量。随着星型参与度阈值的增加，主导特征模式在亚频繁模式中的占比增加，这说明SDFMA 能够保留高参与度的主导特征模式；随着距离阈值增加，SDFMA 和AMDFCP 的主导特征模式数量均增长平缓，这是因为POI 在市中心分布密集，在郊区分布稀疏，距离阈值影响不明显。

图10 Beijing-POI数据集上不同（星型）参与度阈值和距离阈值下的模式数量对比Fig.10 Comparison of pattern number with different min_sprev or d on Beijing-POI dataset

4.4 主导特征co-location模式实例分析

为了验证本文提出的主导特征模式的实用性，对SDFMA和传统AMDFCP 在2个真实数据集上挖掘得到的主导特征模式进行实例分析。表5 列出了它们在这两个数据集上的二阶和三阶模式。

表5 SDFMA和AMDFCP在不同数据上的挖掘结果对比Tab.5 Mining result comparison of SDFMA and AMDFCP on different datasets

从表1中可以看到：首先，SDFMA可以挖掘到二阶及以上主导特征模式，而AMDFCP 只能挖掘到三阶及以上主导特征模式，这是因为AMDFCP 通过分析特征在模式与其子模式中的参与率变化来挖掘主导特征，模式挖掘只能从三阶开始。更进一步，SDFMA 挖掘得到的这些二阶主导特征模式具有重要的现实意义。例如，在Plantdata 数据集上的模式｛冬虫夏草，梭砂贝母*｝中，冬虫夏草的生长基础是蝙蝠蛾，蝙蝠蛾一般生长在贝母、珠芽蓼等植物的根部附近，所以梭砂贝母能够为蝙蝠蛾提供生长环境，间接地促进冬虫夏草的生长，梭砂贝母构成这一模式的主导特征。再例如，在Beijing-POI 数据集上的二阶主导特征模式对城市规划和商业选址等应用具有较高的实用性。在模式｛中餐馆，酒店*｝和｛咖啡馆，花园*｝中，主导特征分别是酒店和花园，那么可以得出，在酒店附近开中餐馆是有价值的，在花园附近开咖啡馆也是合理的。

其次，与AMDFCP 相比，SDFMA 能够挖掘到更多的高阶主导特征模式以及更合理的主导特征。例如，AMDFCP 不能挖掘到模式｛云南榧木*，云南红豆杉，贡山三尖杉*｝和｛中餐馆，咖啡屋*，招待所*｝。再例如，AMDFCP 和SDFMA 都能挖掘到模式｛冬虫夏草*，梭砂贝母*，长苞冷杉｝，但是SDFMA 识别的主导特征为梭砂贝母和长苞冷杉，AMDFCP 识别的主导特征为冬虫夏草和梭砂贝母。我们知道，梭砂贝母和长苞冷杉都能为冬虫夏草提供适宜的生长环境，而长苞冷杉的生长并不依赖于冬虫夏草和梭砂贝母。再看模式｛酒店，停车场，服装店｝，SDFMA 识别的主导特征为酒店和服装店，AMDFCP识别的主导特征为酒店和停车场。在实际生活中，停车场大多存在于酒店或者服装店周边，也就是酒店和服装店主导了停车场的存在，而酒店和停车场对服装店并不存在着直接的主导作用。因此，SDFMA识别的主导特征更合理。

5 结语

主导关系体现的是中心事物对周边事物的吸引力或者周边事物对中心事物的依赖性，本文基于星型实例模型研究空间亚频繁co-location 模式的主导特征挖掘，以更好地揭示空间特征间的主导关系，挖掘更有价值的主导特征模式。首先，本文在亚频繁模式及其星型实例模型的基础上给出了相关定义，并通过特征贡献度和特征影响比指数两个指标度量特征的主导性；然后，提出了有效的主导特征模式挖掘算法；最后，通过在合成数据集和真实数据集上的大量实验验证了本文算法能够挖掘到更丰富、更有价值的主导特征模式。在未来的研究工作中，我们将设计高效的哈希结构和有效的剪枝策略，进一步提高算法的挖掘效率。