The purpose of the paper is to put together the basic ideas of the theory of ordinal clustering, as developed by the first author et al. (1978), and the theory of probabilistic metric spaces, as developed by the second author et al. (1983). The principal result is a new theory of clustering, called percentile clustering, in which clustering is based, not on some average or other typical value of the data, but directly on the distributed data itself.
In the case of the Jardine-Sibson model [N. Jardine and R. Sibson, Mathematical Taxonomy, Wiley, N.Y. (1971)] this leads from dissimilarity coefficients (DC) to percentile dissimilarity coefficients (PDC) - and from a totally ordered set to a lattice. Each PDC determines a family of ordinary DC’s - one for each percentile c in [0,1]. A secondary outgrowth is a generalized theory of ordinal clustering. A number of algorithms that implement percentile clustering is presented.
The paper concludes by applying the new cluster methods to two concrete examples. The first of these is a data set concerning combat death in the Vietnam War; the second is a data set dealing with the classification of species of gibbons. In both instances results obtained with various standard clustering techniques are also presented.