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 , 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.