Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 23:10, 29 October 2016

Revision as of 23:16, 29 October 2016

Line 175:

===Centroid distance===

Another distance measure commonly used in agglomerative clustering is the distance between the centroids of pairs of clusters, also known as the weighted group method.<ref name="mirkin"/><ref name="lance-williams"/> It can be calculated easily in constant time per distance calculation. However, it is not reducible:. forFor instance, if the input forms the set of three points of an equilateral triangle, merging two of these points into a larger cluster causes the inter-cluster distance to decrease, a violation of reducibility. Therefore, the nearest-neighbor chain algorithm will not necessarily find the same clustering as the greedy algorithm. A different algorithm by Day and Edelsbrunner can be used to find the clustering in {{math|''O''(''n''²)}} time for this distance measure.<ref name="day-edels"/>

===Distances sensitive to merge order===