next up previous
Next: Practical Difficulties Up: Hierarchical Clustering Previous: Johnson's Algorithm

Proximity Matrix With Ties

Up to now, we have assumed that the proximity matrix contains no ties so that two new clusters are never formed at the same level and the algorithms defined thus far produce unique dendrograms. A tie implies that two or more edges are added to the proximity graph at once and that the minimum and maximum functions required in matrix updating are not unique.

The single-link method does not suffer from ambiguities due to ties because it has a continuity property. If the ties are broken in the proximities by adding or subtracting a small amount from the tied proximities, the resulting singly-link dendrograms will merge smoothly into the same dendrogram as the added amount tends to zero, no matter how the ties are broken. This statement applies to all single-link algorithms as long as the rank orders of the proximities are not changed by the added amounts. By contrast, several complete-link dendrograms can be obtained by breaking ties in this way.



Miranda Maria Irene
Thu Apr 1 15:43:18 IST 1999