| 本文已被：浏览 6560次 下载 9555次 |
码上扫一扫！ |
|
|
| 基于R-Tree的高效异常轨迹检测算法 |
|
刘良旭1,2, 乔少杰3,4, 刘宾5, 乐嘉锦2, 唐常杰4
|
|
1.宁波工程学院 电子与信息工程学院,浙江 宁波 315016;2.东华大学 计算机科学与技术学院,上海 200051;3.西南交通大学 信息科学与技术学院,四川 成都 61003;4.四川大学 计算机学院,四川 成都 610065;5.Department of Computer Science, School of Computing, National University of Singapore, 117590, Singapore
|
|
| 摘要: |
| 提出了异常轨迹检测算法,通过检测轨迹的局部异常程度来判断两条轨迹是否全局匹配,进而检测异常轨迹.算法要点如下:(1) 为了有效地表示轨迹的局部特征,以k个连续轨迹点作为基本比较单元,提出一种计算两个基本比较单元间不匹配程度的距离函数,并在此基础上定义了局部匹配、全局匹配和异常轨迹的概念;(2) 针对异常轨迹检测算法普遍存在计算代价高的不足,提出了一种基于R-Tree的异常轨迹检测算法,其优势在于利用R-Tree和轨迹间的距离特征矩阵找出所有可能匹配的基本比较单元对,然后再通过计算距离确定其是否局部匹配,从而消除大量不必要的距离计算.实验结果表明,该算法不仅具有很好的效率,而且检测出来的异常轨迹也具有实际意义. |
| 关键词: 异常轨迹检测 R树 基于平移的最小Hausdorff距离 全局匹配 局部匹配 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60773169, 60473071 (国家自然科学基金); the 11th Five-Years Key Programs for Sci. &Tech. Development of China under Grant No.2006BAI05A01 (“十一五”国家科技支撑计划); the Youth Software Innovation Project of Sichuan Province of China under Grant No.2007AA0032 (四川省青年软件创新工程) |
|
| Efficient Trajectory Outlier Detection Algorithm Based on R-Tree |
|
LIU Liang-Xu,QIAO Shao-Jie,LIU Bin,LE Jia-Jin,TANG Chang-Jie
|
| Abstract: |
| Recent progress on location aware services, GPS and wireless technologies has made it possible to real-timely track moving object and collect a large quarlity of trajectories data. As a result, how to effectively discover the knowledge from these trajectory data becomes an attractive and interesting research topic. The new trajectory outlier detection, proposed in this paper, can be used to determine whether two trajectories are globally matched by calculating the local matching degree between every base comparing unit pairs. Firstly, this paper proposes a new distance measure approach, which treats k consecutive points as a local comparing unit to depict the local features in terms of trajectories, via calculating the matching degree between trajectory segments. In addition, the critical concepts as local match, global match and trajectory outlier are presented. Secondly, based on this distance measure method, a new trajectory outlier detection algorithm based on R-tree is proposed to improve the efficiency of outlier detection. The main idea behind this algorithm is to eliminate unnecessary distance computation by R-tree and distance characteristic matrix between every trajectory pair. Extensive experiments demonstrate the efficiency and effectiveness of the proposed algorithm for trajectory outlier detection. |
| Key words: trajectory outlier detection R-tree minimum Hausdorff distance under translation global match local match |
