Maximize K-Clustering Spacing
External
Internal
Overview
This is a greedy algorithm that aims to maximize spacing between any two clusters. By spacing between two clusters we mean the minimum distance between any two separated points, which belong to two distinct clusters:
minseparated p, qd(p,q)
"Good" clustering means that all of the separated points should be as far apart as possible.
Algorithm
The conceptual pseudocode to achieve k-clustering with maximum possible spacing is:
initially each point is a separate cluster repeat until only k clusters: let p,q = closest pair of separated points # determines the current spacing merge the clusters containing p and q into a single cluster
This algorithm is a single-link clustering algorithm, in that it refines the clustering by fusing clusters one point at a time. It is very similar in structure to the Kruskal's algorithm. A practical implementation that sorts the distances in a pre-processing steps, in a similar manner to how the Kruskal's algorithm does it, and then manages clusters with an union-find is:
initialize union-find U # each point belongs initially to its own separate one-point cluster sort distances # distances between point are sorted from smallest to largest for d=(p,q) in sorted_distances: # process distances from smallest to largest if U.find(p) != U.find(q): # points belong to different clusters if U.clusterCount() == k: # we reached the target cluster count, return the spacing between clusters return d else: U.union(cluster(p), cluster(q)) # merge the clusters