计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (24): 127-132.

• 数据库、数据挖掘、机器学习 • 上一篇    下一篇

基于划分的高效异常轨迹检测

陈  刚,钱  猛,刘  金   

  1. 中国工程物理研究院 计算机应用研究所,四川 绵阳 621900
  • 出版日期:2014-12-15 发布日期:2014-12-12

Trajectory outlier detection based on space partition

CHEN Gang, QIAN Meng, LIU Jin   

  1. Institute of Computer Application, China Academy of Engineering Physics, Mianyang, Sichuan 621900, China
  • Online:2014-12-15 Published:2014-12-12

摘要: 为了在海量轨迹数据库中高效准确地挖掘出异常轨迹,提出了基于划分的异常轨迹检测算法。该算法通过计算局部轨迹点之间的匹配程度来探测异常轨迹,将异常轨迹检测由形状匹配问题转化为传统的异常点检测问题,并设计了一种基于空间划分的网格索引结构,提高算法的运行效率。实验证明,该算法不仅具有较高的挖掘效率,而且能够检测出更具实际意义的异常轨迹。

关键词: 异常轨迹, 轨迹点, 空间划分, 网格索引树

Abstract: As the development of mobile computing technology and GPS-enabled mobile devices, the services of moving object receive more and more attention. And trajectory outlier detection is a widely appealing application. In this paper, a novel detection algorithm is proposed to mine trajectory outliers from massive trajectory datasets more efficiently. The algorithm is based on space partition and finds trajectory outliers through mining the local trajectory point outlier. In this way, it converts the problem of finding trajectory to traditional outlier detection problem. In addition, a novel index structure is designed to improve the computing efficiency. Experiments show its higher efficiency and its power to find more meaningful trajectory outlier.

Key words: trajectory outlier, trajectory point, space partition, grid index tree