Three-way metric structures for data analysis

Bernard Fichet

Laboratoire de Biomathematiques
University of Aix-Marseille II

Most of procedures and visual displays in exploratory data analysis are based upon (two-way) metric structures or more generally dissimilarity structures. Classical examples an given by Euclidean distances in multidimensional scaling and ultrametric spaces in clustering.
Three-way dissimilarities may derive from usual dissimilarities by some formula. In this talk, we focus on transformations of Lp-type. For p=1, this is the so-called perimeter model.
Of course, three-way dissimilarities may also be defined intrinsically or directly from the data. As opposed to some recent papers, we assume here, that such dissimilarities are defined only on unordered triples of distinct units. In that case, it is of some interest to recognise whether a three-way dissimilarity is of perimeter type. To this end a six-point characterisation is established.
In our framework we also discuss axioms for metricity and ultrametricity. Some properties emphazize the relationship between those spaces and their corresponding two-way ones.
Embeddability in some structures, such as tree-structures are evoked in the same spirit. In particular, a five-point property characterizes three-way tree metrics of perimeter type.
Finally, some algorithms are given for approximating a three-way dissimilarity by a metric or an ultrametric. The criterion is quadratic for metricity and based on the infinity norm for ultrametricity.