-
空间同位模式挖掘是空间数据挖掘的一个重要分支，能够有效发现多类地理事件间的共生关联关系，现已被广泛应用于生态环境、公共安全、商业选址、移动通信和交通运输等领域[1-2]。然而，由于地理事件具有空间异质特性[3-5]，不同的地理事件经常仅在特定子空间内的邻近位置上频繁并发，发现此类空间模式(即局部空间同位模式)有助于深入理解不同空间现象在微观层次上的空间作用关系[6]。
近年来，在全局空间同位模式挖掘模型[7-8]的基础之上，通过特定的区域划分策略或空间聚类手段，发展了一系列的局部空间同位模式挖掘方法。区域划分的策略旨在将全局空间预先划分为一系列的子区域，进而在子区域内采用全局模型提取局部空间同位模式，主要的区域划分方法有四叉树分区法[9]和k-邻近图分区法[10]。此类策略能够发现一些从全局视角难以发现的局部空间同位模式，但是其挖掘结果依赖于区域划分方法的选择，且人为划分的区域难以真实反映空间同位模式的空间分布结构。为此，一些学者进一步借助空间聚类的思想，分别探测每个候选模式频繁出现的局部热点区域[11-13]。此类方法能够有效区分不同局部空间同位模式分布区域的差异，但是大多需要对所有候选模式执行聚类操作，当空间变量种类众多时，将面临巨大的计算量。为此，文献[14]结合区域划分和空间聚类的优点，提出一种混合的策略，首先利用某个兴趣事件的热点对全局空间进行划分，进而在每个划分中提取与兴趣事件相关的局部同位模式，然后采用多分辨率格网聚类的方法界定每个局部模式的有效分布范围。该方法虽然可以首先剔除一些无效模式，但是其空间划分结果仍然会割裂局部空间同位模式原有的分布结构，进而可能导致某些有效模式的遗漏。
上述方法能够从一定程度上缓解空间异质性对空间同位模式挖掘带来的挑战，但是在挖掘过程中涉及过多的参数设置，在实际应用中由于缺乏相应的领域知识，将难以获得客观的挖掘结果。主要体现在以下两个方面：①现有局部空间同位模式挖掘的研究工作中几乎所有方法都需要预先设置频繁度阈值来评定空间同位模式的频繁度，阈值设置较高将可能遗漏某些有效模式，反之将可能得到某些无效模式；②局部空间同位模式的分布区域提取需要设置空间划分参数或聚类参数，不合理的参数设置会破坏局部空间同位模式自身潜在的空间分布结构。针对以上问题，本文基于非参数统计和自适应聚类的思想，提出一种显著局部空间同位模式自动探测方法。
HTML
-
为了减少人为参数设置对局部空间同位模式的频繁度度量和分布区域提取这两个过程的影响，分别给出相应的研究策略。
1) 空间同位模式的频繁度实际上描述的是多类地理事件间的空间依赖关系，空间统计学中常通过建立两类事件分布相互独立的零假设，对多元点模式的空间依赖关系进行测试[15-17]。仿照该统计思想，将空间同位模式的频繁程度建模为显著性水平，通过非参数模式重建方法[18]构建模拟数据，进而识别统计上显著的空间同位模式。
2) 由于空间同位模式包含多类地理事件，不同空间同位模式的分布各异，传统聚类方法仅能探测单类地理事件的分布热点，且参数设置困难，难以处理分布复杂的空间数据。为此，首先对空间同位模式的实例位置进行建模，将其作为空间聚类的对象，进而借助自适应空间聚类方法[19]自动提取空间同位模式的分布区域。
-
空间同位模式显著性判别的零模型需要在消除多类地理事件间分布依赖性的同时，保持单类地理事件自身的分布特征[17, 20]。本文借助一种非参数模式重建方法[18]构建零模型，相比于其他已有方法(如空间点过程方法[15, 21]和环形移动方法[22])，模式重建方法无需对数据的零分布做先验性假设，且不会破坏原始数据的分布结构。
首先，针对每个地理事件，采用多个空间统计量来刻画其原始数据OD(original data)的分布特征。进而生成与原始数据OD实例个数相同的随机数据SD(stochastic data)，通过不断优化随机数据，使其与原始数据的分布特征尽可能的相似，优化过程的目标函数E(SD)表达如下：
式中，fi(OD, r)和fi(SD, r)分别表示原始和随机数据中第i个空间统计量在邻域距离r上的统计值；wi和Ri分别表示第i个空间统计量的权重和自变量取值范围；I表示空间统计量的个数。
为了在对数据分布特征详尽描述的同时，减少不同统计量间描述信息的冗余，本文共选取对相关函数g(r)、最邻近分布函数D(r)和球面接触分布函数Hs(r)进行模式重建，分别用于描述数据的二阶统计特征、最邻近统计特征和形态学统计特征[24]。如图 1所示，分别对事件A和B进行模式重建，模拟数据中很好地保持了原始数据中每类事件的分布特征。
Figure 1. Construction of Null Model Based on Pattern Reconstruction
进一步，用参与指数(participate index, PI)[1]作为检验统计量，判别空间同位模式的显著性。参与指数是空间同位模式的频繁度度量指标，具体表达为：
式中，#(instances(fi))表示事件fi的实例个数; #(πfi(instances(CP)))表示事件fi参与同位模式CP(colocation pattern)的实例个数。进而，通过大量的模拟数据计算零假设下同位模式CP参与指数的实验分布，由此可以计算出空间同位模式CP参与指数的显著性p值：
式中，PISDn(CP)和PIOD(CP)分别表示第n组模拟数据集和原始数据集中同位模式CP的参与指数; n表示模式重建次数。给定显著性水平α，若同位模式CP的显著性pV≤α，则拒绝零假设，将该模式识别为显著空间同位模式。
-
针对每个同位模式，首先采用§2.1方法检测其全局显著性，若不显著，则将其视为候选局部模式。进而采用自适应空间聚类方法[19]提取候选局部模式的分布热点。空间同位模式每个实例虽然包含多个空间点，但是各空间点彼此邻近，因此，如图 2(a)所示，可用同位模式实例中各空间点的平均位置将该模式建模为特殊的单类地理事件。
Figure 2. Detection of Hot Spots of a Spatial Colocation Pattern Based on Adaptive Clustering Method
如图 2(b)所示，对此特殊地理事件的空间位置构建Delaunay三角网DTN(delay tolerant network)。先从全局层次对三角网DTN的边长施加约束，对于每个空间点Pi，删除与其直接相连的边中长度大于全局边长统计量GET(Pi)的整体长边，表达式为：
其中，mean(DTN)和Variation(DTN)分别表示三角网DTN中所有边长的平均值和标准差; mean(NN1(Pi))表示与点Pi直接相连的所有边的平均长度。进一步对所剩的每个子图SGi，从局部层次删除每个空间点Pi二阶邻域内边长大于局部边长统计量LET(Pi)的局部长边，表达式为：
式中，mean(NN2(Pi))表示空间点Pi二阶邻域内所有边长的平均值; Variation(NN1(Pk))表示子图SGi中与空间点Pk直接相连的所有边的长度标准差; #(SGi)表示子图SGi中空间点的个数。如图 2(c)所示，删除整体长边和局部长边后，三角网DTN被划分为一系列的子图，每个子图即为该候选局部模式的分布热点。
-
为进一步检验候选模式的局部显著性，需要描绘候选模式的热点区域。如图 3(a)所示，对于候选局部模式的每个分布热点，分别构建Delaunay三角网DTNi连接所有空间点。根据三角网中的边长统计量定义长边，表达式为：
式中，mean(DTNi)和Variation(DTNi)分别表示三角网DTNi中所有边长的平均值和标准差。通过删除包含任一长边的三角形，对三角网DTNi进行修剪；将修剪后的三角网中的非公共边视为边界边，由边界边包围的区域即为该候选模式的热点区域，如图 3(b)所示。
Figure 3. Delineation of Hot Spots Based on Delaunay DTN
不断将热点区域向外扩展，在局部区域内对该模式的显著性进行测试。如果发现任一显著性小于等于给定显著性水平α的区域，则将该候选模式识别为显著局部空间同位模式，并将相应的区域定义为显著区域。各个显著区域继续扩展至该模式的局部显著性消失，最终将最大的显著区域识别为该显著局部模式的有效区域。
2.1. 基于模式重建的空间同位模式显著性判别
2.2. 基于自适应聚类的候选局部模式热点探测
2.3. 显著局部空间同位模式的有效区域提取
-
为了验证本文方法的有效性，分别采用包含预设模式的模拟数据与实际生态群落数据进行实验分析，并与Ding等人提出的方法[14](简称MRG)进行比较。为了使MRG算法适用于本文的实验数据和目的，实验中首先对研究区域施加规则格网，进而将包含任意事件的格网定义为空间事务，并按原文建议设置算法参数。本文方法中全局和局部的模式重建次数均设为99，空间同位模式的显著性水平设为0.05。实验测试环境为Windows 10系统，CPU 2.50 GHz，内存8 GB。
-
模拟数据集如图 4所示，其中事件A、B和C均具有预设的聚集结构，且不同类型之间包含相互重叠的空间簇，事件D为随机分布的干扰事件。模拟实验中采用Yoo等人[25]的建议，借助L函数估计合适的邻域距离，估计结果见图 5。
Figure 4. Simulated Dataset
Figure 5. Results of cross-K Function for Features A and B
本文方法自动探测的结果如表 1所示，包含3个显著局部空间同位模式{A，B}、{A，C}、{B，C}和1个显著全局空间同位模式{A，B，C}。以空间同位模式{A，B}为例，进一步采用cross-K函数[24]验证挖掘结果的正确性。如图 5(a)所示，全局范围内事件A和B的cross-K函数计算结果表明两者之间没有显著的空间依赖关系，本文方法全局判别结果与其吻合。如图 6(a)所示，本文方法进一步自适应提取了模式{A，B}的热点区域及其有效范围。如图 5(b)所示，采用cross-K函数对有效范围内两类事件的空间依赖性进行验证，发现事件A和B之间具有显著的空间依赖性。因此，本文方法能够准确识别局部空间同位模式，且能有效剔除随机事件对结果的影响。
同位模式 全局 局部 PI pV PI PI $\underline {pv} $ $\overline {pv} $ {A, B} 0.32 0.17 0.50 0.78 0.01 0.04 {A, C} 0.33 0.20 0.67 0.71 0.01 0.04 {B, C} 0.19 0.38 0.78 1.00 0.02 0.03 {A, B, C} 0.19 0.05 - - - - 注：PI和PI为最小和最大局部参与指数; $\underline {pv} $和$\overline {pv} $为最小和最大局部p值 Table 1. Results of Our Method on the Simulated Dataset
Figure 6. Regional Pattern {A, B} Detected by Our Method
为了与本文方法进行对比分析，进一步采用MRG算法进行实验。对于MRG算法，用10×10的规则格网构建空间事务，采用初始单元大小为50×50、终止单元大小为12.5×12.5的多分辨率格网探测各类事件的热点区域，但未探测出任何事件的热点。因为对于每类事件，模拟数据中都不存在出现概率大于其全局概率的人造格网，从而MRG算法不能从本文模拟数据中发现任何局部空间同位模式。
以空间同位模式{A，B}为例，从效率和稳定性两个方面测试模式重建次数设置对本文方法挖掘结果的影响，每种重建次数都实验20次，取其运行时间的平均值衡量算法效率，并以全局p值和有效区域内局部p值的标准差衡量算法稳定性。如表 2所示，运行时间与重建次数呈线性增长关系，当重建结果大于等于99次时，算法挖掘结果趋于稳定。现有研究亦发现，在显著性水平为0.05时，99次模拟次数能够保证多数应用的可靠性[26]。
算法性能 模式重建次数 49 99 499 999 4 999 运行时间/s 3.010 5.858 29.763 59.642 291.312 全局p值标准差 0.025 0.016 0.013 0.012 0.010 局部p值标准差 0.020 0.011 0.009 0.010 0.008 Table 2. Effects of the Simulation Times on Our Method
-
进一步采用本文方法探测湿地生态数据集中的局部共生关系，以验证本文方法的实际应用效果。在湿地生态系统中，存在复杂的植被种间关系，且易受生长环境的不同而发生显著变化[27-28]，探测湿地物种间的局部共生关系对于研究生态群落结构、维持生态系统平衡、保护物种多样性和促进环境可持续发展都有着重要的现实意义。本文选取中国东北地区某湿地的5种沼泽植被(毛果苔草、漂筏苔草、狭叶甜茅、小叶章和沼柳)进行实验分析，5种沼泽植被的空间分布如图 7所示，分别有666、1 039、1 660、387和2 555个实例。
Figure 7. Study Area and Locations of Five Types of Wetland Species
生态学中，不同生态物种间的相互作用关系可能存在显著差异[28]，因此采用单一邻域距离挖掘空间同位模式难以准确发现共生物种。本文采用Barua等人[29]的建议，设置了多个邻域距离(50 m、100 m和150 m)进行实验分析，探测结果如表 3所示。分析实验结果，可以发现：①部分显著空间同位模式的参与指数很低，现有方法设置较高的参与指数阈值可能会遗漏这些模式，本文方法通过对空间同位模式的显著性进行非参数检验，能够更加客观地评价空间同位模式的频繁程度；②在50 m的邻域距离下主要发现了一些显著全局空间同位模式；随着邻域距离的增加，部分全局模式会逐渐退化为局部模式，甚至消失，有些局部模式也会逐渐消失，同时也出现了一些新的局部模式；另外，也有一些显著同位模式的空间层次不会随着邻域距离的变化而变化，说明这些植被之间具有稳定的共生关系，对湿地生态系统构成起主导性作用。
显著空间同位模式 邻域距离50 m 邻域距离100 m 邻域距离150 m 全局 局部 全局 局部 全局 局部 PI pV PI PI $\underline {pv} $ $\overline {pv} $ PI pV PI PI $\underline {pv} $ $\overline {pv} $ PI pV PI PI $\underline {pv} $ $\overline {pv} $ {小叶章, 沼柳} 0.20 0.54 0.47 0.92 0.01 0.05 - - - - - - - - - - - - {毛果苔草, 狭叶甜茅} 0.65 0.01 - - - - 0.86 0.01 - - - - 0.93 0.01 - - - - {毛果苔草, 沼柳} 0.37 0.01 - - - - 0.60 0.01 - - - - 0.68 0.20 0.86 0.94 0.03 0.05 {漂筏苔草, 狭叶甜茅} - - - - - - 0.26 1.00 0.32 0.57 0.01 0.04 0.39 1.00 0.40 1.00 0.02 0.02 {漂筏苔草, 小叶章} 0.31 0.03 - - - - - - - - - - - - - - - - {漂筏苔草, 沼柳} 0.33 0.83 0.65 0.94 0.01 0.05 0.46 1.00 0.99 1.00 0.03 0.04 0.54 1.00 1.00 1.00 0.02 0.02 {狭叶甜茅, 沼柳} 0.70 0.01 - - - - 0.80 0.15 0.29 0.99 0.01 0.05 0.88 0.95 0.41 1.00 0.01 0.05 {小叶章, 沼柳} 0.20 0.54 0.47 0.92 0.01 0.05 - - - - - - - - - - - - {毛果苔草, 漂筏苔草, 狭叶甜茅} - - - - - - 0.17 0.99 1.00 1.00 0.03 0.03 0.29 1.00 0.35 0.99 0.03 0.04 {毛果苔草, 漂筏苔草, 沼柳} - - - - - - - - - - - - 0.25 1.00 0.33 0.33 0.04 0.04 {毛果苔草, 狭叶甜茅, 沼柳} 0.35 0.01 - - - - 0.60 0.01 - - - - 0.67 0.02 - - - - {漂筏苔草, 狭叶甜茅, 小叶章} - - - - - - - - - - - - 0.03 1.00 1.00 1.00 0.02 0.03 {漂筏苔草, 狭叶甜茅, 沼柳} 0.08 1.00 0.16 0.29 0.01 0.04 0.25 1.00 0.28 1.00 0.01 0.04 0.39 1.00 0.38 1.00 0.02 0.05 {漂筏苔草, 小叶章, 沼柳} 0.16 0.01 - - - - - - - - - - - - - - - - {狭叶甜茅, 小叶章, 沼柳} - - - - - - 0.02 1.00 1.00 1.00 0.02 0.02 - - 1.00 1.00 0.02 0.02 注：PI和PI为最小和最大局部参与指数; $\underline {pv} $和$\overline {pv} $为最小和最大局部p值 Table 3. Significant Spatial Colocation Patterns Detected by Our Method
采用MRG算法进一步比较分析。采用100 m×100 m的规则格网定义空间事务, 结果仅发现了小叶章的热点区域，并挖掘出2个包含小叶章的局部同位模式{漂筏苔草，小叶章}和{小叶章，沼柳}，其有效边界分别如图 8(a)和8(b)所示。可见，MRG算法受限于人工格网的划分，导致探测的局部模式不完整，且局部模式的有效区域被人为切边，难以反映局部同位模式自然的分布结构。
Figure 8. Results of MRG Method on the Real Dataset
实际应用中, 本文方法的运行效率主要取决于3个部分：①所有可能模式的全局显著性检验，其时间复杂度约为O(N·2K)，其中N为模式重建次数，K为地理事件类型数目；②每个候选局部模式的热点探测，其时间复杂度约为O(M·logM)，其中M为该候选模式的实例个数；③每个候选局部模式的局部显著性检验，针对每个局部区域，其时间复杂度约为O(N·X2)，其中X为该局部区域内该候选模式的实例个数。在较大的邻域距离下，每个可能模式的实例个数均会增加，且需要在局部层次进行检验的候选局部模式个数亦会增加，因此，如图 9所示，本文方法运行时间会随邻域距离的增加而显著增加。相比于现有方法，本文方法虽然计算量大，但是很大程度上降低了现有方法中参数设置的主观性。还可以结合空间索引和高性能计算等技术改善本文方法在实际应用中的计算效率。
Figure 9. Running Time of Our Method on the Real Dataset
3.1. 模拟实验与比较
3.2. 实际应用与分析
-
为了降低人为参数对局部同位模式挖掘结果的影响，本文提出了一种显著局部空间同位模式的自动探测方法。通过实验分析和比较发现，本文方法不仅能够有效识别统计上显著的局部空间同位模式，还能自适应地提取局部同位模式的分布区域和有效边界，从而能够更加客观地揭示地理事件间的相互作用关系。
进一步的研究工作主要集中于：①本文多类事件间邻域距离的选择具有一定的主观性，需要研究多元事件邻域的自适应构建方法；②局部空间同位模式热点区域生长采用的是各向等距离扩展的策略，还需要研究热点区域的有向扩展方法。
DownLoad:
