Research On Algorithm Of Road-network Aware Spatial-temporal Trajectory Clustering

With the development in recent years, global positioning technology, wireless communication technology and mobile internet technology promote the various ways of positioning devices(such as satellite telephones, mobile phones, GPS receivers) widely used everywhere. It improves the spatial-temporal moving object trajectories ease of data acquisition, but also greatly reduces the acquisition costs. Since the moving object’s own movement characteristics, the Spatial-temporal trajectory mining aims at discovering temporal change pattern of moving objects or groups of individuals. The track records the movement changes with time of the object, the sampling points are ordered in chronologic. Each sampling point has the time, space, speed, semantic attributes. To determining the similarity between objects, the traditional data mining methods only need to measure the distance between two data points. However, spatial-temporal trajectory is a collection of data points. Part of the distances between two tracks between sampling points are closed, the others may be distant. Thus, the distances between points cannot meet the need if we want to judge the similarity between the trajectories. We need to determine the similarity between the sequences. Visibility, the complexity of spatial-temporal trajectory mining is much higher than traditional data mining. Trajectory data is worth researching; it can be applied to many areas, such as migration patterns discovery of animals, location-based services, traffic management and planning, monitoring climate change, the moving object behavior pattern discovery.After studying the related research background, this paper focuses on the study around trajectory clustering model and framework, similarity measure method, and trajectory clustering algorithm. A novel spatial-temporal trajectory clustering framework based on the road network is proposed, then a spatial-temporal trajectory similarity metrics is proposed after improving the trajectory division method in the road network. At last, an algorithm of road network aware spatial-temporal trajectory clustering is proposed, it also called NEASTT. By researching the traditional trajectory clustering algorithm realize the disadvantages of the current algorithm. Considering the moving objects are move in the certain road network and the trace contains the property of time, space, speed and so on. The original trajectories will be division to trajectory segments in the road network space first, measure the spatial-temporal distance between the segments using the similarity method, and then clustering the similar trajectory segments in the same road. The adjacent trajectories units are merged selectively by dividing the original trajectories based on real road-network to make sure the highly continuous and high flow of the mobile objects. Finally, the motion paths of the mobile objects in certain time slice can be found. From the experimental results can be learned, the new framework and methods proposed in this thesis can mining the spatial-temporal trajectory clustering effectively, and it can reveal the movement represents the path of moving objects within a certain time frame.