| 摘要: |
| 移动对象聚集模式是指由移动对象参与的一组群体事件,通常用来预测交通系统中出现的异常现象.然而由于海量移动轨迹数据的产生,已有的研究方法难以准确、高效地挖掘特定的聚集模式.为此,提出一种基于时空图的移动对象聚集模式挖掘方法.该方法首先通过改进的空间聚类算法(DBScan)分析轨迹数据,从而获得移动对象聚类;然后,利用时空图模型代替单独存储轨迹数据的方式,用于实时观测移动对象聚类的时空变化特征.最后提出基于最大完全子图查找的聚集检索算法及其改进算法,用于查找满足时空约束的最大完全子图.基于真实大规模轨迹数据集上的实验结果表明,所提出的方法在移动对象聚集模式挖掘的准确性和高效性方面优于其他方法. |
| 关键词: 聚集模式挖掘 时空图 轨迹数据 |
| DOI：10.13328/j.cnki.jos.004797 |
| 分类号: |
| 基金项目:国家自然科学基金(61202435); 国家高技术研究发展计划(863)(2012AA111601); 北京市自然科学基金(4132048) |
|
| Mining Moving Object Gathering Pattern Method Via Spatio-Temporal Graph |
|
ZHANG Jun-Ming, LI Jing-Lin, WANG Shang-Guang, LIU Zhi-Han, YUAN Quan, YANG Fang-Chun
|
|
State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing 100876, China
|
| Abstract: |
| Moving object gathering pattern 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. |
| Key words: gathering pattern mining spatio-temporal graph trajectory data |
