利用MapReduce的异常轨迹检测并行算法  

A Parallel Algorithm for Detecting Trajectory Outliers Based on Map Reduce

作　　者：唐梦梦[1] 吉根林[1] 赵斌[1] 

机构地区：[1]南京师范大学计算机科学与技术学院,南京210023

出　　处：《地球信息科学学报》2015年第5期523-530,共8页Journal of Geo-information Science

基　　金：国家自然科学基金项目"云计算环境下顾及用户关系的手机用户时空轨迹模式挖掘方法研究"(41471371)

摘　　要：异常轨迹检测是移动对象数据挖掘的一个重要研究领域。TRAOD(TRAjectory Outlier Dectection Algorithm)算法是一种经典的异常轨迹检测算法,但它对于海量轨迹数据的异常检测效率低。为提高海量轨迹数据集的异常检测效率,本文提出了一种利用Map Reduce的异常轨迹检测并行算法(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 abnormal- ity 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 al- gorithm 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 in- to 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 di- vides 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 abnor- mal. In general, GPTRAOD algorithm takes advantages of the gird index to realize regional query on the basis of PTRAOD algorithm, which furthermore ca

关 键 词：异常轨迹检测 网格索引 并行数据挖掘 MAPREDUCE 

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