Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 01:00, 30 October 2016

Revision as of 01:21, 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, when the 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, andfor determinesclustering amethods clusteringsuch inas Ward's method that allow constant-time quadraticcalculation inof the numberdistance ofbetween pointsclusters. (linearHowever, infor theother inputclustering size,methods whena thelarger inputamount isof givenmemory asmust be used to maintain an explicitarray distanceof matrix)distances between pairs of clusters.

==Background==