Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 02:24, 30 October 2016

Revision as of 02:26, 30 October 2016

Line 4:

The resulting system of merges occurs in a different order than in a naive implementation of the same clustering algorithms, but can be shown to generate the same hierarchy of clusters.

The nearest-neighbor chain algorithm determines a clustering in time quadratic in the number of points. This time bound is linear in the input size, whenfor thean input is given as an explicit distance matrix. The method uses an amount of memory that is linear in the number of points to be clustered, for clustering methods such as Ward's method that allow constant-time calculation of the distance between clusters. However, for other clustering methods a larger amount of memory must be used to maintain an array of distances between pairs of clusters.

==Background==