Tips on speeding up hierarchical linkage clustering algorithm

Question

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:

1. Compute distance matrix between all points (great-circle distance, not Euclidean)
2. Find the pair of points with the minimum distance between them
3. If the minimum distance is larger than a threshold value
   • the algorithm finishes
4. Otherwise
   • 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
5. 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.

Thank you!

Answer 1

Yes. After you merge two points, you can update the distances of just the affected nodes, without having to recompute all pairs of distances again. That will be vastly faster.