# How to cluster trips, i.e. directed lines on a plain

I need to cluster transports/trips based on their start point and end point in longitude/latitude.

I have about 5000 trips. Each has a starting point (lon/lat) and an end point (lon/lat). I computed the haversine distance between those points. Bases on these five criteria (start lon, start lat, end lon, end lat, distance) I want to find clusters.

I tried kmeans and DBSCAN, but the results are not intuitive. Are there any established clustering algorithms for this problem?

• What do you want to find with your clusters? – user3644640 Oct 18 '16 at 10:36
• Similar trips. Similar by start region and end region – mondano Oct 18 '16 at 10:49

## 1 Answer

I would try with only (start lon, start lat, end lon, end lat) because distance does not really mean anything in this case, because one can go the same distance also to the "wrong way" and same distance trips somewhere else have nothing common with itineraries.

One trick could be that, for each pair of flights you calculate a distance between start $d_s$ and end points $d_e$, and sum them. You can try to use other metrics for distance like $d_s^2+d_e^2$ or $(d_s+d_e)^2$. Then you get $flights\times flights$ distance matrix, which you then may cluster.