PROC CLUSTER: Ultrametrics :: SAS/STAT(R) 9.22 User's Guide

The CLUSTER Procedure

Ultrametrics

A dissimilarity measure $\text{[math]}$ is called an ultrametric if it satisfies the following conditions:

$\text{[math]}$ for all $\text{[math]}$
$\text{[math]}$ for all $\text{[math]}$ , $\text{[math]}$
$\text{[math]}$ for all $\text{[math]}$ , $\text{[math]}$
$\text{[math]}$ for all $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$

Any hierarchical clustering method induces a dissimilarity measure on the observations—say, $\text{[math]}$ . Let $\text{[math]}$ be the cluster with the fewest members that contains both $\text{[math]}$ and $\text{[math]}$ . Assume $\text{[math]}$ was formed by joining $\text{[math]}$ and $\text{[math]}$ . Then define $\text{[math]}$ .

If the fusion of $\text{[math]}$ and $\text{[math]}$ reduces the number of clusters from $\text{[math]}$ to $\text{[math]}$ , then define $\text{[math]}$ . Johnson (1967) shows that if

$\text{[math]}$

then $\text{[math]}$ 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).

Top of Page