帮助 关于我们

返回检索结果

利用MapReduce的异常轨迹检测并行算法
A Parallel Algorithm for Detecting Trajectory Outliers Based on MapReduce

查看参考文献22篇

文摘 异常轨迹检测是移动对象数据挖掘的一个重要研究领域。TRAOD(TRAjectory Outlier Dectection Algorithm)算法是一种经典的异常轨迹检测算法,但它对于海量轨迹数据的异常检测效率低。为提高海量轨迹数据集的异常检测效率,本文提出了一种利用MapReduce的异常轨迹检测并行算法(Parallel algorithm for TRAjectory Outlier Detection, PTRAOD),并在此基础上提出了网格索引的异常轨迹检测并行算法(Grid-based Parallel algorithm for TRAjectory Outlier Dectection, GPTRAOD)。GPTRAOD算法在PTRAOD算法的基础上,利用网格索引实现区域查询,进一步提高算法效率。将PTRAOD算法和GPTRAOD算法在Hadoop平台上加以实现,结果表明:本文提出的2个并行检测算法,能实现异常轨迹的检测;GPTRAOD算法的效率优于PTRAOD算法;GPTRAOD算法具有较高的可扩展性和较好的加速比。
其他语种文摘 Trajectory outlier detection is significantly important in the field of data mining for moving object. TRAOD (TRAjectory Outlier Dectection Algorithm), a classic algorithm for detecting trajectory outliers, focuses on a new two-level trajectory partitioning strategy to enhance the efficiency of algorithm. The main advantage of TRAOD algorithm is the ability to detect outlying sub-trajectories. However, it has a low efficiency on abnormality detection for massive trajectory data. In order to improve the efficiency for mining trajectory outliers from massive datasets, a parallel algorithm for detecting trajectory outliers based on MapReduce framework, which is called PTRAOD (Parallel algorithm for TRAjectory Outlier Detection), is presented. It redesigns the TRAOD algorithm based on the MapReduce framework, and encapsulates the steps of TRAOD into its Map and Reduce functions. PTRAOD algorithm takes full advantages of the features from Hadoop platform. It firstly distributes the trajectory data into distributed computing nodes. While distributing the data, it also takes the load-balance into consideration. And after all, each node runs the same algorithms to detect abnormal trajectories. Based on PTRAOD algorithm, a grid-based parallel algorithm for detecting trajectory outliers, called GPTRAOD (Grid-based Parallel algorithm for TRAjectory Outlier Detection), is then proposed. GPTRAOD algorithm makes use of the grid index to realize regional query and reduce unnecessary calculations. At first, GPTRAOD algorithm divides the map into a series of equal-sized grids, whose size is determined with respect to each specific data. Then, the grid index is established to implement the regional query. Finally, the algorithm finds out the abnormal trajectory segments and judges whether the trajectories that contains the abnormal trajectory segments are abnormal. In general, GPTRAOD algorithm takes advantages of the gird index to realize regional query on the basis of PTRAOD algorithm, which furthermore can search abnormal trajectory on the cloud computing platform. To assess the performances of the proposed algorithms, extensive experiments were conducted. The experimental results demonstrate that the proposed two parallel detection algorithms can both successfully achieve the trajectory outlier detection. The efficiency of PTRAOD algorithm is higher than TRAOD algorithm, while GPTRAOD algorithm has the higher scalability and better speedup ratio than PTRAOD algorithm. In addition, with the rapidly expanding of datasets, GPTRAOD algorithm shows obvious advantages and increasing potentials.
来源 地球信息科学学报 ,2015,17(5):523-530 【核心库】
DOI 10.3724/SP.J.1047.2015.00523
关键词 异常轨迹检测 ; 网格索引 ; 并行数据挖掘 ; MapReduce
地址

南京师范大学计算机科学与技术学院, 南京, 210023

语种 中文
文献类型 研究性论文
ISSN 1560-8999
学科 社会科学总论;测绘学
基金 国家自然科学基金
文献收藏号 CSCD:5431084

参考文献 共 22 共2页

1.  Liao L. Learning and inferring transportation routines. Artificial Intelligence,2007,171(5):311-331 被引 17 次    
2.  Yuan J. T-drive:Driving directions based on taxi trajectories. Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems,2010:99-108 被引 25 次    
3.  Giannotti F. Trajectory pattern mining. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2007:330-339 被引 24 次    
4.  Yu Y. Detecting moving object outliers in massive-scale trajectory streams. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2014:422-431 被引 4 次    
5.  Li X. Temporal outlier detection in vehicle traffic data. Proceedings of the 25th International Conference on Data Engineering,2009:1319-1322 被引 1 次    
6.  Ge Y. A taxi driving fraud detection system. 2011 IEEE 11th International Conference on Data Mining (ICDM),2011:181-190 被引 1 次    
7.  Barnett V. Outliers in statistical data,1994 被引 68 次    
8.  Knorr E M. Finding intentional knowledge of distance-based outliers. Proceedings of the 25th International Conference on Very Large Data Bases, 99,1999:211-222 被引 1 次    
9.  Breunig M M. LOF:Identifying density-based local outliers. Proceedings of 2000 ACM SIGMOD International Conference on Management of Data, 29(2),2000:93-104 被引 1 次    
10.  Aggarwal C C. Outlier detection for high dimensional data. Proceedings of 2001 ACM SIGMOD International Conference on Management of Data, 30(2),2001:37-46 被引 1 次    
11.  姜金凤. 移动对象轨道异常检测算法的研究,2010:1-19 被引 3 次    
12.  Knorr E M. Distance-based outliers:algorithms and applications. The VLDB Journal:The International Journal on Very Large Data Bases,2000,8(3/4):237-253 被引 82 次    
13.  Li X. ROAM:Rule-and motif-based anomaly detection in massive moving object data sets. Proceedings of the SIAM International Conference on Data Mining. Minneapolis, 7,2007:273-284 被引 1 次    
14.  刘良旭. 基于R-Tree的高效异常轨迹检测算法. 软件学报,2009,20(9):2426-2435 被引 12 次    
15.  Lee J G. Trajectory outlier detection:A partition-and-detect framework. Proceedings of the 24th International Conference on Data Engineering,2008:140-149 被引 7 次    
16.  Liu L. Efficiently mining outliers from trajectories of unrestraint movement. Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering, 2,2010:V2-261-V2-265 被引 1 次    
17.  Isaksson C. A comparative study of outlier detection algorithms. Machine Learning and Data Mining in Pattern Recognition,2009:440-453 被引 1 次    
18.  Armbrust M. A view of cloud computing. Communications of the ACM,2010,53(4):50-58 被引 322 次    
19.  Dean J. MapReduce:Simplified data processing on large clusters. Communications of the ACM,2008,51(1):107-113 被引 742 次    
20.  Dean J. MapReduce:A flexible data processing tool. Communications of the ACM,2010,53(1):72-77 被引 95 次    
引证文献 3 篇

1 姚楠 MapReduce架构下的大规模轨迹数据压缩策略 小型微型计算机系统,2017,38(5):941-945
被引 0 次

2 蒋华 基于轨迹信息熵分布的异常轨迹检测方法 计算机应用研究,2018,35(6):1655-1659
被引 3 次

显示所有3篇文献

论文科学数据集
PlumX Metrics
相关文献

 作者相关
 关键词相关
 参考文献相关

版权所有 ©2008 中国科学院文献情报中心 制作维护：中国科学院文献情报中心
地址：北京中关村北四环西路33号 邮政编码：100190 联系电话：(010)82627496 E-mail:cscd@mail.las.ac.cn 京ICP备05002861号-4 | 京公网安备11010802043238号