A dissimilarity measure is called an ultrametric if it satisfies the following conditions:
for all x
for all x, y
for all x, y
for all x, y, and z
Any hierarchical clustering method induces a dissimilarity measure on the observationsâ€”say, . Let be the cluster with the fewest members that contains both and . Assume was formed by joining and . Then define .
If the fusion of and reduces the number of clusters from g to , then define . Johnson (1967) shows that if
then is an ultrametric. A method that always satisfies this condition is said to be a monotonic or ultrametric clustering method. All methods implemented in PROC CLUSTER except CENTROID, EML, and MEDIAN are ultrametric (Milligan 1979; Batagelj 1981).