Efficient k-Nearest Neighbour Classification for Trajectory Data by Using R-Tree

Abstract

Trajectory data mining is an emerging area of research, having a large variety of applications. This paper proposes an efficient nearest neighbour based trajectory data classification. The nearest neighbour classification is simplest method. The main issue of a Nearest Neighbour classifier is measuring the distance between two items, and this becomes more complicated for Trajectory Data. The closeness between objects is determined using a distance measure. Despite its simplicity, Nearest Neighbour also has some drawbacks: 1) it suffers from expensive computational cost in training when the training set contains millions of objects; 2) its classification time is linear to the size of the training set. The larger the training set, the longer it takes to search for the nearest neighbors. To improve the efficiency of algorithm an R-tree data structure is used. Extensive experiments were conducted using real datasets of moving vehicles in Milan (Italy) and London (UK). Our experimental investigation yields output as classified test trajectories, significant in terms of correctly classified success rate being 98.2%, the results are discussed with the summaries of confusion matrix. To measure the agreement between predicted and observed categorization of the dataset is carried out using Kappa statistics.