A common and long-known form of iterative optimization
moves single observations from cluster to cluster in search of a
better clustering [Duda & Hart, 1973]. The basic strategy
has been used in one form or another
by numerous sort-based algorithms as well [Fisher et al., 1992].
The idea behind iterative * redistribution* [Biswas, Weinberg, Yang & Koller,
1991]
is simple: observations in a single-level clustering
are `removed' from their original cluster and resorted relative to
the clustering.
If a cluster contains only one observation,
then the cluster is `removed' and its single observation is resorted.
This process continues until two consecutive iterations yield
the same clustering.

The ISODATA algorithm [Duda & Hart, 1973] determines a target cluster for each observation, but does not actually change the clustering until targets for all observations have been determined; at this point, all observations are moved to their targets, thus altering the clustering. We limit ourselves to a sequential version, also described by Duda and Hart [1973], that moves each observation as its target is identified through sorting.

This strategy is conceptually simple, but is limited in its ability to overcome local maxima -- the reclassification of a particular observation may be in the true direction of a better clustering, but it may not be perceived as such when the objective function is applied to the clustering that results from resorting the single observation.

Douglas H. Fisher

Sat Mar 30 11:37:23 CST 1996