Hierarchical clustering

It has been suggested that Cluster analysis#Hierarchical clustering be merged into this article or section. (Discuss)

In statistics, hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:

• Agglomerative: This is a "bottom up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.
• Divisive: This is a "top down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram.

Cluster dissimilarity

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 metric (a measure of distance between pairs of observations), and a linkage criteria which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets.

Metric

The choice of an appropriate metric will influence the shape of the clusters, as some elements may be close to one another according to one distance and farther away according to another. For example, in a 2-dimensional space, the distance between the point (1,0) and the origin (0,0) is always 1 according to the usual norms, but the distance between the point (1,1) and the origin (0,0) can be 2, or 1 under Manhattan distance, Euclidean distance or maximum distance respectively.

Some commonly used metrics for hierarchical clustering are:^[1]

Names	Formula
Euclidean distance
squared Euclidean distance
Manhattan distance
maximum distance
Mahalanobis distance	where S is the covariance matrix
cosine similarity

For text or other non-numeric data, metrics such as the Hamming distance or Levenshtein distance are often used.

A review of cluster analysis in health psychology research found that the most common distance measure in published studies in that research area is the Euclidean distance or the squared Euclidean distance.^{[citation needed]}

Linkage criteria

The linkage criteria 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 are:^[2]

Names	Formula
Maximum or complete linkage clustering
Minimum or single-linkage clustering
Mean or average linkage clustering, or UPGMA

where d is the chosen metric.

• The sum of all intra-cluster variance.
• The increase in variance for the cluster being merged (Ward's criterion).^[3]
• The probability that candidate clusters spawn from the same distribution function (V-linkage).

Discussion

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.

Software

Free

• R has several functions for hierarchical clustering: see CRAN Task View: Cluster Analysis & Finite Mixture Models for more information.
• Orange, a free data mining software suite, module orngClustering
• For a simple C source file implementing the bottom-up algorithm [1]

Commercial

• Software for analyzing multivariate data with instant response using Hierarchical clustering
• SAS CLUSTER
• Matlab Hierarchical Clustering (Statistics Toolbox)

See also

• Cluster analysis
• Hierarchical clustering of networks
• k-means clustering

Notes

References and further reading

• Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). "14.3.12 Hierarchical clustering" (PDF). The Elements of Statistical Learning (2nd ed.). New York: Springer. pp. 520–528. ISBN 0-387-84857-6. http://www-stat.stanford.edu/~tibs/ElemStatLearn/. Retrieved 2009-10-20.