Single Linkage Clustering

Cluster points with agglomerative clustering and single linkage, stopping when k clusters remain.

Agglomerative clustering starts with every point in its own cluster. It then merges the two closest clusters, again and again. Single linkage defines the distance between two clusters as the distance between their closest pair of points, using Euclidean distance. This lets it follow long, thin or curved shapes that k-means cannot, but a single chain of points can also join two groups that should stay apart.

Merge until exactly k clusters are left. If two pairs of clusters are equally close, any choice is accepted. Then label the clusters in order of first appearance: the cluster of point 0 gets label 0, the next new cluster you meet while scanning the points in order gets 1, and so on.

Function signature

def single_linkage(X, k):

Example

Input

X = np.array([[0.0], [1.0], [5.0], [6.0], [20.0]])
single_linkage(X, k=2)

Output

array([0, 0, 0, 0, 1])

Reasoning

The closest pairs are 0-1 and 5-6, both at distance 1, so they merge first. The two new clusters are then 4 apart, at their nearest points 1 and 5, while 20 is 14 from everything. So {0, 1, 5, 6} merges next, and two clusters remain.

Constraints and notes

• X has shape (n, d) and 1 <= k <= n.
• n is small, so an O(n^3) approach is fine.
• Return an integer array of shape (n,).