Hierarchical clustering, also known as hierarchical cluster analysis (HCA), is a method of cluster analysis in data mining and statistics that seeks to build a hierarchy of clusters. Unlike partitional methods such as k-means, which require the number of clusters to be specified in advance, hierarchical clustering produces a nested structure that can be cut at any level to yield different numbers of clusters. The results are typically presented in a dendrogram, a tree-like diagram that illustrates the sequence of merges or splits. This approach is widely used in fields such as biology, social sciences, and Machine learning for exploratory data analysis.
The key advantage of hierarchical clustering is its flexibility: any valid measure of distance can be used, and the observations themselves are not required, only a matrix of distances. However, except for the special case of single-linkage distance, none of the algorithms can be guaranteed to find the optimum solution without exhaustive search, which has a time complexity of O(2^n).
Agglomerative and Divisive Strategies
Hierarchical clustering strategies generally fall into two categories: agglomerative and divisive. Agglomerative clustering, often called 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 a 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 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, meaning that the algorithm makes locally optimal choices at each step without considering the global structure.
Complexity and Algorithms
The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of O(n^3) and requires Ω(n^2) memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods of complexity O(n^2) 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 O(n^2 log n) instead of O(n^3), at the cost of additional 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 O(n^2) total running time with O(n) space.
Divisive clustering with an exhaustive search is O(2^n), but it is common to use faster heuristics to choose splits, such as k-means. These heuristics trade off optimality for computational feasibility, allowing divisive methods to be applied to larger datasets.
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.
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 and is commonly used in text analysis and other high-dimensional settings.
Linkage Criteria
The linkage criterion determines how the distance between two clusters is calculated from the distances between their individual members. Single-linkage (or nearest-neighbor) uses the minimum distance between any two points in the two clusters, which tends to produce long, chain-like clusters. Complete-linkage (or farthest-neighbor) uses the maximum distance, which tends to produce compact, spherical clusters. Average-linkage uses the mean distance between all pairs of points, offering a compromise between the two. Ward's method minimizes the total within-cluster variance, making it popular for continuous data. The choice of linkage criterion can dramatically alter the shape and interpretation of the resulting dendrogram.
Applications and Limitations
Hierarchical clustering is used across many domains. In biology, it is used to construct phylogenetic trees based on genetic similarity. In marketing, it helps segment customers into groups with similar behaviors. In image analysis, it can group pixels or features. In Artificial intelligence, hierarchical clustering is often used as an unsupervised learning technique for exploratory data analysis and as a preprocessing step for other algorithms.
Despite its advantages, hierarchical clustering has limitations. The greedy nature of the algorithms means that once a merge or split is made, it cannot be undone, which can lead to suboptimal results. The computational complexity of the standard algorithm restricts its use to datasets of moderate size, although optimized implementations exist for specific linkage criteria. Additionally, the interpretation of a dendrogram can be subjective, and the choice of distance metric and linkage criterion requires domain knowledge.