Skip to main content
Log in

Cluster-based trajectory segmentation with local noise

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

Notes

  1. The property is not satisfied by border points. Yet, that is marginal for our work.

  2. 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.

  3. http://www.qgis.org.

  4. https://www.r-project.org/.

  5. 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

    Article  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Dodge S, Weibel R, Lautenschütz AK (2008) Towards a taxonomy of movement patterns. Inf Vis 7(3–4):240–252

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Güting R, Valdés F, Damiani ML (2015) Symbolic trajectories. Trans Spat Algorithms Syst 1(2):7:1–7:51

    Google Scholar 

  • Han J, Kamber M, Pei J (2011) Data mining: concepts and techniques. Morgan Kaufmann Publishers Inc., Burlington

    MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Patlak CS (1953) Random walk with persistence and external bias. Bull Math Biophys 15(3):311–338

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Zheng Y, Zhou X (2011) Computing with spatial trajectories. Springer, Berlin

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • Zheng Y, Capra L, Wolfson O, Yang H (2014) Urban computing: concepts, methodologies, and applications. ACM Trans Intell Syst Technol 5(3):1–55

    Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Maria Luisa Damiani.

Additional information

Responsible editor: Jian Pei.

Appendix: the animal dataset

Appendix: the animal dataset

figure c

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10618-018-0561-2

Keywords

Navigation