Spatial Scan Statistic Method for Discovering Regional Network Co-location Patterns

网络约束条件下的同位模式挖掘可为沿街设施选址、城市交通服务及产业分布等众多研究领域提供更深入、可靠的支持建议^[19-20]。现有欧氏空间的挖掘方法难以适应城市环境中地理事件的网络约束特性，可能造成局部同位模式的误判。如图 1所示，实心符号表示两类事件的实例互相邻近，若不顾及网络约束对A、B两类事件实例间邻近关系的影响，则会造成局部区域中包含错误的模式实例。

Figure 1.  Comparison of Regional Co-location Patterns in Euclidean Space and Network Space

本文基于扫描统计思想，将局部网络空间同位模式挖掘建模为网络约束下的二元空间扫描统计问题。首先，基于最短路径重新定义局部同位模式的兴趣度量指标与扫描统计量，将扫描单元沿路网进行扩展，识别使扫描统计量最大化的局部候选路径；其次，假设路网上不存在局部同位模式，即两类事件在全局路网上的关联强度基本一致，基于网络约束下的二元泊松分布对该零假设进行建模，借助假设检验对候选路径上局部同位模式的有效性进行评价。

空间扫描统计方法是识别地理事件聚集模式的重要手段，基本思想是计算研究区域中所有扫描窗口内事件聚集统计量，并筛选出具有最大统计量的局部区域，借助假设检验发现显著的聚集模式。传统的空间扫描统计方法仅针对欧氏空间内的一元空间数据，难以适用于本文的数据类型与研究任务。因此，本文定义了新的扫描统计量（即网络参与概率比），用于评价网络约束下不同地理事件间的邻近频繁程度，并将路径单元定义为基本扫描单元，发展了网络约束下的路径扩展策略，用于发现局部网络空间同位模式的候选路径。

给定研究区域内的全局路网N，A、B两类事件实例e（A）与e（B），以及局部路径L，路径扩展过程中的同位模式兴趣度量指标以及扫描统计量的定义如下：

定义1：网络参与概率（NP）。局部路径L上A类事件周围B类事件的网络参与率定义为L上存在邻近的B类事件实例的A类事件实例数目与L上A类事件实例总数的比值，表达为：

式中，$D\left(e(A),e(B)\right)$为A、B两类事件实例间的最短路径距离；d为网络距离阈值。

定义2：网络参与概率比（NR）。网络空间同位模式的扫描统计量定义为A、B事件在局部路径L上与L外的网络参与概率比值，表达为：

图 2（d）所示蓝色局部路径L上，A类事件实例数目为2，其中邻近网络距离内存在B类事件实例的数目为2；L外A类事件实例数目为7，其中，邻近距离存在B类事件实例的数目为3。因此，$\mathrm{N}\mathrm{P}(A\to B,L)=\mathrm{2}/\mathrm{2}$，$\mathrm{N}\mathrm{R}(A\to B,L)=\mathrm{7}/\mathrm{3}$。

Figure 2.  Example of Network-Constrained Path Expansion Method

基于以上定义，网络约束下路径扩展方法的具体步骤描述如下：

1）初始化扫描路径。对于全局路网N中的每个路段，将其等分为长度为r的路径单元；定义初始扫描路径及其初始位置（图 2（a）蓝色路径）。

2）扩展扫描路径。将当前扫描路径进行路径扩展（见图 2（b）），随机选取与扫描路径邻接的K组路径单元，每组包含M个路径单元，选取其中使扫描统计量（即$\mathrm{N}\mathrm{R}(A\to B,L)$）获得最大增量的一组路径单元进行扩展，得到扩展后的扫描路径。重复以上步骤，直至$\mathrm{N}\mathrm{R}(A\to B,L)$取得最大值，并返回当前扫描路径。

3）遍历扫描路径。移动初始扫描路径的位置（见图 2（c）），并返回步骤2）。重复以上步骤，直至遍历路网中的所有可能位置，将具有最大扫描统计量的局部路径识别为该局部模式的候选路径L_c，并输出其对应的扫描统计量取值，记为S_obs（见图 2（d））。

为排除偶然发生的随机现象，本文采用蒙特卡罗模拟实验对候选路径内局部同位模式的显著性进行检验。假设研究区域内两类事件在全局路网上具有一致的同现概率，即不存在具有显著高于期望水平的局部路径。为构建该零假设，本文借助二元泊松点过程^[22-23]的思想在网络空间内生成大量模拟数据，其步骤描述如下：

1）利用期望值最大算法^[17，24]估计观测数据中A、B两类事件单独发生的概率r_A、r_B及联合发生的概率r_AB。

2）在研究区域内的全局路网N上利用强度为$r_A+r_B+r_{AB}$的一元泊松点过程生成随机分布的空间数据集P。

3）对P中每个空间点的类型进行标记，被标记为独立发生的A类事件的比率为$r_A/(r_A+r_B+r_{AB})$，被标记为独立发生的B类事件的比率为$r_B/(r_A+r_B+r_{AB})$，被标记为与B类事件同现的A类事件比率为$r_{AB}/(r_A+r_B+r_{AB})$。

选取扫描统计量网络参与概率比作为显著性判别的检验统计量。对于每一组模拟数据集，均采用路径扩展方法找到具有最大扫描统计量的局部路径及其对应的扫描统计量取值，记为$S_{\mathrm{s}\mathrm{i}\mathrm{m}}^i$。局部网络空间同位模式候选路径L_c的p值定义为零假设下$S_{\mathrm{s}\mathrm{i}\mathrm{m}}^i$大于等于观测值S_obs的概率，表达为：

式中，I为模拟数据集数目。给定显著性水平α（通常设为0.05），如果p值小于等于α，则拒绝零假设，认为路径L_c上局部同位模式的发生并非偶然事件，并将L_c识别为局部同位模式的显著路径；否则，接受零假设，认为研究区域内不存在局部网络空间同位模式。

为验证方法的有效性，本文通过包含预设局部网络空间同位模式的模拟实验，将本文方法与现有欧氏空间显著局部同位模式的挖掘方法^[17]进行对比。实验中，将两种方法的邻近距离阈值d设为5，扫描单元组数K设为5，每组包含单元个数M设为2，模拟数据集数目设为999。两组包含预设局部同位模式的模拟数据集（simulated dataset，SD）如图 3所示。

Figure 3.  Simulated Dataset and Preset Patterns

模拟数据集1：如图 3（a）所示，SD₁预设有一个含有局部网络空间同位模式的路径（阴影区域）及一个非局部网络同位模式的干扰区域（虚线区域）。

模拟数据集2：如图 3（b）所示，SD₂预设有一个含有局部网络空间同位模式的路径（阴影区域），且在预设路径周围设置了若干干扰实例。

采用两种方法在两组模拟数据中挖掘到的局部同位模式如图 4和图 5所示。可以发现，本文方法能够有效地顾及网络约束对局部同位模式探测的影响，识别结果与预设模式一致，而现有方法缺乏建模网络约束的能力，进而可能造成结果的误判。

Figure 4.  SD₁ Simulated Experiment

Figure 5.  SD₂ Simulated Experiment

SD₁结果分析：如图 4所示，本文方法准确得到了预设有局部同位模式的路径。现有方法识别的局部区域中，尽管两类事件实例间欧氏距离较近，具有较高的欧氏参与概率比（值为2.58），但事件实例大多分布于不同的道路（如图 4（b）中“×”标注的A类事件实例与区域中的B类事件实例），网络参与概率比很低（值为0.86）。现有方法构建实例邻域时没有顾及网络空间中事件实例受到路网约束这一特性，采用欧氏距离定义事件实例间的邻近关系，高估了两类事件的同现频率。

SD₂结果分析：如图 5所示，两种方法得到的局部同位模式位置相近，但本文方法通过扫描邻近路段的方式挖掘局部同位模式，避开了分布于不同道路的事件实例，能够精细地定位出现同位模式的局部路径，其网络参与概率比为2.43。相比之下，现有方法识别的区域更大，其中包含了在欧氏空间内与B类事件实例相互邻近的其他A类事件实例（如图 5（b）中“×”标注的A类事件实例），但两类事件实例间的网络距离大于所设的邻近距离阈值，不存在网络约束下相互邻近的同现关系。尽管该区域的欧氏参与概率比为2，但其网络参与概率比仅为1.63，小于本文所识别路径的概率比。

采用出租车供需数据进行应用分析，出租车供需分析对于促进出租车资源的优化配置和城市交通系统的协调运作具有重要意义^[25]。研究区域包含北京市五环内6个城区（东城区、西城区、朝阳区、海淀区、丰台区和大兴区），实验数据为北京市28 165辆出租车工作日2015-11-04T08：30、16：00及18：00的轨迹数据，从中分别提取各城区不同时刻的出行需求点（即乘客上车点）和出租车供应点（即出租车空载点）。实验中，以出租车需求点定义为式（2）中的A类事件，出租车供应点定义为式（2）中的B类事件，邻近距离阈值设为120 m，采用本文方法在6个区域中分别提取具有最大扫描统计量的局部网络空间同位模式，在其分布路径中出租车的供应对需求表现出高于预期的显著空间依赖性，将该路径识别为出租车供过于求的供需失衡模式，见图 6。

Figure 6.  Significant Regional Network Co-location Pattern with Maximum Scan Statistic in Different Districts

08：30出租车供需失衡路径挖掘结果如图‍6‍（a）所示，6个城区的供需失衡路径大致分布在大型的休闲娱乐场所附近，包括东直门南大街来福士中心附近、广安门北滨河路深圳大厦附近、北三环东路时间国际附近、西四环中路五棵松公园附近、西三环中路莲花池公园附近及德贤路六合庄附近。16：00出租车供需失衡路径挖掘结果图 6（b）所示，包括东直门南大街来福士中心附近、复兴门北顺南路百盛购物中心附近、北三环东路曙光西里附近、北四环西路中关村SOHO附近、广安路莲花池公园附近及德贤路红星楼小区附近，各城区供需失衡路径的周边环境存在较大差别：东城区及西城区的供需失衡路径分布在商业中心附近，朝阳区、丰台区、大兴区的供需失衡路径分布在住宅社区周边，而海淀区内的供需失衡路径则与中关村的科技园相邻。18：00出租车供需失衡路径挖掘结果如图 6（c）所示，包括东直门北大街国盛中心附近、广宁伯街平安大厦、东三环北路佳程广场附近、北四环西路科春社区附近、西三环中路莲花池西里社区附近以及万吉路清乐园小区附近，除东城区、西城区及朝阳区内供需失衡路径在大型商场附近外，其余城区内的供需失衡路径邻近住宅小区。可见早晚高峰时的商业娱乐中心及大型住宅区附近是出租车供应过量的多发区域，可能是因为上述区域人流量较大，出租车在此处逗留徘徊导致出租车空车过多，而在日常工作时间（如16：00），出租车供应过量的分布则差别较大。因此，建议出租车司机可在白天多前往需求较大的住宅区或办公商厦等场所，而在傍晚尽量不在住宅区停留。此外，通过对比同一城区在不同时刻的供需失衡路径发现，5个城区在16：00以及18：00发生出租车供需失衡路径位置均较为邻近；丰台区内3个时刻的供需失衡路径均位于经济活动更频繁、人流量更大的城区北部；东城区内的供需失衡路径则基本发生在东直门附近。

针对现有局部同位模式挖掘方法未顾及网络事件受路网约束的问题，本文基于扫描统计的思想，在候选路径探测以及显著性检验过程中充分考虑事件的网络约束特性，提出了局部网络空间同位模式的扫描统计方法。首先，通过网络约束下的路径扩展方法探测局部同位模式的候选路径；其次，以网络约束下空间点分布模型构建零假设，甄别具有统计显著性的局部网络空间同位模式的路径。采用模拟数据与现有方法进行对比分析，发现本文方法可以有效避免由欧氏距离邻近但网络距离偏远的事件实例导致的两类事件同现频率的错误估计问题，进而可以在网络空间内更加准确地定位两类事件具有显著同位关系的分布路径。运用本文方法分析了北京市不同城区在不同时空的出租车供需失衡模式，可有效辅助出租车在城市道路网络内的资源配置。

进一步研究将集中于以下两个方面：（1）本文方法只返回具有最大扫描统计量的区域，虽然用户可以根据需求指定网络局部同位模式的数量，但发展局部网络空间同位模式多个显著路径的探测方法仍是未来探究的方向；（2）显著性检验阶段利用二元泊松分布构建零模型，而现实中数据的分布情况是未知的，需要进一步降低零模型构建对先验假设的依赖。