基于时空图的移动对象聚集模式挖掘方法-张峻铭.pdf

《基于时空图的移动对象聚集模式挖掘方法-张峻铭.pdf》由会员分享，可在线阅读，更多相关《基于时空图的移动对象聚集模式挖掘方法-张峻铭.pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、软件学报ISSN 10009825，CODEN RUxuEWJournal oSoftware,2016，27(2)：348-362【doi：1013328，jcnkijos004797】中国科学院软件研究所版权所有基于时空图的移动对象聚集模式挖掘方法张峻铭，李静林，王尚广，刘志晗，袁泉，杨放春(交换与智能控制国家重点实验室(北京邮电大学)，北京 100876)通讯作者：张峻铭，E-mail：longmumingmailcomE-mail：josiscasaccnhttp：wwwjnsorgcnTel：+861062562563摘要：移动对象聚集模式是指由移动对象参与的一组群体事件，通常用来预

2、测交通系统中出现的异常现象然而由于海量移动轨迹数据的产生，已有的研究方法难以准确、高效地挖掘特定的聚集模式为此，提出一种基于时空图的移动对象聚集模式挖掘方法该方法首先通过改进的空间聚类算法(DBScan)分析轨迹数据，从而获得移动对象聚类；然后，利用时空图模型代替单独存储轨迹数据的方式，用于实时观测移动对象聚类的时空变化特征最后提出基于最大完全子图查找的聚集检索算法及其改进算法用于查找满足时空约束的最大完全子图基于真实大规模轨迹数据集上的实验结果表明。所提出的方法在移动对象聚集模式挖掘的准确性和高效陛方面优于其他方法关键词： 聚集模式挖掘；时空图；轨迹数据中图法分类号：TP311中文引用格式：

3、张峻铭，李静林，王尚广，刘志晗，袁泉，杨放春基于时空图的移动对象聚集模式挖掘方法软件学报，2016，27(2)：348-362http：wwwjosorgcn100098254797htm英文引用格式：Zhang JM，Li几，Wang SG，Liu ZH，Yuan Q，Yang FCMining moving object gathefing paRern method viaspatiotemporal graphRuan Jian Xue BaoJournal of Software，2016，27(2)：348362(in Chinese)http：wwwjosorgcrdl00098

4、254797htmMining Moving Object Gathering Pattern Method Via SpatioTemporal GraphZHANG Jun-Ming，LI Jing-Lin，WANG ShangGuang，LIU Zhi-Hart，YUAN Quan，YANG FangChun(State Key Laboratory ofNetworking and Switching Technology(Beijing University of Posts and Telecommunications)，Beijing 100876，China)Abstract：

5、Moving object gathering paRern represents a group event or incident that involves congregation of moving objects，enablingthe prediction of anomalies in traffic systemHowever,effectively and efficiently discovering the specific gathering paaem remains achallenging issue since the large number of movi

6、ng objects generate high volume of trajectory dataIn order to address this issue，thisarticle proposes a moving object gathering paRem mining method that aims to support the mining of gathering paRems by usingspatio-temporal graphIn this method，firstly an improved density based clustering algorithm(D

7、BScan)is used to collect the movingobject clustersThen，a spatio-temporal graph is maintained rather than storing the spatial coordinates to obtain the spatiotemporalchanges in real timeFinally,a gathering mining algorithm and its improved version are developed by searching the maximal completegraphs

8、 which meet the spatio-temporal constraintsThe effectiveness and efficiency of the proposed methods aoutperformed otherexisting methods on both real and large trajectory dataKey words：gathering pattern mining；spatiotemporal graph；trajectory data近年来，随着卫星定位技术的普及，越来越多的移动对象都安装了卫星定位系统这项技术使我们获得了大基金项目：国家自然

9、科学基金(61202435)；国家高技术研究发展计划(863)(2012从I 11601)；北京市自然科学基金(4132048)Foundation item：National Natural Science Foundation of China(61202435)；National High-Tech R&D Program of China(863)(2012AAlll601)；BeijingNatural Science Foundation ofChina(4132048)收稿时间：2014一Ol07；修改时间：20140403；采用时间：2014-1125；jOS在线出版时间：20

10、15II03CNKI网络优先出版：201511-04 17：10：00http：wwwcnkinetkcmsdetail112560TP201511041710001html万方数据张峻铭等：基于时空图的移动对象聚集模式挖掘方法 349量的轨迹数据(也就是常说的时空数据)，通过分析这些数据，使得获取移动对象的行为成为可能基于此，国内外的许多研究人员正在通过挖掘移动对象的移动模式，为交通系统提供路况分析、线路规划等服务ll，21(如，基于轨迹数据挖掘的实时路况导航服务)在上述这些研究中，一个重要的研究方向就是如何挖掘移动对象聚集模式(本文简称聚集模式)聚集模式【3】可以看成由一系列事件或者事故引

11、起的一组移动对象的聚合，比如发生了车祸路段由车辆聚集引起的拥堵为了统计或预测交通系统中可能出现的事故或者拥堵等现象，研究人员提出了聚集模式挖掘方法该方法的基本原理是：通过移动对象的轨迹数据分析某一区域出现的密集移动对象群组，统计发生的移动对象聚集其具体实现方法是：通过空间网格(鲥d)检索移动对象轨迹，查找密集的移动对象群组，再使用TAD算法检验每一个移动对象群组能否形成聚集为了通过海量的移动轨迹数据挖掘移动对象聚集模式，flockt4】被定义为一组连续行驶k个时间片的群组，这个群组包含在一个固定大小的圆形区域中而Gudmundsson等人睁】用flock研究一个移动对象群组的最长共同行驶时间L

12、i等人【6】在flock的基础上提出了更加灵活的swarm，它允许群组被包含在任意形状的区域中，其中任意两个对象的距离都小于闽值，群组中移动对象的共同行驶时间不需要连续，使用聚类算法挖掘轨迹中的移动对象群组，采用比以往宽松的移动群组定义方式，能够更广泛地挖掘移动对象群组可以看出，上述研究大多不能观测动态变化的移动群组，特别是在使用流数据的环境下Tang等人【_7】提出一种增量式的算法来挖掘行驶中的伙伴，通过轨迹流可以动态地分析出移动对象的行驶伙伴，行驶伙伴可以用来进行移动对象间的资源分配、智能拼车与安全管控文献【81l】通过分析北京市的出租车轨迹数据来研究该城市交通系统中出现的异常现象S跹ja

13、y等人【ll】进一步通过汽车轨迹的聚合来模拟行驶路线，解释异常现象出现的原因另外，通过相似性判断不同移动对象是否具有相同的移动模式【12,13】，Shi等人【”】使用分段聚类算法对轨迹进行先分段再聚类，挖掘兵棋作战系统中移动对象的运动态势Jeung等人【14】提出了一种通过兴趣区来检测移动对象间是否具有相同的移动模式这种方法通过检测不同对象经过兴趣区的时序序列的相似性来实现Zheng等人【3】定义了移动对象聚集模式的概念，并且使用一种移动群组检测的算法来挖掘移动对象的聚集模式聚集模式可以用来统计或预测交通系统中可能出现的事故或者拥堵等现象但是，现有的研究只给出了聚集模式的发现算法，通过分析轨迹

14、数据中的移动群组来发现移动对象聚集模式这种方法在进行特定时间或者空间的聚集模式挖掘时，每次都需要重新遍历全部轨迹数据比如，通过时间进行挖掘时，需要首先提取所需时间的轨迹数据，对其中的移动物体聚类后进行聚集模式发现这样会耗费大量的时间，在交通系统中不能用来观测实时路况信息，预测也缺乏准确性有些研究【15_1 8】通过时间序列分析移动对象历史、现在和将来的位置比如，Ding等人【l 9】设计了一种基于R树索引结构NDTRTree，能够动态地索引和维护移动对象的当前及将来位置Geraldine等人【20】提出了由移动对象组成的复杂网络，通过这个网络分析对象的移动特性Mondo211提出了强语义时空图

15、模型，使用图来表示移动对象的时间和空间的变化特征但是，这些研究只考虑单个移动对象的移动位置等信息，没有考虑移动群组的变化趋势：同时，由于移动群组中对象间都有很强的时空约束，传统的数据结构并不能完全适应聚集模式挖掘的时空约束条件针对上述不足，为了从海量的轨迹数据中准确、高效地挖掘特定的聚集模式，本文提出一种基于时空图的聚集模式挖掘方法，其核心是：通过使用最大完全子图查找算法检索由移动对象聚类组成的时空图，找出满足时空约束条件的最大完全子图，从而准确、高效地挖掘给定时间或者位置的聚集模式，可以为实时路况分析、路线规划等服务主要贡献如下：(1)引入了时空图数据模型该模型由移动对象聚类构成，图中的每个

16、节点除包含组成聚类的移动对象的信息外，还包含对应聚类的形成时间和位置，每条边记录两个聚类间的时空关系时空图能够准确地反映移动对象聚类的时空变化特征(2)基于时空图，提出了移动对象聚集检索算法GR该算法使用最大完全子图代表移动对象聚集，通过查找完全子图的方式找出满足时空约束的移动对象聚集集合根据移动对象聚集的特点，我们又提出了一种改进的移动对象聚集检索算法GR+它使用高效的极大团检索算法来查找最大完全子图，通过剪枝策略降低搜索空间，提高了移动对象聚集的检索效率(3)提出了一种基于时空图的移动对象聚集模式挖掘方法首先，通过实时的轨迹数据对移动对象进行空间聚类；然后，使用移动对象聚类组成万方数据35

17、0 Journal of Software软件学报V0127，No2，February 2016时空图；最后，根据时空图利用聚集检索算法高效地查找满足时空约束条件的移动对象聚集集合(4)为了验证基于时空图的移动对象聚集模式挖掘方法，本文基于真实的出租车轨迹数据构建了仿真实验，通过准确性指标与效率指标的对比表明：我们的方法在准确性方面提供了较高的精度，在效率方面优于现有的研究本文第l节给出相关概念的定义和移动对象聚集模式挖掘方法，其中，第11节列出本文用到的相关概念和符号，第12节详述移动对象聚集模式挖掘方法，第121对移动对象进行聚类，第122节创建时空图，第123节提出聚集检索算法第2节对本

18、文所述方法进行验证，其中，第21节设置实验环境，第22节对方法的准确性进行对比，第23节对方法的效率进行对比第3节总结全文1研究问题在本节中，我们首先定义了本文用到的相关概念和符号，然后详述了移动对象聚集模式挖掘方法11相关定义定义l(轨迹快照)设移动对象数据库是O协，与它相对应的时间数据库是B，轨迹快照为串(，；，fi)IViEODB，TDB，其中，S是对应时间片t，的轨迹快照，属于轨迹快照集合S的子集一个轨迹快照昌是在ti时刻一组移动对象及其位置的集合，不是所有在集合OoB中的移动对象都会出现在ti时刻的轨迹快照内给出一个轨迹快照S，使用空间聚类算法找出在S上的密集的移动对象群组，如果这个

19、群组的成员超过给定的阈值这个群组就形成一个聚类定义2(移动对象聚类)令集合cr01，02，0I)是对应于每一个时间片i(1iD的移动对象集合对于两个给定的阈值m。和k，当满足以下条件时，c，是一个移动对象聚类：(1)ci中的成员数量size(ci)1m。；(2)Cj存在的一段时间，即生存时间time(cf)屯；(3)Cf包含的任意两个移动对象Ok和DP的距离不大于点可以表示为Dist(ok,)点其中，VDt，opOon移动对象聚类就是在给定的时间片上由一组移动对象形成的指定大小和形状的群组，其中的两个对象的距离都小于给定的阈值根据定义2，我们给出移动对象聚集的定义定义3(移动对象聚集)设一个移

20、动对象聚类集合为C，当满足以下条件时，G是一个移动对象聚集：(1)对于时间阈值肛移动对象聚类的形成时间ct，陈卜qtlmg then7 foreach edge e do8 if Pweightmg then11 Ga7卜苫；12Gae-VerifySimilarity(Ga)；13return Ga；算法中的GetMaximalCompleteGraphO需要找出时空图G中节点玎导出的所有最大完全图由于找某一节点的完全图是一个NP难问题，需要大量的循环来遍历时空图G；同时，时空图包含所有的移动对象轨迹，遍历一遍需要耗费大量的时间，这会使得检索极其缓慢为了提高查找最大完全子图过程的效率，本文又

21、提出一种改进的GR+算法21聚集检索算法GR+为了提高聚集检索过程中最大完全子图查找的效率，本文根据极大团检索BronKerboseh算法【231提出一种高效的聚集检索算法BK算法是一种广泛使用的高效的极大团检索算法，它被认为是现有算法中较高效的一种算法【241根据搜索空间的特点，制定有效的剪枝策略，提出了一种改进的使用极大团检索算法和剪枝策略的算法GlH首先。我们给出极大团的定义定义8(极大团)给定一个无向图G_(，司，如果3NeN,3EE，使得G=fieF)是一个完全图，则称G是一个团如果、SneN且玎7，使得G”=“u玎)是一个完全图，则称G，是一个极大团由于时空图包含所有对象的轨迹，形

22、成了庞大的搜索空间但是极大团检索算法需要多次遍历时空图，为了减少搜索空间，提高算法的效率，我们根据以下定理提出剪枝规则：定理2对于一个t时刻形成的移动对象聚集Cg，不可能存在一个在f，时刻形成的聚集，使得c乒q，其中，户f，证明：假设存在两个聚集集合c产咯1，c92，Cgj和=Cool，C92，Cgi，Cgi+l，它们的形成时间t=f由于cgf+1仨q，所以Cgf+l与c亭不在同一个时间片或者相邻的时间片，这与f=ft相矛盾所以在时刻f有且只有一个移动对象聚集G 口定义9(团的相似性)令G与G”是时空图G中的两个极大团，那么对于给定的差异阈值烈0mg thenforeach edge e do

23、if Pweightmg then23 Ga七一gt；24return Ga；子过程：ProcBK(cLo)25令(为节点vp的所有邻居节点26if Z=a andD=Othen27 将C输出为一个极大团；28 return；29从(几JD)中选择一个枢轴节点；30T-删()；31foreaeh vTdo32zon1，；33 call ProcBK(Cuv，TcVV(vll，Dn(v)；34D-Duv；例3：我们使用图4的例子来简单地说明我们的聚集模式挖掘过程，其中，成员阂值mf3，距离阈值占=200给定一个点集-口145，C4)，对于其中每一个点，使用BK算法找到包含这个点的所有极大团，得到

24、极大团集合：Gkell424344,Is)，Al,A2e1344#15)，Ca，C2，Cj，c4，Cs使用规则l对极大团集合进行剪枝，得到G，-“A1424344爿5，Cl，C2，c3，C4，c5)接下来验证G，中的极大团是否符合聚集要求的时空约束条件，所有集合的大小都大于成员阈值，但是集合臼142434445中A3与A5的距离大于距离闽值，将A3从集合中去掉，得到移动对象聚集集合G萨似-42445，cI，c2，G，a，G3)算法性能分析GR算法使用原始的极大团发现算法，对于满足时间或者空间约束的，1个节点，需要在图中遍历2”个子集，在检验每一个子集时，需要检验n(n一1)2条边，所以极大团发

25、现算法的时间复杂度为o(n22”)然后，需要对m个极大团中的每一个进行验证，看其中的k条边是否满足距离阈值要求，从而检验该极大团是否能够形成聚集，时间复杂度为O(mk)最后，GR算法总时间复杂度为O(n22”+mGR+算法使用具有较高速率的BK算法，时间复杂度为0(3们)【24】；同时，GR+算法使用规则l过滤m个极大团中的相似的项，使用规则2过滤不满足边集要求的极大团，使得验证极大团的复杂度降为O(109(mD)最后，GR+算法总时间复杂度为D(3柏+log(mk)实际情况中，GR每次查询时只需遍历时空图中的移动对象聚类节点，而无需遍历全部的轨迹数据，较CrowdTAD具有较高的查询效率同时

26、，GR+算法又使用了高效的极大团检索算法和剪枝策略，使得检索的时间复杂度进一步优化因此，GR+算法是一种高效的聚集检索算法2实验比较与分析为了验证移动对象聚集模式挖掘方法的准确性和高效性，我们在真实的出租车轨迹数据集下进行了实验，并与现有的移动对象聚集模式挖掘算法【3】进行比较21实验建立我们使用真实世界的汽车轨迹数据251来验证移动对象聚集模式挖掘方法的准确性和高效性该数据集包含了752MB的汽车轨迹数据，是从北京10 357辆出租车采集的一周的行驶轨迹(http：researchmicrosoftcornappspubs?id=152883)图5是轨迹数据集的一个示例图，随机抽取1 200

27、辆汽车的轨迹，画出每辆车的行驶轨迹位置形成该图图中的黑点为汽车的行驶位置，较黑的线段是车辆通行量较大的线路，黑团为较易形成密集群组万方数据358 Journal of Software软件学报V0127，No2，February 2016的地段近期与本文最相近的研究是移动对象聚集模式挖掘算法CrowdTAD该算法由文献3】提出，使用增量式算法逐步扩展移动对象序列本文通过与CrowdTAD的对比来说明本文所提出方法的准确性和高效性实验的硬件平台是4核Intel Xeon cPo(2000Hz)，16G内存，运行Linux操作系统，所有的程序均使用C+实现飘，：t仆i二丁M 弋。 l麟I穗 事霪一

28、。jPj 一。 飞 7t讲 娥 自a 薹II日f一。士口 Pli厂1 霸呻_tt 奠“1 r=u叫 种 9-eClm 警憾 |、 ，_ 彩陌、1 - J_，H 睡 一 7一矾 hl t 蛳f一-i 。王 ； 强圈警 L-；斗rI 一：随 巷 孓 bi 到II 髓!i 槲氇 o rh11 7二卜j4- i-一， 上 ： I鞋睁l 刊鼠 _ _- u鞘!r_扯? H- ULkt-UI_- 一J、l E_ h一i=量! 式 -rrYlJ r一It|， 0p“ux n一毛 已 一 盼 辩l 。主J m H隧 蜂 、 羚I一彳r耳 ，I LL一，0 1，卫 硼 K什I，r!Jr 7 1i一 磷 一 湖一

29、 譬 丑曩 ：一 Y一 ： 、 j 一，：l、i?Fig5 Trajectory dataset graph图5轨迹数据集图22准确性对比首先，我们通过计算某个地区或者某个时间段的移动对象聚集数来与之前的研究【3】进行准确性对比GR与GR+在检索的准确性方面没有差别，在此选用GR+算法与CrowdTAD算法进行准确性对比这一组实验中默认参数的设置为：移动对象数据库IOoBl=10357，时间数据库ToB划分为(7x24x360)个时间点，每个时间片tp=lO，移动对象聚集成员阈值聊产8，聚类的生存时间阈值k。=20，移动对象聚集成员阈值mc=8，时间阈值g=20，距离阈值6=800图6(a)给

30、出了单日、工作日和周末的移动对象聚集数的平均值实验收集一周7天内所有的移动对象聚集数后求出一天的平均值，将7天的轨迹数据分为工作日和周末两类，计算出相应的平均聚集数，结果如图所示可以看出，GR+与Crowd-TAD在单日、工作日、周末的移动对象聚集数基本是相同的这说明本方法提出的移动对象聚集模式挖掘方法在准确性方面与现有的研究具有相同的准确度我们也注意到，周末的聚集数远大于工作日的聚集数这是因为大多数人在工作日一般都是早上上班、晚上下班，一天中多数时间都待在工作地点，所以聚集主要在这两个时间段形成但是周末许多人都会驾车出入商场、餐厅以及其他娱乐场所，这些是较容易形成聚集的地方所以，在工作日形成

31、的聚集数比周末少很多图6(b)是7天中每个小时的平均聚集数根据实际的交通情况得知，北京市的交通在一天中的上下班高峰期经常会出现拥堵情况如图所示，一天中的聚集数在14：00出现峰值，但是在23：007：00都会保持在较低水平因为我们使用的是出租车数据，每天中午都会有较多的人打车，但是晚上出门的人则较少我们还可以观察到，在18：00时也会出现一个次高的峰值，因为这个时段是下班高峰期这个结果基本与北京市的交通情况一致第3个实验统计6个不同区域在单日的平均聚集数，分别是东单、天宁寺桥、中关村、国贸桥、马家楼桥和延庆，这6个地点包括3个较易发生拥堵的地区和3个通行相对顺畅的地区分别获得这6个地区7天的聚

32、集数平均值，结果如图6(c)所示可以发现，发生聚集数发生最多的地区是东单主要原因是东单靠近天安门，车流量较大，很容易形成汇聚的情况；相反，延庆的聚集数较少，这是因为延庆在北京郊区，面积大，车流少，所以不容易形成聚集我们还可以发现：在3个容易发生拥堵的地区，移动对象聚集数差别不大因为在北京的繁华地区车流量都很大，所以汽车的平均行驶速度也相对缓慢，容易发生聚集万方数据张峻铭等：基于时空图的移动对象聚集模式挖掘方法单日 工作日 周末(a)GR+与CrowdTAD移动对象聚集数东单天宁寺桥中关村国贸桥马家楼桥延庆(C)5个区域的移动对象聚集数时间点(h)(b)一天24小时内的移动对象聚集数时间点(da

33、yl(d)GR+与CrowdTAD聚集的相似性对比Fig6 Average gathering number of GR+VSCrowdTAD图6 GR+和CrowdTAD平均聚集数比较359最后一个实验对GR+算法和CrowdTAD算法挖掘出的聚集的相似性进行验证，图6(d)是7天中两种算法得出的聚集的平均相似值我们提取一周7天中的聚集集合，根据定义9，使用sim=Lgln92lllglL)92来计算两个聚集自和92的相似性，其中gl和92分别为GR+算法和CrowdTAD算法得出的同一聚集在图6(d)中可以发现，使用两种算法挖掘出的聚集集合具有较高的相似性23检索效率对比在这一组实验中，我

34、们主要通过改变聚集成员阈值小。和移动对象聚类数ICl与已有方法进行效率对比，使用的默认参数是移动对象数据库IODsl=10357，时间数据库殇口划分为(7x24x360)个时间点，每个时间片tp=lO，移动对象聚类成员阈值所。=8，聚类的生存时间阈值kc=20，时间阈值p=20，距离阈值8=800用4种算法进行效率对比：(a)Bruteforce从轨迹数据中提取包含所需时间和地点的轨迹数据并组成轨迹快照，循环遍历轨迹快照不断扩大移动对象群组，直到发现移动对象聚集；(b)CrowdTAD从轨迹数据中抽取出全部快照，根据时间和地点使用Crowd-TAD算法检索聚集数；(c)GR算法；(d)GR+用

35、改进的极大团检索及剪枝策略实现的GR算法每一个实验均随机选取100个时刻和100个地点进行检索，重复lO次并计算聚集检索时间的平均值图7(a)所示为算法在移动聚类数ICl=7000，变化聚集成员阈值小。时的运行时间从图中可以看出，当肌。增大时，bruteforce和CrowdTAD的运行时间都有一定程度的升高，但是GR的运行时间基本保持不变主要原因是，bruteforce和CrowdTAD实现都需要大量的循环来遍历轨迹快照寻找群组，但是GR搜索依据的是时空流的结构，无论m。如何变化，运行时间都只与图的结构有关图7(b)所示为变化聚类数lq，保持坍产7不变时4种算法的运行时间可以明显地看出，随着

36、ICI的增大，4种算法的运行时间都随着增加，但是GR算法的运行时间仍然远小于另外两种算法聚类数ICl增大，一定会导致时空图规模的上升，检索的时间也随之增大；同时，bruteforce和CrowdTAD遍历的次数也会增加，但是GR算法仍然保持着较高的运行效率从图中我们也可以明显看出，GR+的运行时间低于GR这是因为GR+采用了高效极大团检索算法，剪枝策略也使搜索空间减小根据这一组实验，我们可以看出GR+算法拥有较高的检索效率0钉如”加Mm，0万方数据360 Journal of Software软件学报V0127，No2，February 2016mg(a)变化mg的运行时间l 00000001

37、0 000001000000100000010000OOlOO0000lO00000l【Cf(b)变化lq的运行时间Fig7 Running time of four gathering retrieving algorithm图7 4种聚集检索算法的运行时间图8分别是使用剪枝和不使用剪枝的GR+算法使用与上述实验一样的方法，图8(a)固定聚类数Iq改变闽值，移动对象聚集的检索时间随着mg的增大基本保持不变在图8(b)中，检索时间增长较快从这两个图中我们可以看出，使用剪枝策略的GR+算法的运行效率明显高于一般的GIH算法这是因为剪枝使搜索空间减小。加快了搜索的收敛速度(a)变化m。的运行时间l

38、CI(b)变化lq的运行时间Fig8 Running time of GR+with pruning and without pruning图8使用剪枝策略与不使用剪枝策略的GR+算法的运行时间图9给出了当一个新的移动快照加入导致聚类数Iq增大时，GR更新时空图的时间和CrowdTAD扩展一个移动群组(crowd)的时间CCIFig9 Updating snapshot time of GR+VSCrowdTAD图9 GIH与CrowdTAD的更新快照时间对比如前所述，Crowd-TAD算法只遍历给定时间的相邻轨迹快照，所以它的运行时间基本保持不变GR需要维万方数据张峻铭等：基于时空图的移动对

39、象聚集模式挖掘方法 361护一个时空图，所以当聚类数Jq增大时，更新图的时间会呈指数级增长可以明显看出，GR的时间的增长速度大于CrowdTAD，但是总体时间还是小于CrowdTAD为了避免维护时空图给检索带来的额外的时间开销，将时空图放在线下维护，每次获得一个新的移动快照时都传给线下系统，这样就可以不影响总体查询的效率3结论移动对象聚集模式挖掘是移动模式挖掘中一个重要的研究问题通过分析移动对象的聚集模式，我们可以实时观测城市的交通状况，提供路线规划服务然而，目前关于移动对象聚集模式的研究主要关注如何发现聚集模式，挖掘特定时空约束条件下的聚集模式，需要遍历所有的轨迹数据，极大地增加了挖掘的时间

40、开销此外，现有的移动对象索引机制只支持单个移动对象，不能分析多个群组以及它们的移动趋势已有的数据模型不能适应群组间强时空约束的条件，缺乏必要的灵活性，影响了聚集模式挖掘的效率为了解决上述问题，本文提出了一种移动对象聚集模式挖掘方法该方法首先对DBScan算法进行了改进，以根据轨迹数据中的时空特性对移动对象进行聚类然后，为了更加灵活、高效地挖掘满足时空约束条件的聚集模式，提出了一种时空图模型该模型由移动对象聚类组成，可以实时观测移动对象聚类的变化情况最后，该方法根据聚集的特点提出了一种改进的聚集检索算法以提高检索效率基于北京市真实的汽车轨迹数据上的实验结果表明：与其他方法相比，本文提出的移动对象

41、聚集模式挖掘方法具有更高的准确性和检索效率致谢我们向提供出租车行驶轨迹数据集的微软亚洲研究院的郑宇博士表示感谢References：【1】Dieter P，Jensen CSIndexing of network constrained moving objectsIn：Procof the 1 lth ACM Intl Sympon Advances inGeographic Information SystemsNew Orleans：ACM Press，20032532doi：101 145956676956680】【2】 Bart K Othman WModeling uncertai

42、nty of moving objects on road networks via space-time prismsIntl Journal of GeographicalInformation Science，2009，23(9)：1095-1 1 17【doi：10108013658810802097485】【3】Zheng K。Zheng Y，Yuan NJ，Shung SOn discovery of gathering patterns from trajectoriesIn：Procof the 29th IEEE Int1 Confon Data EngineeringBri

43、sbane：IEEE，2013242-253【doi：101 109ICDE20136544829】【4】Patrick L。Imfeld SAnalyzing relative motion within groups of trackable moving point objectsIn：Procof the 2nd Intl ConfonGeographic Information ScienceBoulder：Springer-Verlag，2002132144【doi：10100713-540-45799210】【515 Gudmundsson J，Van Kreveld MComp

44、uting longest duration flocks intrajectory dataIn：Procof the 1 8th ACM IntI SymponAdvances in Geographic Information SystemsArlington：ACM Press，200635-42【doi：101 1451 1834711 183479】6】Li ZH，Ding BL，Han JW，Kays RSwarm：Mining relaxed temporal moving object clustersProcofthe VLDB Endowment，2010，3(1-2)：

45、723-734【doi：101477819208411920843】【7】Tang LA，Zheng Y，Yuan J，Han JW，Leung A，Hung CC，Peng WCOn discovery of traveling companions from streamingtrajectoriesIn：Procofthe 28th IEEE Intl Confon Data EngineeringWashington：IEEE，2012186-197【doi：101 109ICDE201233】【8】Liu W，Zheng Y，Chawla S，Yuan J，Xie XDiscover

46、ing spatiotemporal causal interactions in traffic data streamsIn：Procof the17th Intl Confon Knowledge Discovery and Data MiningSan Diego：ACM Press，20111010-1018【doi：10114520204082020571】【9】9 Pang LXL，Chawla S，Liu W，Zheng YOn mining anomalous patterns in road traffic streamsIn：Procof the 7th Intl Con

47、fonAdvancedDataMiningandApplicationsBeijing：Springer-Verlag，2011237251【doi：1010079783642258565181【10】Pang LX，Chawla S，Liu W，Zheng YOn detection of emerging anomalous traffic patterns using GPS dataData&KnowledgeEngineering，2013，87：357-373【doi：1010160datak201305002】【I I】Chawla S，zhg Y。HuIFInferring the root cause in road traffic anomaliesIn：Procofthe 12th IEEE Intl Confon Data Mining-Brussels：IEEE，2012141150【doi：101 109ICDM2012104】【12】 Yu YW，Wang Q，Wang XD，Wang H，He JOnline clustering for trajectory dat