Liyao Ma

Thierry Denoeux
email: thierry.denoeux@utc.fr

Making Set-valued Predictions in Evidential Classification: A Comparison of Different Approaches

Keywords: Belief functions, Dempster-Shafer theory, Decision under uncertainty

In classification, it is often preferable to assign a pattern to a set of classes when the uncertainty is too high to make a precise decision. In this paper, we consider the problem of making set-valued predictions in classification tasks, when uncertainty is described by belief functions. Two approaches are contrasted. In the first one, an act is defined as the assignment to only one class, and we define a partial preorder among acts. The set of non-dominated acts is then given as the prediction. In the second approach, an act is defined as the assignment to a set of classes, and we construct a complete preorder among acts. The two approaches are discussed and compared experimentally. A critical issue both to make decisions and to evaluate decision rules is to define the utility of set-valued prediction. To this end, we propose to model the decision maker's attitude towards imprecision using an Ordered Weighted Average (OWA) operator, which allows us to extend the utility matrix. An experimental comparison of different decision rules is performed using UCI and artificial Gaussian data sets.

Introduction

In classification problems, given a model learned from the training set, decisions are made on predicting the labels of new instances [START_REF] Richard O Duda | Pattern classification[END_REF]. Unfortunately, it sometimes happens that our belief about the states of nature cannot be modeled by a probability measure as the information is insufficient to identify precise probabilities [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF]. In such a situation, the commonly-used Maximum Expected Utility principle (MEU) fails to give an adequate decision of label assignment. In this paper, decision strategies in the Dempster-Shafer (DS) framework [START_REF] Arthur | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Thierry Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF] are discussed.

As reviewed in paper [START_REF] Denoeux | Decision-making with belief functions: a review[END_REF], various classical Bayesian decision rules and imprecise probability decision rules have been extended to the DS framework. Yet in classification applications investigated so far, given uncertain information about the states of nature by belief functions, decisions have mainly been made by simple means such as using pignistic probability [START_REF] Liu | Combination of classifiers with optimal weight based on evidential reasoning[END_REF] put forward by Smets [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF], or selecting the class with highest mass value [START_REF] Lian | An evidential classifier based on feature selection and two-step classification strategy[END_REF]. Taking better advantage of uncertainty, Denoeux [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF] analysed three principled decision rules with rejection in the DS framework. A further step is made in this paper, in which different decision approaches allowing for set-valued predictions are discussed. A problem arising from such kind of predictions is how to evaluate their performances. Zaffalon et al. [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] analysed the {0, 1} reward case and proposed an evaluation metric that takes the decision maker's degree of risk aversion into account. Considering a more general case, Yang et al. [START_REF] Yang | The costs of indeterminacy: How to determine them?[END_REF] provided some properties that the utility of set-valued prediction should follow and proposed the p-discounted costs method. In this paper, inspired by the ordered weighted average (OWA) operator [START_REF] Ronald R Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF], we propose another approach to define the utilities for all set-valued predictions based on the utility of precise ones.

Let us denote by Ω = {ω 1 , • • • , ω n } the set of classes (states of nature). For classification problems, in general an act is defined as the assignment of an instance to one and only one of the n classes. The set of acts is

F = { f ω 1 , • • • , f ω n },
where f ω i (or f i for short) denotes the assignment to class ω i . To make decisions, we define a utility matrix U n×n , whose general term u i j ∈ [0, 1] denotes the utility of selecting class ω i when the true class is ω j . The more desirable is the prediction, the higher utility it achieves. Without loss of generality, we assume that u ii = 1 for all i (correct predictions all have unit maximum utility) throughout this paper. When uncertainty is described by a probability distribution on Ω, we can compute an expected utility for each act. A complete preference relation among all available alternatives f ∈ F can then be computed and the optimal act provides a precise prediction of the instance. However, in situations of uncertainty, it may be preferable to assign a pattern to a set of classes. Different decision strategies are available for that purpose when uncertainty is described using either imprecise probabilities, or Dempster-Shafer belief functions. In this paper, we focus on the latter model, but some ideas can be transposed to other models. Describing the decision maker's (DM) information con-cerning the states of nature by a belief function m on Ω, we analyse how to make set-valued classification predictions by different ways.

Two Families of Set-valued Decision Strategies

We have seen that a complete preorder among precise assignments can be used to make precise predictions. To compute set-valued predictions under uncertainty, we can basically start by modifying either the preference relations or the acts. Different decision criteria allowing us to derive either partial preorders among precise assignments, or complete preorders among partial assignments are discussed below.

Partial Preorders Among Precise Assignments

In this approach, we still define the acts as precise assignments (assigning the instance to one and only one of the n classes). Due to lack of information, each act f i induces lower and upper expected utilities defined, respectively, as

E m ( f i ) = ∑ B⊆Ω m(B) min ω j ∈B u i j and E m ( f i ) = ∑ B⊆Ω m(B) max ω j ∈B u i j .
It is well known that the interval

[E m ( f i ), E m ( f i )]
is also the range of expectations E P ( f i ) with respect to all probability measures P compatible with belief function m (called the credal set of m). In the imprecise probability framework, three main decision criteria have been proposed [START_REF] Matthias | Decision making under uncertainty using imprecise probabilities[END_REF]: interval dominance, maximality and weak dominance. These criteria are described in Table 1. By comparing the lower and upper expected utilities of acts, these criteria produce partial preorders, in which some acts are incomparable but more desirable than the others. Therefore, to choose the best act, we drop some sub-optimal alternatives and obtain an optimal set F * such that

∀ f i , f j ∈ F * , f i ∼ f j and ∀ f i ∈ F * , ∀ f j / ∈ F * , f i f j . For instance, if we have the partial relation f ω 1 f ω 3 and f ω 2 f ω 3 (|Ω| = 3), then the optimal set is F * = { f ω 1 , f ω 2 } and the set of predicted classes is {ω 1 , ω 2 }.
Note that we obtain partial preorders because some alternatives cannot be ordered without additional information: from an imprecise probability theory point of view, when the credal set is too large or, from the belief function point of view, when we have some masses on non-singleton focal elements. Given additional information about states of nature, we can further narrow the expected utility intervals and make them comparable. The more information we have, the smaller is the optimal set F * . When the belief functions become Bayesian, a complete preorder revealing a precise prediction is obtained.

Complete Preorders Among Partial Assignments

Let us now consider the other approach to make set-valued predictions by extending the set of acts. Here, we generalize the acts as partially assigning the instance to a non-empty subset A of Ω. The set of acts becomes

F = { f A , A ∈ 2 Ω \ { / 0}}
, where 2 Ω denotes the power set of Ω. Obviously, to make decisions, the original utility matrix U n×n needs to be extended to Û(2 n -1)×n , with each element ûA, j representing the utility of assigning an instance to the set A of classes when the true class is ω j . The details about utility matrix extension will be discussed in Section 3.

Since each act now corresponds to a set of classes, to make set-valued predictions, a complete preorder among partial assignments should be defined. Assuming mass function m on Ω and the extended utility matrix Û(2 n -1)×n to be given, Table 2 recalls extensions of classical decision criteria inducing complete preorders of partial assignments f A . Here only the basic information needed to achieve preorders is described due to length limitation; more complete descriptions of all decision criteria used can be found in [START_REF] Denoeux | Decision-making with belief functions: a review[END_REF]. Some additional remarks about Table 2 are the following: i) For the pignistic criterion [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF],

BetP({ω j }) = ∑ ω j ∈A m(A) |A|
is the pignistic probability where |A| denotes the cardinality of subset A ⊆ Ω; ii) In the generalized OWA criterion, F β is the maximum entropy OWA operator with orness β [START_REF] Yager | Decision making under Dempster-Shafer uncertainties[END_REF] (more details about the OWA operator are given in Section 3); iii) For the generalized minimax regret criterion, r A i , j = max k ûA k , j -ûA i , j is the regret that act f A i is selected when the true state ω j occurs [START_REF] Yager | Decision making using minimization of regret[END_REF].

Also, we can remark that MEU works as a special case where uncertainty about Ω is quantified by probabilities p 1 , • • • , p n . In addition, it can be proved that, for any act f A , the sum of E m ( f A ) and R( f A ) always equals 1 in our utility settings. The complete preorder achieved by descending order of E m ( f • ) is the same as that achieved by ascending order of R( f • ). Therefore, the maximin and miminax regret criteria always result in the same decision for our problem. 2, a complete preorder of partial assignments f A is obtained with respect to mass function m. Therefore, a single but perhaps partial assignment will be selected as the optimal one. Taking complete preference relation

With any decision criterion in Table

f {ω 1 ,ω 2 } f ω 1 f ω 2 (|Ω| = 2) as an example, we have F * = { f {ω 1 ,ω 2 } }, i.e.
, we know for sure that the best choice is to assign the instance to class 1 or class 2, which corresponds to a set-valued prediction {ω 1 , ω 2 }. We can remark that, in this approach, we can still make set-valued predictions even with very precise probabilities of states of nature, which is a major difference with the other approach discussed in Section 2.1.

f i ID f j ⇐⇒ E m ( f i ) ≥ E m ( f j ) maximality f i max f j ⇐⇒ E m ( f i -f j ) ≥ 0 weak dominance f i W D f j ⇐⇒ E m ( f i ) ≥ E m ( f j ) ∧ E m ( f i ) ≥ E m ( f j )
f A i * f A j ⇐⇒ E m ( f A i ) ≥ E m ( f A j ) E m ( f A i ) = ∑ B⊆Ω m(B) min ω j ∈B ûA i , j generalized maximax f A i * f A j ⇐⇒ E m ( f A i ) ≥ E m ( f A j ) E m ( f A i ) = ∑ B⊆Ω m(B) max ω j ∈B ûA i , j generalized Hurwicz f A i α f A j ⇐⇒ E m,α ( f A i ) ≥ E m,α ( f A j ) E m,α ( f A i ) = αE m ( f A i ) + (1 -α)E m ( f A i ) pignistic criterion f A i p f A j ⇐⇒ E p ( f A i ) ≥ E p ( f A j ) E p ( f A i ) = n ∑ j=1 ûA i , j BetP({ω j }) generalized OWA f A i β f A j ⇐⇒ E owa m,β ( f A i ) ≥ E owa m,β ( f A j ) E owa m,β ( f A i ) = ∑ B⊆Ω m(B)F β ({ ûA i , j | ω j ∈ B}) generalized minimax regret f A i r f A j ⇐⇒ R( f A i ) ≤ R( f A j ) R( f A i ) = ∑ B⊆Ω m(B) max w j ∈B r A i , j maximum expected utility f A i m f A j ⇐⇒ EU( f A i ) ≥ EU( f A j ) EU( f A i ) = n ∑ j=1 ûA i , j p j

Extending Utility Matrix via an OWA Operator

As discussed in Section 2.2, the extended utility matrix Û(2 n -1)×n plays an important role in decision-making. Given original utility matrix U n×n , we propose to generate Û(2 n -1)×n using an OWA operator.

An OWA operator of dimension n is a mapping F with associated collection of positive weights w w w = (w 1 , • • • , w n ) summing up to one, such that

F(a 1 , • • • , a n ) = n ∑ i=1 w i b i , (1)
where b i is the i-th largest element of a 1 , • • • , a n . By choosing different weights, it provides a parameterized class of mean type aggregation operators. Yager defined the measure of orness [START_REF] Ronald R Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF] as orness(w w w) = 1 n-1 ∑ n i=1 (ni)w i . Given orness β , the OWA operator F β that maximizes the entropy ENT (w w w) = -∑ n i=1 w i log w i under the constraint orness(w w w) = β will be chosen. Now we consider the classification problem. Given a state of nature ω j , the utility of assigning one instance to set A should intuitively be a function of those utilities of each precise assignments within A. From the most optimistic view, the maximum utility of elements in the set is selected: ûA, j = max ω i ∈A u i j . So as long as set A contains the true label, no matter how imprecise A is, the partial assignment achieves utility 1, representing a total tolerance of imprecision. From a more imprecision-neutral point of view, the utility of partial assignment f A can be defined as the average of the utilities of precise assignments within the set, just as picking one label uniformly at random from set A:

ûA, j = 1 |A| ∑ ω i ∈A u i j . (2)
We denote the average utility as u A, j := 1 |A| ∑ ω i ∈A u i j . It can be noted that if ûA, j is less than the average utility u A, j , it is always preferable to pick a class randomly in A, rather than selecting set A as our prediction. For practical purposes, the utilities of partial assignments can, thus, be defined using a family of parameterized utility functions ranging from the average to the maximum, i.e., 1

|A| ∑ ω i ∈A u i j ≤ ûA, j < max ω i ∈A u i j ,
which can be implemented using OWA operators with different weights w w w: given a set A ⊆ Ω and the state of nature ω j , the aggregated utility for assigning one instance to set A (denoted as ûA, j ) is calculated as a function F of utilities of each elements in this set as where the second equation is the calculation of an OWA operator. u A (k) j denotes the k-th largest element in the set {u i j , ω i ∈ A}, and weight w k ≥ 0 represents the DM's preference to choose u A (k) j when he is forced to make a precise decision among a set of possible choices. Similar to the orness measure, for the OWA operator with weight vector w w w, we define the DM's tolerance degree of imprecision as

ûA, j = F ({u i j | ω i ∈ A}) = |A| ∑ k=1 w k u A (k) j , (3)
T OL(w w w) = |A| ∑ k=1 |A| -k | A | -1 w k = γ, (4)
which is equal to 1 for the maximum and 0.5 for the average. Given γ, the weights corresponding to the OWA operator are obtained by maximizing the entropy

ENT (w w w) = - |A| ∑ k=1 w k log w k , (5)
subject to T OL(w w w) = γ and ∑ |A| k=1 w k = 1. Table 3 shows the extended utility matrix obtained by an OWA operator with γ = 0.8, where the first three rows constitute the original utility matrix. Considering the utility matrix shown in Table 3, let us assume that the true label is ω 1 . Figure 1 displays the aggregated utilities for sets {ω 1 , ω 2 }, {ω 1 , ω 3 } and {ω 1 , ω 2 , ω 3 } with different values of γ. The aggregated utility is only related to the utilities of elements within the set. As γ ranges from 0 to 1, the aggregated utility for each set varies from the minimal utility in this set to the maximal one. When γ = 0.5, the average utility is obtained by the OWA operator. As mentioned above, we only need to consider values of γ between 0.5 and 1, since when γ < 0.5 a precise prediction is always more desirable than an imprecise one.

Table 4 shows the utility matrix extended by the "pdiscounted cost" approach [START_REF] Yang | The costs of indeterminacy: How to determine them?[END_REF] with p = 4. Comparing it to the one extended by an OWA operator ( 0.1707 0.8412 0.8412 f {ω 1 ,ω 2 ,ω 3 } 0.7602 0.7604 0.7602 the true label and slightly higher utilities to imprecise and incorrect predictions. We can also briefly check the properties of utility generated by an OWA operator with respect to the guidelines proposed by Yang et al. [START_REF] Yang | The costs of indeterminacy: How to determine them?[END_REF]. As γ = 0.5 corresponds to the average utility u A, j , for any γ ∈ (0.5, 1), the necessary properties (Properties 1, 3, 4 and 10 in [START_REF] Yang | The costs of indeterminacy: How to determine them?[END_REF]) and desirable properties (Properties 2 and 5) are satisfied. Regarding context-dependent properties, for any set-valued prediction A, we have

ω j / ∈ A ⇒ u γ A, j ≥ u γ=0.5 A, j
= u A, j , satisfying Property 7. Since different utilities can be assigned in U according to the truth, our proposal satisfies Property 9.

Evaluation of Set-valued Predictions

In classification applications, a test set T is used to assess the performance of the learned model. When we make set-valued predictions according to strategies described in Section 2, a standard is needed to evaluate the decisions made by different criteria.

Zaffalon [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] proposed a utility-discounted predictive accuracy under the {0, 1} reward assumption to evaluate set-valued predictions made of credal classifiers. In this paper, we propose to use the extended utility matrix Û generated by an OWA operator for performance evaluation. The classification performance is evaluated by the averaged utility in the test set T :

Acc(T ) = 1 |T | |T | ∑ i=1 ûF * i ,i * , (6)
where ûF * i ,i * denotes the utility of selecting the optimal act f F * i (assigning instance i in T to set F * i ) when its true class is ω * i .

Experiments

In this section, we report on classification experiments aiming to compare experimentally the different decision strategies described above. Belief functions concerning the states of nature were generated through the DS theorybased neural network classifier [START_REF] Denoeux | A neural network classifier based on Dempster-Shafer theory[END_REF], which assigns for each instance a mass to each singleton class and the frame of discernment, i.e.,

m(ω i ) = m i , i = 1, . . . , n; m(Ω) = 1 - n ∑ i=1 m i .

Classification Performances with Varying γ

We first checked the averaged utilities obtained according to different decision criteria with varying γ. Experiments were carried out using the UCI Balance scale dataset [START_REF] Lichman | UCI machine learning repository[END_REF], which is a four-attribute and three-class dataset containing 625 instances. The original utility matrix was arbitrarily assumed to be

U =   1 0.2 0.1 0.2 1 0.2 0.1 0.2 1   ,
where correct predictions (diagonal elements) had utilities 1 and different prediction errors were assumed to be not treated equivalently. This is just an example to show the generality of the approach; in most cases, matrix U can be taken to be the identity matrix, in which only correct prediction can achieve utility 1 while all the other outcomes achieve 0. To evaluate the results, five-fold cross-validation was performed, and all experiments were repeated five times to compute an average result. Table 5 shows the averaged utilities (upper part) and corresponding percentage of precise prediction (lower part) in each case. Given a fixed γ, the averaged utilities of different criteria vary in a narrow range (the maximum averaged utilities are highlighted in bold). For criteria with complete preorders among partial assignments (DC1-DC6), as γ increases, imprecise predictions are more preferred so the percentage of precise predictions decreases; the averaged utilities decrease slightly and then increase to 1. To better explain this behaviour, Table 6 reports the predictions and corresponding utilities of three instances, where ω * is the true label, and Ω = {ω 1 , ω 2 , ω 3 }. For misclassified instance (#2), its utility can increase from 0.2 to 1 as γ becomes larger. Yet for those correctly predicted when γ = 0.5 (#1 and #3), their utilities will drop and then increase back to 1. The majority of instances are of the latter case, so overall, the averaged utilities decrease at first as set-valued predictions containing the true label have lower utility than the precise ones. As γ approaches 1, the utilities of imprecise predictions grow closer to 1, making the averaged utility increase to 1.

For decision criteria yielding partial preorders among precise assignments (DC7-DC9), the extended utility matrix is only used for evaluation, so the predictions remain unchanged as γ increases. The weak dominance criterion (DC9) nearly always gives precise predictions (whose utilities are not affected by γ) for this dataset; consequently, averaged utilities do not change with γ. The averaged utilities of the other two criteria (DC7 and DC8) increase monotonically when γ increases from 0.5 to 1. The extended utility matrix gives the same set-valued prediction a higher utility as γ grows. So even though the predictions themselves are not affected by γ, they do achieve higher averaged utilities with larger γ.

Performances with Noised Test Sets

In many situations, a classifier is trained with "good" data (acquired and preprocessed in controlled conditions) and then used in a real environment where, for instance, sensors may be not well calibrated. In such a case, the test data do not have the same distribution as the learning data. Cautious decision rules making set-valued predictions can be expected to be particularly beneficial in such an environment, and discrepancies between the performances of different decisions rules may be more apparent than they are in the case of "clean" data considered in Section 5.1.

To validate this hypothesis, we performed the experiments on an artificial Gaussian data set. Considering a three-class problem with data set of two attributes, the training sets were simulated from three Gaussian distributions with the following characteristics:

µ 1 = [-1, 0] T , µ 2 = [1, 0] T , µ 3 = [2, 1] T , σ 1 = 0.25I, σ 2 = 0.75I, σ 3 = 0.5I,
where I is the identity matrix. Figure 2 visualizes a particular dataset of 600 instances generated in this way.

To simulate a different distribution, a random noise was added to the features of the test instances by Algorithm 1.

γ #1 (ω * = ω 3 ) #2 (ω * = ω 2 ) #3 (ω * = ω 3 ) 0.5 ω 3 /1 ω 1 /0.2 ω 3 /1 0.6 ω 3 /1 ω 1 /0.2 {ω 1
, ω 3 }/0.64 0.7 {ω 1 , ω 3 }/0.73 ω 1 /0.2 {ω 1 , ω 3 }/0.73 0.8 {ω 1 , ω 3 }/0.82 {ω 1 , ω 2 }/0.84 {ω 1 , ω 3 }/0.82 0.9 {ω 1 , ω 3 }/0.91 Ω/0.8610 Ω/0.8584

1.0 Ω/1 Ω/1 Ω/1 -2 -1 0 1 2 3
≤ i ≤ |T | do Generate ε(i) from N (0, σ 2 ) x(i) ← x(i) + ε(i) end
We set γ = 0.8 and let the noise standard deviation σ vary from 0 to 10 to simulate different levels of noise. The experiments were repeated 20 times to compute an average result. In each experiment, the training and test sets contained 600 and 300 instances, respectively.

With higher noise level, the distribution of the test set becomes more different from that of the training set. The averaged utilities are plotted against the noise level according to various decision criteria in Figure 3. Similar to the previous experiment, the percentage of precise predictions shown in Figure 4 helps to analyse the performances.

For σ = 0, the test set and the training set have the same distribution; the criteria based on partial preorder achieve lower averaged utilities as they make more precise but incorrect predictions. When σ increases, the averaged utilities for all criteria drop quickly and the performances of different criteria start to differ. When the test set distribution becomes more different, the maximax and weak dominance criteria perform worse than others, as they make precise predictions most of the time. For the other seven criteria, as σ varies from 3 to 10, the averaged utilities remain stable or even increase slightly. Basically, when uncertainty increases, the decision criteria (except maximax and weak dominance) assign more instances to sets. As different classes overlap more with larger σ , imprecise predictions are more likely to contain the true labels, achieving a higher averaged utility. The maximin criterion is the most conservative, resulting in fewer misclassifications.

Performances with Increasing Training Set Size

In the third experiment, we compared the performances of different decision criteria as the size of the training set increases. We kept the same experimental settings as in Section 5.2. The size of the training set was increased from 60 to 1200. Twenty training sets of each size were randomly generated and the average result was considered. A test set of 300 instances was used for performance evaluation. Figures 5 and6 display the averaged utilities for different decision criteria for two settings of the DS neural network classifier 1 , respectively, α m = 0.99 (more specific belief functions) and α m = 0.8 (less specific belief functions). In Figures 7 and8, we also give the percentages of precise predictions for, respectively, α m = 0.99 and α m = 0.8. When α m = 0.99 (Figures 5 and7), the output belief functions are close to probabilities. Overall, all criteria based on a complete preorder of partial assignments perform similarly, and significantly better than the criteria based on a partial preorder. When the training set size is smaller than 240, the increase of averaged utility is mainly due to the increasing proportion of precise and correct 1. Parameter 0 < α m < 1 controls the masses given to Ω and each singleton class ω i in the DS neural network classifier (Eqs ( 17) and (18) in Ref. [START_REF] Denoeux | A neural network classifier based on Dempster-Shafer theory[END_REF]). The belief functions provided by the classifier become more specific as α m increases, say, m(ω 1 ) = 0.02, m(ω 2 ) = 0.97, m(Ω) = 0.01 when α m = 0.99 and m(ω 1 ) = 0.07, m(ω 2 ) = 0.90, m(Ω) = 0.03 when α m = 0.8. predictions. When the size continues to grow, more imprecise predictions are made. The averaged utilities increase slightly as some misclassified instances become imprecisely but correctly predicted ones. Compared to the OWA decision criterion, the maximax criterion makes more precise predictions but has similar averaged utility.

When the belief functions are less specific (Figures 6 and8), as the size of the training set increases, more precise predictions lead to an increase in averaged utilities. The maximax and Hurwicz criteria work best in this case. The maximin criterion, which is the most conservative, has relatively low averaged utilities as its predicted sets are larger than others.

For both settings α m = 0.99 and α m = 0.8, the weak dominance criterion gives precise predictions almost all the time and has the worst performance. All the other criteria lead to set-valued predictions, which results in higher averaged utilities.

In addition, it is also notable that for all the experiments, the interval dominance and maximality criteria have quite similar performances. The optimal set of maximality F * max is included in that of interval dominance F * ID . For the data sets used in this paper, F * ID yields singleton predictions most of the times, leaving little space for maximality to provide different decisions.

Conclusion

To make set-valued predictions in evidential classification problems, decision criteria can be based either on a partial preorder among precise assignments, or on a complete preorder among partial assignments. Using an extended utility matrix generated via an OWA operator, experimental com-parisons were performed on UCI and simulated Gaussian data sets. The set-valued predictions induced by a partial preorder turn into precise ones when information becomes more precise. In contrast, the criteria based on a complete preorder can provide set-valued predictions even when uncertainty is quantified by probabilities. Experimental results suggest that set-valued predictions perform better than precise ones in the case of complex data sets: therefore, the most cautious rules should be preferred in highly uncertain environments. More experiments are needed to determine which decision rules should be recommended for different classification problems.

Whereas the Dempster-Shafer setting was assumed in this paper, a similar analysis could be carried out in other settings such as the imprecise probability framework [START_REF] Augustin | Introduction to imprecise probabilities[END_REF]. Also, the belief functions used in this paper were obtained with a particular evidential classifier. In future work, we will consider other DS theory-based classifiers such as described in [START_REF] Kanjanatarakul | An evidential k-nearest neighbor classifier based on contextual discounting[END_REF][START_REF] Denoeux | Logistic regression, neural networks and Dempster-Shafer theory: A new perspective[END_REF], and we will analyse the performances of various decision rules when mass functions have more general focal sets. The various approaches to decision-making in evidential classifications will also be explored more thoroughly, both theoretically and empirically.

Figure 2 : 1 :

 21 Figure 2: A Gaussian data set of 600 instances

Figure 5 :

 5 Figure 5: Averaged utilities of different criteria as a function of training set size (α m = 0.99)

Figure 8 :

 8 Figure 8: Percentage of precise predictions as a function of training set size (α m = 0.8)

Table 1 :

 1 Decision criteria inducing partial preorders

	decision criterion	preference relation
	interval dominance

Table 2 :

 2 Decision criteria inducing complete preorders

	decision criterion	preference relation	detail
	generalized maximin

Table 3 :

 3 Utility matrix extended by an OWA operator with

	γ = 0.8
	acts	ω 1	states of nature ω 2	ω 3
	f {ω 1 }	1.0000 0.2000 0.1000
	f {ω 2 }	0.2000 1.0000 0.2000
	f {ω 3 }	0.1000 0.2000 1.0000
	f {ω 1 ,ω 2 }	0.8400 0.8400 0.1800
	f {ω 1 ,ω 3 }	0.8200 0.2000 0.8200
	f {ω 2 ,ω 3 }	0.1800 0.8400 0.8400
	f {ω 1 ,ω 2 ,ω 3 } 0.7373 0.7455 0.7373

Table 3 ,

 3 γ = 0.8), we can see the similarity between them. Our method assigns slightly lower utilities to set predictions containing

	u 11	1
		0.9
		0.8
		0.7
		0.6
	utility	0.5
		0.4
		0.3
	u 21	0.2
	u 31	0.1
		0
		0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
						utility OWA operator
	Figure 1: Aggregated utilities vs. tolerance degree of im-
			precision γ

Table 4 :

 4 Utility matrix extended by the p-discounted costs approach (p = 4)

	acts	ω 1	states of nature ω 2	ω 3
	f {ω 1 }	1.0000 0.2000 0.1000
	f {ω 2 }	0.2000 1.0000 0.2000
	f {ω 3 }	0.1000 0.2000 1.0000
	f {ω 1 ,ω 2 }	0.8412 0.8412 0.1707
	f {ω 1 ,ω 3 }	0.8409 0.2000 0.8409
	f {ω 2 ,ω 3 }

Table 5 :

 5 Results for the Balance scale data set with different values of γ

		DC1	DC2	DC3	DC4	DC5	DC6	DC7	DC8	DC9
	averaged utility	γ=0.5 0.9186 γ=0.6 0.9179 γ=0.7 0.9059 γ=0.8 0.9043 γ=0.9 0.9339 γ=1.0 1.0000	0.9188 0.9184 0.9064 0.9032 0.9319 1.0000	0.9186 0.9176 0.9052 0.9028 0.9325 1.0000	0.9186 0.9179 0.9059 0.9043 0.9339 1.0000	0.9186 0.9184 0.9056 0.9030 0.9331 1.0000	0.9186 0.9176 0.9054 0.9024 0.9319 1.0000	0.9187 0.9188 0.9190 0.9191 0.9192 0.9194	0.9187 0.9188 0.9190 0.9191 0.9192 0.9194	0.9187 0.9187 0.9187 0.9188 0.9188 0.9188
	% of precision	γ=0.5 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 97.44% 97.44% 99.97% γ=0.6 88.96% 89.47% 88.96% 88.96% 89.18% 89.06% 97.44% 97.44% 99.97% γ=0.7 80.10% 80.77% 80.06% 80.10% 80.22% 80.26% 97.44% 97.44% 99.97% γ=0.8 69.70% 70.14% 69.63% 69.70% 69.82% 69.63% 97.44% 97.44% 99.97% γ=0.9 57.02% 57.76% 57.12% 57.02% 57.38% 57.12% 97.44% 97.44% 99.97% γ=1.0 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 97.44% 97.44% 99.97%
	1 DC1: maximin DC2: maximax DC3: pignistic DC4: minimax regret DC5: Hurwicz (α = 0.6) DC6: OWA (β = 0.6)
		DC7: interval dominance DC8: maximality DC9: weak dominance

Table 6 :

 6 Label predictions/utilities with different

© L. Ma & T. Denoeux.

Acknowledgments

This research was supported by Shandong Provincial Natural Science Foundation ZR2018PF009, Shandong Provincial Key Research and Development Program 2017GGX10116 and the China Scholarship Council. It was also supported by the Labex MS2T funded by the French Government through the program "Investments for the future" by the National Agency for Research (reference ANR-11-IDEX-0004-02).


Feng Li

Shoumei Li

Thierry Denoeux
email: tdenoeux@utc.fr

Combining clusterings in the belief function framework $

Keywords: Evidence theory, Belief functions, Clustering ensemble, Intuitionistic fuzzy relation

Combining clusterings in the belief function framework

Introduction

Clustering is an important task in Machine Learning and Pattern Recognition. It is a statistical method to divide objects into groups, in such a way that objects are similar within each group, and dissimilar across different groups. Clustering methods have proved useful in many real-world application domains, such as data mining, image segmentation, etc.

According to the form of clustering output, we can distinguish between hard and soft partitional clustering; the latter includes fuzzy and evidential clustering. In particular, evidential clustering, based on Dempster-Shafer (DS) theory (also called the theory of belief functions) [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF], has recently attracted the attention of many researchers. Evidential clustering computes a credal partition, which describes cluster membership uncertainty using DS mass functions.

In recent years, several evidential clustering algorithms have been developed. [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] first introduced an evidential relational clustering method called EVCLUS. This method finds a credal partition such that the degree of conflict between the mass functions associated with any two objects match their dissimilarity. Antoine et al. [START_REF] Antoine | CEVCLUS: Evidential clustering with instance-level constraints for relational data[END_REF] proposed a constrained version of EVCLUS, called CEVCLUS, which utilizes prior information provided as pairwise constraints. Denoeux et al. [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF] introduced a faster version of EVCLUS, called k-EVCLUS, where a new cost function is defined and optimized by an iterative row-wise quadratic programming (IRQP) algorithm. Li et al. [START_REF] Li | k-CEVCLUS: Constrained evidential clustering of large dissimilarity data[END_REF] further expanded the k-EVCLUS method by taking prior knowledge into account.

In [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], Masson and Denoeux introduced the evidential c-means algorithm (ECM), which is an extension of the classic and fuzzy c-means in the framework of DS theory. The ECM alternatively searches for the best credal partition and the best prototypes. Masson et al. [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] proposed a variant of ECM for dissimilarity data, called RECM. Antoine et al. [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF] introduced a constrained version of ECM (called CECM) by considering prior knowledge. Liu et al. [START_REF] Liu | Credal c-means clustering method based on belief functions[END_REF] proposed another variant of the ECM algorithm, called CCM, by introducing the notion of meta-cluster. Zhou et al. [START_REF] Zhou | Median evidential c-means algorithm and its application to community detection[END_REF] extended the median c-means and median fuzzy c-means to the Median Evidential c-means (MECM). [START_REF] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF] [START_REF] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF] introduced a new evidential clustering algorithm (Ek-NNclus) based on the evidential k nearest neighbor rule.

Different clustering algorithms may obtain different clustering results for one dataset, and even a single algorithm with different initializations may yield different solutions. It is generally agreed that there is no best single clustering algorithm [START_REF] Akbari | Hierarchical cluster ensemble selection[END_REF]. To solve this problem and further improve the robustness, consistency and stability of the solution, clustering ensemble methods have emerged as an approach for combining multiple clustering results into an improved solution. Among those, the Evidence Accumulation Clustering (EAC) method [START_REF] Fred | Data clustering using evidence accumulation[END_REF][START_REF] Fred | Combining multiple clusterings using evidence accumulation[END_REF] has attracted a lot of attention. It constructs a co-association matrix from base partitions, which can be processed by a hierarchical clustering algorithm to obtain the final solution.

In this paper, we introduce an evidential clustering ensemble method that can be seen as an extension of the EAC method in the DS framework. In our method, base evidential partitions are generated by evidential clustering algorithms. As noted in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], evidential partitions allow for ambiguity, uncertainty or doubt in the assignment of objects to clusters, and constitute a rich and informative description of the clustering structure of a dataset. The base credal partitions are transformed into their relational representations [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF], which are combined using different rules of DS theory. The fused relational representation corresponds to the co-association matrix in the EAC method. It can be seen as defining an intuitionistic fuzzy relation [START_REF] Li | The structures of intuitionistic fuzzy equivalence relations[END_REF], which is made transitive to obtain an intuitionistic fuzzy equivalence relation. The final evidential partition is obtained by minimizing an objective function based on the credal Rand index [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. Experiments with real and simulated data show that our approach can reveal the underlying clustering structure of complex-shape datasets and achieve better results than EAC and single clustering algorithms.

The rest of this paper is organized as follows. Basic notions are first recalled in Section 2. Our method is then described in Section 3, and experimental results are reported in Section 4. Finally, Section 5 concludes the paper.

Background

In this section, we briefly introduce some basic notions used in this paper. The main definitions of DS theory are first recalled in Section 2.1. The notions of credal partition and relational representation are then reviewed in Section 2.2. Section 2.3 introduces intuitionistic fuzzy relations and the transitive closure theorem. We then describe the EAC method in Section 2.4, and we review some related work in Section 2.5.

DS theory

Let Ω = {ω 1 , . . . , ω c } be a finite set. A mass function on Ω is a mapping from the power set 2 Ω to [0, 1], satisfying the condition A⊆Ω m(A) = 1.

(1)

Each subset A of Ω such that m(A) > 0 is called a focal set. In DS theory, a mass function is viewed as a piece of evidence about some question of interest, for which the true answer, denoted by ω, is supposed to be an element of Ω. For any nonempty focal set A, m(A) is a measure of the belief that is committed exactly to A [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The mass m(∅) assigned to the empty set is a measure of the belief that the true answer might not belong to Ω.

m * (A) = m(A) 1 -m(∅) . (2)
Given a mass function m, the corresponding belief and plausibility functions are defined, respectively, as bel

(A) = ∅ =B⊆A m(B)
and

pl(A) = B∩A =∅ m(B),
for all A ⊆ Ω. Clearly, functions bel and pl are linked by the relation pl(A) = 1 -bel(A), where A denotes the complement of A. The quantity bel(A) represents the degree of total support in A, while pl(A) can be interpreted as the degree to which the evidence is consistent with A. Different combination rules have been proposed in the literature. For example, the conjunctive rule [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] and the dual disjunctive rule [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF] are defined, respectively, as

(m 1 ∩ m 2 )(A) = B∩C=A m 1 (B)m 2 (C), ( 3a
) (m 1 ∪ m 2 )(A) = B∪C=A m 1 (B)m 2 (C), (3b)
for any two mass functions m 1 and m 2 on the same frame Ω and all A ⊆ Ω. As shown by Smets [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF], the conjunctive rule assumes that all mass functions to be combined are derived from reliable sources of information, whereas the disjunctive rule only assumes that at least one source of information is reliable, but we do not know which one. Dempster's rule, denoted by ⊕, is defined by the conjunctive rule (3a) followed by normalization (2), i.e., (m 1 ⊕ m 2 )(∅) = 0 and

(m 1 ⊕ m 2 )(A) = (m 1 ∩ m 2 )(A) 1 -(m 1 ∩ m 2 )(∅) (4)
for all A = ∅. The Dubois-Prade (DP) rule [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF] assumes that when two sources are not in conflict, they are both reliable, and at least one is correct when they are conflicting. Specifically, for two mass functions m 1 and m 2 , their combination by the DP rule, denoted by m 1 m 2 , is

(m 1 m 2 )(A) = B∩C=A B∩C =∅ m 1 (B)m 2 (C) + B∪C=A B∩C=∅ m 1 (B)m 2 (C), ∀A = ∅. (5)
It can be seen as a reasonable trade-off between the conjunctive and disjunctive rules.

Let us now assume that mass function m represents our current state of knowledge about ω, and we need to choose one or several elements of Ω as our estimate about the true answer. Decision rules in the DS framework are reviewed in [START_REF] Denoeux | Decision-making with belief functions: a review[END_REF]. Here, we only mention two rules that will be used in the sequel. The maximum plausibility rule selects the element ω * with the highest plausibility,

ω * = arg max ω∈Ω pl({ω}). (6)
This rule yields one single result. In contrast, the interval dominance rule [START_REF] Denoeux | Decision-making with belief functions: a review[END_REF] is based on the following dominance relation: ω dominates ω , iff bel({ω}) > pl({ω }). Then the set of its maximal (non-dominated) elements can be obtained as

Ω * = {ω ∈ Ω | pl({ω}) ≥ bel({ω }), ∀ω ∈ Ω}. (7)
Instead of reaching a single decision, this rule selects a set of potential results.

Credal partitions

Let O be a set of n objects, and Ω = {ω 1 , ..., ω c } the set of clusters. Each object is assumed to belong to at most one cluster. Uncertain knowledge about the cluster-membership of object o i is represented by a mass function m i on Ω. A credal partition [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] is defined as an n-tuple M = (m 1 , .., m n ). The notion of credal partition is more general than those of hard or fuzzy partitions, and a credal partition can be summarized into a partition of any other type [START_REF] Denoeux | Beyond fuzzy, possibilistic and rough: An investigation of belief functions in clustering[END_REF]. Credal partitions also encompass rough partitions as a special case [START_REF] Peters | Soft clustering: fuzzy and rough approaches and their extensions and derivatives[END_REF][START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]: a rough partition corresponds to a credal partition in which all mass functions m i are logical, namely m i (A i ) = 1 for some A i ⊆ Ω. The lower and upper approximations of cluster ω k can then be defined as follows,

ω L k = {o i ∈ O | A i = {ω k }} (8a)
and

ω U k = {o i ∈ O | ω k ∈ A i }. ( 8b
)
For a non-logical mass function m i , the set A i can be selected by the interval dominance rule [START_REF] Denoeux | Decision-making with belief functions: a review[END_REF], after which a rough partition can be obtained. Suppose m i and m j are two mass functions related to objects i and j. We consider the frame Θ ij = {s ij , ¬s ij }, where s ij means that "Objects i and j belong to the same cluster", and ¬s ij means that "Objects i and j belong to different clusters". A mass function m ij on Θ ij representing our beliefs about the joint cluster-membership of objects i and j can be computed from m i and m j as follows [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]:

m ij (∅) = m i (∅) + m j (∅) -m i (∅)m j (∅), (9a)
m ij ({s ij }) = c k=1 m i ({ω k })m j ({ω k }), (9b)
m ij ({¬s ij }) = A∩B=∅ m i (A)m j (B) -m ij (∅), (9c)
m ij (Θ ij ) = A∩B =∅ m i (A)m j (B) -m ij ({s ij }), (9d)
The tuple R = (m ij ) 1≤i≤j≤n is called the relational representation of M . We note that m ij (∅) = 0 whenever m i (∅) = 0 and m j (∅) = 0. Given two credal partitions M and M and their relational representations R and R , the credal Rand index [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF] is defined as

ρ S (R, R ) = 1 - i<j δ(m ij , m ij ) n(n -1)/2 , ( 10
)
where δ is the Jousselme's distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]. In the special case where mass functions are normal, i.e., m ij (∅) = m ij (∅) = 0, we can write mass function m ij as a vector

m ij = (m ij ({s ij }), m ij ({¬s ij }), m ij (Θ ij )) T .
Jousselme's distance between m ij and m ij is then defined as

δ(m ij , m ij ) = 1 2 (m ij -m ij ) T J(m ij -m ij ) 1/2
, where J is the Jaccard matrix

J =   1 0 1/2 0 1 1/2 1/2 1/2 1   . (11)
The range of ρ S is [0, 1], and it boils down to the Rand index when both M and M are hard partitions. The credal Rand index measures the similarity between any two soft partitions.

Intuitionistic Fuzzy Equivalence Relation

Fuzzy relations. In classical set theory, an equivalence relation provides a partition of the underlying set into disjoint equivalence classes. In fuzzy set theory, a fuzzy relation R on a finite set X is defined as a fuzzy subset of the Cartesian product X 2 , i.e., a mapping from X 2 to [0, 1] [START_REF] Ovchinnikov | An introduction to fuzzy relations[END_REF]. Each membership value R(x, y) represents the degree to which x stands in relation R with y. For a fuzzy relation R, we define the following properties:

Reflexivity: For all x ∈ X, R(x, x) = 1;

Irreflexivity: For all x ∈ X, R(x, x) = 0;

Symmetry: For all (x, y) ∈ X 2 , R(x, y) = R(y, x);

Transitivity: For all (x, y, z) ∈ X 3 , min(R(x, y), R(y, z)) ≤ R(x, z).

Furthermore, R is dual transitive iff 1 -R is transitive. If a fuzzy relation is reflexive, symmetric and transitive, it is called a fuzzy equivalence relation. Sometimes, another triangular norm (t-norm) than the minimum is used in the definition of transitivity. For a t-norm T , R is said to be T -transitive if for all (x, y, z) ∈ X 3 , T (R(x, y), R(y, z)) ≤ R(x, z).

The max-T composition for two fuzzy relations R and Q on X is the fuzzy relation

R • Q defined by (R • Q)(x, y) = max z∈X T (R(x, z), Q(z, y)). (12)
Denoting R • R as R 2 , the T -transitivity property can be expressed as R 2 ⊆ R.

The max-T transitive closure R of a fuzzy relation R is the smallest max-T transitive fuzzy relation containing R. It can be computed as

R = ∞ i=1 R i , ( 13
)
where ∪ is the fuzzy set union based on the maximum t-conorm. In particular, if R is a reflexive and symmetric fuzzy relation on a finite set X of cardinality n, then R = R n-1 [START_REF] Boixader | Fuzzy equivalence relations: advanced material[END_REF].

Intuitionistic Fuzzy relations. The notion of Intuitionistic Fuzzy Relation (IFR) is a further generalization of relations based on the theory of intuitionistic fuzzy sets [START_REF] Li | The structures of intuitionistic fuzzy equivalence relations[END_REF]. An intuitionistic fuzzy subset (IFS) A of X is a pair of mappings µ A : X → [0, 1] and ν A : X → [0, 1] such that µ A (x) + ν A (x) ≤ 1 for each x ∈ X. The values µ A (x) and ν A (x) represent, respectively, the membership degree and non-membership degree of element x in the set A. The pair (µ A (x), ν A (x)) is called an intuitionistic fuzzy value (IFV). Let L be the set of all IFVs, i.e.,

L = {α = (µ α , ν α ) | µ α ∈ [0, 1], ν α ∈ [0, 1], µ α + ν α ≤ 1}.
A partial ordering relation on L can be defined as follow:

α ≤ L α ⇔ µ α ≤ µ α and ν α ≥ ν α ,
for all (α, α ) ∈ L 2 . Any pair (α, α ) ∈ L 2 has a unique least upper bound α ∨ α and a unique greatest lower bound α ∧ α given, respectively, by

α ∨ α = max(µ α , µ α ), min(ν α , ν α ) and α ∧ α = min(µ α , µ α ), max(ν α , ν α ) .
Thus (L, ≤ L ) is a complete lattice, with top (1, 0) and bottom (0, 1). An IFR on a non-empty set X is an IFS of X 2 , i.e., a mapping R : X 2 → L. For an IFR R we define the following properties:

Reflexivity: For all x ∈ X, R(x, x) = (1, 0); Symmetry: For all (x, y) ∈ X 2 , R(x, y) = R(y, x); Transitivity: For all (x, y, z) ∈ X 3 , y∈X (R(x, y) ∧ R(y, z)) ≤ L R(x, z).
A reflexive, symmetric and transitive IFR is called an Intuitionistic Fuzzy Equivalence Relation (IFER). An IFR R = (µ R , ν R ) is an IFER if and only if µ R is reflexive, symmetric and transitive, and ν R is irreflexive, symmetric and dual transitive [START_REF] Li | The structures of intuitionistic fuzzy equivalence relations[END_REF]. Consequently, the transitivity of an IFR can be obtained by making µ R and 1 -ν R transitive. In the experiments reported in Section 4, we consider three t-norms: the minimum, the product, and the Lukasiewicz t-norm defined as T (a, b) = max(0, a + b -1).

Evidence Accumulation Clustering

In this section, we briefly summarize the EAC method [START_REF] Fred | Data clustering using evidence accumulation[END_REF][START_REF] Fred | Combining multiple clusterings using evidence accumulation[END_REF]. More details can be found in [START_REF] Ghaemi | A survey: Clustering ensembles techniques[END_REF][START_REF] Vega-Pons | A survey of clustering ensemble algorithms[END_REF][START_REF] Zhan | Research advance of clustering ensemble algorithm[END_REF]. The EAC method uses the co-association matrix to avoid the label correspondence problem. More precisely, assume that a dataset has n objects O = {o 1 , o 2 , . . . , o n }. Suppose that N base partitions P 1 , . . . , P N have been obtained in the first step. In the second step, each base partition P b is mapped to a co-association matrix S b of size N × N with general term

s b ij = I(c b i = c b j )
, where c b i is the cluster index of x i in P b and I is the indicator function. The co-association matrix, denoted as S * = (s * ij ), is the average of all S b ; its general term is

s * ij = 1 N N b=1 s b ij . (14)
Each element s * ij represents the proportion of base partitions in which objects o i and o j are assigned to the same cluster. The co-association matrix can be treated as a new similarity matrix and used as input to single-linkage hierarchical clustering.

In EAC, the co-association matrix is computed by only taking into account whether two objects belong to the same cluster or not. Some researchers [START_REF] Iam-On | Refining pairwise similarity matrix for cluster ensemble problem with cluster relations[END_REF][START_REF] Vega-Pons | Clustering ensemble method for heterogeneous partitions[END_REF][START_REF] Wang | Clustering aggregation by probability accumulation[END_REF] have proposed to use additional information to construct a similarity measure that is more expressive about the relationship between objects. For instance, Yang [START_REF] Yang | Soft cluster ensemble based on fuzzy similarity measure[END_REF] proposed a fuzzy co-association matrix to summarize the ensemble of fuzzy partitions, where the membership of an object to clusters is expressed by a fuzzy membership function.

We can remark that, in the EAC method, the numbers of clusters in the base partitions do not need to be close to the "true" number of clusters. Indeed, in [START_REF] Fred | Combining multiple clusterings using evidence accumulation[END_REF], the authors construct the base partitions using the k-means algorithms with a large (and sometimes random) number of clusters. For instance, in one dataset with two clusters, they construct base partitions with up to 80 clusters. The underlying assumption is that objects that truly belong to true same cluster are likely to be assigned to the same cluster in different partitions, which is summarized in the co-association matrix. The number of clusters in the final aggregated partition is determined by analyzing the dendrogram after applying single-link hierarchical clustering to the co-association matrix.

In this paper, we propose to extend the EAC method in the framework of DS theory. In our method, the membership of an object to clusters is represented by a mass function in the credal partition, which contains more information than fuzzy and hard partitions. To better exploit this type of information, we use the relational interpretation recalled in Section 2.2 to measure the "similarity" between objects, which can be seen as a generalization of the co-association matrix. To capture the neighborhood relationship, we make the combined relational representation transitive based on IFR theory recalled in Section 2.3.

Other related Work

In the ensemble clustering literature, most contributions focus on hard partitions, and some are based on fuzzy partitions. Only a few methods are based on DS theory. DS theory is a sound approach for ensemble clustering methods, because it provides ways to combine different pieces of evidence. Preliminary results have already demonstrated the feasibility of this approach. For example, in [START_REF] Denoeux | Evidential reasoning in large partially ordered sets[END_REF][START_REF] Masson | Ensemble clustering in the belief functions framework[END_REF] the authors propose to define mass functions on the lattice of interval partitions of a set of objects; they obtain a consensus belief function by a suitable combination rule, and use hierarchical clustering to get the final partition. Unlike other direct methods relying on a voting process, Li et al. [START_REF] Li | Multigranulation information fusion: A Dempster-Shafer evidence theory-based clustering ensemble method[END_REF] introduce another direct approach based on Dempster's rule of combination; their method consists of two steps: finding the correspondence labels and using the combination rule to produce the final result. Although these ensemble clustering methods are rooted in Dempster's theory, they still consider hard partitions as input and also output of the procedure. Wang et al. [START_REF] Wang | Ensemble clustering based on evidence theory[END_REF] propose an ensemble clustering method for evidential partitions. After solving the label correspondence problem, the final results are obtained by combining the selected base partitions. Due to high computational complexity, they only consider the fixed (true) number of clusters in the base partitions.

In this paper, we combine credal partitions, a very general form of partitions that can be generated by hard, fuzzy, rough or evidential clustering algorithms. After mapping the base partitions to their relational representations, we combine these partitions in a coarser frame, where we only need to consider two focal sets. The combined relational representation is made transitive using the theory of IFRs. Finally, we generate an evidential partition that matches the combined relational representation, providing a much more informative output than can be obtained using hard or fuzzy clustering methods.

Evidential Clustering Ensemble Method

In this section, we introduce the proposed method. The generation and combination of base credal partitions are described in Section 3.1. The computation of transitive closures to make the combined relational representation transitive is then addressed in Section 3.2, and the method for computing the final credal partition is presented in Section 3.3.

Generation of base partitions

In the first step of our method, base partitions can be obtained by hard, fuzzy and rough clustering methods, which all produce special forms of credal partitions. In this paper, we focus on base partitions generated by evidential clustering methods. We assume that we start with N base partitions

M b = (m b 1 , . . . , m b n ), b = 1, .
.., N generated by evidential clustering algorithms such as ECM or EVCLUS. The number of clusters in base partition b is denoted by k b . Before converting credal partitions to their relational representations, we compute the average mass assigned to the empty set for each object i as

m i (∅) = 1 N N b=1 m b i (∅), i = 1, ..., n, (15)
and we normalize each base credal partition by [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF]. We denote the b-th normalized credal partition as

M b * = (m b * 1 , . . . , m b * n ),
m b * i (A) = m b i (A) 1 -m b i (∅) , (16)
for all nonempty subset A of Ω. The reason for this normalization is that the analogy between relation representations and IFRs developed in Section 3.2 requires the mass functions to be normalized. However, we cannot just discard the mass on the empty set, because it is useful to detect outliers. This information will be utilized in the last step of our method (see Section 3.3).

After the relational representations R b * have been computed, they can be combined using different rules. The combined relational representation is denoted by R * = (m * ij ) 1≤i≤j≤n . For example, using the average rule we get

m * ij = 1 N N b=1 m b * ij .
We can remark that, when the base partitions are hard, the n × n matrix with general term [m * ij ({s})] boils down to the co-association matrix [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. As a consequence, EAC is a special case of our method. Other combination rules introduced in Section 2.1 can also be used.

Transitivity

The combined relational representation R * sometimes cannot be successfully exploited because it lacks a notion of transitivity, namely: if we believe that objects i and j belong to the same cluster, and objects j and k also belong to the same cluster, then we should believe that this is also the case for objects i and k. When applying hierarchical clustering in the second step, this property is used implicitly in the EAC method.

A relational representation is not a classical fuzzy relation, because it specifies two numbers for each pair (i, j); the degree of belief that i and j belong to the same cluster, and the degree of belief that they do not belong to the same cluster. We can observe the similarity between this kind of information and IFRs recalled in Section 2.3. Using this formal analogy, we consider the combined relational representation R * as an IFR, and we make it transitive using the techniques reviewed in Section 2.3.

For a normalized mass function m * ij on Θ ij , the degrees of belief in s ij and ¬s ij are, respectively,

bel * ij ({s ij }) = m * ij ({s ij }) and bel * ij ({¬s ij }) = m * ij ({¬s ij }), with bel * ij ({s ij }) + bel * ij ({¬s ij }) ≤ 1. These numbers define an IFR R = (µ R , ν R ) on the set O of objects, with µ R (o i , o j ) = bel * ij ({s ij }) and ν R (o i , o j ) = bel * ij ({¬s ij }).
This IFR is reflexive (as bel * ii ({s ii }) = 1 and bel * ii ({¬s ii }) = 0 for all i) and symmetric, but it is usually not transitive. As recalled in Section 2.3, R is transitive iff µ R is transitive and ν R is dual transitive, i.e., ν d R = 1 -ν R is transitive. To obtain an IFER, we thus need to replace µ R and ν d R by their transitive closures. We observe that

ν d R (o i , o j ) = 1 -bel * ij ({¬s ij }) = pl * ij ({s ij }).
Denoting by µ R and ν d R the transitive closures of µ R and

ν d R , let bel ij ({s ij }) = µ R (o i , o j ) and pl ij ({s ij }) = ν d R (o i , o j
). These belief and plausibility values correspond to new mass functions m ij such that m ij (∅) = 0 and

m ij ({s ij }) = bel ij ({s ij }), (17a)
m ij ({¬s ij }) = 1 -pl ij ({s ij }), (17b)
m ij (Θ ij ) = pl ij ({s ij }) -bel ij ({s ij }). (17c)
The new relational representation R = (m ij ) 1≤i≤j≤n will hereafter be referred to as the transitivized combined relational representation.

Recovering the combined credal partition

In the EAC method, the final result is obtained by applying hierarchical clustering to the association matrix. We could apply the same procedure to matrices (bel ij ({s ij })) or (pl ij ({s ij }), similarly to what was proposed in [START_REF] Masson | Ensemble clustering in the belief functions framework[END_REF]. However, our objective is to recover a credal partition, which cannot be obtained by a hierarchical clustering algorithm.

Our approach is to find a normalized credal partition M * whose relation representation is as close as possible to the transitivized combined relational representation R, closeness being measured by the credal Rand index [START_REF] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF]. We need to fix the number k r of clusters as well as the focal sets in the credal partition M * . For example, we can take the singletons and Ω as focal sets, or we can also consider some pairs of clusters.

We thus seek a normal credal partition M * , solution of the maximization problem

max M * ρ S (R(M * ), R), (18)
where R(M * ) is the relational representation of M * . From [START_REF] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF], maximizing ( 18) is equivalent to minimizing the following stress (error) function:

S(M * ) = i<j (m * ij -m ij ) T J(m * ij -m ij ), (19)
where

m * ij = (m * ij ({s ij }), m * ij ({¬s ij }), m * ij (Θ ij )) T , m ij = (m ij ({s}), m ij ({¬s}), m ij (Θ ij )) T ,
and J is the Jaccard matrix [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. To solve [START_REF] Iam-On | Refining pairwise similarity matrix for cluster ensemble problem with cluster relations[END_REF], let us write m * ij as a function of mass functions m * i and m * j in matrix form. Assuming that each mass function m * i has f focal sets F 1 , . . . , F f , it can be written as an f -vector m * i = (m * i (F 1 ), . . . , m * i (F f )) T , and the credal partition can be written as an n × f matrix M * = (m * 1 , . . . , m * n ) T . Let S = (S k ) and C = (C kl ) be the f × f matrices defined as follows:

S kl = 1 if k = l and |F k | = 1 0 otherwise, (20)
and

C kl = 1 if F k ∩ F l = ∅, 0 otherwise. ( 21
)
We have:

m * ij ({s ij }) = (m * i ) T S m * j , (22a)
m * ij ({¬s ij }) = (m * i ) T C m * j , (22b)
m * ij (Θ ij ) = 1 -m * ij ({s ij }) -m * ij ({¬s ij }). (22c)
We can observe that m * ij is linear in m * i and, consequently, S(M * ) is quadratic in m * i , the other mass functions being fixed. Consequently, we can minimize S(M * ) using a cyclic coordinate descent algorithm, minimizing S(M * ) with respect to each m * i in turn, while keeping the other m * j constant; this is the iterative row-wise quadratic programming (IRQP) algorithm [START_REF] Ter Braak | Approximating a similarity matrix by a latent class model: a reappraisal of additive fuzzy clustering[END_REF], also used in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. Using this approach, we minimize at each step the following cost function:

g i (m * i ) = n j=1 j =i (m * ij -m ij ) T J(m * ij -m ij ), (23)
which is quadratic in m * i . To simplify the expression of this function, let us define the matrix A j of size 3 × 3f as

A j = I 3 ⊗ (m * j ) T . ( 24
)
where I 3 is the identity matrix of size 3 × 3 and ⊗ is the Kronecker product, and the matrix B of size 3f × f as

B =   S C 1 -S -C   . ( 25
)
With these notations, (23) can be written as

g i (m i ) = n j=1 j =i (A j Bm * i -m ij ) T J(A j Bm * i -m ij ) (26)
Developing the right-hand side of ( 26) and rearranging the terms, we obtain

g i (m * i ) = (m * i ) T Σm * i + u T m * i + c 0 , (27)
with

Σ = B T     n j=1 j =i A T j JA j     B (28a) u = -2     n j=1 j =i m T ij JA j     B (28b) c 0 = n j=1 j =i m T ij Jm ij . (28c)
Minimizing g(m i ) under the constraints (m * i ) T 1 = 1 (where 1 = (1, . . . , 1) T ) and m * i ≥ 0 is a quadratic programming (QP) problem, which can be solved efficiently with any QP solver. As we iteratively update each row of M * , the overall stress S(M * ) decreases and eventually reaches a local minimum. As in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], we compute the following running mean after each cycle of the algorithm as e 0 = 1 and e t = 0.5e t-1 + 0.5

|S t -S t-1 | S t-1 , ( 29
)
where t is the iteration counter and S t is the error at iteration t. The algorithm stops when e t becomes less than some given threshold .

Let M * = ( m * 1 , . . . , m * n ) denote the normalized credal partition obtained after convergence of the algorithm. The last step is to "denormalize" it using the masses m(∅) on the empty set computed in [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF]. This is done by multiplying each mass m * (A) with A = ∅ by 1 -m(∅):

m i (A) = [1 -m i (∅)] m * i (A), (30)
for all A ∈ 2 Ω \ {∅}. The final consensus credal partition is M = ( m 1 , . . . , m n ). The whole procedure is summarized in Algorithm 1.

Concerning the time complexity of the method, converting each base credal partition to its relational representations requires O(n 2 ) operations, where n is the number of objects, and combining the average partition takes O(n 2 N ). To compute the transitive closure, Lee [START_REF] Lee | An optimal algorithm for computing the max-min transitive closure of a fuzzy similarity matrix[END_REF] describes an optimal algorithm with O(n 2 ) time complexity. Consequently, the calculation of the transitivized combined relational representation R can be performed in O(n 2 N ) operations. The most computationally demanding step of the method is to recover the credal partition from the obtained relational representation. The complexity of this step depends on the Quadratic Programming (QP) problem [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] solved at each iteration. As the Jaccard matrix ( 11) is positive definite [START_REF] Bouchard | A proof for the positive definiteness of the Jaccard index matrix[END_REF], so is matrix Σ in (27) (of size f × f , where f is the number of focal sets). Consequently, the quadratic function [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] being minimized in convex. It is known [START_REF] Vavasis | Complexity theory: quadratic programming[END_REF] that convex QP problems can be solved in polynomial time. The computing time of the optimization can be controlled by limited the number of focal sets in the recovered credal partition.

Experiments

In this section, we evaluate our approach using various datasets. In Section 4.1, we study the influence of different parameters using simulated datasets. Detailed results with simulated and real datasets are then reported in Section 4.2.

Qualitative experiments

In this section, we present the results on simulated datasets to investigate different stages of the ensemble procedure. We study the effect of different combination rules and transitive closure with different t-norms.

Effect of different combination rules

We first investigate the effect of different combination rules on the Fourclass data, consisting of four classes in two-dimensional space, each generated from a Gaussian distribution. From Figure 1a, we can see that the clusters overlap, and there is an outlier.

In the first step, we ran the ECM algorithm [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF][START_REF] Denoeux | evclust: Evidential Clustering[END_REF] with the Fourclass dataset for generating base partitions. To obtain useful information, we use the two-step approach introduced in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF][START_REF] Su | BPEC: Belief-peaks evidential clustering[END_REF] to extract informative focal sets. More precisely, the ECM algorithm was first run with ∅, the singletons and Ω as focal sets. Based on the obtained credal partition, the similarity between each pairs of clusters {ω j , ω l } was measured by s(j, l) = n i=1 pl ij pl il , where pl ij and pl il are the normalized plausibility that object i belongs, respectively, to cluster j and l. The pairs {ω j , ω l } of mutual K = 2 nearest neighbors were then selected as informative focal sets. In the second step, the evidential clustering initialized with the credal partition computed in the previous step was run again with those informative focal sets. In [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], this method has been shown to be tractable and to yield good results even when the number of clusters is large.

In this experiment, we generated N = 20 base partitions, each of which had k b = 15 clusters, and we set δ to the 0.2-quantile of the dissimilarities between objects. The diversity of the partitions is obtained by setting the number of clusters to a large number and using different random initializations. We considered the four combination rules reviewed in Section 2.1: average, Dempster, disjunctive and DP. For simplicity, after combining the relational representations we did not make the corresponding IFR transitive. We recovered a credal partition with four clusters, k r = 4. In the second step, we firstly recovered a credal partition with the mass on the singletons and Ω, and secondly with the mass on the informative focal sets as we did in the generation step. One of the base partitions is shown in Figure 1b. In Figures 1b-1f, each point is represented by a symbol corresponding to its true class, and a color corresponding to the maximum plausibility cluster [START_REF] Denoeux | evclust: Evidential Clustering[END_REF]. The convex hulls of the lower and upper approximations computed using the interval dominance rule [START_REF] Denoeux | Decision-making with belief functions: a review[END_REF] are displayed using solid and broken lines, respectively.

From Figure 1d, we can see that Dempster's rule fails to capture the structure of this dataset. As recalled in Section 2.1, important assumptions for Dempster's rule are that all the mass functions come from reliable and independent sources; it is clear that none of these assumptions is satisfied in our case. When generating the base partitions, the number of clusters is set to a larger value than the number of "natural" clusters, and the base partitions, being based on the same data, are not independent. The DP rule behaves better than Dempster's rule, as it relaxed the assumption of perfect sources. However, the DP rule also cannot recognize the structure of the dataset (Figure q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 5 10 q q q q q q q q q Base partition (b) 1f). The average and disjunctive rules both yield acceptable results (Figure 1c and1e), but the credal partition obtained by the disjunctive rule is too imprecise: the inner approximations of the clusters are very small and the upper approximations are identical, which means that all objects possibly belong to any cluster (Figure 1e). This result is due to the very cautious assumption underlying this combination rule (at least one source is reliable). In contrast, the average rule successfully identifies the objects that can be clustered with high confidence (those in the inner approximations), as well as the objects in the overlapping area between clusters (Figure 1c). As the average rule appears to be the most effective, it was used in subsequent experiments.

Effect of transitive closure with different t-norms

In this section, we investigate the effect of transitive closure with respect to different t-norms on Half-rings data. This dataset is composed of two clusters in two-dimensional space, separated by a nonlinear boundary (Figure 2a). Such non-spherical clusters are typically difficult to identify without prior information. The parameter settings were the same as before, except that we set k b = 15, N = 20, k r = 2 and δ equal to the 0.1-quantile of the dissimilarities between objects in this experiment. We combined the relational representations by the average rule and made the belief and plausibility matrix transitive with respect to the minimum, Lukasiewicz and product t-norms. We also considered the results without transitivity comparison. One of the base partitions is shown in Figure 2b.

The recovered partitions with the different transitive closure operations are shown in Figure 2c-2e, and the recovered partition without transitivity is displayed in Figure 2f. In these figures, each point is represented by a symbol corresponding to its true class, and a color corresponding to the obtained cluster using the maximal plausibility rule. We can see that, without transitivity, our method fails to identify nonspherical clusters (Figure 2f). The results with the Lukasiewicz t-norm are similar to those without transitivity (Figure 2d). The best result is obtained with the minimum t-norm (Figure 2c).

Discovering clusters with complex shape is one of the most challenging issues in clustering. In this experiment, we have show that our method has the ability to discover such clusters after making the combined relational representation transitive in the sense of IFRs.

Quantitative experiments

In this section, we apply our method to the simulated and real data summarized in Table 1. Five simulated datasets1 are shown in Figure 3; the first four datasets contain complex shape clusters, while R15 contains a comparatively larger number of well-separated clusters. All the real datasets can be found in the UCI Repository of machine learning databases2 . For all the datasets considered in this study, we assume that the "ground-truth" partition exists. To compare an evidential partition with the true partition, we first converted it to a hard partition using the maximum plausibility rule, and we computed the adjusted Rand index (ARI) between the derived hard partition and the true partition.

We used the ECM algorithm with informative pair of clusters to generate base partitions for each dataset. We considered three cases for the number of clusters in the base partitions (Table 2): fixed small number (case 1); randomly selected from an interval (case 2) and fixed large number q q q q q qq q qq q q q q q q q q q q q q q q q q qq qq q q q q q q q q q q q q q q q 5 10 15 20

q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 10 15 20 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 2 4 6 8 10 12 14 (c) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q qq q q q q q q q q q 5 10 15

q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q 4 6 8 10 12 14 16 For comparison, we show the results of the ECM algorithm with the true number of clusters. For this method, only ∅ and singletons were treated as focal sets, and we fixed δ = 100. We also compared our method with the EAC method: in the first step we used the hard c-means algorithm to obtain N = 100 base partitions; in the second step, we used single-linkage hierarchical clustering to obtain the true number of clusters. For the EAC method, we also considered three cases as we did in our method. The results for the ECM algorithm and the EAC method are shown in the first and second columns of Table 3.

From Table 3, we can see that the results obtained by our method are better than those obtained by the ECM algorithm, except for the Wine data. When compared to the EAC method, our method achieves higher accuracy and better stability, especially for real datasets. The EAC method performs very well with simulated datasets, but better or similar results were obtained with our method, except for the Spiral dataset.

Comparing the results obtained with different t-norms for the transitive closure operation, we can see that the minimum t-norm often performs well, except with the R15 and Seeds dataset, for which better results are obtained with the other t-norms, or even without transitivity. The results with the Lukasiewicz and product t-norms are often similar to those obtained without transitivity. Generally, it seems that making the combined relational minimum-transitive is beneficial for datasets with complex-shaped clusters, but it can sometimes degrade the performance for datasets with overlapping clusters. The reason is that, where there is an overlapping area between clusters and we make the fuzzy relation transitive, objects from different clusters become similar to each other, which hinders the performance of the method. As far as the number of clusters in the base partitions is concerned, better results are generally obtained in Cases 2 and 3, i.e., with a larger number of clusters.

Conclusion

We have presented a method for combining clusterings in the DS framework. Each base clustering is assumed to take the form of a credal partition, in which the clustering membership of each object is allowed to be uncertain and represented by a mass function. This very general formalism encompasses hard, fuzzy and rough partitions as special cases [START_REF] Denoeux | Beyond fuzzy, possibilistic and rough: An investigation of belief functions in clustering[END_REF]. Credal partitions of special forms can be generated by hard, fuzzy or rough clustering algorithms, and general credal partitions can be obtained by evidential clustering procedures such a EVCLUS [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], BPEC [START_REF] Su | BPEC: Belief-peaks evidential clustering[END_REF], CCM [START_REF] Liu | Credal c-means clustering method based on belief functions[END_REF], etc.

Base credal partitions cannot be combined directly, because there is not always a clear correspondence between clusters in different partitions; in particular, base credal partitions can have different numbers of clusters. To circumvent this difficulty, we proposed to convert each base credal partition to its relational representation, defined as the collection of pairwise mass functions describing the uncertain joint cluster-membership for each pair of objects. After the normalized relational representations have been computed, they can be aggregated using any combination rule of DS theory. The best results have been obtained with the averaging operator.

Using the similarity between relational representations and intuitionistic fuzzy relations studied in [START_REF] Li | The structures of intuitionistic fuzzy equivalence relations[END_REF], we have proposed a way to transitivize the combined relational representation by computing the transitive closures of two fuzzy relations, based on a t-norm. Our experimental results suggest that the minimum t-norm often yields the best results, especially for datasets with complex-shaped clusters. However, making the relational representation transitive does not always improve the results, and may even degrade them in the case of datasets with many spherical clusters.

After the combined relational representation has been computed, the last step of our method consists in constructing a credal partition whose relational representation is as close as possible to the combined relational representation obtained in the previous step. We have proposed an error measure based on Jousselme's metric, which can be minimized using a grouped coordinate descent algorithm that solves a convex quadratic optimization problem at each step. After a normalized credal partition has been obtained, we "denormalize" it by assigning to the empty set the average of the masses assigned to the empty set by the base partitions, which provide useful information to signal outliers.

We have applied this method to a variety of simulated and real datasets. It has been shown to perform well in terms of adjusted Rand index as compared to the EAC method and to the ECM algorithm alone. It should also be emphasized that, in contrast with EAC and most existing ensemble clustering methods, our approach computes a credal partition, which constitutes a richer description of the clustering structure of a dataset, as compared to hard or fuzzy partitions.

Although very encouraging, these results are still preliminary. The determination of the number of clusters remains a crucial issue that remains to be thoroughly investigated. The application of this approach to very big datasets with a large number of clusters still represents a challenge. Finally, we could apply this approach not only to combine credal partitions, but also to combine all kinds of partitions generated by all kinds of clustering algorithms. These research directions will be investigated in future work.

  where m b * i is the normalized mass function defined by m b * i (∅) = 0 and

Figure 1 :

 1 Figure 1: Results for the Fourclass data with different combination rules: original data (a), one of the base partitions (b), average rule (c), Dempster's rule (d), disjunctive rule (e), DP rule (f).

Figure 2 :

 2 Figure 2: Results for Halfrings data: original data (a), one of base partitions (b), and recovered partition from transitive closures the minimum (c), Lukasiewicz (d) and product (e) t-norms, as well as without transitivity (f).

Figure 3 :

 3 Figure 3: Simulated datasets: Aggregation (a), Compound (b), Flame (c), Spiral (d) and R15 (e).

Table 3 :

 3 Average ARI results for simulated and real datasets. The best results are shown in bold. 68(0.05) 0.81(0.06) 0.83(0.08) 0.73(0(0.07) 0.98(0.01) 0.98(0.01) 0.73(0.04) 0.71(0.05) 0.81(0.08) 0.77(0.06) 0.74(0.03) 0.73(0.04) Compound case 1 0.53(0.09) 0.65(0.09) 0.78(0.02) 0.72(0(0.01) 0.73(0.1) 0.88(0.05) 0.41(0(0.14) 0.92(0.01) 0.92(0.01) 0.79(0.05) 0.79(0(0.33) 0.93(0.04) 0.93(0.04) 0.82(0.03) 0.82(0.03) case 3 -0.01(0.06) 0.92(0.01) 0.92(0.01) 0.47(0(0.02) 0.78(0.02) 0.75(0.01) 0.75(0.02) 0.78(0.02) 0.77(0(0.23) 0.83(0.05) 0.83(0.05) 0.58(0

  The mass m(Ω) is a measure of ignorance. A mass function is said to be logical if it has only one focal set. It is said to be normalized if the empty set is not a focal set, and unnormalized otherwise. An unnormalized mass function m can be converted into a normalized one m

* by Dempster's normalization operation defined by m * (∅) = 0 and

Table 1 :

 1 Datasets used in the experiments.

	Dataset	Number of objects Number of clusters Number of attributes
	Aggregation	788	7	2
	Compound	399	6	2
	Flame	240	2	2
	Spiral	312	3	2
	R15	600	15	2
	Iris	150	3	4
	Seeds	210	3	7
	Wine	178	3	13
	Ecoli	307	4	5

Table 2 :

 2 Number of clusters in base partitionsWe averaged the relational representations, and we computed the transitive closure operations with the minimum, product and Lukasiewicz t-norms. We also included the solution without transitivity for comparison. The true number of clusters was assumed to be known; in practice, this number can often be guessed using, e.g., visualization techniques. When recovering the combined credal partition, we first used only singletons and Ω as focal sets (denoted by "simple" in the table), and then we included informative pairs informative pairs (denoted by "pairs" in the table) as explained in Section 4.1. The ensemble size was N = 20. The procedure was run 10 times for each experiment. The average ARI values are shown in Table3, and the standard deviations are shown in parentheses.

	Dataset	Case 1 Case 2 Case 3
	Aggregation	10	[10,20]	20
	Compound	10	[10,20]	20
	Flame	8	[8,15]	15
	Spiral	30	[30,40]	40
	R15	20	[20,30]	30
	Iris	8	[8,15]	15
	Seeds	5	[5,10]	10
	Wine	5	[5,10]	10
	Ecoli	8	[8,15]	15
	(case 3).

Available at http://cs.joensuu.fi/sipu/datasets/.

Available at http://archive.ics.uci.edu/ml.

$ This research was supported by grant No.11571024 from NSFC, and by the Overseas Talent program from the Beijing Government.

 19) while e t ≥ do t ← t + 1 S t ← 0 for i = 1 to n do Compute A j for all j = i using [START_REF] Li | Multigranulation information fusion: A Dempster-Shafer evidence theory-based clustering ensemble method[END_REF] Compute Σ, u and c using (28) Find m * (t) i by minimizing [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF]

i , i = 1, . . . , n Denormalize the combined credal partition using [START_REF] Peters | Soft clustering: fuzzy and rough approaches and their extensions and derivatives[END_REF] return Credal partition M