Croisements, ordres et ultramétriques: Application à la recherche de consensus en classification automatique. (Crossings, orders and ultrametrics: Application of consensus research to automatic classification). (French) Zbl 0592.62051

Summary: One of the most important and difficult problems encountered in automatic classification is that of comparison of classifications. The problem arises when we want to compare the same set of objects characterized by several data arrays. For instance, a time-series of data arrays or data arrays each depending on a different set of variables. This problem also arises when we wish to study the effect of different coding transformations, different choices of dissimilarity indices, the robustness of classification obtained, etc.
The notion of crossing sheds new light in this framework. It allows us to relate the visual representation of a hierarchy and the notion of compatibility between an order and a dissimilarity index for which matrix characterizations are provided. The notion of Robinson matrix is extended; the ”semi-compatibility” between an order and a distance gives a new characterisation of chains which are minimum spaning trees; it is shown that the different times of compatibility are equivalent in the case of an ultrametric. The theoretical results provide simple and effective algorithms which facilitate the visual comparison of classifications and the study of consensus between them.


62H30 Classification and discrimination; cluster analysis (statistical aspects)