The Research Of Clustering Algorithms On Spatio-temporal Trajectories Of Moving Object

With the development of technology, people can get the real-time position of moving object more and more convenient. The real-time position of moving object during a period of time constitutes its spatio-temporal trajectory. Advances in GPS technology and miniaturization of the equipment make the application of positioning device more and more popular. Thuswise, the data of spatio-temporal trajectory producing during people’s life is more and more, as an explosive trend. Digging out the useful information from the vast amounts of trajectory data is hard for human in a manual way. Clustering algorithm play an important role in data mining field, and more and more researchers apply it to spatio-temporal trajectory data mining.After studying the relevant similarity measure methods and clustering algorithms of spatio-temporal trajectory, we propose AMDLTP algorithm and DBSTC algorithm.Trajectory partitioning algorithm based on turning angle and minimum description length principle (AMDLTP). At first, AMDLTP get a candidate set of partitioning characteristic using turning angle threshold. Then, use the principle of minimum description length to filter the candidate set further. The partitioning characteristic point can not only keep the original feature of trajectory, but also reducing the computational complexity for next clustering progress.Sub-Trajectory clustering algorithm based on density (DBSTC). When measuring the similarity of spatio-temporal trajectory, DBSTC take both spatial similarity and temporal similarity into consideration. Their proportion in the overall similarity is different, and can be adjusted to adapt to different application environments. DBSTC calculate the density connected set of core sub-trajectory to generate sub-trajectory cluster.We experiment our algorithm on hurricane and flight data, the experimental result show that our AMDLTP algorithm can keep the original feature of trajectory, also reducing the number of trajectory point greatly. Algorithm DBSTC cluster the result of algorithm AMDLTP, the final result show that the clustering effect of DBSTC is good enough.