Spectral Clustering Method Based On Affinity Propagation For Vessel Trajectory Clustering

The continuous development of the world economic integration process poses higher requirements for water traffic management.Therefore,using an appropriate clustering algorithm to cluster ship trajectory has a great application value in water traffic areas.Spectral clustering algorithms work effeciently on both the clustering of non-convex sphere of sample spaces and the distribution of complex and high-dimension data,therefore it is widly applied.But the results of conventional spectral clustering algrithms are often unsatisfactory because they are sensitive to the initial value selection and usually plunge into local optima.Firstly,this paper proposes a new spectral clustering algorithm based on Affinity Propagation(AP-SC algorithm)aming at solving the problems above.Secondly,this paper adopts Douglas Peucker algorithm(DP algorithm)for extracting ship trajectory features to reduce the calculation time and optimize the results of AP-SC algorithm.Finally,this paper applies the AP-SC algorithm in the water traffic sector,clusters and digs characterisitics of the ship trajectory.The main research work is summarized as follows:1.This paper proposes a spectral clustering algorithms based on Affinity Propagation.After analizes the theory of spectral clustering,based on the Affinity Propagation,this paper improves the disadvantages of convetional spectral clustering algorithms are sensitive to the initial value selection and usually plunge into local optima while using K-means to converge characterized vector groups.By comparing the experimental results of ship trajectory clustering with different clusters,it is verified that the AP-SC algorithm proposed in this paper not only solves the problem of spectral clustering which is sensitive to the initial value and has stronger robustness,but also gets a higher accuracy than the conventional spectral clustering algorithm.2.This paper adopts DP algorithm to reduce the calculation time and optimize the results of AP-SC algorithm.Since the AP-SC algorithm consumes more time than the conventional spectral clustering algorithm,this paper adopts DP algorithm for extracting ship trajectory features by deleting the non-key points in the trajectory to reduce the calculation time of ship trajectory similarity and optimize the AP-SC algorithm.Taking compression rate and the influence of compression trajectory on the clustering results into full consideration,the optimal threshold is selected to compress the ship trajectory.After experimental comparison and analysis of the ship trajectory clustering results as well as the original trajectory,it's verified that adopting DP algorithm can not only reduce the calculation time of AP-SC algorithm,but also can improve the accuracy of clustering.3.This paper applies the AP-SC algorithm in the water traffic sector.Firstly,this paper analyzes the clustering results of AP-SC algorithm to the waters of the ship trajectory,combined with the actual situation of Wuhan Yangtze River bridge navigable waters,and then verifies the validity of the clustering results.Secondly,this paper apllies results of clustering to monitoring ship speed.We can avoid the ship collision accidents happened in Wuhan Yangtze River bridge caused by the subjective problem of over-speed.