Single-linkage clustering

Single-linkage clustering is one of several methods of hierarchical clustering. It works bottom-up, as an agglomerative method: every element starts in a cluster of its own, and at each step the two clusters that contain the closest pair of elements not yet in the same cluster are combined, until everything is in one cluster. The distance between two clusters is the distance between their single closest pair of elements, one from each, which is why the method is also called nearest neighbour clustering. The result can be drawn as a dendrogram showing the order of merges and the distance at which each happened. The method tends to produce long thin clusters, which can make classes hard to define for some data, but it is popular in astronomy for analysing galaxy clusters, where it is also known as the friends-of-friends algorithm. The naive algorithm is essentially Kruskal's algorithm for minimum spanning trees and takes cubic time; in 1973 R. Sibson proposed SLINK, which runs in quadratic time and linear space.