曾 新，张晓玲，李晓伟

（大理大学数学与计算机学院，云南大理 671003）

空间co-location 模式表示布尔空间特征的子集，它们的实例在地理位置上是邻近的。例如，生态学家对生态数据集进行分析时发现：尼罗鳄所在附近区域内经常有埃及鹄鸟〔1〕。

尽管Huang 等〔1〕提出了空间co-location 模式频繁度的衡量标准，并在确定数据集上构建了基于全连接的模式挖掘算法full-based，但是full-based算法在计算模式表实例过程中产生的连接操作耗费了大量计算时间。为了解决计算瓶颈问题，基于部分连接的partial-join 算法〔2〕、基于无连接的join-less 算法〔3〕和基于CPI-tree 结构的新join-less算法〔4〕相继被提出。

除基于确定数据集的数据挖掘算法之外，Wang等〔5〕提出在空间不确定数据集上高效挖掘top-k 概率频繁co-location 模式；Yoo 等〔6〕提出一种在连续变化的空间动态数据库中发现co-location 模式的方法，而Lu 等〔7〕进一步基于挖掘出的频繁colocation 模式〔8〕挖掘强共生和竞争模式；Huang 等〔9〕将实例数明显少于其他特征实例数的特征定义为稀有特征，进而提出含稀有特征的空间co-location模式挖掘算法，而冯岭等〔10〕在此基础上加入特征权重，提出新的含稀有特征的空间co-location 模式挖掘算法。

然而，空间co-location 模式主要考虑模式内不同特征实例频繁出现的频率，没有考虑特征存在的其他因素，例如，单位价值（或效用）等，因此，模式挖掘过程中忽略了即使效用值高但出现频率较低的模式。为了解决这一问题，杨世晟等〔11〕将特征的效用值引入空间co-location 模式挖掘中，定义了模式效用、模式效用率等概念，构建了空间高效用colocation 模式挖掘算法，并以扩展模式的反单调性构建了完全剪枝算法，提升了算法的挖掘效率。现实世界中的数据是不断更新的，Wang 等〔12〕基于动态数据库提出构建动态挖掘空间高效用co-location模式的有效方法；同一特征的不同实例可能具有不同的效用值，Wang 等〔13〕将实例效用值引入空间高效用co-location 模式挖掘，同时考虑模式中每个特征的内效用和外效用，以得到特征在模式中的全局影响，并提出了相应的挖掘算法和剪枝策略。尽管空间高效用co-location 模式挖掘方法不断被报道，却没有统一的高效用co-location 模式衡量标准。因此，王晓璇等〔14〕提出基于特征效用参与率的空间高效用co-location 模式挖掘方法；Zeng 等〔15〕提出基于特征实例参与权重的空间高效用co-location 模式挖掘方法。

空间高效用co-location 模式挖掘以模式的效用作为主要的衡量标准，没有考虑模式长度对模式效用的影响，因此，采用相同的模式最小效用阈值来挖掘高效用co-location 模式存在不足。尽管从事务数据库中挖掘高平均效用项集的有效算法很多〔16-23〕，但是从空间数据集中挖掘高平均效用colocation 模式的研究还未见报道。因此，探索模式长度对高效用co-location 模式挖掘的影响是必要的。

1 空间co-location 模式

布尔空间特征集合F=｛f1，f2，f3，…，fn｝和特征的实例集S=｛o1，o2，o3，…，on｝，每个实例包含所属特征类型、实例编号和位置坐标等三部分信息，部分实例的空间分布情况见图1。任意两个实例oi和oj间的距离（例如欧式距离等）小于等于用户或领域专家设置的距离阈值d，则它们满足邻近关系R，即R（oi，oj）≤d，则在图1 中用实线将它们连接。

图1 部分实例的空间分布示例

图1 中，如果co-location 模式c=｛A，B，C｝，则其模式长度为3，它包含模式c'＝｛A，B｝的所有特征，是c'的一个超集。实例集合｛A.2，B.4，C.2｝中的任意两个实例满足邻近关系R 且包含模式c 的所有特征的一个实例，但是其子集却不包含c 的所有特征的一个实例，所以，集合｛A.2，B.4，C.2｝是模式c 的一个行实例，用row_instance（c）表示，模式c的所有行实例的集合为其表实例，用table_instance（c）表示。例如，在图1 中，table_instance（c）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝。

为了有效评价空间co-location 模式的频繁度，Huang 等〔1〕提出特征参与率PR（c，fi）和模式参与度PI（c）两个评价指标，如公式（1）、（2）所示：

其中，π 是去除重复的关系投影操作。

例如，模式c=｛A，B，C｝，从图1 的实例分布中可以得出table_instance（c）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝，而A，B，C 分别有4，5，3 个实例，所以由公式（1）有，进一步根据公式（2）得到c的参与度PI（c）=min（0.5，0.4，0.67）=0.4。如果最小参与度阈值min_prev 为0.4，由于PI（c）≥0.4，所以c 为频繁co-location 模式。

为了提高频繁co-location 模式的挖掘效率，Huang 等〔1〕证明参与率和参与度满足反单调性，即参与率和参与度会随着co-location 模式长度的增大单调递减。如果一个co-location 模式是非频繁的，则它的所有超集也是非频繁的。

2 空间高平均效用co-location 模式

以下描述空间高平均效用co-location 模式的相关基本概念和判别高平均效用co-location 模式的准则。

定义1 实例外效用 实例外效用用来描述特征fi不同实例的单位价值，fi的第j 个实例fij的单位价值表示为ieu（fij）。例如，图1 中A，B，C 特征的实例外效用，见表1。

表1 特征A，B，C 的实例外效用

定义2 实例内效用 假定fi∈c，那么fij的内效用为fij在模式c 的表实例中出现的次数，表示为iiu（c，fij）。例如，在图1 中，如果模式c=｛A，B，C｝，它的表实例table_instance（c）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝，那么iiu（c，A.2）=1，iiu（c，A.3）=1，同理，iiu（c，B.4）=1，iiu（c，C.1）=1。

定义3 特征参与效用 假定fi∈c，fi有k 个实现出现在模式c 的表实例中，那么模式c 中fi的特征参与效用等于其每个参与实例的ieu（fij）与iiu（c，fij）的积之和，即fij）。例如，在图1 中，若模式c=｛A，B，C｝，则fpu（c，A）=ieu（A.2）× iiu（c，A.2）+ieu（A.3）×iiu（c，A.3）=8。

定义4 模式效用 如果模式c=｛f1，f2，…，fk｝，则模式c 的模式效用pu（c）等于其所有特征的特征参与效用之和，即例如，对于模式c=｛A，B，C｝而言，pu（c）= fpu（c，A）+fpu（c，B）+fpu（c，C）=8+10+20=38。

定义5 co-location 模式的平均效用 如果模式c=｛f1，f2，…，fk｝，它的长度和模式效用分别为k和pu（c），那么模式c 的平均效用au（c）等于pu（c）与k 的比值，即例如，模式c=｛A，B，C｝，其模式长度为3，模式效用为38，则c 的平均效用

假设用户或领域专家设定的最小平均效用阈值为min_au，如果一个co-location 模式的平均效用大于或等于min_au，那么为高平均效用co-location模式，否则为低平均效用co-location 模式。例如，设定min_au=10，对于c=｛A，B，C｝，因为au（c）=12.67＞10，所以c 为高平均效用co-location 模式。

3 算法

首先，构建了高平均效用co-location 模式挖掘的基本算法；其次，为了提高算法的效率，提出了两个剪枝策略，并进一步构建高平均效用co-location模式挖掘的剪枝算法。

3.1 基本算法首先，采用组合的方法产生所有候选二阶co-location 模式，并基于k（k≥2）阶colocation 模式，以类Apriori 算法〔24〕产生k+1 阶colocation 模式。其次，根据co-location 模式和高平均效用co-location 模式的相关定义，计算出所有候选模式的表实例和平均效用。最后，基于用户或领域专家指定的最小平均效用阈值，发现高平均效用co-location 模式的完全集。高平均效用co-location模式挖掘基本算法（HAUCP_BA）的详细描述如下：

算法1高平均效用co-location 模式挖掘基本算法HAUCP_BA

输入：

a.布尔空间特征集合F=｛f1，f2，…，fk｝；

b.空间实例及其外部权重集合S=｛（o1，ieu（o1）），（o2，ieu（o2）），…，（on，ieu（on））｝；

c.最小距离阈值d；

d.最小平均效用阈值min_au。

输出：高平均效用co-location 模式集合haucp。

变量：模式长度l，模式长度为l 的候选colocation 模式集合Cl，Cl中co-location 模式的表实例集合Tl，模式长度为l 的高平均效用co-location 模式集合。

步骤：

1.l=1；Cl=F；Hl=Ø；

2.Tl=generate_table_instance（Cl，S）；

3.while Tl≠Ø

4.do

5.Hl=select_high_average-utility_co-location_pattern（Cl，S，l，Tl，min_au）；

6.haucp=haucp∪Hl；

7.Hl=Ø；

8.l=l+1；

9.Cl=generate_candidate_co-location_pattern（Cl-1）；

10.Tl=generate_table_instance（Cl，Tl-1，d）；

11.done

12.return haucp

尽管HAUCP_BA 能够有效从空间数据集中发现高平均效用co-location 模式的完全集，但是大量连接操作和巨大搜索空间所产生的计算成本让用户难以承受。空间co-location 模式挖掘满足反单调性〔1〕，可以有效减少连接操作和搜索空间，然而，HAUCP_BA 算法并不满足反单调性。例如，在图1和表1 当中，如果模式c=｛A，B｝⊂c'=｛A，B，C｝，则c和c'的表实例分别为table_instance（c）=｛｛A.1，B.1｝，｛A.2，B.4｝，｛A.3，B.3｝｝、table_instance（c'）=｛｛A.2，B.4，C.2｝，｛A.3，B.3，C.1｝｝，根据空间高效用colocation 模式的相关定义可计算出au（c）=（11+15）/2=13、au（c'）=（8+10+25）/3= 14.3。假定min_au=14，则有au（c）min_au，所以，HAUCP_BA 算法不满足反单调性，对空间高平均效用co-location 模式挖掘算法的效率提出了巨大挑战。

3.2 剪枝算法为了减少不同特征的实例之间的连接操作和搜索空间的巨大耗费，提出了两种有效的剪枝策略，并进一步构建了高效的剪枝算法。

剪枝策略1假设两个k（k≥2）阶模式c'和c"的前k-1 个特征是相同的，经过连接后产生（k+1）阶候选模式ck+1。如果两个模式的平均效用满足au（c'）＜min_au，au（c"）＜min_au 且模式c'或c"的前k-1 个特征的平均效用大于或等于min_au，那么候选模式ck+1不是一个高平均效用co-location 模式。

证明：假定两个k（k≥2）模式c' 和c"分别为c'＝｛f1，f2，…，fk-1，fk'｝，c"＝｛f1，f2，…，fk-1，fk"｝，其中fk'≠fk"，ck+1＝c' c"＝｛f1，f2，…，fk-1，fk'，fk"｝。由于au（c'）＜min_au，au（c"）＜min_au，则可以推导出pu（c'）＜k×min_au，pu（c"）＜k×min_au，两边相加则有pu（c'）+pu（c"）＜2×k×min_au，可进一步得出：2×pu（ck-1in c'）+ fpu（c'，fk'）+ fpu（c"，fk"）＜2×k×min_au，因为au（ck－1in c'）≥min_au，所以pu（ck－1in c'）+fpu（c'，fk'）+ fpu（c"，fk"）＜2×k×min_au－（k－1）×min_au=（k+1）×min_au。根据空间co-location 模式挖掘算法满足反单调性，可以得到pu（ck－1in ck＋1）≤pu（ck－1in c'），fpu（ck＋1，fk'）≤fpu（c'，fk'）和fpu（ck＋1，f"）≤fpu（c"，fk"）。因此pu（ck－1in ck＋1）+fpu（ck＋1，fk"）≤（k+1）×min_au 得出剪枝策略1 是成立的。

剪枝策略2如果一个k 阶模式c 的所有k-1阶子模式的平均效用值均小于min_au，那么c 为非高平均效用co-location 模式。

证明：假设c＝｛f1，f2，…，fk｝，则模式c 有k 个k-1 阶子模式，即c1k-1＝｛f1，f2，…，fk-1｝，c2k-1＝｛f1，f3，…，fk｝等等。因为所有的k-1 阶子模式的平均效用值小于min_au，所以（c2k-1）＜min_au 等等，将这k 个不等式进行相加可以得到由空间colocation 模式挖掘算法满足反单调性可知，特征fi（fi∈c 且fi∈ck-1）在模式c 中的任意一个实例的外效用不大于其在子模式ck-1中的同一实例的外效用，由此可以得到pu（c）＜k×min_au，即au（c）＜min_au，所以c 不是一个高平均效用co-location 模式，剪枝策略2 成立。

接下来，基于剪枝策略1 和剪枝策略2 构建了高效的剪枝算法HAUCP_IA，具体描述如下：

算法2高平均效用co-location 模式挖掘优化算法HAUCP_IA

输入：

a.布尔空间特征集合F=｛f1，f2，…，fk｝；

b.空间实例及其外部权重集合S=｛（o1，ieu（o1）），（o2，ieu（o2）），…，（on，ieu（on））｝；

c.最小距离阈值d；

d.最小平均效用阈值min_au。

输出：

高平均效用co-location 模式集合haucp。

变量：模式长度l；长度为l 的候选co-location模式集合Cl；利用剪枝策略1 进行剪枝后的长度为l 的候选co-location 模式集合Cl'；利用剪枝策略2进行剪枝后的长度为l 的候选co-location 模式集合Cl"；Cl中co-location 模式的表实例的集合Tl；长度为l 的高平均效用co-location 模式集合Hl；长度为l 的非高平均效用co-location 模式集合Ll。

步骤：

1.l=1；Cl=F；Hl=Ø；temp=Ø；Ll=Ø；Cl'＝Ø；Cl"＝Ø；

2.Tl=generate_table_instance（Cl，S，d）；

3.while l≤k

4.do

5.if l<2 then

6.Hl=select_high_average-utility_co-location_pattern（Cl，S，Tl，min_au）；

7.Ll=Cl-Hl；

8.else

9.Cl'=generate_pruned_co-location_pattern（Cl，l≥3，Ll-1）；

10.Cl" =generate_pruned_co -location_pattern（Cl-Cl'，l≥2，Ll-1）；

11.temp=Cl；

12.Cl=Cl-Cl'-Cl"；

13.Tl=generate_table_instance（Cl，Tl-1，d）；

14.Hl=select_high_average-utility_co-location_pattern（Cl，S，Tl，min_au）；

15.Cl=temp；

16.Ll=Cl-Hl；

17.haucp=haucp∪Hl；

18.l=l+1；

19.Cl=generate_candidate_co-location_pattern（Cl-1）；

20.Hl=Ø；Ll=Ø；Cl'＝Ø；Cl"＝Ø；

21.done

22.return haucp

首先，计算了一阶模式的表实例、高平均效用co-location 模式和非高平均效用co-location 模式。其次，对于k（k≥2）阶候选模式ck，进一步基于剪枝策略1 和剪枝策略2 排除了所有的非高平均效用co-location 模式，并计算保留的候选模式的表实例，得到所有k 阶高平均效用co-location 模式。最后，由于高平均效用co-location 模式挖掘算法不满足反单调性，所以，将所有k 阶候选模式连接生成k+1 阶候选模式，继续判断模式是否为高平均效用co-location模式，并返回所有高平均效用co-location 模式。

4 实验与结果

以下呈现实验所需要的真实数据集、合成数据集和相关的默认参数，并在真实数据集和合成数据集上，对所提出的基本算法HAUCP_BA 和剪枝算法HAUCP_IA 的有效性、可扩展性进行大量实验。

4.1 实验环境和数据集本文所有实验都是基于Intel Core i5-8500 CPU 3.00 GHz、8 GB 内存的硬件平台和Windows 10 操作系统、Python 3.7 的软件平台进行的。

真实数据集来源于重庆POI（Point of Interest）数据集，共有18 个特征和141 785 个实例，分别表示宾馆、学校、医院、购物商场等事物。实验过程中运行的样本是通过非重复抽样从真实数据集中获取的，具体样本大小和参数见表2。

表2 基于真实数据集的样本相关参数

合成数据集通过随机的方式产生，共包含18个特征和138 422 个实例，每个实例的坐标范围为［1，10 000］，实验过程中运行的样本是通过非重复抽样从合成数据集中获取的，具体样本大小和参数见表3。

表3 基于合成数据集的样本相关参数

4.2 算法性能评估首先，在距离阈值和最小高平均效用阈值采用默认值的情况下，在真实样本和合成样本下测试了基本算法HAUCP_BA 和剪枝算法HAUCP_IA 的运行效率，并对两个算法的运行效率进行对比，见图2。

图2 不同数据集下算法的运行效率

随着样本数量的增多，无论是基本算法HAUCP_BA，还是剪枝算法HAUCP_IA 中实例连接的数目也会不断增多，算法的运行时间会呈上升趋势。由于剪枝策略1 和剪枝策略2 主要是针对效用进行剪枝，因此，剪枝策略在样本数量变化中没有起到好的效果。

其次，在样本数量和最小高平均效用阈值采用默认值的情况下，基于真实样本和合成样本测试了HAUCP_BA 和HAUCP_IA 在不同距离阈值下的运行效率，并对两个算法的运行效率进行了对比，见图3。

图3 不同距离阈值下算法的运行效率

距离阈值的增大，会导致不同特征的更多实例处于同一邻近区域内，模式表实例的个数也会随之增多，连接操作也会随之增多，算法运行时间会呈现上升趋势，由于最小高平均效用阈值仍采用默认值，剪枝效果仍然不明显。

最后，在样本数量和距离阈值采用默认值的情况下，基于真实样本和合成样本测试了HAUCP_BA和HAUCP_IA 在不同的最小高平均效用阈值下的运行效率，并对两个算法的运行效率进行了对比，见图4。

图4 最小高平均效用阈值对算法运行效率的影响

由于高平均效用算法不满足反单调性，因此，需要考虑计算每个候选模式是否为高效用colocation 模式，所以整体的连接操作变化不大，算法的运行时间波动也不大，然而，采用剪枝策略后，减少了部分模式的效用值计算，剪枝算法的效率要高于基本算法的效率。

4.3 实验结果与分析数据集或距离阈值的不断增大导致不同特征实例连接的数目随之增大，根据特征实例内部效用的定义可知，实例的内部效用也会不断增大。然而，最小高平均效用阈值是由用户或领域专家设定的，因此，在设定的最小高平均效用阈值下，高平均效用模式的数目会不断增加，但是，随着最小高平均效用阈值的增大，符合高平均效用co-location 模式的数目也会不断减少。同时，为了进一步证明模式的长度越大，模式的总效用值越大，其成为高效用模式的概率也越大。在相关参数采用默认值的情况下，基于真实样本和合成样本，将高平均效用co-location 模式挖掘算法（简称为HAUCP 算法）与不考虑模式长度的高效用colocation 模式挖掘算法（简称为HUCPM 算法）的挖掘结果进行了对比，见图5~6。

图5 真实数据集下HAUCP 和HUCPM 算法挖掘结果对比

图6 合成数据集下HAUCP 和HUCPM 算法挖掘结果对比

从图5~6 中可以得出：模式的长度对模式的效用值有一定的影响，因此，在考虑模式长度的情况下，挖掘出的高平均效用co-location 模式更符合实际，对决策支持更有价值。

5 结论

本文基于空间数据库，主要考虑模式长度对高效用co-location 模式的影响，提出高平均效用colocation 模式挖掘的相关定义、基本算法和剪枝策略。最终，在真实数据集和合成数据集上进行充分实验，实验结果表明：模式长度对高效用co-location模式有一定影响，高平均效用co-location 模式挖掘比高效用co-location 模式挖掘更符合实际需求。由于高平均效用模式挖掘算法不满足反单调性，计算所有模式的表实例所带来的时间耗费过长，虽然本文提出了两个针对性的剪枝策略，但是，剪枝效果并不明显，因此，在未来的工作中，我们将继续研究高平均效用co-location 模式挖掘的剪枝算法，进一步提高算法的挖掘效率。