Patrick Meyer
email: patrick.meyer@uni.lu

Marc Roubens

On the use of the Choquet integral with fuzzy numbers in multiple criteria decision support

Keywords: Multiple criteria decision support, Fuzzy partial evaluations, Choquet integral, Choice, Ranking

This paper presents a multiple criteria decision support approach in order to build a ranking and suggest a best choice 1 on a set of alternatives. The partial evaluations of the alternatives on the points of view can be fuzzy numbers. The aggregation is performed through the use of a fuzzy extension of the Choquet integral. We detail how to assess the coefficients of the aggregation operator by using alternatives which are well-known to the decision maker, and which originate from his domain of expertise.

Introduction

This paper presents a multiple criteria decision support approach which aims at building a ranking and a best choice recommendation on a set of alternatives A. The work is based on a multiple criteria sorting procedure proposed in [START_REF] Marichal | Sorting multiattribute alternatives: The TOMASO method[END_REF] and later in [START_REF] Meyer | Choice, ranking and sorting in fuzzy multiple criteria decision aid[END_REF]. Here, we present an extension to the general case where alternatives are described by fuzzy partial evaluations. In real life problems, this extension can be very useful, as very often it is difficult to determine an exact value for alternatives on certain points of view.

As an example one can consider the hypothetical problem of the localisation of a large factory in a country. The alternatives represent different areas and among the points of view one can find for example the number of direct and indirect working places which will be created. It seems obvious that for most of the areas it will be hard to determine their exact evaluation on this point of view. Nevertheless, it is probably possible to determine a range of values which may apply with more or less credibility. This small example shows that the use of imprecise information as evaluations can be useful in a lot of situations.

One possible way to represent such imprecise information is by fuzzy numbers. In particular, in the context of multiple criteria decision support, it can be quite useful to consider trapezoidal or triangular fuzzy numbers (see Section 2) for the partial evaluations.

We briefly recall general results in Section 2 and focus on trapezoidal and triangular fuzzy numbers. Then, in Section 3, we present the context of the multiple criteria decision support problem we are dealing with here. Section 4 recalls a few results on the aggregation by means of a Choquet integral. Later, in Section 5 we show how to extend the Choquet integral [START_REF] Choquet | Theory of capacities[END_REF] by Zadeh's extension principle [START_REF] Zadeh | Fuzzy sets[END_REF]. In Section 6, we present 2 possible rankings and a best choice procedure on the alternatives of A. An important point is dealt with in Section 7 where we show how to assess the coefficients of the Choquet integral from well-known alternatives.

Preliminary considerations

In this section, we first recall general concepts on fuzzy sets, fuzzy numbers and possibility distributions. In 1965, Zadeh [START_REF] Zadeh | Fuzzy sets[END_REF] introduced the concept of fuzzy set to be able to represent and manipulate data which have nonstatistical uncertainty or in case of impreciseness. Let X be a classical set. A fuzzy set Y in X can be defined by its membership function

Y : X → [0, 1]. For x ∈ X, Y (x) = 0 means that x does not belong to Y , Y (x) = 1 represents the complete membership of x to Y ,
and the values between 0 and 1 stand for intermediate memberships. We write Y (x) = Y (x) for the degree of membership of the element x in the fuzzy set Y , for each x in X.

The support Y of a fuzzy set Y of X is the crisp set of elements of X for which the membership degree to Y is non-zero,

Y = {x ∈ X : Y (x) > 0}. A fuzzy set Y of X is said to be normal if there exists an element x in Y for which Y (x) = 1. Let us call cl( Y ) the closure of the support of Y . A -level set of a fuzzy set Y of X is given by [ Y ] = {x ∈ X : Y (x) } if > 0, cl( Y ) if = 0. A fuzzy set Y of X is said to be convex if [ Y ] is a convex subset of Y for all ∈ [0, 1].
A fuzzy number x of R is a fuzzy set Y in R that is normal, convex and has a continuous membership function of bounded support. Let F be the family of all fuzzy numbers. For a fuzzy number x ∈ F we define

a m ( ) = min [ x] , a M ( ) = max [ x] .
We now can introduce the concept of possibility distributions by means of the fuzzy numbers as defined in [START_REF] Zadeh | Fuzzy sets[END_REF] and [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF]. This allows to see fuzzy numbers as possibility distributions. Let a, b ∈ R ∪ {-∞, +∞} with a b. The possibility that x ∈ F takes its value from the interval [a, b] is defined by

Pos( x ∈ [a, b]) = max x∈[a,b]
x(x).

In particular for ∈ [0, 1],

Pos( x a m ( )) = max x a m ( ) x(x) = , Pos( x a M ( )) = max x a M ( ) x(x) = .
In [START_REF] Dubois | Fuzzy Sets and Systems: Theory and Application[END_REF] the authors write a fuzzy number in a very general way as A particular type of fuzzy numbers are the trapezoidal fuzzy numbers. They can be very useful in the framework of multiple criteria decision support which is presented in Section 3. A fuzzy number x is called a trapezoidal fuzzy number if its membership function can be written as

x(x) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ L a -x if a - x a, 1 i fa < x b, R x -b if b < x b + , 0 otherwise, where [a, b] is the peak of x, L, R : [0, 1] → [0,
x(x) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 - a -x if a - x a, 1 i fa < x b, 1 - x -b if b < x b + , 0 otherwise.
and are called the left and right width. We use the notation x = (a, b, , ). One can show that

[ x] = [a -(1 - ) , b + (1 -) ],
for all ∈ [0, 1]. In the particular case where a = b the fuzzy number is called triangular and a is said to be the centre of x.

In order to be able to use mathematical operations on the fuzzy numbers, Zadeh [START_REF] Zadeh | Fuzzy sets[END_REF] introduces the sup-min extension principle which allows to work consistently with the crisp case. If x 1 , . . . , x n ∈ F and f : R n → R is a continuous function, then the sup-min extension principle is defined by

f ( x 1 , . . . , x n )(y) = sup f (x 1 ,...,x n )=y min{ x 1 (x 1 ), . . . , x n (x n )} ∀y ∈ R.
It has been shown in [START_REF] Nguyen | A note on the extension principle for fuzzy sets[END_REF] that f ( x 1 , . . . , x n ) is a fuzzy number.

In the following section, we present the multiple criteria decision support problem which we aim at solving in this paper.

A particular multiple criteria decision support framework

Let A be a set of q alternatives and N = {1, . . . , n} be a label set of points of view. The partial evaluation of each alternative for each point of view is made on an interval scale. It accepts as admissible transformation function a positive linear transformation (see [START_REF] Roberts | Measurement Theory[END_REF]). Moreover the evaluations are supposed to be commensurable. We can then suppose without any loss of precision that the performance scale of each point of view is the closed continuous unit interval [0, 1].

The particular case we are actually presenting here is where the evaluations of the alternatives on the points of view are fuzzy numbers. This means that each alternative x ∈ A can be identified with its corresponding fuzzy profile

x ≡ ( x 1 , . . . , x n ) ∈ [0, 1] n ,
where for any i ∈ N , x i represents the partial evaluation of x on point of view i.

In order to suggest a ranking of the alternatives of A to the decision maker, one possible way is given below:

• Aggregate the partial evaluations of each alternative on the points of view in a global evaluation.

• Order these global evaluations to obtain a ranking.

Classically, the weighted sum is often used as an aggregation operator. This additive representation, however, implies preferential independence of the points of view. One way to avoid this independence condition is to use the Choquet integral [START_REF] Choquet | Theory of capacities[END_REF][START_REF] Grabisch | Fuzzy measures and integrals[END_REF] as an aggregation operator.

A further hypothesis has to be made here in order to be able to use Zadeh's extension principle. Let x 1 , . . . , x n be fuzzy numbers. A fuzzy number c of R n is called the joint possibility distribution of x 1 , . . . , x n if it satisfies

c(x 1 , . . . , x n ) min{ x 1 (x 1 ), . . . , x n (x n )} ∀x i ∈ R, i = 1, . . . , n. Equivalently [ c] ⊆ [ x 1 ] × • • • × [ x n ] for all ∈ [0, 1]. Fuzzy numbers x i ∈ F, i = 1, . . . , n are said to be non- interactive if [ c] = [ x 1 ] × • • • × [ x n ] for all ∈ [0, 1].
Zadeh implicitly supposes that the fuzzy numbers have to be non-interactive in the extension principle.

In the sequel, we suppose that the partial evaluations of the alternatives, represented by fuzzy numbers, are noninteractive (in the sense discussed above). Nevertheless, this does not mean that the points of view cannot interact. On the level of the points of view, different types of interactions can occur. For example, one can have substitution2 , complementarity 3 or preferential dependence 4 . These types of interactions among the points of view can be expressed by a Choquet integral (and clearly not by a weighted sum).

In the following section, we present this aggregation operator which allows to deal with interacting points of view, namely the Choquet integral.

The Choquet integral as an aggregation operator

Let us consider an alternative x ∈ A which is described by crisp partial evaluations x i , (i ∈ N). The Choquet integral of x is then defined by

C v (x) := n i=1 x (i) [v(A (i) ) -v(A (i+1) )],
where v represents a fuzzy measure on N, that is a monotone set function v : 2 N → [0, 1] fulfilling v(∅) = 0 and v(N) = 1. This fuzzy measure merely expresses the importance of each subset of points of view. The parentheses used for indexes represent a permutation on N such that

x (1) • • • x (n) ,
and

A (i) represents the subset {(i), . . . , (n)}, A (n+1) = ∅ by convention.
If points of view cannot be considered as being independent, the importance of the combinations S ⊆ N , namely v(S) has to be taken into account.

The Choquet integral presents standard properties for aggregation [START_REF] Marichal | An axiomatic approach of the discrete Choquet integral as a tool to aggregate interacting criteria[END_REF][START_REF] Wakker | Additive Representations of Preferences: A New Foundation of Decision Analysis[END_REF][START_REF] Marichal | Aggregation of interacting criteria by means of the discrete Choquet integral[END_REF]: it is continuous, non decreasing, located between min and max.

The major advantage linked to the use of the Choquet integral derives from the large number of coefficients (2 n -2) associated with a fuzzy measure. On the other hand, this flexibility can also be considered as a serious drawback, especially when assigning real values to the importance of all possible combinations.

Let us present an equivalent definition of the Choquet integral which will be used in the context of fuzzy partial evaluations. Let v be a fuzzy measure on N . The Möbius transform of v is a set function m : 2 N → R defined by

m(S) = T ⊆S (-1) |S|-|T | v(T ) (S ⊆ N).
This transformation is invertible and thus constitutes an equivalent form of a fuzzy measure. v can be recovered from m by using

v(S) = T ⊆S m(T ) (S ⊆ N).
This transformation can be used to redefine the Choquet integral without reordering the partial scores:

C m (x) = T ⊆N m(T ) i∈T x i .
(

A fuzzy measure is k-additive [START_REF] Grabisch | k-order additive discrete fuzzy measure and their representation[END_REF] if its Möbius transform m satisfies m(S) = 0 for S such that |S| > k and there exists at least one subset S such that |S| = k and m(S) = ∅. Thus, k-additive fuzzy measures can be represented by at most k i=1 ( n i ) coefficients. For a k-additive fuzzy measure,

C m (x) = T ⊆N |T | k m(T ) i∈T x i .
In order to be able to use fuzzy partial evaluations, we define the fuzzy extension of the Choquet integral in the following section.

A fuzzy extension of the Choquet integral

We can see that definition (1) of the Choquet integral in terms of a set function m is a combination of functions which are continuous on R × R, namely the addition (+), the multiplication (•) and the minimum (∧) functions.

By using the extension principle of Zadeh described in Section 2 one can extend these three functions to their fuzzy versions.

First of all, the extension + of the addition of two real numbers to two fuzzy numbers can be defined as

x 1 + x 2 (y) = sup a+b=y min [ x 1 (a), x 2 (b)].
The result is a fuzzy number according to [START_REF] Nguyen | A note on the extension principle for fuzzy sets[END_REF]. In particular, the sum of two trapezoidal (resp. triangular) fuzzy numbers remains a trapezoidal (triangular) fuzzy number. Let us consider two trapezoidal fuzzy numbers x = (a x , b x , x , x ) and y = (a y , b y , y , y ). According to the definition of the sum of two fuzzy numbers we have x + y = (a x + a y , b x + b y , x + y , x + y ).

The multiplication, in our case, is a scalar multiplication of a fuzzy number by a crisp number p ∈ R (a coefficient of m). p • x is such that

[p • x 1 ] = p[ x 1 ]
for any ∈ [0, 1]. Again, the result of this scalar multiplication is a fuzzy number. In the particular case of a trapezoidal (triangular) fuzzy number, the output remains a trapezoidal (triangular) fuzzy number. For a trapezoidal number x = (a x , b x , x , x ) we have p x = (pa x , pb x , p x , p x ).

Finally, the extension ∧ of the minimum of two crisp numbers becomes

( x 1 , x 2 )(y) = sup min(a,b)=y min [ x 1 (a), x 2 (b)].
Again the result is a fuzzy number. But in the special case of trapezoidal or triangular fuzzy numbers, the result no longer remains a trapezoidal or triangular fuzzy number. The side functions become piecewise linear functions. Fig. 1 represents the minimum (bold dashes) of two fuzzy numbers. Now that we have presented the extensions of the operators needed to use the Choquet integral as an aggregation operator for fuzzy numbers, we define the fuzzy extension of the Choquet integral as

C m (x) = T ⊆N m(T ) • i∈T x i ,
where m is the set function which is obtained by a Möbius transform of the fuzzy measure v.

The Choquet integral of a vector of fuzzy partial evaluations is a fuzzy number. In case of partial evaluations which are trapezoidal or triangular fuzzy numbers, the resulting fuzzy number has piecewise linear side functions. It is obvious that this extension remains valid in the case of a k-additive fuzzy measure. The definition can then be written

C m (x) = T ⊆N |T | k m(T ) • i∈T x i .
Let us consider a short example to show how the Choquet integral is calculated in case of triangular partial evaluations. This example is taken from [START_REF] Yang | Fuzzy numbers and fuzzification of the Choquet integral[END_REF] (Example 5.1).

Example 1. Let

N = {1, 2}, v({1}) = 0.1, v({2}) = 0.2, v({1, 2}) = 1.
In terms of the set function m (the Möbius transform of v) defined previously this problem can be rewritten as m({1}) = 0.1, m({2}) = 0.2, m({1, 2}) = 0.7. The partial evaluations are represented by the triangular fuzzy numbers x 1 = (1, 1, 0) and x 2 = (0.5, 0, 1). The Choquet integral then becomes:

C m (( x 1 , x 2 )) = m({1}) • x 1 + m({2}) • x 2 + m({1, 2}) • ( x 1 , x 2 ) = (0.2, 0.1, 0.2) + 0.7 • ( x 1 , x 2 ) := s + s ,
where s = (0.2, 0.1, 0.2) and s = 0.7 • ( x 1 , x 2 ). Fig. 2 shows a few steps of these calculations. (1) and (2) stand respectively for x 1 and x 2 . (3) and (4) represent s and s . Finally, [START_REF] Dubois | Fuzzy Sets and Systems: Theory and Application[END_REF] shows the aggregated value C m (( x 1 , x 2 )).

In [START_REF] Yang | Fuzzy numbers and fuzzification of the Choquet integral[END_REF] a fuzzy extension of the Choquet integral is presented, based on the classical representation of the Choquet integral by means of a fuzzy measure. A difficulty in that case is the ordering of the fuzzy numbers which is not needed in our approach and is problematic in the case of non linear fuzzy numbers. A numerical method is developed to estimate the value of the Choquet integral using trapezoidal fuzzy numbers. The authors of [START_REF] Ceberio | An interval-valued 2-additive Choquet integral for multicriteria decision making[END_REF] present an interval-based Choquet integral to derive preferences on multicriteria alternatives.

Ranking the alternatives and determining a best choice

Let us suppose that the partial evaluations of the elements of A have been aggregated into a fuzzy number for each alternative. We will see later in Section 7 how to determine the values of the coefficients of the fuzzy measure v (or equivalently of its Möbius transform m). The global evaluations obtained by the aggregation will allow us to determine a ranking or a best choice on the set A which can be proposed to the decision maker.

To build such a ranking, we suggest two possibilities: a complete preorder and a complete interval order. By means of a fuzzy preference digraph, we show how to obtain a solution for the best choice problem. These three proposals are described in the following three subsections.

To obtain the rankings we use the concept of possibilistic mean. Recall what has been said in Section 2 and consider the membership function of a fuzzy number x as a possibility distribution. We then define the upper possibilistic mean of x by

M + ( x) := 1 0 a M ( ) d = 1 0 a M ( ) dPos( x a M ( ))
and the lower possibilistic mean of x by

M -( x) := 1 0 a m ( ) d = 1 0 a m ( ) dPos( x a m ( )).
The possibilistc mean of the fuzzy number x is then defined by

M( x) := 1 2 [M + ( x) + M -( x)].
Fig. 3 gives a representation of the upper possibilistic mean in terms of a real number and a surface.

If we consider two fuzzy numbers x and y we can define the upper dominance + of x over y by

x + y ⇐ ⇒ M + ( x) -M -( y) 0.
Similarly one can define the lower dominance -.

Ranking by a complete preorder

The definition of the possibilistic mean can be applied to the global evaluation of an alternative x of A by means of the fuzzy extension of the Choquet integral C m (x). Let x and y be two alternatives of A. A complete preorder is then defined by the relation (is not worse than)

x y ⇐ ⇒ M( C m (x)) M( C m (y)).
(2)

+ M (x)
A 3 = M + ( x) -M + ( y) (upper dominance) and A 1 -A 2 = M -( x) -M -( y) (lower dominance).
Definition 2 can then be rewritten as

x y ⇐ ⇒ A 4 + A 1 A 3 + A 2 .
This complete preorder proposal corresponds to the area compensation method of Fortemps and Roubens [START_REF] Fortemps | Ranking and defuzzification methods based on area compensation[END_REF].

Ranking by a complete interval order

This approach is based on the comparison of the intervals

[M -( C m (x)), M + ( C m (x))],
for each x in A. Let I be a symmetrical relation, and P be an antisymmetrical relation on

A × A such that ⎧ ⎨ ⎩ xP y ⇐ ⇒ M -( C m (x)) > M + ( C m (y)), yP x ⇐ ⇒ M -( C m (y)) > M + ( C m (x)), xIy else.
The relation (P , I ) is an interval order. It is now possible to build a ranking on the alternatives of A. The particularity of such an interval order is that the associated indifference relation I is not transitive. For three alternatives x, y and z of A it is possible to have the situation where xIy and yI z, but xP z.

Choosing in a fuzzy preference digraph

This proposal extracts a subset of alternatives which can be considered as the "best" ones. This subset is called a best choice recommendation and each alternative which does not belong to the choice should be rejected. It is based on a degree of credibility of the preference of one alternative on another one. One can define this credibility as the possibility that an alternative x is not worse than y (let's write x y) in the following way:

(x y) = sup a b [min ( x(a), y(b))].
(3) Fig. 5 illustrates the meaning of this degree of credibility of the preference of x over y (x, y ∈ A). h represents the height at the intersection of the two fuzzy numbers x and y representing x and y. We have (x y) = h and (y x) = 1. Roubens and Vincke [START_REF] Roubens | Fuzzy possibility graphs and their application to ranking fuzzy numbers[END_REF] have shown that the credibility as defined in (3) is a fuzzy interval order (a reflexive, complete 5 and Ferrers6 valued relation) and that it is min-max-transitive. If these credibilities are computed for each pair of alternatives of A, it is possible to represent the problem as a valued digraph where the nodes represent the alternatives and the arcs the valued relation . This graph is called a fuzzy possibility digraph. Starting from this strongly complete relation , one can define a preference relation by

P (x, y) = 1 -(y x) ∀(x, y) ∈ A 2 [6].
The associated digraph is called a fuzzy preference digraph. The goal is now to extract some useful information from this digraph, in order to determine a best choice among the alternatives of A. Let us first recall the concept of the score of non-domination of an alternative

x of A [15] N D(x) = 1 -max y =x P (y, x).
The core Y 0 of A is a subset Y 0 ⊂ A such that its elements all have a score of non-domination of 1. In other words,

Y 0 = {x ∈ A | N D(x) = 1}.
It has been shown in [START_REF] Roubens | Fuzzy possibility graphs and their application to ranking fuzzy numbers[END_REF] that the core of a fuzzy preference digraph is non-empty. Y 0 gives a solution to the best choice problem (the subset of best actions among A).

On the calculation of the possibilistic means in practise

In real-life multiple criteria decision support problems, one can suppose that the partial evaluations of the alternatives are given by trapezoidal or triangular fuzzy numbers. Besides the objective can be to build the simplest possible model, which means in our framework to use a k-additive Choquet integral with k as low as possible.

Let us, therefore, suppose that the partial evaluations of an alternative x are trapezoidal fuzzy numbers x i = (a i , b i , i , i ) (i ∈ N) and that we restrict to a 2-additive Choquet integral. The aggregation can then be written

C m (x) = n i=1 m({i}) • x i + n {i,j }⊆N m({i, j }) • min ( x i , x j ).
The minimum of two trapezoidal fuzzy numbers can be summarised by eight parameters (a, b, -, , , + , , ) representing two upper piecewise linear shape functions passing through the following points: (a -, 0), (a -, -), (a, 1), (b, 1), (b+ , + ), (b+ , 0). Fig. 6 represents these eight parameters. Let m be the minimum of two trapezoidal fuzzy numbers. One can easily obtain that

M -( m) = a - + - 2 and M + ( m) = b + + + 2 .
Furthermore, one can see that for any fuzzy numbers x and y and any real number p, M ± (p • x) = pM ± ( x) and M ± ( x + y) = M ± ( x) + M ± ( y) 7 . For any alternative x ∈ A we therefore have

M ± [ C m (x)] = n i=1 m({i})M ± ( x i ) + n i,j =1 i =j m({i, j })M ± (min ( x i , x j )).
This shows that in this particular case where the partial evaluations are trapezoidal fuzzy numbers and where we restrict to a 2-additive fuzzy number, the possibilistic mean of the global evaluations of the alternatives can be very easily calculated.

The following section shows how to determine the coefficients of the set function m used in the definition of the fuzzy extension of the Choquet integral.

Assessment of the coefficients of m

The method described in Section 6 presents how to build two possible rankings and a best choice recommendation on alternatives which have fuzzy partial evaluations on a set of criteria. These evaluations are aggregated by means of a fuzzy extension of the Choquet integral presented in Section 5. One important point concerns the assessment of the coefficients of the set function m which is the Möbius transform of the fuzzy measure v (see Section 4).

Even if one restricts the model to a 2-additive Choquet integral, the number of coefficients which have to be determined for the aggregation is 2 i=1 ( n i ) = n(n + 1)/2. It seems obvious that neither the coefficients of the fuzzy measure v, nor those of its Möbius transform m have a clear meaning to the decision maker. Therefore the large number of coefficients linked to an unclear semantics of v or m lead us to think that an alternative possibility has to be explored.

In [START_REF] Meyer | Choice, ranking and sorting in fuzzy multiple criteria decision aid[END_REF] we have explored the sorting of alternatives by means of a Choquet integral in a universe of crisp partial evaluations. The idea is to ask the decision maker to provide information on a set of prototypes. A prototype is an alternative which is well known to the decision maker and which belongs to his domain of expertise.

A decisive hypothesis has to be done here. As a prototype is a well-known alternative for the decision maker, we suppose that it is also well-defined, and has therefore crisp partial evaluations. We are aware that this assumption is very strong and may be a weakness of our proposal. We nevertheless think that it is reasonable to suppose that the decision maker, as an expert of a particular knowledge field, can provide a few of these well-defined alternatives.

Let us suppose that the decision maker has provided a set P of such prototypes. We then ask him to determine a total order on the elements of P . Once again, as he is an expert of the knowledge field we are working on, he should be able to provide such an order. The next step is to determine the coefficients of the set function m used in the definition of the Choquet integral. As we have no guarantee that the total order provided by the decision maker is compatible with a discrimant function of the Choquet integral type, 8 the objective is to determine a set function m which will provide a satisfactory ranking on the prototypes. Therefore, the following procedure tends to minimise the gap between the ranking given by the decision maker and the one resulting from the aggregation. Intuitively, for a given alternative x ∈ P , its Choquet integral C m (x) should be as close as possible to an unknown global evaluation y(x), which respects the total order imposed by the decision maker on the prototypes.

The coefficients of the set function m are determined by solving the following quadratic program:

min x∈P [C m (x) -y(x)] 2 ,
where the unknowns are:

• the coefficients of the set function m;

• some global evaluations y(x) for each x ∈ P .

In order to ensure boundary and monotonicity conditions imposed on the fuzzy measure v, its Möbius transform m must satisfy [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF]:

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ m(∅) = 0, T ⊆N m(T ) = 1, T :i∈T ⊆S m(T ) 0, ∀S ⊆ N, ∀i ∈ S.
The global evaluations y(x) must verify the ranking imposed by the decision maker. In other words, for every ordered pair (x, x ) ∈ P × P , the condition y(x)y(x ) ε, ε > 0 must be satisfied 9 .

The solution of the quadratic program gives the coefficients of the set function m and the global evaluations y(x), ∀x ∈ A. If the objective function equals 0, then for each alternative, its global evaluation corresponds to its aggregated evaluation by a Choquet integral. In that case, the ranking obtained by ordering the alternatives according to their aggregated evaluations is consistant with the ranking on the prototypes. If the objective function is strictly positive, then it was not possible to determine the coefficients of the set function m in order to respect the ranking on the prototypes. In the ranking obtained by ordering the alternatives according to their aggregated evaluations, certain pairs of alternatives may be reversed compared to the ranking imposed on the prototypes.

It is possible to measure the adequacy of both rankings. The symmetric difference distance defined as where R and S are two binary relations on A, measures the number of disagreements between R and S. Barthélemy [START_REF] Barthélemy | Caractérisations axiomatiques de la distance de la différence symétrique entre des relations binaires[END_REF] shows that satisfies a number of naturally desirable properties. In our case, we can measure the symmetric difference distance between the ranking imposed on the prototypes, and the one obtained by the use of a Choquet integral. By using it is now quite easy to measure the adequacy of both rankings.

If the decision maker is satisfied with the model built on the prototypes (let us suppose that the distance is small), the next step is to determine the global evaluations of the alternatives of A which have fuzzy partial evaluations. The coefficients of the set function m, determined by the procedure we just described, are used to aggregate the fuzzy partial evaluations by means of the extension of the Choquet integral presented in Section 5.

Concluding remarks

In this paper, we have presented an extension of the Choquet integral to fuzzy partial evaluations in the case of multiple criteria decision support. This extension is very simple as we use the representation of the Choquet integral by means of the Möbius transform. We have presented two rankings and a best choice recommendation on the alternatives and we have shown how it is possible to determine the coefficients of the Choquet integral.

1 ]

 1 are upper semi-continuous and non-increasing shape functions with L(0) = R(0) = 1 and L(1) = R(1) = 0 which are called side functions. The support x is equal to ]a -, b + [. The crisp numbers are particular cases of the fuzzy numbers. If x ∈ F with x = {a} then x is a crisp number.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Minimum of two fuzzy numbers (bold dashes).

1 Fig. 3 .

 13 Fig. 3. Representations of M + ( x): a number and a surface.

4 .

 4 Comparing x to y. It is possible to give a geometric interpretation to this relation. Let us consider a situation with two fuzzy numbers x and y which represent the global evaluation of two alternatives x and y of A. These two fuzzy numbers define four areas A 1 , . . . , A 4 as shown on Fig. 4. We see that A 4 -

5 .

 5 Degree of credibility of the preference of x over y.

Fig. 6 .

 6 Fig. 6. The minimum of two trapezoidal fuzzy numbers.

(

  R, S) = |{(a, b) ∈ A 2 : [xRy and ¬(xSy)] or [¬(xRy) and (xSy)]}|,

The satisfaction of one point of view has almost the same effect as the satisfaction of both.

The satisfaction of only one point of view is weak compared to the satisfaction of both points of view.

Consider x, y ∈ A for which the evaluations on S ⊆ N are equal. The subset N \ S is preferentially independent of S if the preference of x over y is not influenced by their common part on S.

x y or y x for each x = y.

w x, y z ⇒ w z or z x.

The partial order may violate the triple cancellation axiom[START_REF] Marichal | An axiomatic approach of the discrete Choquet integral as a tool to aggregate interacting criteria[END_REF][START_REF] Wakker | Additive Representations of Preferences: A New Foundation of Decision Analysis[END_REF] for example.

In practise, one of the main problems is to fix the value of ε. We think that it has to be chosen in ]0, 1/p[ where p is the number of prototypes considered by the decision maker.


Jean-Luc Marichal
email: marichal@cu.lu

Patrick Meyer

Marc Roubens

Sorting multi-attribute alternatives: The TOMASO method

Keywords: Multi-attribute decision-making, Ordinal data, Interacting points of v iew, Choquet integral, Freeware TOMASO

We analyze a recently proposed ordinal sorting procedure (TOMASO) for the assignment of alternativ es to graded classes and we present a freeware constructed from this procedure. We illustrate it by two examples, and do some testing in order to show its usefulness.

Introduction

In this paper we analyze an ordinal sorting procedure for the assignment of alternatives to graded classes in the presence of interacting points of view. This procedure has been recently proposed by Roubens [START_REF] Marichal | On a sorting procedure in the presence of qualitative interacting points of view[END_REF][START_REF] Roubens | Ordinal multiattribute sorting and ordering in the presence of interacting points of view[END_REF] and is now known under the name TOMASO, which means "Tool for Ordinal Multi-Attribute Sorting and Ordering".

The technique used in this method proceeds in two steps: a pre-scoring phase determines for each point of view and for each alternative a net score (the number of times a given alternative beats all the other alternatives minus the number of times this alternative is beaten by the others) and is followed by an aggregation phase, using the discrete Choquet integral, which produces a global net score associated to each alternative. These global scores are then used to assign the alternatives to graded classes.

The fuzzy measure associated to the Choquet integral can be learnt from a subset of alternatives (called prototypes) that are assigned beforehand to the classes by the decision maker. This leads to solving a linear constraint satisfaction problem whose unknown variables are the coe cients of the fuzzy measure.

Once a fuzzy measure is found, it is useful to interpret it through some behavioral parameters:

(1) The importance indices (Shapley importance indices), which make it possible to appraise the overall importance of each point of view. [START_REF] Roubens | Ordinal multiattribute sorting and ordering in the presence of interacting points of view[END_REF] The interaction indices (Shapley interaction indices), which measure the extent to which the points of view interact (positively or negatively).

The main purpose of this paper is to present a freeware, also called TOMASO, which allows the user to apply this method to a learning set and analyze the resulting assignments. It is written in Visual Basic, which increases its ergonomy.

The paper is organized as follows. In Section 2 we recall the general sorting procedure TOMASO. In Sections 3-5 we present the freeware TOMASO, its implementation, and its application on two particular case studies. Finally, in Section 6, we compare this procedure with classical methods in terms of both results and computational e ciency.

The TOMASO method

In the present section, we brie y recall the procedure TOMASO. For theoretical developments on this procedure, the readers are referred to [START_REF] Marichal | On a sorting procedure in the presence of qualitative interacting points of view[END_REF].

Let A be a set of q potential alternatives, which are to be assigned to disjoint classes, and let N ={1; : : : ; n} be a label set of points of view to satisfy. For each point of view i ∈ N , the alternatives are evaluated according to a s i -point ordinal performance scale; that is, a totally ordered set

X i := {g i 1 ≺ i g i 2 ≺ i • • • ≺ i g i si }:
We assume that each alternative x ∈ A can be identiÿed with its corresponding proÿle (x 1 ; : : : ;

x n ) ∈ n × i=1 X i =: X;
where, for any i ∈ N , x i represents the partial evaluation of x related to point of view i. Now, consider a partition of X into m nonempty classes {Cl t } m t=1 , which are increasingly ordered; that is, for any r; s ∈ {1; : : : ; m}, with r ¿ s, the elements of Cl r have a better evaluation than the elements of Cl s .

We also set Cl ¿ r := t¿r Cl t (r = 1; : : : ; m):

The procedure TOMASO consists in partitioning the elements of A into the classes {Cl t } m t=1 . It is mainly based on the following result, adapted from [3, Theorem 2.1], which states that, under a simple condition of monotonicity, it is possible to ÿnd a discriminant function that strictly separates the classes Cl 1 ; : : : ; Cl m by ordered numerical thresholds.

For any x i ∈ X i and any y -i ∈ X -i := × j∈N \{i} X j , we set x i y -i := (y 1 ; : : : ; y i-1 ; x i ; y i+1 ; : : : ; y n ) ∈ X: Theorem 1. The following two assertions are equivalent:

(1) For all i ∈ N , t ∈ {1; : : : ; m}, x i ; x i ∈ X i , y -i ∈ X -i , we have

x i i x i and x i y -i ∈ Cl t ⇒ x i y -i ∈ Cl ¿ t : (2) There exist • functions g i : X i → R (i ∈ N ), strictly increasing, called criteria, • a function f : R n → R, increasing in each argument, called discriminant function, • m -1 ordered thresholds {z t } m t=2 satisfying z 2 6 z 3 6 • • • 6 z m
such that, for any x ∈ X and any t ∈ {2; : : : ; m}, we have

f[g 1 (x 1 ); g 2 (x 2 ); : : : ; g n (x n )] ¿ z t ⇔ x ∈ Cl ¿ t :
For a practical use of this result and in order to produce a meaningful result, Roubens [START_REF] Roubens | Ordinal multiattribute sorting and ordering in the presence of interacting points of view[END_REF] restricted the family of possible discriminant functions to the class of n-variable Choquet integrals and the criteria functions to normalized scores.

Such scores, whose deÿnition might vary from an application to another, should have a precise meaning for the decision maker.

Two natural approaches can be considered: either the score of each alternative is built on the basis of all the alternatives in A or this score is constructed in a context-free manner, that is, independently of the other alternatives. The decision maker must be aware that the ÿnal results may signiÿcantly di er according to the considered approach. Therefore, a prior analysis of the problem is recommended to choose the scores appropriately.

In the ÿrst approach, one possible way to build the scores is to consider comparisons of the alternatives on each of the points of view. We consider S i (x), the ith partial net score of alternative x ∈ A along point of view i ∈ N , as the number of times that x is preferred to any other alternative of A minus the number of times that any other alternative of A is preferred to x for point of view i. We furthermore normalize these scores so that they range in the unit interval, i.e.,

S N i (x) := S i (x) + (q -1) 2(q -1) ∈ [0; 1] (i ∈ N );
where q = |A|. Clearly, this normalized score is not a utility, and should not be considered as such. Indeed, observing an extreme value (close to 0 or 1) means that x is rather "atypical" compared to the other alternatives along point of view i. Thus, the resulting evaluations strongly depend on the alternatives which have been chosen to build A.

Consider now the second approach, that is, where the score of each alternative does not depend on the other alternatives in A. In this case, we suggest the decision maker provides the score functions as utility functions. Alternatively, we can approximate these utility functions by the following linear formula:

S N i (x) := ord i (x) -1 s i -1 ∈ [0; 1] (i ∈ N );
where ord i : A → {1; : : : ; s i } is a mapping deÿned by ord i (x) = r if and only if x i = g i r . In this latter case, S N i does not necessarily represent a real utility and probably does not correspond to the utility the decision maker has in mind. We therefore continue to call it a score.

Notice that the case studies we present in this paper are treated by means of the scores of the ÿrst type, i.e., based on the comparison of alternatives.

The normalized scores of each alternative x are then aggregated by means of a Choquet integral [START_REF] Choquet | Theory of capacities[END_REF], namely

C v (S N (x)) := n i=1 S N (i) (x) [v(A (i) ) -v(A (i+1) )];
where S N (x) stands for (S N 1 (x); : : : ; S N n (x)) and v represents a fuzzy measure on N ; that is, a monotone set function v : 2 N → [0; 1] fulÿlling v(∅) = 0 and v(N ) = 1. This fuzzy measure merely expresses the importance of each subset of points of view. Also, the parentheses used for indices represent a permutation on N such that

S N (1) (x) 6 • • • 6 S N (n) (x)
and, for any i ∈ N , A (i) represents the subset {(i); : : : ; (n)}. The Choquet integral presents standard properties for aggregation (see [START_REF] Grabisch | k-order additive discrete fuzzy measures and their representation[END_REF][START_REF] Marichal | An axiomatic approach of the discrete Choquet integral as a tool to aggregate interacting criteria[END_REF]): it is continuous, non-decreasing, located between min and max. The major advantage linked to the use of this integral derives from the large number of parameters (2 n -2) associated with a fuzzy measure. However, this exibility can be also considered as a serious drawback when assessing the fuzzy measure. To reduce the number of parameters, it is proposed to consider k-additive fuzzy measures [START_REF] Grabisch | k-order additive discrete fuzzy measures and their representation[END_REF]: a fuzzy measure v on N is k-additive if its M obius transform m : 2 N → R, deÿned by

m(S) = T ⊆S (-1) |S|-|T | v(T ) (S ⊆ N );
satisÿes m(S) = 0 for S such that |S| ¿ k and there exists at least one subset S such that |S| = k and m(S) = 0. It can be shown that k-additive fuzzy measures on N can be represented by at most k i=1 n i parameters. We now explain how the fuzzy measure is assessed in this procedure. Assume that all the alternatives of A ⊆ X are already sorted into classes Cl 1 ; : : : ; Cl m . In some particular cases there exist a fuzzy measure v on N and m -1 ordered thresholds {z t } m t=2 satisfying

z 2 6 z 3 6 • • • 6 z m
such that for any x ∈ A, and any t ∈ {2; : : : ; m}, we have

C v (S N (x)) ¿ z t ⇔ x ∈ Cl ¿ t :
Of course, if such a fuzzy measure does exist then the thresholds may be deÿned by

z t := min x∈Cl ¿ t C v (S N (x)
) (t = 2; : : : ; m):

In real situations, the assignment of all alternatives is not known but has to be determined. However, this assignment, or equivalently the fuzzy measure v, can be learnt from a reference subset, made up of prototypes that have been sorted beforehand by the decision maker. Practically, the decision maker is asked to supply such a prototypical subset P ⊆ A and the assignment of each of its elements to a given class; that is, a partition of P into prototypical classes {P t } m t=1 , where P t := P ∩ Cl t for all t ∈ {1; : : : ; m}. Here some prototypical classes may be empty. As the Choquet integral is supposed to strictly separate the classes Cl t , we must impose the following necessary condition:

C v (S N (x)) -C v (S N (x )) ¿ (1)
for each ordered pair (x; x ) ∈ P t × P t-1 and each t ∈ {2; : : : ; m}, where is a given strictly positive threshold. These separation conditions, put together with the boundary and monotonicity constraints on the fuzzy measure, form a linear constraint satisfaction problem whose unknowns are the coe cients of the fuzzy measure. Thus the sorting problem consists in ÿnding a feasible solution satisfying all these constraints. If has been chosen too big, the problem might have no solution. To avoid this, we can consider as a non-negative variable to be maximized. In this case its optimal value must be strictly positive for the problem to have a solution.

In the resolution of this problem, we use the principle of parsimony. If no solution is found for k =1, we turn to k =2. If no solution is still found, we turn to k =3, and so forth, up to k =n. Notice however that an empty solution set for k = n is necessarily due to an incompatibility between the assignment of the given prototypes and the assumption that the discriminant function is a Choquet integral.

Due to the increasing monotonicity of the Choquet integral, the number of separation constraints (1) can be reduced signiÿcantly. For example, if

x ∈ P t-1 is such that C v (S N (x )) ¿ C v (S N (x ))
then, by transitivity, the constraint

C v (S N (x)) -C v (S N (x )) ¿ is redundant.
Now, we can deÿne a dominance relation D on X as follows: For each x; y ∈ X ,

xDy ⇔ S N i (x) ¿ S N i (y) ∀i ∈ N:
Being an intersection of complete (total) orders, the binary relation D is a partial order, i.e., it is re exive, antisymmetric, and transitive. Furthermore we clearly have

xDy ⇒ C v (S N (x)) ¿ C v (S N (y)):
It is then useful to deÿne, for each t ∈ {1; : : : ; m}, the set of non-dominating alternatives of P t , Nd t := {x ∈ P t | @x ∈ P t \ {x} : xDx } and the set of non-dominated alternatives of P t , ND t := {x ∈ P t | @x ∈ P t \ {x} : x Dx} and to consider only constraint [START_REF] Marichal | On a sorting procedure in the presence of qualitative interacting points of view[END_REF] for each ordered pair (x; x ) ∈ Nd t ×ND t-1 and each t ∈ {2; : : : ; m}. Thus, the total number of separation constraints boils down to

m t=2 |Nd t | |ND t-1 |:
Finally, suppose that there exists a k-additive fuzzy measure v * that solves the problem above. Then any alternative x ∈ A will be assigned to

• the class Cl t if min y∈Ndt C v * (S N (y)) 6 C v * (S N (x)) 6 max y∈NDt C v * (S N (y)); • one of the classes Cl t or Cl t-1 if max y∈NDt-1 C v * (S N (y)) ¡ C v * (S N (x)) ¡ min y∈Ndt C v * (S N (y)):

The freeware TOMASO

We now present the freeware TOMASO, 2 which is an implementation (written in Visual Basic) of the algorithm presented in Section 2. In the present section we describe brie y the various aspects of the freeware. In the next section, we present an application on a ÿctitious example of evaluation of students, we show how the freeware deals with a leave-one-out procedure, and we present a way to test its performance on this particular example. In the following section, we present an application of the method to a classiÿcation problem of quality indices for association rules.

The freeware TOMASO can be used for supervised classiÿcation of ordinal multi-criteria data. In order to work properly, it requires some information about the structure of the data. We call a prototypical set the set of objects used to build the classiÿer. It is described by a set of alternatives which are already classiÿed by the decision maker.

This means that the class of problems which can be solved by this method is quite particular. The decision maker must be aware of some a priori information on certain objects of his decision problem. He must be an expert in the ÿeld and should be able to give a global evaluation on some particular elements. Later, when the model is built, new alternatives can be considered. The classiÿer will then assign them to one or more of the predeÿned classes, according to the preferences of the decision maker.

When using the freeware, at ÿrst the user has to load the ÿle with the data he wants to analyze. 3These data have to be of ordinal nature and, as mentioned before, can be composed of the prototypes and some alternatives that need to be classiÿed.

After the calculation of the net scores, the user has to ÿx the number of classes and their structures. This last point is achieved by adding the prototypes to their respective classes, which can be done either manually or by loading a ÿle. At the end of this step, the alternatives which are not assigned to any class do not belong to the prototypical set and will either be used as a test subset (to check the validity of the method) or simply as objects to be classiÿed.

The next stage of the freeware is to check the consistency of the assignments within the set of prototypes. The inconsistencies can be of two types:

• Two alternatives x and y with the same net scores for each criterion (S N (x) = S N (y)) belong to two di erent classes. • Two alternatives x and y so that x dominates y (i.e., S N i (x) ¿ S N i (y) ∀i ∈ N ) and y belongs to a better class than x.

If no inconsistency is detected, the freeware allows the user to go on. Else, the user has to change the deÿnition of the classes by the prototypes (either manually, or by loading another class ÿle). The next step is the determination of the non-dominating set of alternatives and the non-dominated set of alternatives in each class. These sets are not empty, because the user should add at least one alternative in each class. As already mentioned earlier, this is meant to reduce the number of separation constraints and is justiÿed by the increasing monotonicity of the Choquet integral.

The resolution of the linear constraint satisfaction problem is the next stage. The user can choose between ÿxing the value of k ¡ n or solving the problem for k =n. In both cases, a ÿle of constraints is computed. An external solver 4 uses this ÿle as an input and tries to solve the problem.

If the problem has no solution for k = n, the user should revise the deÿnition of the classes. On the other hand, if there is a solution for the problem, the following results are displayed:

• the coe cient of the fuzzy measure v, • the values of the M obius transform m of v, • the value of , • the borders of the classes (for each class Cl t , given by the maximal and the minimal value of the Choquet integral of the alternatives of Cl t ), • the Shapley importance indices for each point of view i, • the Shapley interaction indices for each pair of points of view, • the Choquet integral of each prototype.

An important tool is the assignment of the alternatives which are not in the prototypical set to the classes, according to the previously built model. During this step, it may happen that the Choquet integral of some of these objects may not be between the limits of any of the classes. In that case, those alternatives are assigned to "imprecise" classes which lie between the original classes. If for one particular alternative x the decision maker is not satisÿed with such a fuzzy assignment between classes Cl r and Cl s , he may revise the deÿnition of the adjacent classes in order to include x or maybe another alternative similar to x. Else, one can say that alternative x simply belongs to class Cl r or Cl s .

To check the structure of the set of prototypes, it is possible to apply a particular leave-one-out procedure to the data. For each alternative x of the prototypical set, the model is rebuilt without the alternative. Then x is assigned to a class, according to the prototypes. This class should then be the original class of x. If not, it is considered as an error. At the end of the whole procedure, a high error ratio, say e=p, with e close to p (p is the cardinality of the prototypical set and e is the number of badly classiÿed alternatives during the leave-one-out procedure) does not necessarily mean that the data of the prototypes are badly chosen. It either stands for a "minimal" prototypical set, where nearly each alternative is important for the building of the model, or for a quite complex data structure. In this latter case, the set of prototypes should perhaps be revised and enriched with new alternatives to increase its diversity.

Assigning students to graded classes

In order to validate the TOMASO method, we apply it on the following example. Consider a set of students evaluated in three courses: mathematics, physics, and literature. For each course, the evaluation scale has three ordered qualitative levels: bad ≺ medium ≺ good. In total this makes 27 possible di erent students. Besides, for each student, a decision maker has given a global evaluation on an qualitative ordinal scale with three levels: bad (1) ≺ medium (2) ≺ good [START_REF] Greco | Conjoint measurement and rough set approach for multicriteria sorting problems in presence of ordinal criteria[END_REF]. We analyze two di erent subproblems of this example. The ÿrst one uses the complete set of 27 students as prototypes and any future assignment has to be correct, because the 27 students represent all possible cases. The second study is on a random subset of the set of 27 students. It is somewhat more realistic, as a global information is known only on a subset of students. There, future assignments are not necessarily correct. In order to test the usefulness of the method, a particular algorithm of cross validation will be applied to the problem.

Subproblem 1: 27 students

Fig. 1 represents the assignments of the decision maker, and the dominance relations between students of the same class. The determination of the non-dominating and non-dominated sets of alternatives for each class results in the following table:

ND g (3 3 3) ND m (2 2 3) (3 3 1) ND b (1 3 3) (3 1 3) (2 2 1) Nd g (2 3 2) (3 2 2) Nd m (2 2 2) (2 3 1) (3 2 1) Nd b (1 1 1)
The extreme sets (ND g and Nd b ) will not be used in the linear constraint satisfaction program. The problem has a solution for k = n = 3, with = 0:086 (but no solution can be found for k ¡ 3). This means that all the prototypes can be assigned to their correct classes with the help of a

(2 3 2) (1 3 2) (2 3 3) (3 2 3) (1 3 3) (3 3 3) (3 3 2) (3 2 1) (3 3 1) (3 1 1) (2 1 1) (1 1 2) (1 1 1) (3 1 3) (3 2 2)
(2 3 1) For this problem, we chose a random subset of the 27 prototypical students as follows: we scan sequentially the original set of 27 students and assign each student with a probability of 1=2 to the new subset. The randomly generated subset used here is described in the following table:

(2 2 3) (3 1 2) (2 1 3) (2 2 2) (1 2 3) (1 2 2) (1 3 1) (1 1 3) (2 1 2) (2 2 1) (1 2
Good (3 2 2) (3 3 2) (3 2 3) (3 3 3) Medium (3 2 1) (3 3 1) Bad (3 1 1) (1 2 1) (1 3 1) (3 1 2) (1 3 2) (3 1 3) (1 2 3) (1 3 3)
The structure of this problem if given in Fig. 2. The original classes are represented by dashed lines. The prototypical classes are described by solid lines. The goal is to reconstruct the original classes as accurately as possible.

(2 3 2) We can also see that there is a solution for k = 2, with = 0:069. In this case, the importance indices are given in the following table :   Math Physics Literature 0:500 0:300 0:200

(1 3 2) (2 3 3) (3 2 3) (1 3 3) (3 3 3) (3 3 2) (3 2 1) (3 1 1) (2 1 1) (1 1 2) (1 1 1) (3 2 2) (2 3 1) (2 2 3) (3 1 2) (2 1 3) (2 2 2) (1 2 3) (1 2 2) (1 3 1) (1 1 3) (2 1 2) (1 2
The (pairwise) interaction indices are given in the following table :   (Math, Physics) (Math, Literature) (Physics, Literature) 0.200 0 0.400

Coming back to the solution with k =3, the leave-one-out procedures gives a misclassiÿcation ratio of 14:29%. This means that 2 alternatives out of the 14 of the prototypes were badly reclassiÿed. Besides, the importance indices stay rather constant during these 14 leave-one-out procedures. The three next tables resume the value of the Shapley indices for the three branches (mathematics (m), physics (p) and literature (l) The average values for mathematics and physics are both 0:39 with a variance of 7:43 × 10 -5 . For literature the mean is 0:220 with a variance of 2:89 × 10 -4 .

The assignments of the remaining 13 alternatives are resumed in the following table:

Student Assignment Original class (1 1 1) Bad Bad (2 1 1) Bad Bad (2 2 1) Medium Bad (2 3 1) Medium Medium (1 1 2) Bad Bad (2 1 2) Bad Bad (1 2 2) Bad Bad (2 2 2) Good Medium (2 3 2) Good Good (1 1 3) Bad Bad (2 1 3) Bad Bad (2 2 3) Good Medium (2 3 3) Good Good
The three erroneous assignments (indicated in boldface type) lead to an error rate of 23:08%. If we analyze these problems, they are not surprising at all. The randomly chosen subset has very few representatives in the middle class of medium students. The three erroneous assignments slide from the middle to the top class, or from the lower to the middle class. Hence we can conclude that the class of medium students is quite problematic in this particular case. But the error rate is still satisfactory.

In order to determine if the algorithm used in the TOMASO method is useful on this particular example of 27 students, we use a special 2-fold cross validation. The goal is to prove that the previous randomly chosen subproblem is not a particular case, and that pertinent conclusions can be drawn for any possible prototypical subset of the 27 students.

The general idea behind this test is to split the data D of the 27 students in 2 random subsets, a training set R and a test set T . The model is built on R and tested on T . The resulting classiÿcation (on T ) is then compared to the original classes of D. To determine the accuracy of the model, an error ratio is calculated by dividing the number of misclassiÿed elements of T by the cardinality of T .

In this particular example, we build a certain number S of subsets of the set of 27 students. One condition needs to be fulÿlled: there must be at least one object of each decision class in the subset. To do so, we scan sequentially the original set of 27 students and assign each student with a probability of 50% to the new subset. Afterwards, we check if each class is represented at least once in the new set of students.

Let X be a random variable which represents the error ratio. Our main concern is the mean value of X , E[X ], on all possible subsets of D under the constraint described before.

In order to give an estimation of E[X ] we calculate the mean X of X on 30 subsets. The values for the X i are given in the following Hence X = 0:2247 and the standard deviation s = 0:0231. Besides, the normality of the distribution given by the values in the previous table cannot be rejected. Hence we compute the Student conÿdence interval around the value of X . Finally:

P(E[X ] ∈ [0:2131; 0:2363]) = 99%:
More intuitively, we can claim that with a probability of 99%, TOMASO allows to classify the students of this example with an error rate between 21.31% and 23.63% if the prototypes are chosen randomly as described beforehand.

We observe that the previous example treated in Section 4.2 is not aberrant, and that it could represent a real case study. Furthermore the conclusions drawn from it are pertinent.

We also have analyzed the variation of the importance indices over these 30 cross validations. In a majority of cases, the order "mathematics ∼ physics literature" is maintained. But the values for each criterion are varying signiÿcantly. It is important to emphasize here that the exact values of these indices should merely be considered as parameters.

Assigning quality measures of association rules to graded classes

We present a second example to show that the TOMASO method can be used in various real-life problems where a MCDA problem requires graded classes as an output. This particular example comes from the data mining and knowledge extraction ÿelds. Certain data mining algorithms, especially those used for unsupervised learning, can generate a large number of rules (A → B; read: if A is satisÿed then B is probably also satisÿed). They need to be evaluated before being presented to an expert in order to reduce their number, and to retain only the "best" and the most interesting ones. Intuitively one could say that an association rule is "good" if it has few counterexamples. Therefore, many quality measures have been proposed to evaluate rules. Most of them have di erent properties and express more subtle properties than simply counting the counterexamples. These properties are often contradictory and con icting. In [START_REF] Ph | Aide multicrit ere  a la dà ecision pour à evaluer les indices de qualità e des connaissances[END_REF] the authors have described quality measures on a limited set of criteria. Currently, the work has progressed and a set of 20 measures is evaluated on 8 criteria. The interested reader should refer to [START_REF] Ph | Aide multicrit ere  a la dà ecision pour à evaluer les indices de qualità e des connaissances[END_REF] for further details. The list of criteria is given hereafter:

• g 1 : Asymmetric processing of A and B (To distinguish A → B rules from B → A rules) (asymmetric Hence the quality measure should take a ÿxed value at independence (e.g. 0)) (ÿxed value at independence (1) value at independence varying with rule (0)). • g 4 : Constant at situation of logical rule (If no counterexample to the rule exists, the measure should take a ÿxed maximum value (e.g. 1)) (constant at maximum (1) maximum value dependant on rule (0)).

• g 5 : Shape of the curve [measure = f(counterexamples)] (A slow decrease with the number of counterexamples allows to keep the rule longer, a fast decrease with the number of counterexamples bans the rule faster; depends on the preferences of the expert) (concave (2) linear (1) (0) convex or convex (0) linear ( 1) concave ( 2)). • g 7 : Ease to ÿx an acceptance threshold (If the value of the measure lies above this threshold, the rule is accepted, else it is rejected) ((1) easy hard (0)). • g 8 : Intelligibility of the measure (easily explainable (2) basic mathematical knowledge required (1) hardly explainable (0)).

The data matrix is shown in Table 1. The expert would like to assign these 20 measures to 3 graded classes: Good Medium Bad. During a discussion, he is asked to provide at least one measure for each class. He chooses a few measures he knows quite well, and for which he is able to interpret the resulting rules and their quality. The assignment of the prototypes is given in Table 2. One should mention here that this assignment is re ecting the preferences of the expert. He is not necessarily a data mining expert. Therefore, he is not aware of all the subtilities of the A solution is found for k=1. This additive model allows to classify the non-prototypical alternatives as shown in Table 3. The importance indices are shown in Table 4. These results are in close relation with the current research which is made on the evaluation of quality measures of decision rules. In [START_REF] Ph | Aide multicrit ere  a la dà ecision pour à evaluer les indices de qualità e des connaissances[END_REF] the authors analyze the same type of problem, with the Promethee-Gaia method for multiple criteria ranking. Our results are not in contradiction with those published in [START_REF] Ph | Aide multicrit ere  a la dà ecision pour à evaluer les indices de qualità e des connaissances[END_REF].

Beneÿts and speciÿcities of TOMASO and comparison to two classical MCDA methods

In the general context of multicriteria decision aiding and sorting methods, TOMASO has two major particular features.

First of all, it is able to cope with interacting criteria. This allows to deal with a larger set of problems, and the deÿnition of the criteria is less restrictive than for classical methods (like PROMETHEE [START_REF] Brans | PROMETHEE-GAIA -Une mà ethode d'aide  a la dà ecision en prà esence de crit eres multiples[END_REF], or ELECTRE TRI [START_REF] Mousseau | ELECTRE TRI 2.0a, Methodological guide and user's documentation[END_REF]).

Secondly, the decision maker does not have to provide di cult information on parameters of the model (like weights for the criteria). They are "learnt" from a set of well-known alternatives by the decision maker. One could say that in certain problems this may be as complicated as determining the weights of the criteria. But our experience has shown that in our case studies, expert decision makers have an a priori knowledge about a few objects of the problem they are analyzing. This particular information is fully exploited in TOMASO through the concept of prototypes.

In the theoretical example of the assignment of students to graded classes, we observe ÿrst of all that the particular classiÿcation of the prototypes implies interaction among criteria (no model could be found for k = 1). In case of the two classical MCDA methods PROMETHEE and ELECTRE TRI, the criteria require to be independent. This restrictive condition implies that here a solution which is compatible with the decision maker's preferences cannot be found. The strong condition of independent criteria may be quite restrictive in many real-life cases.

Another point concerns the information that the decision maker has to provide. In PROMETHEE, a weight system has to be determined in order to obtain a ÿnal ranking on the alternatives. Some visualization tools allow an easier ÿxing of these parameters, but nevertheless, this information is quite complex and hard to obtain. In ELECTRE TRI, A procedure allows to provide some prototypical alternatives to the method, in order to ÿx certain parameters. But other parameters still need human interaction (thresholds). Anyway, nothing guarantees that a solution to the classiÿcation of the prototypical alternatives will be found if the criteria are not independent. In TOMASO the decision maker, such as a teacher in a student evaluation, has to express a global feeling on a subset of students. No further parameter has to be ÿxed. These assignments are "natural" opinions of the teacher on some students, without any precise considerations on the exact weights of the di erent matters. In this case, this simpliÿed information is enough to build a model, and to provide the "weights" of the criteria by means of the Shapley indices.

A further speciÿcity of the TOMASO method is the possibility to use and work with purely ordinal data. No further information is required. In PROMETHEE, the user has to decide what type of preference function he wants to use in order to make di erent ordinal and cardinal scales comparable. Besides, each preference function requires some parameters to be ÿxed by the user. The method ELECTRE TRI also needs some parameters to be ÿxed by the decision maker. In our case, the problem is solely analyzed (and solved) by asking the decision maker a minimal number of questions on global evaluations concerning the alternatives and no further information on the structure of the data.

Conclusion

We have introduced a freeware that uses the procedure TOMASO to build a supervised classiÿer. Some interesting observations can be made with the help of this tool. We want to emphasize that the interaction indices as well as the Shapley indices are mainly parameters of the method. In particular the importance indices should not be interpreted as "real" weights of the problem. Even if they are stable during the leave-one-out procedures, this does not indicate that they "ÿt" to the decision maker's mind. As we have shown in the last part of Section 4.2, they can vary quite signiÿcantly from one prototypical set to another. At most their order can give an indication on the ranking of the "real" weights.

Fig. 2 .

 2 Fig. 2. Assignments of the decision maker.

  We observe that these sets are quite reduced in comparison to the previous subproblem. The problem has a solution for k = n = 3, with = 0:115. The importance indices are given in the following tableto those of the ÿrst subproblem. Mathematics and Physics have the highest importance indices with equal values.

• g 2 :

 2 Decrease with n b (n b = |B|) with ÿxed |A| (decreasing with n b (1) non-decreasing with n b (0)). • g 3 : Constant at independence (If A and B are independent, the rule contains no information.

table :

 :

	0.2857	0	0.2308	0.2500	0.5455
	0.1538	0	0.1429	0.0667	0.1818
	0.3571	0.4286	0	0.4286	0.5333
	0.3889	0.3333	0	0.1538	0.0769
	0.2500	0.2941	0.2308	0.3077	0.0769
	0.1250	0.1333	0.2222	0.3125	0.2308

Table 1

 1

	Decision matrix for the quality measures problem
		g1	g2	g3	g4	g5	g6	g7	g8
	SUP	0	0	0	0	1	0	1	2
	CONF	1	0	0	1	1	0	1	2
			0	0	0	1	0	1	0
	Table 2
	Assignment of the prototypes
	GOOD	CENCONF		LOE		OM		EII
	Medium	ZHANG		ECR		PDI
	Bad	SUP			SURP		KAPPA
	• g 6 : Sensitivity to the total number of examples of the analyzed data table (sensible (1)	not
	sensible (0)).

Table 3

 3 Assignment of the remaining measures

	Good		CONF		CONV		INTIMP
	Medium		PS		-IMPIND		SEB
	Medium ∪ Bad		R		LIFT
	Bad		LAP		IG
	Table 4
	Importance indices
	g1	g2	g3	g4	g5	g6	g7	g8
	0.182	0.000	0.182	0.182	0.000	0.181	0.001	0.273
	measures, but during the discussion, he gets information on the 8 selected properties and on certain
	measures.

Available at http://patrickmeyer.tripod.com

See tutorial at http://patrickmeyer.tripod.com for a detailed description of the data ÿle formats.

lp solve 3.0, downloadable at ftp://ftp.ics.ele.tue.nl/pub/lp solve/, released under the LGPL license.

Supported by the project CELoFA 9813803 of the RÃ egion Wallonne (Belgium).