Classification and Dissimilarity Analysis

Classifying objects according to their likeness seems to have been, for all time, a step in the human process of acquiring knowledge. We could possibly find the beginning of this process as early as infancy, if we admit that the brain of a young child learns to distinguish categories of objects or persons (distinguishing one animal from another, his parents from strangers,…), or of situations (what is allowed from what is not) proceeding by analogies. Historically the scientific process, even when it is purely descriptive, works in the same way. We dominate well a domain when all its notions are classified and categorised. Such classifications show some relationships from which the exploration yields, in a second stage, improvements in the knowledge of the domain. Even far back in time, we find texts and authors who have shown organisation and clustering particularly in descriptions in the areas of botany or geology (Aristotle). Closer to us, the scientists of the “siècle des lumières” and their heirs introduced some famous classifications (A.L. de Jussieu, G. Cuvier, G. L. Buffon, C. von Linneaus,…). In the same way, we can find, outside natural science, various works in classification in the exact sciences (D.I. Mendeleïev,…), in astronomy or in linguistics (see Marcotorchino (1991) for an interesting historical presentation). The criteria of classification used are generally empirical ones: mammals are separated from nonmammals, vertebrates from non vertebrates,‖ In a modern context, this is equivalent to deriving a hierarchical clustering of objects (we use this generic name for individuals, or statistical units, Operational Taxonomic Units (OTU),…) using some variables which are introduced one after another in a given order.

We begin with a short overview of the whole domain of dissimilarity analysis. The contents of this particular paper are then summarised in Section 2.1.2.

The basic tool, in Statistics like in many branches of experimental sciences concerned with the study of information expressed in observations, is comparison analysis: in the field of statistical modelling, comparison to a theoretical model, in exploratory data analysis (EDA), comparison between data.

The primary objective of this and the following chapter is to show that one simple results unifies and generalises a number of familiar bijections in the mathematical classification literature. These include the classical bijections concerning ultrametrics on a finite set, obtained in Benzécri (1965), Hartigan (1967), Jardine, Jardine and Sibson (1967) and Johnson (1967), as well as their several later extensions reported in Jardine and Sibson (1971), Janowitz (1978), Barthélémy, Leclerc and Monjardet (1984) and the unpublished research report Critchley and Van Cutsem (1989).

In chapter 4 of this book, the simple but general Theorem 4.5.1 was established and shown to have a variety of important applications in mathematical classification. In particular, it was seen to unify and generalise four bijections reported in the literature concerning dendrograms and generalised dendrograms, numerically stratified clusterings and residual maps

The aim of this chapter is to present an ordinal model of valued objects, special cases of which appear in many contexts. The model lies on basic notions of ordered set theory: residuation or, equivalently, Galois connections; it is not new: explicitly proposed in fuzzy set theory by Achache (1982, 1988), it also underlies an order formalization of a Jardine and Sibson (1971) model given by Janowitz (1978; see also Barthélemy, Leclerc and Monjardet 1984a). Here, our main concern is to apply the model in order to obtain and study dissimilarities such as ultrametrics, Robinson or tree-compatible ones. Valued objects of other types, already considered in the literature, will be also given as examples: two types of valued non symmetric relations and two types of valued convex subsets. The chapter is neither a theoretical general presentation nor a detailed study of a few special cases. It is, tentatively, something between these extreme points of view. Some references are given to the reader interested to more details on a specific class of valued objects, or to more information about residuation (or Galois mappings) theory. In what follows, E will be a given finite set with n elements. Several families of combinatorial objects defined on E will be considered.

Let I denote a totally ordered set of n ≥ 1 elements. It is notationally convenient to identify I with the set of the first n integers or, on occasion, with the row vector (1,…,n). In the former case the order on I is embodied in the natural order on the reals, and in the latter case in the ordering amongst the elements of a vector

The use of the L ₁-norm via the least absolute deviations appeared early in the field of statistics. Generally people mention Boscovich (1757) and Laplace (1793), and for further historical aspects the reader will may consult Farebrother (1987). However, many periods of silence followed those pioneering works. There are many reasons for this lack of development. In particular, some computational difficulties arose in the city-block approaches. During the last two decades, we note a growing interest in statistical methods based upon the L ₁-norm. This phenomenon concerns many areas such as robustness, nonparametric analysis, multidimensional scaling. In this last field, dimensionality problems are crucial. This chapter is devoted to theoretical and computational results on the dimension of an L ₁-figure.