基于时空图的移动对象聚集模式挖掘方法-张峻铭.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《基于时空图的移动对象聚集模式挖掘方法-张峻铭.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算法找到包含这个点的所有极大团,得到
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 时空 移动 对象 聚集 模式 挖掘 方法 张峻铭
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内