# How to predict routes using clustering data

I've been working on a ship route prediction algorithm such that given the past and current trajectory of a ship I am able to estimate the future one. The trajectories are represented as a sequence of coordinates (latitude,longitude).

This is what I have done so far:

1. Route clustering: Using past information of ship trajectories within an area of interest, group these routes according to proximity and similarity, as illustrated in this image:

1. Classification: Given the past and current trajectory of the target ship, determine its corresponding cluster, e.g. the black line is the current trajectory and it should be associated with the blue cluster:

1. Prediction: Predict the upcoming trajectory.

I was successful in steps 1 and 2 and I'm trying to figure out how to proceed with step 3.

• First I tried to perform linear regression to each cluster in order its "identifying route" and then try to overlap it with the black line. Unfortunately this is not good in many scenarios, e.g. by moving the line it may end up overlapping land when the cluster is near shore.
• I tried to use a neural network trained to accept sequences of (lat,lon) points as input and output the next ones, but I had little success in terms of precision.

I wonder if I am looking at this all wrong and if there are better approaches to address step 3. Does anyone have any suggestions?

• If you are able to classify a current trajectory into a cluster, then why can't you just use the cluster average path as the predicted trajectory? Commented Feb 18, 2019 at 14:10
• Unless the current trajectory coincides with the average path, you will not get a smooth continuation of the current trajectory Commented Feb 18, 2019 at 14:48
• I'm curious about why you cluster first rather than building a prediction model based on the past trajectory directly without clusters? Commented May 16, 2020 at 10:28
• Aren't you assuming that the route(s) the ship travels is fixed? Otherwise, the route picking issue resemble the classic traveling salesman optimization problem in computer science, historically an np hard, computationally complex computer science challenge. One of the first to address this challenge was S.C. Johnson who developed hierarchical clustering as his approach to its solution. en.wikipedia.org/wiki/Travelling_salesman_problem Johnson, S.C. (1967) Hierarchical Clustering Schemes. Psychometrika, 32, 241-254. Commented Jul 17, 2023 at 10:58

Because of my low reputation I'll use this reply as a comment. Fitting a curve over the points of the blue course isn't enough? There are a lot of methods out there, one of them being the classic spline.

You can also try your own heuristic. I'll give some that came in mind.

Depending on the number of points you could create a graph in which the coordinates are the nodes and the vertices have cost measured by the euclidean distance (or any other distance method) between the coordinates. Then, you use some graph theory algorithm to take the minimum cost spanning tree of this graph. It will be like, given the route from the other ships, the optimal one.

Another method would be based on the KNN. Take the origin point of the ship. Then take the N (arbitrary value) points and do the mean. From this next point, do the process of finding the next one from the N closest points. For this you will have to create some rule to discard coordinates, so you don't move back.

Hope it give you some more ideas. Please comment back if you like me to throw more, as I would like to discuss this in more detail

• I has actually considered using graph theory, but I strongly suspect that this won't result in a smooth line, because it will include points of multiple lines Commented Feb 18, 2019 at 14:50
• Actually, the more points the better. Imagine you have a grid which each square are 1 by 1 meter. Now, imagine a grid with squares with 1 by 1 cm. If you can only move on the vertices of the squares, the grid with smaller squares will grant you a much more free movement. That being said, the more points a minimum spanning tree has, the smoother "curve" should be because the algorithm will have more directions to choose from Commented Feb 18, 2019 at 22:03
• The route created by the algorithm will be the one with least distance. So it will tangent the curves, just as a race car. It makes sense, because the boat must optimize the time duration of the trip. You can also go event beyond and put cost on the vertices of the graph that are related to ocean current Commented Feb 18, 2019 at 23:50