Abstract
We present a framework for the partitioning of a spatial trajectory in a sequence of segments based on spatial density and temporal criteria. The result is a set of temporally separated clusters interleaved by sub-sequences of unclustered points. A major novelty is the proposal of an outlier or noise model based on the distinction between intra-cluster (local noise) and inter-cluster noise (transition): the local noise models the temporary absence from a residence while the transition the definitive departure towards a next residence. We analyze in detail the properties of the model and present a comprehensive solution for the extraction of temporally ordered clusters. The effectiveness of the solution is evaluated first qualitatively and next quantitatively by contrasting the segmentation with ground truth. The ground truth consists of a set of trajectories of labeled points simulating animal movement. Moreover, we show that the approach can streamline the discovery of additional derived patterns, by presenting a novel technique for the analysis of periodic movement. From a methodological perspective, a valuable aspect of this research is that it combines the theoretical investigation with the application and external validation of the segmentation framework. This paves the way to an effective deployment of the solution in broad and challenging fields such as e-science.
Similar content being viewed by others
Notes
The property is not satisfied by border points. Yet, that is marginal for our work.
The implementation of the algorithm has been kindly provided by M. Elfeky, co-author of WARP (Elfeky et al. 2005). Another implementation is available on: //github.com/Serafim-End/periodicity-research.
http://www.movebank.org. Study: Raptor Tracking: NYSDEC.
References
Alewijnse S, Buchin K, Buchin M, Kölzsch A, Kruckenberg H, Westenberg M (2014) A framework for trajectory segmentation by stable criteria. In: Proceedings of ACM SIGSPATIAL
Amigó E, Gonzalo J, Artiles J, Verdejo F (2009) A comparison of extrinsic clustering evaluation metrics based on formal constraints. Inf Retr 12(4):461–486
Ankerst M, Breunig MM, Kriegel HP, Sander J (1999) Optics: ordering points to identify the clustering structure. In: Proceedings of ACM SIGMOD
Aronov B, Driemel A, van Kreveld M, Löffler M, Staals F (2015) Segmentation of trajectories on nonmonotone criteria. ACM Trans Algorithms 12(2):26:1–26:28
Basu S, Banerjee A, Mooney R (2004) Active semi-supervision for pairwise constrained clustering. In: Proceedings of SIAM international conference on data mining
Berger-Tal O, Bar-David S (2015) Recursive movement patterns: review and synthesis across species. ESA Ecosphere 6(9):1–12
Birant D, Kut A (2007) St-dbscan: an algorithm for clustering spatial–temporal data. Data Knowl Eng 60(1):208–221
Buchin M, Driemel A, van Kreveld MJ, Sacristán V (2011) Segmenting trajectories: a framework and algorithms using spatiotemporal criteria. J Spat Inf Sci 3(1):33–63
Buchin M, Kruckenberg H, Kölzsch A (2013) Advances in spatial data handling, Springer, chap segmenting trajectories by movement states, pp 15–25
Cao F, Ester M, Qian W, Zhou A (2006) Density-based clustering over an evolving data stream with noise. In: Proceedings of SIAM international conference on data mining
Cao H, Mamoulis N, Cheung DW (2007) Discovery of periodic patterns in spatiotemporal sequences. IEEE Trans Knowl Data Eng 19(4):453–467
Cerf M, Harel J, Einhaeuser W, Koch C (2008) Predicting human gaze using low-level saliency combined with face detection. In: Advances in neural information processing systems, Curran Associates, pp 241–248
Cudré-Mauroux P, Wu E, Madden S (2010) Trajstore: an adaptive storage system for very large trajectory data sets. In: Proceedings of IEEE international conference on data engineering
Damiani ML, Hachem F (2017) Segmentation techniques for the summarization of individual mobility data. Wiley Interdiscip Rev Data Min Knowl Discov 7(6):e1214
Damiani ML, Issa H, Cagnacci F (2014) Extracting stay regions with uncertain boundaries from GPS trajectories: a case study in animal ecology. In: Proceedings of ACM SIGSPATIAL
Damiani ML, Issa H, Fotino G, Hachem F, Ranc N, Cagnacci F (2015) MigrO: a plug-in for the analysis of individual mobility behavior based on the stay region model. In: Proceedings of ACM SIGSPATIAL
Damiani ML, Issa H, Fotino G, Heurich M, Cagnacci F (2016) Introducing ’presence’ and ’stationarity index’ to study partial migration patterns: an application of a spatio-temporal clustering technique. Int J Geogr Inf Sci 30(5):907–928
Dodge S, Weibel R, Lautenschütz AK (2008) Towards a taxonomy of movement patterns. Inf Vis 7(3–4):240–252
Edelhoff H, Signer J, Balkenhol N (2016) Path segmentation for beginners: an overview of current methods for detecting changes in animal movement patterns. Mov Ecol 4(1):21
Elfeky M, Aref W, Elmagarmid A (2005) Warp: time warping for periodicity detection. In: Proceedings of IEEE international conference on data mining
Esling P, Agon C (2012) Time-series data mining. ACM Comput Surv 45(1):12:1–12:34
Ester M, Kriegel HP, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of international conference on knowledge discovery and data mining
Ester M, Kriegel HP, Sander J, Wimmer M, Xu X (1998) Incremental clustering for mining in a data warehousing environment. In: Proceedings of VLDB
Farber I, Guennemann S, Kriegel HP, Kroeger P, Mueller E, Schubert E, Seidl T, Zimek A (2010) On using class-labels in evaluation of clusterings. In: Proceedings of international workshop on discovering, summarizing and using multiple clusterings
Gan J, Tao Y (2015) DBSCAN revisited: mis-claim, un-fixability, and approximation. In: Proceedings of ACM SIGMOD international conference on management of data
Giannotti F, Pedreschi D (2008) Mobility, data mining and privacy: geographic knowledge discovery. Springer, Berlin
Gibbons JD, Chakraborti S (2011) Nonparametric statistical inference. In: International encyclopedia of statistical science. Springer, pp 977–979
Groeve JD, de Weghe NV, Ranc N, Neutens T, Ometto L, Rota-Stabelli O, Cagnacci F (2016) Extracting spatio-temporal patterns in animal trajectories: an ecological application of sequence analysis methods. Methods Ecol Evol 7(3):369–379
Gudmundsson J, Laube P, Wolle T (2008) Movement patterns in spatio-temporal data. In: Encyclopedia of GIS. Springer, US, pp 726–732
Gurarie E, Andrews RD, Laidre KL (2009) A novel method for identifying behavioural changes in animal movement data. Ecol Lett 12:395–408
Güting R, Valdés F, Damiani ML (2015) Symbolic trajectories. Trans Spat Algorithms Syst 1(2):7:1–7:51
Han J, Kamber M, Pei J (2011) Data mining: concepts and techniques. Morgan Kaufmann Publishers Inc., Burlington
Kang J, Welbourne W, Stewart B, Borriello G (2004) Extracting places from traces of locations. In: Proceedings of ACM international workshop on wireless mobile applications and services on WLAN hotspots
Keogh E, Chu S, Hart D, Pazzani M (2001) An online algorithm for segmenting time series. In: Proceedings of IEEE international conference on data mining
Li Z, Han J (2014) Mining periodicity from dynamic and incomplete spatiotemporal data. In: Data mining and knowledge discovery for big data. Springer, pp 41–81
Li Z, Han J, Ji M, Tang LA, Yu Y, Ding B, Lee JG, Kays R (2011) Movemine: mining moving object data for discovery of animal movement patterns. ACM Intell Syst Technol 2(4):1–32
Michelot T, Langrock R, Bestley S, Jonsen I, Photopoulou T, Patterson T (2017) Estimation and simulation of foraging trips in land-based marine predators. Ecology 98(7):1932–1944
Moorter BV, Visscher D, Benhamou S, Borger L, B M, Gaillard JM (2009) Memory keeps you at home: a mechanistic model for home range emergence. Oikos 118(5):641–652
Morales J, Haydon D, Frair J, Holsinger KE, Fryxell J (2004) Extracting more out of relocation data: building movement models as mixtures of random walks. Ecology 85(9):2436–2445
Palma AT, Bogorny V, Kuijpers B, Alvares LO (2008) A clustering-based approach for discovering interesting places in trajectories. In: Proceedings of ACM symposium on applied computing
Parent C, Spaccapietra S, Renso C, Andrienko G, Andrienko N, Bogorny V, Damiani ML, Gkoulalas-Divanis A, Macedo J, Pelekis N, Theodoridis Y, Yan Z (2013) Semantic trajectories modeling and analysis. Comput Surv 45(4):1–32
Patlak CS (1953) Random walk with persistence and external bias. Bull Math Biophys 15(3):311–338
Rasetic S, Sander J, Elding J, Nascimento MA (2005) A trajectory splitting model for efficient spatio-temporal indexing. In: Proceedings of ACM international conference on very large data bases
Worton B (1989) Kernel methods for estimating the utilization distribution in home-range studies. Ecology 70(1):164–168
Zheng Y (2015) Trajectory data mining: an overview. ACM Trans Intell Syst Technol 6(3):1–41
Zheng Y, Zhou X (2011) Computing with spatial trajectories. Springer, Berlin
Zheng Y, Zhang L, Ma Z, Xie X, Ma W (2011) Recommending friends and locations based on individual location history. ACM Trans Web 5(1):1–44
Zheng Y, Capra L, Wolfson O, Yang H (2014) Urban computing: concepts, methodologies, and applications. ACM Trans Intell Syst Technol 5(3):1–55
Acknowledgements
The authors thank Walid Aref, Purdue University, for the discussion on the use of the WARP technique, and Roland Keys, NC Museum of Natural Sciences, for kindly providing the real data used in the experiments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Responsible editor: Jian Pei.
Appendix: the animal dataset
Appendix: the animal dataset
Rights and permissions
About this article
Cite this article
Damiani, M.L., Hachem, F., Issa, H. et al. Cluster-based trajectory segmentation with local noise. Data Min Knowl Disc 32, 1017–1055 (2018). https://doi.org/10.1007/s10618-018-0561-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10618-018-0561-2