Comparing classification tree structures: a special case of comparing q-ary relations

Irisa, Université de Rennes 1, Campus de Beaulieu, Avenue du General Leclerc, 35042 Rennes Cedex, France.

Received: April 1997

Abstract

Comparing q-ary relations on a set of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the context of a set theoretic representation of these relations. Formal and combinatorial computing aspects of a construction method for a very general family of association coefficients between relations are presented. The main purpose of this article is to specify the components of this construction, based on a permutational procedure, when the structures to be compared are classification trees.

Résumé

La comparaison des relations q-aires sur un ensemble d'objets élémentaires, est l'un des problèmes les plus fondamentaux de la classification et analyse combinatoire des données. La comparaison des structures d'arbres de classification (binaires ou non) est étudiée dans ce contexte en tenant compte de la spécificité de ces structures. Deux représentations mathématiques sont proposées. La première correspond à une relation binaire valuée et la seconde, à une relation 4-aire. Dans ces conditions, les approches les plus classiques de comparaison d'arbres, sont situées relativement à une représentation ensembliste de ces relations. Nous présentons les aspects du calcul formel et combinatoire, d'une méthode de construction, d'une famille très générale de d'association entre relations. L'objet principal de cet article consiste à spécifier les composantes de cette construction fondée sur un modèle permutationnel, quand les structures à comparer sont des arbres de classification.