基于有向频繁子图挖掘的移动性模式网络构建方法

张海涛，李济平，罗 城，冀 康，沈慧娴

(1.南京邮电大学 地理与生物信息学院，江苏 南京 210023 2.南京邮电大学 通信与信息工程学院，江苏 南京 210003)

随着通信技术、互联网的发展，提供位置服务智能终端的数量日益增加，产生了大量的移动轨迹数据［1］。将移动轨迹数据与众多行业的专题数据进行集成关联分析以及数据挖掘处理后，能发现含有丰富语义隐喻信息的移动性知识［2－6］。对获取的移动性知识进行研究分析，能为众多行业应用带来有效的辅助决策［7］。同时，移动性知识的分析方法还可为研究人口流动和经济、资源等具有动态变化特征的复杂系统提供重要支撑［8］。

当前对于移动性知识的研究，通常基于时空数据库的概念进行定义，主要包含关联规则［9］、序列模式［10］等简单移动性模式。分析单一的简单移动性知识，不容易找出其中的关联关系和整体结构特性。而基于简单移动性知识间的共同项构建移动性模式网络［11－12］，通过分析网络的结构特征，可以发现移动性模式形成的潜在规律。因此，从移动轨迹数据中挖掘移动性知识并构建复杂网络对于分析产生移动轨迹数据的复杂系统的特性具有重要意义。

目前，国内外学者提出了一些移动性知识复杂网络的构建方法［13］。典型的方法包括：2008年Lacasa等［14］首次提出的基于时间序列构建复杂网络的可视图建网算法。2009年Luque等［15］提出的一种便捷、效率高的水平可视图算法。但是，这两种方法主要应用于时间序列的数据处理，缺乏对数据空间特性的考虑。2018年汪佩佩［16］提出了一种基于图挖掘的移动性知识复杂网络构建方法。这种基于图论的构网方法，充分考虑了移动轨迹的空间特性，构建出的网络能够很大程度表现移动数据运动规律。但是该方法存在的主要问题是：没有考虑移动轨迹的有向性，构建的移动性模式网络为无向加权网络。这种方法很大程度上制约了对于移动性模式网络的进一步分析应用。因此，本文提出了基于有向图的频繁子图挖掘方法。

1 基本概念

1.1 移动性知识

移动性知识是指使用某种挖掘方法，依据设定的阈值，从大量移动轨迹数据中发现的某种频繁出现的规律性知识。简单的移动性知识包括：关联规则、序列模式等形式的移动性模式。其中，关联规则是数据库中支持度和置信度大于等于阈值的移动性模式。关联规则中的数据项目是并发关系，不区分发生的时间先后顺序。序列模式是数据库中支持度大于等于阈值的移动性模式。序列模式中的数据项目不指定具体的时间，只区分时间先后顺序。本文构建移动性模式网络中使用的移动轨迹频繁子图［17］可视为序列模式的图形式表达。

1.2 复杂网络

复杂网络［18］是复杂系统的拓扑抽象。点和边是复杂网络的基本构成单元。依据边是否具有方向，网络进一步分为有向网络和无向网络。分析复杂网络的结构特性，可以了解复杂系统的宏观特征，发现隐藏复杂系统中的机制规律。复杂网络的结构特性主要包括：节点的度和度分布、平均最短路径长度、聚集系数等。

从移动轨迹数据构建的移动性模式网络，实际是有向加权的地理空间交互网络，其通常是诸如智能交通［19－21］、城市规划［22－24］、疾病传染［25－27］等大量具有地理空间特征的复杂系统拓扑抽象。本文重点关注移动性模式网络的节点度值、聚集系数这两类网络特征。

2 基于有向频繁子图挖掘的移动性模式网络构建方法

网络构建方法包含两个阶段：基于有向图的频繁子图挖掘，从移动轨迹有向图中挖掘频繁子图；使用大数据计算平台Apache Spark的图并行计算引擎GraphX实现频繁子图连接和网络构建。首先给出方法涉及的基本定义，然后进行算法设计和实例分析。

2.1 基本定义

定义1 移动轨迹定义为移动对象的时空演变，表示为 T ＝ ｛（tp1，t1），（tp2，t2），…，（tpn，tn）｝。其中，n表示对象在运动过程中记录采样点的数量；tpi表示第i个轨迹点；ti表示第i个时间间隔；tpi在tpi＋1之前出现。

定义2 移动轨迹有向图定义为G＝｛V（G），E（G），L（V（G）），L（E（G）），L｝。 其中， V（G） 为图G中节点的集合，对应于移动轨迹中的轨迹点tpi（i∈n）；E（G） ＝ ｛ek＝ （vi，vj） ｜vi，vj∈ V（G）｝ 为图G中边的集合，对应于移动轨迹中的轨迹点间的演变 （tpi→ tpj｜i，j ∈ n）；L（V（G）） ＝ ｛L（vi）｜∀vi∈V（G）｝为节点的标号集合， L（E（G）） ＝｛L（ek） ｜∀ek∈E（G）｝为边的标号集合，L为标号函数。

定义3 对于移动轨迹有向图G1，G2，如果存在映射函数 f：V（G1） → V（G2），满足条件： e ＝ （vi，vj） 是 G1的一条边， e′＝ （f（vi），f（vj）） 是 G2的一条边，则称图 G1，G2同构。

对于移动轨迹有向图 G，G′， 如果 V（G′） ⊆V（G） 且 E（G′） ⊆E（G） ，则称 G′是 G 的子图。 进一步给定移动轨迹有向图G″，若有图 G″和 G′同构，则称图G″和G是子图同构。

定义4 给定移动轨迹有向图数据库GD＝，若子图g与Gi子图同构，则δ（g，Gi） ＝ 1， 否则 δ（g，Gi） ＝ 0。

定义5 给定移动轨迹有向图数据库GD＝{G1，G2，…，Gn}， 设置最小支持度阈值为minsup。如果δ（g，GD）≥minsup，则称g是一个频繁子图。

定义6 给定频繁子图数据库gD＝｛g1，g2，…，gn｝，n≥1，频繁子图网络定义为：gN＝ ｛V，E｝，其中，V 为 gD中节点的集合，E ＝｛ek＝（vi，vj）｜vi，vj∈V｝为gD中边的集合。合并频繁子图数据库gD中的共同项可构建频繁子图网络gN。

定义7 给定移动轨迹有向图G，对于其中的任一有向边e＝（vi，vj），按照其两个节点标识、源节点标号、边标号、目标节点标号的顺序进行扩展，得到其对应的扩展边 e′＝ （vi，vj，li，li，lj）， 其中，边标号与源节点标号相同，表示边的有向性。按照深度优先遍历图G中所有边，得到对应扩展边的序列，记为图G的DFS编码。

定义8 一个图G可能生成多个DFS编码，对多个编码建立字典序，选择其中一个最小序来对图G进行唯一标识。其中，字典序定义为a≺b≺c≺…≺z和A≺B≺C≺…≺Z，对其中任意两条扩展边e′1＝（c1，c2，c3，c4，c5）和e′2＝（d1，d2，d3，d4，d5）满足条件：

（1） e′1＝ e′2， 当且仅当 ci＝ di，i＝ 1 ～ 5；

（2） e′1≺ e′2，当 ci＝ di，i＝ 1，2，…，n － 1 且 cn≺dn，n ＝ 1 ～ 5；

（3） e′1≻ e′2， 其他。

2.2 算法设计

基于有向频繁子图挖掘的移动性模式网络构建方法包括：基于有向图的频繁子图挖掘和频繁子图网络构建。基于有向图的频繁子图挖掘是基于用户设置的最小支持度阈值从移动轨迹有向图库中找到全部1阶频繁子图的过程。具体的步骤包括：（1）将所有移动轨迹数据转换成移动轨迹有向图，并形成有向图数据库。（2）遍历所有有向图，计算出图中节点的支持度。（3）去掉所有不频繁的节点，以及对应的孤立节点和不连通边，简化有向图数据库。（4）重复步骤（3），直至不存在孤立节点和不连通边，并且所有节点均满足最小支持度阈值，得到最终的简化有向图数据库。（5）遍历最终的简化有向图数据库，得到所有满足最小支持度阈值的1阶频繁子图。

基于有向图的频繁子图挖掘算法实现伪代码见算法1。

算法1 基于有向图的频繁子图挖掘

其中，第1行将移动轨迹数据库转换为移动轨迹有向图库；第2～6行是预处理过程，其中第2～4行基于minsup得到所有的频繁节点，第5～6行重复去除孤立节点和单点边，最终得到简化后的有向图数据库；第7行是扫描简化后的有向图数据库，找出所有频繁单边，得到1阶频繁子图集。

频繁子图网络构建过程是：合并1阶频繁子图集中的共同项，得到频繁子图网络。算法实现的伪代码见算法2。

算法2 频繁子图网络构建

其中，第1行合并1阶频繁子图集中的相同节点，合并结果记为V；第2行合并1阶频繁子图集中的相同边，合并结果记为E；第3行基于1阶频繁子图数据库中节点和边，生成频繁子图网络。

2.3 算法时间复杂度分析

本文提出方法包含移动性知识挖掘和复杂网络构建。移动性知识的挖掘采用基于有向图的频繁子图挖掘算法，从移动轨迹有向图中挖掘频繁子图。分析移动性知识挖掘算法的时间复杂度包括：（1）移动轨迹数据转换为移动轨迹有向图。假设存在n条移动轨迹数据，每条轨迹数据包含m个节点，形成n个有向标记图，其时间复杂度为Ttrans（n）＝O（n∗m）。 （2） 移动性知识挖掘过程包括预处理阶段和频繁子图挖掘阶段。其中，预处理阶段计算n个有向标记图中的m个节点的支持度，去掉所有不频繁的节点以及对应的孤立节点和不连通边，简化有向图数据库，其时间复杂度为Tpre（n）＝O（n∗m）；频繁子图挖掘阶段遍历简化后的n个有向图数据库，得到所有的满足最小支持度阈值的1阶频繁子图。假设简化后的图库中包含p个节点，挖掘过程的时间复杂度为Tdm（n）＝O（n∗p2）。 因此，挖掘算法的时间复杂度为Tmining（n）＝max｛O（n∗m），O（n∗p2）｝。 复杂网络构建合并 1阶频繁子图集中的共同项，得到频繁子图网络。假设1阶频繁子图集中包含q个频繁子图，则构建网络过程的时间复杂度为Tcon（q）＝O（q）。

2.4 实例分析

下面通过一个例子来说明从移动轨迹有向图库中挖掘频繁子图，进而构建频繁子图网络的具体过程。如表1所示，初始移动轨迹有向图库由3个有向标记图G1、G2、G3构成。设置最小支持度阈值min sup＝1。

表1 移动轨迹的有向图数据库

2.4.1 预处理

基于移动轨迹有向图数据库的频繁子图挖掘和网络构建过程包括3个步骤：

（1）统计表1中所有节点的标号个数，并计算对应的支持度，结果如表2所示。

表2 各节点的标号个数及支持度

基于设定的最小支持度阈值，去掉不频繁的节点标号E。

（2）删除孤立节点标号、不连通边（单点边）。删除节点标号E后，G2中连通D、E的边变得不连通，需要删除；同理G3中连通D、E和连通B、E的边也变得不连通，也需要删除。最终，得到简化后的轨迹有向图数据库如表3所示。

表3 简化后的轨迹有向图数据库

（3） 简化轨迹有向图数据库，重复（1）和（2），直至统计结果均满足min sup＝1为止。最终得到简化的轨迹图有向图数据库如表4所示。

表4 预处理后的轨迹有向图数据库

2.4.2 获取1阶频繁子图数据库

对于预处理后的轨迹有向图数据库，基于min sup＝1获取频繁单边集。遍历有向图数据库，计算所有单边的支持度，每条边均使用5元组DFS编码表示，结果如表5所示。

表5 图库中的所有单边及其支持度

删除支持度小于min sup＝1的单边，得到频繁单边集，即1阶频繁子图数据库。结果如表6所示。

表6 1阶频繁子图数据库

（3）构建频繁子图网络

合并1阶频繁子图数据库中的共同项，即可得到频繁子图网络。将表6转换为图的形式，合并其中的共同项得到频繁子图网络，如图1所示。

图1 频繁子图网络

3 实验

3.1 实验数据

本文采用的实验数据是收集于2019年7月13日南京市的2 612辆出租车的GPS轨迹数据。实验设定的相对支持度阈值为0.01。为保证方法性能测试的稳定性，随机采样了10个批次的数据，基本信息如表7所示。

表7 10个批次移动轨迹的基本信息

3.2 实验结果

通过采用本文提出的方法，得到10个批次移动轨迹数据对应的移动性模式网络，图示表达分别如图2和图3所示。从10个批次数据对应的移动性模式网络的空间分布可以看出，每个网络都可以清晰反映生成移动轨迹数据的出租车辆的频繁运行路线和主要的空间聚集区域。

图2 第1～6个批次移动轨迹数据对应的移动性模式网络

图3 第7～10个批次移动轨迹数据对应的移动性模式网络

3.3 网络特征分析

分析10个批次网络的网络特征如图4～7所示。

图4 频繁子图数量

从图4至图7可以看出10个批次移动轨迹数据对应移动性模式网络的特征具有较为显著的区分。其中，第5批次和第6批次由于数据挖掘得到的频繁子图的数量较多（见图4），相应地，其构建网络的平均聚集系数、平均节点度、平均节点入度、平均节点出度等网络特征值较大（分别见图5、图6、图7）。表明两个批次数据生成的网络聚集程度高，网络的连通性强，更易发现网络中多次被访问、较为重要的节点。而对于第7批次的数据，挖掘出的频繁子图的数量较少，其对应构建网络的特征值则具有相反的结果。

图5 平均聚集系数

图6 平均节点度数

图7 平均节点入度／出度

4 结束语

由于传统移动性知识特征表达太过单一而不能反映出生成移动性知识的复杂系统的潜在规律，本文提出了一种基于有向频繁子图挖掘的移动性模式网络构建方法。该方法通过移动轨迹数据到移动轨迹有向图的转换、基于有向图的移动轨迹频繁子图挖掘以及基于GraphX图框架处理实现移动性模式网络构建。实验结果表明：基于有向图的频繁子图挖掘方法构建出的复杂网络能清晰地反映移动轨迹数据的特征，具有可用性。今后，随着大规模移动轨迹数据分析和应用需要的增加，需要进一步研究减少内存开销和提高处理速度等性能优化问题。同时，如何将基于本文提出方法构建的移动性模式网络应用于最优路径规划，传播分析等场景应用，也是未来关注的重点方向。