Research And Application Of Moving Object Trajectory Clustering Algorithm In Road Network Environment

The intelligent transportation system has established a huge traffic data resource.Intelligent analysis of traffic data with time and space characteristics can obtain valuable knowledge,which can provide decision support for the urban traffic congestion area detection and the optimal path recommendation,etc.This thesis addresses the needs of urban traffic congestion analysis,and based on the trajectory data elements of mobile objects,studies trajectory similarity measurements and expression methods.Based on this,trajectory clustering are performed and applied to the detection of traffic congestion areas.The main work of this thesis is shown as follows:(1)This thesis introduces the relevant concepts of the intelligent transportation system,analyzes the practical application value of the trajectory clustering technology for moving objects,and summarizes the research status and application status of the moving object trajectory clustering technology at home and abroad.(2)Aiming at the existing trajectory similarity measurement algorithm is not suitable for analyzing the noise trajectory of non-uniform distribution in the time dimension,a trajectory similarity measurement algorithm based on feature points and edit distance is proposed.Firstly,a trajectory feature point selection algorithm based on motion direction and time segmentation is given.The position point where the direction of motion in the trajectory changes significantly is selected as a feature point,and the original trajectory is represented as a feature point trajectory.In the process of trajectory similarity measurement,a trajectory similarity measurement algorithm based on edit distance is proposed.The similarity between trajectories can be obtained by defining the cost of insert operation,substitute operation and delete operation in edit distance respectively.The experimental results show that compared with the trajectory similarity measure based on the real penalty value edit distance and the trajectory similarity measure algorithm based on the real sequence edit distance,the algorithm has a good performance in terms of operating efficiency and clustering quality.(3)Aiming at the problem that the TRACLUS algorithm based on partition and reorganization framework is very sensitive to two input parameters,a clustering algorithm based on density peaks for moving object trajectories is proposed.Firstly,non-parametric kernel density estimation is used to calculate the probability density of a given trajectory data set.Based on the theory of heat diffusion,the distribution characteristics of data points are analyzed and the cut-off distance parameter is adaptively selected to improve the original density peak clustering algorithm.Then the improved density peak clustering algorithm is applied to clustering the sub-trajectory.Experimental results on artificial datasets show that the improved density peak clustering algorithm not only effectively avoids the subjectiveness of artificially selected cut off distances,but also has better robustness and accuracy than the original CFSFDP algorithm.Experimental results on real trajectory datasets show that the clustering algorithm for moving object trajectories based on density peaks reduces the sensitivity to the input parameters compared to the TRACLUS algorithm,and has a better trajectory clustering effect.(4)Based on the above research results,a prototype system for detecting urban traffic congestion regions is designed and implemented.The prototype system realized the functions of urban traffic data collectionurban,traffic congestion area detection and map operations.