Marie-Hélène Masson

Thierry Denoeux

Ensemble clustering in the belief functions framework

Keywords: Clustering, ensemble clustering, belief functions, lattice of partitions, intervals of partitions

Ensemble clustering in the belief functions framework

Introduction

Ensemble clustering methods [START_REF] Hornik | Ensemble methods for cluster analysis[END_REF][START_REF] Fred | Cluster Ensemble Methods: from Single Clusterings to Combined Solutions[END_REF][START_REF] Hadjitodorov | Moderate diversity for better cluster ensemble[END_REF] consist in combining multiple clustering solutions into a single one, called the consensus. The aim is to produce a more accurate and robust clustering of the data. Over several years a number of studies have been published on this topic 1 . The recent interest of the machine learning and artificial intelligence communities in ensemble techniques for clustering can be explained by the success of such ensemble techniques in a supervised setting. Moreover, some recent practical applications have shown the utility of such an approach in different contexts such as, e.g. in medical diagnosis [START_REF] Fern | Solving cluster ensemble problems by bipartite graph partitioning[END_REF][START_REF] Greene | Ensemble clustering in medical diagnostics[END_REF], gene expression microarray data clustering [START_REF] Monti | Consensus clustering: a resampling-based method for class discovery and visualization of gene expression microarray data[END_REF][START_REF] Avogadri | Fuzzy ensemble clustering for DNA microarray data analysis[END_REF], image segmentation [START_REF] Singh | Ensemble Clustering using Semidefinite Programming[END_REF]. Fundamental issues to be addressed when using ensemble clustering methods include: i) how to construct a set of individual solutions (or how to choose the base "clusterers"); and ii) how to combine the results of the ensemble into a single one.

This paper focuses on the second issue. Recent approaches to the problem of aggregating multiple clusterings include: voting schemes [START_REF] Dimitriadou | Voting-Merging: an ensemble method for clustering[END_REF][START_REF] Dudoit | Bagging to improve the accuracy of a clustering procedure[END_REF], graph-based approaches [START_REF] Strehl | Cluster ensemble -a knowledge reuse framework for combining multiple partitions[END_REF][START_REF] Fern | Solving cluster ensemble problems by bipartite graph partitioning[END_REF], parameters estimation in a mixture of multinomial distributions [START_REF] Topchy | A mixture model for clustering ensembles[END_REF], evidence accumulation clustering (EAC) [START_REF] Fred | Data clustering using evidence accumulation[END_REF][START_REF] Fred | Combining multiple clustering using evidence accumulation[END_REF][START_REF] Greene | Ensemble clustering in medical diagnostics[END_REF]. This last approach is one of the most popular and will be shown to have some connections with the method proposed in this paper. In EAC, the collection of partitions is mapped onto a square co-association matrix where each cell (i, j) represents the fraction of times the pair of objects (x i , x j ) has been assigned to the same cluster. This matrix is then considered as a similarity matrix which can in turn be clustered. A hierarchical clustering algorithm is often used for this purpose.

In this paper, which is an extension of [START_REF] Masson | Belief Functions and Cluster Ensembles[END_REF], we address the problem of finding a consensus clustering as an information fusion problem in the general framework of uncertain reasoning. In fact, each clustering algorithm can be considered as a source, partially reliable, providing an opinion about the true, unknown, partition of the objects. The reliability of each source is assumed to be described by a confidence degree, either assessed by an external agent or evaluated using internal indices. An important point to consider is that, in some cases, the output of a clusterer does not provide evidence in favor of a single partition but supports naturally a set of possible hypotheses. This situation can occur in various circumstances, depending on the way the ensemble is generated, for example:

1. Distributed clustering: in that case, it is assumed that the whole data set is not available in a centralized location. Each clusterer has only a partial view (of small dimension) of the data and the combination is performed in a central location using only high level information such as cluster labels [START_REF] Strehl | Cluster ensemble -a knowledge reuse framework for combining multiple partitions[END_REF]. 2. Random subspaces, random hyperplanes: for clustering high-dimensional data, some authors [START_REF] Fern | Random projection for high dimensional data clustering: A cluster ensemble approach[END_REF][START_REF] Avogadri | Fuzzy ensemble clustering for DNA microarray data analysis[END_REF] have proposed to generate their ensemble by randomly projecting the data on several low dimensional spaces. A similar approach is considered by Topchy et al. [START_REF] Topchy | Clustering Ensembles: Models of Consensus and Weak Partitions[END_REF] who propose to combine multiple weak clusterings obtained by splitting the data by random hyperplanes. 3. Complex shape clusters: one way to generate a cluster ensemble is to split the data into a large number of small clusters [START_REF] Fred | Data clustering using evidence accumulation[END_REF]; different decompositions can be obtained by using different clustering algorithms or the same algorithm while varying a characteristic of the method (starting values, number of clusters, hyperparameter, order of presentation of the samples for on-line algorithms). The search for a partition compatible with all individual clusterings is a way to detect complex shape clusters.

In the first two cases, if a small number c of clusters is discovered in a given subspace, it seems natural to consider that the true number of clusters in the whole space is at least c. In other words, the information provided by each clusterer can be expressed as the set of all partitions that are at least as fine as the output of the clusterers. The third case correspond to the opposite situation: multiple clusterings of this type may be reconciled by assuming that the true unknown partition belongs to sets of partitions coarser than the individual ones.

There is thus a need to represent and manipulate information expressed as sets of partitions, possibly associated to confidence degrees. In this context, belief functions, a theory which has been successfully applied to many fusion and pattern recognition problems in recent years (sensors fusion, expert opinion pooling, classification), appear as a suitable framework for representing and combining the opinion of several clusterers. In this framework, a straightforward approach would be to consider, as the set of possible hypotheses (the frame of discernment), the set P of all possible partitions of the set to be clustered. Unfortunately, this approach requires algebraic manipulation of the elements of 2 P and this can be intractable in the case where the number of partitions is high.

However, it is possible to work with a particular class of subsets of 2 P (intervals of partitions), which will be shown to have a lattice structure. Some recent works ( [START_REF] Grabisch | Belief functions on lattices[END_REF], [START_REF] Barthélémy | Monotone functions on finite lattices: an ordinal approach to capacities, belief and necessity functions[END_REF]) have shown the possibility of defining and manipulating belief functions on any lattice. The use of a lattice structure allows us to dramatically limit the complexity when allocating belief masses to sets of partitions.

The rest of the paper is organized as follows. Section 2 gives the necessary background about lattices and belief functions. Section 3 focuses on partition lattices. Our approach is developed in Section 4. Some experimental results are presented in section 5. Finally, Section 6 concludes this paper.

Belief functions on general lattices

Lattices have recently attracted a great interest due to their high number of potential applications in computer science (databases, data mining, distributed computing, scheduling applications). This section begins with a short introduction to lattices. Section 2.2 gives the necessary background on belief functions which are classically defined on a Boolean lattice. Then the extension of belief functions to general lattices is presented.

Lattices

The following presentation follows [START_REF] Grabisch | Belief functions on lattices[END_REF]. Only the main definitions will be recalled. A more complete description on lattice theory can be found in [START_REF] Montjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF].

A poset is a set P endowed with a partial order (a reflexive, antisymmetric, transitive relation). A lattice is a poset (P , ) such that for any x, y ∈ P , their least upper bound x ∨ y and their greatest lower bound x ∧ y exist. The element x ∨ y, is called the supremum or join of x and y and x ∧ y is called the infimum or meet of x and y. For finite lattices, there exist a greatest element, denoted ⊤, and a least element, denoted ⊥. We say that y covers x if x y and there is no z such that x z y. An element x is an atom if it covers only one element and this element is ⊥. It is a co-atom if it is covered by a single element and this element is ⊤.

A lattice is distributive if (x∨y)∧z = (x∧z)∨(y ∧z) holds for all x, y, z ∈ P . A lattice (P, ) is said to be complemented if any x ∈ P has a complement x ′ defined by x ∧ x ′ = ⊥ and x ∨ x ′ = ⊤. A lattice is Boolean if it is distributed and complemented. For any set Ω, the collection of all subsets of Ω, 2 Ω , ordered via subset inclusion, forms a lattice under the operations ∨ = ∪ (set union) and ∧ = ∩ (set intersection).

Belief functions on a Boolean lattice

Dempster-Shafer theory of evidence (or belief functions theory) [START_REF] Shafer | A mathematical theory of evidence[END_REF], like probability or possibility theories, is a theoretical framework for reasoning with partial and unreliable information. In this section, only the main concepts of this theory are recalled.

Let us consider a variable ω taking values in a finite set Ω called the frame of discernment. Partial knowledge regarding the actual value taken by ω can be represented by a basic belief assignment (bba) [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF], defined as a function m from 2 Ω to [0, 1], verifying:

A⊆Ω m(A) = 1.
(

) 1
The subsets A of Ω such that m(A) > 0 are the focal elements of m. Each focal set A is a set of possible values for ω, and the quantity m(A) can be interpreted as the measure of the belief that is committed exactly to ω ∈ A on the basis of a given evidential corpus. Complete ignorance corresponds to m(Ω) = 1 (vacuous mass function), whereas perfect knowledge of the value of ω is represented by the allocation of the whole mass of belief to a unique singleton of Ω (m is then called a certain bba). A bba with nested focal elements is said to be consonant. A bba m is said to be of simple support if there exists A ⊂ Ω and w ∈ [0, 1] such that m(A) = 1w and m(Ω) = w, all other masses being equal to zero. A bba m such that m(∅) = 0 is said to be normal. The bba m can be equivalently represented by a credibility function bel, a plausibility function pl, and a commonality function q defined, respectively, by: bel(A)

∅ =B⊆A m(B) ∀A ⊆ Ω , (2)
pl(A)

B∩A =∅ m(B) ∀A ⊆ Ω , (3) q
(A) B⊇A m(B) ∀A ⊆ Ω . (4)
When the reliability of a source is doubtful, the mass provided by this source can be discounted using the following operation (discounting process):

m α (A) = (1 -α)m(A) ∀A = Ω, m α (Ω) = (1 -α)m(Ω) + α, (5)
where 0 ≤ α ≤ 1 is the discount rate. This discount rate is related to the confidence held by an external agent in the reliability of the source [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. It can be interpreted as the plausibility that the source is unreliable. When α is equal to 1, the vacuous mass function is obtained. When α=0, m remains unchanged.

Two bbas m 1 and m 2 induced by distinct items of evidence on Ω can be combined using the conjunctive rule of combination. The resulting mass function m 1 ∩ m 2 is defined by:

(m 1 ∩ m 2 )(A) B∩C=A m 1 (B)m 2 (C) ∀A ⊆ Ω. ( 6
)
This conjunctive rule transfers the product of the masses m 1 (B) and m 2 (C) to the intersection of B and C. It can be expressed in a simple way using commonalities:

(q 1 ∩ q 2 )(A) = q 1 (A)q 2 (A) ∀A ⊆ Ω, (7)
where q 1 (A) and q 2 (A) denote, respectively, the commonalities associated to m 1 and m 2 .

Extension to general lattices

As recalled in the previous section, belief functions are classically defined on the Boolean lattice 2 Ω . However, following initial investigations of Barthélemy [START_REF] Barthélémy | Monotone functions on finite lattices: an ordinal approach to capacities, belief and necessity functions[END_REF], Grabisch [START_REF] Grabisch | Belief functions on lattices[END_REF] has shown that it is possible to extend these notions to the case where the underlying structure is no more a Boolean lattice, but any lattice: most results from Dempster-Shafer theory transfer to this general setting. Let (P, ) denote a lattice endowed with a ∨-meet and a ∧-join operations. A basic belief assignment (bba) is defined as a mass function m from P to [0,1] verifying:

x∈P m(x) = 1. (8)
The bba m can be equivalently represented by a credibility function bel, and a plausibility function q defined, respectively, by: bel(x)

x ′ x m(x ′ ) ∀x ∈ P, (9)
pl(x)

x∧x ′ =⊥ m(x ′ ) ∀x ∈ P. (10)
The conjunctive rule of combination is rewritten as:

(m 1 ∩ m 2 )(x) = x ′ ∧x ′′ =x m 1 (x ′ )m 2 (x ′′ ) ∀x ∈ P, (11)
with the following relation between the commonalities:

(q 1 ∩ q 2 )(x) = q 1 (x)q 2 (x) ∀x ∈ P. ( 12
)

Lattices of partitions

In this section, we focus on a particular lattice structure on which belief functions may be defined: the lattice of partitions of a finite set. We first recall basic definitions about partitions and orders on partitions. The section ends with the presentation of another lattice derived from the previous one. This lattice, which seems particularly suitable in the context of consensus clustering, is composed of intervals of partitions. This makes it possible to manipulate sets of partitions with an acceptable level of complexity.

Partitions of a Finite Set

Let E denote a finite set of n objects. A partition p is a set of non empty subsets E 1 ,...,E k of E such that:

1) the union of all elements of p, called clusters, is equal to E; 2) the elements of p are pairwise disjoint.

Every partition p can be associated to an equivalence relation (i.e., a reflexive, symmetric, and transitive binary relation), on E, denoted by R p , and characterized, for all (x, y) ∈ E 2 , by: R p (x, y) = 1 if x and y belong to the same cluster in p, 0 otherwise.

Example. Let E = {1, 2, 3, 4, 5}. A partition p of E, composed of two clusters {1, 2, 3} and {4, 5} will be denoted as p = (123/45). The associated equivalence relation is:

R p =       1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 1      
.

The set of all partitions of E, denoted by P E , can be partially ordered using the following ordering relation: a partition p is said to be finer than a partition p ′ on the same set E (or, equivalently p ′ is coarser than p) if the clusters of p can be obtained by splitting those of p ′ (or equivalently, if each cluster of p ′ is the union of some clusters of p). In, this case, we write:

p p ′ .
This partial ordering can be alternatively defined using the equivalence relations associated to p and p ′ :

p p ′ ⇔ R p (x, y) ≤ R p ′ (x, y) ∀(x, y) ∈ E 2 .
The notation will be used for the reverse relation defined by:

p ′ p ⇔ p p ′ ,
and that ≺, and ≻ will denote the restrictions of and , respectively, to pairs of distinct elements:

p ≺ p ′ ⇔ p p ′ and p = p ′ , p ≻ p ′ ⇔ p p ′ and p = p ′ .
The finest partition (⊥) in the order (P E , ), denoted p 0 = (1/2/.../n), is the partition in which each object is a cluster. The coarsest partition (⊤) is p E = (123..n), in which all objects are put in the same cluster. Each partition precedes in this order every partition derived from it by aggregating two of its clusters. Similarly, each partition succeeds (covers) all partitions derived by subdividing one of its clusters in two clusters. The atoms of (P E , ) are the partitions preceded by p 0 . There are n(n-1)/2 such partitions, each one having (n -1) clusters with one and only one cluster composed of two objects. Atoms are associated with matrices R p with only one off-diagonal entry equal to 1.

Lattice of Partitions

The set P E endowed with the -order has a lattice structure [START_REF] Montjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF]. Meet (∧) and join (∨) operations can be defined as follows. The partition p ∧ p ′ , the infimum of p and p ′ , is defined as the coarsest partition among all partitions finer than p and p ′ . The clusters of p ∧ p ′ are obtained by considering pairwise intersections between clusters of p and p ′ . The equivalence relation R p∧p ′ is simply obtained by taking the minimum of R p and R p ′ . The partition p ∨ p ′ , the supremum of p and p ′ , is similarly defined as the finest partition among the ones that are coarser than p and p ′ . The equivalence relation R p∨p ′ is given by the transitive closure of the maximum of R p and R p ′ . Figures 1 and2 show examples of partition lattices in the case where E is composed of three and four objects.

Lattices of intervals of partitions

To enable the manipulation of sets of partitions, the previous framework has to be further extended in the following way. In P E , a closed interval of lattice elements is defined as: An interval [p, p] in P E is thus a particular set of partitions, namely the set of all partitions finer than p and coarser than p.

[p, p] = {p ∈ P E | p p p}. ( 13
)
1/2/3
We consider now the set I E of all intervals of P E , including the empty set of P E (denoted by ∅ PE ). The intersection of two intervals is also an interval:

[p 1 , p 1 ] ∩ [p 2 , p 2 ] = [p 1 ∨ p 2 , p 1 ∧ p 2 ], if p 1 ∨ p 2 p 1 ∧ p 2 ∅ PE otherwise . (14)
So the set I E is a closure system and, as shown by [START_REF] Montjardet | The presence of lattice theory in discrete problems of mathematical social sciences[END_REF], is also a lattice, endowed with the inclusion relation:

[p 1 , p 1 ] ⊆ [p 2 , p 2 ] ⇔ p 2 p 1 and p 1 p 2 . ( 15
)
The meet operation is the intersection and the join of two elements [p 1 , p 1 ] and [p 2 , p 2 ] in I E is defined as:

[p 1 , p 1 ] ⊔ [p 2 , p 2 ] = [p 1 ∧ p 2 , p 1 ∨ p 2 ]. (16)
Note that the meet of two intervals corresponds exactly to the intersection of the corresponding sets of partitions, whereas the join of two intervals may be larger than the union of the sets of partitions. In this lattice, the least element ⊥ IE is ∅ PE and the greatest element ⊤ IE is P E . The atoms of I E are the singletons of P E . The co-atoms are of the form [p 0 , p] with p a co-atom of (P E , ) or [p, p E ] with p an atom of (P E , ). An example of such a lattice, in the case where E is composed of three objects, is shown in Figure 3.

Within this framework, several kinds of imprecise knowledge about a partition can be expressed. For example, the intervals [p 0 , p] and [p, p E ] represent the set of partitions finer and coarser, respectively, than a partition p. Suppose now that we know that the elements of a set A ⊆ E are in the the same cluster. This external information is referred to as "must-link" constraints (see e.g. [START_REF] Wagstaff | Constrained kmeans clustering with background knowledge[END_REF]) between the elements of A and can be translated as an interval of I E as follows. Let p A denote the partition in which the only elements which are clustered together are the elements of A:

p A = {A} ∪ {x}/x ∈ Ā .
Then the interval [p A , p E ] represents the set of all partitions in which the elements of A are clustered together. Note that "cannot link" constraints also used in constrained clustering, which specify that elements must not be clustered in the same class, can not be expressed in the proposed framework.

= [1/2/3,123] P E P E {1/2/3} {12/3} {13/2} {23/1} {123} [1/2/3,12/3] [1/2/3,23/1] [13/2,123] [23/1,123] [1/2/3,13/2] [12/3,123]

Ensemble Clustering with partitions lattices

Belief functions defined on lattices of intervals of partitions, as introduced in the previous sections, offer a general framework for combining and synthesizing the results of several clustering algorithms. Note that an approach using the lattice of partitions (and not lattices of intervals of partitions, as it is proposed in this paper) for finding a consensus partition has been already suggested in the 80's by by Neumann and Norton [START_REF] Neumann | On lattice consensus methods[END_REF]. Their approach works well for ensembles with little diversity. In case of strong conflicting opinions of the clusterers, their way of deriving a strict consensus, using meet and join operations on the lattice, can lead to very non informative results (the most trivial result is obtained when the meet is the set of singletons and the join is the partition with one cluster). This poor behavior is partly explained by the fact that, in this theoretical setting, the outputs of the clusterers are categorical opinions which are pooled together without the possibility of weighting them using mass functions.

We propose to use the following strategy for ensemble clustering:

1) Mass generation: Given r clusterers, build a collection of r bbas m 1 ,m 2 ,...,m r on the lattice of intervals; 2) Aggregation: Combine the r bbas into a single one using the conjunctive rule of combination; 3) Synthesis: Provide a summary of the results.

These steps are discussed in detail below.

Basic belief assignment

A credal clustering ensemble is a collection of r bbas C = {m 1 , ..., m r }. The way of choosing the focal elements and allocating the masses from the results of several clusterers depends mainly on the applicative context and on the nature of the clusterers in the ensemble. Two representative examples are given below.

The simplest situation is encountered when a given clusterer l produces a single partition p l of the data set (using for example the hard or fuzzy cmeans algorithm). To account for the uncertainty of the clustering process, this categorical opinion can be transformed into a simple support mass function using the discounting operation [START_REF] Davies | A cluster separation measure[END_REF]. Let α l denote the discounting factor of clusterer l (note that it is proposed in the experimental section to relate α l to to an internal indice of validity of the partition). If the true unknown partition is considered to be at least as fine as p l , the following mass allocation can be used:

m l1 = m l ([p 0 , p l ]) = 1 -α l m l2 = m l ([p 0 , p E ]) = α l . ( 17
)
On the contrary, if the true unknown partition is considered to be at least as coarse as the individual partition, then the following allocation may be considered:

m l1 = m l ([p l , p E ]) = 1 -α l m l2 = m l ([p 0 , p E ]) = α l . (18)
Note that only two mass allocations are presented in this paper because they correspond to the practical cases mentioned in the introduction like complex shape clustering or random subspace clustering, but many other clustering methods could be described in the same framework. For instance, fuzzy equivalence relations, used for cluster analysis [START_REF] Bezdek | Fuzzy Models and Algorithms for Pattern Recognition and Image Processing, Series: The Handbooks of Fuzzy Sets[END_REF], or hierarchical clusterings, could be naturally represented by belief functions on the lattice of intervals of partitions.

The result of this mass allocation step is a collection of r bbas m l which are defined, in the most general case, as a set of n l focal elements [p l s , p l s ] with a mass m l s = m l ([p l s , p l s ]) (s = 1, ..., n l ):

m l = {([p l s , p l s ], m l s ), s = 1, n l }
The equivalence relations associated to p l s and p l s will be denoted R l s and R l s , respectively.

Two particular cases of ensembles will be of interest in the sequel. Type I ensembles will refer to ensembles composed exclusively of bbas m l of the form:

m l = {([p 0 , p l s ], m l s ), s = 1
, n l }, whereas type II ensembles will refer to ensembles composed of bbas m l of the form:

m l = {([p l s , p E ], m l s ), s = 1, n l }.

Combination

Once the results provided by the r clusterers have been converted into r bbas, they can be aggregated into a single bba m * = m 1 ∩ m 2 ∩ ... ∩ m r using the conjunctive rule of combination [START_REF] Dunn | Well separated clusters and optimal fuzzy partitions[END_REF] with the meet operation defined by [START_REF] Fred | Data clustering using evidence accumulation[END_REF]. The combination algorithm is summarized in appendix (algorithms 1 to 3).

The result of this combination is a bba m * , i.e. a set of K intervals, associated with belief masses:

m * = {([p * k , p * k ], m * k ) k = 1, K}.
The associated equivalence relations of p * k and p * k will be denoted R * k and R * k , respectively, in the sequel. Similarly, the credibility and plausibility functions related to m * will be denoted bel * and pl * , respectively.

Synthesizing the results

The interpretation of the results is a difficult problem, since, depending on the number of clusterers in the ensemble, on their nature, on the conflict between them, and on the combination rule, a potentially high number K of focal elements may be found. If the number of focal elements in the combined bba is too high to be explored, a first way to proceed is to select only the focal elements associated with the highest masses. We propose also another approach which is explained below.

Let p ij denote the partition with (n -1) clusters, in which the only objects which are clustered together are objects i and j (partition p ij is an atom in the lattice (P E , )). Then, the interval [p ij , p E ] represents the set of all partitions in which objects i and j are put in the same cluster. Our belief in the fact that i and j belongs to the same cluster can be characterized by two quantities, namely, the plausibility and the credibility of [p ij , p E ]. They can be simply computed as follows:

P l ij = pl * ([p ij , p E ]) = [pij ,pE ]∩[p * k ,p * k ] =∅ P E m * k (19) = p * k pij m * k (20) = K k=1 m * k R * k (i, j), (21)
Bel ij = bel * ([p ij , p E ]) = [p * k ,p * k ]⊆[pij ,pE ] m * k (22) = p * k pij m * k (23) = K k=1 m * k R * k (i, j). (24)
Note that, in case of a type I ensemble, the meet of any two focal elements [p 0 , p l s ] and [p 0 , p l ′ s ′ ] is equal to [p 0 , p l s ∧ p l ′ s ′ ] so the combined bba m * is such that:

p * k = p 0 ∀k = 1, K.
In that case, one has:

Bel ij = bel * ([p ij , p E ]) = K k=1 m * k R 0 (i, j) = 0, ∀i = j,
where R 0 denotes the equivalence relation associated to p 0 . In case of a type II ensemble, the meet of any two focal elements [p l s , p E ] and [p l ′ s ′ , p E ] is equal to [p l s ∨ p l ′ s ′ ; p E ] so the combined bba m * is such that:

p * k = p E ∀k = 1, K.
In that case, one has:

P l ij = pl * ([p ij , p E ]) = K k=1 m * k R E (i, j) = 1, ∀i = j,
where R E denotes the equivalence relation associated to p E . Matrices P l = (P l ij ) and Bel = (Bel ij ) can be considered as new similarity matrices and can be in turn clustered using, for instance, a hierarchical clustering algorithm. If a partition is needed, the classification tree can be cut at a specified level or so as to insure a user-defined number of clusters.

Special case of type I ensembles

In case of type I ensembles, the computation of P l ij can be further simplified. In fact, the particular shape of the focal elements of m * allows us to write P l ij as:

P l ij = pl * ([p ij , p E ]) = q * ([p 0 , p ij ]), (25)
where q * denotes the commonality function associated to m * . As it is recalled in Section 2.3 in Eq. ( 12), q * can be expressed as the product of the commonalities q 1 ,• • • ,q r associated to m 1 ,• • • ,m r , respectively:

P l ij = r l=1 q l ([p 0 , p ij ]). ( 26
)
We have:

q l ([p 0 ; p ij ]) = p l s pij m l s = n l s=1 m l s R l s (i, j). (27)
Thus:

ln P l ij = r l=1 ln n l s=1 m l s R l s (i, j) . (28)
Equation [START_REF] Monti | Consensus clustering: a resampling-based method for class discovery and visualization of gene expression microarray data[END_REF] shows that, in case of type I ensembles, it is not necessary to compute the result of the conjunctive rule of combination, because each P l ij can be simply computed from the initial bbas of the ensemble.

Link with the EAC approach

We assume in this section that the ensemble is of type I and that all bbas m l are simple mass functions obtained by discounting categorical opinions given by the clusterers. We further assume that the discount factor is equal to α for all clusterers, so that:

m l = {([p 0 , p l ], 1 -α), ([p 0 , p E ], α)}.
In that case, the following equations hold:

q l ([p 0 , p ij ]) = 1 if p l p ij 1 -α if p l ≺ p ij , (29)
and

P l ij = {l/p l pij } 1 {l ′ /p l ′ ≺pij } (1 -α) = (1 -α)    r - r l=1 R l (i, j)   
, or, equivalently:

ln P l ij = r - r l=1 R l (i, j) ln(1 -α). ( 30
)
One can see that ln P l ij is an increasing function of the fraction of times where i and j have been assigned to the same cluster by the individual clusterers. Consequently, clustering matrices P l or 1 r l R l using the single or complete linkage hierarchical clustering algorithm will yield the same results. This particular case is thus equivalent to the evidence accumulation approach. A weighted version of EAC, that weights differently the partitions in the co-association matrix, has also been proposed in [START_REF] Duarte | Weighted evidence accumulation clustering[END_REF]. It turns out that it is equivalent to our approach when each clusterer has its own discount rate α l , as it can easily be shown that:

ln P l ij = r l=1 ln(1 -α l ) 1 -R l (i, j) .
(31)

Toy example

Let E = {1, 2, 3, 4, 5, 6, 7} be a set of 7 objects. We assume that two clustering algorithms have produced partitions p 1 = (123/45/67) and p 2 = (12/345/67). As it can be seen, the partitions disagree on the third element which is clustered with {1, 2} in p 1 and with {4, 5} in p 2 . As proposed in Section 4, we construct two simple mass functions by discounting each clusterer l by a factor α l . In a first situation, we consider that we have an equal confidence in the two clusterers, so we fix α 1 = α 2 = 0.1. Moreover, we assume that the unknown partition is finer than p 1 and p 2 (type I assignment). We have:

m 1 ([p 0 , p 1 ]) = m 2 ([p 0 , p 2 ]) = 0.9, m 1 ([p 0 , p E ]) = m 2 ([p 0 , p E ]) = 0.1.
Applying Dempster's rule of combination [START_REF] Dunn | Well separated clusters and optimal fuzzy partitions[END_REF] Suppose now that the confidence in the second clusterer is less than in the first one. Two situations are considered: we first fix α 1 = 0.1 and α 2 = 0.5 and then α 1 = 0.1 and α 2 = 0.9. The corresponding matrices P l and Bel are represented in the middle and lower parts of Figure 4. As expected, the more the opinion of the second clusterer is discounted, the closer the combined partitions, whatever their type, to the partition given by the first clusterer.

Bel (type II ensemble) m 1 =m 2 =0.9

Some examples of applications

5.1. Preamble: discount rates When a mass allocation such as [START_REF] Grabisch | Belief functions on lattices[END_REF] or ( 18) is used, fixing the discount rates α l is a major issue. Each discounting factor has to reflect the confidence held in the clusterer. A way to automatically determine these factors is to relate them to a cluster validity index. The notion of cluster validation refers to concepts and methods for the quantitative evaluation of the output of a clustering algorithm.

Various cluster validity indices have been proposed to measure the quality of clustering results. They can be broadly divided into external and internal indices. External validity indices assess the agreement between a clustering solution and a predefined reference clustering. One of the most popular is the Rand Index [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF], which determines the similarity between two partitions as a function of positive and negative agreements in pairwise cluster assignments. The Adjusted Rand index [START_REF] Hubert | Comparing partitions[END_REF] (AR) introduces a normalization in order to yield values close to zero for random partitions. It is computed as follows. Let

• p 1 and p 2 be two partitions of a set E;

• a denote the number of pairs of elements in E that are in the same cluster in p 1 and in the same cluster in p 2 ;

• b denote the number of pairs of elements in E that are in different clusters in p 1 and in different clusters in p 2 ;

• c denote the number of pairs of elements in E that are in the same cluster in p 1 and in different clusters in p 2 ;

• d denote the number of pairs of elements in E that are in different clusters in p 1 and in the same cluster in p 1 .

The Adjusted Rand index, AR, is defined as:

ARI(p 1 , p 2 ) = 2(ab -cd) (a + d)(d + b) + (a + c)(c + b) . (32)
This index belongs to [-1,1] and is close to 1 when the two partitions are in good agreement. In real-life unsupervised tasks, there is no reference clustering, so that such criterion is not directly applicable for deriving a discounting factor. However, the Adjusted Rand index will be used in the experiments to evaluate the quality of the final clustering with respect to known labels (when they are known) and also in the definition of an internal validity criterion as explained below.

Internal validation methods compare different solutions based on the goodness of fit between each clustering and the data by using combined notions of compactness, separation, and connectedness of the clusters. Examples of such indices are Dunn's index [START_REF] Dunn | Well separated clusters and optimal fuzzy partitions[END_REF], the Davies-Bouldin index [START_REF] Davies | A cluster separation measure[END_REF], and the Silhouette score [START_REF] Rousseeuw | Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[END_REF]. However, these indices can only make comparisons between clusterings generated using the same metric. When, for example, a situation of distributed clustering is considered, these indices are not applicable. More recent approaches to the problem of cluster validation suggest to use the stability of a partitioning as an internal validation measure. In particular, we adopt the approach of [START_REF] Levine | Resampling method for unsupervised estimation of cluster validity[END_REF][START_REF] Ben-Hur | A stability based method for discovering structure in clustered data[END_REF] based on the idea that a clustering algorithm should produce consistent results when applied to data sampled from the same source. The general principle is to repeatedly draw two overlapping subsamples of the same dataset. Each subsample is clustered individually, and the two resulting partitions are compared by applying an external validation index (we use the AR index) to the partial partitions obtained for the overlapping shared set of points. The average of the AR index over several repetitions is retained as a stability index of the clusterer (note that the AR index has been truncated to zero considering that negative AR values were associated to bad agreements between partitions). The detailed algorithm for computing the stability index is given in appendix (algorithm 4). This stability index has been used in all the experiments reported below (with a number of bootstrap samples n boot = 30 and a sampling ration S = 0.9), by defining the discount rate of each clusterer as one minus the stability index.

Distributed clustering: first experiment

In a distributed computing environment, the data set is spread into a number of different sites. In that case, each clusterer has access to a limited number of features and the distributed computing entities share only higher level information describing the structure of the data such as cluster labels. The problem is to find a clustering compatible with what could be found if the whole set of features was considered. To illustrate this point, we used a dataset named 8D5K, described in [START_REF] Strehl | Cluster ensemble -a knowledge reuse framework for combining multiple partitions[END_REF]. This dataset is composed of five Gaussian clusters of 200 points in dimension 8. Three 2D views of the data were created by selecting three pairs of features for which a clear cluster structure appeared. The fuzzy c-means algorithm (FCM) was applied in each view after selecting by hand the number of desired clusters to obtain three hard partitions computed from the fuzzy partitions. These partitions are represented in Figure 5. The left column shows the partitions in the 2D views, and the right one shows the same partitions projected onto the first two principal components of the data. An ensemble of three mass functions of type I was constructed by considering that the true unknown partition is at least as fine as the individual ones: each clusterer, discounted according the stability of the partition, was represented by a mass function with two focal elements. A "consensus" clustering was obtained by applying the conjunctive rule of combination, computing the matrix ln(P l) and the associated tree using Ward linkage, and cutting the tree to obtain five clusters. The consensus clustering and the dendrogram are presented in Figure 6. It may be seen that a clear structure in five clusters is highlighted by the tree and that a very good clustering is obtained. The AR index between the true partition and the result of the ensemble is equal to 0.95.

Distributed clustering: second experiment

In this section, we illustrate the interest of the discounting process applied to the clusterers according to their stability. We used the same data set as in the previous section and we progressively added to the previous ensemble "noisy" clusterers (from one to nine additional clusterers). Each noisy clusterer was constructed by running the fuzzy c-means algorithm with new pairs of features and by randomly perturbing the labels of the points according to a given noise level (namely 0%, 25%, 50%, 75% and 100%). The results of the ensemble are judged using the Adjusted Rand index between the true partition and the partition into five clusters found by the ensemble. This experiment was repeated 50 times to report errors bars. Our method is compared to the EAC approach.

We can see in Figure 7 that the discount process allows our method to be remarkably stable. On the contrary, the performance of the EAC approach is highly variable and decreases when the number of noisy clusterers added in the ensemble grows.

Discovering non spherical clusters

This section is intended to show the ability of the proposed approach to detect clusters with complex shapes. Two experiments are presented. The first data set is the half-ring data set which is inspired from [START_REF] Fred | Data clustering using evidence accumulation[END_REF]. It consists of two clusters of 100 points each in a two-dimensional space. To build the ensemble, we used the fuzzy c-means algorithm with a varying number of clusters (from 6 to 11). The hard partitions computed from the soft partitions are represented in Figure 8. As in the previous example, each partition was discounted according to the stability index and six mass functions with two focal elements each were combined using the conjunctive rule of combination. The mass functions were chosen of type II since the true partition is supposed to be coarser than each individual one. A tree was computed from matrix Bel using Ward's linkage. This tree, represented in the left part of Figure 9, indicates a clear separation in two clusters. Cutting the tree to obtain two clusters gives the partition represented in the right part of Figure 9. We can see that the natural structure of the data is perfectly recovered. The second experiment was conducted with the Iris data set, which is a real data set composed of 3 classes of 50 points each in a four dimensional space. This data set is represented in Figure 10. An ensemble of 4 clusterers was constructed using the same approach as before: the fuzzy c-means algorithm was run with a varying number of clusters (8 to 11). The corresponding hard partitions were discounted according to the stability criterion and four mass functions of type II were built. These mass function were combined using the conjunctive rule of combination and matrix Bel was computed. The corresponding tree obtained using Ward's linkage, which shows a cut in 2 or 3 classes, is represented in the top left of Figure 12. The partition computed from this tree in three classes is shown in the top right of Figure 12. The adjusted Rand index is equal to 0.922.

As a matter of comparison, the tree computed using Ward's linkage from the co-association matrix of the EAC approach and the related partition into three classes are shown in the bottom of Figure 12. It may be seen from the figure that the EAC approach does not give a clear indication about the number of clusters to be chosen and that the partition does not reflect the natural structure of the data (note that the EAC approach and our approach are equivalent only in case of type I assignments). The co-association matrix and the Bel matrix are displayed in Figure 12. This representation confirms that the structure of the data is better described by matrix Bel.

We also give in Table 1 the averaged Adjusted Rand index and its standard deviation obtained over 100 repetitions of four methods: our method, the EAC approach, and a direct application of a hierarchical clustering (Ward's method) and FCM on the original features. Note that the variability of the results for the first two methods comes, on the one hand, from the variability of the results of FCM (which occurs when the number of clusters is high) and, one the other hand, from the resampling process in the computation of the validity indices.

Belief ens.

EAC approach

Hierarc. FCM (3 clusters) 0.8821 ± 0.11 0.6139 ± 0.07 0.7312 ± 0 0.7294 ± 0

Conclusion

We have proposed in this paper a new approach for aggregating multiple clusterings. This approach is based on the use of belief functions defined on a lattice of sets of partitions. Belief functions theory has been already successfully applied to unsupervised learning problems [START_REF] Hégarat-Mascle | Application of Dempster-Shafer Evidence Theory to Unsupervised Classification in Multisource Remote Sensing[END_REF][START_REF] Denoeux | EVCLUS: EVidential CLUStering of proximity data[END_REF][START_REF] Masson | Clustering interval-valued data using belief functions[END_REF][START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. In those methods, belief functions are defined on the set of possible clusters, the focal elements being subsets of this frame of discernment. The idea suggested here is radically different. Each clustering algorithm is considered as a source providing an opinion, potentially unreliable, about the unknown partition of the objects. The information of the different sources are converted into masses of evidence allocated to sets of partitions. These masses are then combined and synthesized using some generalizations of classical tools of the belief functions theory. A popular clustering ensemble approach, namely the EAC approach and its weighted version, are recovered as a special case of the method.

Several ways of defining the masses have been suggested in this paper. In particular, type I and type II masses appear as natural expressions of partial knowledge about an unknown partition. We have chosen to relate the masses to a stability index of the partition. This stability index has the advantage of being independent of the feature space and on the clusterer type. Experimental results have shown the ability of the method to recover correct partitions from partial information provided by simple clustering algorithms. Moreover, the robustness of the method against noisy clusterers has been demonstrated in one of the experiments. Algorithm 4 Validity Index Input: A data set X , a sampling ratio 0.7 ≤ S ≤ 0.9, a number n boot of bootstrap samples Output: C = Cluster Stability Index for i = 1 to n boot do Draw two bootstrap samples X 1 and X 2 from X with a sampling ratio S. p 1 : partition obtained from X 1 p 2 : partition obtained from X 2 I = X 1 ∩ X 1 S(i) ← max (0, AR(p 1 (I), p 2 (I))) end for

C ← 1 n boot n boot i=1 S(i)

Figure 1 :

 1 Figure 1: Lattice of partitions of a set of three elements.

Figure 3 :

 3 Figure 3: Lattice of intervals of partitions of a set composed of three elements.

Figure 4 .

 4 Logically, the type I assignment leads to a partition of the set into 4 clusters, whereas the type II assignment shows a structure into 2 clusters.

Figure 4 :

 4 Figure 4: Plausibility and belief matrices for the toy example (white=1, black=0).

Figure 5 :Figure 6 :

 56 Figure5: 8D5K data set[START_REF] Strehl | Cluster ensemble -a knowledge reuse framework for combining multiple partitions[END_REF]. The ensemble is composed of three individual clustering solutions obtained from three 2D views of the data. The left column shows the partition obtained in each two-dimensional features space and the right one shows the corresponding partition in the plane spanned by the two first principal components.

Figure 7 :

 7 Figure 7: 8D5K data set. Influence of noisy clusterers on the performances of the ensemble (squares: proposed method; circles: EAC approach).

2 Figure 8 :Figure 9 :

 289 Figure 8: Half-rings data set. Individual partitions.

Figure 10 :

 10 Figure 10: Iris data set. True partition in the plane spanned by the first two principal components.

Figure 11 :Figure 12 :

 1112 Figure 11: Iris data set. Top: Ward's linkage computed from Bel and derived consensus.Bottom: Ward's linkage using the EAC approach and derived consensus.

  leads to the following combined bba m * = m 1 ∩ m 2 : ∨ p 2 = (12345/67). The matrices P l and Bel computed from m * are represented in the upper part of

	Focal elements	mass m *	bel *
	[p 0 , p 1 ∧ p 2 ]	0.81	0.81
	[p 0 , p 1 ]	0.09	0.90
	[p 0 , p 2 ]	0.09	0.90
	[p 0 , p E ]	0.01	1
	with p 1 ∧ p 2 = (12/3/45/67).
	A type II assignment, corresponding to the hypothesis that the true partition
	is coarser than the individual ones leads to the following combined mass m * :
	Focal elements	mass m *	bel *
	[p 1 ∨ p 2 , p E ]	0.81	0.81
	[p 1 , p E ]	0.09	0.90
	[p 2 , p E ]	0.09	0.90
	[p 0 , p E ]	0.01	1
	with p 1

Table 1 :

 1 Iris data set. Adjusted Rand Index over 100 repetitions of four approaches.

see, for example, the special issue of the Journal of Classification devoted to the "Comparison and Consensus of Classifications" published in 1986[START_REF] Day | Foreword: Comparison and Consensus of Classifications[END_REF]

Appendix Algorithm 1 CombineEnsemble

Input:


Violaine Antoine

Benjamin Quost

Marie-Hélène Masson

Thierry Denoeux

CEVCLUS: Constrained evidential clustering of proximity data

Keywords: Semi-supervised clustering, pairwise constraints, belief functions, evidence theory, proximity data

We present an improved relational clustering method integrating prior information. This new algorithm, entitled CEVCLUS, is based on two concepts: evidential clustering and constraint-based clustering. Evidential clustering uses the Dempster-Shafer theory to assign a mass function to each object. It provides a credal partition, which subsumes the notions of crisp, fuzzy and possibilistic partitions. Constraint-based clustering consists in taking advantage of prior information. Such background knowledge is integrated as an additional term in the cost function. Experiments conducted on synthetic and real data demonstrate the interest of the method, even for unbalanced datasets or non-spherical classes.

Introduction

Unsupervised learning analysis refers to a large variety of methods that aim at grouping data into clusters [START_REF] Diday | Cluster analysis[END_REF]. These algorithms can be distinguished according to the type of input data used. The two most frequent data types are feature vectors in a Euclidean vector space and pairwise proximity measures. The ubiquity of pairwise proximity measures in empirical sciences such as biochemistry, linguistic, psychology and the possibility of feature vectors to be transformed into proximity data make clustering algorithms that can handle proximity data more general than those using feature vectors.

The degree of information provided by a clustering algorithm may be expressed with a crisp, fuzzy, possibilistic or credal partition. Given n objects to classify in c classes, a crisp partition aims at grouping each object in one cluster, whereas a fuzzy partition U classifies each object i to each cluster k with a degree of membership u ik ∈ [0 1] such that c i=1 u ik = 1 ∀i ∈ {1, . . . , n}.

(

A possibilistic partition expresses membership values as degrees of possibility. A credal partition, which extends the concepts of crisp, fuzzy and possibilistic partition, has been recently considered in [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF][START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF][START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF]. This is done by allocating, for each object, a mass of belief, not only to single clusters, but also to any subsets of the set of clusters Ω = {ω 1 , . . . , ω c }. The value m i (A) such that A ⊆ Ω corresponds then to the belief given to A (and to no more specific subset) regarding the actual cluster of the i th object. This formulation mainly enables gaining deeper insight into the structure of the data, and also improves the robustness of the algorithm with respect to outliers.

In some situations, extra-information about the data may be available or easy to collect. Making use of these can lead algorithms towards desired solutions. Such algorithms based on background knowledge are known as semi-supervised clustering algorithms. There exists many ways to exploit prior information, at different levels such as the model level [START_REF] Zhong | A unified framework for model-based clustering[END_REF][START_REF] Gondek | Non-redundant data clustering[END_REF], the cluster level [START_REF] Davidson | Agglomerative hierarchical clustering with constraints: Theoretical and empirical results[END_REF] or the instance level. This last level mainly includes small sets of labelled points. Recently, a weaker form of partial supervision has been considered. Wagstaff [START_REF] Wagstaff | Constrained k-means clustering with background knowledge[END_REF] proposed to introduce two types of instance-level constraints. A Must-Link constraint specifies that two objects must be in the same class, and a Cannot-Link constraint expresses the fact that two objects should not be in the same class. Such pairwise constraints have been considered and integrated in many unsupervised algorithms such as the hard or the fuzzy c-means (FCM), and have recently become a topic of great interest [START_REF] Basu | A probabilist framework for semi-supervised clustering[END_REF][START_REF] Wagstaff | Value, cost, and sharing: Open issues in constrained clustering[END_REF][START_REF] Davidson | Clustering with constraints: Feasibility issues and the kmeans algorithm[END_REF][START_REF] Liu | Boostcluster: boosting clustering by pairwise constraints[END_REF][START_REF] Antoine | CECM: Adding pairwise constraints to evidential clustering[END_REF][START_REF] Antoine | CECM: Constrained Evidential C-Means algorithm[END_REF]. They have been incorporated in many different ways, generally by including a penalty term in the objective function [START_REF] Basu | Active semi-supervision for pairwise constrained clustering[END_REF][START_REF] Grira | Active semi-supervised fuzzy clustering[END_REF] or by altering the distances between objects with respect to the constraints [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF][START_REF] Klein | From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering[END_REF].

In this paper, we propose to add instance-level constraints in EVCLUS [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF], an evidential clustering algorithm dedicated to proximity data. This new algorithm, called CEVCLUS, combines the advantages of adding background knowledge and evidential clustering. The rest of this paper is organized as follows. First, Section 2 recalls the basic background on belief function and evidential clustering with EVCLUS, then Section 3 presents the CEV-CLUS algorithm. We initially formulate Must-Link and Cannot-Link constraints in the framework of belief functions to subsequently integrate them in the evidential clustering scheme. Some results are shown in Section 4. Finally Section 5 concludes and gives some perspectives of the work.

Background

Belief functions theory

The Dempster-Shafer theory [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF], also referred to as belief functions theory, is a mathematical framework for uncertain and imprecise knowledge. The main concepts are presented in this section.

Let Ω be a finite set called frame of discernment. A mass function m : 2 Ω → [0, 1] represents partial knowledge about the actual value taken by a variable y. This function satisfies

A⊆Ω m(A) = 1.
(

) 2
The subsets A such that m(A) > 0 are called the focal elements of m. The value m(A) represents the degree of belief that the variable y belongs to the subset A, knowing that it has been impossible to assign this belief to a more specific subset of A. Thus, complete ignorance corresponds to m(Ω) = 1. A particular case arises when all focal sets are singletons: m is then equivalent to a probability distribution. If m(∅) > 0 then y may not belong to Ω. This interpretation is defined as the open-world assumption.

Given a mass function m, it is possible to define a plausibility function pl : 2 Ω → [0, 1] and a belief function bel : 2 Ω → [0, 1] by:

pl(A) = B∩A =∅ m(B) ∀A ⊆ Ω, ( 3
) bel(A) = B⊆A,B =∅ m(B) ∀A ⊆ Ω. (4)
The quantity bel(A) represents the total amount of support given to A, whereas pl(A) measures the maximal degree of belief that could be given to A.

Those functions are variants of the same information, and one can be retrieve from each other by:

pl(A) = 1 -m(∅) -bel(A), ( 5
)
where A denotes the complement of A ⊆ Ω. The conjunctive rule makes it possible to combine two belief functions define on the same frame:

(m 1 ∩ m 2 )(A) = B∩C=A m 1 (B)m 2 (C) ∀A ⊆ Ω. (6)
The quantity (m 1 ∩ m 2 )(∅) is called the degree of conflict between m 1 and m 2 . It denotes the degree of disagreement between the two belief functions, and satisfies

K 12 = (m 1 ∩ m 2 )(∅) = B∩C=∅ m 1 (B)m 2 (C). (7)
For decision making, the mass function is transformed into a pignistic probability distribution [START_REF] Smets | The transferable be-lief model[END_REF]:

BetP (ω) = ω∈A m(A) |A| ∀ω ∈ Ω, (8)
where |A| denotes the cardinality of A ⊆ Ω. If m(∅) > 0, a normalization step has to be performed before carrying out the pignistic transformation. There exists many different methods to execute this step, for example Yager's normalization consists in transferring m(∅) to m(Ω) [START_REF] Yager | On the normalization of fuzzy belief structures[END_REF].

Evidential clustering of proximity data

Let us consider O = {o 1 , . . . o n } a collection of n ob- jects to classify in a set Ω = {ω 1 , . . . ω c }.
In [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF], it was proposed to use the concept of credal partition instead of a crisp or a fuzzy one. Partial knowledge regarding the class membership of an object is represented by a mass function on the set of possible classes. A credal partition of O is denoted by M = (m 1 , . . . , m n ). Let us consider an example of five objects that need to be classified into two classes. A credal partition is shown in Table 1. The classes of the three first objects are known with certainty whereas the class of the fourth object is completely unknown. The fifth object, with all its mass allocated to the empty set, corresponds to an outlier.

A m 1 (A) m 2 (A) m 3 (A) m 4 (A) m 5 (A) ∅ 0 0 0 0 1 {ω 1 } 1 1 0 0 0 {ω 2 } 0 0 1 0 0 Ω 0 0 0 1 0 Table 1: Example of credal partition
Let us suppose that the available data consists of a n × n dissimilarity matrix ∆ = (δ ij ) where δ ij = δ ji represents the degree of dissimilarity between two objects o i and o j . To derive a credal partition from the input dissimilarities, Denoeux and Masson [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] proposed the following compatibility condition:

δ ij > δ i ′ j ′ ⇒ K ij ≥ K i ′ j ′ , ( 9
)
where (o i , o j ) and (o i ′ , o j ′ ) represent any pairs of object in O 2 and K ij denotes the degree of conflict between m i and m j . Thus, the more dissimilar the objects, the higher the conflict between the mass functions. The purpose is then to find a credal partition M that is the most compatible with ∆. This problem is similar to the one addressed by multidimensional scaling algorithms, which aim at finding a configuration of points in a p-dimensional space such that the distances between points approximate the dissimilarities [START_REF] Borg | Modern multidimensional scaling[END_REF]. The EVCLUS [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] algorithm minimizes the following stress function:

J EV CLUS (M, a, b) = 1 C i<j (aK ij + b -δ ij ) 2 δ ij , ( 10
) where a and b are two coefficients, and C is a normalizing constant defined as

C = i<j δ ij . ( 11
)
In addition, the credal partition should satisfy the constraints m i (A k ) ≥ 0 for all object o i and all subset A k , as well as the Equation [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF]. In order to avoid constrained optimization issues, it is possible to remove the current constraints by using the following parametrization:

m i (A k ) = exp(α ik ) 2 c l=1 exp(α il ) , ( 12
)
where A k , k = {1, . . . 2 c } are the focal sets and the α ik are the (n × 2 c ) real parameters representing the credal partition. Thus, the EVCLUS algorithm carries out an iterative optimization of the objective function ( 10) using a gradient-based procedure.

EVCLUS with constraints

Expression of the constraints

Let us consider two objects o i and o j . We recall that a Must-Link constraint specifies that both objects belong to the same class while a Cannot-Link constraint expresses the fact that the two objects do not belong to the same class. A mass function regarding the joint class membership of both objects may be computed from m i and m j in the Cartesian product Ω 2 = Ω × Ω. This mass function, denoted m i×j , is the combination of the vacuous extension of m i and m j . As shown in [START_REF] Smets | The transferable be-lief model[END_REF], we have for all

A, B ⊆ Ω, A = ∅, B = ∅: m i×j (A × B) = m i (A) m j (B), (13)
and

m i×j (∅) = m i (∅) + m j (∅) -m i (∅) m j (∅). ( 14
)
In Ω 2 , a Must-Link corresponds to the subset of Ω:

θ ij = {(ω 1 , ω 1 ), (ω 2 , ω 2 ), . . . (ω c , ω c )}, whereas a Cannot-Link corresponds to its complement θ ij .
Then, the plausibilities pl i×j (θ ij ) and pl i×j (θ ij ) associated with m i×j can be determined:

pl i×j (θ ij ) = A∩B =∅ m i (A) m j (B), (15)
and

pl i×j (θ ij ) = 1 -m i×j (∅) -bel i×j (θ ij ), ( 16
) = 1 -m i×j (∅) - c k=1 m i ({ω k }) m j ({ω k }).
As an example, the plausibilities associated to the credal partition shown in Table 1 are expressed in Table 2. Let us remark that the objects o 1 and o 2 belong to the same class (cf. Table 1); this translates the plausibilities pl 1×2 (θ 12 ) = 1 and pl 1×2 (θ 12 ) = 0. On the other hand, the objects o 1 and o 3 do not belong to the same class (cf. Table 1), and consequently their joint class plausibilities are pl 1×3 (θ 13 ) = 0 and pl 1×3 (θ 13 ) = 1. The credal partition does not give any information about the class membership of the object o 4 : its relationship with object o 1 is unknown, and both could either be in the same class or not. Thus, pl 1×4 (θ 14 ) = pl 1×4 (θ 14 ) = 1. Object o 5 does not belong to Ω and represents an outlier. Hence, pl 1×5 (θ 15 ) = pl 1×5 (θ 15 ) = 0.

F pl 1×2 (F ) pl 1×3 (F ) pl 1×4 (F ) pl 1×5 (F ) θ ij 1 0 1 0 θ ij 0 1 1 0
In summary, we deduce that the relationship between two objects can be expressed by using the joint plausibilities of both events θ ij and θ ij . Indeed, two objects o i and o j are surely in the same class if pl i×j (θ ij ) = 0 and pl i×j (θ ij ) = 1. Inversely, we assume that two objects o i and o j are surely in a different class if pl i×j (θ ij ) = 0 and pl i×j (θ ij ) = 1.

Expression of the objective function

In a clustering algorithm, the credal partition is unknown. However, prior information expressed by pairwise constraints may be available. Let us denote by M and C the sets of Must-Link constraints and Cannot-Link constraints, respectively. A simple formulation of the constraints can be proposed using joint class plausibilities. Indeed, if we know that two objects o i and o j have a Must-Link constraint, then pl i×j (θ ij ) must be low and pl i×j (θ ij ) must be high. On the contrary, if we know that two objects o i and o j have a Cannot-Link constraint, then pl i×j (θ ij ) must be low and pl i×j (θ ij ) must be close to 1. Let us define J CON ST , the cost of violating pairwise constraints:

J CON ST = 1 2(|M| + |C|) (J M + J C ) , ( 17
)
J M = (oi,oj )∈M pl i×j (θ ij ) + 1 -pl i×j (θ ij ), ( 18
)
J C = (oi,oj )∈C pl i×j (θ ij ) + 1 -pl i×j (θ ij ), ( 19
)
where |M| and |C| denote the number of Must-Link constraints and the number of Cannot-Link constraints, respectively.

The CEVCLUS algorithm should compute a credal partition compatible with the input dissimilarities and satisfying as much as possible the instance-level constraints. Thus, we propose to minimize the following objective function: [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF] where ξ ∈ [0 1] is a parameter that controls the trade-off between the evidential model and the constraints.

J CEV CLUS = (1 -ξ)J EV CLUS + ξJ CON ST ,
Positivity constraints on mass functions as well as constraint (2) vanish by employing [START_REF] Liu | Boostcluster: boosting clustering by pairwise constraints[END_REF]. Like in EVCLUS, a gradient based optimization is then applicable to minimize the objective function.

Results

Methodology

The data sets used in the following experiments include a label for each object. The final partition P is known and can be compared with a crisp partition P computed by CEVCLUS. A popular measure of agreement between two partitions P and P is the Rand Index (RI) defined as:

RI(P, P ) = 2(a + b) n(n -1) , ( 21
)
where a (respectively, b) is the number of pairs of objects simultaneously assigned to identical classes (respectively, different classes) in P and P , and n is the total number of objects included in the data set.

In order to get a crisp partition P , we transform the final credal partition found with CEVCLUS into a fuzzy partition by using the pignistic transformation. Then we assign each object to the class with maximal pignistic probability.

For each data set in the following experiments, a single trial consists in running 10 times CEVCLUS with different initializations, and retaining the solution with the minimum value of the objective function. Note also that the dissimilarity matrix consists of the matrix of squared Euclidean distances.

Synthetic data set

We first illustrate how the constraint-based algorithm CEVCLUS can be oriented towards a desired solution using a suitable set of constraints. For this purpose, we created an unlabeled synthetic data set. It was generated according to a mixture of four Gaussians in a two-dimensional space. We then defined two labeled data sets by separating the data in two different ways, as shown in Table 3. The data sets are represented in Figures 1 and2.

In the Toys1 data set, the two classes are separated by an horizontal boundary. The EVCLUS algorithm applied for this data set gives a credal partition with either vertical or horizontal boundary between the classes, depending on the initialization. The case of an horizontal boundary (cf.

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 2 2 2 2
Figure 3) does not correspond to the true partition of the Toys1 data set. Figure 4 shows that randomly adding 10 constraints makes it possible to guide the algorithm towards the desired solution. Note that constraints were selected by hand so that two constrained objets are not in the same Gaussian. The hard credal partition represent the assignment of each object to the subset A ⊆ Ω with the maximal degree of belief. Parameter ξ was set to 0.2. data set gives the same solutions that on the Toys1 data set. Figures 5 and6 show the hard credal partition given by CEVCLUS with 20 constraints randomly chosen and ξ = 0.5. The degrees of belief of the objects for the sets ω 1 and Ω are also presented with contour lines in those figures. We remark that the constraints allow us to modify the contour lines in such a way that the algorithm finds the desired classes. It can be also observed that the highest degree of belief given to the set of total uncertainty Ω is located at the boundary of the two classes. It can be noticed that, unlike previously, the actual partition of the data set Toys2 is not one of the partitions given by EVCLUS, and is hard to reach as it is far from the initial solutions. Thus, we decided to increase the importance given to the constraints, by setting ξ = 0.5.

Iris data set

The Iris data set is composed of three classes that represent different species of Iris: Setosa, Virginica and Versicolor. Each species includes 50 samples. It should be emphasized that the distributions of the classes are not spherical. However, we suppose we do not have this information and we use the Euclidean distances as proximity values.

Figure 7 shows the evolution of the average RI and RI on unconstrained objects (computed over 100 trials) according to the number of constraints. Remark that ξ is set to 0.2 and five focal elements are selected: the singletons, Ω and ∅. Adding constraints not only increases the RI, but also improves the RI computed over unconstrained objects. This shows that including constraints leads the algorithm towards a better partition. Remark that adding a small amount of randomly chosen constraints seems to have a negative impact on the performances, as we can observe on the Figure 7. This happens when constrained objects have been misclassified with a high degree of belief. The same behavior has been noticed in many semi-supervised clustering algorithms and has been discussed in [START_REF] Wagstaff | Value, cost, and sharing: Open issues in constrained clustering[END_REF][START_REF] Davidson | Measuring constraint-set utility for partitional clustering algorithms[END_REF].

Conclusion

We have developed a new algorithm, called CEV-CLUS, based on the belief functions theory and that makes it possible to incorporate background knowledge in the classification process. It is an extension of the relational evidential clustering algorithm EVCLUS. CEVCLUS computes a credal partition from a dissimilarity matrix. This notion of credal partition generalizes those of crisp, fuzzy and possibilistic partitions. Our contribution consists in introducing background knowledge in the clustering process of EVCLUS. This prior information is formulated as pairwise constraints on instances: a Must-Link constraint (respectively, a Cannot-Link constraint) indicates that two objects belong (respectively, do not belong) to the same class.

Experiments show that adding a few number of constraints makes it possible to guide the algorithm towards a desired solution, even for unbalanced and non-spherical classes. The quality of the solution depends on the number of constraints and on the trade-off between the evidential model and the constraints. As a rule, the value of the parameter ξ should not be close to 1. Furthermore, the value of ξ should preferably be low when there are few constraints, to prevent constrained objects from being misclassified with a high degree of belief.

Future work may be conducted in the choice of the set of constraints. Indeed, we are interested in adding a small number of very informative constraints. The expected result is to decrease the needed quantity of prior-information and to increase the accuracy of the final partition. Such a method, known as active learning [START_REF] Basu | Active semi-supervision for pairwise constrained clustering[END_REF][START_REF] Grira | Active semi-supervised fuzzy clustering[END_REF], automatically selects pairwise constraints during the clustering process.

Figure 1 :

 1 Figure 1: Toys1 data set.

Figure 2 :

 2 Figure 2: Toys2 data set.

2 ΩFigure 3 :

 23 Figure 3: Hard credal partition obtained using EV-CLUS.

1 ΩFigure 4 :

 14 Figure 4: Hard credal partition obtained for Toys1 using CEVCLUS with 10 constraints. Solid and dashed lines represent Must-Link and Cannot-Link constraints, respectively.

1 Figure 5 :

 15 Figure 5: Hard credal partition and contour lines of the mass m({ω 1 }), obtained for Toys2 using CEV-CLUS with 20 constraints.

Figure 6 :

 6 Figure 6: Hard credal partition and contour lines of the mass m(Ω), obtained for Toys2 using CEV-CLUS with 20 constraints.

Figure 7 :

 7 Figure 7: Averaged Rand Index and 95% confidence interval as a function of the number of randomly selected constraints.

Table 2 :

 2 Plausibilities for the events θ ij and θ ij

Table 3 :

 3 Construction of the Toys data set

	N		Nb	Toys1	Toys2
	µ	σ	objects classes classes
	(0,0)		100	1	1
	(0, 7)	2 0	100	1	2
	(7, 0)	0 2	100	2	2
	(7, 7)		100	2	2