移动目标关联共现规则挖掘算法研究

谢 , , ,,

(1.南京理工大学 计算机科学与工程学院,南京 210094; 2.中国电子科技集团公司第三十二研究所,上海 201808)

0 概述

在计算机及网络普遍应用的信息化时代,人们已经习惯在任何时空环境下自然地与计算设备进行交互,具有位置感知功能的计算设备更是无时无刻地处于运转状态,记录着人、车辆等移动目标的行为轨迹[1-2]。随着卫星通信、无限传感器等信息采集设备的快速发展和广泛应用,移动目标的轨迹数据和行为信息可以被更实时、有效地记录下来[3]。这些移动目标跟踪数据包含了大量时间信息、空间信息及行为信息,为挖掘移动目标的活动规律和行为模式提供了有力支撑[4]。同时,这些活动规律和行为模式在城市规划[5-6]、位置服务[7]、国防军事[8]等方面也具有非常重要的研究和应用价值。

移动目标活动规律是根据目标轨迹数据进行分析的。通过统计、关联分析等手段,对时空轨迹数据加以分析,可以得到移动目标的一些活动模式,如频繁活动路线、频繁停留地点等[9]。早期的移动目标行为规律研究仅考虑单一时刻移动目标的行为特征,如文献[10]提出的最长持续群体模式,要求某时刻至少有m个移动目标在同一区域内保持相同的移动状态。该算法为群体行为挖掘提供了研究思路,但严格限制移动目标须在持续时间内同时移动,不能适用于实际应用。文献[11]为了解决这一问题,提出了更加通用化的模型,对于移动目标的活动,在时间上不要求连续性,且不局限于活动区域的形状。在频繁模式挖掘方面,文献[12]对轨迹进行分割预处理后,利用最小支持度挖掘移动目标的频繁轨迹,该方法忽略了移动目标轨迹数据与兴趣区域的关联性。文献[13]对轨迹数据进行了聚类预处理,对其中符合预设区域的数据进行分段提取,从而进一步针对移动目标在兴趣区域内的行为规律进行分析。现有的频繁模式挖掘研究多基于传统Apriori算法或树结构,加入时序特征后,针对不同应用场景分别对算法进行优化[14-15]。

现行的移动目标活动规律侧重于空间或时间单一维度,且忽略目标的行为,并且多集中于单目标的活动规律分析[16]。而考虑到在类似于军情分析等场景中,用户除了需要了解敌方装备活动的地点关联性,也需要获取敌我两方以及敌方装备间在时空上的协同出现规律,以提前制定应对策略。

移动目标间活动数据越相似,或协同行为越规律,则两者存在关联共现的可能性越高。基于此,本文基于传统的时间戳和地点的关联模型,加入任务属性信息,对关联共现进行定义,提出一种基于序列模式和关联规则的移动目标共现行为挖掘算法。

1 关联共现的相关定义

关联共现规律发现是以移动目标在空间上的共同出现模式为基准,进一步分析时间上的频繁度而得到。本文将移动目标间的关联共现规律称作对象关联共现,而单移动目标会存在自身地点关联。在计算中,时间上的频繁度是以天为单位进行计算的。

1.1 对象关联共现

定义1对于2个移动目标A和B,若1 d内,存在移动目标A和B的活动数据,则称移动目标A和移动目标B共同出现了一次,记SAB=1。若1 d内移动目标间对象关联的共同出现的次数大于1,SAB仍为1。在选定时间段D=[ds,de]内,若移动目标A和B共同出现次数SAB大于阈值SΔ,则称SAB为移动目标A和B在选定时间段内对象关联的共现次数,即:

其中,i∈{1,2,…,|D|},ds和de分别为选定时间段的开始日期和结束日期,SABi∈{0,1}为移动目标A和B在从ds开始第i天的共同出现次数。

定义2定义tAB为移动目标A和B的共同出现时长。若1 d内,移动目标A和B存在共同出现的情况,对于tAB则有:

在选定时间段D=[ds,de]内,若移动目标A和B共同出现时长TAB大于阈值tΔ,则称TAB为移动目标A和B在选定时间段内的共现时长,即:

其中,tABi为移动目标A和B在从ds开始第i天的共同出现时长。

定义3定义disAB为移动目标A和B共同出现的间隔距离。若1 d内,移动目标A和B存在共同出现的情况,具能够测得共同出现的时长,则对其共同出现的时间段等分取样,计算同时刻,移动目标A和B之间的欧氏距离,并求和取平均,对于disAB即有:

其中,xj、yj分别为移动目标A和B在第j个取样点的位置信息,n为同时刻采样点的对数。在选定时间段D=[ds,de]内,若移动目标A和B共同出现时的间隔距离dAB小于阈值disΔ,则称dAB为移动目标A和B在选定时间段内的间隔距离,即:

其中,xj、yj为移动目标A和B在从ds开始第i天的间隔距离,SAB为在选定时间段D内,移动目标A和B的共同出现次数,此处距离均以千米为单位。

对于对象关联共现中的共同出现,存在2类情况,f(x)为判断函数:

1)移动目标A和B间,共同出现的次数、时长、间隔距离都存在,即:

f((SAB>0)& & (TAB>0)& & (dAB≠∞))=true

该种情况称为存在三参的共同出现。

2)移动目标A和B间,仅存在共同出现的次数,而时长、间隔距离均不存在,即:

f((SAB>0)& & (TAB==0)& & (dAB==∞))=true

该种情况称为存在一参的共同出现。

当且仅当在选定时间段D=[ds,de]内,对移动目标A和B的三参与一参共同出现结果进行累加与合并,若共现次数SAB>sΔ,共现时长TAB>tΔ,间隔距离disAB>disΔ均满足,则称此时间段内,移动目标A和移动目标B存在对象关联共现。

定义4定义φ为对象关联共现强度,ξi为对象关联共现中第i种关联度的分配权重,αi为第i种关联度的度量值,则三者之间存在关系:

其中,i∈{1,2,3}。

在选定时间段D=[ds,de]内,若αi为共现次数关联度度量值,则有:

若α2为共现时长关联度度量值,则有:

若α3为共现间隔距离关联度度量值,则有:

1.2 对象自身地点关联

定义5移动目标A在选定时间段D=[ds,de]内的活动轨迹数据集为Q={q1,q2,…,qn},每条轨迹qi对应移动目标A的一条活动区域转移序列。

现寻找Q中出现频繁度sup(qj)大于频繁度阈值supΔ的最长子序列FFS={fs1,fs2,…,fsm},其中,n为目标A在选定时间段内的活动轨迹总数,m为找到的频繁子序列总数,且有m≤n,fsi⊆qj,i∈{1,2,…,m},j∈{1,2,…,n}。FFS即为移动目标A在选定时间段D内的对象自身地点关联结果集。

2 移动目标关联共现行为模式挖掘算法

本文算法是基于原始的轨迹和活动数据,提取关键属性,并对移动目标之间的共现参数进行计算。算法由移动目标对象关联共现挖掘与移动目标自身地点关联挖掘2个子算法构成。

2.1 移动目标对象关联共现挖掘算法

对象关联共现挖掘算法是在传统的轨迹序贯模式挖掘的基础上,从含有{时间戳-地点-任务}三要素的关联模型中,依据2个移动目标在时间上的频繁度以及空间上的距离进行共现模式挖掘。设计思路为:对历史时间段内的轨迹数据进行初始化,将其处理为统一的数据格式。然后根据定义,计算移动目标间的关联度度量值,对其进行加权求和,从而得到两两移动目标间的对象关联共现强度,构建共现模式链。此时链表中保存的是完整的对象关联共现模式集合,在实际需求中,还需要根据用户的筛选条件,将关联度度量值及对象关联共现强度与阈值进行比较,判断其是否满足设定的时空频繁度,再进行输出展示,从而辅助用户从模式链中获取满足条件的对象关联共现模式集。

算法分为2步:

1)计算任意2个移动目标间的对象关联共现参数。以天为单位,计算两两移动目标在不同区域的共现参数,并将结果数据写入对象关联共现参数表中。

2)在用户点击查询后,直接从生成的结果表中查找数据,进行计算得出最后结果。

构建对象关联共现参数表的具体步骤为:

1)初始化轨迹数据集,将数据格式处理成{轨迹信息唯一标识符,移动目标,任务,出现时间,出现经度,出现纬度,消失时间,消失经度,消失纬度,经过区域,经过区域时间}的格式。

2)以天为单位,从历史数据第一天起,截取当天所有的轨迹记录,找到所有移动目标的轨迹信息唯一标识符tidi。

3)对tidi进行两两匹配,这里以目标A对应的tid1和目标B对应的tid2为例。

4)找出tid1包含的经过区域集合area1,tid2包含的经过区域集合area2,然后对area1、area2中包含的区域及对应的经过区域时间进行两两匹配。

5)例如,area1={区域1,区域2},area2={区域3}。tid1对应的经过区域1的时间是Tin1,Tout1为在Tin1时刻,目标A进入区域1,在Tout1时刻,目标A离开区域1。tid2对应的经过区域3的时间是Tin2、Tout2。

此时,比较Tin1与Tin2的大小,以较晚时间点为基准,记作Tin,即:

Tin=max{Tin1,Tin2}

同样,比较Tout1与Tout2的大小,以较早时间点为基准,记作Tout,即:

Tout=max{Tout1,Tout2}

判断Tin与Tout的关系,若Tout≤Tin,说明目标A和B的活动没有重合时间,则当天一参共同出现的次数记为1,写入对象关联共现参数表,并标注共同出现标示为1,回到步骤4),对下一种区域匹配情况进行计算。

若TouttΔ,跳转到步骤7),并在此打上断点breakpoint,若返回值flag=true,则当天三参共同出现次数记为1,写入对象关联共现参数表,并标注共同出现标示为3。如果返回值flag=false,则不统计。回到步骤4),对下一种区域匹配情况进行计算。

6)若当前时刻,在tid1包含的经过区域集合area1和tid2包含的经过区域area2中,所有区域均已遍历,跳转到步骤9)。

7)对tid1和tid2的共同出现开始时间点Tin、共同出现结束时间点Tout等分出5个时间点,提取tid1和tid2对应的相应时间点的轨迹点信息各5条。

8)计算读取到的相同时间点的轨迹点的经纬度欧式距离,并求取平均值,得到d。如果d

9)回到步骤1),对下一天所有的轨迹记录进行计算,直到所有日期都遍历结束。

10)将同一天内,两两移动目标匹配关系相同的数据进行合并,写入临时结果表。

11)对临时结果表进行再次处理,将两两移动目标匹配关系相同的数据进行合并,同时对不同的共同出现标示进行合并,写入最终的对象关联共现参数表中。

12)根据用户筛选条件,计算用户选定时间段内的共同出现次数、共同出现时长以及对应的间隔距离,判断是否属于对象关联共现,若关联度度量值符合定义中的阈值,则进行输出展示;若不符合,则略去。

目标对象关联共现规律挖掘算法流程如图1所示。

图1 目标对象关联共现规律挖掘算法流程

2.2 移动目标自身地点关联挖掘算法

移动目标的自身地点关联就是针对单一目标挖掘活动的频繁序列,即对目标以天为单位的活动区域集合使用频繁序列挖掘算法,在符合支持度阈值的条件下,找出目标经常活动的、有时间先后顺序的活动区域[17]。此处采用序列模式算法中的PrefixSpan算法[18]。

基于前缀投影进行频繁序列模式挖掘的主要步骤如下:

步骤1找出频繁单项:扫描数据库,寻找出现次数大于设定支持数的单项(每个单项在一个序列中即使出现多次也只算一次),得到长度为1的频繁项目集。

步骤2生成投影数据库:为上一步得到的频繁项目集中所有项目生成投影数据库。

步骤3寻找频繁序列子集:通过递归挖掘投影数据库得到频繁序列子集。找到以步骤1得到的频繁项目集中的元素为前缀的频繁序列,然后为其构造投影数据库并挖掘。

步骤4重复步骤1～步骤3,直到找不出频繁项目。

基于以上对于PrefixSpan算法的理解,利用PrefixSpan算法挖掘移动目标自身地点关联步骤如下:

步骤1扫描历史轨迹数据,根据用户选择的移动目标、时间范围、所属任务,筛选出符合条件的轨迹信息。一条轨迹的出现时间只要在用户所选的时间范围内,那么这条轨迹的时间和用户选择的时间范围条件就是相符的。

步骤2对于每一条轨迹信息,经过区域属性下所包含的区域转移信息,已经是按照时间升序排列的了。此时,以目标的轨迹信息唯一标识符tidi为单位,记录符合条件的目标,对用户筛选时间段内所有的经过区域信息,记作该目标的一条活动序列Qij。

步骤3对同一个移动目标的活动序列构建数据库Si,使用PrefixSpan算法分析数据库Si,获得目标的频繁序列集合Fi,其中,i表示第i个符合用户筛选条件的移动目标。

步骤4对第i个移动目标计算获得的频繁序列集合Fi,去除子集序列,获得最长频繁序列集合Li,Li即为该目标的频繁活动序列集。

步骤5跳回步骤3,对下一个符合用户筛选条件的目标计算频繁序列,直到符合用户选定条件的所有移动目标的频繁序列都已被挖掘,算法结束。

目标自身地点关联规律挖掘算法流程如图2所示。

图2 目标自身地点关联规律挖掘算法流程

3 实验结果与分析

对轨迹数据进行对象关联共现和自身地点关联分析,得到任意两两移动目标间的对象关联共现参数值,以及任意移动目标自身频繁执行的轨迹序列。进一步地,根据这些数据,可以判断任意一段时间内,两两移动目标间的关联强度,以及单移动目标自身的活动规律,从而据此针对各个移动目标建立监控和反应机制。

本文描述的轨迹数据集包括轨迹唯一标识符、移动目标名称、任务、出现时间、出现经度、出现纬度、消失时间、消失经度、消失纬度、经过区域、经过区域时间共11个属性,具体数据格式如表1所示。

设定对象关联共现中的出现次数阈值SΔ为1次,时长阈值tΔ为0.2 h,间隔距离阈值disΔ为200 km,对象自身地点关联中的频繁度阈值为原始轨迹总条数的20%。针对2017年全年,全部约1 TB的移动目标轨迹数据进行分析。得到的对象关联共现结果数据包括对象关联共现唯一标识符、日期、2个移动目标各自的名称、任务、所在区域,2个移动目标共同出现的开始时间、共同出现的结束时间、共同出现的时长、间隔距离,以及出现标识、关联强度共14个属性,具体数据格式如表2所示。

分析得到的目标自身地点关联结果数据包括自身地点关联唯一标识符、移动目标名称、任务、频繁经过区域、日期、经过次数,共6个属性,具体数据格式如表3所示。

表1 轨迹数据集数据格式

表2 对象关联共现结果数据集数据格式

表3 对象自身地点关联结果数据集数据格式

以移动目标A和移动目标W为例,通过对A和W的原始轨迹的可视化展示,如图3所示,可以发现,在同一时间轴上,移动目标A和W的活动倾向于协同出现,并且距离较近。而在实验中,通过本文提出的对象关联共现规律挖掘算法,可以得到移动目标A和移动目标W存在对象关联共现。因此,算法的实验结果与实际情况相符。

以移动目标A为例,通过对其原始轨迹的分析,如表4所示,可以发现,在该时间轴上,移动目标A总是倾向于出现在区域a、区域b和区域c,并且经常由区域b进入区域a,同时执行普通任务。若设置阈值为20%,则移动目标A的频繁活动序列为区域a、区域b、区域b->a,以及区域b->a->b->a。而在实验中,通过本文提出的对象自身关联规律挖掘算法,可以得到移动目标A的频繁活动序列为b->a->b->a,出现次数为2。算法的实验结果与实际情况相符。

图3 对象关联共现结果可视化展示

表4 移动目标A简化后的轨迹信息

由实验结果可以看出,任意2个移动目标之间,对象关联共现的关联强度越高,则说明这2个移动目标活动数据越相似,协同行为越规律。根据关联强度,对两两移动目标间的关联度进行多档划分,可以对进一步制定的应对方案给出决策指导。而对于移动目标自身具有的地点关联共现规律而言,其得到的结果标识了单移动目标大概率活动区域及活动的先后顺序,可以辅助用户深入研究移动目标的行为特征,进而辅助预测分析。

就算法效率而言,对象关联共现规律挖掘算法采取的是以空间换取时间效率的方式,首先按d将计算结果存入数据库中,当用户执行查询操作时,将相应数据从数据库中调出并进行简单的低维运算,此时的复杂度仅为O(n),其中,n表示数据库中的数据条数。这一举措可以大大降低用户执行操作的耗时,优化查询效率。而在移动目标自身地点关联规律挖掘算法中,相较于传统的序列挖掘算法,如Apriori算法[19]、GSP算法[20]、SPADE算法[21],本文采取的PrefixSpan算法因其无需保存频繁序列的候选集,而只需保存投影数据,可以大幅度减少内存的消耗[22],在设定同等最小支持度阈值的条件下,该算法的耗时更低,且运行良好。

4 结束语

本文研究了一种基于数据挖掘的移动目标行为模式挖掘算法,基于传统的时间戳和地点的关联模型,加入任务属性信息,对关联共现进行了定义,分析时空轨迹数据,获得2个移动目标之间的协同行为规律。同时运用序列模式挖掘算法,分析单移动目标自身的行为规律,为针对各个移动目标建立监控和反应机制提供了数据基础。实验结果证明,本文所提算法可以有效挖掘移动目标间的活动地点关联性以及协同共现规律,并且具有较低的算法复杂度,可以适用于基于海量数据的计算和应用。