Journal of Geo-information Science ›› 2015, Vol. 17 ›› Issue (10): 1152-1161.doi: 10.3724/SP.J.1047.2015.01152

• Orginal Article • Previous Articles     Next Articles

A Fast Method of FCD Trajectory Data Clustering Based on the Directed Density

LIAO Lvchao1,2(), JIANG Xinhua1,2,*(), ZOU Fumin2, LI Luming1, LAI Hongtu2   

  1. 1. School of Information Science and Engineering, Central-South University, Changsha 410075, China
    2. Fujian Key Laboratory for Automotive Electronics and Electric Drive , Fujian University of Technology, Fuzhou 350108, China
  • Received:2015-04-20 Revised:2015-05-18 Online:2015-10-10 Published:2015-10-10
  • Contact: JIANG Xinhua E-mail:achao@fjut.edu.cn;xhjiang@fjut.edu.cn
  • About author:

    *The author: CHEN Nan, E-mail:fjcn99@163.com

Abstract:

Floating car data (FCD), which is the trajectories of vehicles, are automatically collected by huge quantities of commercial vehicles which are equipped with GPS devices. Exploring and exploiting such data is essential to understand the dynamic aggregation patterns of trajectory data. However, the existing methods of spatial density clustering mainly focus on undirected data, and it is difficult to effectively find the characteristics of trajectory data. We contribute to the literatures on FCD trajectory data mining by presenting a novel method called directed density clustering method (D-OPTICS), which is formulated based on the spatial density clustering algorithm (OPTICS). In our method, the directed density is computed by a fan-shaped neighborhood region, and the density connectivity is restrained by its direction information. Then, the base clusters are generated using the curve analysis of reachable distance. Finally, the D-OPTICS cluster method is formed by the optimization method of spatial grid and cluster polymerization. This method can be naturally applied to FCD trajectory data mining, and it is also appropriate for handling other directed spatial data. It can be employed to discover the spatio-temporal distribution characteristic of traffic trajectory, and then be adopted to extract the structure information of complex road network. The experiments, with massive floating car data of Fuzhou city, show that the D-OPTICS can cluster directed spatial data effectively, and is useful to uncover the inherent distribution characteristic of the massive trajectory data. Based on its clustering result, the topology information of road network can be extracted. In this work, we extracted the topology graph for the complex road network of Fuzhou city. The experiment results also show that the algorithm can automatically determine the number of clusters, and it is found that the algorithm is not limited to globular cluster data and is capable to deal with clusters of arbitrary shapes. The key contribution of this method is that it takes the direction information into account and it can also be effective in reducing the problems caused by traditional clustering algorithms which may incorrectly merge or decompose thus naturally produce large clusters and noise data. Meanwhile, the result of performance experiments shows that, compared with DBSCAN and OPTICS, the proposed method is more suitable for large-scale data processing.

Key words: FCD trajectory data, spatial-temporal data mining, density clustering, directed density clustering, floating car data