Research On Trajectory Clustering Algorithm Of Moving Object On Road Network Space

In the recent years, with the development and popularity of locating technology, sensor technology and tracking devices, we can easily track the moving objects, and record their movement trajectories. The trajectory data of moving objects contains a wealth of useful information, using data mining technology for analysis and processing the trajectory information acquired can find relationships and rules hidden in the data and predict the future movement of moving objects and so on. The goal of this study is to analyze and mine trajectories of moving objects in road network space, clustering similar trajectories to obtain movement features and models of moving objects and providing foundation for path planning and intelligent navigation.Moving objects with continuous motions in the road network will constantly generate trajectories as time goes by, while the clustering request for trajectories is likely to occur at any time and once a request comes, the trajectory situation in road network is bound to have changed. Traditional clustering approaches are deal with static data sets, and when they are applied to dynamic trajectory clustering, it will reprocess all trajectories every time, including the track segment has been processed previously, so it will waste a lot of unnecessary overhead. Our study is base on the problem mentioned above, analyzing and summarizing the existing methods and proposing the following method to cluster trajectory data of moving objects:Firstly, we propose a representation method of trajectory of moving objects based on road network space. We represent a trajectory as the manner of discrete points, it records the real location information of moving object at a moment in the road network and the speed of each point when the object through as while, and the representation can reflect the real situation of position changing of moving objects in the road network;Secondly, we calculate trajectory distance considering the spatio-temporal characteristics of trajectories. In the basis of analyzing and summarizing the existing trajectory distance functions and trajectory similarity measurement, this paper computes the spatial distance of trajectories with the average Hausdorff distance, we compute the network distance of two points on two trajectories instead of using their Euclidean distance, and then refine the trajectories by the temporal distance, obtaining the spatio-temporal distance of trajectories as the basis for clustering accordingly.Thirdly, we propose a trajectory incremental clustering algorithm INC_CLUS to cluster trajectories. Based on the density-based clustering algorithm, it processes initial clustering for current trajectories at the beginning in the first and gets a set of initial clusters, and then using the incremental clustering method for the new coming and mutative trajectories, thus it will update the initial clusters to get final clustering result. Owing to consider the temporal information of trajectories at the same time, it can distinguish similar trajectories between different time intervals;Finally, we take a period of road network area of Harbin urban as experiment region to analyze and storage, and simulate a set of trajectory data of moving objects traveling in the real road network space. According to cluster these trajectory data using the trajectory incremental clustering algorithm proposed in this paper, and compare the result with the using of initial DBSCAN algorithm, we get a performance evaluation from the aspects of clustering result and processing efficiency and have verified the correctness and validity of the proposed INC_CLUS algorithm.