String-Based Feature Representation for Trajectory Clustering

String-Based Feature Representation for Trajectory Clustering

B. A. Sabarish (Department of Computer Science and Engineering, Amrita School of Engineering, Coimbatore, Amrita Vishwa Vidyapeetham, India), Karthi R. (Department of Computer Science and Engineering, Amrita School of Engineering, Coimbatore, Amrita Vishwa Vidyapeetham, India) and Gireesh Kumar T (TIFAC CORE in Cyber Security, Amrita School of Engineering, Coimbatore, Amrita Vishwa Vidyapeetham, India)
DOI: 10.4018/IJERTCS.2019040101

Abstract

A trajectory is the spatial trail of a moving object as a function of time. All moving objects such as humans, robots, cloud, taxis, animals, mobile phones generate trajectories. Trajectory clustering is grouping of trajectories that have similar moving patterns, and the formed clusters depend on feature representation, similarity metrics, and clustering algorithm used. In this article, trajectory features are generated after mapping trajectories onto grids, as this smoothens the variations that occur in spatial coordinates. These variations occur due to differences in how GPS points at varying intervals are generated by the device, even when they follow the same path. The main motivation for the article is to devise an algorithm for trajectory clustering that is independent of the variations from GPS devices. A string-based model is used, where trajectories are represented as strings and string-based distance metrics are used to measure the similarity between trajectories. A hierarchical method is applied for clustering and the results are validated using three metrics. An experimental study is conducted and the results show the effectiveness of string-based representation and distance metrics for trajectory clustering.
Article Preview
Top

Literature Review

Trajectory data is regarded as time sequenced spatial data and a number of trajectory clustering methods have been proposed and a review of these methods is discussed by Zheng (2015) and Sabarish, Karthi and Gireeshkumar (2015). Trajectory clustering approaches analyse trajectories as a whole as a single unit or as multiple segments. Gaffney and Smyth (1999) proposed a model-based clustering approach where trajectories are considered to be generated from mixture models and EM algorithm is used to assign data to clusters. Trajectories are considered as a whole and assigned to clusters based on cluster parameters. Lee, Han, Li and Gonzalez (2008) proposed traclus algorithm that generates many line segments for a trajectory using characteristic points in partition phase and clusters line segments using dbscan algorithm in grouping phase. Trajectories are considered as multiple sub trajectories and helps in discovering patterns in these sub trajectories.

Tripathi, Debnath and Elmasri (2016) proposed a framework where directional orientation of the trajectories is used for clustering. The algorithm does smoothing, filtration, segmentation and clustering of segments to obtain overall directional patterns in the data set. Mao, Zhong, Qi, Ping and Li (2017) proposed an adaptive dbscan trajectory clustering method where trajectory are segmented into sub trajectories using modified Minimum Description Length. The clustering space is divided into grids and trajectories are mapped into grids and an adaptive dbscan algorithm is proposed for clustering. A survey of trajectory clustering algorithms is discussed by Yuan, Sun, Zhao, Li and Wang (2017) where the trajectory algorithms are classified into categories as spatial based, time based, group and partition, uncertainty, sematic based, road network and optimization based methods for clustering.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 2 Issues (2018)
Volume 8: 2 Issues (2017)
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing