Ultrametrics

The CLUSTER Procedure

Ultrametrics

A dissimilarity measure d(x,y) is called an ultrametric if it satisfies the following conditions:

d(x,x) = 0 for all x
$d(x,y) \geq 0$ for all x, y
d(x,y) = d(y,x) for all x, y
$d(x,y) \leq \max ( d(x,z) , d(y,z) )$ for all x, y, and z

Any hierarchical clustering method induces a dissimilarity measure on the observations, say h(x_i,x_j). Let C_M be the cluster with the fewest members that contains both x_i and x_j. Assume C_M was formed by joining C_K and C_L. Then define h(x_i,x_j) = D_KL.

If the fusion of C_K and C_L reduces the number of clusters from g to g - 1, then define D_(g) = D_KL. Johnson (1967) shows that if

$0 \leq D_{(n)} \leq D_{(n-1)} \leq ... \leq D_{(2)}$

then h(·,·) 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).

Chapter Contents
Previous
Next
Top