In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two categories: Agglomerative: Agglomerative clustering, often referred to as a "bottom-up" approach, begins with each data point as an individual cluster. At each step, the algorithm merges the two most similar clusters based on a chosen distance metric (e.g., Euclidean distance) and linkage criterion (e.g., single-linkage, complete-linkage). This process continues until all data points are combined into a single cluster or a stopping criterion is met. Agglomerative methods are more commonly used due to their simplicity and computational efficiency for small to medium-sized datasets. Divisive: Divisive clustering, known as a "top-down" approach, starts with all data points in a single cluster and recursively splits the cluster into smaller ones. At each step, the algorithm selects a cluster and divides it into two or more subsets, often using a criterion such as maximizing the distance between resulting clusters. Divisive methods are less common but can be useful when the goal is to identify large, distinct clusters first.
In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram.
Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances. On the other hand, except for the special case of single-linkage distance, none of the algorithms (except exhaustive search in ) can be guaranteed to find the optimum solution.
Complexity The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of and requires memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of complexity ) are known: SLINK for single-linkage and CLINK for complete-linkage clustering. With a heap, the runtime of the general case can be reduced to instead of , at the cost of additional the memory requirements. In many cases, the memory overheads of this approach are too large to make it practically usable. Methods exist which use quadtrees that demonstrate total running time with space.
Divisive clustering with an exhaustive search is , but it is common to use faster heuristics to choose splits, such as k-means.
Distance metrics While the linkage criterion determines how dissimilarity between sets of observations is computed, the underlying distance metric determines how dissimilarity between individual observations is measured. Because hierarchical clustering permits any valid measure of distance, the choice of metric is guided by the nature of the data and can have a significant effect on the resulting clustering.Everitt, B. S.; Landau, S.; Leese, M.; Stahl, D. (2011). Cluster Analysis (5th ed.). Wiley. ISBN 978-0-470-74991-3.
Euclidean distance is the most widely used metric for continuous numerical data. It corresponds to the straight-line distance between two points in Euclidean space and is the default choice in most statistical software:
Manhattan distance (also called city-block or L1 distance) sums the absolute differences across features:
It is often preferred when features are measured on different scales or when the data contain outliers, as it is less sensitive to large deviations than Euclidean distance.
Cosine distance measures angular dissimilarity between two non-zero vectors:Manning, C. D.; Raghavan, P.; Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. ISBN 978-0-521-86571-5.
Because it disregards vector magnitude, it is frequently used in text mining and document clustering, where documents are represented as high-dimensional term-frequency vectors.
Mahalanobis distance accounts for correlations between features by incorporating the inverse of the data's covariance matrix S:Mahalanobis, P. C. (1936). "On the generalised distance in statistics". Proceedings of the National Institute of Sciences of India. 2 (1): 49–55.
Unlike Euclidean distance, it is scale-invariant and is useful when features are correlated or measured in different units.
Hamming distance is used for categorical or binary data and counts the number of positions at which two observations differ. It is commonly applied to genetic sequences and binary feature vectors.Jain, A. K.; Dubes, R. C. (1988). Algorithms for Clustering Data. Prentice Hall. ISBN 978-0-13-022278-7.
The choice of metric interacts with the choice of linkage criterion. For example, Ward's method and centroid-based linkages are defined in terms of squared Euclidean distances, whereas single-linkage and complete-linkage clustering can be used with any valid metric.
Cluster linkage In order to decide which clusters should be combined (for agglomerative), or where a cluster should be split (for divisive), a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate distance d, such as the Euclidean distance, between single observations of the data set, and a linkage criterion, which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets. The choice of metric as well as linkage can have a major impact on the result of the clustering, where the lower level metric determines which objects are most similar, whereas the linkage criterion influences the shape of the clusters. For example, complete-linkage tends to produce more spherical clusters than single-linkage.
The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations.
Some commonly used linkage criteria between two sets of observations A and B and a distance d are: Names Formula Maximum or complete-linkage clustering Minimum or single-linkage clustering Unweighted average linkage clustering (or UPGMA) Weighted average linkage clustering (or WPGMA) Centroid linkage clustering, or UPGMC where and are the centroids of A resp. B.Median linkage clustering, or WPGMC where Versatile linkage clustering Ward linkage, Minimum Increase of Sum of Squares (MISSQ)Minimum Error Sum of Squares (MNSSQ)Minimum Increase in Variance (MIVAR)Minimum Variance (MNVAR)Hausdorff linkageMinimum Sum Medoid linkage such that m is the medoid of the resulting clusterMinimum Sum Increase Medoid linkageMedoid linkage where , are the medoids of the previous clusters Minimum energy clustering Some of these can only be recomputed recursively (WPGMA, WPGMC), for many a recursive computation with Lance-Williams-equations is more efficient, while for other (Hausdorff, Medoid) the distances have to be computed with the slower full formula. Other linkage criteria include:
The probability that candidate clusters spawn from the same distribution function (V-linkage). The product of in-degree and out-degree on a k-nearest-neighbour graph (graph degree linkage). See also: https://github.com/waynezhanghk/gacluster The increment of some cluster descriptor (i.e., a quantity defined for measuring the quality of a cluster) after merging two clusters.
Comparison of linkage methods
The choice of linkage criterion significantly affects the shape and quality of the resulting clusters. Each method has distinct strengths and weaknesses depending on the structure of the data.Verma, Neeraj; Grover, Pooja; Deep, Ajay (2012). "An Approach for Cluster Analysis based upon Hierarchical Algorithm - Agglomerative Algorithm". IJESM, 2(3). PDF Link.
Single linkage (also called the nearest-neighbor method) defines the distance between two clusters as the minimum distance between any pair of points, one from each cluster. This method can detect and handle clusters of arbitrary shape, including elongated and non-globular structures. However, it is highly sensitive to noise and outliers, because a single pair of close points is sufficient to merge two clusters.
Complete linkage defines the distance between two clusters as the maximum distance between any pair of points across the two clusters. It is less susceptible to noise and outliers than single linkage. However, complete linkage is biased toward producing globular clusters of similar size and may incorrectly break apart large or irregularly shaped clusters.
Average linkage (specifically UPGMA, the unweighted pair group method with arithmetic mean) defines the distance between two clusters as the average of all pairwise distances between points in the two clusters. It represents a compromise between the extremes of single and complete linkage. Average linkage is more robust to noise than single linkage but, like complete linkage, it tends to be biased toward detecting globular clusters.
+ Comparison of common linkage methods in hierarchical clustering Linkage method Distance definition Cluster shape detected Noise sensitivity Key limitation Single linkage Minimum pairwise distance Arbitrary (non-globular) High Sensitive to noise and outliers Complete linkage Maximum pairwise distance Globular Low Tends to break large clusters Average linkage (UPGMA) Mean of all pairwise distances Globular Moderate Biased toward equal-sized clusters
Computational complexity The naive implementation of agglomerative hierarchical clustering has a time complexity of O(n³) and a space complexity of O(n²), where n is the number of data points, because at each of the n − 1 merge steps the algorithm must search and update an n × n proximity matrix. For single linkage, optimized algorithms based on minimum spanning trees reduce the time complexity to O(n² log n). For other linkage criteria, the use of priority queues and nearest-neighbor chains can also achieve O(n² log n) time in practice.
Hausdorff linkage
Hausdorff linkage is a hierarchical clustering criterion based on the Hausdorff distance, a metric defined between sets of points in a given metric space. Unlike standard linkage methods that rely on pairwise distances between individual observations, Hausdorff linkage evaluates distances between entire clusters, thereby incorporating information about their geometric structure.
Formally, let be a metric space, and let and be nonempty compact subsets of . The distance from a point to a set is defined as:
Extending this to sets, the directed distance from to is:
Since this quantity is not symmetric, the Hausdorff distance between two sets is defined as:
This definition captures the largest distance from a point in one set to the closest point in the other set. Equivalently, it can be interpreted as the smallest radius such that every point of lies within distance of some point in , and every point of lies within distance of some point in . In this sense, the Hausdorff distance measures the maximum mismatch between two sets.
In hierarchical clustering, Hausdorff linkage uses as the dissimilarity measure between clusters. Initially, each data point forms its own cluster, and the Hausdorff distance between singleton sets reduces to the original metric. At each step, the two clusters with the smallest Hausdorff distance are merged, and distances are recomputed using the same set-based definition. This iterative process continues until all points belong to a single cluster, producing a hierarchical structure (dendrogram).