Ultrametric

This relation between hierarchical clusterings and ultrametrics is one-to-one; if, that is, we agree not to distinguish ultrametrics that are (strictly) monotonically related to each other. That is, there is one and only one ultrametric for each hierarchical tree structure. Thus there is an isomorphism between ultrametrics and hierarchical tree structures. In this sense the two can be identified.

Obviously, an absolute guarantee of optimality is not possible through this type of heuristic search, but the eventual stability achieved leads to an ultrametric that is usually very good (although not verifiably optimal). Throughout this discussion it is assumed that the subsets of objects for which separate optimal ultrametrics are generated, or the number of object classes to be used in obtaining an optimal ultrametric beginning from that point, are all of a size that could be handled optimally (i.e., some number in the lower teen’s).

The ultrametric defined by Theorem 10 is known as the maximal subdominant ultrametric for the dissimilarity d. The situation is not symmetric with respect to the infimum of a set of ultrametrics because, in general, the infimum of a set of ultrametrics is not necessarily an ultrametric.