nach oben

Artificial Intelligence Review

Erschienen in:

25.03.2016

A review of moving object trajectory clustering algorithms

verfasst von: Guan Yuan, Penghui Sun, Jie Zhao, Daxing Li, Canwei Wang

Erschienen in: Artificial Intelligence Review | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Clustering is an efficient way to group data into different classes on basis of the internal and previously unknown schemes inherent of the data. With the development of the location based positioning devices, more and more moving objects are traced and their trajectories are recorded. Therefore, moving object trajectory clustering undoubtedly becomes the focus of the study in moving object data mining. To provide an overview, we survey and summarize the development and trend of moving object clustering and analyze typical moving object clustering algorithms presented in recent years. In this paper, we firstly summarize the strategies and implement processes of classical moving object clustering algorithms. Secondly, the measures which can determine the similarity/dissimilarity between two trajectories are discussed. Thirdly, the validation criteria are analyzed for evaluating the performance and efficiency of clustering algorithms. Finally, some application scenarios are point out for the potential application in future. It is hope that this research will serve as the steppingstone for those interested in advancing moving object mining.

Vorheriger Artikel The variants of the Bees Algorithm (BA): a survey

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Alvares LO, Bogorny V, Kuijpers B, Macedo JAF, Moelans B, Vaisman A (2007) A model for enriching trajectories with semantic geographical information. In: Proceedings of the 15th annual ACM international symposium on advances in geographic information systems, New York, NY, USA, pp 162–169

Alvares LO, Bogorny V, Macedo JF, Moelans B, Spaccapietra S (2007b) Dynamic modeling of trajectory patterns using data mining and reverse engineering. In: Proceedings of the 26th international conference on conceptual modeling, pp 149–154

Amorim RC, Mirkin B (2012) Minkowski metric, feature weighting and anomalous cluster initializing in K-means clustering. Pattern Recognit 45(3):1061–1075CrossRef

Ankerst M, Breunig MM, Kriegel HP, Sander J (1999) OPTICS: ordering points to identify the clustering structure. In: The 1999 ACM SIGMOD international conference on management of data, pp 49–60

Apeltauer J, Babinec A, Herman D, Apeltauer T (2015) Automatic vehicle trajectory extraction for traffic analysis from aerial video data. Int Arch Photogramm Remote Sens Spat Inf Sci 43(W2):9–15CrossRef

Bashir FI, Khokhar AA, Schonfeld D (2003) Segmented trajectory based indexing and retrieval of video data. In: Proceedings of the 2003 international conference on image processing, vol 2, pp 623–626

Beckmann N, Kriegel HP, Schneider R, Seeger B (1990) The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings Of the SIGMOD’90, ACM, New York, pp 322–331

Birant D, Kut A (2007) St-dbscan: an algorithm for clustering spatial and temporal data. Data Knowl Eng 60(1):208–221CrossRef

Boukhers Z, Shirahama K, Li F, Grzegorzek M (2015) Object detection and depth estimation for 3D trajectory extraction. In: Proceedings of the 13th international workshop on content-based multimedia indexing, pp 1–6

Buchin K, Buchin M, Gudmundsson J (2010) Constrained free space diagrams: a tool for trajectory analysis. Int J Geogr Inf Sci 24(7):1101–1125CrossRef

Buchin M, Drieme A, Kreveld MV, Sacrist’an V (2011) Segmenting trajectories: a framework and algorithms using spatiotemporal criteria. J Spat Inf Sci 3:33–63

Chen JY, Huo QY, Chen P, Xu XZ (2012) Sketch-based uncertain trajectories clustering. In: Proceedings of the 9th international conference on fuzzy systems and knowledge discovery, pp 747–751

Chen JD, Lai CF, Meng XF, Xu JL, Hu HB (2007) Clustering moving objects in spatial networks. In: Proceedings of the 12th international conference on database systems for advanced applications, 2007, pp 611–623

Chen JY, Wang RD, Liu LX, Song JT (2011) Clustering of trajectories based on Hausdorff distance. In: Proceedings of the 2011 international conference on electronics, communications and control, pp 1940–1944

Chen JD, Meng XF, Lai CF (2007) Clustering objects in a road network. J Softw 18:332–344CrossRef

Chen L, Özsu M, Oria V (2005) Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD international conference on management of data, ACM, New York, NY, USA, pp 491–502

Comer D (1979) The ubiquitous B-tree. Comput Surv 11(2):123–137MathSciNetCrossRefMATH

Eiter T, Mannila H (1994) Computing discrete Fréchet distance. Technical report CD-TR 94/64, Technische Universitat Wien

Ester M, Kriegel HP, Sander J, Xu X (1996) Density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd international conference on knowledge discovery and data mining, pp 226–231

Fileto R, Raffaetà A, Roncato A, Sacenti JAP, May C, Klein D (2014) A semantic model for movement data warehouses. In: Proceedings of the 17th international workshop on data warehousing and OLAP, 2014, pp 47–56

Fisher DH (1987) Knowledge acquisition via incremental conceptual clustering. Mach Learn 2(2):139–172

Fraley C, Raftery AE (2002) Model-based clustering, discriminant analysis, and density estimation. J Am Stat Assoc 97(458):611–631MathSciNetCrossRefMATH

Gudmundsson J, Kreveld M, Speckmann B (2004) Efficient detection of motion patterns in spatio-temporal data sets. In: Proceedings of the 12th annual ACM international workshop on Geographic information systems, pp 250–257

Guha S, Rastogi R, Shim K (2001) CURE: an efficient clustering algorithm for large databases. Inf Syst 26(1):35–58CrossRefMATH

Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD international conference on management of data, pp 47–57

Halkidi M, Batistakis Y, Vazirgiannis M (2001) On clustering validation techniques. J Intell Inf Syst 17(2–3):107–145CrossRefMATH

Han JW, Kamber M, Pei J (2011) Data mining: concepts and techniques, 3rd edn. Morgan Kaufmann Publishers, San FranciscoMATH

Han B, Liu L, Omiecinski E (2012) NEAT: road network aware trajectory clustering. In: Proceedings of the 32nd IEEE international conference on distributed computing systems, pp 142–151

Hung CC, Peng WC, Lee WC (2015) Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. VLDB J 24(2):169–192CrossRef

Igiesias F, Kastner W (2013) Analysis of similarity measures in time series clustering for the discovery of building energy patterns. Energies 6:579–597CrossRef

Jeung HY, Yiu ML, Zhou XF, Jensen CS, Shen HT (2008) Discovery of convoys in trajectory databases. In: Proceedings of the 34th international conference on very large data bases, pp 1068–1080

Jeung HY, Yiu ML, Zhou XF, Jensen CS, Shen HT (2008) Discovery of convoys in trajectory databases. J Proc VLDB Endow 1(1):1068–1080CrossRef

Khoshaein V (2014) Trajectory clustering using a variation of Fréchet distance. Doctoral dissertation, University of Ottawa, Ottawa, Canada

Kisilevich S, Mansmann F, Nanni M, Rinzivillo S (2010) Spatio-temporal clustering: a survey. Data mining and knowledge discovery handbook, 2nd edn. Springer, Heidelberg, pp 1–22

Lee JG, Han JW, Whang KY (2007) Trajectory clustering: a partition-and-group framework. In: Proceedings of the 2007 ACM SIGMOD international conference on management of data, Beijing, China, pp 593–604

Lee JJ, Kim GJ, Kim MH (2012) Trajectory extraction for abnormal behavior detection in public area. In: Proceedings of the 9th international conference & expo on emerging technologies for a smarter world, pp 1–5

Li XL, Han JW, Lee JG, Gonzalez H (2007) Traffic density-based discovery of hot routes in road networks. In: Proceedings of the 10th international conference on advances in spatial and temporal databases, pp 441–459

Liao TW (2005) Clustering of time series data—a survey. Pattern Recognit 38:1857–1874CrossRefMATH

Lin B, Su J (2008) OneWay distance, for shape based similarity search of moving object trajectories. GeoInformatica 12(2):117–142CrossRef

Lu GQ, Kong LF, Wang YP, Tian DX (2014) Vehicle trajectory extraction by simple two-dimensional model matching at low camera angles in intersection. IET Intell Transp Syst 8(7):631–638CrossRef

Manolopoulos Y, Nanopoulos A, Theodoridis Y (2006) R-trees: theory and applications. Springer, New York. ISBN 978-1-85233-977-7

Masciari E (2009) A framework for trajectory clustering. Lecture notes in computer science, vol 5659, pp 102–111

Michael S, Alex W (2011) Fast and accurate k-means for large datasets, advances in neural information processing systems 24. In: 25th annual conference on neural information processing systems 2011, pp 1–9

Michail V, Marios H, Dimitrios G (2006) Indexing multidimensional time-series. Int J Very Large Data Bases 15(1):1–20CrossRef

Mitsch S, Muller A, Retschitzegger W, Salfinger A, Schwinger W (2013) A survey on clustering techniques for situation awareness. In: Proceedings of the 15th Asia-Pacific web conference, pp 815–826

Nagesh H, Goil S, Chooudhary A (2001) Adaptive grids for clustering massive data sets. In: Proceedings of the 1st SIAM international conference on data mining, pp 1–17

Nanni M, Pedreschi D (2006) Time-focused clustering of trajectories of moving objects. J Intell Inf Syst 27(3):267–289CrossRef

Nock R, Nielsen F (2006) On weighting clustering. IEEE Trans Pattern Anal Mach Intell 28(8):1–13CrossRef

Palma AT, Bogorny V, Kuijpers B, Alvares LO (2008) A clustering-based approach for discovering interesting places in trajectories. In: Proceedings of the 2008 ACM symposium on applied computing, pp 863–868

Panagiotakis C, Pelekis N, Kopanakis I, Ramasso E, Theodoridis Y (2012) Segmentation and sampling of moving object trajectories based on representativeness. IEEE Trans Knowl Data Eng 24(7):1328–1343CrossRef

Parent C, Spaccapietra S, Renso C, Andrienko G, Andrienko N, Bogorny V, Damiani ML, Divanis AG, Macedo J, Pelekis N, Theodoridis Y, Yan ZX (2013) Semantic trajectories modeling and analysis. J ACM Comput Surv 45(4):1–37

Park HS, Jun CH (2009) A simple and fast algorithm for K-medoids clustering. Expert Syst Appl 36(2):3336–3341CrossRef

Pelekis N, Kopanakis I, Kotsifakos EE, Frentzos E, Theodoridis Y (2011) Clustering uncertain trajectories. Knowl Inf Syst 28(1):117–147CrossRef

Plaue M, Chen MJ, Bärwolff G, Schwandt H (2011) Trajectory extraction and density analysis of intersecting pedestrian flows from video recordings. Lecture notes in computer science, vol 6952, pp 285–296

Qian WN, Zhou AY (2002) Analyzing popular clustering algorithms from different viewpoints. J Softw 13(8):1382–1394

Rick C (2002) Efficient computation of all longest common subsequences. Lecture notes in computer science, vol 1851, pp 407–418

Roh GP, Hwang SW (2010) NNCluster: an efficient clustering algorithm for road network trajectories. In: Proceedings of the 15th international conference on database systems for advanced applications, vol 2, pp 47–61

Sankoff D, Kruskal J (1983) Time warps, string edits, and macromolecules: the theory and practice of sequence comparison. Addison-Wesley, MAMATH

Shi J, Tomasi C (1994) Good features to track. In: Proceedings of of the IEEE computer society conference on computer vision and pattern recognition, pp 593–600

Tao YF, Papadias D (2001) Efficient historical R-trees. In: Proceedings of the 13th international conference on scientific and statistical database management, pp 223–232

Tao YF, Papadias D, Sun JM (2003) The TPR*-tree: an optimized spatio-temporal access method for predictive queries. In: Proceedings of the 29th international conference on very large data bases, vol 29, pp 790–801

Tsumoto S, Hirano S (2009) Behavior grouping based on trajectory mining. In: Proceedings of the 2nd international workshop on social computing, behavioral modeling and prediction, Phoenix, AZ, USA, pp 219–226

Vlachos M, Kollios G, Gunopulos D (2002) Discovering similar multidimensional trajectories. In: Proceedings of the 18th international conference on data engineering, San Jose, CA, pp 673–684

Wang XF, Li G, Jiang G, Shi ZZ (2013) Semantic trajectory-based event detection and event pattern mining. Knowl Inf Syst 37(2):305–329CrossRef

Wang S, Wu L, Zhou F, Zheng C, Wang H (2015) Group pattern mining algorithm of moving objects’ uncertain trajectories. Int J Comput Commun Control 10(3):428–440CrossRef

Wang W, Yang J, Muntz RR (1997) STING: a statistical information grid approach to spatial data mining. In: Proceedings of the 23rd international conference on very large databases, pp 186–195

Wei LX, He XH, Teng QZ, Gao ML (2013) Trajectory classification based on Hausdorff distance and longest common subsequence. J Electron Inf Technol 35(4):784–790CrossRef

Wikipedia (2015) DBSCAN, https://en.wikipedia.org/wiki/DBSCAN 2015-11-25

Won JI, Kim SW, Baek JH, Lee JH (2009) Trajectory clustering in road network environment. In: Proceedings of the 2009 IEEE symposium on computational intelligence and data mining, pp 299–305

Yan ZX, Chakraborty D, Parent C, Spaccapietra S, Abere K (2012) Semantic trajectories: mobility data computation and annotation. ACM Trans Intell Syst Technol 9(4):1–34

Yan ZX (2011) Semantic trajectories: computing and understanding mobility data. Doctoral dissertation, Swiss Federal Institute of Technology, Lausanne

Yanagisawa Y, Akahani J, Satoch T (2003) Shape-based similarity query for trajectory of mobile objects. In: Proceedings of the 4th international conference on MDM, pp 63–77

Yanagisawa Y, Satph T (2006) Clustering multidimensional trajectories based on shape and velocity. In: Proceedings of the 22nd international conference on data engineering workshops, pp 12–21

Yasodha M, Ponmuthuramalingam DRP (2012) A survey on temporal data clustering. Int J Adv Res Comput Commun Eng 1(9):772–786

Ying JJC, Lee WC, Weng TC, Tseng VS (2011) Semantic trajectory mining for location prediction. In: Proceedings of the 19th ACM SIGSPATIAL GIS, November 1–4, pp 34–43

Yuan G, Xia SX, Zhang YM (2013) Interesting activities discovery for moving objects based on collaborative filtering. Math Probl Eng 2013:1–9

Yuan G, Xia SX, Zhang L, Zhou Y, Ji C (2012) An efficient trajectory-clustering algorithm based on an index tree. Trans Inst Meas Control 34(7):850–861CrossRef

Zhang Z, Huang K, Tan TN (2006) Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes. In: Proceedings of the 18th international conference on pattern recognition, vol 3, pp 1135–1138

Zhang T, Ramakrishnan R, Livny M (1996) BIRCH: an efficient data clustering method for very large databases. In: Proceedings of the 1996 ACM SIGMOD international conference on management of data, pp 103–114

Zheng Y (2015) Trajectory data mining: an overview. ACM Trans Intell Syst Technol 6(3):1–41

Zheng Y, Li Q, Chen Y, Xie X. (2011) Understanding mobility based on GPS data. In: Proceedings of the 13th international conference on ubiquitous computing, ACM, pp 312–321

Zhong S, Ghosh J (2003) A unified framework for model-based clustering. J Mach Learn Res 4:1001–1037MathSciNetMATH

Zhou FC, He XY, Wang S, Xu J, Wang MW, Wu LN (2014) A clustering-based privacy-preserving method for uncertain trajectory data. In: Proceedings of the IEEE 13th international conference on trust, security and privacy in computing and communications, pp 1–8

Zhou SG, Zhou AY, Cao J, Hu YF (2000) A fast density-based clustering algorithm. J Comput Res Dev 37(11):1287–1292

Titel: A review of moving object trajectory clustering algorithms
verfasst von: Guan Yuan
Penghui Sun
Jie Zhao
Daxing Li
Canwei Wang
Publikationsdatum: 25.03.2016
Verlag: Springer Netherlands
Erschienen in: Artificial Intelligence Review / Ausgabe 1/2017
Print ISSN: 0269-2821
Elektronische ISSN: 1573-7462
DOI: https://doi.org/10.1007/s10462-016-9477-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"