Julien Ah-Pine

Jean-Franc ¸ois Marcotorchino

Overview of the Relational Analysis approach in Data-Mining and Multi-criteria Decision Making

Overview of the relational analysis approach in data-mining and multi-criteria decision making

Julien Ah-Pine, Jean-François Marcotorchino

General scope

In this chapter we introduce a general framework called the Relational Analysis approach and its related contributions and applications in the fields of data analysis, data mining and multi-criteria decision making. This approach was initiated by J.F. Marcotorchino and P. Michaud at the end of the 70's and has generated many research activities. However, the aspects of this framework that we would like to focus on are of a theoretical kind. Indeed, we are aimed at recalling the background and the basics of this framework, the unifying results and the modeling contributions that it has allowed to achieve. Besides, the main tasks that we are interested in are the ranking aggregation problem, the clustering problem and the block seriation problem. Those problems are combinatorial ones and the computational considerations of such tasks in the context of the RA methodology will not be covered. However, among the list of references that we give thoughout this chapter, there are numerous articles that the interested reader could consult to this end.

In order to introduce the Relational Analysis approach (denoted "RA" in the rest of the document), let us first introduce several problems that one could encounter in the data analysis field. To this end, let us consider a data table concerning a set of N objects O = {O 1 , . . . ,O i , . . . ,O N } described by a set of M variables V = {V 1 , . . . , V k , . . . , V M }. These data can be represented using a (N × M) feature matrix denoted T given by the following eqs. ( 1) and ( 2); ∀i = 1, . . . , N; k = 1, . . . , M:

T ik = V k i = Numerical value assigned to object O i according to V k (1)
T =            V 1 V 2 . . . , V k . . . V M O 1 V
O N V 1 N V 2 N . . . V k N . . . V M N            (2)
Depending on the nature of the features of T, we can list the different following problems tackled in the data analysis field and related domains:

• The variables in V can correspond to M criteria that give M different rankings on the objects O. In that case, the objects could be N different alternatives. Then, one can be interested in finding a consensual ranking that "sums up" these M different rankings in order to determine the best (the most consensual) alternative 1 . This task is known as the ranking aggregation problem and it can be encountered in other domains, than data analysis, such as social choice theory, multi-criteria decision making or multi-agent systems.

• The variables in V can be categorical 2 variables. In that case, one can be motivated by discovering patterns among the set of objects O. In other words, one would want to find a partition such that objects belonging to the same cluster have high similarities and objects belonging to different clusters have low similarities. This problem, known as the clustering problem, is studied in statistical data analysis, and data-mining fields and it has many applications such as customer relationship management, text mining or web data clustering for instance.

• Finally, one could also be interested in finding a bi-partition which simultaneously decompose both sets O and V. In that context, a bicluster is the association of a cluster of objects and a cluster of variables. This task is known as the biclustering or block seriation problem and it is studied notably in gene-mining or in group technology problems for example.

The previously mentioned problems are often modeled and solved by means of different approaches. One of the main advantages of the method presented here, is that it allows to synthesize in a unique formal way, all those different data analysis tasks, as particular cases of a general model. In the RA framework, those different problems can be formalized as binary relations aggregation problems. Departing from the feature matrix T, the different aforementioned tasks, can be seen as finding a consensual binary relation that aggregates and summarizes a set of individual binary relations (the variables) of T.

We briefly give in what follows some illustrative examples:

• When the variables V k ; k = 1, . . . , M, are numerical criteria, they induce M different rankings R k ; k = 1, . . . , M, on the set of alternatives O. These rankings are order relations (partial or total orders) and the solution we look for is a consensual relation R (a total order for example) that fits "as good as possible", the M individual rankings.

• When the variables V k ; k = 1, . . . , M, are categorical features, the latter induce M different partitions R k ; k = 1, . . . , M, of the set of objects. Clustering those objects can thus be seen as looking for a consensual partition (or an equivalence relation) R, that sums up the M individual partitions.

• When the feature matrix T consists of 0/1 values such as indicator tables that encode categorical variables, the biclustering problem amounts to determine a bi-partition of objects and categories. This problem can also be interpreted as the search for a consensual relation R. This kind of relation is called a "block seriation" relation.

The RA approach uses algebraic concepts related to binary relations in order to turn the previously mentioned problems into binary relations aggregation problems. Basically, if we denote by R k the binary relation associated to a variable V k , then all the aforementioned problems could be seen as a particular instance of the following problem:

max R Aggreg(R 1 , . . . , R k , . . . , R M ; R) ( 3
)
where Aggreg is an aggregation procedure.

One of the main characteristics of the RA methodology is to use pairwise comparisons matrices similar as adjacency matrices in order to represent binary relations. We will see that the representation of binary relations through that coding has many properties. The second principle of the RA approach consists in using a criterion called "the Condorcet's criterion" as a global measure of consensus. This criterion has its origins in mathematical social sciences and was first studied in its literal form by A. de Condorcet in 1785. This criterion is nothing but a voting criterion, which was applied first to the ranking aggregation problem. It was shown that this criterion satisfies many axioms in the context of social choice theory. The Condorcet's criterion was, then, extended to the partitions aggregation problem. Therefore it can be interpreted as a partitioning criterion as well. The RA approach notably contributed to show that the ranking aggregation problem and the clustering one were particular cases of a unique model, as we will show in the next paragraphs.

The rest of this chapter is organized as follows. In section 2, we basically recall some key properties of the RA approach: the individual relational matrices, that represent individual binary relations; the collective relational matrix, that is aimed at aggregating the individual binary relations in a simple yet efficient way; the relational properties of binary relations that can be expressed as linear inequalities or equalities using relational matrices; and the general expression of the Condorcet's criterion. In section 3, 4, 5, we respectively detail the applications of the RA approach in ranking aggregation problems, clustering problems, and block seriation problems. Particularly, in the RA framework, all these problems are modeled using the same formalism, based on 0/1 integer linear programming. Recently, "Correlation Clustering" (CC) problems were proposed in [START_REF] Bansal | Correlation clustering[END_REF]. This setting tackles the clustering problem from a graphic point of view and has many relationships with different concepts underlined in the RA approach. Indeed, the partitioning criterion used in the CC approach is very similar to the Condorcet criterion. Moreover, the linear program used by this approach for modeling the clustering problem (see for example [START_REF] Demaine | Correlation clustering with partial information[END_REF], ( 22), ( 18)), is the same as in the RA method. Accordingly, we also introduce in section 6, other results of interest obtained in the clustering field by using the RA method in order to strengthen the graphical and the linear programming point of views for addressing clustering problems.

Introduction to the Relational Analysis approach

We first recall some previous contributions concerning the analysis of relational data, that is to say, data which have particular structures such as binary relations: order relations, equivalence relations or graph relations in general. There has been a growing interest for such kinds of data since the end of the 70's.

Concerning order relations, Condorcet's work opened up the mathematical field of decision making in the social sciences [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF]. In France, A. de Condorcet's work got a particular interest in the 80's, rediscovered and updated by J.F. Marcotorchino and P. Michaud [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF], [START_REF] Michaud | Condorcet: A man of the avant-garde[END_REF], B. Monjardet, J.P. Barthélémy and B. Leclerc (8), [START_REF] Leclerc | Latticial theory of consensus[END_REF]... In the USA, we can also mention the Nobel Prize's laureate, K.J. Arrow who has contributed to the social choice theory [START_REF] Arrow | Social choice and individual values 2nd ed[END_REF] and also the book of Kemeny and Snell (23) in mathematical sciences as well.

Concerning equivalence relations (categorical data), since this type of data has been mostly studied by statisticians and data analysts, it is an other set of contributors which has to be quoted. We can firstly mention S. Régnier [START_REF] Régier | Sur quelques aspects mathématiques des problèmes de classification automatique[END_REF], I.C. Lerman (27) and J.F. Marcotorchino and P. Michaud [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF], on the french side. Apart from french researchers, we can particularly mention H.T. Zahn's work [START_REF] Zahn | Approximating symmetric relations by equivalence relations[END_REF] as well as B. Mirkin's work, see [START_REF] Mirkin | Approximation problems in space of binary relations and analysis of non quantitative characteristics[END_REF] for example.

Obviously, this is not an exhaustive reference list of scientists who have contributed to this area. We have only mentioned some main papers that are closely related to the approach proposed by the RA framework.

The RA methods, presented here, are mainly the approaches, studied and developed by J.F. Marcotorchino and P. Michaud and colleagues. Their work is essentially based upon the study of relational data from the graph theory, the statistical and the integer linear programming standpoints [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF], [START_REF] Michaud | Optimisation en analyse de données relationelles[END_REF].

First of all, let us recall basic definitions about binary relations. We can also associate to R, its complement which is a binary relation denoted by R and which is the subset of the cartesian product O × D such that (O i , D j ) / ∈ G(R).

When D = O, we talk about binary relations on a single set O. This particular kind of binary relations is of interest and it will be referred as (O, G(R)).

There exist different properties that a binary relation (O, G(R)) can satisfy. Among all those relational properties, the most useful ones are given in Table 1.

Those properties allow us to characterize the type of a binary relation (O, G(R)). We have the following definitions:

• A preorder is a binary relation that is reflexive and transitive.

• A strict total order is a binary relation that is irreflexive, asymmetric, transitive and total.

• An equivalence relation is a binary relation that is reflexive, symmetric, and transitive.

Relational

Logical property definition

Reflexivity

O i RO i ∀ O i ∈ O Irreflexivity O i R k O i ∀ O i ∈ O Symmetry O i RO i ⇒ O i RO i ∀ (O i ,O i ) ∈ O 2 Asymmetry O i RO i ⇒ O i R k O i ∀ (O i ,O i ) ∈ O 2 : O i = O i Transitivity O i RO i ∧ O i RO i ⇒ O i RO i ∀ (O i ,O i ,O i ) ∈ O 3 Totality O i RO i ∨ O i RO i ∀ (O i ,O i ) ∈ O 2 : O i = O i Table 1. Relational properties for (O, G(R))
After recalling briefly, basic concepts inherent to binary relations, we now present how the RA approach copes with such data structures.

The first principle of the RA methodology amounts to represent binary relations as pairwise comparisons matrices, called "relational matrices", which are made of 0/1 values. Let (O, G(R)) be a binary relation on a single set O, where #O = N. Then in the RA method, we represent this binary relation by its (N × N) relational matrix4 X where, ∀i, i = 1, . . . , N:

X ii = 1 if O i RO i 0 otherwise (4)
Using the RA formalism, we can easily define the relational matrix X, associated to the complement of the relation (O, G(R)). Indeed, we have, ∀i, i = 1, . . . , N:

X ii = 1 -X ii (5)
In the block seriation problems, we are no longer faced with relations on the same set, as previously done, but we will consider, in that case, binary relations on two different sets (O, D, G(R)).

For clarity reasons, we will use other notations for that type of binary relations. Suppose that, #O = N and #D = P; then the relational matrix that represents the binary relation is the (N × P) binary matrix Z, where, ∀i = 1, . . . , N; j = 1, . . . , P:

Z ij = 1 if O i RD j 0 otherwise (6)
The representation of binary relations by using pairwise comparison matrices allows to express the relational properties as linear equations. This is a strong property of the RA formalism. We give in Table 2, the linear equations related to the relational properties already presented in Table 1.

Relational

Linear equations using properties the relational matrix

Reflexivity X ii = 1 ∀i = 1, . . . , N Irreflexivity X ii = 0 ∀i = 1, . . . , N Symmetry X ii = X i i ∀i, i = 1, . . . , N Asymmetry X ii + X i i ≤ 1 ∀i, i = 1, . . . , N : i = i Transitivity X ii + X i i -X ii ≤ 1 ∀i, i , i = 1, . . . , N Totality X ii + X i i ≥ 1 ∀i, i = 1, . . . , N : i = i
Table 2. Relational properties as linear equations in the RA formalism for (O, G(R)) binary relations

The second principle of the RA approach is the use of Condorcet's criterion as an association and consensus criterion. This criterion is based upon a similarity or association measure between objects, and a dissimilarity or non association measure between the same items as well.

Let us call respectively, A and A, the matrices associated to relation 5 and to non relation 6between pairs of objects. Then the Condorcet's criterion applied to binary relations on a single set is given as follows:

Condorcet(A, A, X) = N ∑ i=1 N ∑ i =1 A ii X ii + A ii X ii (7)
For the case of binary relations on two different sets 7 , we have:

Condorcet(A, A, Z) = N ∑ i=1 P ∑ j=1 A ij Z ij + A ij Z ij (8)
As we can see, the Condorcet's criterion is a quite "logical" criterion: it measures the total agreements ("positive" and "negative" agreements) between two relations. Likewise, the greater the values of A ij (resp. A ij ), the more (resp. less) likely objects O i and D j should be in relation from a consensus standpoint.

The ranking aggregation problem

The ranking aggregation problem consists in looking for a consensual ranking (or order relation) on a set of objects (or alternatives) that summarizes a set of individual rankings (or a set of several criteria). This problem was firstly mathematically addressed by A. de Condorcet [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF] in the context of voting theory and decision making. Historically, it is the first background of the RA approach and the first consistent foundation of such a theoretical framework.

The first aspect of this task consists in aggregating individual rankings in a natural manner. Indeed, suppose that we have items who are described by two real continuous quantitative variables such as their height (in centimeters) and their weight (in kilograms). These two real continuous quantitative variables induce a ranking among the items (the smallest to the tallest for example). How can we compute a consensual ranking that could efficiently summarize the rankings given by the height and the weight ?

In statistics, suppose we want to measure a central trend for the variable "height", it is then possible to compute the mean of this variable for instance. While computing the mean, we have to sum up the heights over all the items and we divide the obtained value by N.

Here, the addition is possible because we aggregate "centimeters with centimeters". On the contrary, it is not obvious to aggregate for each item, his height and his weight. Indeed, it is a non sense to add centimeters with kilograms. Thus, how could we proceed to aggregate both variables ?

In order to answer this question, the RA suggests to compute the relational matrices associated to the individual rankings induced by the real continuous quantitative variables. Let us suppose that we have M real continuous quantitative variables denoted by V k ; k = 1, . . . , M. Let V k i be the value assigned to item O i with respect to variable V k . Then, for each variable, we can associate its following relational matrix:

C k ii = 1 if V k i ≤ V k i 0 otherwise (9)
For example we build up a relational matrix as follows:

V k O 1 0.5 O 2 0.2 O 3 0.6 O 4 0.9 →     O 1 O 2 O 3 O 4 O 1 1 0 1 1 O 2 1 1 1 1 O 3 0 0 1 1 O 4 0 0 0 1     (10)
Considering the M individual relational matrices, the relation aggregation procedure becomes possible: it is just given by the sum over all the individual relational matrices. By doing so, we define the collective relational matrix also called the "collective Condorcet's matrix", denoted C. The general term of the latter matrix is given by:

C ii = M ∑ k=1 C k ii = Nb of variables for which O i has a lower rank than O i (11)
Similarly, we can also define the collective relational matrix C related to the aggregation of the M individual relational matrices C k where:

C ii = M ∑ k=1 C k ii =
Nb of variables for which O i has not a lower rank than O i

This aggregation process that we have just introduced, gives a partial answer to the initial problem represented by eq. ( 3). It gives a subsequent process for aggregating order relations in a natural manner. But now that we have aggregated the different rankings, how can we determine a consensual ranking R that agrees as much as possible with the M individual rankings ?

In the RA methodology, the consensus ranking is the one that maximizes the Condorcet's criterion where

A ii = C ii and A ii = C ii : Condorcet(A, A, X) = N ∑ i=1 N ∑ i =1 C ii X ii + C ii X ii (13)
Replacing X ii with 1 -X ii and selecting only the part of the criterion which is dependent on X, we then have the following Condorcet's criterion:

Condorcet(C, C, X) = N ∑ i=1 N ∑ i =1 C ii -C ii X ii (14)
This means that O i should have more chances to have a lower rank than O i in the consensual ranking 8 , if the number of variables that give a lower rank to O i than to O i is greater or equal than the number of variables that give a higher rank to O i than to O i .

If we suppose, moreover, that there is no missing rank value among the individual rankings, then we have:

C ii = M -C ii .
If we take into account this expression in eq. ( 14), then we obtain the following simplified Condorcet's criterion:

Condorcet(C, X) = N ∑ i=1 N ∑ i =1 C ii - M 2 X ii (15)
In the particular case where we do not have any missing value, the consensual ranking will more likely give to O i a rank lower than to O i9 , provided that the number of variables or criteria which ranked O i before O i is greater or equal to the simple majority.

If we simply apply the previous rule we will observe a paradoxical situation most of the time. Indeed, aggregating order relations using the simple majority decision rule does not guarantee to obtain an order relation as a solution 10 . This is the famous "Condorcet's paradox", which states that if a majority of voters prefer "i" to "j" and a majority of voters prefer "j" to "k", it could happen that a majority of voters prefer "k" to "i", thus violating the transitivity condition. Consequently the real problem, we want to solve is now based upon the following key question: how can we determine the strict total order relation that maximizes the Condorcet's criterion ? This problem is unfortunately not so simple, since it is an NP-hard problem [START_REF] Wakabayashi | On the complexity of computing medians of relations[END_REF]. Without any algorithmic process, it would need a complete enumeration of all the N! possible solutions to get the final result (by the way, just for N=70, notice that 70!≈ 1.2 100 ). Thanks to the RA approach we can solve the ranking aggregation problem, through an 0/1 integer linear programming approach. Furthermore, it is also possible to use a simpler model, based upon binarity relaxation scheme by considering 0 ≤ X ii ≤ 1. In that case, we could use continuous linear programming technique and the "dual of dual process" described in [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF] for instance.

According to Table 1, the use of pairwise comparisons matrices allows to turn the relational properties, characterizing an order relation, into linear constraints. Furthermore, once we are given A and A, we can see that the Condorcet's criterion is a linear objective function with respect to X, the solution we are looking for. As a result, we can model the ranking aggregation problem by maximizing a linear consensus criterion subject to linear constraints. Hence, we can get the exact optimal solution using an integer linear programming solver as mentioned beforehand and as described in ( 36), ( 41), [START_REF] Michaud | Opinions aggregation[END_REF]:

max X Condorcet(A, A, X) st X ii ∈ {0, 1} (binarity) X ii + X i i ≤ 1 ∀i, i = 1, . . . , N : i = i (asymmetry) X ii + X i i ≥ 1 ∀i, i = 1, . . . , N : i = i (totality) X ii + X i i -X ii ≤ 1 ∀i, i , i = 1, . . . , N (transitivity)
We have presented the general model to solve the ranking aggregation problem using the RA methodology. In eq. ( 16), X must respect the linear constraints of a strict and total order, but other types of order relations could also be modeled in a similar way. The interested reader could find in ( 41), (2), other relational properties and their associated linear equations (in terms of the RA formalism).

Other works, related to the ranking aggregation problem, can be found in ( 4), ( 21), ( 47) or [START_REF] Barthélémy | Median linear orders: heuristics and a branch and bound algorithm[END_REF] for example. In those papers, the ranking aggregation problem, which is also referred as the "median linear ordering problem" or shortly the "linear ordering problem"; is treated from a combinatorial optimization viewpoint. For a study of the complexity of problems like relations aggregation, see [START_REF] Wakabayashi | On the complexity of computing medians of relations[END_REF] for instance.

Among the different contributions in ranking aggregation problems, for which RA approach was used as a basic concept, special attention must be paid to the results obtained by S. Ghashghaie in [START_REF] Ghashghaie | Agrégation relationnelle des données ordinales: généralisation de critères d'association[END_REF]. In this work, it is shown that statistical association criteria for comparing rankings such as Goodman and Kruskal, Somers, Kendall, Deuchler and Kim; differ from the Condorcet's criterion, just by slight changes. We can also mention the following reference too [START_REF] Giraud | Comparaison de règles d'agrégation d'ordres et études de règles multicritères d'aide à la décision[END_REF], where the author provides a theoretical and axiomatic comparison of Condorcet's criterion against other aggregation criteria.

The clustering problem

The RA methodology is still valid when we want to consider other relations and aggregation problems than the ranking aggregation task.

From an algebraic point of view, we can observe that the only difference between a linear order and an equivalence relation mainly consists in replacing the asymmetry property with the symmetry one. From this observation, J.F. Marcotorchino and P. Michaud extended the 0/1 integer linear programming that optimally solves the rank aggregation problem to the similarities aggregation problem (41), [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF]. Hence, we get the second main application of the RA methods in data analysis: modeling the clustering of categorical data problem as a linear program.

Suppose that we have at our disposal (N × N) matrices A and A of pairwise similarities and dissimilarities between pairs of objects that we want to cluster. Then we can use the Condorcet's criterion as a clustering function similarly as for the ranking aggregation:

Condorcet(A, A, X) = N ∑ i=1 N ∑ i =1 A ii X ii + A ii X ii = N ∑ i=1 N ∑ i =1 A ii -A ii X ii + N ∑ i=1 N ∑ i =1 A ii (17)
If we consider the part of eq. ( 17) which is only a function of X, we can notice that maximizing the Condorcet's criterion in the clustering task, consists in putting 11 objects O i and O i in the same cluster 12 if their measure of similarity A ii is higher than their measure of dissimilarity

A ii .
Given A and A, then looking for a partition which is represented by a relational matrix X and which is aimed at maximizing the Condorcet's criterion, can be obtained by means of 0/1 integer linear programming ( 41), ( 37), ( 32), [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF].

max X Condorcet(A, A, X) st X ii ∈ {0, 1} (binarity)
X ii = 1 ∀i = 1, . . . , N (reflexivity) X ii -X i i = 1 ∀i, i = 1, . . . , N : i = i (symmetry) X ii + X i i -X ii ≤ 1 ∀i, i , i = 1, . . . , N (transitivity)
This model is particularly adapted for clustering objects, described by categorical variables 13 . Hence, the same aggregation method introduced beforehand for dealing with orders relation can be applied here as well.

Suppose that we have M categorical variables denoted by V k ; k = 1, . . . , M, and let denote by V k i the class of V k assigned to object O i . Then each variable induce an equivalence relation on the objects. As a result, we can associate to each V k a relational matrix C k :

C k ii = 1 if V k i = V k i 0 otherwise (19)
For instance, we can get the following relational matrix:

V k O 1 blue O 2 brown O 3 brown O 4 blue →     O 1 O 2 O 3 O 4 O 1 1 0 0 1 O 2 0 1 1 0 O 3 0 1 1 0 O 4 1 0 0 1     (20)
Just by considering the M individual relational matrices, we can, as for order relations, aggregate equivalence relations by summing up the individual relational matrices. We then define the collective relational matrix which general term is given by:

C ii = M ∑ k=1 C k ii =
Nb of variables for which O i and O i are in the same cluster [START_REF] Gr Ötschel | A cutting plane algorithm for the linear ordering problem[END_REF] We can also define the collective relational matrix C related to the aggregation of the individual relational matrices C k where:

C ii = M ∑ k=1 C k ii =
Nb of variables for which O i and O i are not in the same cluster [START_REF] Joachims | Error bounds for correlation clustering[END_REF] Similarly to the previous section, if we take A = C and A = C and if we replace X ii with 1 -X ii then we first obtain:

Condorcet(C, C, X) = N ∑ i=1 N ∑ i =1 C ii -C ii X ii (23)
Secondly, if we suppose that there is no missing value then we have, C ii = M -C ii , and the following simplified Condorcet's criterion:

Condorcet(C, X) = N ∑ i=1 N ∑ i =1 C ii - M 2 X ii (24)
Maximizing the Condorcet's criterion in order to cluster categorical data, amounts to highly consider to put O i and O i in the same cluster 14 of the consensus partition 15 , if the number of variables considering that O i and O i are in the same cluster is higher than the number of variables considering that O i and O i are not in the same cluster. Moreover, if there is no missing value then it is equivalent to say that O i and O i are more likely in the same cluster of the consensual partition, if the number of variables indicating that O i and O i are in the same cluster is greater or equal to the simple majority M 2 of the total number of variables.

Here, it is worth mentioning that the integer linear program given in eq. ( 18) does not require as an "a priori" hypothesis, the knowledge of the expected number of clusters of the partition we are looking for. This is quite an attractive and interesting property of the RA approach in the clustering context: the number of clusters obtained solving eq. ( 18) is an optimal inherent value according to Condorcet's criterion.

There are other problems related to the clustering task that have been studied in the context of the RA framework. We quote here some references 16 . In [START_REF] Chah | Nouvelles techniques de codage d'association et de classification[END_REF], the RA approach is used for studying binary relations over triples of objects. This work led to the definition of association and partitioning criteria for heterogeneous data. In [START_REF] Bédécarrax | Relational analysis and dictionnaries[END_REF], an application in computational linguistics is proposed and particularly for the automatic building of synonyms dictionaries. We can also mention other theoretical contributions from ( 8), [START_REF] Owsinski | Optimization in clustering: an approach and other approaches[END_REF], or (50) for example.

More recently, the "Correlation Clustering" (CC) method has been proposed by G. Bansal and al in [START_REF] Bansal | Correlation clustering[END_REF]. The similarity matrix, considered here, is built up as follows: we put 1 if objects O i and O i are considered as similar and -1 otherwise. In terms of the notations presented in this chapter, this corresponds to the particular case where A ii = 1 if O i and O i are similar and A ii = 1 if they are not. In [START_REF] Demaine | Correlation clustering with partial information[END_REF], the linear program used for approximating the clustering problem is equivalent to eq. ( 18) except that the unknown relational matrix is X with general term X ii = 1 -X ii . This latter representation leads to a distance relation which is irreflexive, symmetric and which satisfies the "triangle inequality" which is the exact dual of the transitivity property 17 . In a recent work, L. Labiod [START_REF] Labiod | Contribution au formalisme relationnel des classifications simultanes de deux ensembles[END_REF] has studied the possible connections between the CC methods, the N-Cuts methods and other clustering functions and the RA approach. Accordingly, his conclusions corroborate the fact that the Condorcet's criterion is a central and focal concept.

The block seriation problem

Let us consider the case where we have as an input, a (N × P) 0/1 indicator table K. Then in its original form, the problem of seriation consists in finding two permutations, the first one τ, corresponding to a permutation of the rows of K, and the other one σ, corresponding to a permutation of the columns of K; such that a dense structure "appears" along the diagonal of the permuted K . A simple example is given below:

K =           D 1 D 2 D 3 D 4 D 5 D 6 D 7 D 8 D 9 O 1 1 0 0 1 0 0 1 0 0 O 2 1 0 0 0 1 0 0 1 0 O 3 1 0 0 1 0 0 1 0 0 O 4 0 1 0 0 1 0 0 1 0 O 5 0 1 0 0 1 0 0 1 0 O 6 0 0 1 0 1 0 0 0 1 O 7 0 0 1 0 0 1 0 0 1           ↓ (τ, σ) K =           D 1 D 4 D 7 D 2 D 8 D 5 D 3 D 6 D 9 O 1 1 1 1 0 0 0 0 0 0 O 3 1 1 1 0 0 0 0 0 0 O 2 1 0 0 0 1 1 0 0 0 O 4 0 0 0 1 1 1 0 0 0 O 5 0 0 0 1 1 1 0 0 0 O 6 0 0 0 0 0 1 1 0 1 O 7 0 0 0 0 0 0 1 1 1           (25)
In a more general perspective, let suppose that we have two (N × P) matrices, A and A, such that A ij gives the "strength" of the relation O i RD j and A ij gives the "strength" of the relation O i RD j , ∀i = 1, . . . , N; j = 1, . . . , P. For example, considering the previous example, we can take

A ij = K ij and A ij = 1 -K ij .
Let us moreover denote by P = P 1 ∪ . . . ∪ P k ∪ . . .

P κ and Q = Q 1 ∪ . . . ∪ Q k ∪ . . . Q κ ,
two partitions with regards to the set of objects O and the set of descriptors D. These two partitions have the same number of clusters κ. Then, the block seriation problem can be reshaped under the maximization of the following criterion:

F(κ, P, Q) = κ ∑ k=1     ∑ O i ∈ P k D j ∈ Q k A ij + ∑ O i ∈ P k D j / ∈ Q k A ij     (26)
We can see that the solution κ = 3;

P 1 = {O 1 ,O 3 }, P 2 = {O 2 ,O 4 ,O 5 }, P 3 = {O 6 ,O 7 } and Q 1 = {D 1 , D 4 , D 7 }, Q 2 = {D 2 , D 8 , D 5 }, Q 3 = {D 3 , Dv,O 9
}; is the triple that maximizes the criterion considering the example given in eq. ( 25).

We can therefore define the two following assignment matrices:

P ik = 1 if O i belongs to P k 0 otherwise (27)
Q jk = 1 if D j belongs to Q k 0 otherwise (28)
Using those assignment matrices, the problem can be re-stated as follows:

max κ,P,Q F(κ, P, Q) = ∑ κ k=1 ∑ N i=1 ∑ P j=1 A ij P ik Q jk + ∑ N i=1 ∑ P j=1 A ij P ik (1 -Q jk ) st P ik ∈ {0, 1} ∀i = 1, . . . , N; k = 1, . . . , κ Q jk ∈ {0, 1} ∀i = 1, . . . , N; k = 1, . . . , κ ∑ κ k=1 P ik = 1 ∀i = 1, . . . , N ∑ κ k=1 Q jk = 1 ∀j = 1, . . . , P (29)
There are N + P linear constraints but the criterion that we have to maximize is quadratic according to P ik Q jk thus we cannot use integer linear programming solvers.

But, considering the criterion given in eq. ( 29), one can distribute the sum over k into the brackets and introduce the following variable ( 33), (

Z ij = ∑ κ k=1 P ik Q jk = 1 if O i and D j belong to the same block 0 otherwise 35):
For example, according to this variable, the optimal solution corresponding to the example given previously is the following one (to be clear we give this solution according to permutations τ and σ):

Z =           D 1 D 4 D 7 D 2 D 8 D 5 D 3 D 6 D 9 O 1 1 1 1 0 0 0 0 0 0 O 3 1 1 1 0 0 0 0 0 0 O 2 0 0 0 1 1 1 0 0 0 O 4 0 0 0 1 1 1 0 0 0 O 5 0 0 0 1 1 1 0 0 0 O 6 0 0 0 0 0 0 1 1 1 O 7 0 0 0 0 0 0 1 1 1           (31)
For instance we can see that the first block constituted of (P 1 ; Q 1 ) is given by ({O 1 ,O 3 }; {D 1 , D 4 , D 7 }) and all terms of Z corresponding to the Cartesian product {O 1 ,O 3 } × {D 1 , D 4 , D 7 } are assigned 1.

The (N × P) binary matrix Z is interpreted as a relational matrix associated to a binary relation on two sets O and D. The important facts are that this approach firstly allows us to have a criterion that is independent of κ and which is linear according to Z, and secondly, it is possible to express the relational properties of this particular relation using linear equations.

These linear equations were given in (33):

∑ P j=1 Z ij ≥ 1 ∀i = 1, . . . , N ∑ N i=1 Z ij ≥ 1 ∀j = 1, . . . , P        Z ij + Z i j + Z ij -Z i j ≤ 2 Z ij + Z i j + Z i j -Z ij ≤ 2 Z ij + Z ij + Z i j -Z i j ≤ 2 Z i j + Z ij + Z i j -Z ij ≤ 2 ∀i = 1, . . . , N (32)
These four latter constraints are called "impossible triads": "at the crossing of two rows and two columns of Z, one cannot get a "1" value three times". More precisely, let us suppose that for the optimal solution, Z ij = 1, that is to say, O i and D j are in the same block. If furthermore, Z ij = 1 and Z i j = 1 then we must also have Z i j = 1. In other words, if O i is in the same block as D j and D j , and if O i is in the same block as D j then O i should be in the same block as D j .

Using the binary relation formalism, we can see that we can also obtain the relational matrix Z by means of integer linear programming solver:

max Z Condorcet(A, A, Z) st Z ij ∈ {0, 1} (binarity)
∑ P j=1 Z ij ≥ 1 ∑ N i=1 Z ij ≥ 1 ∀i = 1, . . . , N ∀j = 1, . . . , P (assignment)
       Z ij + Z i j + Z ij -Z i j ≤ 2 Z ij + Z i j + Z i j -Z ij ≤ 2 Z ij + Z ij + Z i j -Z i j ≤ 2 Z i j + Z ij + Z i j -Z ij ≤ 2
∀i, i = 1, . . . , N ∀j, j = 1, . . . , P (impossible triads)

Let us recall that the Condorcet's criterion under its general form, is given as follows:

Condorcet(A, A, Z) = N ∑ i=1 P ∑ j=1 A ij Z ij + A ij Z ij (34)
If A = K, K being an indicator table, commonly used in categorical data analysis, then the block seriation model given in eq. ( 33) gives rise to a biclustering method for this type of table. In this particular case, we have A ij = 1 -K ij and by replacing Z ij with 1 -Z ij , we obtain the following simplified Condorcet's criterion:

Condorcet(K, Z) = N ∑ i=1 P ∑ j=1 K ij - 1 2 Z ij (35)
We have highlighted the RA approach for biclustering tasks in the particular case of 0/1 data type but, the proposed method can be straightforwardly extended to other types of data such as real continuous quantitative data. In that case, matrices A and A18 are required.

Block seriation models, through their relational formalism, have generated many research works, both for theoretical and practical purposes. We can quote as an illustrative example C. Bédécarax's Phd Thesis [START_REF] Bédécarrax | Classification automatique en analyse relationnelle: la quadridécomposition et ses applications[END_REF] where is defined a more general framework called "quadridecomposition". From that general model, the above mentioned clustering problems 19 are in fact structural derivatives. Besides, "quadri-decomposition" modeling was successfully applied to the automatic building of dictionaries in computational linguistics see [START_REF] Bédécarrax | Relational analysis and dictionnaries[END_REF]. Furthermore, in order to take into account large amount of data, several heuristics have been developed and the interested reader could consult [START_REF] Mutel | Application of relational analysis techniques to production data structuring[END_REF] for such algorithms and also [START_REF] Garcia | Group technology in production management[END_REF] for an application to production management optimization.

Other results of the RA method in the context of clustering problems

In the analysis of equivalence relations, the RA approach has allowed other interesting contributions.

The first one, concerns the study of numerous "association criteria" crossing categorical variables 20 such as Belson, Lerman, χ 2 of Tchuprow, Jordan, Rand and Janson and Vegelius indexes for instance. Suppose that we have at our disposal two categorical variables V k and V l with respectively p k and p l categories. Then the previous association criteria are basically defined using the (p k × p l ) contingency table n kl where ∀(u, v) ∈ {1, . . . , p k } × {1, . . . , p l }:

n kl uv = Nb of objects that have both category D u of V k and category D v of V l (36)
Relational matrices such as C k and C l , are other ways to encode categorical variables. Following some previous contributions from M.G. Kendall [START_REF] Kendall | Rank correlation methods[END_REF], J.F. Marcotorchino in ( 28), ( 29), ( 30), [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF], developed correspondence or transfer formulas that allow one to express the association criteria using relational matrices C k and C l . Some of the main correspondence formulas are given below:

p k ∑ u=1 p l ∑ v=1 (n kl uv ) 2 = N ∑ i=1 N ∑ i =1 C k ii C l ii ( 37
) p k ∑ u=1 (n kl u. ) 2 = N ∑ i=1 N ∑ i =1 C k ii (38)
The reformulation of association criteria into the RA formalism, allows us to model coefficients like Belson, Rand, χ 2 of Tchuprow, Janson and Vegelius..., as particular cases of a general Coefficient, which is nothing but a simple variant of Bravais-Pearson's correlation coefficient 28), ( 38), ( 44), ( 2), (3).

∆(C k , C l , f , µ k , µ l ) see (
The RA formalism has allowed to get a deeper understanding of the main differences between several association criteria: in fact, the latent differences between the above mentioned association criteria can be expressed, according to 3 parameters ( f , µ k , µ l ):

• f is a function that transforms the general term of each relational matrix 21• µ k is a central trend (playing the role of a mean) corresponding to C k

• µ l is a central trend (playing the role of a mean) corresponding to C l

In order to illustrate those results, we give as an example, the different formulations of the χ 2 of Tchuprow criterion:

Tchuprow(V k , V l ) = ∑ u,v 1 n kl u. n kl .v n kl uv -n kl u. n kl .v N 2 (p k -1)(p l -1) (39)
= ∑ i,i C k ii C k i. -1 N C l ii C l i.
-

N ∑ i,i C k ii C k i. -1 N 2 ∑ i,i C l ii C l i. -1 N 2 1
where

C k i. = ∑ i C k
ii gives the number of objects that belong to the same cluster 22 of O i according to V k . Here, the parameters ( f , µ k , µ l ) corresponding to the χ 2 of Tchuprow is

( f (C ii ) = C ii /C i. , µ k = 1/N, µ l = 1/N).
Another example is the (modified) Rand index, which can also be expressed using this general coefficient ∆: it is linked to the particular coefficient given by (

f (C ii ) = C ii , µ k = 1/2, µ l = 1/2).
Concerning the relational expression of association criteria, we can also quote the "Maximal Association model" defined in [START_REF] Marcotorchino | Maximal association theory as a tool of research[END_REF] and [START_REF] Saporta | About maximal association criteria in linear analysis and in cluster analysis[END_REF] which is aimed at defining partitioning criteria by aggregating association criteria between relations and X. More precisely, suppose that we have M relational matrices 23 , C k ; k = 1, . . . , M, and we want to find out a consensual equivalence relation X. In that case, we can use a particular association criterion ∆(C k , X, f , µ k , µ l ) in order to measure the correlation between a given partition C k and an unknown relational matrix X representing the consensus partition. Then, one can consider to determine X such that it maximizes 24 the following partitioning criterion 25 :

M ∑ k=1 ∆(C k , X, f , µ k , µ l ) (41)
We can see that the Maximal Association model for partitions gives many solutions to the initial problem given by eq. ( 3). Moreover these association criteria, can be interpreted as similarity measures between categorical variables. As a result, one can use those measures to partition categorical variables and apply these results in a dimension reduction purpose. This question was investigated in the context of the RA framework in [START_REF] Abdallah | Application de l'analyse relationnelle pour classifier descripteurs et modalités en mode discrimination[END_REF].

The second contribution in data analysis that is worth noticing is related to the measure of similarity between objects. The approach developed in (11), [START_REF] Benhadda | Introduction à la similarité régularisée en analyse relationnelle[END_REF], called "regularized similarity" consists in giving automatic weights to the initial variables according to particular models of weighting, among them let us quote: the logical, the statistical and the probabilistic models.

One can represent a set of M categorical variables using the (N × P) indicator matrix K where P = ∑ M k=1 p k . This matrix is a binary one and we have, ∀i = 1, . . . , N; ∀j = 1, . . . , P:

K ij = 1 if object O i is in the category 26 D j 0 otherwise (42)
We have previously defined C ii according to a logical approach in terms of equivalence relations aggregation. We can also have a more geometrical approach since we have:

C ii = P ∑ j=1 K ij K i j = O i , O i (43)
where O i = (K i1 , . . . , K ij , . . . , K iN ) and ., . is the canonical scalar product. From a geometrical standpoint, the regularized similarity method amounts to exhibiting a diagonal metric, for which the diagonal weights are computed from the categorical variables.

The regularized similarity of type α denoted by A α ii is given by:

A α ii = P ∑ j=1 α j K ij K i j (44)
For instance, "statistical regularized similarity", defined in [START_REF] Benhadda | La similarité régularisée et ses applications en classification automatique[END_REF], gives higher weights to infrequent categories and reciprocally, very low weights to those frequent categories. In this particular case, we have actually α j = 1/K .j . We can observe that the model supposes that if two objects have a rare category in common then their similarity should be higher than if their shared category were frequent.

This particular similarity measure is related to the χ 2 metric used in Correspondence Factor Analysis methods [START_REF] Greenacre | Theory and applications of correspondence analysis[END_REF]. We can mention here, the following paper [START_REF] Marcotorchino | L'analyse factorielle relationnelle: parties i et ii[END_REF], where the latent link between the RA method and Factor Analysis methods is explained. Basically, the Condorcet's criterion, while we use the statistical regularized similarity, becomes highly related to "Inertial criteria". More precisely, J.F. Marcotorchino showed that the Condorcet's criterion associated to the similarity matrix of general term A α ii , and the dissimilarity matrix of general term

A α ii = A α ii +A α i i 2 -A α
ii , is the non trivial partitioning criterion strongly relevant to the family of criteria based upon inertia or "variance". This result led to the design of a full methodology called "Relational Factor Analysis method" (34) that consists in coupling the representations of clusters in terms of "bubbles", resulting from the RA 27 method, with the projection of objects on a 2D space obtained after applying the Factor Analysis method. Both approaches complement each other, because they resectively maximize objective criteria that are very close.

The third contribution that we can mention finally, is based on the extension of the RA method which is well-designed for clustering categorical data, to deal with objects described by real continuous quantitative variables. Indeed, we can notice that similarity measures can be expressed through scalar products or in a general manner by kernels. Then if we take

A ii = O i , O i and A ii = O i , O i + O i , O i 2 -O i , O i which is equal to 1 2 || O i -O i ||,
we have the following simplified Condorcet's criterion:

Condorcet(A, X) = N ∑ i=1 N ∑ i =1 O i , O i - 1 2 O i , O i + O i , O i 2 X ii (45)
Following previous results given in [START_REF] Marcotorchino | L'analyse factorielle relationnelle: parties i et ii[END_REF], we can show that the criterion based upon the inertial difference can be expressed using the RA formalism as follows:

IB(X) -IW(X) = 2 N ∑ N i=1 ∑ N i =1 O i , O i -1 2 O i , O i + O i , O i 2 X ii X i. -1 N 2 ∑ N i=1 ∑ N i =1 O i , O i (46)
IB(X) is the "between classes inertia" related to a partition represented by its relational matrix X, IW(X) is the "within classes inertia 28 " and ., . is a scalar product (kernel).

In the formula ( 46), if we look at the subpart depending on X, we can observe that the main difference between Condorcet's criterion and the inertial difference criterion resides in the fact that the first one does not weight the general term X ii , whereas the second one integrates a weight 29 , 1/X i. , to the general term X ii .

Finally, by considering eq. ( 46) and the 0/1 integer linear program described in eq. ( 18) we can thus extend the RA approach for clustering problems to the more general case of objects described by real continuous quantitative variables.

A

  binary relation R on two sets of objects O (the domain) and D (the codomain 3 ), is a triple (O, D, G(R)), where G(R) called the graph of the relation R, is a subset of the Cartesian product O × D. If we have (O i , D j ) ∈ G(R), then we say that object O i is in relation with object D j for the relation R. This will be denoted by O i RD j .

The alternative that is ranked first in the consensual ranking.

And more generally, numerical variables.

For a real continuous quantitative variable, D could equal R for example; for a categorical variable, D could be the set of categories of this variable.

In graph theory those matrices are adjacency matrices but in the case of particular binary relations, these matrices have special properties as we will see later.

For two objects O i and O i , this measure gives the "strength" of the relation O i RO i .

For two objects O i and O i , this measure gives the "strength" of the relation O i RO i .

In the case of two different sets, A ij gives the "strength" of the relation O i RD j and A ij gives the "strength" of the relation O i RD j .

ie X ii = 1.

ie X ii = 1.

That is to say: irreflexive, asymmetric, total and transitive.

In condition to satisfy the relational properties of an order relation see eq. (18).

ie X ii = 1.

However, in section 6, we will consider the case where objects are described by real continuous quantitative variables.

In condition to satisfy the relational properties of an equivalence relation see eq. (18).

ie X ii = 1.

But we will show in section 6 other main results obtained by using the RA formalism.

If X satisfies the transitivity inequality given in eq. (18), then it is easy to see that X satisfies the triangle inequality: X ii ≤ X ii + X i i .

A could be taken from A.

ie clustering O or D or both.

Two way contingency tables analysis.

For example, among the transformation functions that occurred in the relational formalism, Torgerson's transformation is the one related to the Belson criterion.

ie the number of objects that have the same category of O i according to V k .

Derived from M categorical variables.

Most of the association criterion's numerators given by particular ∆(C k , X, f , µ k , µ l ) lead to linear partitioning criteria according to X and can then be used with integer linear programming.

[START_REF] Labiod | Contribution au formalisme relationnel des classifications simultanes de deux ensembles[END_REF] With respect to the linear equations given in eq. (18).

Acknowledgements

Part of this work was supported by Cap Digital (french business cluster in the digital content creation and knowledge management area)


Julien Ah-Pine
email: julien.ah-pine@fr.thalesgroup.com

Jean-François Marcotorchino
email: jeanfrancois.marcotorchino@fr.thalesgroup.com

Julien Ah
email: julien.ah-pine@xrce.xerox.com

Unifying some association criteria between partitions by using relational matrices

Keywords: Relational Analysis, Association criteria, Independence, Nominal categorical variables, Partitions comparison

Association criteria used for measuring the relationship between categorical variables or partitions, are mainly applied and studied using contingency tables. There is another way for representing categorical variables : the Relational Analysis representation which uses binary pairwise comparison matrices and which has many properties. There exist correspondence formulas that allow to get from the contingency representation to the relational representation. By using these formulas, we show in this paper how Relational Analysis allows to unify many association criteria such as Rand, Tchuprow, Belson criteria and others. This unified framework allows also to have a better understanding of the main differences between those association criteria. In that context, we also present different kinds of independence : statistical, geometrical and "logical".

Introduction

Relational Analysis1 (RA in the rest of the paper) is concerned with the analysis of binary relations2 and it has many applications in different mathematical fields [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF], [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF], [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF]. Particularly, this approach represents binary relations as pairwise comparison matrices (also called relational matrices), and it is basically related to different concepts from graph theory, statistics and linear programming. The most usual application domains of RA are data analysis and multicriteria decision making which are respectively based upon the aggregation of equivalence and order relations.

In this paper, we are particularly interested in the applications of RA in the analysis of association criteria between nominal categorical variables (or partitions). There are already many results in that context see for example [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF], [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF], [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie III[END_REF], [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF], [START_REF] Messatfa | Unification relationnelle des critères et structures optimales des tables de contingences[END_REF], [START_REF] Idrissi | Contribution à l'unification de critères d'association pour variables qualitatives[END_REF], [START_REF] Youness | Some measures of agreement between close partitions[END_REF]. This paper recalls some of these results and it also presents some other extensions [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF].

There are, in the literature, numerous works that have studied different methods for measuring the relationship between partitions see for example [START_REF] Zahn | Approximating symmetric relations by equivalence relations[END_REF], [START_REF] Rand | Objective criteria for the evaluation of clusterings methods[END_REF], [START_REF] Fowlkes | A method for comparing two hiearchical clusterings[END_REF], [START_REF] Hubert | Comparing partitions[END_REF], [START_REF] Janson | The j-index as a measure of association for nominal scale response agreement[END_REF], [START_REF] Mirkin | Mathematical classification and clustering[END_REF]. The RA approach in this context aims at having a better understanding of the main differences between several of these methods.

In that perspective, the different goals of the present paper are the following ones :

• We want to show different properties that the relational representation allows compared to the contingency representation. Indeed, we can formally unify 7 different association criteria found in the literature by showing that they can be deduced from a general Bravais-Pearson like correlation coefficient. In their relational representation, we show that the main differences between these association criteria, can be expressed using three parameters. • In their contingency representation, many association criteria are based upon the statistical independence deviation concept whereas in their relational representation, they are mainly related to the geometrical independence deviation concept. We want to underline also, another kind of independence called the "indetermination" situation which has a "logical" aspect as it is also encountered in voting theory.

This paper is organized as follows :

• In section 2, we recall basics of the contingency and relational representations, the different association criteria we are going to analyze and the correspondence formulas that allow us to express those association criteria from their contingency representation to their relational representation. • In section 3, we give a general formula which is similar to the Bravais-Pearson correlation coefficient. This formula has three parameters : a transformation function of the relational matrices, and two central trends.

We show that many association criteria can be deduced from this general equation when using particular parameters. • When using the contingency representation or the relational representation, there is a duality between the statistical independence and the geometrical independence concepts. In section 4, we try to strengthen this property by showing a particular relationship between Belson's criterion and Janson-Vegelius' criterion. Moreover, we give some comparisons to Mirkin's classification of association criteria. • In section 5, we recall the "indetermination" situation concept and its "logical" foundations. Then we suggest some extensions by defining a parametric normalized coefficient based on this concept.

From contingency representation to relational representation

We assume that we have N objects, {O i ; i = 1, . . . , N }. For these objects, let V k and V l be two nominal categorical variables with respectively p k and p l classes. The sets of classes will be respectively denoted by {D k u ; u = 1, . . . , p k } and {D l v ; v = 1, . . . , p l }. One can represent each of these variables by binary assignment matrices. For example, in the case of V k , we have the following (N × p k ) matrix :

K k iu = 1 if O i belongs to the class D k u 0 else
From K k and K l , we can deduce the following contingency table denoted by n kl with dimensions (p k × p l ) :

n kl = t K k • K l
where t K k is the transpose matrix associated to K k and • the matrix multiplication.

We have the following notations and interpretations, ∀u = 1, . . . , p k and ∀v = 1, . . . , p l :

• n kl uv =Number of objects belonging both to the class We will study the following association criteria : Belson (B) [START_REF] Belson | Matching and prediction on the principle of biological classification[END_REF], Lerman (L) [START_REF] Lerman | Classification et analyse ordinale de données[END_REF], χ 2 of Tchuprow (T ), Jordan (J) [START_REF] Ch | Les coefficients d'intensité relative de korosy[END_REF], Rand (R) [START_REF] Rand | Objective criteria for the evaluation of clusterings methods[END_REF], and Janson-Vegelius (JV ) [START_REF] Janson | The j-index as a measure of association for nominal scale response agreement[END_REF]. We first recall the definitions of these criteria in their contingency representation. We precise that the Rand criterion and the Lerman criterion that we mention, are modified versions according to [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF] and [START_REF] Idrissi | Contribution à l'unification de critères d'association pour variables qualitatives[END_REF].

D k u of V k and D l v of V l , •
B(V k , V l ) = p k u=1 p l v=1 n kl uv - n kl u. n kl .v N 2 (1)
L(V k , V l ) = u,v (n kl uv ) 2 -u (n kl u. ) 2 v (n kl .v ) 2 N 2 u (n kl u. ) 2 1 -u (n kl u. ) 2 N 2 v (n kl .v ) 2 1 -v (n kl .v ) 2 N 2
(2)

T (V k , V l ) = u,v 1 n kl u. n kl .v n kl uv - n kl u. n kl .v N 2 (p k -1)(p l -1) (3) J(V k , V l ) = 1 N u,v n kl uv n kl uv - n kl u. n kl .v N (4) R(V k , V l ) = 2 u,v (n kl uv ) 2 -u (n kl u. ) 2 -v (n kl .v ) 2 + N 2 N 2
(5)

JV (V k , V l ) = p k p l u,v (n kl uv ) 2 -p k u (n kl u. ) 2 -p l v (n kl .v ) 2 + N 2 (p k (p k -2) u (n kl ) 2 u. + N 2 ) (p l (p l -2) u (n kl .v ) 2 + N 2 ) (6)
We also have the following expression for the Janson-Vegelius criterion :

JV (V k , V l ) = p k p l u,v n kl uv - n kl u. p l + n kl .v p k -N p k p l 2 (p k (p k -2) u n 2 u. + N 2 ) (p l (p l -2) u n 2 .v + N 2 ) (7)
RA is another way for representing nominal categorical variables. This representation uses pairwise comparison matrices also called relational matrices.

Let C k and C l be the relational matrices of dimension (N × N ), representing the variables V k and V l . We can obtain C k and C l by using the assignment matrices K k and K l :

C k = K k • t K k and C l = K l • t K l
In general terms, let R be a binary relation among a set of N objects O 1 , . . . , O N . If C is the relational matrix for R then we have, ∀i, i = 1, . . . , N :

C ii = 1 if O i is in relation with O i 0 else
In our context, we deal with equivalence relations or partitions. As a result we have, for instance for V k :

C k ii = 1 if O i and O i belong to the same class according to V k 0 else
Furthermore, the relational matrix C k represents an equivalence relation. Thus, it respects the following relational properties which can be expressed as linear equations :

• reflexivity : C k ii = 1 ∀i = 1, . . . , N , • symmetry : C k ii -C k i i = 0 ∀i, i = 1, . . . , N , • transitivity : C k ii -C k i i + C k ii ≤ 1 ∀i, i , i = 1, . . . , N .
There are different correspondence formulas that exist between the contingency representation and the relational one. We give in Table 1 some of the most useful ones.

Contingency ↔ Relational representation representation p k u=1 p l v=1 (n kl uv ) 2 = N i=1 N i =1 C k ii C l ii u (n kl u. ) 2 = i,i C k ii v (n kl .v ) 2 = i,i C l ii u,v (n kl uv ) 2 n kl u. n kl .v = i,i C k ii C l ii C k i. C l i. u,v n kl uv n kl u. n kl .v = i,i C k i. +C k .i 2 C l ii u,v (n kl uv ) 2 n kl u. = i,i C k i. +C k .i 2 C k ii C l ii u,v (n kl uv ) 2 n kl u. = i,i C k ii C k i. C l ii v u n kl u. n kl uv 2 = i,i C k i. C k .i C l ii u,v (n kl u. ) 2 (n kl .v ) 2 = N i,i C k .. C l ii
where n kl u. = v n kl uv and

C k i. = i C k ii Table 1.
Correspondence formulas between contingency representation and relational representation

In [START_REF] Idrissi | Contribution à l'unification de critères d'association pour variables qualitatives[END_REF], the author uses these formulas, in order to obtain the symmetric relational expression of Rand (modified version), Janson-Vegelius, Lerman, and Tchuprow criteria. We extend these results by giving in addition, the symmetric expression of Belson and Jordan criteria. The related definitions are given below.

B(C k , C l ) = N i=1 N i =1 C k ii - C k i. + C k .i N + C k .. N 2 C l ii - C l i. + C l .i N + C l .. N 2 (8) L(C k , C l ) = i,i C k ii -i,i C k ii N 2 C l ii -i,i C l ii N 2 i,i C k ii -i,i C k ii N 2 2 i,i C l ii -i,i C l ii N 2 2 (9) T (C k , C l ) = i,i C k ii C k i.
-

1 N C l ii C l i.
-

1 N i,i C k ii C k i.
-

1 N 2 i,i C l ii C l i.
-

1 N 2 (10)
J(C k , C l ) = 1 N i,i C k ii - C k i. N C l ii - C l i. N (11)
R(C k , C l ) = 1 N 2 i,i C k ii C l ii + C k ii C l ii (12) JV (C k , C l ) = i,i C k ii -1 p k C l ii -1 p l i,i C k ii -1 p k 2 i,i C l ii -1 p l 2 (13)
where

C k ii = 1 -C k ii , C k = U N -C k and U N is the (N × N ) square matrix
where all terms equal 1.

We also have the following equation for the modified Rand criterion that will be called the symmetric modified Rand criterion, R (C k , C l ) :

R (C k , C l ) = 2R(C k , C l ) -1 = i,i C k ii -1 2 C l ii -1 2 i,i C k ii -1 2 2 i,i C l ii -1 2 2 (14)
The relational representation of the studied association criteria can easily be proved by using the correspondence formulas given in Table 1. Besides, the different proofs for these correspondence formulas are given in [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF].

A unifying relational approach for many association criteria

Using the relational representation, one can express the different association criteria that we have recalled, as particular cases of a general criterion similar to a Bravais-Pearson correlation coefficient 3 between transformed relational matrices [NI00], [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF] :

∆(C k , C l , f, µ k , µ l ) = i,i (f(C k ii )-µ k )(f(C l ii )-µ l ) i,i (f(C k ii )-µ k ) 2 i,i (f(C l ii )-µ l ) 2 (15)
According to (15), we can see that the main differences between the studied criteria are based upon :

• the transformation function f applied to the terms of the relational matrices, • the central trends µ k and µ l , which are given parameters.

We give in Table 2, different values to the parameters (f, µ k , µ l ), which define particular coefficients. The latter are related to the association criteria recalled previously. Therefore, we also give the relationship type that exists between the defined coefficient and its corresponding association criterion.

In this table, we mention the Torgerson transformation [START_REF] Torgerson | Multidimensional scaling : I. theory and method[END_REF]. We recall that it is an operation used in multidimensional scaling which, given a scalar products matrix between objects, gives as output the scalar products matrix between centered objects :

f (C k ii ) = C k ii - C k i. + C k .i N + C k .. N 2 = O i k -G k , O i k -G k {O i k ; i = 1, . . . , N } are (p k × 1) binary vectors where [O i k ] u = K k iu ; u = 1, . . . , p k and G k = 1 N N i=1 O i k .
The RA approach allows to have a better understanding of the main differences between the studied association criteria. Moreover, in their relational 3 similar coefficients for measuring the relationship between square matrices were considered in [START_REF] Escoufier | Le traitement des variables vectorielles[END_REF] and in [START_REF] Hubert | A general statistical framework for assessing categorical clustering in free recall[END_REF]. These coefficients were respectively defined as RV coefficients and Γ statistics

f (C ii ) µ k µ l Related criteria
Relation with the related criteria

f (C ii ) 0 0 Belson Normalized = Belson C ii - C i. +C .i N + C.. N 2 (Torgerson transf.) f (C ii ) = C ii C k .. /N 2 C l .. /N 2 Lerman Lerman f (C ii ) = C ii /Ci. 1/N 1/N Tchuprow Tchuprow f (C ii ) = C ii C k i. /N C l i. /N Jordan Normalized Jordan f (C ii ) = C ii 1/2 1/2 Modified Symmetric Rand modified Rand f (C ii ) = C ii 1/p k 1/p l Janson-Vegelius Janson-Vegelius
Table 2. Correspondence between correlation coefficient and association criteria expressions all these association criteria are related to the geometrical independence deviation concept. Indeed, we can also express the general equation (15) using the Frobenius scalar product between two relational matrices :

C k , C l F = N i=1 N i =1 C k ii C l ii = Trace( t C k • C l ) Then, we can see that ∆(C k , C l ) = 0 ⇔ f (C k ) -µ k U N , f (C l ) -µ l U N F = 0
In [START_REF] Mirkin | Mathematical classification and clustering[END_REF], Mirkin gives four different classes for classifying association criteria :

• structural association approach, • contingency modeling approach, • geometrical approach,

• cross-classificational approach.

Regarding this classification, our results would give more emphasis to the contingency modeling approach and to the geometrical approach. The first one is related to the contingency representation and to the statistical independence deviation concept whereas the second one is related to the relational representation and to the geometrical independence deviation concept. We will study in more details those two different approaches in the following section.

Moreover, our approach underlines the geometrical approach more than the definition given in [START_REF] Mirkin | Mathematical classification and clustering[END_REF] does. Indeed, in [START_REF] Mirkin | Mathematical classification and clustering[END_REF], only the Tchuprow criterion is considered as belonging to the geometrical approach4 . Using the relational representation, we can show that the equivalence match criterion given in [START_REF] Mirkin | Mathematical classification and clustering[END_REF] is exactly Marcotorchino's version of Rand criterion [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF]. Regarding equation ( 15) and Table 2, this last criterion is related to the parameters (f = Id, µ k = 1/2, µ l = 1/2) which leads to the symmetric modified Rand criterion with range values [-1, 1]. In a more general perspective, we have shown that many other association criteria which are not considered5 in [START_REF] Mirkin | Mathematical classification and clustering[END_REF] can also be expressed using the geometrical correlation coefficient given in (15). Finally, unlike the contingency representation, the relational representation allows to express the differences between the studied association criteria using three clearly defined parameters.

Statistical and geometrical independence concepts

In the contingency representation, we say that two nominal categorical variables V k and V l are statistically independent if their joint probabilities, n kl uv N , equal the product of their marginal probabilities,

n kl u. N n kl .v N : V k ⊥ S V l ⇔ n kl uv N = n kl u. N n kl .v N ∀(D k u , D l v ) : D k u ∈ V k , D l v ∈ V l (16)
Many of the studied association criteria are based upon this concept when using contingency representation. Indeed, we clearly see, that Belson, Lerman, Tchuprow and Jordan criteria are null if V k and V l are statistically independent.

On the contrary, in the relational representation, all studied association criteria are related to the geometrical independence deviation concept 6 . We say that two nominal categorical variables are geometrically independent if we have the following relation :

V k ⊥ G V l ⇔ ∆(C k , C l , f, µ k , µ l ) = 0 (17) ⇔ i,i f (C k ii ) -µ k f (C l ii ) -µ l = 0
Regarding statistical / geometrical independence, we now focus on a particular relationship between two of the recalled association criteria : the Belson criterion and the Janson-Vegelius criterion's numerator. This relationship can be stated as follows :

• The Belson criterion, in its contingency representation, is based on the statistical independence whereas in its relational representation, it is based on a geometrical independence associated to the Torgerson transformation. • On the contrary, the Janson-Vegelius criterion's numerator, in its contingency representation, is based on the geometrical independence associated to the Torgerson transformation whereas, in its relational representation, it is related to the statistical independence with an equiprobability assumption.

We summarize the Belson / Janson-Vegelius criteria relationship in Table 3.

Deviation from Geometrical independence statistical independence based on Torgerson transformation

Belson u,v n kl uv - We give below more details about our interpretations of the independence concepts underlying the relational and the contingency representations of Janson-Vegelius criterion's numerator, which show the duality property between the latter and Belson criterion.

n kl u. n kl .v N 2 i,i C k ii - C k i. N + C k .i N - C k .. N 2 C l ii - C l i. N + C l .i N - C l .. N 2 Janson-Vegelius i,i C k ii -1 p k C l ii -1 p l u,v n kl uv - n kl u. p l + n kl .v p k - n kl .. p k p l 2 (numerator)
First, if we consider the Janson-Vegelius criterion's relational representation, we can interpret the term (C k ii -1 p k ), as a deviation from the statistical independence situation in an equiprobability context. Let P (C k ii ) be, symbolically, the probability for two objects O i and O i , belonging to the same class of V k . Let us assume moreover, that the different classes D k u ; u = 1, . . . , p k ; are equiprobable. This implies that the probability for an object to belong to any class of V k equals 1/p k . Then, in case of probability independence, we have :

P (C k ii ) =
n kl uv - n kl u. p l - n kl .v p k + n kl .. p k p l = D k u -G k , D l v -G l ∀(D k u , D l v ) ∈ V k × V l where G k = 1 p k D k u ∈V k D k u and G l = 1 p l D l v ∈V l D l v .
5 A "logical" independence concept : the "indetermination" situation Despite the general geometrical independence deviation concept underlying the relational representations of the studied association criteria, we can distinguish another kind of independence which has a "logical" aspect. This concept was defined in [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF] and was called the situation of "indetermination". It is related to Condorcet criterion defined in voting theory [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF].

In that context, we have an "indetermination" situation when the number of voters in favor of a candidate equals the number of voters against this candidate. This criterion which measures the relationship between order relations was extended to the case of equivalence relations [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF]. This extension allows to link the Condorcet criterion to the modified Rand criterion as we formally have :

R(C k , C l ) = Condorcet(C k , C l ) N 2 (18)
In order to introduce the "indetermination" situation concept we first introduce the four-fold / tetrachoric 7 table given in its relational representation. Indeed in that case, the nominal categorical variables through their relational matrices C k and C l , can be interpreted as 0/1 variables. As a result, we can consider the (2 × 2) table given in Table 4.

C l C l Margin C k 11 kl = i,i C k ii C l ii 10 kl = i,i C k ii C l ii i,i C k ii C k 01 kl = i,i C k ii C l ii 00 kl = i,i C k ii C l ii i,i C k ii Margin i,i C l ii i,i C l ii N 2
Table 4. Agreements and disagreements between relational matrices

We say that two nominal categorical variables are in an "indetermination" situation if we have the following relation :

V k ⊥ L V l ⇔ 11 kl + 00 kl -10 kl -01 kl = 0 (19) ⇔ i,i C k ii C l ii + i,i C k ii C l ii - i,i C k ii C l ii - i,i C k ii C l ii = 0 ⇔ i,i C k ii -C k ii C l ii -C l ii = 0 ⇔ 4 i,i C k ii -1/2 C l ii -1/2 = 0
7 this table is equivalent to the four-fold / tetrachoric table given in [START_REF] Mirkin | Mathematical classification and clustering[END_REF] but the latter only uses the contingency representation. However, when using the relational representation the following notations 11 kl , 01 kl , 10 kl and 00 kl are straightforward unlike for the contingency representation. Finally this allows us to naturally apply other coefficients such as the odds-ratio as we suggest in (20) or other similarity indexes between 0/1 vectors This result shows that the symmetric modified Rand criterion 8 is null when we have an "indetermination" situation associated to uniform weights : µ k 1 = µ k 0 = µ l 1 = µ l 0 . Another example is the Janson-Vegelius criterion which is null when we have an "indetermination" situation associated to the following parameters : µ k 1 = (p k -1), µ k 0 = 1, µ l 1 = (p l -1), µ l 0 = 1.

Finally by using equation ( 23), we could also enrich Table 2, by adding some other Λ coefficients associated to particular weight systems.

  uv = n kl u. =Number of objects belonging to the class D k u of V k , • p k u=1 n kl uv = n kl .v =Number of objects belonging to the class D l v of V l , • p k u=1 p l v=1 n kl uv = N = Total number of objects.

p

  p k u=1 P ("O i and O i belong to the class D k u ") = p k u=1 P ("O i belongs to the class D k u ")P ("O i belongs to the class D k u Second, if we consider the Janson-Vegelius criterion's contingency representation, we can interpret the term (n kl uvk p l ), as the Torgerson transformation of the (N × 1) binary vectors {D k u ; u = 1, . . . , p k } and {D l v ; v = 1, . . . , p l } where [D k u ] i = K k iu ; i = 1, . . . , N . Indeed, we have n kl uv = D k u , D l v and the following relation :

Table 3 .

 3 Dual relationship between Belson and Janson-Vegelius criteria due to the contingency / relational representation duality

see for example[MAP] for a recent overview of this theory

their aggregation, their association measures

see also[START_REF] Mirkin | Eleven ways to look at the chi-squared coefficient for contingency tables[END_REF]

Belson, Lerman, Jordan, Janson and Vegelius criteria

notice that the (non symmetric) Rand criterion, R(C k , C l ), equals 1/2 in case of geometrical independence

Using the notations given in Table 4, we can define the number of agreements between two categorical variables as 11 kl + 00 kl and the number of disagreements as 10 kl + 01 kl . These last quantities are exactly the equivalence match and equivalence mismatch criteria given in [START_REF] Mirkin | Mathematical classification and clustering[END_REF]. Finally, we have an "indetermination" situation when the number of agreements equals the number of disagreements. This situation means that the variables are neither "concordant" nor "discordant".

Using Table 4, we can formally characterize the "indetermination" situation concept compared to the statistical independence deviation concept. Indeed, when considering 0/1 variables, we can use the odds-ratio measure in order to determine if two variables are statistically independent or not :

⇔ 11 kl 00 kl -10 kl 01 kl = 0

Using correspondence formulas, we can easily show that the modified Lerman criterion, L(C k , C l ), is null if and only if the odds-ratio measure, OR(C k , C l ), equals one.

Comparing equation ( 19) to (20), we can see that the "indetermination" situation concept is related to an additive model, 11 kl + 00 kl -10 kl -01 kl , whereas the statistical independence deviation concept is related to a multiplicative model, 11 kl 00 kl -10 kl 01 kl .

Similarly to equation (15), we propose to extend the "indetermination" situation concept to a more general parametric family by assigning different weights to agreements and disagreements quantities :

Then, we introduce the following general formula which defines a normalized coefficient, Λ, that measures the deviation from the weighted "indetermination" situation between two nominal categorical variables :

We give below the formal relationship between the geometrical independence and the "indetermination" situation in the relational representation :