I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude.
I read about this algorithm here.
These are the steps:
- Compute distance matrix between all points (great-circle distance, not Euclidean)
- Find the pair of points with the minimum distance between them
- If the minimum distance is larger than a threshold value
- the algorithm finishes
- The two points are merged, and removed from the list of points.
- The center point of this pair is added to the list of points
- Go back to 1
I do not consider single, complete, etc. types of linkage, since the points are substituted by a central point. Therefore, the distance is just the distance between all points (instead of point-cluster).
It runs okay for small amount of pairs, but it takes 1 second per iteration as soon as I run it for 5,000 points; potentially 83 minutes although it probably stops halfway due to the distance threshold.
Although I use Haversine formulation in the calculation of distances, it does not change much if I use a simple Euclidean approach; it then takes 1 second for 3 iterations.
Am I making a mistake in understanding and implementing this algorithm? If not, are there ways in which this could be sped up?
I am using MATLAB R2018b.