Trajectory clustering: a partition-and-group framework

ABSTRACT

Existing trajectory clustering algorithms group similar trajectories as a whole, thus discovering common trajectories. Our key observation is that clustering trajectories as a whole could miss common sub-trajectories. Discovering common sub-trajectories is very useful in many applications, especially if we have regions of special interest for analysis. In this paper, we propose a new partition-and-group framework for clustering trajectories, which partitions a trajectory into a set of line segments, and then, groups similar line segments together into a cluster. The primary advantage of this framework is to discover common sub-trajectories from a trajectory database. Based on this partition-and-group framework, we develop a trajectory clustering algorithm TRACLUS. Our algorithm consists of two phases: partitioning and grouping. For the first phase, we present a formal trajectory partitioning algorithm using the minimum description length(MDL) principle. For the second phase, we present a density-based line-segment clustering algorithm. Experimental results demonstrate that TRACLUS correctly discovers common sub-trajectories from real trajectory data.

REFERENCES

• 1: Elke Achtert , Christian Böhm , Hans-Peter Kriegel , Peer Kröger , Arthur Zimek, Deriving quantitative models for correlation clusters, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150408]
• 2: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014064]
• 4: Chen, J., Leung, M. K. H., and Gao, Y., "Noisy Logo Recognition Using Line Segment Hausdorff Distance," Pattern Recognition, 36(4): 943--955, 2003.
• 5: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 6: Ester, M., Kriegel, H. P., Sander, J., and Xu, X., "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise," In Proc. 2nd Int'l Conf. on Knowledge Discovery and Data Mining, Portland, Oregon, pp. 226--231, Aug. 1996.
• 7: Scott Gaffney , Padhraic Smyth, Trajectory clustering with mixtures of regression models, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.63-72, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312198]
• 8: Gaffney, S., Robertson, A., Smyth, P., Camargo, S., and Ghil, M., Probabilistic Clustering of Extra tropical Cyclones Using Regression Mixture Models, Technical Report UCI-ICS 06-02, University of California, Irvine, Jan. 2006.
• 9: Grünwald, P., Myung, I. J., and Pitt, M., Advances in Minimum Description Length: Theory and Applications, MIT Press, 2005.
• 10: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 11: Han, J. and Kamber, M., Data Mining: Concepts and Techniques, 2nd ed., Morgan Kaufmann, 2006.
• 12: Keogh, E. J., "Exact Indexing of Dynamic Time Warping," In Proc. 28th Int'l Conf. on Very Large Data Bases, Hong Kong, China, pp. 406--417, Aug. 2002.
• 13: Eamonn Keogh , Stefano Lonardi , Chotirat Ann Ratanamahatana, Towards parameter-free data mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014077]
• 14: Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P., "Optimization by Simulated Annealing," Science, 220(4598): 671--680, 1983.
• 15: Lee, T. C. M., "An Introduction to Coding Theory and the Two-Part Minimum Description Length Principle," International Statistical Review, 69(2):169--184, 2001.
• 16: Lee, J. G., Han, J., and Whang, K. Y., Trajectory Clustering: A Partition-and-Group Framework, Technical Report UIUCDCS-R-2007-2828, University of Illinois at Urbana-Champaign, Mar. 2007.
• 17: Lloyd, S., "Least Squares Quantization in PCM," IEEE Trans. on Information Theory, 28(2): 129--137, 1982.
• 18: Powell, M. D. and Aberson, S. D., "Accuracy of United States Tropical Cyclone Landfall Forecasts in the Atlantic Basin (1976-2000),"Bull. of the American Meteorological Society, 82(12): 2749--2767, 2001.
• 19: Volker Roth , Julian Laub , Motoaki Kawanabe , Joachim M. Buhmann, Optimal Cluster Preserving Embedding of Nonmetric Proximity Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1540-1551, December 2003 [doi>10.1109/TPAMI.2003.1251147]
• 20: Shannon, C. E., "A Mathematical Theory of Communication," The Bell System Technical Journal, 27: 379--423 and 623--656, 1948.
• 21: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 22: Wei Wang , Jiong Yang , Richard R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, Proceedings of the 23rd International Conference on Very Large Data Bases, p.186-195, August 25-29, 1997
• 23: Wisdom, M. J., Cimon, N. J., Johnson, B. K., Garton, E. O., and Thomas, J. W.,"Spatial Partitioning by Mule Deer and Elk in Relation to Traffic," Trans. of the North American Wildlife and Natural Resources Conf., Spokane, Washington, pp. 509--530, Mar. 2004.
• 24: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
MDL principle, density-based clustering, partition-and-group framework, trajectory clustering