移动目标同现模式挖掘算法的研究∗

周 濛 朱保平

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

从移动目标的时空轨迹数据中挖掘目标的关联关系是时空数据挖掘领域的重要研究内容之一，也是本文研究的主要内容。大量的时空轨迹数据蕴含着大量移动目标的行为规律。通常情况下，移动目标在某段时间范围内具备一定的规律，因此从时空轨迹数据集中挖掘目标的关联关系具有极高的研究价值。时空同现模式研究是时空数据挖掘研究的热点之一。为了挖掘时空同现相关的模式，M.Celik 等提出混合群时空同现模式的概念并定义了时空兴趣度［1］，并给出基于混合群的时空同现模式的挖掘方法及相关改进算法［2～3］。

近些年来学术界在时空数据建模方面也取得了较大研究进展。George等在空间网络的基础上，通过将时间序列作为图中节点与边的属性，提出了一种比Kohler 等提出的利用时间拓展图构建一个随时间动态变化的空间网络［4］更为有效的时间汇总图建模方式［5］，解决重复建模问题［6～7］。Y. Wan等定义了一种基于k-邻近对象的空间同位模式［8～9］，探讨了基于k-邻近空间关系的同位模式及基于距离阈值的空间同位模式的区别和联系，解决了基于距离阈值的空间同位模式算法中难以解决的对稀少空间特征对象的同位模式的发现，为基于k-邻近对象的空间同位模式应用于时空数据挖掘提供参考。龚健雅在空间数据库中研究了分布式数据模型［10］，但是该模型不能够直接应用于时空数据库中。本文针对现有时空数据建模及挖掘算法的计算瓶颈，给出粗细粒度结合的时空模型CFCMDCOP Graph，粗粒度层的构建基于移动目标轨迹信息匹配及FT 过滤器筛选，代替了直接遍历轨迹点集，通过减少计算对象来降低建模耗时；并提出基于连接的挖掘算法CFCMDCOP Graph Miner，挖掘中通过对粗粒度层移动目标间的引发序列计算，提前对不满足引发阈值的移动目标组合进行剪枝，细粒度层能够快速挖掘多条轨迹之间的时间交集，并计算多轨迹间的时空邻近频繁度，减少挖掘过程中的冗余计算来提高算法挖掘效率。

2 关联性挖掘主要公式及定义

本文提出了粗细粒度结合的混合时空模型（Coarse-fine-grained Combination Mixed-Drove Co-occurrence Pattern Graph，CFCMDCOP Graph）。粗粒度层存储元素之间的时空引发关系，细粒度层存储元素对应的实例集间的时空邻近状态，通过访问CFCMDCOP Graph，能够高效获取挖掘时空引发同现模式过程中需要的信息，避免冗余计算，提高了计算效率。下面来介绍本文的CFCMDCOP Graph存储模型。

定义1：粗粒度的引发关系网络（Coarse-grained Initiation Relation Graph，CIRG）：描述时空引发同现模式中各元素对应实例的出现情况及其引发关系。

N表示元素集，E表示有向边集，两个元素节点之间的边是双向的。fi为元素对的候选2 时空引发同现模式，edegi为fi对应的引发序列，FT 为过滤规则，根据实际数据特性建立相应的规则。

定义2：细粒度的时空聚合网络（Fine-grained Spatiotemporal Aggregation Graph，FSAG）：描述实例对在有效时间槽下的时空邻近状态。

N 表示实例集，E 表示无向边集，CR 为候选引发关系集，TF为时间框架，ci为邻近实例对的集合，ei为邻近实例对对应的时空邻近序列，edgei表示ci与ei的对应关系。

定义3：CFCMDCOP Graph：描述时空引发同现模式中各元素对应实例的出现情况及其引发关系、元素与实例的映射关系及实例对在有效时间槽下的时空邻近状态。

图1 CFCMDCOP Graph

TF 表示时间框架，Nelement表示元素集，Nintance表示实例集，E 表示边集，li表示类型与实例之间的连接，pk表示类型对与实例对集之间的连线，一个类型对对应多个实例对集。

以上是对CFCMDCOP Graph 时空存储模型的描述。CFCMDCOP Graph 时空存储模型的细粒度时空聚合网络是基于时间汇总图的，并且在细粒度层的基础上扩展出了一层粗粒度层，用于模式挖掘时提前对非时空引发同现模式进行剪枝。

定义4：时空引发同现模式。借鉴灾害关联之间存在的关联关系［11］、同现模式及时空兴趣度定义［1，12～13］，基于移动目标的时空数据，认为不同移动目标之间出现时间较早的移动目标有引发与其距离较近且出现时间较晚的移动目标的可能性［14］，由此定义元素之间的时空引发同现模式，给定：1）CFCMDCOP Graph 混合模型；2）时空引发阈值θI；3）过滤规则FT；4）邻近距离R；5）引发时长YFSC；6）空间频繁阈值θPr；7）时空邻近频繁阈值θSPF。最终挖掘出满足上述条件的移动目标组合，k 元时空引发同现模式的形式为P={C1→C2…→Ck}，该模式存在方向性。

实例名称在时间框架下获取到的相应实例集描述一条轨迹。给出移动目标及其轨迹的相关定义。

定义5：移动目标轨迹定义：Tr=(mc，st，et，areas，D)，mc表示具体的移动目标轨迹名称，st、et表示移动目标轨迹的首尾点对应的时间，即出现与消失时间，areas 表示轨迹的经过区域，D 表示组成轨迹的轨迹点集合，D={m t1，mt2，mt3，…，mtn} ，n ∈N+，n 为轨迹点的数量。

定义6：轨迹点mt=( )x，y，t ，其中x，y 表示移动目标所在的经纬度坐标，t 表示轨迹点对应的时间戳。

定义7：时空邻近状态。元素的实例映射到时间框架下，可以描述出一条完整轨迹。时空邻近状态用于表征轨迹组合之间在交集时长内处于空间邻近状态的频繁程度。描述如下：1）时空邻近序列seq；2）时空邻近频繁阈值θSPF；3）包含n 个时间槽的时间框架TF。seq 由若干0、1、2 组成一组序列值，序列值中的2 表示该时间槽对轨迹组合而言是无效时间槽；序列值中1 表示单个时间槽下轨迹组合处于空间邻近状态，0 表示不处于空间邻近状态。序列中1的数量与n的比值为时空邻近频繁度SPF，如果大于θSPF，则称轨迹组合处于时空邻近状态。

定义8：时空引发率，描述时空引发同现模式的引发程度。计算模式p 的时空引发率的公式如下：

如果时空引发同现模式p 的引发率大于引发阈值，那么模式p为时空引发同现模式。

2.1 移动目标关联性挖掘建模

粗粒度的引发关系网络层构建基于移动目标轨迹的匹配，由于构建出的移动目标轨迹数量远远少于轨迹点集的数量，由此降低了计算的数量级，减少了计算耗时；通过FT 过滤规则，得到候选2 元时空引发同现模式。同时，细粒度的时空聚合网络层基于时间汇总图的建模方式，避免了为每个时间槽的空间关系重复建模的问题，并且本文基于有效时间段进行算法建模，进一步减少了关联性模式算法建模的时间与空间消耗。

粗粒度的移动目标引发关系网络的构建流程如下。

1）初始化提取轨迹点的特征信息，构建所有移动目标轨迹；

2）按日期划分移动目标的轨迹信息，并按出现时间进行升序排序，对相同日期的轨迹集进行两两不重复的匹配操作；

3）基于FT 的过滤规则筛选出候选2 元时空引发同现模式，通过有向边对节点之间进行连接，并记录候选2元时空引发同现模式p，及其轨迹组合。

4）迭代步骤3），直到所有轨迹匹配完成，由此构建出粗粒度的引发关系网络。

5）将记录下的候选2 元时空引发同现模式输入细粒度的时空聚合网络层，根据已知的轨迹标识映射到轨迹点集，建立时空聚合网络，给粗粒度层返回结果。同时，更新移动目标对的引发序列。

其中，细粒度的移动目标时空聚合网络的构建步骤如下。

1）如果粗粒度层不再获取新的轨迹组，则完成时空聚合网络构建，结束；否则获取轨迹组

2）对其中任意一对未访问过的轨迹对Ai，Bj进行匹配。

3）新建轨迹的节点，根据引发关系网络中节点的轨迹出现时间、消失时间信息，计算时间交集，根据时间交集进行轨迹点抽样，每条轨迹抽取其轨迹点集的c个轨迹点，得到轨迹点集合DAi、DBj。

4）对轨迹点集合DAi、DBj之间进行欧式距离计算，添加轨迹的节点之间的连线，如果满足邻近距离R，那么时空邻近序列添加1，否则序列添加0，直到遍历完DAi、DBj的所有抽样轨迹点，计算时空邻近频繁度SPF，如果满足时空邻近频繁阈值θSPF，那么给粗粒度层返回1，否则返回0。

5）判断是否遍历完轨迹组{ }Ai，Bj，…，Ck中的所有轨迹对，如果没有则返回2），否则返回1）。

2.2 移动目标关联性挖掘算法

移动目标关联性挖掘，其粗粒度的引发关系网络层存储移动目标对的引发序列，挖掘过程中能够快速找到候选关联性模式，提前对不满足引发阈值的移动目标组合进行剪枝，减少了关联性模式算法挖掘过程的时间消耗；其细粒度的时空聚合网络层基于时间汇总图的建模方式，轨迹对是基于自身出现的有效时间段的，能够快速挖掘多条轨迹之间的时间交集，在时间交集下建立时间槽并计算多轨迹间的时空邻近频繁度，减少了挖掘过程中的冗余计算，进一步减少了关联性模式算法挖掘的时间与空间消耗问题。

本节借鉴Huang Yan 等提出的基于连接的空间同位模式挖掘［15］，将该挖掘方法应用到移动目标时空引发同现模式挖掘中。基于连接的移动目标关联性模式挖掘方法如下。

1）遍历粗粒度的引发关系层的候选2 元时空引发同现模式，根据引发序列计算时空引发率I( p )，当时空引发率值满足设定的时空引发阈值θI时，输出2 元时空引发同现模式。否则直接对其剪枝，减少后续计算量。

2）利用2 元时空引发同现模式集对应的轨迹组合做连接操作，如果结果不为空，则对应的移动目标组合构成候选3 元时空引发同现模式集，记录轨迹组合。例如，已知2 元时空引发同现模式集F1、F2，模式与对应轨迹组合为F1 →{C 1，C2} ，F2 →{C 1，C3} ，对 F1、F2 做 连 接，生 成F3 →{C 1，C2，C3} ，并且基于FT 过滤规则进行剪枝，如果没有被剪枝，则模式F3 为候选3 元时空引发同现模式。

3）根据候选3 元时空引发同现模式中轨迹组合各轨迹的出现时间、消失时间计算交集时长，在有效时间段内进行时空邻近频繁度SPF计算，若时空邻近频繁度SPF满足时空邻近频繁阈值，n(p)加1，skyfi(p)加1，否则仅n(p)加1。

4）遍历完该候选3 元时空引发同现模式的所有轨迹组合集，计算时空引发率I( )p ，如果引发率大于引发阈值，则为3 元时空引发同现模式。以此类推，直到k 元时空引发同现模式集数量小于2。则结束计算，最终生成2，3…，k 元时空引发同现模式。

这里需要说明的是，基于移动目标之间的关联性模式，其移动目标在同一时间槽下不会出现多个实例，在任意时间槽下，实例的空间频繁度的值不是0 就是1，所以在挖掘时简化了空间频繁度的计算。本文是基于带有效时段的时间汇总图，因此只在实例处于有效时段的时候对实例之间进行计算，即空间频繁度为1，保证其值大于空间频繁阈值。

2.3 移动目标关联性挖掘算法分析

本节分析推导了CFCMDCOP Graph Miner挖掘的完整性与正确性，以及分析了建模和挖掘过程的时间复杂度［16］，并在挖掘算法的时间复杂度上与传统算法fastMDCOP-Miner 算法运行的时间效率进行对比。

2.3.1 时空引发同现模式的单调非递增性

如果模式pi是模式pj的子模式，那么假设pi的时空引发率大于设定引发阈值θI，则pj的时空引发率一定不小于引发阈值θI，符合单调非递增的性质。

所以，挖掘过程不会存在子模式不存在，而模式存在的情况。换句话说，如果模式存在，则其子模式一定存在。

2.3.2 时空引发同现模式的完整性

CFCMDCOP Graph 建模过程是先基于轨迹构建及轨迹两两匹配，再进行轨迹之间的时空聚合网络构建的，由于时空聚合网络基于TAG 建模［5］，则时空聚合网络建模是完整的，那么针对轨迹构建，在不破坏原轨迹点集结构的基础上，不同的轨迹拆分构建规则可能对同一条轨迹拆分出不同的子轨迹集。因此，验证并推导不同的轨迹拆分规则不会导致时空引发同现模式挖掘结果的缺失，是保证时空引发同现模式挖掘完整性的前提。

证明方式如下：现有移动目标的原轨迹Tr，将Tr 拆分成Tr1与Tr2，其中Tr1、Tr2与待匹配轨迹Trw的有效时间槽分别为s1、s2，满足邻近距离的时间槽数分别为rs1、rs2，易知原轨迹Tr 与待匹配轨迹Trw的有效时间槽、满足邻近距离的时间槽数分别为s1+s2、rs1+rs2。假设原轨迹Tr 与待匹配轨迹Trw满足时空邻近状态，即：

即假设Tr1与Trw不满足时空邻近状态。对式（3）进行推导，得到

根据上述结果可以推断，若原轨迹与待匹配轨迹之间满足时空邻近状态，则子轨迹中至少存在一条轨迹与待匹配轨迹满足时空邻近状态。

如果通过原始轨迹点集构建出若干条轨迹信息，那么满足时空邻近状态的轨迹组合的数量一定不少于构建前的原轨迹生成的时空邻近轨迹组合的数量。但是，由于拆分构建的不确定性，可能会存在不同情况构建出轨迹的出现时间不同，导致模式的方向性发生变化。

综上所述，基于轨迹匹配的时空引发同现模式挖掘结果不会因轨迹构建规则变化而缺失，适当调整引发阈值可以保证挖掘时空引发同现模式的完整性。

2.3.3 建模时间复杂度分析

建模过程包括根据轨迹点构建轨迹集合、构建混合网络。首先构建轨迹集合，在已排序好的轨迹点集中进行遍历，得到轨迹点的经过区域、出现时间与消失时间，生成轨迹，并通过外键对轨迹与轨迹点进行关联，这个过程的时间复杂度为O( n )，n表示轨迹点的总数量。

在粗粒度移动目标引发关系网络构建过程中，主要通过对轨迹信息之间进行两两不重复的匹配操作，这个过程的时间复杂度为中N表示构建的轨迹集合的大小。

在细粒度移动目标空间关系建模过程中，主要是对移动目标实例的交集时长进行计算，提取相应时间段内的轨迹点，然后进行轨迹点抽样提取，采样方式采用等时间间隔采样，假设已知抽样点个数c，粗粒度层计算完成后，满足FT 过滤规则的有效移动目标组合数量为Ne，则细粒度层建模总的时间复杂度为O()。

根据数据集的不同大小，对粗粒度引发关系网络层与细粒度的时空聚合网络层进行建模，其建模时间如图2。

图2 粗细粒度混合建模耗时

2.3.4 挖掘时间复杂度分析

本节针对真实的行人数据，采用fastMDCOP-Miner［1］和CFCMDCOP Graph Miner 进行模式挖掘比较。

移动目标关联性挖掘算法主要进行移动目标间引发率的计算、移动目标对应轨迹组合的空间频繁度计算、时空邻近频繁度计算，移动目标及对应轨迹组合的连接操作，从而完成移动目标时空引发同现模式挖掘。

综上所述，总复杂度为OCFCMDCOPGraphMiner=。

图3 算法挖掘时间对比

分别使用传统挖掘算法与CFCMDCOP 挖掘算法，对现有行人数据进行时空引发同现模式挖掘，控制时间槽数、邻近距离、空间频繁阈值等相同。实验结果如图5 所示，由图可知，随着轨迹点数量不断增加，算法执行的时间呈递增趋势，CFCMDCOP挖掘算法比传统挖掘算法花费时间更少，算法效率更高。

2.3.5 实验环境及结果

数据实验环境为Win7 虚拟机，JDK1.8，2 核CPU、8GB内存，硬盘容量50GB，MySQL版本5.5。

本文实验所用的行人移动目标的轨迹数据来自于微软亚洲研究院Geolife项目采集的数据集［17］。

人的轨迹数据源数据是由182位用户为期5年的轨迹数据构成，这些数据是用户手机和GPS记录仪记录的轨迹点数据，每个轨迹点记录以经纬度、日期、时间等多个数据字段组成，样本数据如表1所示。本文选取2008-10-23 至2008-11-21 的30天数据进行挖掘分析计算。

表1 行人移动目标源数据

为了验证挖掘效率，本文将阈值设定调整到较低的限度。保证大多数模式能够被发现。挖掘结果如表2所示。

表2 挖掘结果

3 结语

本文基于行人移动目标时空数据集，提出一种移动目标粗细粒度结合的混合网络模型CFCMDCOP Graph，并给出挖掘算法CFCMDCOP Graph Miner。本文主要工作如下：1）对粗细粒度结合的模型CFCMDCOP Graph的结构进行描述，定义时空引发同现模式，为设计有效挖掘算法提供基础；2）提出建模方法，粗粒度层的构建基于移动目标轨迹信息匹配及FT 过滤器筛选，代替了直接遍历轨迹点集，通过减少计算对象来降低建模耗时；3）提出针对混合模型的挖掘算法CFCMDCOP Graph Miner。挖掘中通过对粗粒度层的引发序列计算，提前对不满足引发阈值的移动目标组合进行剪枝，其细粒度层能够快速挖掘多条轨迹之间的时间交集，在时间交集下建立时间槽并计算多轨迹间的时空邻近频繁度，减少挖掘过程中的冗余计算来提高算法挖掘效率。

最后，通过实验结果对建模与挖掘进行验证，结果表明该模型能够对移动目标及其轨迹点实例的时空关系进行快速建模，并且在移动目标模式挖掘方面较传统算法具有更少的时间消耗、效率更高。