0 votes

I have a table with 5 columns: point_id (Integer); postal_code (Integer); latitude (Decimal); longitude (Decimal); geoLatLon (GeoPoint)

1. I would like to calculate the pairwise distances between these points according to my formula (par exemple, haversine distance)

2. Group these points into given number of clusters (for exemple, 2 clusters) with minimum 2 points at each cluster  so that the total distance between the points of one cluster is less as possible. 

How could I implement these steps? I was planning to use quick clustering model with K-means algorithm , but I have not found any tutorial on how to calculate pairwise distances between all points and pass these distances to the model.

asked by

1 Answer

+1 vote
Hi,

Computing all pairwise distances between points require to compute a cross-join product. It can be very expensive as it involves N_rows ^ 2 computations.

The K-means algorithm uses L2-distance, which can be seen as a local approximation of Haversine. Unless your points are very far from each other (different time zones for instance) you can safely use this approximation. Hence, I would advise going for a simple K-means first, as you did.

If you want to go further and your data has a reasonable number of rows, you could compute a distance matrix using a Join recipe to Cross-Join the dataset with itself, then use the "Post-join computed columns" section with the geoDistance formula. Then use a custom clustering function which takes a distance matrix argument, such as DBSCAN (https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html). Beware that the computational cost will be much higher than the simple approach.

Hope it helps,

Alex
answered by
996 questions
1,023 answers
1,075 comments
3,030 users

┬ęDataiku 2012-2018 - Privacy Policy