Weak hierarchies associated with similarity measures - An additive clustering technique (Q1116591)

A new useful and natural concept in cluster analysis is studied. Given a similarity measure on a set of subjects, a subset is regarded as a cluster if any two objects a,b inside this subset have greater similarity than any third object outside has to at least one of a,b. These clusters then form a closure system which can be described as a hypergraph without triangles. Conversely, given such a system, one may attach some weight to each cluster and then compose a similarity measure additively, by letting the similarity of a pair be the sum of weights of the clusters containing that particular pair. The original clusters can be reconstructed from the obtained similarity measure. This clustering model is thus located between the general additive clustering model of \textit{R. N. Shepard} and \textit{P. Arabie} [Psychol. Rev. 86, 87-123 (1979)] and the standard hierarchical model. Potential applications include fitting dendograms with few additional nonnested clusters and simultaneous representation of some families of multiple dendograms, as well as assisting the search for phylogenetic relationship by proposing a somewhat larger system of possibly relevant ``family groups'', from which an appropriate choice remains to be made. So, the basic theory of weighted weak hierarchies is developed and the relationship to the general additive clustering model is investigated. The paper concludes with three illustrative applications and a short discussion.