Title: Dynamic k-means: a clustering technique for moving object trajectories

Authors: Omnia Ossama; Hoda M.O. Mokhtar; Mohamed E. El-Sharkawi

Addresses: Information Systems Department, Faculty of Computers and Information, Cairo University, 5 Dr Ahmed Zewail St., Orman, Giza 12613, Egypt. ' Information Systems Department, Faculty of Computers and Information, Cairo University, 5 Dr Ahmed Zewail St., Orman, Giza 12613, Egypt. ' Information Systems Department, Faculty of Computers and Information, Cairo University, 5 Dr Ahmed Zewail St., Orman, Giza 12613, Egypt

Abstract: k-means clustering algorithm is a famous clustering algorithm applied in many applications. However, traditional k-means algorithm assumes that the initial number of centroids is known in advance. This dependence on the number of clusters and the initial choice of the centroids affect both the performance and accuracy of the algorithm. To overcome this problem, in this paper, we propose a heuristic that dynamically calculates k based on the movement patterns in the trajectory dataset and optimally initialises the k centroids. We basically consider distinct similar moving patterns as an initialisation for the number of clusters (k). In addition, we design a scalable tool for mining moving object data through (an architecture composed of) a rich set of cluster refinement modules that operate on top of the moving object database enabling users to analyse trajectory data from different perspectives. We validate our approaches experimentally on both real and synthetic data and test the performance and accuracy of our techniques.

Keywords: moving object databases; MODs; mining object trajectories; clustering moving objects; similarity search; dynamic k-means; moving object trajectories; clustering algorithms; movement patterns; k centroids.

DOI: 10.1504/IJIIDS.2012.049111

International Journal of Intelligent Information and Database Systems, 2012 Vol.6 No.4, pp.307 - 327

Received: 11 Dec 2010
Accepted: 09 Oct 2011
Published online: 16 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article