Content deleted Content added
→Background: also here |
→Centroid distance: "a good heuristic" |
||
Line 179:
===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. For 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. Nevertheless, {{harvtxt|Murtagh|1983}} writes that the nearest-neighbor chain algorithm provides "a good heuristic" for the centroid method.<ref name="murtagh-tcj"/>
A different algorithm by {{harvtxt|Day ===Distances sensitive to merge order===
| |||