Dynamic spatio-temporal pattern discovery: a novel grid and density-based clustering algorithm

Abstract

Clustering is a robust machine- learning technique for exploration of patterns based on similarity of elements over multidimensional data. Spatio-temporal clustering aims to identify target objects to mine spatial and temporal dimensions for patterns, regularity, and trends. It has been applied in humancentric applications, such as recommendation systems, urban development and planning, clustering of criminal activities, traffic planning, and epidemiology to identify the extent of disease spread. Although the existing research work in the field of clustering relies widely on partition and densitybased methods, no major work has been carried out to handle the spatiotemporal dimension and understand the dynamics of temporal variation and connectivity between clusters. To address this, our paper proposes an algorithm to mine clustering patterns in spatiotemporal dataset using an adaptive, dynamic hybrid technique based on grid and density clustering. We adopt spatio-temporal partitioning of the virtual grid for distribution of data and reducing distance computation and increasing efficiency. Grouping the higher density regions along with neighborhood cluster density attraction rate to merge the clusters. This method has been experimentally evaluated over the Indian earthquake dataset and found to be effective with clustering silhouette index up to 0.93.