Research Of Distance Measurement And Clustering Algorithms In Trajectory Clustering

As the sensor, satellites, GPS and other mobile positioning system are widely used, the trajectory information of moving object can be collected easily. Trajectory is normally consists of a sequence of discrete sampling points that have same time intervals. In the face of massive of large trajectory data, how to find useful information from these data becomes increasingly important. A typical analysis task of trajectories is to find the movement rule and behavior patterns of moving objects by trajectory clustering. The results can contribute to the navigation, decision-making and urban road planning, etc.In this paper, through the study of trajectory distance measures and clustering methods, we propose a trajectory distance measurement based on grid space (GDTW) and a trajectory clustering method based on hierarchy (CARS_FAOM).GDTW. This method first transforms the representation of trajectories from the Euclidean space to the Grid space by Dynamic Grid Partitioning method, and then uses the DTW method to measure the distance between the transformed trajectories. By this way, we can not only ignore the influence of different sampling frequency and speed of moving objects, but also define the applicable distance values between trajectories according to their directions. Compared with the state-of-the-art, experimental results show that this method can effectively measure the distance between trajectories.CARS_FAOM. Since trajectories have the characteristics of local similarity and different density in different areas, this paper introduces the ideas of hierarchy. This method first divide the trajectory data space to several equal height layers according to a certain dimension. Then it clusters each layer and finds the representative route of each cluster by using CARS algorithm. Finally, it merges conjoint layers that have similar representative routes in the form of bottom-up by FAOM algorithm in order to find the right hierarchy of trajectory data space. Through the experimental analysis of the San Francisco international airport flight data, we prove that this method can effectively perform the trajectory clustering, find the center of a cluster, discover the local patterns of trajectories, and obtain clustering results that have different accuracy.