Michalski and Stepp's [Michalski & Stepp, 1983a] CLUSTER/2 seeks the optimal K-partitioning of data. The first step selects K random `seed' observations from the data. These seeds are `attractors' around which the K clusters are grown from the remaining data. Since seed selection can greatly impact clustering quality, CLUSTER/2 selects K new seeds that are `centroids' of the K initial clusters. Clustering is repeated with these new seeds. This process iterates until there is no further improvement in the quality of generated clusterings.
Ordering effects in sorting are related to effects that arise due to differing fixed-K seed selections: the initial observations in an ordering establish initial clusters that `attract' the remaining observations. In general, sorting performs better if the initial observations are from diverse areas of the observation-description space, since this facilitates the establishment of initial clusters that reflect these different areas. Fisher, Xu, and Zard [1992] showed that ordering data so that consecutive observations were dissimilar based on Euclidean distance led to good clusterings. Biswas et al. [1994] adapted this technique in their ITERATE system with similar results. In both cases, sorting used the PU score described previously.
This procedure presumes that observations that appear dissimilar by Euclidean distance tend to be placed in different clusters using the objective function. Taking the lead from CLUSTER/2, a measure-independent idea first sorts using a random data ordering, then extracts a biased `dissimilarity' ordering from the hierarchical clustering, and sorts again. The function of Table 1 outlines the reordering procedure. It recursively extracts a list of observations from the most probable (i.e., largest) cluster to the least probable, and then merges (i.e., interleaves) these lists, before exiting each recursive call -- at each step, an element from the most probable cluster is placed first, followed by an element of the second most probable, and so forth. Whatever measure guides clustering, observations in differing clusters have been judged dissimilar by the measure. Thus, this measure-independent procedure returns a measure-dependent dissimilarity ordering by placing observations from different clusters back-to-back.
Table 1: A procedure for creating a `dissimilarity' ordering of data.
Following initial sorting, we extract a dissimilarity ordering, recluster, and iterate, until there is no further improvement in clustering quality.
JAIR, 4