Tuning a Major Part of a Clustering
Katherine M. Hansen, John W. Tukey · 1992
Summary Most proposals for clustering algorithms have been initially based on introspective selection of a criterion or an algorithm. Few proposed algorithms have had their performance under difficult circumstances, such as overlapping clusters, studied. Few, if any, have been developed in an evolutionary and exploratory manner. Our approach involves (a) striving to avoid comparing distances on remote parts of the data (because metrics deserve only minimum trust), and (b) using a stochastically-defined test bed to measure, and where possible understand, the performance of an evolving algorithm, with the intent of using our understanding to modify it, repeatedly, in such a way as to improve its performance. Our algorithms have evolved from a double-rank based modification of single-linkage clustering. Our test bed involves 3 circular Gaussian samples, of size 50 each, centered at the vertices of an equilateral triangle of side to. In its use we assume that a 3-group answer is being sought. Thus we are only concerned with a part of the clustering process. Our early algorithms begin to misbehave in the range 5 < t <7. Our successive steps of improvement work at smaller and smaller t. The last version we have tried still performs usefully (median misclassification about 16%) at t = 2.7, where complete knowledge of the three populations would only let us hold misclassification to a median of 13*3%. Comparison (by Kaye Basford) with a Gaussian maximum likelihood algorithm on the same set of triple samples shows only slightly better performance for that algorithm than for our algorithm. The steps of improvement are discussed. We believe empirically-motivated modification is likely to be important in other instances of algorithm selection.