Computer Science ›› 2019, Vol. 46 ›› Issue (1): 251-259.doi: 10.11896/j.issn.1002-137X.2019.01.039

• Artificial Intelligence • Previous Articles     Next Articles

iBTC:A Trajectory Clustering Algorithm Based on Isolation Forest

ZHANG Huai-feng, PI De-chang, DONG Yu-lan   

  1. (College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)
  • Received:2017-11-27 Online:2019-01-15 Published:2019-02-25

Abstract: The clustering of moving object trajectories has important theoretical and practical value in the fields of urban planning,public space design and mobile object behavior prediction.In this paper,aiming at the poor clustering effect of traditional clustering algorithms (e.g.,k-means,DBSCAN) on moving object trajectories,a new trajectory clustering algorithm named iBTC was proposed.The algorithm segments the trajectory firstly,and based on the principle of minimum description length,the trajectory segmentation problem is modeled as the shortest path problem for undirected graphs.Then,Dijkstra algorithm is used to find the optimal segmentation.Next,based on the idea of Isolation Forest,the trajectory clustering problem is transformed into a special anomaly detection problem,and the algorithm uses partition-merging procedure to cluster trajectory data.Finally,experiments were performed on the simulated data set and pedestrian track data recorded by monitor.The results show that the algorithm can achieve good clustering effect.

Key words: Clustering, Isolation forest, Moving object, Trajectory segmentation

CLC Number: 

  • TP309
[1]ACHTERT E,KRIEGEL H P,ZIMEK A.Deriving quantitative models for correlation clusters[C]//ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining.ACM,2006:4-13.<br /> [2]周志华.机器学习[M].北京:清华大学出版社,2016.<br /> [3]LLOYD S.Least squares quantization in PCM[J].IEEE Transactions on Information Theory,1982,28(2):129-137.<br /> [4]ZHANG T,RAMAKRISHNAN R,LIVNY M.BIRCH:An Effcient Data Clustering Method for Very Large Databases[C]//ACM SIGMOD Int’l Conference on Management of Data.ACM,1996:103-114.<br /> [5]ESTER M,KRIEGEL H P,XU X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]//International Conference on Knowledge Discovery and Data Mining.AAAI Press,1996:226-231.<br /> [6]WANG W,YANG J,MUNTZ R R.STING:A Statistical Information Grid Approach to Spatial Data Mining[C]//Internatio-nal Conference on Very Large Data Bases.Morgan Kaufmann Publishers Inc,1997:186-195.<br /> [7]NICOL F,PUECHMOREL S.Trajectories clustering:a minimum entropy approach[C]//The Second International Confe-rence on Big Data,Small Data.Linked Data and Open Data,2016:35-41.<br /> [8]LEE J G,HAN J,WHANG K Y.Trajectory clustering:a partition-and-group framework[C]//ACM SIGMOD International Conference on Management of Data.ACM,2007:593-604.<br /> [9]ZHANG D,LI N,ZHOU Z H,et al.iBAT:detecting anomalous taxi trajectories from GPS traces[C]//International Conference on Ubiquitous Computing.ACM,2011:99-108.<br /> [10]PALMA A T,BOGORNY V,KUIJPERS B,et al.A clustering-based approach for discovering interesting places in trajectories[C]//ACM Symposium on Applied Computing.DBLP,2008:863-868.<br /> [11]MASCIARI E.A Framework for Trajectory Clustering[C]//International Conference on Geosensor Networks.Springer-Verlag,2009:102-111.<br /> [12]HUNG C C,PENG W C,LEE W C.Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J].Vldb Journal,2015,24(2):169-192.<br /> [13]FLORIAN T,POKORNY F T,GOLDBERG K,et al.Topological trajectory clustering with relative persistent homology[C]//IEEE International Conference on Robotics and Automation.IEEE,2016:16-23.<br /> [14]GAFFNEY S,SMYTH P.Trajectory clustering with mixtures of regression models[C]//ACM SIGKDD International Confe-rence on Knowledge Discovery and Data Mining.ACM,1999:63-72.<br /> [15]IZAKIAN Z,MESGARI M S,ABRAHAM A.Automated clustering of trajectory data using a particle swarm optimization[J].Computers Environment & Urban Systems,2016,55:55-65.<br /> [16]NANNI M,PEDRESCHI D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems,2006,27(3):267-289.<br /> [17]MITSCH S,MLLER A,RETSCHITZEGGER W,et al.A Survey on Clustering Techniques for Situation Awareness[M]//Web Technologies and Applications.Springer Berlin Heidelberg,2013:815-826.<br /> [18]YASODHA M,PONMUTHURAMALINGAM P.A survey on temporal data clustering[J].International Journal of Advanced Research in Computer and Communication Engineering,2016,1(9):768-772.<br /> [19]YUAN G,XIA S,ZHANG L,et al.An efficient trajectory-clustering algorithm based on an index tree[J].Transactions of the Institute of Measurement & Control,2012,34(7):850-861.<br /> [20]LI Z,JAEGIL L,LI X,et al.Incremental Clustering for Trajectories[C]//International Conference on Database Systems for Advanced Applications.Springer-Verlag,2010:32-46.<br /> [21]LIU F T,KAI M T,ZHOU Z H.Isolation Forest[C]//Eighth IEEE International Conference on Data Mining.IEEE Computer Society,2008:413-422.<br /> [22]CHEN M,CHOWDHURYR A,RAMACHANDRAN V,et al.Priority Queues and Dijkstra’s Algorithm.USA:University of Texas,2007:1-25.<br /> [23]FISHER B.Edinburgh informatics forum pedestrian database [OL].http://homepages.inf.ed.ac.uk/rbf/FORUMTRACKING.
[1] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[2] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[3] YU Shu-hao, ZHOU Hui, YE Chun-yang, WANG Tai-zheng. SDFA:Study on Ship Trajectory Clustering Method Based on Multi-feature Fusion [J]. Computer Science, 2022, 49(6A): 256-260.
[4] MAO Sen-lin, XIA Zhen, GENG Xin-yu, CHEN Jian-hui, JIANG Hong-xia. FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition [J]. Computer Science, 2022, 49(6A): 285-290.
[5] CHEN Jing-nian. Acceleration of SVM for Multi-class Classification [J]. Computer Science, 2022, 49(6A): 297-300.
[6] Ran WANG, Jiang-tian NIE, Yang ZHANG, Kun ZHU. Clustering-based Demand Response for Intelligent Energy Management in 6G-enabled Smart Grids [J]. Computer Science, 2022, 49(6): 44-54.
[7] CHEN Jia-zhou, ZHAO Yi-bo, XU Yang-hui, MA Ji, JIN Ling-feng, QIN Xu-jia. Small Object Detection in 3D Urban Scenes [J]. Computer Science, 2022, 49(6): 238-244.
[8] XING Yun-bing, LONG Guang-yu, HU Chun-yu, HU Li-sha. Human Activity Recognition Method Based on Class Increment SVM [J]. Computer Science, 2022, 49(5): 78-83.
[9] ZHU Zhe-qing, GENG Hai-jun, QIAN Yu-hua. Line-Segment Clustering Algorithm for Chemical Structure [J]. Computer Science, 2022, 49(5): 113-119.
[10] ZHANG Yu-jiao, HUANG Rui, ZHANG Fu-quan, SUI Dong, ZHANG Hu. Study on Affinity Propagation Clustering Algorithm Based on Bacterial Flora Optimization [J]. Computer Science, 2022, 49(5): 165-169.
[11] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[12] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[13] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[14] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[15] ZHANG Ya-di, SUN Yue, LIU Feng, ZHU Er-zhou. Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index [J]. Computer Science, 2022, 49(1): 121-132.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!