ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

An anomaly detection algorithm for taxis based on trajectory data mining and online real-time monitoring

  • Research and Development Center of Software Engineering and Technology, Institute of Software Chinese Academy of Sciences, Beijing 100190, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2016.03.010
  • Received Date: 12 September 2015
  • Accepted Date: 29 December 2015
  • Rev Recd Date: 29 December 2015
  • Publish Date: 30 March 2016
    Abstract

  • Abstract

    Taking the prevention of taxi frauds as a motivating example, an anomalous spatio-temporal trajectory detection method that combines offline mining and online detection was proposed. A city roadmap was partitioned into a grid based on the longitude and latitude, using Pathlet sequences to express taxi trajectories instead of the traditional GPS sequences. Then, K-racial classes’ normal sequences were clustered in the same origin-destination pair from history data sets. The incoming online GPS data was transformed into Pathlet sequences and matched with K-racial classes’ normal sequences. The distance was computed and scored. Distance along with spatial and temporal factors together forms the criterion for determing anomalous taxi trajectories. Finally, based on the real taxi GPS data sets in Beijing area during March, 2011 to May, 2011, experimental results indicate that the proposed method is able to detect online anomalous trajectories efficiently and quickly.

    Abstract

    Taking the prevention of taxi frauds as a motivating example, an anomalous spatio-temporal trajectory detection method that combines offline mining and online detection was proposed. A city roadmap was partitioned into a grid based on the longitude and latitude, using Pathlet sequences to express taxi trajectories instead of the traditional GPS sequences. Then, K-racial classes’ normal sequences were clustered in the same origin-destination pair from history data sets. The incoming online GPS data was transformed into Pathlet sequences and matched with K-racial classes’ normal sequences. The distance was computed and scored. Distance along with spatial and temporal factors together forms the criterion for determing anomalous taxi trajectories. Finally, based on the real taxi GPS data sets in Beijing area during March, 2011 to May, 2011, experimental results indicate that the proposed method is able to detect online anomalous trajectories efficiently and quickly.
    • FullText(HTML)
  • loading
    • References(19)
  • [1]
    CHANDOLA V, BANERJEE A, KUMAR V. Anomaly detection a survey[J]. ACM Computing Surveys, 2009, 41(3): 75-79.
    [2]
    VELOSO M, PHITHAKKITNUKOON S, BENTO C. Sensing urban mobility with taxi flow[C]// Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks. Chicago, USA: ACM Press, 2011: 41-44.
    [3]
    ZHU B, HUANG Q, GUIBAS L, et al. Urban population migration pattern mining based on taxi trajectories[C]// Proceedings of the 3rd International Workshop on Mobile Sensing. Springer, 2015, 9142: 172-181.
    [4]
    ZHENG Y, LIU Y C, YUAN J, et al. Urban computing with taxicabs[C]// Proceedings of the 13th International Conference on Ubiquitous Computing. Beijing, China: ACM Press, 2011: 89-98.
    [5]
    YUAN J, ZHENG Y, ZHANG C Y, et al. T-drive: Driving directions based on taxi trajectories[C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose, USA: ACM Press, 2010: 99-108.
    [6]
    LEE J G, HAN J W, WHANG K Y. Trajectory clustering a partition-and-group framework[C]// Proceedings of the SIGMOD International Conference on Management of Data. Beijing, China: ACM Press, 2007: 593-604.
    [7]
    GE Y, XIONG H, LIU C R, et al. A taxi driving fraud detection system[C]// Proceedings of the 11th International Conference on Data Mining. Vancouver, Canada: IEEE Press, 2011: 181-190.
    [8]
    FU Z Y, HU W M, TAN T N. Similarity based vehicle trajectory clustering and anomaly detection[C]// IEEE International Conference on Image Processing. Beijing, China: IEEE Press, 2005, 2: 602-605.
    [9]
    ZHANG D, LI N, ZHOU Z H, et al. iBAT: Detecting anomalous taxi trajectories from GPS traces[C]// Proceedings of the 13th International Conference on Ubiquitous Computing. Beijing, China: ACM Press, 2011: 99-108.
    [10]
    CHEN C, ZHANG D Q, CASTRO P S, et al. Real-time detection of anomalous taxi trajectories from GPS traces[A]// Mobile and Ubiquitous Systems Computing, Networking, and Services. Berlin Heidelberg: Springer, 2012: 63-74.
    [11]
    GE Y, XIONG H, ZHOU Z H, et al. Top-eye Top-k evolving trajectory outlier detection[C]// Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto, Canada: ACM Press, 2010: 1733-1736.
    [12]
    胡佳峰. 基于轨迹数据的事件检测技术研究[D].硕士学位论文, 中国科学院大学, 2014.
    [13]
    袁晶. 大规模轨迹数据的检索、挖掘及应用[D].博士学位论文, 中国科学技术大学, 2012.
    [14]
    CHEN C, ZHANG D Q, CASTRO P S, et al. iBOAT: Isolation-based online anomalous trajectory detection[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 806-818.
    [15]
    SUN L, ZHANG D, CHEN C, et al. Real time anomalous trajectory detection and analysis[J]. Mobile Networks and Applications, 2013, 18(3) 341-356.
    [16]
    CHEN C, SU H, HUANG Q, et al. Pathlet learning for compressing and planning trajectories[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando, USA: ACM, 2013: 392-395.
    [17]
    LEE A J T, CHEN Y A, IP W C. Mining frequent trajectory patterns in spatial-temporal databases[J]. Information Sciences, 2009, 179(13): 2218-2231.
    [18]
    CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]//Proceedings of the 30th International Conference on Very Large Databases. Toronto, Canada: VLDB Endowment, 2004: 792-803.
    [19]
    HAN B, LIU L, OMIECINSKI E. Neat Road network aware trajectory clustering[C]// 32nd International Conference on Distributed Computing Systems. Macau, China: IEEE, 2012: 142-151.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    CHANDOLA V, BANERJEE A, KUMAR V. Anomaly detection a survey[J]. ACM Computing Surveys, 2009, 41(3): 75-79.
    [2]
    VELOSO M, PHITHAKKITNUKOON S, BENTO C. Sensing urban mobility with taxi flow[C]// Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks. Chicago, USA: ACM Press, 2011: 41-44.
    [3]
    ZHU B, HUANG Q, GUIBAS L, et al. Urban population migration pattern mining based on taxi trajectories[C]// Proceedings of the 3rd International Workshop on Mobile Sensing. Springer, 2015, 9142: 172-181.
    [4]
    ZHENG Y, LIU Y C, YUAN J, et al. Urban computing with taxicabs[C]// Proceedings of the 13th International Conference on Ubiquitous Computing. Beijing, China: ACM Press, 2011: 89-98.
    [5]
    YUAN J, ZHENG Y, ZHANG C Y, et al. T-drive: Driving directions based on taxi trajectories[C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose, USA: ACM Press, 2010: 99-108.
    [6]
    LEE J G, HAN J W, WHANG K Y. Trajectory clustering a partition-and-group framework[C]// Proceedings of the SIGMOD International Conference on Management of Data. Beijing, China: ACM Press, 2007: 593-604.
    [7]
    GE Y, XIONG H, LIU C R, et al. A taxi driving fraud detection system[C]// Proceedings of the 11th International Conference on Data Mining. Vancouver, Canada: IEEE Press, 2011: 181-190.
    [8]
    FU Z Y, HU W M, TAN T N. Similarity based vehicle trajectory clustering and anomaly detection[C]// IEEE International Conference on Image Processing. Beijing, China: IEEE Press, 2005, 2: 602-605.
    [9]
    ZHANG D, LI N, ZHOU Z H, et al. iBAT: Detecting anomalous taxi trajectories from GPS traces[C]// Proceedings of the 13th International Conference on Ubiquitous Computing. Beijing, China: ACM Press, 2011: 99-108.
    [10]
    CHEN C, ZHANG D Q, CASTRO P S, et al. Real-time detection of anomalous taxi trajectories from GPS traces[A]// Mobile and Ubiquitous Systems Computing, Networking, and Services. Berlin Heidelberg: Springer, 2012: 63-74.
    [11]
    GE Y, XIONG H, ZHOU Z H, et al. Top-eye Top-k evolving trajectory outlier detection[C]// Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto, Canada: ACM Press, 2010: 1733-1736.
    [12]
    胡佳峰. 基于轨迹数据的事件检测技术研究[D].硕士学位论文, 中国科学院大学, 2014.
    [13]
    袁晶. 大规模轨迹数据的检索、挖掘及应用[D].博士学位论文, 中国科学技术大学, 2012.
    [14]
    CHEN C, ZHANG D Q, CASTRO P S, et al. iBOAT: Isolation-based online anomalous trajectory detection[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 806-818.
    [15]
    SUN L, ZHANG D, CHEN C, et al. Real time anomalous trajectory detection and analysis[J]. Mobile Networks and Applications, 2013, 18(3) 341-356.
    [16]
    CHEN C, SU H, HUANG Q, et al. Pathlet learning for compressing and planning trajectories[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando, USA: ACM, 2013: 392-395.
    [17]
    LEE A J T, CHEN Y A, IP W C. Mining frequent trajectory patterns in spatial-temporal databases[J]. Information Sciences, 2009, 179(13): 2218-2231.
    [18]
    CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]//Proceedings of the 30th International Conference on Very Large Databases. Toronto, Canada: VLDB Endowment, 2004: 792-803.
    [19]
    HAN B, LIU L, OMIECINSKI E. Neat Road network aware trajectory clustering[C]// 32nd International Conference on Distributed Computing Systems. Macau, China: IEEE, 2012: 142-151.
    Recommended articles
    TrendMD
    Volume 46 Issue 3 page: 247-252
    Cover

    Article Metrics

    Article views (24) PDF downloads(67)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return