Israël-César César Lerman
email: lerman@irisa.fr

Facets of the set theoretic representation of categorical data

Keywords: Categorical attribute, Relational description, Category set, Preordonances and Taxonomies Attribut catégoriel, Description relationnelle, Ensemble de catégories, Préordonnances et Taxonomies

There are three basic notions in Data Analysis : object, category and descriptive attribute. Two description cases are of concern ; describing an object set O or describing a category set C. For the former case the set theoretic representation of a given attribute is defined with respect to O and for the latter, it is defined within each category of C. For these representations a given descriptive attribute is interpreted in terms of a relation with a given arity defined on the described set. We propose in this work a unique principle for the set theoretic representation of a descriptive attribute of different types : boolean, numerical, nominal categorical, ordinal categorical, preordonance categorical, taxonomic categorical and taxonomic preordonance categorical. The formal representations of these different types are explicited and compared in both cases : for an object set description and for a category set description. Then these representations are applied in interesting real examples.

Introduction

We show in this report how the set theoretic representation of descriptive attributes allows to cover a very large scope of data description in Data Analysis. For this representation the attributes are interpreted in terms of relations on the described object set. For a given descriptive attribute, the arity of the associated relation is defined by the structure endowing the value set of this attribute. A typology of the descriptive attributes based on the mentioned structure is proposed. In this typology the following types are defined : boolean, numerical, nominal categorical, ordinal categorical, preordonance categorical, taxonomic categorical and taxonomic preordonance categorical. We will study below these different types and we will mutually compare them. The categorical attributes will play a very important part in our analysis. A value of a categorical attribute is called "category". Conditions of exclusivity and exhaustivity are required for the different categories of a categorical attribute (see Section 3.1). A category is determined by the intuitive notion of "concept".

Formal definition, mathematically expressed, of a "concept" in real life is very difficult [START_REF] Sutcliffe | Concept, class, and category in the tradition of aristotle[END_REF] [START_REF] Sutcliffe | Concept, class, and category in the tradition of aristotle[END_REF]. It depends on a knowledge domain and on recognition techniques. For example, let us consider the cirrhosis concept defined in the hepatho-biliary pathology. For this pathology, we assume a universe U of liver ill persons. U is a real or hypothetical finite set and each of its elements defines an elementary and indivisible object interesting the domain studied. On a given element of U, the concept may be T RU E or F ALSE. A series of clinical tests are necessary in order to recognize if a given person is a cirrhosis ill. A concept is defined in "intension" (one can say in "comprehension") from a precise description using primitive concepts. It is detected by the domain expert for two reasons : first, its frequency is not negligible ; and second, its consequences are globally comparable on all the objects where it is observed.

Let us denote by γ such a concept, for example the "liver cirrhosis". γ is defined with respect to the universe U of the ill liver persons. γ is represented by the subset of U, that we denote by U(γ), whose disease is cirrhosis. Equivalently, a boolean attribute corresponds bijectively to the concept γ. This attribute, denoted by a γ , is a mapping of U onto the set {0, 1} comprising two codes 0 and 1 :

a γ : U → {0, 1} (1)
For a given u in U, a γ (u) = 1 (resp., 0) if γ is T RU E (resp., F ALSE) on u. In these conditions, the above subset U(γ) of U can be expressed as follows :

U(γ) = a -1 γ (1) (2)
where a -1 γ (1) is the reciprocal image of 1. U(γ) is called "extension" of the concept γ at the level of U. The introduced concept notion is boolean. However, its definition may require non-boolean attributes. Consider the following example taken in the framework of an epidemiological survey concerning a male adult population living in a given area and aged 18-60 years. The concept "smoking more than 20 cigarettes a day" is a boolean concept. Nevertheless, its definition requires a non-boolean attribute defined by "counting". The scale value of this attribute is the set of integer numbers.

The notion of a value scale associated with a descriptive attribute is preliminary to define descriptions in Data Analysis Suppes and Zinnes (1963) [START_REF] Suppes | Basic measurement theory[END_REF]. A given descriptive attribute a is defined at the level of a universe U of objects concerned by a set of concepts (see the above example where the concepts are those of the hepatho-biliary pathology). By denoting E the value scale of a, a is mathematically interpreted as a mapping of U in E, associating with each element u of U, a unique value in E denoted by a(u).

a : U → E u → a(u) (3)
a : O → E u → a(u) (4)
Now, let us define the scale E under the form E = {e 1 , e 2 , ..., e h , ..., e k } where e h is one possible value of the attribute a, 1 ≤ h ≤ k. The meaning of the studied field enables to define a structure on the value set E. This structure induces a mathematical relation on O. In Sections 2 and 3 we shall detail the different types of descriptive attributes and their formal representations at the level of the object set O. The main type of a descriptive attribute is defined from the arity of the relation on O, induced by the structure of the value set E. We distinguish three main types I, II and III. For I the induced relation on O is unary. It comprises the boolean attribute and the numerical one (Sections 2.1 and 2.2). For II, the relation is binary, non-valuated or valuated. This type includes the nominal categorical attribute (Section 3.1), the ordinal categorical attribute (Section 3.2), the ranking attribute (Section 3.3) and the categorical attribute valuated by a numerical similarity (Section 3.4). These two types (I and II) cover a large range of formal descriptions in combinatorial data analysis (see Sections 2, 3, 5 and 6). Type III is defined when the attribute scale induces a binary relation -generally defined by a ranking -on the set P 2 (O) (resp., O × O) of unordered (resp., ordered) pairs of elements of O. Then, the preordonance categorical attribute, the taxonomic attribute and the taxonomic preordonance attribute are presented in Sections 4.1, 4.2 and 4.3, respectively. In Section 4.4 preordonance representations of the different types of descriptive attributes are proposed. Section 4 is devoted for defining the representation of the different types of attributes when describing a set of categories instead of a set of objects.

Relational representation of descriptive attributes is clearly emphasized in our work. One of its specificities consists in highlighting the set theoretic representation sustaining the relational one [START_REF] Lerman | Les bases de la classification automatique[END_REF] [START_REF] Lerman | Les bases de la classification automatique[END_REF], (1973) [START_REF] Lerman | Étude distributionnelle de statistiques de proximité entre structures finies de même type ; application à la classification automatique[END_REF], (1981) [START_REF] Lerman | Classification et analyse ordinale des données[END_REF], (1992) [START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles[END_REF], [START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles, ii[END_REF] and (2009) [START_REF] Lerman | Analyse de la vraisemblance des liens relationnels une méthodologie d ' analyse classificatoire des données[END_REF]. In our work we were very influenced by the M.G. Kendall work Kendall (1948) [START_REF] Kendall | Rank correlation methods[END_REF]. Several authors in Combinatorial Data Analysis interpret, implicitly or explicitly, the representation of a descriptive attribute of an object set O in terms of of a binary relation on O. This is generally done for a given type of descriptive attribute [e.g. nominal (resp., ordinal) categorical attribute], in relation with a specific method to be developed Guénoche and Monjardet (1987) [START_REF] Gu Énoche | Méthodes ordinales et combinatoires en analyse des données[END_REF], [START_REF] Hubert | Assignment methods in combinatorial data analysis[END_REF] [START_REF] Hubert | Assignment methods in combinatorial data analysis[END_REF], [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF] [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF], [START_REF] Marcotorchino | Essai de typologie structurelle des indices de similarité vectoriels par unification relationnelle[END_REF] [START_REF] Marcotorchino | Essai de typologie structurelle des indices de similarité vectoriels par unification relationnelle[END_REF], [START_REF] Giakoumakis | Coefficients d ' accord entre deux préordres totaux[END_REF] [START_REF] Giakoumakis | Coefficients d ' accord entre deux préordres totaux[END_REF], Régnier (1965) [START_REF] Égnier | Sur quelques aspects mathématiques des problèmes de la classification automatique[END_REF]. In the following, we wish to present a general framework independent of a given methodology, in which the different types of decriptive attributes and their formal representations will be expressed.

Representation of the attributes of type I

As mentioned above, an attribute of type I induces a unary relation on O. Such an attribute can be called an "incidence" attribute. For this type we distinguish exactly the "boolean" attribute and the "numerical" one.

The boolean attribute

This attribute is also called a "presence-absence" attribute. It has been already considered above in Section 1. As previously, let us denote it by a. Formally, a is a mapping of O onto the set {F ALSE, T RU E}. Mostly, in Data Analysis, F ALSE and T RU E are coded by the integer numbers 0 and 1, respectively. For the following mapping diagram, also considered above in a different context,

a : O → {0, 1} x → a(x) (5)
a(x) denotes the value of a on x, a(x) = 1(resp., 0) if a is T RU E (resp., F ALSE) for x. a is represented by the subset O(a) of O constituted by the objects for which a is T RU E :

O(a) = a -1 (1) (6)
where a -1 denotes the reciprocal mapping of a. Now, let us introduce the cardinalities of O and O(a) that we denote by n and n(a) : n = card(O) and n(a) = card(O(a)). Thus, the proportion or relative frequency p(a) of objects for which a is T RU E is defined by p(a) = n(a)/n.

The negated boolean attribute ā is defined by (∀x ∈ O), ā(x) = T RU E if and only if a(x) = F ALSE [START_REF] Ghazzali | Comparaison et réduction d ' arbres de classification, en relation avec des problèmes de quantification en imagerie numérique[END_REF] Clearly, with ā, is associated O(ā), which is the complementary subset of O(a) in O. We can also define n(ā) = card(O(ā)) and p(ā) = n(ā)/n. Trivially, we have p(a) + p(ā) = 1.

The couple {a, ā} is the value set of a binary catégorical attribute. Let us denote this attribute by α. The empirical distribution of α is defined by the ordered pair [p(a), p(ā)].

Thus, with logically independent boolean attributes1 , binary categorical attributes can be associated. Conversely, with categorical binary attributes, boolean attributes can be associated by retaining for each binary categorical attribute, one of its two possible values. Generally and for significance statistical reasons, the retained value is the least frequent among the both values.

Boolean attributes occur very frequently in database descriptions. For the above example in Section 1 where O is defined by a sample of liver ill persons, the concept of liver cirrhosis specifies a boolean attribute.

The numerical attribute

The value scale of a numerical attribute is the set R of real numbers. Mostly, in Data Analysis, numerical descriptions are considered for measuring quantities (e.g. weight, size, ...). In these conditions, we shall assume a positive scale including 0 for the numerical attribute. In any case, this does not restrict the generality. Indeed, by representing geometrically R with an horizontal axis directed from left to right, the scale origin can be moved to left in order to make positive the observed values of the numerical attribute on the object set O. Let us denote by v the numerical attribute. v is a mapping of O on the set that we denots by R + of real positive numbers

v : O → R + (8)
associating with each object o of O, a positive real number v(o)

(∀o ∈ O) o → v(o) (9)
v is interpreted as a valuated unary relation :

{v(o)|o ∈ O} (10)
Thereby, boolean attribute and numerical attribute are considered at the same relational level. Indeed, their extensions are represented in a set theoretic way at the level of the object set O : a subset of O for the boolean attribute, and a numerical valuation on O for the numerical attribute.

Taking into account the accuracy of measurement, the scale of decimal positive numbers is largely sufficient for defining a numerical attribute in data analysis. Therefore, by denoting D + the latter scale, D + can be substituted for R + in the right member of 8.

As mentioned above, generally and more specially in Data Mining the size of the object set O is very large. Consequently, the size of the reached values by v on O is much smaller than the cardinality of O. Let us designate by

[x (1) , x (2) , ..., x (l) , ..., x (m) ] (11)
the increasing ordered sequence of the reached values by v on O (m < n) and introduce the subset

O l = v -1 (x (l) ) constituted by all objects whose v value is x (l) , 1 ≤ l ≤ m. Denote n l = card[O l ], 1 ≤ l ≤ m. The empirical distribution of v on O is defined by the sequence (x (l) , f l ) ( 12
)
where f l = n l /n, f l defines the relative frequency (proportion) of objects whose v value is x l , 1 ≤ l ≤ m.

As an example, let us consider the following increasing sequence of a numerical attribute v on a set of 10 objects

Thus, there are m = 7 distinct values.

In the geometrical methods of data analysis, a numerical attribute is represented by a linear form. This gives the projection measurement on a linear axis endowed with an origin and a unit vector. To fix idea, we can assume an horizontal axis. In these conditions, a given object o is represented by a point of the axis whose abscissa is v(o). By considering the sequence [START_REF] Hubert | Assignment methods in combinatorial data analysis[END_REF] of the v values, n l distinct objects are represented by the same point that we denote by M l , whose abscissa is x l , 1 ≤ l ≤ m. A graphical representation, called "histogram" is obtained by drawing from each point M l , 1 ≤ l ≤ m, an ascendant vertical segment whose length is proportional to the relative frequency f l , 1 ≤ l ≤ m. Thus we obtain for the distribution (13) (see In terms of factorial analysis the sequence

(M l , f l ) (14)
defines one dimensional cloud of points where the point M l is endowed with the positive numerical value f l , the latter being interpreted as a weight, 1 ≤ l ≤ m.

This structure was exploited in image scalar quantization [START_REF] Ghazzali | Comparaison et réduction d ' arbres de classification, en relation avec des problèmes de quantification en imagerie numérique[END_REF] [START_REF] Ghazzali | Comparaison et réduction d ' arbres de classification, en relation avec des problèmes de quantification en imagerie numérique[END_REF], Ghazzali, Léger and Lerman (1994) [START_REF] Ghazzali | Rôle de la classification statistique dans la compression du signal image : panorama et une étude spécifique de cas[END_REF].In this application the concerned numerical attribute v is the luminance for which a scale of 256 grey levels, from 0 to 255, is established : 0 for the black and 255 for the blank. Here, the object set O is defined by the image pixels. Thus, for a squared image comprising 512 rows and 512 columns, the object set O includes n = 512 × 512 = 262144 elements. The one dimensional cloud [START_REF] Lafaye | Une méthode de discrétisation de variables continues[END_REF] has at most 256 points. It can be put in the following form :

{(l, f l )|0 ≤ l ≤ 255} ( 15
)
where f l = n l /n is the proportion of image pixels whose luminance is l, 0 ≤ l ≤ 255.

Defining a categorical attribute from a numerical one

As seen above, in the framework of the attributes of general type I, corresponding to a unary relation on the object set O, we distinguish two cases (see Sections 1 and 2). The first one is defined by the boolean attribute. The scale value of the latter is the poorest one. The second one is defined by the numerical attribute. Its scale value is the richest one.

There are several reasons for transforming a numerical attribute into a categorical one. One important reason may be to make homogeneous the description of the object set O. Indeed, imagine that the vast majority of the description is provided by categorical attributes. To fix idea, we assume a small number of categories by categorical attribute. In addition, suppose that few descriptive attributes are numerical. In these conditions it might be appropriate to transform the numerical attributes into categorical ones (see the following Sections 3.1 and 3.2). Another important reason related to the above first one, consists in retaining from the numerical value v(o) of v on the object o, what can be significant in this value. In fact, knowing the exact value v(o) might be less interesting than knowing that v(o) is located inside a given interval. Indeed, in order to categorize a numerical attribute, its interval variation is divided into subintervals.

Precisely, regarding the sequence [x (1) , x (2) , ..., x (l) , ..., x (m) ] (see equation ( 11)), let us denote here by a, x (1) and by b, x (m) + ǫ, where ǫ is an arbitrary small positive number. Therefore, the attribute v takes its values in the interval [a, b[= {x|x ∈ R + , a ≤ x < b, where, as above, R + denotes the real positive numbers. An increasing sequence, denoted by σ : σ = (y 0 = a, y 1 , ..., y k , y k+1 , ..., y l = b) [START_REF] Lerman | Directed binary hierarchies and directed ultrametrics[END_REF] defines a subdivision of the interval [a, b[ into a sequence of l subintervals

[y k , y k+1 [|0 ≤ k ≤ l -1 (17)
With each subinterval [y k , y k+1 [, 0 ≤ k ≤ l -1, is associated a category of a categorical attribute (see Section 3). By denoting c k the category representing the interval [y k , y k+1 [, 0 ≤ k ≤ l -1, c k is defined by the following boolean attribute

(∀o ∈ O), c k (o) = 1(resp. 0) iff v(o) ∈ [y k , y k+1 [(resp. v(o) / ∈ [y k , y k+1 [) (18)
Now, the fundamental question is "How to define the subdivision σ ?"

There are a large variety of methods depending each on a given type of purpose. The simplest and the most direct one consists in defining σ by dividing the entire interval

y k+1 = y k + L l (19)
Collection des Publications Internes de l'Irisa c IRISA 0 ≤ k ≤ l -1. Notice that for a given practical application this technique requires an adequate value of l. On the other hand, for this technique, the statistical distribution of the attribute v on the object set O is not taken into account at all.

Another simple technique consists in interval division with as equal frequencies as possible. A given interval will be written [x i , x i ′ [ where i ′ > i and where n i + ... + n i ′ is adjusted to be as close as possible the ratio n/l. For this solution, in order to be consistent with the statistical distribution of the attribute v, we have also to determine in a non-arbitrary way an adequate value of l.

None of both previous techniques respect intimately the heterogeneity of the statistical distribution of v. Nevertheless, it might exist subintervals of [a, b[ such that two consecutive and near values of these, have comparable and high frequencies. Discovering such subintervals leads to the definition of "significant" categorical attribute (see equation [START_REF] Lerman | Étude distributionnelle de statistiques de proximité entre structures finies de même type ; application à la classification automatique[END_REF]). Thus in Figure 2 we recognize intuitively five subintervals.

[x [START_REF] Anderberg | Cluster Analysis for Applications[END_REF] [

[ [ [ x (m) [ Fig. 2 -Histogram-2
These subintervals correspond to high concentration zones. Precisely, clustering methods enable the discovering of such subintervals. In these latter methods an objective criterion is optimized, locally or globally.

The interest of the well known Fisher method Fisher(1958) [START_REF] Fisher | On grouping with maximum homogeneity[END_REF] is to maximize globally the inter-cluster inertia in case where the number of clusters is fixed. Each cluster is represented by an interval of the sought subdivision. The method is based on a dynamic programming algorithm. [START_REF] Lafaye | Une méthode de discrétisation de variables continues[END_REF] [START_REF] Lafaye | Une méthode de discrétisation de variables continues[END_REF] analyzed and made effective a graphical method that we suggested the general idea. Let us consider the number of observations in a small interval window having a fixed length. This number defines a kind of "local density". By moving the window from left to right along the variation range of v, we can determine the stable minima of this local density. This stability is obtained by varying in a suitable fashion the length of the window interval. The stable local minima define the cut points of the sought subdivision. For this method the number of the subdivision intervals is not fixed. It is a resulting of the employed algorithm. This method shown to be particularily effective for the treatment of small samples Kerjean(1978) [START_REF] Kerjean | Tentative d'établissement de 100 typologies d'examens biologiques. Contribution à l'établissement du système[END_REF]. In his paper [START_REF] Lafaye | Une méthode de discrétisation de variables continues[END_REF] Lafaye gives a brief and interesting synthesis on the dicretization of numerical attributes, With this respect, see also [START_REF] Rabaseda | Discretization of continuous attributes : a survey of methods[END_REF] [START_REF] Rabaseda | Discretization of continuous attributes : a survey of methods[END_REF].

In vector quantization (see the above example at the end of Section 2, considered in scalar quantization) Ghazzali (1992) [START_REF] Ghazzali | Comparaison et réduction d ' arbres de classification, en relation avec des problèmes de quantification en imagerie numérique[END_REF], Ghazzali, Léger and [START_REF] Ghazzali | Rôle de la classification statistique dans la compression du signal image : panorama et une étude spécifique de cas[END_REF] [START_REF] Ghazzali | Rôle de la classification statistique dans la compression du signal image : panorama et une étude spécifique de cas[END_REF] hierarchical ascendant (or agglomerative) clustering was applied. Two methods were employed : the Likelihood Linkage Analysis method [START_REF] Lerman | Likelihood linkage analysis (lla) classification method (around an example treated by hand)[END_REF] [START_REF] Lerman | Likelihood linkage analysis (lla) classification method (around an example treated by hand)[END_REF] and the classical Ward method [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF] [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF]. In this case and for coding compression purpose the order of the number of clusters is given (for example 16). Preliminary, it is established that each step of the agregation algorithm joins two consecutive intervals of [START_REF] Hubert | Assignment methods in combinatorial data analysis[END_REF] obtained previously as clusters in the hierarchical process. A method of detecting the most consistent levels of a classification tree (see Chapters 4 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF] and [START_REF] Lerman | Likelihood linkage analysis (lla) classification method (around an example treated by hand)[END_REF]) allows to obtain the wished subdivision.

A non-hierarchical dynamic and adaptative clustering method in the spirit of the K-means one, can also be applied in order to determine a subdivision σ. The method built by A. [START_REF] Schroeder | Analyse d ' un mélange de distributions de même type[END_REF] [START_REF] Schroeder | Analyse d ' un mélange de distributions de même type[END_REF] is based on a statistical criterion having a probabilistic nature : the likelihood classifying criterion.

For this criterion the observed cloud of points -one dimensional in our case -is considered as provided from a mixing of probability laws, having distinct modes and distinct probability occurences, respectively, [START_REF] Symons | Clustering criteria and multivariate normal mixture[END_REF] [START_REF] Symons | Clustering criteria and multivariate normal mixture[END_REF]. [START_REF] Celeux | Comparison of the mixture and the classification maximum likelihood in cluster analysis[END_REF] [START_REF] Celeux | Comparison of the mixture and the classification maximum likelihood in cluster analysis[END_REF] employ a stochastic algorithm for separating the entire cloud into subclouds corresponding each to one of the probability laws. This separation enables to detect an ordered sequence of intervals dominated each by one of the probability laws. And then, a subdivision σ of the variation range of v can be deduced. This approach may lead to fine and sophisticated techniques. However, these assume probabilistic conditions on the shapes of the probability laws, difficult to validate in general. On the other hand, these methods may seem conceptually too heavy for the submitted problem of discretization of an observed numerical attribute.

Representation of the attributes of type II

As mentioned in Section 1, an attribute of type II induces a binary relation on O. In this section we shall consider three sub-types of attributes. The nominal categorical attribute, the ordinal categorical attribute and the categorical attribute valuated by a numerical similarity.

The nominal categorical attribute

π = {O 1 , O 2 , ..., O h , ..., O k } (21)
where O h is defined by c -1 (c h ) that is the reciprocal image of c h , 1 ≤ h ≤ k. It is easier and without loss of generality to assume this partition defined with labelled classes. Different expressions will be used for expressing O h : O h is the set of objects where c h is T RU E, having the category c h , belonging to the category c h , ..., 1 ≤ h ≤ k.

With the partition π we associate the sequence (n 1 , n 2 , ..., n h , ..., n k ) of its cardinality classes ; n h = card(O h ), 1 ≤ h ≤ k. This sequence defines the type of the partition π. We also associate the sequence of proportions or relative frequencies (f 1 , f 2 , ..., f h , ..., f k ), where f h = n h /n. This sequence defines the statistical distribution of c on O.

The mapping [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF] can be viewed as the representation of the nominal categorical attribute c at the level of the object set O. It assigns to each elementary object o its value c(o), which is a nominal code. It is important to realize that this representation does not allow to compare directly two different nominal categorical attributes by comparing directly their respective values. Indeed, given two nominal categorical attributes c and c ′ we cannot compare directly the statistical distributions of c and c ′ on O. This comparison requires to cross the two respective partitions induced by c and c ′ .

There are different alternatives to carry out this comparison (see Chapter 4 of [START_REF] Anderberg | Cluster Analysis for Applications[END_REF] and Chapter 2 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF]). That we adopt requires a higher representation level. By noticing that representing a categorical attribute c is equivalent to represent the associated partition π, we define the following binary relation P π :

(∀(x, y) ∈ O × O), xP π y iff ∃h, 1 ≤ h ≤ k, s.t. x ∈ O h and y ∈ O h (22)
This binary relation is an equivalence relation (reflexive, symmetrical and transitive relation). Its symmetry and reflexive properties allow a representation at the level of the set, that we designate by

P P = {{x, y}|x ∈ O, y ∈ O, x = y} (23)
of unordered object pairs. P is exactly the set P 2 (O) of all subsets with 2 elements of O. Another notation we consider for P 2 (O) is O {2} . Two related representations denoted by R(π) and S(π) can be considered :

R(π) = {x, y} ∈ P 2 (O)|∃h, 1 ≤ h ≤ k, x ∈ O h and y ∈ O h (24)
and

S(π) = {x, y} ∈ P 2 (O)|∃g = h, 1 ≤ g, h ≤ k, x ∈ O g and y ∈ O h (25)
With R(π) and S(π) are naturally associated their indicator functions that we denote by ρ π and σ π , respectively :

(∀{x, y} ∈ P ), ρ π ({x, y}) = 1(resp., 0) iff {x, y} ∈ R(π)(resp., / ∈ R(π)) (26)
and

(∀{x, y} ∈ P ), σ π ({x, y}) = 1(resp., 0) iff {x, y} ∈ S(π)(resp., / ∈ S(π)) (27)
The 1 and 0 values represent the logical values T RU E and F ALSE respectively. The interpretation where 1 and 0 are integer values can also be considered. In the latter case (∀{x, y} ∈ P ), ρ π ({x, y}) + σ π ({x, y}) = 1 [START_REF] Lerman | Comparaison entre deux indices pour l'évaluation probabiliste discriminante des règles d ' association[END_REF] Indeed, {R(π), S(π)} defines a bi-partition of P , that is to say a partition of P into two classes. R(π) [resp.,S(π) ] is the set of joined (resp. separated) distinct object pairs, by π.

The expressions of R(π) and S(π) with respect to the partition classes (see equation ( 21)) are respectively

R(π) = 1≤h≤k P 2 (O h )
and

S(π) = 1≤g<h≤k O g ⋆ O h (29)
In these expressions the sign Σ means a union of disjoint subsets. P 2 (O h ) is the set of unordered pairs of elements of O h , or equivalently, the set of all 2-subsets of

O h , 1 ≤ h ≤ k. O g ⋆ O h designates the set of all unordered pairs {x, y} such that x ∈ O g and y ∈ O h , 1 ≤ g = h ≤ k. We have card[R(π)] = 1≤h≤k n h × (n h -1)/2 and card[S(π)] = 1≤g<h≤k n g × n h (30)
The following formula can be verified

Collection des Publications Internes de l'Irisa c IRISA card[R(π)] + card[S(π)] = n × (n -1)/2 (31)
where the left member is the cardinality of P = P 2 (O) (see equation [START_REF] Lerman | Likelihood linkage analysis (lla) classification method (around an example treated by hand)[END_REF]). Now, let us consider an example given in [START_REF] Goodman | Measures of association for cross classifications[END_REF] [START_REF] Goodman | Measures of association for cross classifications[END_REF] and where the origin of the data is specified. The population is defined by white Protestant married couples living in Indianapolis, married in 1927, 1928, or 1929. Thus, each elementary element u of our universe U is defined by such a married couple. The data sampling leads to an object set O comprising 1438 elements. One categorical attribute c defined is the "highest level of formal education of wife". Three categorical values are considered. We take them as following -c 1 = "less than three years high school" ; -c 2 = "3 or 4 years high school" ; -c 3 = "one year college or more". The partition π (see equation ( 21)) includes here three classes O 1 , O 2 and O 3 , where O 1 , O 2 and O 3 are the subsets of married couples whose formal education of wife are c 1 , c 2 and c 3 , respectively. We have according to the above notations,

n 1 = card[O 1 ] = 591, n 2 = card[O 2 ] = 608 and n 3 = card[O 3 ] = 239. P 2 (O) is the set of unordered pairs of distinct married couples. card[P 2 (O)] = 1438 × 1437/2 = 1033203. P 2 (O h ) is the set of unordered pairs of distinct married couples whose formal education of wife is c h , 1 ≤ h ≤ 3. -card[P 2 (O 1 )] = 591 × 590/2 = 174345 ; -card[P 2 (O 2 )] = 608 × 607/2 = 184528 ; -card[P 2 (O 3 )] = 239 × 238/2 = 28441.
Equations ( 29) and [START_REF] Lerman | Classification en présence de variables préordonnances taxonomiques à choix multiple. application à la structuration des phlébotomes de la Guyane Française[END_REF] give

card[R(π)] = 174345 + 184528 + 28441 = 387314 O g ⋆ O h
is the set of unordered pairs of married couples whose formal education of wives are c g and c h , respectively, 1 ≤ g < h ≤ 3.

-

card[O 1 ⋆ O 2 ] = card(O 1 ) × card(O 2 ) = 591 × 608 = 359328 ; -card[O 1 ⋆ O 3 ] = card(O 1 ) × card(O 3 ) = 591 × 239 = 141249 ; -card[O 2 ⋆ O 3 ] = card(O 2 ) × card(O 3 ) = 608 × 239 = 145312.
Equations ( 29) and [START_REF] Lerman | Classification en présence de variables préordonnances taxonomiques à choix multiple. application à la structuration des phlébotomes de la Guyane Française[END_REF] give

card[S(π)] = 359328 + 141249 + 145312 = 645889
We immediatly verify the equation ( 31) :

387314 + 645889 = 1033203

The ordinal categorical attribute

As in [START_REF] Goodman | Measures of association for cross classifications[END_REF] [START_REF] Goodman | Measures of association for cross classifications[END_REF], we assume in the above example a total (i.e ; linear) order on the category set {c 1 , c 2 , c 3 } for the categorical attribute c defined by the "Highest level of formal education of wife". We adopt the total order :

c 1 < c 2 < c 3
More generally, by considering the formalism introduced in Section 3.1 (see equation ( 20)), for an ordinal version of the categorical attribute c, the category set C is provided by a strict total order ; that is to say, a ranking on C. By supposing h the rank of the category c h , 1 ≤ h ≤ k, the latter total order is defined by

c 1 < c 2 < ... < c h < ... < c k (32)
This structure induces a total preorder on the object set O that we denote by ω. By defining, as in Section 3.1,

O h = c -1 (c h ), 1 ≤ h ≤ k, we have O 1 < O 2 < ... < O h < ... < O k ( 33
)
Collection des Publications Internes de l'Irisa c IRISA and that means : for any (x, y) in the cartesian product O g × O h , c(x) < c(y) if and only if g < h, 1 ≤ g < h ≤ k. The above total order on the set of classes O 1 , O 2 , ..., O h , ..., O k is called the quotient order associated with ω. Given a total preorder on O consists of given a partition on O and, additionally, a total order on its classes. This mathematical expression formalizes the notion of a "ranking with ties" given in Kendall (1948) [START_REF] Kendall | Rank correlation methods[END_REF]. Now, the ordered sequence of the cardinal classes (n 1 , n 2 , ..., n h , ..., n k ), denoted as in Section 3.1, is called here composition of the total preorder ω. The statistical distribution of c on O has the same meaning as for the nominal case (Section 3.1). It is defined by (f 1 , f 2 , ..., f h , ..., f k ), where

f h = n h /n, 1 ≤ h ≤ k.
Nevertheless, the labelling of the different classes satisfies here the linear order [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations ii[END_REF].

As for the nominal categorical attribute and in spite of the linear order defined on the category set C = {c 1 , c 2 , ..., c h , ..., c k } the formal valuation on O defined by [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF] does not allow the comparison between ordinal categorical attributes (see Sections 2.3.2, 2.3.4 and 2.4). As discussed in Section 3.3 a ranking attribute defining a linear order on the object set can be interpreted as a very specific case of an ordinal categorical attribute. However, the ranking function has a clear numerical interpretation and this enables one version of the comparison between two ranking attributes defining respectively two specific numerical valuations on the object set O.

In order to make possible the comparison between two ordinal categorical attributes in the most general case (see Chapter 2 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF]) let us define the following binary relation R ω associated with the ordinal categorical attribute c :

(∀((x, y) ∈ O × O)), xR ω y iff c(x) < c(y) (34)
Because of no symmetry and no reflexivity of R ω , we consider the following representation set

C = {(x, y)|x ∈ O, y ∈ O, x = y} (35)
In other words, C is the set of all ordered pairs of distinct objects from O. Another notation we consider for C is C [2] . In C, R ω is represented by the following subset

R ω = {(x, y) ∈ C|xR ω y} (36)
More explicitly R ω can be put in the following form

R(ω) = 1≤g<h≤k O g × O h ( 37
)
where Σ designates a union of disjoint subsets and where O g × O h is the cartesian product of O g and O h . C can be decomposed as follows

C = R(ω) + E(ω) + S(ω) (38)
where

E(ω) = 1≤h≤k O [2] h and S(ω) = 1≤g<h≤k O h × O g (39)
The cardinalities of the three components of c (see equation [START_REF] Ph | Méthodes de classification hiérarchique et problèmes de structuration et de recherche d ' informations assistée par ordinateur[END_REF]) are, respectively

Collection des Publications Internes de l'Irisa c IRISA card[R(ω)] = 1≤g<h≤k n g × n h card(E(ω)) = 1≤h≤k n h × (n h -1) card(S(ω)) = 1≤g<h≤k n h × n g (40)
Clearly,

card[R(ω)] = card(S(ω)) (41)
on the other hand, we can verify the formula

card[R(ω)] + card(E(ω)) + card(S(ω)) = n × (n -1) (42)
Let us retake the above example in its ordinal version :

c 1 < c 2 < c 3 . We have card[R(ω)] = 591 × 608 + 591 × 239 + 608 × 239 = 359328 + 141249 + 145312 = 645889 card(E(ω)) = 591 × 590 + 608 × 607 + 239 × 238 = 348690 + 369056 + 56882 = 774628
In these conditions, we verify the equation [START_REF] Spearman | The proof and measurement of association between two things[END_REF] where the right member is equal to 1438 × 1437 = 2066406. With R(ω) is naturally associated its boolean indicator function that we denote by ρ ω :

(∀(x, y) ∈ C), ρ ω (x, y) = 1(resp., 0) iff (x, y) ∈ R(ω)(resp., / ∈ R(ω)) (43)
As above (see what follows the equations ( 26) and ( 27)), 1 and 0 are interpreted as the logical values T RU E and F ALSE, respectively. However, the interpretation where 1 and 0 are numerical scorings can be taken into account. In his work Kendall (1948) [START_REF] Kendall | Rank correlation methods[END_REF] uses a scoring numerical function with two values +1 and -1 in order to code a total order (ranking) R(ω) on an object set O, coded itself by means of a given ranking R. More clearly, for the R ordered pair (x, y) such that xRy, the scoring value is +1 (resp.,-1) if xR ω y (resp., yR ω x). The value +1 (resp., -1) indicates that (x, y) ∈ R(ω) (rep., (y, x) ∈ R(ω)) (see equation [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF]).Thus, our set theoretic representation is equivalent to the Kendall coding of a ranking. However, for our representation the initial ranking R is useless.

The set representation of the ordinal categorical attribute c by R(ω) (see equation ( 36)) does not take into account explicitly the set of ordered pairs (x, y) of distinct objects such that x and y belong to the same class 38) and [START_REF] Rabaseda | Discretization of continuous attributes : a survey of methods[END_REF]. However, due to (38) E(ω) is implicitly taken into account. Indeed, E(ω) is deduced from R(ω). In order to weight the part of E(ω), the attribute c can be represented by the following numerical scoring function denoted score ω :

O h c(x) = c(y) = h, 1 ≤ h ≤ k. This set is denoted by E(ω) in equations (
score ω (x, y) =    1 if (x, y) ∈ R(ω) 0.5 if (x, y) ∈ E(ω) 0 if (x, y) ∈ S(ω) (44)
Collection des Publications Internes de l'Irisa c IRISA

Let us now consider the more general case where the category set C = {c 1 , c 2 , ..., c h , ..., c k } is provided by a strict partial order. An instructive exercise we propose to the reader consists in taking up again the above set representation formalism for this general case. For our part, we reconsider the above example of the categorical attribute "Highest level of formal education of wife" where we only assume c 1 < c 2 and c 2 < c 3 for the categorical values (see above). Therefore, c 1 and c 2 are considered no comparable. This categorical scale induces a partial preorder on the object set O, defined here by married couples. As above, denote ω this partial preorder. The expression of R(ω), E(ω) and S(ω) (see equations 37, 38 and 39) become

R(ω) = O 1 × O 3 + O 2 × O 3 E(ω) = O [2] 1 + O [2] 2 + O [3] 1 + O 1 × O 2 + O 2 × O 1 S(ω) = O 3 × O 1 + O 3 × O 2 (45)
where the sign + indicates a set sum defined by a union of disjoint subsets.

The scoring function defined in ( 44) is appropriate to code the partial strict order ω.

The ranking attribute

In his book Kendall (1948) [START_REF] Kendall | Rank correlation methods[END_REF] uses the ability in a given subject taught (e.g. mathematics) to rank totally and strictly the described object set O. Thus, a linear order that we denote by ω l is induced on O. For this two conditions must be satisfied : (i) the cardinality of O is enough small ; (ii) the scoring function is enough discriminating. The ranking attribute r is a bijective mapping of O on the set of the first n integer numbers :

r : O → {1, 2, ..., i, ..., n} (46)
associating with a given object x of O, its rank defined as follows :

(∀x ∈ O), x → r(x) = card{y|y ∈ O and y ≤ x for ω l } (47)
By using the rank function r, the representation of the ranking attribute would have been considered in the framework of descriptive attributes of type I. Indeed, r defines a numerical valuation on the set O, given by the first n integer numbers. In fact, this coding of a linear order leads to the Spearman coefficient [START_REF] Spearman | The proof and measurement of association between two things[END_REF] [START_REF] Spearman | The proof and measurement of association between two things[END_REF]. But, as expressed in the preceding Section 3.2 the originality of the Kendall representation is the level O × O of its definition. In fact, a ranking attribute can be seen as a very particular case of an ordinal categorical attribute. For this, each class of the induced total order on O becomes a singleton (i.e. comprises exactly one element) (see equation [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations ii[END_REF]). The representation set R(ω) (see equation [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF]) becomes

R(ω l ) = {(x, y)|(x, y) ∈ O × O and r(x) < r(y)} (48)
where r(x) < r(y) is equivalent to x ≤ y and not y ≤ x for ω l . We have

card[R(ω l )] = n × (n -1) 2 (49)
The "mean rank" function is an extension of the rank function (see equation ( 47)) employed to code a total preorder (ranking with ties) on an object set O. For the total preorder ω considered in [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations ii[END_REF], the mean rank function, denoted r m , is defined as follows

(∀h, 1 ≤ h ≤ k), (∀x ∈ O h ), r m (x) = n 1 + n 2 + ... + n h-1 + 1 2 × (n h + 1) (50)
where n g = card(O g ), 1 ≤ g ≤ h. The expression "mean rank" is explained by the fact that the mean rank of an arbitrary element x of O h , over all the linear orders compatible with the total preorder ω, is given by r m (x). The following formula is easy verify

x∈O r m (x) = n × (n + 1) 2 (51)
In these conditions, a total preorder ω on O and then, an ordinal categorical attribute describing O can be represented as a particular numerical valuation on O, given by the mean rank function r m . However the nature of this representation is very different from the relational one defined by R(ω) (see equation [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF]). Indeed, the latter representation is logical. It gives for a given ordered pair (x, y) in O × O, a logical value.

For the above mentioned reasons, a ranking attribute inducing a linear (total and strict) order on O cannot occur in case of the description of large data sets. However, a realistic case where such a description occurs, concerns the problem of m rankings Kendall (1948) [START_REF] Kendall | Rank correlation methods[END_REF]. Let us imagine a few number of objects : n = card(O) is relatively small. O is for example a set of manufactured products of a given type. We assume a set of m judges giving each his preferences by ranking (without ties) the n objects. Thus, each judge defines a ranking attribute on O. In this type of data there is no restriction on the number m of judges.

The categorical attribute valuated by a numerical similarity

We consider here the case where the category set C (see equation [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF]) is provided by a numerical similarity. The latter is supposed given a priori, for example, by an expert knowledge. Let us denote it by ξ. ξ is defined by a mapping of the cartesian product C × C onto the real numbers. Mostly, the set value of ξ is the positive reals that is denoted by R + :

ξ : C × C → R + (c g , c h ) → ξ(c g , c h ) (52)
where ξ(c g , c h ) is the numerical similarity value between the categories c g and c h , 1 ≤ g, h ≤ k. Mostly, ξ is symmetrical :

(∀(g, h), 1 ≤ g, h ≤ k), ξ(c g , c h ) = ξ(c h , c g ) (53)
However, real important cases of asymmetrical similarity may occur. This point will be mentioned below. On the other hand we assume

((∀(g, h), 1 ≤ g, h ≤ k)), min[ξ(c g , c g ), ξ(c h , c h )] > ξ(c g , c h ) (54)
Nevertheless, ξ(c h , c h ) is not necessarily invariant with respect to h, 1 ≤ h ≤ k. ξ can be figured by the following square matrix

C c 1 • • • c h • • • c k c 1 . . . c g ξ(c g , c h ) . . . c k Table 1 : Matrix of ξ
Now, let us consider the above example of the categorical attribute "Highest level of formal education of wife", having the three categories denoted c 1 , c 2 and c 3 (see Section 3.1). The matrix of ξ might be :

C c 1 c 2 c 3 c 1 5 2 1 c 2 2 4 3 c 3 1 3 6
Table 2 : Matrix of ξ for the example

In fact, we have determined this matrix of numerical integer numbers from the following similarity ranking on C × C

(c 1 , c 3 ) < (c 1 , c 2 ) < (c 2 , c 3 ) < (c 2 , c 2 ) < (c 1 , c 1 ) < (c 3 , c 3 ) (55)
It may seem surprising that the similarity between a given category with itself is not the same whatever is this category. This can be justified by taking into account the specificity of the concerned category. In our example, we have considered that rarer is a category, more specific it is. Thereby, the category c 3 ("one year college or more") is more specific than c 2 ("3 or 4 years high school"). Intuitively, the resemblance between two different married couples whose common category is c 3 , is stronger than that between two different married couples whose common category is c 2 .

The valuation ξ (see equation ( 52)) induces a complete valuated symmetrical graph, without loops, on the object set O.

Explicitly (∀(x, y) ∈ O [2] ), ξ(x, y) = ξ[c(x), c(y)] ( 56
)
This graph is decomposed according to the partition π (see equation ( 21)) as following

(∀(x, y) ∈ O g × O h ), ξ(x, y) = ξ(c g , c h ) and (∀(x, y) ∈ O [2] h , ξ(x, y) = ξ(c h , c h ) (57) 1 ≤ g = h ≤ k.
Now, let us illustrate this graph in the framework of the above example

(∀(x, y) ∈ O 1 × O 2 + O 2 × O 1 ) ξ(x, y) = 2 (∀(x, y) ∈ O 1 × O 3 + O 3 × O 1 ) ξ(x, y) = 1 (∀(x, y) ∈ O 2 × O 3 + O 3 × O 2 ) ξ(x, y) = 3 (∀(x, y) ∈ O [2] 1 ) ξ(x, y) = 5 (∀(x, y) ∈ O [2] 2 ) ξ(x, y) = 4 (∀(x, y) ∈ O [2] 3 ) ξ(x, y) = 6
Let us end this development by noticing that a nominal categorical attribute can be interpreted in terms of a very particular similarity categorical attribute as following

(∀h, 1 ≤ h ≤ k), ξ(c h , c h ) = 1 (∀(g, h), 1 ≤ g = h ≤ k), ξ(c g , c h ) = 0 (58)
Now, for an asymmetrical similarity providing the category set of a categorical attribute, equation (53) does not hold. On the other hand, ξ(c h , c h ), 1 ≤ h ≤ k, may not be defined. Besides, equations (56) and (57) are still valid. As an example, consider the traffic of cellular call phones between the towns of France. "Town of France" defines a categorical attribute. For a given ordered pair (A, B) of towns of France, let us consider the number, ν(A, B), of cellular call phones emitted from A to B. The ν function defines an asymmetrical similarity on the set of the towns of France (the category set in our example). Indeed, generally ν(A, B) = ν(B, A). The object set could be the set of antennae of cellular telephone located in the different towns. Generally S is the positive reals. The valuated binary relation can be represented by a valuated graph :

The valuated binary relation attribute

{ (x, y), v(x, y) |(x, y) ∈ R(b)} (61)
The valuated binary relation attribute is a generalization of all the above attributes considered in this Section 3. However, it does not correspond to a categorical attribute. And, the specificity of the categorical structure is very important for comparing attributes or building similarity indices between described objects or between categories (see Capter 3). The attribute type considered here occurs frequently in communication problems.

Representation of the attributes of type III

As mentioned in the introduction (Section 1) a categorical attribute is of type III if the similarity structure of its category set C = {c 1 , c 2 , ..., c h , ..., c k } induces a binary relation on the set -denoted above by O {2} (see equation ( 23)) -of unordered pairs of distinct objects, or on the set denoted above by O [2] (see equation ( 35)) of ordered pairs of distinct. Specific ordinal similarity structures on C occur importantly for describing data [START_REF] Lerman | Organisation et consultation d'une banque de petites annonces à partir d'une méthode de classification hiérarchique en parallèle[END_REF] [START_REF] Lerman | Organisation et consultation d'une banque de petites annonces à partir d'une méthode de classification hiérarchique en parallèle[END_REF], [START_REF] Lerman | Representation of concept description by multivalued taxonomic preordonance variables[END_REF] [START_REF] Lerman | Representation of concept description by multivalued taxonomic preordonance variables[END_REF], Ouali-Allah (1991) [START_REF] Ouali-Allah | Analyse en préordonnance des données qualitatives[END_REF] and Peter (1987) [START_REF] Ph | Méthodes de classification hiérarchique et problèmes de structuration et de recherche d ' informations assistée par ordinateur[END_REF]. Each of them defines a specific total preorder on O {2} (ranking with ties). We shall distinguish below three versions of such a categorical attribute : "preordonance attribute", "taxonomic attribute" and "taxonomic preordonance attribute". A set theoretic representation at the level of the cartesian product O {2} × O {2} will be first given. Next, a representation by means of an adequate numerical valuation on O {2} will be proposed. The latter is easier and more efficient to handle for comparing data described by such a categorical attribute. As just mentioned, for the below presented categorical attributes, the induced total preorder is defined at the level of the set O {2} of unordered object pairs. For this case, the ordinal similarity structure on C is symmetrical with respect to the categories to be compared. Nevertheless, extension can be envisaged for the case where the induced total preorder is defined at the level of O [2] of ordered object pairs. For this case the ordinal similarity on C is asymmetrical.

The preordonance categorical attribute

A "preordonance" categorical attribute is a categorical attribute whose category set C is provided by an ordinal similarity, called preordonance on C. Formally, as said above, a preordonance on C is a total preorder on a specific set of category pairs of C. For the categorical attributes to be introduced where the ordinal similarity is symmetrical2 , the C category pairs to be considered is {(c g , c h )|1 ≤ g ≤ h ≤ k}. By denoting K = {1, 2, ..., h, ..., k} the category codes of the concerned attribute, the total preorder is defined on the following set

K 2 = {(g, h)|1 ≤ g ≤ h ≤ k} (62)
Lerman and Peter (1985) [START_REF] Lerman | Organisation et consultation d'une banque de petites annonces à partir d'une méthode de classification hiérarchique en parallèle[END_REF], [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF] [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF], Ouali-Allah (1991) [START_REF] Ouali-Allah | Analyse en préordonnance des données qualitatives[END_REF], [START_REF] Lerman | Comparing taxonomic data[END_REF] [25], Lerman and Peter (2003) [START_REF] Lerman | Indice probabiliste de vraisemblance du lien entre objets quelconques : analyse comparative entre deux approches[END_REF]. In fact, we have used already and implicitly such a categorical attribute in the above example of "Highest level of formal education of wife" (see equation ( 55)).

Let us now give an example concerning the problem of a database management of real estate advertisements Peter (1987) [START_REF] Ph | Méthodes de classification hiérarchique et problèmes de structuration et de recherche d ' informations assistée par ordinateur[END_REF]. One categorical attribute defined in this database is "subject of the transaction". Its categories are : c 1 = house, c 2 = villa, c 3 = apartment, c 4 = studio apartment, c 5 = room, c 6 = garage and c 7 = piece of land. By denoting gh the category pair (c g , c h ), 1 ≤ g ≤ h ≤ k, the proposed preordonance is :

14 ∼ 15 ∼ 16 ∼ 17 ∼ 24 ∼ 25 ∼ 26 ∼ 27 ∼ 35 ∼ 36 ∼ 37 ∼ 46 ∼ 47 ∼ 56 ∼ 57 ∼ 67 < 23 ∼ 34 < 13 < 45 < 12 < 11 ∼ 22 ∼ 33 ∼ 44 ∼ 55 ∼ 66 ∼ 77 ( 63
)
where the symbols ∼ and < mean "equivalent" and "strictly lower than", respectively.

There are in all k × (k + 1)/2 = 7 × (7 + 1)/2 = 28 pairs. This total preorder comprises 6 classes. Their respective cardinalities (composition of the total preorder) are 16, 2, 1, 1, 1 and 7.

Generally, the expert establishes the total preorder on K 2 (preordonance on C), recursively, by sorting the pairs at each step the most similar among pairs of K 2 not yet sorted.

The preordonance categorical attribute has played an important part in our formalization work of data description (see the above references). Let us mention that this type of attribute appeared also independently with a different expression and in a very different context in [START_REF] Chah | Critères de classification sur des donées hétérogènes[END_REF] [START_REF] Chah | Critères de classification sur des donées hétérogènes[END_REF].

The preordonance categorical attribute concept does not require a notion of metrical difference between categories. Nevertheless, psychometric researchers consider a numerical scale measurement called "ordered metric scale" in which the differences between categories are defined and ordered [START_REF] Stevens | Mathematics, measurement and psychophysics[END_REF] [START_REF] Stevens | Mathematics, measurement and psychophysics[END_REF].

Let us now define the set theoretic representation of a preordonance categorical attribute. Denote by ω(K 2 ) the total preorder on (K 2 ) (see equation ( 62)) expressing this preordonance attribute.

(L 1 , L 2 , ..., L q , ..., L r ) (64)

will designate the ordered sequence of the class preorder. L 1 (resp., L r ) comprises the most dissimilar (resp., similar) category pairs. To fix idea and for consistent reasons, we can assume that the last classes are defined on the subset {(h, h)|1 ≤ h ≤ k}. However, this point is out of our representation problem. The basic representation level is the cartesian product K 2 × K 2 . This representation has the same nature as that given in Section 3.2 for a total preorder on an object set (see equation [START_REF] Ph | Méthodes de classification hiérarchique et problèmes de structuration et de recherche d ' informations assistée par ordinateur[END_REF]). But clearly, the context is different. In the latter, we define the following set sums of cartesian products

R(ω(K 2 )) = 1≤p<q≤r L p × L q (65) P (ω(K 2 )) = 1≤p≤r L p × L p (66) S(ω(K 2 )) = 1≤p<q≤r L q × L p (67)
I m (L p × L q ) = ( (e,f )∈Lp O e ⋆ O f )( (g,h)∈Lq O g ⋆ O h ) I m (L p × L p ) = ( (g,h)∈Lp O g ⋆ O h ) 2 (68)
1 ≤ p < q ≤ r, where as above the sums indicate union of disjoint subsets and where O g ⋆ O h is defined by the set of distinct unordered pairs whose components belong to O g and O h , respectively, 1 ≤ g ≤ h ≤ k.

In order to avoid too big combinatorial complexity we code the total preorder ω(K 2 ) with the "mean rank function" r m (see equation (50) expressed in another context). Referring to equation (64), denote by l q the cardinality of L q , 1 ≤ q ≤ r. Therefore, for a given pair (g, h) belonging to L q we get Israël César Lerman

r m (g, h) = 1≤p<q l p + l q + 1 2 (69)
Thus,we can verify the equation

1≤q≤r l q = k × (k + 1) 2
For example, for the total preorder (63), the sequence of the values of r m is We verify that the sum of the r m ranks is equal to 28 × 29/2 = 406. Thus, a preordonance categorical attribute is coded as a specific categorical attribute valuated by a numerical similarity (see Section 3.4), given by the mean rank function.

Let us denote by R q the right member of (69). R q is the common value of the mean rank function r m on the pairs (g, h) belonging to the q th preorder class L q (see ( 64)). The empirical statistical distribution of R q on O ⋆ O is given by

{(R q , (g,h)∈Lq (n g × n h /n [2] ))|1 ≤ q ≤ r} ( 70
)
where n [2] = n × (n -1)/2. We have considered above the case of symmetrical ordinal similarity for which the ordinal similarity for the ordered pair (c g , c h ) is the same as that for (c h , c g ), 1 ≤ g = h ≤ k. As mentioned above, there might be data where the ordinal similarity is asymmetrical Lerman and Guillaume (2011) [START_REF] Lerman | Comparaison entre deux indices pour l'évaluation probabiliste discriminante des règles d ' association[END_REF], [START_REF] Lerman | Directed binary hierarchies and directed ultrametrics[END_REF] [START_REF] Lerman | Directed binary hierarchies and directed ultrametrics[END_REF]. In this case the total preorder comparing categories has to be established on

H 2 = {(g, h)|1 ≤ g, h ≤ k} (71)
instead of on K 2 (see equation ( 62)). In these conditions, an analogous development as above (see equations (62) to (70)) has to be setup. In this, the nonordered object pairs O {2} has to be replaced by the ordered object pairs O [2] . We leave this development to the reader.

The taxonomic categorical attribute

Let us begin with an example taken from data we have processed Lerman andPeter (1988, 2007) [START_REF] Lerman | Classification en présence de variables préordonnances taxonomiques à choix multiple. application à la structuration des phlébotomes de la Guyane Française[END_REF], [START_REF] Lerman | Representation of concept description by multivalued taxonomic preordonance variables[END_REF]. These data are provided by biological descriptions of phlebotomine sandfly species of French Guiana [START_REF] Lebbe | Identification assistée par ordinateur des phlébotomes de la Guyane Française[END_REF] [START_REF] Lebbe | Identification assistée par ordinateur des phlébotomes de la Guyane Française[END_REF]. Descriptions are very complex. Relative to a descriptive categorical attribute and for subsets of category values, hierarchical logical dependencies associated with the mother → daughter relation, have to be taken into account. Consider the attributes 1, 18, 19 and 20 defined in this database [START_REF] Lebbe | Identification assistée par ordinateur des phlébotomes de la Guyane Française[END_REF] and retaken in [START_REF] Lerman | Classification en présence de variables préordonnances taxonomiques à choix multiple. application à la structuration des phlébotomes de la Guyane Française[END_REF]. We denote them by a 1 , a 21 , a 31 and a 32 , respectively. a 1 is the "Sex" attribute, a 21 is defined by the "Number of style spines", a 31 indicates the "Distribution of 4 style spines" and a 32 , the "Distribution of 5 style spines". The code category sets of these attributes are : {1 : male 2 : f emale}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5, 6} and {1, 2, 3, 4, 5}, respectively. We obtain the following taxonomic structure organizing the different attributes according to the mother → daughter relation. Then, with a categorical value of a given attribute a daughter attribute might be associated. For example, the attribute a 21 is associated with the value 1 of the attribute a 1 (see Figure 2.3).

Clearly, the attribute a 21 is defined only when the a 1 value is 1. It is defined on the subset of objects whose a 1 value is 1 (male phlebotomine sandflies in our example). On the other hand, the attributes a 31 and a 32 are defined only when the values of a 21 are 4 or 5. a 31 (resp., a 32 ) is defined on the subset of objects where the value of a 1 is 1 and where the value of a 21 is 4 (resp., 5). The common mother of the attributes a 31 and a 32 is a 21 .

More generally, a taxonomic categorical attribute denoted τ , is defined by an organization of logically dependent attributes. It consists of a sequence of collections of categorical attributes of the following form :

In the above example τ is instanciated as follows :

τ = ({a 1 }, {a 21 }, {a 31 , a 32 })
Now, let us imagine two categorical attributes a 41 and a 42 defined respectively for a 31 = 4 and for a 32 = 5. By denoting A 41 and A 42 the respective category sets of a 41 and a 42 , A 41 and A 42 will be placed at the same 5 th level of the above hierarchical structure (see Figure 2.3). A 41 and A 42 will be instanciations of the above {a pi , ..., a pi ′ } (i ′ > i) subset of categories. Two categorical elements of A 41 (resp., A 42 ) would have the same mother a 41 (resp., a 42 ).

The construction of a taxonomic attribute must be done in a descendant manner, level by level. The first level 1 is assigned to the root of the taxonomy. Hence, in our example, the root is defined by the categorical attribute "Sex". Now, consider a given node ν defined at the l th level (l integer) and corresponding to a value of a preceding categorical attribute. The categorical attribute a ν gives rise to a (l + 1) th level, on which the values of a ν are represented by different nodes. Directed descendant arrows join the node ν to the new nodes. Thus, in the example of Figure 2.3, the node corresponding to the value 1 of a 1 , where the attribute a 21 is defined, gives rise to the level 3 on which the nodes corresponding to the values of a 21 are placed. There are in all 5 values. Moreover, the two sets of nodes associated with the attributes a 31 and a 32 are placed at the fourth level,respectively (a 31 is defined for the value 4 of a 21 and a 32 is defined for the value 5 of a 21 ). There are 6 values for a 31 and 5 values for a 32 .

Each node of the taxonomic tree representing a taxonomic attribute is labelled. There are two alternatives for this labelling whether the concerned node is terminal or not. For a terminal node -defining a leave of the taxonomic tree -the label is a value of a categorical attribute taking part in the taxonomy. For a non-terminal node the labelling includes two values : the first one is defined by a categorical attribute value and the second one specifies the categorical attribute considered at this node. As an example, consider the level 3 of the taxonomic tree given in Figure 2.3. From left to right, the first three nodes are terminal nodes and the two last nodes are non-terminal nodes.

A lateral ranking of leaves (terminal nodes) from left to right can be considered in the taxonomic structure. This ranking is given in the above pictured tree where there are in all 15 terminal nodes. Consider again the level 3 of the taxonomic tree. The extreme left node is a terminal node. It is labelled by the ordered pair (1, 1). The first component is defined by the first value of the mother categorical attribute a 21 . The second component is its lateral rank. The terminal node at the extreme left of level 4 is labelled [START_REF] Anderberg | Cluster Analysis for Applications[END_REF][START_REF] Chah | Critères de classification sur des donées hétérogènes[END_REF]. It corresponds to the value coded 1 of the categorical attribute a 31 involved in its mother node. It is created directly after the terminal node (3, 3) of level 3. Clearly, the lateral ranking depends on drawing options. At the 3 level, the terminal nodes are first placed. This could have been done for the level 2. The chosen alternative is due to legibility reason. Anyway, a precise status could be defined for a consistent and systematic technique of drawing the taxonomic tree associated with a taxonomic attribute. This is left to the reader as an exercise. In the following each terminal node (leave of the taxonomic tree) will be coded by its lateral rank. Notice that each terminal node can be identified with the associated complete chain of the taxonomic tree, starting with the root and ending with it. Now, we are going to associate bijectively with the taxonomic structure defined by the taxonomic attribute expressed by equation ( 72) and its graphical representation as given in Figure 2.3, a level labelled classification tree on the set denoted T of its terminal nodes. This is mathematically defined by a partition chain on T (see Chapter 0 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF]). Assume that k levels are comprised in the taxonomic structure (k = 4 for our example). The level 1 is the root level and the k level is determined by the terminal nodes corresponding to attributes introduced at the (k -1) th level. In our example these attributes are a 31 and a 32 . Denote (P 0 , ..., P j-1 , P j , ..., P k-1 ) the partition chain associated with the taxonomic structure. In order to precise this sequence of partitions, identify each non-terminal node with the subset of terminal nodes deriving from it. As an example, the node (5, a 32 ) is identified with the subset {10, 11, 12, 13, 14}. Besides, the node (1, a 21 ) is identified with the subset {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}.

P 0 is the finest partition. Each of its classes is a singleton including exactly one single element. In our example P 0 comprises 15 classes. P k-1 is the least fine partition, it includes only one class grouping all the elements. P j is deduced from P j-1 by aggregating nodes (terminal or not) appearing at the the level k -j + 1 of the taxonomic structure and derived from a same categorical attribute attribute defined for a given node of the level k -j. In our example, the partition P 1 is obtained from the partition P 0 by aggregating {4}, {5}, {6}, {7}, {8}, {9} on one side and by aggregating {10}, {11}, {12}, {13}, {14} on the other side. Thus, we have In Chapter 0 (Section 4.2) of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF] bijective correspondence has been established between a partition chain on a finite set E and a ultrametric distance on E given by a level notion of the classification tree associated with the partition chain. Here, equivalently, we shall define a bijective correspondence between a taxonomic structure (see equation ( 72)) and a ultrametric proximity on the set that denoted by T of its terminal nodes (see Figure 2.3). Let us recall that this ultrametric proximity that we denote p is characterized by the following property :

P 1 = {1},
(∀x, y and z ∈ T , x = y, x = z and y = z), p(x, y) ≥ min[p(x, y), p(y, z)]

(see Chapter 0 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF], Section 0.4.1).

Here, the node level is defined by 1 plus the number of branches joining the root of the taxonomic structure to the concerned node. As examples in Figure 2.3, level (4, a 31 ) = 3 and level (5, 8) = 4. For u and v belonging to T , p(u, v) is defined by the highest node level of the taxonomic structure where u and v are aggregated. Thus, as an example relative to the figured taxonomic tree (see Figure 2.3), p(10, 14) = 3 and p(7, 13) = 2 ; p(10, 14) > p [START_REF] Ghazzali | Comparaison et réduction d ' arbres de classification, en relation avec des problèmes de quantification en imagerie numérique[END_REF][START_REF] Kerjean | Tentative d'établissement de 100 typologies d'examens biologiques. Contribution à l'établissement du système[END_REF].

The proof of the above condition (equation ( 73)) is analogous to that given for the ultrametric distance associated with a partition chain (see Chapter 0 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF], Section 4.2). Indeed, for a subset {x, y, z} of 3 elements of T , suppose p(x, y) > p(y, z) : the highest aggregating level of x and y is strictly greater than that of y and z. Therefore, x and y belong to the same node -appearing at the level p(x, y) -excluding z. Otherwise p(y, z) ≤ p(x, y). Now, if p(x, y) = p(y, z), the node highest level joining x and y is the same as that joining y and z. Hence and necessarily, the first node is identical to the second one, because both include y. Therefore, p(x, y) = p(y, z) = p(x, z). This ends the proof of (73).

The proximity p function valuates a total preordonance on the set T of the terminal nodes ; that is to say, a total preorder on the set

T 2 = {(x, y)|x ∈ T , y ∈ T , 1 ≤ x ≤ y ≤ |T |} (74)
where |T | is the cardinality of T (|T | = 15 in the above example). This total preorder (ranking with ties) that we denote by ω(T 2 ) is established as follows

(∀(x, y) and (u, v) ∈ T 2 ), (x, y) ≤ (u, v) iff p(x, y) ≤ p(u, v) (75)
The total preordonance defined on T is ultrametric in the sense given in Chapter 0 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF], Section 4.3. More explicitly, if ρ is a ranking function on T 2 compatible with p (i.e. strictly increasing with respect to p), we have (∀x, y, and z ∈ T ), ρ(x, y) ≥ r and ρ(y, z) ≥ r ⇒ ρ(x, z) ≥ r (76)

Collection des Publications Internes de l'Irisa c IRISA where r is an arbitrary positive integer. We adopt for the ranking function ρ, the mean rank function r m introduced above (see equations ( 69) and ( 70)). Finally, we represent a taxonomic attribute by a ultrametric preordonance on the set T of the terminal nodes of the associated taxonomic structure. This preordonance is numerically coded with the mean rank function defined on T 2 (see equations ( 74) and ( 75)). Now, let us ilustrate how this represetation is established in the framework of our example. Consider the diagram of Figure 2.3 from down to top. The root node results from aggregating the two components of all ordered pairs of the form (i, 15), 1 ≤ i ≤ 14. Then, the first preorder class of ω(T 2 ) includes 14 pairs. Therefore, the common mean rank of each of them is (14+1)/2=7.5. The node (1, a 21 ) is obtained from three types of pair aggregations. These are :

1. {(i, j)|1 ≤ i < j ≤ 3} ; 2. {(i, j)|1 ≤ i ≤ 3, 10 ≤ j ≤ 14} ; 3. {(i, j)|1 ≤ i ≤ 9, 10 ≤ j ≤ 14}.
There are in all 3 + 3 × 6 + 9 × 5 = 66 pairs. These constitute the second class of ω(T 2 ). In these conditions the mean rank of each of these pairs is 14 + (66 + 1)/2 = 47.5.

The nodes (4, a 31 ) and (5, a 32 ) are constituted at level 3. The former aggregates the components of the set of pairs {(i, j)|4 ≤ i < j ≤ 9} and the latter those of {(i, j)|10 ≤ i < j ≤ 14}. There are in all ((6×5)/2)+((5×4)/2) = 25 pairs. They constitute the third class preorder of ω(T 2 ). Consequently, the common mean rank of these pairs is 14 + 66 + (25 + 1)/2 = 93 The fourth class preorder of ω(T 2 ) is defined by all ordered pairs of the form (i, i), 1 ≤ i ≤ 15. The common mean rank assigned to each of these pairs is 14 + 66 + 25 + (15 + 1)/2 = 113.

The expected value of the mean rank sum is easily obtained : . ω(T 2 ) induces a total preorder on the set O {2} of unordered object pairs. In order to explicit this total preorder (ranking with ties), denote O(i) the O subset defined by the value i of the taxonomic attribute, 1 29) for its definition) and substitute in ω(T 2 ), O(i) ⋆ O(j) for (i, j). On the other hand, substitute in ω(T 2 ), the unordered object pairs P 2 (O(i)) of O(i) for the ordered pair (i, i),

≤ i ≤ |T |. The set {O(i)|1 ≤ i ≤ |T |} defines a partition on O. Now, for i < j, 1 ≤ i < |T |, consider the unordered object pairs O(i) ⋆ O(j) (see what follows equation(
1 ≤ i ≤ |T |.

The taxonomic preordonance attribute

Let us reconsider here the ordinal similarity structure provided by a taxonomic attribute τ organizing a set of logically dependent categorical attributes (see equation ( 72)). We further assume here that the category set denoted C(a pi ) of a given categorical attribute a pi is provided by a total preordonance (see Section 4.1), 1 ≤ i ≤ k p , 1 ≤ p ≤ q. These preordonances are locally defined, attribute by attribute. They have to be integrated in the taxonomic structure. In these conditions, we have to build a total preordonance on the set of the taxonomy leaves, or, equivalently, on the set of the associated complete chains going from the root to the leaves. This preordonance must take into account both the preordonance defined by the taxonomic structure and those we have just mentioned.

Such preordonance is built step by step, decreasingly according to the taxonomic resemblance between terminal nodes (leaves of the taxonomy). The general principle consists in refining the ultrametric preordonance associated with the taxonomy (see Section 4.2) by means of the preordonances locally defined on the category sets of the different attributes.

In order to clarify the technique, let us begin by illustrating the refinement process in the framework of our example (see Figure 2.3). By going from the deepest level (4 in our case) to the root one, each refinement step concerns the terminal nodes aggregated at the first time at a given level. We begin by ordering the set

∆(T ) = {(x, x)|x ∈ T } (77)
according to the leaf depth in the taxonomy : in other words, the deeper the leaf the higher the ordinal similarity between the represented category and itself is. Thus, in case of our example (see Figure 2. By considering this ranking in a reverse manner, according to increasing ordinal similarity, the mean ranks assigned to the three preorder classes -that we can distinguish -are 106, 108 and 115, respectively. They replace the common rank 113 (see above). The concerned sum rank is preserved. Indeed, 106 + 3 × 108 + 11 × 115 = 15 × 113 = 1695. Now, let us consider the passage from level 4 to level 3. A = {4, 5, 6, 7, 8, 9} and B = {10, 11, 12, 13, 14} code the category sets of the attributes a 31 and a 32 , respectively. A and B are constituted by terminal nodes. According to above notations (see Sections 2.4.1 and 2.4.2), the set P 2 (A) (resp., P 2 (B)) of unordered element pairs is defined by {(x, y)|4 ≤ x < y ≤ 9} (resp., {(x, y)|10 ≤ x < y ≤ 14}). P 2 (A) ∪ P 2 (B) determines a unique class of the total preorder defined at the level 3 by the tree structure. This class comprises all the element pairs aggregated at the level 3 of the taxonomy. There are in all card[P 2 (A)] + card[P 2 (B)] = 15 + 25 pairs. Two preordonance structures on the category sets A and B of the attributes a 31 and a 32 provide total preorders on P 2 (A) and P 2 (B), respectively. These two total preorders must be employed consistently in order to define a unique total preorder on the entire set P 2 (A) ∪ P 2 (B). One option for this consists in requiring the expert knowledge for ranking the category pairs of A with respect to those of B. The option we adopt uses the mean rank functions, locally defined on P 2 (A) and P 2 (B) from the total preordonances on A and on B. These are interpreted as numerical similarity coefficients on A and on B, respectively. Denote r A and r B these mean rank functions. The value sum of r A (rep., r B ) is (15 × 16)/2 = 120 (rep., (10 × 11)/2 = 55). In these conditions, we define a numerical function r A∪B on P 2 (A) ∪ P 2 (B) directly deduced from r A and r B , as follows

r A∪B : P 2 (A) ∪ P 2 (B) → V al(r A ) ∪ V al(r B ) ( 78
)
where V al(r A ) (resp., V al(r B )) is the value set of r A (resp., r B ) and where r A∪B (x, y) is equal to

r A (x, y) [resp., r B (x, y) ] if {x, y} ∈ P 2 (A) [resp., P 2 (B)].
Therefore, according to the value scale of r A∪B , a total preorder on P 2 (A) ∪ P 2 (B) is established as follows ∀{x, y} and {z, t}

∈ P 2 (A) ∪ P 2 (B), {x, y} ≤ {z, t} iff r A∪B (x, y) ≤ r A∪B (z, t) (79)
This total preorder is substituted for the unique class P 2 (A) ∪ P 2 (B). A new global mean ranking function refining the previous one is established on the set defined by this class. Recall that we had one common value 93 for all of its elements (See Section 4.2). Necessarily the new assigned values belong to the interval [14 + 66 + 1 + 81, 14 + 66 + 25].

The nature of the passage from level 3 to level 2 is somewhat different than the preceding one. All the nodes occupying the level 3 derive from only one mother node occupying the level 2, this being defined by the categorical attribute a 21 . Recall that the unique preorder class of ω(T 2 ) (see equation ( 74)) associated with the taxonomy is defined by the set of unordered leave pairs given in equation (77). For this, the mean rank of a given pair of such a preorder class is 47.5. The category set D of a 21 is defined by {1, 2, 3, a 31 , a 32 }. A total preordonance on D enables to determine a total preorder on the mentioned unique preorder class of ω(T 2 ). In order to built the latter, we have to do the following substitutions

(∀x ∈ {1, 2, 3}), (x, 4) ← {(x, y) | y ∈ A} (∀x ∈ {1, 2, 3}), (x, 5) ← {(x, y) | y ∈ B} for {4, 5} ← {(x, y) | (x, y) ∈ A × B} ( 80
)
where the different pairs included in a given class substitution are interpreted as equally similar, A and B have been defined above.

Notice that the new mean rank values in the concerned class of ω(T 2 ) are comprised between 14+1 = 15 and 14+66 = 80. Now, let us give a general expression of the construction of a taxonomic preordonance attribute. For this purpose, we start with the definition (72) of a taxonomic attribute τ . {a pi |1 ≤ i ≤ k p } is the set of the categories introduced at the p th level in a descendant way from the top to the bottom. Some of these categories define terminal nodes of the τ structure and some others define categorical attributes which are divided at the next (p + 1) th level (see level p = 3 of the example). Denote P 2 [C(a pi )] the set of unordered pairs of the category set C(a pi ) of a pi , 1 ≤ i ≤ k p . i P 2 [C(a pi )] determines a new unique class -by going from down to top -of the taxonomic preordonance. This unique class is refined by means of the total preordonances defined on C(a pi ), 1 ≤ i ≤ k p , respectively.

We begin by ordering the set ∆(T ) = {(x, x)|x ∈ T } considered in equation ( 77), of category pairs of the form (x, x) where x is a terminal node (leaf) of the taxonomic structure (see above for the given example following (77)). Then and recursively, for p = q to p = 2, the unique taxonomic class i P 2 [C(a pi )] is refined. The following steps are needed for this refinement :

Collection des Publications Internes de l'Irisa c IRISA (i) Compute the local mean rank rank function r i m for the total preorder P 2 [C(a pi )], defined from the preordonance attribute a pi ;

(ii) Establish a global total preorder on i P 2 [C(a pi )] compatible with the respective local mean ranking functions r i m , 1 ≤ i ≤ k p , that is to say :

(∀(x, y) ∈ P 2 [C(a pi )], (z, t) ∈ P 2 [C(a pi ′ )]), (x, y) ≤ (z, t) iff r i m (x, y) ≤ r i ′ m (z, t) (81)
(iii) Begin by associating with each category set C(a pi ) the category set C t (a pi ) corresponding to terminal nodes derived from a pi and then, for any (x, y) belonging to P 2 [C(a pi )] consider the subset A(x) [resp., A(y)] of C t (a pi ) defined by terminal nodes issued from x (resp., y). In these conditions, the set leaf pairs A(x) × A(y) is substituted for (x, y) (see (80)). All the concerned pairs are interpreted as equally similar and the mean rank function value r i m (x, y) is applied to all of these pairs. The set (x,y) A(x) × A(y) ((x, y) ∈ i P 2 [C(a pi )]) of terminal node pairs constituted a unique class of the total preorder representing the taxonomic attribute. And now, this class is divided into subclasses depending on the respective preordonances defined on the category sets C(a pi ) and the local mean rank functions r i m calculated for the respective total preorders on

P 2 [C(a pi )], 1 ≤ i ≤ k p .
When the process ends with p = 2, we obtain a total preorder on the entire set of terminal node pairs, comprising the pairs of ∆(T ) (see ( 77)). This global preordonance is valuated by means of rhe mean rank function according to increasing ordinal similarity (see the above example).

Coding the different attributes in terms of preordonance or similarity categorical attributes

We have just seen above (Sections 4.2 and 4.3) how the taxonomic categorical attribute can be represented as a specific preordonance categorical attribute (see Section 4.1). By applying for each of them the mean rank function in order to code the associated total preorder on the category pairs (see (70)) we obtain categorical attributes whose value sets are evaluated by specific similarity measures (see Section 3.4), defined by the mean rank functions.

In fact, preordonance coding of the different attributes of types I or II can be considered. And this may contribute to enrich the scale value of the concerned attribute. Let us make clear this representation for the following cases : (i) boolean (Section 2.1) ; (ii) numerical (Section 2.2) ; (iii) nominal categorical (Section 3.1) ; (iv) ordinal categorical (Section 3.2) and (v) ranking (Section 3.3).

Preordonance coding of the boolean attribute

As expressed in Section 2.1, with a boolean attribute a is associated a binary categorical attribute whose value set being {a, ā}, where ā is the negated boolean attribute of a. Let us index by 1 (resp., 2) the category a (resp., ā) and consider the following set of ordered pairs

B 2 = {(1, 2), (1, 1), (2, 2)} ( 82
)
The preordonance is defined by a total preorder (ranking with ties) on B 2 , and for this three alternatives can be envisaged :

1. (1, 2) < (1, 1) ∼ (2, 2) ; 2. (1, 2) < (1, 1) < (2, 2) ; 3. (1, 2) < (2, 2) < (1, 1).
There is no enrichment of the scale value in the first case. However, this representation is not equivalent to that given in Section 2.1 for comparing categorical attributes (see Chapter 2 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF]).

Between 2 and 3 the chosen preordonance structure depends on the most significant category. If a (resp., ā) is the most important category according to expert knowledge, then the preordonance 3 (resp., 2) is adopted. For the example given in Section 1 the category a = cirrhosis is more significant than ā = non-cirrhosis. Therefore, the preordonance 3 is considered.

Preordonance coding of the numerical attribute

Here we consider the presentation given in Section 2.2 frm which the notations are retaken. In fact, the proposed representation is given by a categorical attribute valuated by a numerical similarity. In this case asymmetrical similarity is needed. Denote by w the categorical attribute associated with the numerical attribute v (see Section 2.2). Consider the category set of w indexed by {1, 2, ..., i, ..., m}. Then , the ordered category pairs is represented by

C 2 = {(i, j)|1 ≤ i, j ≤ m} (83)
it includes m 2 elements. The valuation assigned to the ordered pair (i, j) is ξ(i, j) = x (j) -x (i) , 1 ≤ i, j ≤ m (see Section 2.2). It is asymmetrical and defined by the directed range -from left to rightof the interval [x (i) , x (j) ], 1 ≤ i, j ≤ m. The empirical distribution of the defined valuation is

{(ξ(i, j), f i × f j )|1 ≤ i, j ≤ m} (84)
where f i is defined in ( 12), 1 ≤ i ≤ m.

As an example, consider the distribution given in [START_REF] Kerjean | Tentative d'établissement de 100 typologies d'examens biologiques. Contribution à l'établissement du système[END_REF]. We have :

(ξ(2, 5), f 2 × f 5 ) = ((7.2 -2.3), 0.1 × 0.2) = (4.9, 0 .02)
.

Notice that generally, a 0 value for ξ(i, j) may occur for i = j, 1 ≤ i, j ≤ m. It occurs necessarily for j = i, 1 ≤ i ≤ m.

Preordonance coding of the nominal categorical attribute

The notations of Section 3.1 are retaken here. {1, 2, ..., h, ..., k} indexes the category set of a nominal categorical attribute c. We consider the ordered pairs of categories

K 2 = {(g, h)|1 ≤ g ≤ h ≤ k} (see (62)). If g < h, (g, h)
designates the unordered pair of categories {g, h} that we denote by gh (see (63)) ; if g = h, (h, h) denoted hh, is considered for the comparison between the category h with itself, 1 ≤ g ≤ h ≤ k.

In the established preordonance two distinct categories are considered as equally dissimilar. On the other hand, the similarity of a given category with itself is the same whatever is the concerned category. Consequently, the preordonance can be written as follows

12 ∼ 13 ∼ ... ∼ 1k ∼ 23 ∼ 24 ∼ ... ∼ 2k ∼ ... ∼ (k -1)k < 11 ∼ 22 ∼ ... ∼ kk (85)
There are two classes for this total preorder on K 2 . The first one comprises k × (k -1)/2 elements and the second one, k elements. The corresponding mean ranks are ((k 2 -k + 2)/4) for one element of the first class and (k 2 + 1)/2, for one element of the second class. We verify easily that the mean rank sum is equal to

[(1/2) × (k × (k + 1)/2)] × [(k × (k + 1)/2) + 1].
Denote by p = n × (n -1)/2 the cardinality of the set P = O {2} of unordered object pairs from the object set O, the empirical statistical distribution of the categorical attribute whose value set is K 2 can be expressed as follows

{(gh, n g × n h p )|1 ≤ g < h ≤ k} ∪ {hh, n h × (n h -1) 2p |1 ≤ h ≤ k} (86)
(see [START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles[END_REF] and following). By denoting r(π) = card[R(π)] and s(π) = card[S(π)] (see [START_REF] Lerman | Classification en présence de variables préordonnances taxonomiques à choix multiple. application à la structuration des phlébotomes de la Guyane Française[END_REF]), the empirical statistical distribution of the mean rank function is given by

( k 2 -k + 2 4 , s(π) p ), ( k 2 + 1 2 , r (π) p ) (87)
Collection des Publications Internes de l'Irisa c IRISA Now, we are going to illustrate the above presentation in the framework of the example given in Section 3.1, provided by [START_REF] Goodman | Measures of association for cross classifications[END_REF] [START_REF] Goodman | Measures of association for cross classifications[END_REF]. Three categories c 1 , c 2 and c 3 were defined in Section 3.1. The preordonance (85) becomes

12 ∼ 13 ∼ 23 < 11 ∼ 22 ∼ 33
The two mean rank values associated with the two preorder classes are 2 and 5. By recalling that n 1 = 591, n 2 = 608, n 3 = 239 and p = 1033203, the empirical statistical distribution (86) is instanciated as follows ( We verify the value 1 for the sum of the relative frequencies. r(π) and s(π) are equal to 387314 and 645889, respectively (see the end of Section 3.1). Therefore, the empirical statistical distribution (87) of the mean rank function becomes (2, 0.3749), (5, 0.6251)

Preordonance coding of the ordinal categorical attribute

Recall the notations of Section 3.2. The category set {c h |1 ≤ h ≤ k} is indexed by {h|1 ≤ h ≤ k}. The preordonance on the category set is defined by a total preorder on the set H = {(g, h)|1 ≤ g, h ≤ k} (see ( 71)) of all ordered category pairs. This will correspond to an asymmetrical ordinal similarity. More precisely, an ordered pair (g, h) is ranked according to the difference h -g between the two integer codes h and g, 1 ≤ g, h ≤ k. Therefore, a given class of the total preorder is defined by where the first term correspond to g = k and the second one to g = 1. Therefore, the value of the mean rank function assigned to a current element of D e is given by

D e = {(g, h)|1 ≤ g, h ≤ k, h -g = e} (88)
1-k≤f ≤e-1 [min(k, k + f ) -max(1, 1 + f ) + 1] + 1 2 [min(k, k + e) -max(1, 1 + e) + 2] (90)
Now, remind that n × (n -1) is the cardinality of the set O [2] of ordered distinct object pairs. For e = 0, the relative frequency of D e is given by

{(g,h)∈De} n g × n h n × (n -1) (91)
For e = 0, this relative frequency becomes

1≤g≤k n g × (n g -1) n × (n -1) (92)
(91) and (92) define the empirical statistical distribution of h -g, 1 ≤ g, h ≤ k.

In the previous treatment we have represented a given category c h of an ordinal categorical attribute by the integer code h, 1 ≤ h ≤ k. And this is arbitrary. However, for comparing two ordered category pairs (c g , c h ) and (c g ′ , c h ′ ) of this type of attribute, it is intuitively acceptable to consider the ordinal dissimilarity between (c g and c h ) strictly greater than that between (c g ′ and c h ′ ), if and only if h -g > h ′ -g ′ . Nevertheless, in case where h -g = h ′ -g ′ = e = 0, assigning the same ordinal dissimilarity to (c g , c h ) and to (c g ′ , c h ′ ) may seem difficult to admit. One option might consist in refining the class D e by associating with (g, h) the relative frequency (n g -n h )/n = f g -f h . Thus the ordinal dissimilarity on D e becomes an increasing function of the latter relative frequency.

Let us now illustrate this coding in our example considered in Section 3.2. The linear order defined for the three categories c 1 , c 2 and c 3 is c 1 < c 2 < c 3 . The total preorder on the set H of all ordered pairs (g, h), 1 ≤ g, h ≤ 3, is defined by

(3, 1) < (2, 1) ∼ (3, 2) < (1, 1) ∼ (2, 2) ∼ (3, 3) < (1, 2) ∼ (2, 3) < (1, 3)
The associated mean rank values are 1, 4.5, 5, 7.5 and 9, respectively. By recalling that n 1 = 591, n 2 = 608 and n 3 = 239, the second and the fourth classes can be refined as follows (2, 1) < (3, 2) and (2, 3) < (1, 2)

Indeed, n 1 -n 2 < n 2 -n 3
Let us end this formal presentation by indicating that our focus for comparing ordinal categorical attributes is the set theoretic representation given in Section 3.2 above.

Preordonance coding of the ranking attribute

This coding can be interpreted as a particular case of the previous one. Each category is represented by only one object :

n h = 1, 1 ≤ h ≤ k. For this interpretation k = n = card(O).
In these conditions, the above development can be retaken, except the refinement technique. Indeed, for any element (g, h) of D e (see 91), n g = n h = 1. But in this case, it is intuitively acceptable to consider as equivalent all the ordered pairs of D e . Two main approaches for building association coefficients between ranking attributes are derived from the two codings given in Section 3.3 and in this section, respectively (see Chapter 2 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF], [?] and [START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles, ii[END_REF]).

Attribute representations when describing a set C of categories

We have seen in the above sections that the basic data for describing an object set O by an attribute a is an ordered pair (a, o) where o is an element of O. The value of a on o, denoted by a(o) is unique. In this section the description concerns a set Γ categories. Let us designate by {C 1 , C 2 , ..., C i , ..., C I } this set of categories :

Γ = {C 1 , C 2 , ..., C i , ..., C I } (93)
We assume Γ obtained from a nominal categorical attribute γ defined on a universe Ω of objects. We designate by Ω i the subset of Ω constituted by the objects where C i is T RU E : Ω i = γ -1 (C i ), 1 ≤ i ≤ I. For this description by an attribute a, the basic data is defined here by an ordered pair (a, C), where C belongs to Γ. Relative to a given ordered pair (a, C i ), 1 ≤ i ≤ I, the description of C i by a has necessarily a global and then, a statistical nature. To fix idea, but also because of effective reason, a sample (set learning) O i. provided from Ω i is subtituted for C i , O i. ⊂ Ω i , 1 ≤ i ≤ I. Neverthless, cases may occur where the statistical distribution of a on C i is directly estimated by the expert knowledge, 1 ≤ i ≤ I, [START_REF] Lebbe | Identification assistée par ordinateur des phlébotomes de la Guyane Française[END_REF] [START_REF] Lebbe | Identification assistée par ordinateur des phlébotomes de la Guyane Française[END_REF].

i. = card(O i. ) card( 1≤i ′ ≤I O i. ) (95) 1 ≤ i ≤ I.
Under these conditions the data are defined here by the sequence

(D i a , p i. )|1 ≤ i ≤ I (96)
We have realized previously that the statistical distribution of a descriptive attribute a on an object set O, depends on the nature of the set theoretic representation of the concerned attribute. Consequently and in order to explicit (96) for the different data description cases, we are going to remind and to highlight these statistical distributions. The attributes of type I (boolean and numerical) will be considered in Section 5.2. The nominal and ordinal categorical attributes will be studied in Section 5.3 and finally, the preordonance attributes, in Section 5.4. In Section 5.5 we shall formalize the data table notion by means of two relational systems : The Tarski system T and a statistical system that we shall designate by S.

Attributes of type I

Let us refer to the above Section 2. We retake here the same notations. The considered attributes are the boolean attribute (Section 2.1) and the numerical attribute (Section 2.2). For the boolean attribute describing an object set O, the relative frequency (proportion) p(a) = n(a)/n has been defined and then, the sequence of distributions (96) becomes

(p i a , p i. )|1 ≤ i ≤ I) (97)
where p i a is a proportion defined at the level of the object set O i. . More precisely, consider the subset

O i. (a) of O i.
where a is T RU E and denote by n i. the cardinality of O i. and by n i. (a) the cardinality of O i. (a), we have p i a = n i. (a)/n i. , 1 ≤ i ≤ I. Now, let us consider the case of a numerical attribute v whose distribution was expressed in the above equation [START_REF] Kendall | Rank correlation methods[END_REF]. The distribution sequence can be written

{(x i (l) , f i (l) )|1 ≤ i ≤ I} (98)
where the distribution (x i (l) , f i (l) ) is defined at the level of the object set O i. , 1 ≤ i ≤ I.

Nominal or ordinal categorical attributes

The case of the nominal categorical attribute

This case is particularily instructive. Different representation levels have been considered for this type of attribute (see Section 3.1). The most basic one is defined by [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF]. The latter gives a valuation at the level of the object set O. This valuation assigns to each object o (o ∈ O) a code representing the value c(o) of the categorical attribute c. According to the notations of Section 3.1, we denote by {f i h |1 ≤ h ≤ k} the statistical distribution of c on the set O i. , 1 ≤ i ≤ I. In other words,

f i h = n ih /n i.
is the relative frequency (proportion) of objects from O i. possessing the h th category of the attribute c. As just defined above, n i. = card(O i. ). On the other hand,

n ih = card(O i.h ) where O i.h = c -1 (h) ∩ O i. , 1 ≤ i ≤ I, 1 ≤ h ≤ k.
Thus, the distribution sequence (96) can be put in the following form

({f i h |1 ≤ h ≤ k}, p i. )|1 ≤ i ≤ I (99)
Let us notice here that this data structure is exactly that addressed by Correspondence Analysis and related methods Benzecri (1973) [START_REF] Benz Écri | L'analyse des données[END_REF] (see also Chapters 2 and 6 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF]). Using these techniques have meaning only when k and I are large enough. Now, let us consider the relational representation given by the equations ( 22) to [START_REF] Lerman | Organisation et consultation d'une banque de petites annonces à partir d'une méthode de classification hiérarchique en parallèle[END_REF]. According to the notations of Section 4.4.3, r(π) and s(π) denote the cardinalities of the sets R(π) and S(π), respectively (see [START_REF] Lerman | Classification en présence de variables préordonnances taxonomiques à choix multiple. application à la structuration des phlébotomes de la Guyane Française[END_REF]). The statistical distribution of the indicator function ρ π (see [START_REF] Lerman | Coefficient numérique général de discrimination de classes d ' objets par des variables de types quelconques. application à des données génotypiques[END_REF]) can be put in the following form

(1, r(π) p ), (0, s(π) p ) (100)
where p = card(P ) = n(n -1)/2. Let us denote by π i the partition on O i. induced by the categorical attribute c, namely

π i = O i.h = c -1 (h) ∩ O i. |1 ≤ h ≤ k , 1 ≤ i ≤ I.
r(π i ) (resp., s(π i )) designates the number of object pairs joined (resp., separated) by π i , 1 ≤ i ≤ I. Also, denote by p i = n i. × (n i. -1)/2 the number of object pairs of O i. , 1 ≤ i ≤ I. With these notations, the sequence of the statistical distributions (96) becomes

({(1, r(π i ) p i ), (0, s(π i ) p i )}, p i sump )|1 ≤ i ≤ I (101)
where sump = 1≤i ′ ≤I p i ′ . Indeed, the weighting p i /sump associated with the distribution D i c is obtained in a relative way from the cardinality of the set O i. on which D i c is defined. However, this statistical distribution -defined by the previous equation -is too global in order to compare finely the different categories of Γ (see (93)), represented, respectively, by the sets O i. , 1 ≤ i ≤ I. A discriminant representation has to take into account the decomposition of the sets R(π) and S(π) (see equations ( 29) and ( 30)). In these conditions, the sequence of the statistical distributions (96)

({{f i hh |1 ≤ h ≤ k}, {f i gh |1 ≤ g < h ≤ k}}, p i sump )|1 ≤ i ≤ I (102)
where

f i hh = (n ih × (n ih -1))/(n × (n-)) and f i gh = (n ig × n ih )/(n × (n -1)), 1 ≤ h ≤ k, 1 ≤ g < h ≤ k, 1 ≤ i ≤ I.
The relative frequencies f i hh and f i gh are defined with respect to the set O {2} i.

of unordered object pairs. In Section 4.4.3 a representation in terms of a preordonance attribute was proposed for the nominal categorical attribute. This preordonance was coded from the mean rank function. The statistical distribution of this function (see (87)) refines that (101). We obtain

{( k 2 -k + 2 4 , s(π i ) p i ), ( k 2 + 1 2 , r(π i ) p i )}, p i sump |1 ≤ i ≤ I (103)
However, in spite of this refinement, comparing the categories C i , 1 ≤ i ≤ I of Γ, on the basis of such distributions, remains not discriminant enough. Finally, two statistical relational representations have to be retained for this comparison (99) and (102).

The case of the ordinal categorical attribute

The development of this case follows the same rationale as the preceding one. Assigning to each object of O a category (see ( 20)) provides a representation of the categorical attribute c at the level of O. This representation is defined by a valuation on O. In these conditions (99) is retaken exactly. Therefore, the linear order (32) on the category set C = {c 1 , c 2 , ..., c h , ..., c k } cannot be taken into account. Now, let us consider the relational representation of the categorical attribute c (see equations from [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF] to [START_REF] Suppes | Basic measurement theory[END_REF]). Denote by r(ω

i ) = card[R(ω i )]), e(ω i ) = card[E(ω i )]) and s(ω i ) = card[S(ω i )]
) respectively, the cardinalities defined in [START_REF] Égnier | Sur quelques aspects mathématiques des problèmes de la classification automatique[END_REF] and restricted to the set O i. . Then, denote c i. the cardinality of O [START_REF] Benz Écri | L'analyse des données[END_REF] i. (set of distinct object pairs from O i. ), c i. = n i. × (n i. -1). By considering the score ω function defined in [START_REF] Suppes | Basic measurement theory[END_REF], the sequence of the statistical distribution (96) can be written

{(1, r(ω i ) c i.
), (0.5, e(ω i ) c i.

), (0,

s(ω i ) c i. )}, c i. sumc |1 ≤ i ≤ I (104)
where sumc = 1≤i ′ ≤I c i ′ . This distribution sequence extends to the ordinal case that (101) considered previously for the nominal case. Now, let us consider the extension of the (102) expression in the ordinal case. This expression is written here exactly in the same manner, namely

({{f i hh |1 ≤ h ≤ k}, {f i gh |1 ≤ g < h ≤ k}}, c i sumc )|1 ≤ i ≤ I (105)
where f i hh and f i gh have exactly the same meaning as for the nominal case ; but here they derive from counting ordered pairs of distinct objects.

As an example and also as an exercise consider the table Table 3 below provided from Goodman and Kruskal (1954) [START_REF] Goodman | Measures of association for cross classifications[END_REF]. These data have been already employed for illustration (see Section 3). Table 3 Let us now illustrate the above distribution (104). We suppose as in Section 3.2, the linear order c 1 < c 2 < c 3 for the values of the attribute c. For this illustration we are going to give the contribution of i = 2 to the (104) expression. We have

Preordonance or numerical similarity categorical attributes

In Section 4.1 the preordonance categorical attribute was defined. It has been represented from the mean rank function (see (69)) as a categorical attribute valuated by a specific numerical similarity. This type of attribute was presented in Section 3.4. We have seen that the taxonomic categorical attribute (Section 4.3) is represented as a specific preordonance on the the set of the leaves of the taxonomic tree. Consequently, it suffices, without any loss of generality, to give the form of the distribution sequence (96) in case of a categorical attribute valuated by a numerical similarity. By reconsidering the notations of Section 3.4 with respect to the set of ordered distinct object pairs of O i. , 1 ≤ i ≤ I, we obtain

({{f i hh |1 ≤ h ≤ k}, {f i gh |1 ≤ g = h ≤ k}}, c i sumc )|1 ≤ i ≤ I (107)
where

f i hh = (n ih × (n ih -1))/(n × (n -1)) and f i gh = (n ig × n ih )/(n × (n -1)), 1 ≤ h ≤ k, 1 ≤ g = h ≤ k, 1 ≤ i ≤ I.
c i and sumc have been defined above. The relative frequencies are computed for distinct object ordered pairs. More precisely, f i hh is the relative frequency in O

[2] i. whose value is ξ(c h , c h ), 1 ≤ h ≤ k, f i gh is the relative frequency in O [2]
i. whose value is ξ(c g , c h ), 1 ≤ g = h ≤ k. Let us now illustrate the statistical distribution (106) in the case of our example (see Table 2 andTable 3 5. [START_REF] Chah | Critères de classification sur des donées hétérogènes[END_REF] The data table : a Tarsky system T or a statistical system S

In Sections 2, 3 and 4, the description of a set O of objects by a descriptive attribute a has been defined. Relative to an ordered pair (a, o) constituted by a descriptive attribute a and by an object o, a(o) designates the value of a on o. a is represented by a mapping of O onto the value scale E. We assume that E is endowed with a relation r a . This relation is unary in Section 2 (boolean and numerical attributes), binary in Section 3 (nominal and ordinal categorical attributes, ranking attribute), binary on the set of object pairs in Section 4 (preordonance and taxonomic attributes). Thus, a very large range of attribute description in Combinatorial Data Analysis and in Machine Learning is covered. In addition, any arity of this relation can be handled [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations[END_REF] [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations[END_REF], [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations ii[END_REF] [START_REF] Lerman | Comparing classification tree structures : a special case of comparing q-ary relations ii[END_REF]. r a induces on O a relation that we denote by R a . Thus, the description of O by a can be formalized by the ordered pair (O, R a ).

Generally, for the description of an object set O provided from a universe U of objects (see Section 1) the expert defines a vast set of descriptive attributes. Let us denote by A = {a j |1 ≤ j ≤ p} this set, where p is the number of attributes. Then, the very important notion of a data table T crossing an object set O with an attribute set A can be expressed (see Table 4). O that we denote by {o i |1 ≤ i ≤ n} indexes the row set of T whereas, the attribute set A indexes the column set of T ; A given cell is established at the intersection of the i th row and the j th column, it contains the value a j (o i ), 1 ≤ i ≤ n}, 1 ≤ j ≤ p. As said above, each descriptive attribute induces a relation on the object set O. Let us designate by R j the relation on O defined by the a j attribute. Let us emphasize once again that this relation is induced from the relation which endows the value scale of a j , 1 ≤ j ≤ p. Hence, we associate with the data table T the Tarski system [START_REF] Tarski | Contribution to the theory of models[END_REF] [START_REF] Tarski | Contribution to the theory of models[END_REF].

O A a 1 • • • a j • • • a p o 1 a 1 (o 1 ) • • • a j (
T = O; R 1 , R 2 , ..., R j , ..., R p (109)
where the different relations R j have not necessarily the same arity, 1 ≤ j ≤ p.

In clustering there are two dual problems. The first one which is the most familiar and mostly the only considered consists of organizing by proximity into a classification structure the set O of objects. The concerned proximity notion is global with respect to the different relations R j , 1 ≤ j ≤ p, by integrating all of them. For a given relation R j and two objects o i and o i ′ , the higher the proximity between o i and o i ′ , the more linked they are with respect to the relation R j , 1 ≤ j ≤ p,

1 ≤ i < i ′ ≤ n.
The second problem is dual of the first one. It consists of organizing by proximity into a classification scheme the set A of descriptive attributes ; that is to say and according to our formalism, the set {R j |1 ≤ j ≤ p} of relations on O, associated with the descriptive attributes, respectively. A fundamental task consists in building a proximity notion between two relations R j and R k on O, 1 ≤ j ≤ p. A numerical version of this gives rise to the notion of association coefficient between descriptive attributes [START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles[END_REF][START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles, ii[END_REF]. A complementary and very instructive clustering analysis consists of organizing the whole set of the categories taking part in the different categorical attributes [START_REF] Lerman | Classification des éléments constitutifs d'une juxtaposition de tableaux de contingence[END_REF][START_REF] Tallur | Contribution à l'analyse exploratoire de tableaux de contingence par la classification[END_REF].

The implicit principle of the Likelihood Linkage Analysis (LLA) ascendant hierarchical clustering approach Lerman (1993) [START_REF] Lerman | Likelihood linkage analysis (lla) classification method (around an example treated by hand)[END_REF] is to cluster the set A of descriptive attributes before the set O of the described objects [START_REF] Lerman | Analyse de la vraisemblance des liens relationnels une méthodologie d ' analyse classificatoire des données[END_REF]. An ultimate stage consists of interpreting by crossing techniques each clustering with respect to the other one (see Chapter 3 of [START_REF] Lerman | Classification et analyse ordinale des données[END_REF]), [START_REF] Lerman | Coefficient numérique général de discrimination de classes d ' objets par des variables de types quelconques. application à des données génotypiques[END_REF]. Condition of same arity for the different relations R j , 1 ≤ j ≤ p is required in order to cluster them. In practice and mostly, this condition is brought back Lerman (1992) [START_REF] Lerman | Conception et analyse de la forme limite d'une famille de coefficients statistiques d'association entre variables relationnelles[END_REF] [22], Ouali-Allah (1991) [START_REF] Ouali-Allah | Analyse en préordonnance des données qualitatives[END_REF]. Moreover, statistical homogeneity in the description by the different attributes a j , 1 ≤ j ≤ p, is also an intuitive necessary condition. More explicitly and for example, for a description by nominal categorical attributes, the number of categories by attribute has to be of the same order.

In the LLA approach the two above requested conditions (same arity of the relations R j (1 ≤ j ≤ p) and same statistical homogeneity of the different descriptive attributes) for clustering the set A, are no more required for clustering the object set O [START_REF] Lerman | Construction d ' un indice de similarité entre objets décrits par des variables d ' un type quelconque. application au problème de consensus en classification[END_REF][START_REF] Lerman | Indice probabiliste de vraisemblance du lien entre objets quelconques : analyse comparative entre deux approches[END_REF].

We have presented above the description of a set Γ = {C i |1 ≤ i ≤ I} of categories by an attribute interpreted as a relation on a set of objects. We have associated with the category C i a learning set O i. composed of objects belonging to the category C i , 1 ≤ i ≤ I. If R denotes the relation endowing the value set of the concerned attribute, we have represented R by its statistical distribution on O i. , 1 ≤ i ≤ I. Thus Γ is represented by a sequence of statistical distributions whose general form is defined in (96) (see also (105)). Each distribution is computed for one category. It is weighted according to the relative frequency of the learning set that represents it. Now, assume a set A = {a 1 , a 2 , ..., a j , ..., a p , } of p relational attributes. As expressed above, these define a sequence of p relations on each of the sets O i. , 1 ≤ i ≤ I. We denote by {R 1 i , R 2 i , ..., R j i , ..., R p i } this sequence of relations on O i. , 1 ≤ i ≤ I. Notice that for category description, what is retained from R j i is its statistical distribution on O i. , 1 ≤ j ≤ p, 1 ≤ i ≤ I (see Sections 5.1 to 5.4 when only one set is considered). Thus, we are led to define a system S as follows : S = Γ; R 1 , R 2 , ..., R j , ..., R p (110)

where for each pair (C i , R j ) (C i ∈ Γ), the statistical distribution of R j on C i is estimated on the basis of a learning set O i. , 1 ≤ i ≤ I, 1 ≤ j ≤ p. In these conditions, the data table takes the following form As it was remarked above, the contingency table can be formalized by a system S 1 = (Γ, R 1 ) where only one relation is considered, the latter being defined by a nominal categorical attribute a 1 . R 1 defines a partition on each of the sets O i. , 1 ≤ i ≤ I. Designate by C 1 = {c 1 1 , ..., c 1 g , ..., c 1 h , ..., c 1 k } the category set of a 1 . As said above, this data structure is the main matter of Correspodence Analysis Benzecri (1973) [START_REF] Benz Écri | L'analyse des données[END_REF][START_REF] Lerman | Classification des éléments constitutifs d'une juxtaposition de tableaux de contingence[END_REF][START_REF] Tallur | Contribution à l'analyse exploratoire de tableaux de contingence par la classification[END_REF]. In this approach, basically, the comparison between two categories γ i and γ i ′ of Γ is evaluated from {|f i h -f i ′ h |1 ≤ h ≤ k} where f i h ( resp., f i ′ h ) is the relative frequency in O i. (resp., O i ′ . ) of objects having the category h, 1 ≤ i < i ′ ≤ I. Let us suppose now a structure on the category set C 1 , given for example by a valuated binary relation (see Section 3.4). This structure cannot in anyway be taken into account in the mentioned approach. On the contrary, clustering approach as that given by the LLA method is able to integrate

Γ A a 1 • • • a j • • • a p C 1 D 1 (a 1 ) • • • D 1 (a j ) • • • D 1 (
(val 1 (g, h), f i g × f i h )|1 ≤ g < h ≤ k and (val 1 (g, h), f i ′ g × f i ′ h )|1 ≤ g < h ≤ k (111)
As for the data defined by a Tarski system, it is matter for the data defined by an S system to organize by clustering the set Γ of categories and the set A of descriptive attributes. Clustering A consists of clustering the relation set {R j |1 ≤ j ≤ k} on the basis of estimated statistical distributions on the different categories of Γ (see above). On the other hand and particularily for this structure, a fundamental problem for data analysis consists of clustering the whole set of the categories defined by the different attributes a j , 1 ≤ j ≤ k. Let us notice that we obtain the structure of an horizontal juxtaposition of contingency tables [START_REF] Lerman | Classification des éléments constitutifs d'une juxtaposition de tableaux de contingence[END_REF] [START_REF] Lerman | Classification des éléments constitutifs d'une juxtaposition de tableaux de contingence[END_REF], [START_REF] Tallur | Contribution à l'analyse exploratoire de tableaux de contingence par la classification[END_REF] [START_REF] Tallur | Contribution à l'analyse exploratoire de tableaux de contingence par la classification[END_REF], where the categorical attributes a j , 1 ≤ j ≤ p, are nominal.

To end, let us emphasize the importance of interpreting in a comparative manner a clustering of Γ, a clustering of A and also, a clustering of the set of categories taking part in the definition of A. For this purpose specific tools are studied in [START_REF] Lerman | Coefficient numérique général de discrimination de classes d ' objets par des variables de types quelconques. application à des données génotypiques[END_REF].

( 1 .

 1 5, 2.3, 3.4, 3.4, 3.4, 5.1, 7.2, 7.2, 8.5, 9.0) We suppose from the accuracy measurement of v, only one decimal after the point. The above distribution (12) becomes [(1.5, 0.1), (2.3, 0.1), (3.4, 0.3), (5.1, 0.1), (7.2, 0.2), (8.5, 0.1), (9.0, 0.1)]

Figure 2 Fig. 1 -

 21 Fig. 1 -Histogram

  [a, b[ into subintervals with the same length. By denoting L the length of the interval [a, b[ : L = b -a, we have

  Let C = {c 1 , c 2 , ..., c h , ..., c k } be the value set of a categorical attribute c. No structure is assumed on C. The attribute c is defined by a mappingc : O → {c 1 , c 2 , ..., c h , ..., c k }(20)of O on C, such that for x in O, c(x) = c h if and only if x possesses the value c h , 1 ≤ h ≤ k. c 1 , c 2 , ..., c h , ... and c k are called the categories of the categorical attribute c. The value set C is assumed exclusive and exhaustive. That is to say : each object possesses necessarily and exactly one and only one categorical value. The attribute c induces a partition on O that we denote by

  The definition of this attribute is directly given at the level of the cartesian product O × O where O is the object set. Let us denote by B the binary relation defined by a given attribute. B is represented by the following subset of the cartesian product O × O : R(b) = {(x, y)|(x, y) ∈ O × O and xBy} (59) Additionally, a valuation v on R(b) is considered. v is a mapping of R(b) on the value scale of v, denoted S in the following expression v : R(b) → S (60)

14 × 7 . 5 +

 75 66 × 47.5 + 25 × 93 + 15 × 113 = 7260

  3) we have (4, 4) ∼ (5, 5) ∼ (6, 6) ∼ (7, 7) ∼ (8, 8) ∼ (9, 9) ∼ (10, 10) ∼ (11, 11) ∼ (12, 12) ∼ (13, 13) ∼ (14, 14) > (1, 1) ∼ (2, 2) ∼ (3, 3) > (15, 15)

where 1 -

 1 k ≤ e ≤ k -1. Its cardinality is min(k, k + e) -max(1, 1 + e) + 1(89)

  For a given pair (a, O) composed by a descriptive attribute a of a fixed type and by an object set O described by a we have previously (see the above sections) expressed the statistical distribution of a on O. Here, instead of one only pair (a, O), we have a sequence of such a pair, namely (a, O i. )|1 ≤ i ≤ I (94) where the different sets O i. are mutually disjoint. Let us denote by D i a the statistical distribution of a on O i. . On the other hand, define p i. the relative frequency of the objects belonging to O i. with respect to all the objects belonging to the union of the O i. . Explicitly, Collection des Publications Internes de l'Irisa c IRISA

  p

r(ω 2 )

 2 = card[R(ω 2 )] = 168 × 215 + 168 × 68 + 215 × 68 = 62164 s(ω 2 ) = card[S(ω 2 )] = 215 × 168 + 68 × 168 + 68 × 215 = 62164 e(ω 2 ) = card[E(ω 2 )] = 168 × 167 + 215 × 214 + 68 × 67 = 62164 c 2 = card(O [2] 2. ) = 451 × 450 = 202950 sumc = c 1 + c 2 + c 3 = 379 × 378 + 451 × 450 + 205 × 204 = 388032 c contribution of i = 2 to (104) is {(1, 0.3036), (0.5, 0.3874), (0, 0.3063)}, 0.5230 The statistical distributions (101), (103)or (104) are too global for comparison purpose in case of nominal or ordinal categorical attributes. The most accurate statistical distributions for comparing the categories of Γ (Γ = {A, B, C, D} in the above example), are (102) for the nominal case and (105) for the ordinal one. Illustrating these distributions in the framework of our example is left for the reader.

  }, {a21 , a 22 , ..., a 2k2 }, ..., {a p1 , a p2 , ..., a pkp }, ..., {a q1 , a q2 , ..., a qkq })

			a1									1
			1, a21	2, 15								2
	1, 1	2, 2	3, 3	4, a31				5, a32				3
	1, 4	2, 5	3, 6	4, 7	5, 8	6, 9	1, 10	2, 11	3, 12	4, 13	5, 14	4
					Fig. 3 -Taxonomic attribute
	τ = ({a 1

Table 3 :

 3 is a contingency table crossing two classifications. These are associated with two categorical attributes. In Sections 3.1 and 3.2 we have considered the categorical attribute c : "Highest level of formal education of wife". Its values denoted c 1 , c 2 and c 3 (see Section 3.1) index the columns of the contingency table (see table3). The rows of Table3are indexed by the values of the categorical attribute "Fertility planning status of couple". These values denoted D, C, B and A, are ranked from the lowest level D to the highest one A.Here, I = 4. On the other hand, card(O 1. ) = 379, card(O 2. ) = 451, (O 3. ) = 205 and card(O 4. ) = 403. Crossing between "Fertility planning" and "Highest level of formal education of wife"

	F L	c 1	c 2	c 3	Row totals
	D	223 122 34	379
	C	168 215 68	451
	B	90	80	35	205
	A	110 191 102	403
	Column totals 591 608 239	1438

  ). Consider i = 2. We have n i. × (n i. -1) = 451 × 450 = 202950.

		f 2 11 =	168 × 167 202950	= 0.1382 , f 2 22 =	215 × 214 202950	= 0.2267
	f 2 33 =	68 × 67 202950	= 0.0224
		f 2 12 =	168 × 215 202950	= 0.1780 , f 2 13 =	168 × 68 202950	= 0.0563
		f 2 21 =	215 × 168 202950	= 0.1780 , f 2 23 =	215 × 68 202950	= 0.0720
		f 2 31 =	68 × 168 202950	= 0.0563 , f 2 32 =	68 × 215 202950	= 0.0720
						(108)

Table 4 :

 4 o 1 ) • • • a p (o 1 ) . . . (o n ) • • • a j (o n ) • • • a p (o n ) Data table T

		. . .	. . .	. . .	. . .	. . .
	o i	a j (o i )	. . .	a j (o i )	. . .	a p (o i )
	. . .	. . .	. . .	. . .	. . .	. . .
	o n	a 1

Table 5 :

 5 I (a 1 ) • • • D I (a j ) • • • D I (a p ) Data table S

	a p )

Collection des Publications Internes de l'Irisa c IRISA

(i.e. any attribute can be derived from the others) Collection des Publications Internes de l'Irisa c IRISA

The ordinal similarity between cg and c h is the same as that between c h and cg, 1 ≤ g ≤ h ≤ k.Collection des Publications Internes de l'Irisa c IRISA