GRASP-UTS: an algorithm for unsupervised trajectory segmentation
- 14 July 2014
- journal article
- research article
- Published by Taylor & Francis in International Journal of Geographical Information Science
- Vol. 29 (1) , 46-68
Abstract
An important problem in the knowledge discovery of trajectories is segmentation in subparts (subtrajectories). Existing algorithms for trajectory segmentation generally use explicit criteria to create segments. In this article, we propose segmenting trajectories using a novel, unsupervised approach, in which no explicit criteria are predetermined. To achieve this, we apply the Minimum Description Length (MDL) principle, which can measure homogeneity in the trajectory data by computing the similarities between landmarks (i.e. representative points of the trajectory) and the points in their neighborhood. Based on the homogeneity measurements, we propose an algorithm named Greedy Randomized Adaptive Search Procedure for Unsupervised Trajectory Segmentation (GRASP-UTS), which is a meta-heuristic that builds segments by modifying the number and positions of landmarks. We perform experiments with GRASP-UTS in two real-world datasets, using segment purity and coverage metrics to evaluate its efficiency. Experimental results demonstrate that GRASP-UTS correctly segmented sample trajectories without predetermined criteria, by computing similarities between landmarks and other trajectory points.Keywords
Funding Information
- CNPq (SWE/CSF 238212/2012-2)
- CAPES-DFAIT (008/11)
- NSERC
This publication has 18 references indexed in Scilit:
- Transportation mode-based segmentation and classification of movement trajectoriesInternational Journal of Geographical Information Science, 2013
- Trajectories of Moving Objects on a Network: Detection of Similarities, Visualization of Relations, and Classification of TrajectoriesTransactions in GIS, 2012
- Discovering Spatial Patterns in Origin‐Destination Mobility DataTransactions in GIS, 2012
- Discovering Chasing Behavior in Moving Object TrajectoriesTransactions in GIS, 2011
- Space–time density of trajectories: exploring spatio-temporal patterns in movement dataInternational Journal of Geographical Information Science, 2010
- A conceptual view on trajectoriesData & Knowledge Engineering, 2008
- Time-focused clustering of trajectories of moving objectsJournal of Intelligent Information Systems, 2006
- Discovering relative motion patterns in groups of moving point objectsInternational Journal of Geographical Information Science, 2005
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- Modeling by shortest data descriptionAutomatica, 1978