next up previous
Next: Proximity Matrix With Ties Up: Matrix Updating Algorithms Previous: Matrix Updating Algorithms

Johnson's Algorithm

Step 1
Begin with the disjoint clustering having level L(0) = 0 and sequence number m = 0.

Step 2
Find the least dissimilar pair of clusters in the current clustering, say pair (r), (s), according to

d[(r), (s)] = min d[(i),(j)]

where the minimum is over all pairs of clusters in the current clustering.

Step 3
Increment the sequence number : m = m +1. Merge clusters (r) and (s) into a single cluster to form the next clustering m. Set the level of this clustering to

L(m) = d[(r),(s)]

Step 4
Update the proximity matrix, D, by deleting the rows and columns corresponding to clusters (r) and (s) and adding a row and column corresponding to the newly formed cluster. The proximity between the new cluster, denoted (r,s) and old cluster (k) is defined as follows. For the single-link method.

d[(k), (r,s)] = min d[(k),(r)], d[(k),(s)]

For the complete-link method,

d[(k), (r,s)] = max d[(k),(r)], d[(k),(s)]

Step 5
If all objects are in one cluster, stop. Else, go to step 2.

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