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

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. It is very similar in structure to the Kruskal's algorithm.

Correctness Proof

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