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?

  • $\begingroup$ What do you want to find with your clusters? $\endgroup$ Commented Oct 18, 2016 at 10:36
  • $\begingroup$ Similar trips. Similar by start region and end region $\endgroup$
    – mondano
    Commented Oct 18, 2016 at 10:49

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.