Skip to content
Last Dictionary
Plane
Machine LearningData & Datasets

hierarchical clustering

nounAlso: agglomerative clustering, divisive clustering, dendrogram, linkage, Ward's method, UPGMA

In plain wordsA way of grouping data that builds a family tree of clusters, joining the most similar items step by step, so you can cut the tree at whatever level of detail you need.

  1. A family of clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size. methods that produce a nested hierarchy of clusters rather than a single partition, usually drawn as a dendrogram: a tree in which the height of each merge records the dissimilarity at which two groups join. Most implementations are agglomerative, building the tree upward from single points by repeatedly fusing the two nearest groups; the less common divisive approach works downward, recursively splitting one all-inclusive group. A linkage criterion defines the distance between clusters: single linkage (closest pair of members, prone to chaining into long, thin clusters), complete linkage (farthest pair), average linkage (UPGMA, the mean pairwise distance) and Ward's method (the merge that least increases within-cluster variance). Cutting the dendrogram at a chosen height yields a flat clustering, so the number of clusters need not be fixed beforehand. Cost is the practical limit: keeping every pairwise distance takes O(n²) memory, and although single linkage can be computed in O(n²) time (SLINK), the naive general procedure needs O(n³).

    Cut the dendrogram at a distance of 0.7 and you get five product families.

Origin

Hierarchical grouping grew out of numerical taxonomy. Single linkage appeared in work by Kazimierz Florek and colleagues (1951) and by Peter Sneath (1957); Robert Sokal and Charles Michener introduced average linkage (UPGMA) in 1958; and Joe Ward published his minimum-variance method in 1963. Efficient algorithms such as Robin Sibson's SLINK (1973) made the approach practical on larger datasets.

Usage note

Results depend strongly on the linkage and distance measure, and merges are greedy: a poor early merge is never undone. Widely used in biology (gene-expression heatmaps, phylogeny-like trees) and for building taxonomies of documents or products.

Related

See also
  • clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size.
  • k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.
  • DBSCANDBSCAN, n.: A clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise.
  • Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length.
  • silhouette scoresilhouette score, n.: A number between −1 and 1 that grades a grouping of data by checking, for each point, whether it sits closer to its own group than to the next-nearest group.
  • dimensionality reductiondimensionality reduction, n.: Squeezing data that has many measurements per item into far fewer numbers while keeping the patterns that matter, so it is easier to visualize, store or learn from.

Sources

  1. Sokal, R. R. & Michener, C. D. (1958). A Statistical Method for Evaluating Systematic Relationships. University of Kansas Science Bulletin 38.
  2. Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association 58(301).
  3. Sibson, R. (1973). SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method. The Computer Journal 16(1).

Mentioned in

clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size., DBSCANDBSCAN, n.: A clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise., k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat., silhouette scoresilhouette score, n.: A number between −1 and 1 that grades a grouping of data by checking, for each point, whether it sits closer to its own group than to the next-nearest group.