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 O ( 2 n ) {\displaystyle {\mathcal {O}}(2^{n})} ) can be guaranteed to find the optimum solution.
Complexity The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of O ( n 3 ) {\displaystyle {\mathcal {O}}(n^{3})} and requires Ω ( n 2 ) {\displaystyle \Omega (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 ) {\displaystyle {\mathcal {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 ) {\displaystyle {\mathcal {O}}(n^{2}\log n)} instead of O ( n 3 ) {\displaystyle {\mathcal {O}}(n^{3})} , 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 O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} total running time with O ( n ) {\displaystyle {\mathcal {O}}(n)} space. Divisive clustering with an exhaustive search is O ( 2 n ) {\displaystyle {\mathcal {O}}(2^{n})} , 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. 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:
d ( x , y ) = ∑ i = 1 n ( x i − y i ) 2 {\displaystyle d(\mathbf {x} ,\mathbf {y} )={\sqrt {\sum _{i=1}^{n}(x_{i}-y_{i})^{2}}}}
Manhattan distance (also called city-block or L1 distance) sums the absolute differences across features:
d ( x , y ) = ∑ i = 1 n | x i − y i | {\displaystyle d(\mathbf {x} ,\mathbf {y} )=\sum _{i=1}^{n}|x_{i}-y_{i}|}
… excerpt ends here. Continue reading the full article.
