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

On data fusion in information retrieval using different aggregation operators

Keywords: Aggregation operator, fuzzy results merging, data fusion, metasearch, unsupervised rank aggregation

This paper is concerned with the problem of unsupervised rank aggregation in the context of metasearch in information retrieval. In such tasks, we are given many partial ordered lists of retrieved items provided by many search engines and we want to define a way for aggregating those lists in order to find out a consensus. One classical approach consists in aggregating, for each retrieved item, the scores given by the different search engines. Then, we use the resulting aggregated scores distribution in order to infer a consensus ordered list. In this paper we investigate whether aggregation operators defined in the fields of multi-sensor fusion and multicriteria decision making are of interest for metasearch problems or not. Moreover, another purpose of this paper is to introduce a new aggregation operator, its foundations and its properties. We finally test all these aggregation operators for metasearch tasks using the Letor 2.0 dataset. Our results show that among the studied aggregation functions, the ones which are more compensatory outperform the baseline methods CombSUM and CombMNZ.

Introduction

Data fusion problems arise when, for a given task, there are several experts or information sources that give different opinions, or scores with respect to a set of alternatives or strategies. These opinions or scores can correlate or not and we are faced with the problem of combining them in order to figure out a consensus.

That kind of problem can be encountered in many different contexts. First, in social choice theory which encompasses voting theory and welfare economics, aggregating preference relations is a central problem. Indeed, in an election for example, we have to aggregate the votes or preferences of many voters in order to elect a consensual candidate.

Another example is the multicriteria decision making field. In that case, the decision maker is given a set of alternatives and a set of criteria. Each alternative is given a degree of satisfaction according to each criterion. But, the criteria are often conflicting. Thus, the decision maker needs to find a way to come up with a compromise.

Next, in the multi-sensor fusion field, the aim is to combine information coming from distinct sources in order to achieve a resulting information that is expected to be more accurate than the ones provided by one source only.

Lately, in information retrieval field, there have been several tasks for which aggregating information coming from different sources is beneficial. In [START_REF] Dwork | Rank aggregation methods for the web[END_REF] for example, the authors investigate the use of unsupervised rank aggregation to tackle the problem of web spam. In that case, combining the results obtained by several search engines allows to filter spam. Indeed, authors of web pages that attempt to enhance the ranking of their own pages by analyzing the drawbacks of one search engine cannot do it for all search engines. Apart from web spam filtering, there are many other applications in the information access domain where aggregation techniques play a crucial role [START_REF] Herrera-Viedma | Applying aggregation operators for information access systems: An application in digital libraries[END_REF]. In that context, tools such as multimedia search engines or recommender systems are examples that make use of data fusion techniques.

In this paper, we are concerned with the metasearch problems in information retrieval. In that case, the goal 1570-1263/0-1900/$17.00 c 0 -IOS Press and the authors. All rights reserved is to combine the results given by different search engines into a single consensus list of items which is expected to be more relevant than any of the search engines results if they were considered individually.

Accordingly our first aim is to investigate if some aggregation operators defined in the fields of multisensor fusion and multicriteria decision making can be applied to solve metasearch problems. Next, our second goal is to introduce a new aggregation operator and to compare its results with other techniques in the context of metasearch problems. This paper is an expanded version of the conference paper [START_REF] Ah-Pine | Data fusion in information retrieval using consensus aggregation operators[END_REF].

The rest of the paper is organized as follows. In section 2, we recall some previous works that address metasearch problems and we also introduce some notations. In section 3, we explain the pre-processing step which is necessary before applying any aggregation operators. The latter consists in normalizing each scores distributions so that their values become comparable. Then in section 4, we recall some famous aggregation functions that are studied in different contexts namely, weighted quasi-arithmetic means, triangular norms and conorms and triangular norms ordered weighted averaging operator (TOWA). Next, in section 5, we introduce a new aggregation operator, its set-based foundations and its combinatorial properties. We tested all the aforementioned approaches for metasearch tasks using the Letor 2.0 dataset [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF]. We report and we analyse the results we obtained in section 6. Finally we conclude and sketch some future work in section 7.

Related work and notations

Basically, we suppose there are M experts (the search engines) and N alternatives (the documents). Each expert gives an ordered list of those N objects according to their own preferences (or scores).

However, when dealing with information retrieval tasks there are some particular points that are worth noticing (see [START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF] for more details). In general, the number of objects of the collection N is much larger than the number of search engines M . In voting theory for example, this is indeed the contrary: there are more voters ("experts") than candidates ("alternatives"). Besides, given a query, each search engine attempts to give in its top-list the most relevant objects. Therefore, the goal of search engines is not to score every objects in the collection. Furthermore, we can also assume that after a certain position, let say 100, objects that are ranked beyond are not relevant. Consequently, each search engine gives a partial ranking of the objects.

The top-lists provided by the M search engines are not mutually disjoint: there are overlaps between them. Thus, one can assume that objects that appear in many top-lists are more likely to be relevant. Accordingly, the problem we address is to find a single consensus list which combines the M rankings in order to achieve a more consistent list.

In the literature, there are different kinds of method to address the unsupervised rank aggregation problem. According to [START_REF] Riker | Liberalism against populism[END_REF][START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF], we can notice two broad families of approaches:

positional methods: for each object, we consider the scores given by each expert (the object's profile), we then aggregate these scores using different techniques and we finally re-rank the objects using the aggregated scores. The first positional method was proposed by Borda [START_REF] Borda | Mémoire sur les élections au scrutin[END_REF] but linear combination such as the weighted arithmetic mean is for instance, one of these methods [START_REF] Fox | Combination of multiple searches[END_REF]. Example of more recent approaches are the following ones [START_REF] Klementiev | An unsupervised learning algorithm for rank aggregation[END_REF][START_REF] De | On fuzzy result merging for metasearch[END_REF]. In [START_REF] Klementiev | An unsupervised learning algorithm for rank aggregation[END_REF], it is proposed to learn the weight assigned to any search engine in an unsupervised manner. In [START_REF] De | On fuzzy result merging for metasearch[END_REF], the authors apply aggregation functions based on ordered weighted averaging functions1 (OWA), originally designed in the domain of multicriteria decision making, to metasearch problems. majoritarian methods: these methods use pairwise comparisons matrices of objects and are mostly based upon order relations aggregation techniques using association criteria such as Condorcet's criterion [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF][START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF][START_REF] Montague | Condorcet fusion for improved retrieval[END_REF] or distance criteria such as Kendall distance [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF][START_REF] Fagin | Comparing top k lists[END_REF]. Other methods have also been proposed using Markov chain models [START_REF] Dwork | Rank aggregation methods for the web[END_REF]. Lastly, outranking methods which were introduced in multicriteria decision problems have also been adapted for information retrieval tasks [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF][START_REF] Farah | An outranking approach for rank aggregation in information retrieval[END_REF].

In this paper we are exclusively concerned with approaches that belong to the positional family. Before introducing the most popular techniques used in this context, we first give some basic notations:

-S j (i) is the normalized score expert j assigns to object i (see the next section for details about the normalization step). -L(j) is the ordered list of expert j.

-L k (j) is the first k objects of L(j) or the topk list of expert j. We will also denote L k = {L k (j); j = 1, . . . , M } the set of all top-k lists.

-U = M j=1 L k (j)
is the union set of the M top-k lists. We will also denote K = #U, the number of elements in U.

-∀i ∈ U : NZ(i, L k ) is the number of top-k lists in which object i appears.

Using these notations, we can define below the general linear combination which represents the baseline methods for unsupervised rank aggregation problems in information retrieval [START_REF] Fox | Combination of multiple searches[END_REF], ∀i ∈ U:

Comb v,w (i) = NZ(i, L k ) v M j=1 w j S j (i) (1)
where v is an integer and w a weight vector.

In this kind of approach, the most usually employed cases are the following ones [START_REF] Fox | Combination of multiple searches[END_REF], ∀i ∈ U:

CombSUM(i) = M j=1 S j (i) (2)
CombMNZ(i) = NZ(i, L k ) M j=1 S j (i) (3)
CombSUM is the aggregated score given by the sum over the experts scores. CombMNZ weight the latter with respect to the number of experts who have ranked the element in their top-k list. According to CombMNZ, the greater NZ(i, L k ), the higher the aggregated score. The NZ factor amounts to reinforcing the aggregated score on the basis of the number of times an object reaches a top-k list among the search engines. Suppose that for two objects i and i , CombSUM(i) = CombSUM(i ) than the CombMNZ approach would rank higher the object that appears most often in the top-k lists.

As mentioned previously, some methods have been proposed for learning the weight vector w in an unsupervised manner. In [START_REF] Klementiev | An unsupervised learning algorithm for rank aggregation[END_REF] for example, an unsupervised learning algorithm is suggested. However, this approach is a linear combination of scores. In our case, we rather focus on non-linear aggregation operators.

Normalization step

The normalization step is inherent to any positional method. Indeed, each expert may have its own particular score distribution which belongs to a certain range of values. As a result, before applying any aggregation function, we have to normalize each distribution if we want them to be mutually comparable. There exist several normalization methods [START_REF] Renda | Web metasearch : rank vs score based rank aggregation methods[END_REF]. However, most of the aggregation operators we are going to introduce in sections 4 and 5 use different tools taken from fuzzy logic. In other words, they manipulate truth measures that belong to [0, 1]. Thus, we propose to normalize the experts scores as follows.

Let us denote by V j (i), the original score value the expert j assigns to object i. Then, its associated normalized score denoted by S j (i) is given by, ∀j = 1, . . . , M ; ∀i ∈ L k (j):

S j (i) (4) = V j (i) -min i ∈L k (j) {V j (i )} max i ∈L k (j) {V j (i )} -min i ∈L k (j) {V j (i )}
With respect to expert j, the previous normalization formula is given for all objects belonging to the expert's top-k list, L k (j). We still need to assign normalized scores to objects that belong to U -L k (j). The only thing we can assume about these latter objects is that they are not preferred to any of the objects belonging to L k (j). Consequently, ∀j = 1, . . . , M ; ∀i ∈ U -L k (j), we set: S j (i) = 0.

Recalling some aggregation operators

Many aggregation functions have been defined in the field of information fusion and multicriteria decision making (see for example [START_REF] Bloch | Information Combination Operators for Data Fusion: A Comparative Review with Classification[END_REF][START_REF]Aggregation and Fusion of Imperfect Information[END_REF][START_REF] Dubois | On the use of aggregation operations in information fusion processes[END_REF]). We recall some of them namely weighted quasi-arithmetic means, triangular norms, triangular conorms and triangular norm OWA operators.

Weighted quasi-arithmetic means

Weighted quasi-arithmetic means, also called weighted generalized f -means, are functions that generalize the classical weighted arithmetic mean by using a transformation function f . In our case, we consider f : [0, 1] → [-∞, ∞]. f must be continuous, strictly monotonic, and it must also respects the following conditions: {f (0), f (1)} = {-∞, ∞}. The quasi-arithmetic mean associated to f is denoted M f . Given a sequence of M values (a 1 , . . . , a M ) ∈ [0, 1] M and a system of weights (or a weight vector) (w 1 , . . . , w M ) such that M j=1 w j = 1, the weighted quasi-arithmetic mean is defined by:

M f (a 1 , . . . , a M ) = f -1   M j=1 w j f (a j )  
We will consider more particularly, the case of power functions f (a) = a p with p ∈ R which are strictly monotonic functions. In that case, these operators are also called weighted power means.

M p (a 1 , . . . , a M ) =   M j=1 w j (a j ) p   1/p (5)
We can notice that CombSUM is equivalent to the arithmetic mean given by p = 1 associated to a uniform weight distribution. Weighted power means are non-decreasing with respect to p, ∀ -∞ < p ≤ p < +∞:

M p (a 1 , . . . , a M ) ≤ M p (a 1 , . . . , a M )
Furthermore, they are lower bounded by the minimum function min(a 1 , . . . , a M ) which corresponds to the limit case p → -∞. Likewise, they are upper bounded by max(a 1 , . . . , a M ) which corresponds to the dual limit case p → +∞.

Other famous particular cases are the weighted harmonic, geometric and quadratic means which are respectively given by p = -1, the limit case p → 0 and p = 2.

The weighted power mean is compensatory in the sense that its values are bounded by the minimal and the maximal values of its arguments. Particularly, as p grows, the averaged value tends to the maximum and we say that the limit value of the power mean has a disjunctive behavior. On the contrary, when p tends to -∞, we say that the limit value of the power mean reflects a conjunctive behavior. These considerations will become clearer with the following subsection.

Triangular norms and conorms

Triangular norms (t-norms) are binary operations T : [0, 1] 2 → [0, 1] which are associative, commutative, non decreasing in each argument and such that T (a, 1) = a, ∀a ∈ [0, 1]. They are special functions used in probabilistic metric spaces [START_REF] Schweizer | Probabilistic metric spaces[END_REF], and fuzzy logic [START_REF] Klement | Triangular norms[END_REF].

In fuzzy logic particularly, these operations extend the conjunction from the binary case to the multivalued case. Let A and B be two events and µ(A) = a and µ(B) = b their associated truth values in [0, 1]. Typically, in our case, atomic events are: "object i is relevant for expert j". Then, T (a, b) measures the truth value of the conjunction A ∩ B 2 . As t-norms are associative and commutative, they can be extended easily for measuring the conjunction of more than two events. We have for example: T (a, b, c) = T (T (a, b), c) and so on.

T-norms are aimed at measuring the conjunction of events provided by different sources. However, the disjunction measures of events are also of interest. Then, departing from a t-norm T , we can define its related triangular conorm T * (t-conorm) as follows:

T * (a, b) = 1 -T (1 -a, 1 -b) (6)
Similarly to t-norms, t-conorms allow one to extend the disjunction to the multi-valued case.

There exist non-parametric and parametric t-norms and t-conorms. The four fundamental non-parametric ones are:

the minimum t-norm and its related t-conorm:

T M (a, b) = min(a, b) T * M (a, b) = max(a, b)
the product t-norm and its related t-conorm:

T P (a, b) = ab T * P (a, b) = a + b -ab -the Lukasiewicz t-norm and t-conorm: T W (a, b) = max(a + b -1, 0) T * W (a, b) = min(a + b, 1)
the drastic product and its related t-conorm:

T D (a, b) = 0 if (a, b) ∈ [0, 1[ 2 min(a, b) otherwise T * D (a, b) = 1 if (a, b) ∈]0, 1] 2 max(a, b) otherwise
T M and T D are respectively, upper and lower bounds for t-norms. Thus, if T is a t-norm, we have

∀(a, b) ∈ [0, 1] 2 : T D (a, b) ≤ T (a, b) ≤ T M (a, b) (7)
T M gives the highest value for the conjunction of two events: it assumes that one event is included in the other one and thus a strong relationship between them. T P gives the conjunction value of two events assuming that the latter are independent. On the contrary, T W which is lower than T P , supposes that there is a rather low dependence between the events. Finally, T D gives a zero value to the conjunction of two events unless one of the two has a truth value 1.

Similarly, T * M and T * D are respectively, lower and upper bounds for t-conorms. Thus, if

T * is a t-conorm, we have ∀(a, b) ∈ [0, 1] 2 : T * M (a, b) ≤ T (a, b) ≤ T * D (

a, b)

There also exist numerous parametric t-norms and tconorms. However, we will introduce only one pair of them: the Schweizer-Sklar family for which the nonparametric t-norms and conorms are particular cases.

The Schweizer-Sklar t-norm is given by, ∀λ ∈ [-∞, ∞]:

T λ SS (a, b) =    T M (a, b) λ = -∞ T P (a, b) λ = 0 T D (a, b) λ = ∞ and for λ ∈] -∞, 0[∪]0, ∞[, we have: T λ SS (a, b) = max(a λ + b λ -1, 0) 1 λ
Its corresponding t-conorm is as follows:

T * λ SS (a, b) =    T * M (a, b) λ = -∞ T * P (a, b) λ = 0 T * D (a, b) λ = ∞ and for λ ∈] -∞, 0[∪]0, ∞[, we have: T * λ SS (a, b) = 1 -max((1 -a) λ + (1 -b) λ -1, 0) 1 λ
T-norms or t-conorms can be used as aggregation operators. In that case they represent two extreme point of views which are respectively the conjunction and the disjunction over all their arguments. In our case, this would be the truth value of "object i is relevant for all experts" and the truth measure of "object i is relevant for at least one expert".

Triangular norm ordered weighted averaging operators (TOWA)

Ordered weighted averaging operators (OWA) are well-known aggregation techniques that were introduced by R.R. Yager in the field of multicriteria decision making in [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decision making[END_REF].

In the basic case, OWA operators aggregate a set of values (a 1 , . . . , a M ) with respect to a system of weights (w 1 , . . . , w M ) such that w j ∈ [0, 1]; j = 1, . . . , M and M j=1 w j = 1. Let denote (σ(1), . . . , σ(M )) a permutation of (1, . . . , M ) that satisfies:

a σ(1) ≥ a σ(2) ≥ . . . ≥ a σ(M )
Then the OWA operator is defined as follows:

OWA(a 1 , . . . , a M ) = M j=1 w j a σ(j) (8)
As far as the weighted arithmetic mean is concerned, we can see that the system of weights attributes different measures of importance to the different experts j. On the contrary, OWA functions rather focus on the position with respect to the non-increasing order of the values. In other words, independently of the expert, OWA operators assign the same weight w j to the j th greatest value, a σ(j) , in the sequence of measures to combine.

It is easy to see that OWA functions generalize order statistics. It is a compensatory aggregation operator bounded by the minimum and the maximum of its arguments, unlike t-norms and t-conorms but such as weighted power means.

In [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and owa operators[END_REF][START_REF] Yager | On some properties of mixing owa operators with t-norms and t-conorms[END_REF], the authors consider a particular extension of OWA functions by mixing t-norms and OWA functions. The resulting triangular norm OWA operator (TOWA) is defined below:

TOWA T (a 1 , . . . , a M ) (9) = M j=1 w j T (a σ(1) , . . . , a σ(j) )
where T is a t-norm as described in the previous subsection.

TOWA functions generalize OWA operators since the latter correspond to the former when T = T M . Indeed, in Eq. ( 9), T M (a σ(1) , . . . , a σ(j) ) reduces to a σ(j) which leads to the classical OWA function.

TOWA allows one to take into account two different aspects that are of interest when combining data. First, using different t-norms enables one to consider different kinds of conjunctive relationship between subset of values based upon their position with respect to the non-increasing order. Second, the weight vector allows one to model fuzzy linguistic concepts such as "for all" or "at least m". Regarding those two latter examples, the corresponding weight systems would be: on the one hand, w j = 0; ∀j = M and w M = 1; on the other hand, w j = 0; ∀j = m and w m = 1.

It is easy to see that the case w j = 0; ∀j = M and w M = 1 reduces to the conjunction over all values given by the t-norm since we obtain TOWA T (a 1 , . . . , a M ) = T (a 1 , . . . , a M ). As a result, TOWA T (a 1 , . . . , a M ) is lower bounded by T (a 1 , . . . , a M ) unlike OWA(a 1 , . . . , a M ) whose lower bound is min(a 1 , . . . , a M ). However, both functions are upper bounded by max(a 1 , . . . , a M ).

The distribution of weights allows one to control the compensatory degree (also called orness or andness degrees) of the TOWA functions. A general approach for computing the weights w j ; j = 1, . . . , M , consists in using fuzzy quantifiers. The most used method is based upon regular increasing monotone (RIM) functions denoted Q [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decision making[END_REF]. The latter are functions from

[0, 1] to [0, 1] such that Q(0) = 0, Q(1) = 1 and a < b ⇒ Q(a) ≤ Q(b). Q(a)
gives the degree of satisfaction for the decision maker, when a% of the criteria is fulfilled. Assuming that Q is a RIM function is the same as assuming that the more criteria fulfilled, the greater the satisfaction.

Given Q, one can define a weight vector as follows, ∀j = 1, . . . , M :

w j = Q j M -Q j -1 M (10)
In that case, w j represents the marginal satisfaction a decision maker gets from having j -1 criteria to j criteria fulfilled.

Power functions, Q(a) = a q with q > 0 are examples of RIM functions. In that case, the greater q, the more the TOWA operator has a conjunctive behavior.

Some basic properties of aggregation operators

Let us now replace ourselves in the context of metasearch problems and consider the notations introduced in section 2, Then, in section 3, we have presented the normalization step which is aimed at making the scores between the different search engines comparable. With respect to Eq. ( 4), we propose to normalize the score of elements i between 0 and 1, for each search engine j. The resulting normalized score, denoted S j (i), is a non-negative measure and we proposed to interpret the latter as a truth measure. As a result, all of the aggregation operators that we have recalled previously can be employed.

Let us denote C any of the aggregation functions we have introduced so far. They are all functions from [0, 1] M to [0, 1]. Furthermore, they all respect the following basic properties (see for example [START_REF] Calvo | Aggregation operators: properties, classes and construction methods[END_REF] for a list of basic conditions for aggregation operators):

-Identity when unary:

C(S 1 (i)) = S 1 (i) -Boundary conditions: C(0, . . . , 0) = 0 and C(1, . . . , 1) = 1 -Non-decreasing: {∀j = 1, . . . , M : S j (i) ≤ S j (i )} ⇒ C(S 1 (i), . . . , S M (i)) ≤ C(S 1 (i ), . . . , S M (i )) -Symmetry (or commutativity): C(S 1 (i), . . . , S M (i)) = C(S σ(1) (i), . . . , S σ(M ) (i))
where σ is a permutation of (1, 2, . . . , M ).

Moreover, it is worth mentioning again the different kinds of behavior that an aggregation operator can have: conjunctive (t-norms), disjunctive (tconorms) and compensatory (weighted power means and TOWA). This can be underlined following the relations below:

0 ≤ T ≤ min ≤ M p ≤ max ≤ T * ≤ 1 0 ≤ T ≤ TOWA T ≤ max ≤ T * ≤ 1

A new consensus aggregation operator

In addition to the previous aggregation functions, we introduce a new approach for data fusion. Unlike t-norms and t-conorms which are not compensatory functions and which represent complete conjunctive and disjunctive behaviors, the method we are going to introduce is more compensatory. Thus, it is comparable to weighted quasi-arithmetic means and TOWA functions. After having introduced our proposal, we will particularly underline the relationships it has with the TOWA method.

Basic concepts and theoretical framework

Let us denote by S j (i) the event: "object i is relevant for expert j". Then for each object i, we consider the following set of atomic events X i = {S 1 (i), . . . , S M (i)} and σ(X i ) a σ-algebra over X i . In other words, σ(X i ) is the set of events generated by X i that is closed under set operations.

We give in Fig. 1 a Venn diagram representing the case M = 3. Each circle corresponds to an atomic event. The more irregular regions corresponding to different numbers are mutually disjoint events given by:

(i) ∩ S 2 (i) ∩ S 3 (i) 2 S 2 (i) ∩ S 1 (i) ∩ S 3 (i) 3 S 3 (i) ∩ S 1 (i) ∩ S 2 (i) 4 S 1 (i) ∩ S 3 (i) ∩ S 2 (i) 5 S 1 (i) ∩ S 2 (i) ∩ S 3 (i) 6 S 2 (i) ∩ S 3 (i) ∩ S 1 (i) 7 S 1 (i) ∩ S 2 (i) ∩ S 3 (i) 8 S 1 (i) ∩ S 2 (i) ∩ S 3 (i)
Our assumption is that (X i , σ(X i )) is a measurable space 3 and for all atomic events S j (i); j = 1, . . . , M , we are given a positive measure µ(S j (i)) ≥ 0. Since µ is a measure it then satisfies the σ-additivity property: if A and B are two incompatible events (disjoint sets) then µ(A ∪ B) = µ(A) + µ(B).

If we consider all M experts, we can define the following event: "object i is relevant for at least m experts among M ". We will denote this event E M m (i). Formally, we can define the latter from a set viewpoint as follows, ∀m = 1, . . . , M ; ∀i = 1, . . . , K:

E M m (i) (11)
= 1≤j1<...<jm≤M (S j1 (i), . . . , S jm (i))

Given the measures, µ(S j (i)); j = 1, . . . , M , of event S j (i); j = 1, . . . , M , we are interested in computing the measure of the events E M m (i) for m = 1, . . . , M . This is a combinatorial problem which generalizes Poincaré's formula4 also known as the "inclusionexclusion principle". Since µ is a measure, we can show [START_REF] Jordan | Problèmes de la probabilité des épreuves répétées dans le cas général[END_REF][START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF] that µ(E M m (i)) can be expressed as a linear combination of the following quantities, ∀i = 1, . . . , K:

for l = 1:

S M l (i) = M j=1 µ(S j (i)) (12)
for l = 2, . . . , M :

S M l (i) (13) = 1≤j1<...<jl≤M µ (S j1 (i) ∩ . . . ∩ S jl (i))
This linear combination is related to Jordan's combinatorial formulas [START_REF] Jordan | Problèmes de la probabilité des épreuves répétées dans le cas général[END_REF][START_REF] Comtet | Analyse Combinatoire, tome 1 et tome 2[END_REF], and we have, ∀m = 1, . . . , M ; ∀i = 1, . . . , K:

µ(E M m (i)) = M l=m (-1) l-m l -1 m -1 S M l (i) (14)
where n p = n! p!(n-p)! , are binomial coefficients. We also have the following formulation [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF]:

µ(E M m (i)) = M l=m -m l -m S M l (i) (15)
where

-n p = (-n)(-n-1)...(-n-p+1) p!
, are the negative binomial coefficients.

Designing a consensus aggregation operator

Now that we have introduced the consensus measures µ(E M m ); m = 1, . . . , M , we make the following assumption on which our aggregation function is based: the greater the number of experts who find object i relevant, the higher the aggregated score corresponding to object i must be 5 [START_REF] Lee | Analyses of multiple evidence combination[END_REF].

In a literal formulation, our aggregation function could be defined as follows: we weight by m the measure that object i is relevant for at least m experts then we sum over m from 1 to M and we normalize this aggregated score according to M m=1 m = M (M + 1)/2. As the proposed method gives increasing weights when m, the number of considered experts, grows, it is a method that satisfies the assumption we have mentioned beforehand.

We denote our consensus aggregation function A. It is formally defined by the following equation, ∀i = 5 Notice that baseline methods given in Eq. ( 1) pursue the same goal by weighting by NZ(i, L k ) v the experts score sum. However, our proposal is different in spirit and corresponds to a non-linear and smoother way to reinforce the aggregated scores. See subsection 5.3 for more details.

1, . . . , K:

A(i) = 1 M (M +1) 2 M m=1 mµ(E M m (i)) (16)
In its original formulation given by equations Eqs. ( 14) and ( 13), the computational cost of A(i) is very expensive. Indeed, in order to compute S M l (i) in Eq. ( 13), we need to enumerate M l combinations which grows exponentially. But, as we will show in the following paragraph we can reduce the computational cost of A(i) to O(M 2 ) by using combinatorial properties.

The combinatorial "trick"

From Eq. ( 16) which has an exponential computational cost, we can prove the following statement which enables us to significantly reduce the computational cost of the proposed consensus aggregation operator, ∀i = 1, . . . , K:

A(i) (17) = M j=1 µ(S j (i)) + 1≤j<j ≤M µ(S j (i) ∩ S j (i)) M (M +1) 2
Proof. In order to prove the property given in Eq. ( 17), we will use the two following combinatorial identities 6 :

n p=0 (-1) p n p = 1 {n=0} ( 18
) n p=0 (-1) p+1 n p p = 1 {n=1} (19)
where 1 {P} is the indicator function which equals 1 if proposition P is true; 0 otherwise. We first have:

M (M + 1) 2 A(i) = M m=1 mµ(E M m (i)) = M m=1 m M l=m (-1) l-m l -1 m -1 S M l (i) = M m=1 m M l=1 (-1) l-m l -1 m -1 S M l (i)1 {l≥m} = M l=1 M m=1 m(-1) l-m l -1 m -1 S M l (i)1 {m≤l} = M l=1 l m=1 m(-1) l-m l -1 m -1 S M l (i)
Then we denote m = m -1; l = l -1 and M = M -1. Using these variables we obtain:

M (M + 1) 2 A(i) = M l =0 l m =0 (m + 1)(-1) l -m l m S M +1 l +1 (i) = M l =0 S M +1 l +1 (i) l m =0 (m + 1)(-1) l -m l m = M l =0 S M +1 l +1 (i)   l m =0 (-1) l -m l m + l m =0 (-1) l -m l m m  
Next, if we enumerate a bit this latter expression we can see that using the combinatorial identities given in Eqs. ( 18) and ( 19): we obtain S M 1 (i) for l = 0; S M 2 (i) for l = 1 and we obtain a null quantity, for l > 1. This finally shows that M (M +1) 2

A(i) = S M 1 (i) + S M 2 (i).
We give in Fig. 2, an illustration of the property for M = 3. Given Eq. ( 17), we can see that our proposal goes beyond a simple sum 7 since the introduced aggregation function allows us to take into account pairwise conjunctions between experts. Particularly, we can specify the type of relationship between pairs of experts by using conjunction operations. The following subsection focuses on this aspect.

Conjunction measures and properties of the new aggregation operator

Given an object i, the only data we are provided with are the normalized scores given by each search engine (or experts) (S 1 (i), . . . , S M (i)). As S j (i) is a non-negative measure, we propose to set µ(S j (i)) = S j (i); ∀j = 1, . . . , M, ∀i = 1, . . . , N From these inputs, we need to compute pairwise conjunction measures to apply our aggregation function A according to Eq. ( 17). Since we interpret S j (i) as a truth value, we propose to use t-norms to evaluate 7 As the first part is similar to CombSUM or the arithmetic mean.

the conjunction measures between pairs of experts:

µ(S j (i) ∩ S j (i)) = T (µ(S j (i)), µ(S j (i))) = T (S j (i), S j (i)) (20)
where T is a t-norm such as described in subsection 4.2.

In the unsupervised case we use the same t-norm T for each pair of experts. Therefore we will use the notation A T and we have:

A T (i) (21)
= M j=1 S j (i) + 1≤j<j ≤M T (S j (i), S j (i)) M (M +1) 2
Providing that we use t-norms as conjunction functions, we can precise the basic properties that our proposal satisfies. It is easy to see that A T respect the following conditions (see subsection 4.4):

-Identity when unary -Boundary conditions -Non-decreasing -Symmetry (or commutativity) Besides, we have the following relation:

0 ≤ min i,1≤j<j ≤M T (S j (i), S j (i)) ≤ A T ≤ max ≤ 1
From a more general perspective, one could set for each pair of experts a specific kind of t-norm and even a particular conjunction operator. This is possible if we have any a priori information on the relationships between experts. However, since we focus on unsupervised rank aggregation tasks, we do not assume that we have such expertise and we rather use the approach given by Eq. ( 21).

The relationship between A and TOWA

In [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and owa operators[END_REF][START_REF] Yager | On some properties of mixing owa operators with t-norms and t-conorms[END_REF], the link between TOWA functions and multicriteria decision functions based upon previous works detailed in [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF][START_REF] Yager | General multiple-objective decision functions and linguistically quantified statements[END_REF] is pointed out. In that framework, decision functions are based on events such as "alternative i fulfills at least m criteria among M ". From a set viewpoint, the latter are basically the same as the consensus events we have introduced in Eq. [START_REF] Dubois | On the use of aggregation operations in information fusion processes[END_REF].

More formally, if we replace the notations given in [START_REF] Yager | On some properties of mixing owa operators with t-norms and t-conorms[END_REF] with the ones used in this paper, a decision function D (an aggregation operator actually) that scores an alternative i with respect to a set of M criteria, is defined as follows:

D(i) = M m=1 w m ν(E M m (i)) (22)
where w m ∈ [0, 1]; ∀m = 1, . . . , M ; M m=1 w m = 1 and ν is a fuzzy measure. This is very close to our proposal given in Eq. ( 16). In fact, there are two main differences between Yager's approach and ours:

1. In [START_REF] Yager | Extending multicriteria decision making by mixing t-norms and owa operators[END_REF][START_REF] Yager | On some properties of mixing owa operators with t-norms and t-conorms[END_REF], the measure of the event E M m (i) relies on the possibility paradigm for which, the fuzzy measure of the disjunction between two events A and B is given by ν(A ∪ B) = max(ν(A), ν(B)) whether A or B are disjoints or not. On the contrary, we have made in section 5.1, the assumption that the measure µ respects the classical measure paradigm that is to say the σ-additivity property. In that case, we rather have the following relation:

µ(A ∪ B) = µ(A) + µ(B) if A and B are disjoints and; µ(A ∪ B) = µ(A) + µ(B) - µ(A ∩ B) otherwise. 2.
There are two kinds of parameter for the TOWA: on the one hand, the t-norm(s) 8 for measuring the conjunction between nested subsets of experts ranked, for each object, according to the non-increasing order of their scores; on the other hand, the weight vectors (w 1 , . . . , w M ) such as presented in subsection 4.3. In our case, we definitely set the weight vector to

( 1 M (M +1)/2 , 2 M (M +1)/2 , . . . , M M (M +1)/2
) since this is a reasonable choice to define a consensus aggregation operator. Thus, the weight vector is not a parameter to set anymore. The only type of parameter(s) to set is the t-norm(s) 9 for measuring the conjunction measures of pairs of experts.

Regarding the first point, we can notice that the possibility axiom has the advantage to avoid the complexity issue. Indeed, t-norms are monotonic functions such that, for all m-uple (a j1 , . . . , a jm ):

T (a σ(1) , a σ(2) , . . . , a σ(m) ) ≤ T (a j1 , a j2 , . . . , a jm ) 8 Possibly M different t-norms. 9 Possibly M (M -1)/2 different t-norms.

As a consequence we don not have to enumerate all combinations to compute ν(E M m ) since we have:

ν(E M m ) = max 1≤j1<...<jm≤M T (S j1 (i), . . . , S jm (i)) = T (S σ(1) (i), S σ(2) (i), . . . , S σ(m) (i)) (23)
One can see that if we replace the previous relation in Eq. ( 22) we obtain the definition of TOWA operator given in Eq. [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF].

In comparison to Eq. ( 23) which relies on the possibility paradigm, the σ-additivity axiom leads to combinatorial issues as we can see by considering Jordan's combinatorial formula given in Eq. ( 14) and our definition of aggregation function given in Eq. ( 16). However, by assuming a reasonable condition concerning the weight vectors, as aforementioned in the second point, we have proved in section 5.3, that we can avoid the complexity problem of such an approach. More than a simple combinatorial "trick", the resulting form of our aggregation operator A given in Eq. ( 17) has an interesting semantic. It explicitly enables one to take into account the relationships between experts by considering conjunction measures between each pair of experts. Thus, despite similar basic concepts based on consensus events, our approach finally leads to a really different aggregation techniques in comparison to TOWA. In our method, we model the relationships between experts by considering pairs whereas for TOWA, the relationships between experts is rather based upon nested subsets that depend on the nonincreasing order of their scores.

Experiments and discussion

In this section, using numerical examples, we show that the proposed aggregation operators can perform better than baseline approaches. We first describe the settings of the experiments we made. Then we report and discuss the results we obtained.

Experimental results

We tested the different methods introduced previously, on the three different datasets of the Letor 2.0 package [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF]: For each dataset, we have different queries (topics) and for each ranking feature, we are given a distribution of scores among a set of objects (medical publications or html files). The ranking features are either low-level or high-level content features, between each judged query-document pairs. The reader can consult [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF], for a more detailed description of the characteristics of these datasets and for the definition of the features that were extracted.

-OHSUMED dataset (subset of
The Letor 2.0 package was initially constituted to benchmark "learning to rank" methods. In that context the goal is to learn, from a training set, how to combine the different experts. In our case, we are in an unsupervised context and we only use the relevance file for measuring a posteriori the performances of the proposed methods.

First, we normalized the data using the score normalization 10 given by Eq. ( 4) with k = 1000. Then, we computed the following aggregation functions:

-CombSUM (equivalent to M p with p = 1 and with uniform weights), CombMNZ (with similar settings than CombSUM). -T-norms and t-conorms T M = min and T * M = max.

the power-mean M p with p = 2 and p = 3 and since we don not suppose any a priori information on the importance of each search engine, we took w j = 1/M ; ∀j = 1, . . . , M . -The TOWA T approach with T = T M , T P and T λ SS with λ = 6 and with w j = j M 5 -j-1 M 5 . Regarding Eq. [START_REF] De | On fuzzy result merging for metasearch[END_REF] this corresponds to take Q as a power function with q = 5. We chose this setting following the work presented in [START_REF] De | On fuzzy result merging for metasearch[END_REF] that investigates the application of the TOWA technique (and other OWA based methods) to metasearch problems on similar datasets. In [START_REF] De | On fuzzy result merging for metasearch[END_REF], q = 5 performed better than other settings. Besides, we recall that the case T = T M is the same as the classical OWA function given in Eq. ( 8).

-The new aggregation method A T using either non-parametric t-norms T M , T P or the parametric t-norm T = T λ SS with λ = 6.

For measuring and comparing the performances of the different aggregation methods, we used the trec_eval tool 11 and we retained the mean average precision (MAP) and the precision at 10 (P@10) measures. The results are given in Tables 1, 2 and 3. In italic are the baseline results given by CombSUM. We put in bold the two best results among the aggregation operators we tested.

Discussion

The first conclusion we can draw out from Tables 1, 2 and 3, is that the t-norm T M and the t- 12 . This is not surprising since, as we mentioned earlier, they represent extreme point of views and their behavior are too conjunctive or too disjunctive. They are not well-adapted for metasearch tasks. Furthermore, one could have tried to have a trade-off between the t-norm and the t-conorm such as the so-called convex-linear compensatory operator defined in [START_REF] Zimmermann | Latent connectives in human decision making[END_REF] as (1 -β)T (S 1 (i), . . . , S M (i)) + βT (S 1 (i), . . . , S M (i)). But we can see that this would not work out neither.

As a consequence, and this is confirmed from our results, we need more compensatory aggregation operators when dealing with metasearch problems. Indeed, the other aggregation techniques namely the power mean, the TOWA and our proposal can all perform better than the baseline given by CombSUM.

Nevertheless, the results between all three aforementioned techniques are very close to each other and from our experiments we cannot conclude that one approach consistently outperforms the other ones. This is even true as each of them has different parameters to tune. Finally the three techniques offer three different models.

First the weighted quasi-arithmetic means allow one to assign different weights to experts that must reflect the importance of the latter. However, they do not permit one to model the relationships between them. Furthermore, it is not an easy task to set the function f or even the parameter p in the case of power means, 12 Other t-norms or t-conorms perform similarly as T M and T * M since there is no particular semantic associated to such functions.

On the contrary, TOWA T and A T allow us to take into account different kinds of relationships between experts on the basis of consensus events and this is done by using t-norms among subsets of experts. For TOWA operators, these subsets of experts are different for each object and they are given by the nonincreasing order of the scores. In the case of A T , these subsets are constituted of all pairs of experts and are independent of any object. Finally, despite quite similar results, both methods are different and further experiments need to be pursued to better understand the pros and cons of those two techniques.

Conclusion

In this paper, we have addressed data fusion problems. We have been particularly concerned with unsupervised rank aggregation tasks or metasearch tasks in information retrieval field. The general aim of this work is to investigate the use of some aggregation operators defined in information fusion and multicriteria decision making fields in the context of metasearch problems. We have recalled and tested classical aggregation operators such as weighted quasi-arithmetic means, t-norms, t-conorms and TOWA functions. We have moreover introduced a new aggregation method A, its logical foundations and its combinatorial properties.

Our experiments using the Letor 2.0 package show that t-norms and t-conorms are not good aggregation operators for that kind of tasks since they are not compensatory. On the contrary, more compensative operators such as weighted quasi-arithmetic means, TOWA and A functions can improve the baseline results. The two latter approaches allow to consider the relationships between search engines through two different manners. Because of this general property we think that they are interesting techniques to further study.

As far as our future work is concerned, we intend to apply the studied aggregation operators to "learning to rank" tasks which correspond to supervised rank aggregation problems in information retrieval. Indeed, the different approaches that we have proposed to tackle the metasearch problems in information retrieval need all some paramaters to be tuned. In this paper, we have been in an unsupervised setting and we have set the parameters arbitrarily but to increase the performances of the different non-linear aggregation models, one could estimate their respective parameters by using a training set and machine learning techniques. In that perspective and regarding the different models we have proposed in this paper, one could better capture the efficiency of the search engines or evaluate the relationships between experts and use those pieces of information to better fit the models to the particular data and tasks a user would need to deal with. Thereby, in our future work, we intend to work on the concepts of search engines reliability on the one hand, and learning to model the relationships between search engines on the other hand. Furthermore, more experiments in that context would help us to better compare the different aggregation operators from a practical viewpoint.

Fig. 1 .

 1 Fig. 1. Venn diagram and disjoint regions

Fig. 2 .

 2 Fig. 2. Illustration of the combinatorial "trick" with 3 experts

Table 1

 1

	Results for the OHSUMED dataset
	Method	MAP	P@10
	CombSUM	39.52 %	44.81 %
	CombMNZ	38.68 % 44.34 %
	Quadratic mean	40.37 % 47.36 %
	Cubic mean	40.65 % 47.45 %
	T M	0.82 %	0.38 %
	T * M	39.71 % 49.25 %
	TOWA T with T M	37.21 % 41.79 %
	TOWA T with T P	40.89 % 47.55 %
	TOWA T with T 6 SS	40.50 % 48.68 %
	A T with T M	38.49 % 43.96 %
	A T with T P	39.44 % 44.91 %
	A T with T 6 SS	40.38 %	47.93 %
	Table 2
	Results for the TREC 2003 dataset
	Method	MAP	P@10
	CombSUM	16.83 %	13.20 %
	CombMNZ	15.42 % 12.40 %
	Quadratic mean	16.57 % 13.60 %
	Cubic mean	17.33 % 14.60 %
	T M	0.51 %	1.0 %
	T * M	07.98 % 07.20 %
	TOWA T with T M	13.03 % 11.40 %
	TOWA T with T P	17.38 % 14.60 %
	TOWA T with T 6 SS	18.18 % 14.60 %
	A T with T M	15.86 % 11.80 %
	A T with T P	16.81 % 13.20 %
	A T with T 6 SS	18.52 %	15.40 %

Table 3

 3 Results for the TREC 2004 dataset

	Method	MAP	P@10
	CombSUM	26.81 % 16.53 %
	CombMNZ	23.09 % 14.53 %
	Quadratic mean	29.41 % 16.93 %
	Cubic mean	29.48 % 17.33 %
	T M	0.03 %	0.0 %
	T * M	07.93 % 04.80 %
	TOWA T with T M	18.59 % 12.93 %
	TOWA T with T P	30.76 %	17.73%
	TOWA T with T 6 SS	28.33 % 16.40 %
	A T with T M	22.63 % 15.33 %
	A T with T P	26.78 % 16.40 %
	A T with T 6 SS	29.90 % 16.53 %
	conorm T * M perform very badly compared to the
	baseline

We particularly recall the triangular norm ordered weighted averaging function in subsection 4.3.

It is not in general a probabilistic space since we cannot guarantee that the probabilities of the disjoint sets, depicted in Fig.1for example, always sum to 1.

[START_REF] Bloch | Information Combination Operators for Data Fusion: A Comparative Review with Classification[END_REF] Poincaré's formula corresponds to the case m = 1.

For identities and properties referring to binomial coefficients and Pascal's triangle, a good reference is the following website http://binomial.csueastbay.edu/.

We found that it may happen that for some features, a unique value is assigned to all objects. In that case, we replaced this value by 0.

cf. http://trec.nist.gov/


Julien Ah-Pine
email: julien.ah-pine@eric.univ-lyon2.fr

A general framework for comparing heterogeneous binary relations

We propose a general framework for measuring the proximity between heterogeneous binary relations. We are particularly interested in equivalence relations (or partitions, or categorical variables) on the one hand, and in order relations (or rankings or ranked data) on the other hand. We study Kendall's general correlation coefficient that encompasses many statistical association measures for both types of binary relations. Then, we propose a generalization of this approach. Our proposal has several interesting properties. It addresses the case of heterogeneous binary relations, it has a well-motivated geometrical interpretation and it also leads to Euclidean metrics.

Introduction

Binary relations (BR) are fundamental mathematical concepts that allow structuring a set of items or objects in intelligent ways. Among the different types of BR, equivalence relations (ER) and order relations (OR) are ubiquitous. Some examples of ER are : "is similar to", "has the same predicate than", "belongs to the same group as", . . . and some illustrations of OR are : "is lower than", "is preferred to", "is ranked above than", . . . Such types of data are relational since they encode the relationship between items unlike more classical representations of objects described by features. There are many situations where we have to deal with such relational data. For instance, in the statistical literature, research works in categorical data analysis study ER while in non-parametric statistics one is interested in the OR underlying quantitative variables. In both topics, association measures have been proposed in order to compare two ER and two OR.

In this paper, we design a general framework for measuring the proximity between BR. Our framework addresses heterogeneous BR where ER can have different numbers of equivalence classes with different cardinals and OR can be partial and/or with ties. We propose to extend Kendall's general correlation coefficient Γ which is a formula used in many ways in order to compare ER and OR. Our generalization proceeds in two steps. In section 2, after recalling some basics about BR, we firstly reformulate Kendall's Γ in the Relational Analysis (RA) framework. This approach allows us to propose an unifying formula for both ER and OR which emphasizes the relational nature of such data and which also relies on the indeterminacy principle. Secondly, in section 3, we extend Kendall's Γ in the goal of dealing with heterogeneous BR in a more effective manner. In that perspective, we introduce a family of proximity measures called similarity of order t. These measures have a clear geometrical interpretation and result in Euclidean metrics. Finally, we conclude this paper and sketch some future work in section 4.

2 Measures for BR using relational matrices

BR and relational matrices

A binary relation R on a set of objects A = {. . . , i, j, . . .} with |A| = n, is a couple (A, G(R)), where G(R) called the graph of the relation R, is a subset of the Cartesian product A 2 . If (i, j) ∈ G(R), then we say that i is in relation with j for R. This will be denoted by iRj. We can associate to a BR R, its complement which is a BR denoted by R and whose graph is defined by, ∀i, j ∈

A : (i, j) ∈ G(R) ⇔ (i, j) / ∈ G(R)
. Furthermore, we can derive from R its inverse (also called its converse) which is also a BR that we denote by Ȓ and whose definition is given by, ∀i, j

∈ A : (i, j) ∈ G( Ȓ) ⇔ (j, i) ∈ G(R).
There are different properties that a BR can satisfy. Some of the most used ones are : reflexivity, ∀i (iRi); symmetry, ∀i, j (iRj ⇒ jRi); antisymmetry, ∀i, j ((iRj ∧ jRi) ⇒ i = j); complete (or total), ∀i = j (iRj ∨ jRi); transitivity, ∀i, j, k ((iRj ∧ jRk) ⇒ iRk).

The BR we are interested in are defined as follows : ER are reflexive, symmetric and transitive; preorders are reflexive and transitive; partial orders are reflexive, antisymmetric and transitive; total (or linear or complete) orders are reflexive, antisymmetric, transitive and complete. Concerning OR, total orders are rankings without missing values and without ties, partial orders are rankings without ties but missing values can occur; complete preorders are rankings without missing values but with possible ties and preorder are rankings with possible missing values and ties.

In the RA approach [START_REF] Marcotorchino | Optimisation en analyse ordinale des données[END_REF][START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF][START_REF] Ah-Pine | Overview of the relational analysis approach in data-mining and multi-criteria decision making[END_REF], BR are represented by their adjacency matrices that are called more specifically relational matrices (RM) in this context. We denote by R the RM of the BR R, which is a binary pairwise comparison matrix whose general term is given by, ∀i, j : R ij = 1 if iRj and R ij = 0 if iRj. Besides, we will respectively denote by R and Ȓ the RM of the complement and inverse of R. Using RM, the relational properties of BR can be expressed as linear equations. This is a first interesting feature of RA which allows aggregating binary relations using 0-1 integer linear programming [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF][START_REF] Ah-Pine | On aggregating binary relations using 0-1 integer linear programming[END_REF]. However, in this paper, we focus on a second kind of contributions of this approach which concerns statistical association measures. We review this topic and propose the first generalization of Kendall's Γ in the next paragraph.

Measures based on Kendall's Γ and RM

In his famous book [START_REF] Kendall | Rank correlation methods, 4th Edition[END_REF], Kendall proposed a general correlation coefficient in order to define a broad family of association measures. Even if his proposal initially aimed at rankings, it can also be adapted to categorical variables. Let x and y be two given variables of measurements on A. Kendall's Γ takes the following general form :

Γ (x, y) = i,j X ij Y ij i,j X 2 ij i,j Y 2 ij (1)
where X and Y are two square matrices derived from x and y. This coefficient is symmetric and both variables are treated the same way. Hereafter, we thus mention the transformation for x only.

Let us start with ER. In that case, x and y are two categorical variables with p x and p y categories and categories sets denoted {1, . . . , p x } and {1, . . . , p y }. We denote by n x u the total number of items in category u ∈ {1, . . . , p x }. In [START_REF] Vegelius | Criteria for symmetric measures of association for nominal data[END_REF], Janson and Vegelius suggested to adapt Kendall's approach to categorical variables. They particularly showed that when

X ij = (n/n x u ) -1 if x i = x j and X ij = -1 if x i = x j ,
we obtain Tchuprow's T coefficient. Another interesting measure, called the J-index, that was proposed by the same authors, is given by :

X ij = p x -1 if x i = x j and X ij = -1 if x i = x j .
Suppose now that x and y are quantitative variables. If we compare the measures assigned to all pairs (i, j) ∈ A 2 we obtain two OR of the type "is lower than". In [START_REF] Kendall | Rank correlation methods, 4th Edition[END_REF], Kendall proposed the following setting to measure the dependence between x and y from a non-parametric perspective :

X ij = 1 if x i < x j and X ij = -1 if x i > x j . In that case, i,j X ij Y ij
is twice the number of concordant pairs minus twice the number of discordant pairs while i,j X 2 ij gives n(n -1). The resulting coefficient is Kendall's popular τ a . Another famous rank correlation measure is Spearman's ρ a statistic. In that case, we assume that x i and y i are the ranks associated to i according to X and Y . Then, ρ a is given by

X ij = x i -x j .
Let X and Y be the BR implicitly encoded by x and y and let X and Y be their respective RM. Then, we introduce the notation X which represents the opposite relation of X in a general way. In our case, X will refer to X if X is an ER and to X if X is an OR. In other words, if X is an ER ("is in the same category as") then we consider its complement ("is not in the same category as") as its opposite whereas if X is an OR ("is lower than") its opposite is its inverse ("is greater than"). We propose the following expression denoted Λ that generalizes Kendall's Γ by explicitly integrating the RM X, Y, X and Y :

Λ(X, Y, µ, µ) = i,j (µ x ij X ij -µ x ij X ij )(µ y ij Y ij -µ y ij Y ij ) i,j (µ x ij X ij -µ x ij X ij ) 2 i,j (µ y ij Y ij -µ y ij Y ij ) 2 (2)
where ∀i, j ∈ A : µ x ij and µ x ij are non-negative weights for iXj and i Xj. There have been many research works about using RM to better understand the differences between association measures [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences parties I, II et III[END_REF][START_REF] Ghashghaie | Agrégation Relationnelle des donnèes ordinales[END_REF][START_REF] Najah Idrissi | Contribution à l'unification de critères d'association pour variables qualitatives[END_REF][START_REF] Marcotorchino | Paradigme logique des écritures relationnelles de quelques critères fondamentaux d'association[END_REF][START_REF] Youness | Some measures of agreement between close partitions[END_REF]. In this paper, (2) follows the formalism proposed in [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF] which underlines the weighted indeterminacy situation between two BR. This concept was first introduced in [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences parties I, II et III[END_REF] and lately studied in the case of ER in [START_REF] Ah-Pine | Unifying some association criteria between partitions by using relational matrices[END_REF]. In order to better understand how (2) generalizes Kendall's Γ and the weighted indeterminacy concept as well, it is worth emphasizing the roles played by the weights µ x ij and µ x ij . Indeed, µ and µ should be viewed as mappings reflecting weighting models which, given a RM X and a pair (i, j), assign a non-negative value to X ij (iXj) and to X ij (i Xj). In our framework, the semantic underlying weighting models is what allows differentiating coefficients from one to another.

Accordingly, the following results show that (2) indeed encompasses1 famous coefficients derived from Kendall's Γ . As for ER, the findings in [START_REF] Vegelius | Criteria for symmetric measures of association for nominal data[END_REF] and [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences parties I, II et III[END_REF][START_REF] Najah Idrissi | Contribution à l'unification de critères d'association pour variables qualitatives[END_REF] enable us to state the following particular cases of Λ :

µ x ij = [( i X ij + j X ij )/2] -1 -1/n = [ j X ij ] -1 -1/n and µ x ij = 1/n leads to Tchuprow's T co- efficient; µ x ij = 1-1/ i,j [2X ij /( i X ij + j X ij )] 2 = 1-1/ i,j [X ij / j X ij ] 2 = 1 -1/p x and µ x ij = 1/p x gives the J-index; µ x ij = µ x ij = 1 is related to Rand's in- dex; µ x ij = 1 -i,j X ij /n 2 and µ x ij = i,j X ij /n 2 is Pearson's product-moment correlation coefficient on a fourfold contingency tables.
Regarding OR, the results provided in [START_REF] Kendall | Rank correlation methods, 4th Edition[END_REF] and [START_REF] Ghashghaie | Agrégation Relationnelle des donnèes ordinales[END_REF][START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF], allow establishing the following cases derived from [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF]. If X and Y are total orders then Λ with µ x ij = μx ij = 1 gives Kendall's τ a and Λ with µ x ij = x i -x j and μx ij = x j -x i leads to Spearman's ρ a . However, if X and Y are preorders then the previous weighting schemes respectively give Kendall's τ b and Spearman's ρ b which were meant to better take tied ranks into account. As a consequence, what is remarkable with ( 2) is that it allows unifying in a unique framework, well-known association measures for both ER and OR. Moreover, this approach has the particularity to highlight the relational nature of the variables by explicitly using their RM.

Next, we explain the indeterminacy concept between two BR on which (2) is based. This concept is different from the statistical independence principle, and it can be better understood by looking at the numerators of (2) when it is equal to 0. In such a case we have :

(µ x ij X ij -µ x ij X ij )(µ y ij Y ij -µ y ij Y ij ) = 0 ⇔ µ x ij µ y ij X ij Y ij 11 + µ x ij µ y ij X ij Y ij 00 = µ x ij µ y ij X ij Y ij 10 + µ x ij µ y ij X ij Y ij

01

(3) In (3) the left hand side 11 + 00 corresponds to the total weight of agreement or concordant pairs between the two BR whereas the right hand side 10 + 01 represents the total weight of disagreement or discordant pairs. Typically the weighted indeterminacy situation is when both total weights are equal. Suppose the classical case where all µ and µ are uniform, then indeterminacy means that there are as many agreement pairs as disagreement pairs. Note that the correlation between x and y is positive if the weighted agreement is greater than the weighted disagreement and it is negative otherwise. Therefore, our first generalization of Kendall's Γ is based on the weighted indeterminacy concept which gives a clear interpretation of the correlation between two BR in terms of the difference between the weighted agreement and the weighted disagreement.

In the next paragraph, we propose to generalize (2) further in order to better treat heterogeneous BR.

3 Similarity of order t and generalization of Kendall's Γ

Weighted Symmetric RM as vectors in an Euclidean space

Our goal now, is to extend the previously introduced Λ measure in order to deal with heterogeneous BR. Note that this can be partly done using Λ by choosing adequate weighting schemes. For instance, we previously showed that (2) embeds Kendall's τ b which better deals with tied ranks. However, we argue that we can also model such a heterogeneity from a geometrical perspective. To this end, we introduce the concept of weighted symmetric RM (WSRM) of a variable x, denoted by X and defined as follows, ∀i, j ∈ A :

X ij = µ x ij X ij -µ x ij X ij (4)
Moreover, let us denote by M n , the vectorial space of real valued square matrix of size n. Given a variable x we can represent its underlying BR by the RM X, X, and by the WSRM X associated with µ and µ. All of the latter matrices are elements of M n . Furthermore, let us equip M n with the Frobenius inner product denoted by ., . , and defined by,

∀X, Y ∈ M n : X, Y = i,j X ij Y ij .
Using WSRM in this geometrical framework, (2) can be written as below :

Λ(X, Y, µ, µ) = i,j X ij Y ij i,j X 2 ij i,j Y 2 ij = X, Y X, X Y, Y (5)
In other terms Λ is the cosine of the angular measure between vectors X and Y. In this context, we argue that ER with different numbers of groups and/or with different distributions give WSRM with distinct norms. Vectors norms can even be more different depending on the weighting models µ and µ. The same kind of observation can be made with regard to heterogeneous OR. Indeed, two vectors X and Y representing two total orders, have the same norm but this is no longer true when OR are partial and/or with ties. Accordingly, we argue that in order to deal with the heterogeneity of BR when comparing them, one has to penalize the difference between the norms of associated WSRM. In the next paragraph, we introduce a method which takes this point into account.

Similarity of order t and application to WSRM vectors

We present a family of proximity measures called similarity of order t with t > 0 which was initially introduced in [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF] and lately applied to kernels normalization in [START_REF] Ah-Pine | Normalized kernels as similarity indices[END_REF]. We apply this approach within the framework we have set up previously and we show how our method defines a family of association measures for heterogeneous BR. To this end, we give below the formal definition of similarities of order t, denoted by S t and which are applied to two BR X and Y that were derived from two variables x and y :

S t (X, Y, µ, µ) = i,j (µ x ij X ij -µ x ij X ij )(µ y ij Y ij -µ y ij Y ij ) 1 2 i,j (µ x ij X ij -µ x ij X ij ) 2 t + i,j (µ y ij Y ij -µ y ij Y ij ) 2 t 1/t = X, Y M t ( X, X , Y, Y ) (6)
where M t (a, b) = [ 1 2 (a t +b t )] 1/t is the generalized power mean of order t. In order be rigorous regarding the notations, we use S t (X, Y) to refer to the similarity of order t when WSRM are used as inputs such as in the second line of (6). On the contrary, we use S t (X, Y, µ, µ) to make explicit the two types of inputs we initially have i.e. the RM (X, Y) and the weighting models (µ, µ). However, the reader has to keep in mind that S t (X, Y, µ, µ) is similar to S t (X, Y) where X was determined from X, µ, µ, by using (4), beforehand.

In [START_REF] Vegelius | Criteria for symmetric measures of association for nominal data[END_REF], we have introduced the use of generalized power means. Particular cases of M t are the following ones : the limit when t → 0 gives the geometric mean; t = 1 is the arithmetic mean; the limit when t → ∞ gives the maximum. The reason we consider t positive only is given later on. Before, we observe that (6) generalizes ( 5) since the latter equation is the limit of the former one when t → 0. Next, let us denote by θ(X, Y) and γ(X, Y) = max( X, X , Y, Y )/ min( X, X , Y, Y ) the angular measure and the norms ratio between X and Y. To simplify the formulas we use the shorthands θ and γ. Using these geometrical measures, (5) can be equivalently written as follows [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF][START_REF] Ah-Pine | Normalized kernels as similarity indices[END_REF] :

S t (X, Y, µ, µ) = cos θ M t (γ, γ -1 ) (7)
The semantic of S t can be apprehended from [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences parties I, II et III[END_REF] by considering the two geometric features we have introduced. Note that cos θ ∈ [-1, 1] whereas γ ∈ [1, ∞[. Therefore, the sign of S t is given by the cosine measure. In [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF][START_REF] Ah-Pine | Normalized kernels as similarity indices[END_REF], it was shown that ∀t > 0 : in the limit case t → 0, γ has no effect on S t ; S t is monotonically increasing w.r.t. cos θ; if cos θ > 0 then S t is monotonically decreasing w.r.t. γ (converging towards 0); on the contrary if cos θ < 0 then S t is monotonically increasing w.r.t. γ (also converging towards 0). Intuitively, the norms ratio γ aims at refining the cosine measure in the following sense : given two vectors, the greater the difference between their norms is, the less significant the cosine measure is as a similarity value and therefore the lower the amplitude of the similarity value should be. For instance, in the limit case γ → ∞, whatever the value of cos θ, the proximity measure is close to 0. S t enables refining the cosine index by penalizing it on the basis of the difference between the vectors norms. Thus, this feature allows S t to deal with heterogeneous BR better than Λ.

In this framework, the real parameter t > 0 enables monitoring the strength of this penalization : as t grows the penalization is stronger and the similarity index of order t ranges from one limit case t → 0 to the other one t → ∞ which are respectively given by S t→0 (X, Y, µ, µ) = cos θ and S t→∞ (X, Y, µ, µ) = cos θ/γ.

Moreover, S t measures satisfy the following axioms in regard to similarity indices [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF][START_REF] Ah-Pine | Normalized kernels as similarity indices[END_REF]. We have, ∀t >

0, ∀X, Y ∈ M n : boundedness, |S t (X, Y)| ≤ 1; max- imal self-similarity, S t (X, = 1; symmetry, S t (X, Y) = S t (Y, X); indiscernibility of identicals, x = y ⇒ S t (X, Y) = 1; identity of indiscernibles 2 , S t (X, Y) = 1 ⇒ x = y; order relation on S t , ∀t ≥ t > 0 : |S t (X, Y)| ≤ |S t (X, Y)| 3 .
One other attractive property of S t indices is given below :

Theorem 1. If t > 0 then the square matrix of general term S t (X, Y) is positive semi-definite.

This result can be proved by using Gershgorin circle theorem [START_REF] Ah-Pine | Normalized kernels as similarity indices[END_REF]. Besides, by using theorem 6 of [START_REF] Gower | Metric and euclidean properties of dissimilarity coefficients[END_REF], we can deduce the following corollary of theorem 1 :

Corollary 1. If t > 0 then the square matrix of general term D t (X, Y) = 2 -1 (1 -S t (X, Y)) is Euclidean.
In other words, the rows X and columns Y of D t are points of M n that can be represented in an Euclidean space such that D t (X, Y) are their pairwise Euclidean distance values.

Next, we present another geometrical interpretation of S t which brings some other insights about this method. Let us denote the orthogonal projection of X on Y by P Y (X)Y where P Y (X) = X, Y / Y, Y is called the scalar projection. The orthogonal projection of X on Y is the best approximation of the former vector given the latter one according to the least square approach. In that case, the scalar projection is a real value that expresses an asymmetric proximity relationship between the two vectors. Similarly, we can use P X (Y) = X, Y / X, X as another asymmetric measure when comparing X and Y. We can mix scalar projections in order to have a symmetric coefficient. In that perspective, we can relate scalar projections with S t by the following formula [START_REF] Ah-Pine | Sur des aspects algébriques et combinatoires de l'Analyse Relationnelle[END_REF][START_REF] Ah-Pine | Normalized kernels as similarity indices[END_REF], ∀t > 0 : S t (X, Y, µ, µ) = M -t (P Y (X), P X (Y)) [START_REF] Ghashghaie | Agrégation Relationnelle des donnèes ordinales[END_REF] Regarding OR, it is worth mentioning that when µ ij = μij = 1 for all (i, j), P Y (X) is Somers's asymmetric measure d and S 1 (X, Y, µ, µ) is Kim's d index.

Finally, we point out the particular weighting models given by, ∀(i, j) ∈ A2 : µ x ij = 1 and µ x ij = 0. In that case, the opposite relation in (4) vanishes, and the WSRM X reduces to the RM X in all other following equations. In this case, S t given in ( 6) is related to some similarity indices for binary vectors. Accordingly, our framework also encompasses the generalization to BR of measures such as Ochiaï or Dice indices. Indeed, the two latter measures are given by the limit case t → 0 and t = 1. There are plenty similarity indices for binary vectors and classifying them in order to better understand their differences is a challenge which is tackled in [START_REF] Marcotorchino | Essai de Typologie Structurelle des Indices de Similarité Vectoriels par Unification Relationnelle[END_REF]. The framework we propose can thus partly help in this research line.

Due to space restriction, we were not able to give all the details of these properties.

Note that the limit case t → 0 (the cosine index) does not satisfy this property.

Showing that when t grows the amplitude of S t decreases.

Conclusion and future work

We have generalized Kendall's Γ coefficient and proposed an unifying framework to define association or proximity measures for the comparison of heterogeneous ER and OR. Our method presents several attractive features that we have shown from a theoretical viewpoint. Due to space restriction, we were not able to illustrate these properties on practical examples. We will thus target applications of our method in future work. In that perspective, it is worth noticing that the metric properties of S t allow using classical data analysis tools such as Multidimensional Scaling in order to represent heterogeneous BR in Euclidean spaces.