Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 08:28, 11 December 2016

Revision as of 08:35, 11 December 2016

Line 186:

===Distances sensitive to merge order===

The above presentation explicitly disallowed distances sensitive to merge order. Indeed, allowing such distances can cause problems. In particular, there exist order-sensitive cluster distances which satisfy reducibility, but for which the above algorithm will return a hierarchy with suboptimal costs. Therefore, when cluster distances are defined by a recursive formula (as some of the ones discussed above are), care must be taken that they do not use the hierarchy in a way which is sensitive to merge order.<ref>{{citation

| last=Müllner

| first=Daniel

Line 194:

| year=2011

| bibcode=2011arXiv1109.2378M

}}.</ref>

}}.</ref> Following the earlier discussion of the value of defining cluster distances recursively (so that [[memoization]] can be used

to greatly speed up distance computations), care must be taken with recursively defined distances so that they are not using the hierarchy in a way which is sensitive to merge order.

==History==