基于时空图的移动对象聚集模式挖掘方法  

Mining Moving Object Gathering Pattern Method Via Spatio-Temporal Graph

作　　者：张峻铭[1] 李静林[1] 王尚广[1] 刘志晗[1] 袁泉[1] 杨放春[1] 

机构地区：[1]交换与智能控制国家重点实验室(北京邮电大学),北京100876

出　　处：《软件学报》2016年第2期348-362,共15页Journal of Software

基　　金：国家自然科学基金(61202435);国家高技术研究发展计划(863)(2012AA111601);北京市自然科学基金(4132048)~~

摘　　要：移动对象聚集模式是指由移动对象参与的一组群体事件,通常用来预测交通系统中出现的异常现象.然而由于海量移动轨迹数据的产生,已有的研究方法难以准确、高效地挖掘特定的聚集模式.为此,提出一种基于时空图的移动对象聚集模式挖掘方法.该方法首先通过改进的空间聚类算法(DBScan)分析轨迹数据,从而获得移动对象聚类;然后,利用时空图模型代替单独存储轨迹数据的方式,用于实时观测移动对象聚类的时空变化特征.最后提出基于最大完全子图查找的聚集检索算法及其改进算法,用于查找满足时空约束的最大完全子图.基于真实大规模轨迹数据集上的实验结果表明,所提出的方法在移动对象聚集模式挖掘的准确性和高效性方面优于其他方法.Moving object gathering pattem represents a group event or incident that involves congregation of moving objects, enabling the prediction of anomalies in traffic system. However, effectively and efficiently discovering the specific gathering pattern remains a challenging issue since the large number of moving objects generate high volume of trajectory data. In order to address this issue, this article proposes a moving object gathering pattern mining method that aims to support the mining of gathering patterns by using spatio-temporal graph. In this method, firstly an improved density based clustering algorithm （DBScan） is used to collect the moving object clusters. Then, a spatio-temporal graph is maintained rather than storing the spatial coordinates to obtain the spatio-temporal changes in real time. Finally, a gathering mining algorithm and its improved version are developed by searching the maximal complete graphs which meet the spatio-temporal constraints. The effectiveness and efficiency of the proposed methods are outperformed other existing methods on both real and large trajectory data.

关 键 词：聚集模式挖掘 时空图 轨迹数据 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]