全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

DOI: 10.3724/SP.J.1047.2015.00523, PP. 523-530

Keywords: 异常轨迹检测,网格索引,并行数据挖掘,MapReduce

Full-Text   Cite this paper   Add to My Lib

Abstract:

异常轨迹检测是移动对象数据挖掘的一个重要研究领域。TRAOD(TRAjectoryOutlierDectectionAlgorithm)算法是一种经典的异常轨迹检测算法,但它对于海量轨迹数据的异常检测效率低。为提高海量轨迹数据集的异常检测效率,本文提出了一种利用MapReduce的异常轨迹检测并行算法(ParallelalgorithmforTRAjectoryOutlierDetection,PTRAOD),并在此基础上提出了网格索引的异常轨迹检测并行算法(Grid-basedParallelalgorithmforTRAjectoryOutlierDectection,GPTRAOD)。GPTRAOD算法在PTRAOD算法的基础上,利用网格索引实现区域查询,进一步提高算法效率。将PTRAOD算法和GPTRAOD算法在Hadoop平台上加以实现,结果表明本文提出的2个并行检测算法,能实现异常轨迹的检测;GPTRAOD算法的效率优于PTRAOD算法;GPTRAOD算法具有较高的可扩展性和较好的加速比。

References

[1]  Liao L, Patterson D J, Fox D, et al. Learning and inferring transportation routines[J]. Artificial Intelligence, 2007,171(5):311-331.
[2]  Yuan J, Zheng Y, Zhang C, et al. T-drive: Driving directions based on taxi trajectories[C]. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010:99-108.
[3]  Giannotti F, Nanni M, Pinelli F, et al. Trajectory pattern mining[C]. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007:330-339.
[4]  Yu Y, Cao L, Rundensteiner E A, et al. Detecting moving object outliers in massive-scale trajectory streams[C]. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2014:422-431.
[5]  Li X, Li Z, Han J, et al. Temporal outlier detection in vehicle traffic data[C]. In: Proceedings of the 25th International Conference on Data Engineering. Washington: IEEE Computer Society, 2009:1319-1322.
[6]  Ge Y, Xiong H, Liu C, et al. A taxi driving fraud detection system[C]. 2011 IEEE 11th International Conference on Data Mining (ICDM), 2011:181-190.
[7]  Barnett V, Lewis T. Outliers in statistical data[M]. New York:Wiley, 1994.
[8]  Knorr E M, Ng R T. Finding intentional knowledge of distance-based outliers[C]. In: Proceedings of the 25th International Conference on Very Large Data Bases. Edinburgh, Scotland: Springer-Verlag, 1999,99:211-222.
[9]  Breunig M M, Kriegel H P, Ng R T, et al. LOF: Identifying density-based local outliers[C]. In: Proceedings of 2000 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2000,29(2):93-104.
[10]  Aggarwal C C, Yu P S. Outlier detection for high dimensional data[C]. In: Proceedings of 2001 ACM SIGMOD International Conference on Management of Data. California: ACM, 2001,30(2):37-46.
[11]  姜金凤.移动对象轨道异常检测算法的研究[D].南京:南 京航空航天大学,2010:1-19.
[12]  Knorr E M, Ng R T, Tucakov V. Distance-based outliers: algorithms and applications[J]. The VLDB Journal?The International Journal on Very Large Data Bases, 2000,8(3-4):237-253.
[13]  Li X, Han J, Kim S, et al. ROAM: Rule-and motif-based anomaly detection in massive moving object data sets[C]. In: Proceedings of the SIAM International Conference on Data Mining. Minneapolis. Minnesota: SIAM, 2007,7: 273-284.
[14]  刘良旭,乔少杰,刘宾,等.基于R-Tree 的高效异常轨迹检 测算法[J].软件学报,2009,20(9):2426-2435.
[15]  Lee J G, Han J, Li X. Trajectory outlier detection: A partition-and-detect framework[C]. In: Proceedings of the 24th International Conference on Data Engineering. Washington: IEEE Computer Society, 2008:140-149.
[16]  Liu L, Fan J, Qiao S, et al. Efficiently mining outliers from trajectories of unrestraint movement[C]. In: Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering, 2010,2:V2-261-V2-265.
[17]  Isaksson C, Dunham M H. A comparative study of outlier detection algorithms[M]. In: Machine Learning and Data Mining in Pattern Recognition. Berlin: Springer Berlin Heidelberg, 2009:440-453.
[18]  Armbrust M, Fox A, Griffith R, et al. A view of cloud computing[J]. Communications of the ACM, 2010,53(4): 50-58.
[19]  Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008,51(1):107-113.
[20]  Dean J, Ghemawat S. MapReduce: A flexible data processing tool[J]. Communications of the ACM, 2010,53(1): 72-77.
[21]  Lee J G, Han J, Whang K Y. Trajectory clustering: A partition-and-group framework[C]. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, 2007:593-604.
[22]  UNISYS. The Atlantic hurricane database[EB/OL]. [2014-9-10]. http://weather.unisys.com/hurricane/atlantic/.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133