A clustering-based approach for discovering interesting places in trajectories

ABSTRACT

Because of the large amount of trajectory data produced by mobile devices, there is an increasing need for mechanisms to extract knowledge from this data. Most existing works have focused on the geometric properties of trajectories, but recently emerged the concept of semantic trajectories, in which the background geographic information is integrated to trajectory sample points. In this new concept, trajectories are observed as a set of stops and moves, where stops are the most important parts of the trajectory. Stops and moves have been computed by testing the intersections of trajectories with a set of geographic objects given by the user. In this paper we present an alternative solution with the capability of finding interesting places that are not expected by the user. The proposed solution is a spatio-temporal clustering method, based on speed, to work with single trajectories. We compare the two different approaches with experiments on real data and show that the computation of stops using the concept of speed can be interesting for several applications.

REFERENCES

• 1: L. O. Alvares, V. Bogorny, J. F. de Macedo, B. Moelans, and S. Spaccapietra. Dynamic modeling of trajectory patterns using data mining and reverse engineering. In Twenty-Sixth International Conference on Conceptual Modeling - ER2007 - Tutorials, Posters, Panels and Industrial Contributions, volume 83, pages 149--154. CRPIT, November 2007.
• 2: Luis Otavio Alvares , Vania Bogorny , Bart Kuijpers , Jose Antonio Fernandes de Macedo , Bart Moelans , Alejandro Vaisman, A model for enriching trajectories with semantic geographical information, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington [doi>10.1145/1341012.1341041]
• 3: Daniel Ashbrook , Thad Starner, Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, v.7 n.5, p.275-286, October 2003 [doi>10.1007/s00779-003-0240-0]
• 4: Derya Birant , Alp Kut, ST-DBSCAN: An algorithm for clustering spatial-temporal data, Data & Knowledge Engineering, v.60 n.1, p.208-221, January, 2007 [doi>10.1016/j.datak.2006.01.013]
• 5: V. Bogorny, A. T. Palma, P. Engel, and L. O. Alvares. Weka-gdpm: Integrating classical data mining toolkit to geographic information systems. In WAAMD, pages 9--16. SBC, 2006.
• 6: Sotiris Brakatsoulas , Dieter Pfoser , Nectaria Tryfona, Modeling, Storing, and Mining Moving Object Databases, Proceedings of the International Database Engineering and Applications Symposium, p.68-77, July 07-09, 2004 [doi>10.1109/IDEAS.2004.45]
• 7: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In E. Simoudis, J. Han, and U. M. Fayyad, editors, Second International Conference on Knowledge Discovery and Data Mining, pages 226--231. AAAI Press, 1996.
• 8: E. Frank, M. A. Hall, G. Holmes, R. Kirkby, B. Pfahringer, I. H. Witten, and L. Trigg. Weka - a machine learning workbench for data mining. In O. Maimon and L. Rokach, editors, The Data Mining and Knowledge Discovery Handbook, pages 1305--1314. Springer, 2005.
• 9: Fosca Giannotti , Mirco Nanni , Fabio Pinelli , Dino Pedreschi, Trajectory pattern mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281230]
• 10: Hartmut Güting , Teixeira de Almeida , Zhiming Ding, Modeling and querying moving objects in networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.165-190, June 2006 [doi>10.1007/s00778-005-0152-x]
• 11: Jae-Gil Lee , Jiawei Han , Kyu-Young Whang, Trajectory clustering: a partition-and-group framework, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247546]
• 12: X. Li, C. Claramunt, C. Ray, and H. Lin. A semantic-based approach to the representation of network-constrained trajectory data. In Progress in Spatial Data Handling - 12th International Symposium on Spatial Data Handling, pages 451--464, Berlin, 2006. Springer.
• 13: Mirco Nanni , Dino Pedreschi, Time-focused clustering of trajectories of moving objects, Journal of Intelligent Information Systems, v.27 n.3, p.267-289, November 2006 [doi>10.1007/s10844-006-9953-7]
• 14: OGC. Topic 5, opengis abstract specification - features (version 4) (1999). Available at: http://www.OpenGIS.org/techno/specs.htm. Accessed in August (2005), 1999.
• 15: Jörg Sander , Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications, Data Mining and Knowledge Discovery, v.2 n.2, p.169-194, June 1998 [doi>10.1023/A:1009745219419]
• 16: W. Society. Frequency 1550. Available at: http://www.waag.org/project/frequentie. Accessed in September (2007), 2005.
• 17: S. Spaccapietra, C. Parent, M.-L. Damiani, J. A. F. de Macedo, F. Porto, and C. Vangenot. A conceptual view on trajectories. Technical report, Ecole Polytechnique Federal de Lausanne, April 2007.
• 18: Michalis Vazirgiannis , Ouri Wolfson, A Spatiotemporal Model and Language for Moving Objects on Road Networks, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.20-35, July 12-15, 2001
• 19: C. Zhou, N. Bhatnagar, S. Shekhar, and L. Terveen. Mining personally important places from gps tracks: a hybrid approach. In Proceedings of the 23rd International Conference on Data Engineering Workshops, ICDE 2007, Istambul, Turkey, pages 517--526. IEEE Computer Society, April 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
data mining, moving objects, semantic trajectory annotation, spatio-temporal clustering, trajectories