Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 01:21, 30 October 2016

Revision as of 02:24, 30 October 2016

Line 1:

In the theory of [[cluster analysis]], the '''nearest-neighbor chain algorithm''' is aan method[[algorithm]] that can be used to perform several types of [[agglomerative hierarchical clustering]], in which a hierarchy of clusters is created by repeatedly merging pairs of smaller clusters to form larger clusters. In particular it can be used for [[Ward's method]], [[complete-linkage clustering]], and [[single-linkage clustering]], which all work by merging the closest two clusters under different definitions of the distance between clusters.

The main idea of the algorithm is to find pairs of clusters to merge by following paths in the [[nearest neighbor graph]] of the clusters until the paths terminate in pairs of mutual nearest neighbors. That pair of clusters is then chosen as the pair to merge by the algorithm. The algorithm uses a [[Stack (abstract data type)|stack]] to find and merge mutually nearest pairs of clusters efficiently.