Maximize K-Clustering Spacing

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/QWubN/application-to-clustering

Internal

• Clustering Concepts

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

Correctness Proof

https://www.coursera.org/learn/algorithms-greedy/lecture/7lWTf/correctness-of-clustering-algorithm