Feng Li

Shoumei Li

Thierry Denoeux
email: tdenoeux@utc.fr

k-CEVCLUS: Constrained Evidential Clustering of Large Dissimilarity Data $

Keywords: Constrained evidential clustering of large dissimilarity data Evidence theory, Dempster-Shafer theory, belief functions, relational data, credal partition, constrained clustering, instance-level constraints

Introduction

Cluster analysis, also called data segmentation, is one of the basic tasks in data mining and machine learning. The goal of cluster analysis is to segment a collection of objects into clusters in such a way that similar objects belong to the same cluster, while dissimilar ones are assigned to different clusters. Typically, two data types are considered: attribute and dissimilarity data. Dissimilarity data, also known as relational data or proximity data, are composed of distances, or dissimilarities between objects. Attribute data can always be transformed into dissimilarity data by using a suitable metric. In this paper, we focus mostly on dissimilarity data.

Several approaches to clustering have been developed over the years. In hard clustering, each object is assigned with full certainty to one and only one cluster; the c-means algorithm is the reference method in this category. In contrast, "soft" clustering algorithms [START_REF] Peters | Soft clustering: fuzzy and rough approaches and their extensions and derivatives[END_REF] are based on different ways of representing cluster-membership uncertainty. These include fuzzy [START_REF] Bezdek | Pattern Recognition with fuzzy objective function algorithm[END_REF], possibilistic [START_REF] Krishnapuram | A possibilistic approach to clustering[END_REF] and rough [START_REF] Lingras | Applying rough set concepts to clustering[END_REF] clustering. Evidential clustering [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] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF][START_REF] Liu | Credal c-means clustering method based on belief functions[END_REF] is a recent approach to soft clustering, in which uncertainty is represented by Dempster-Shafer mass functions [START_REF] Shafer | A mathematical theory of evidence[END_REF]. The resulting clustering structure is called credal partition. Thanks to the generality of Dempster-Shafer theory, evidential clustering can be shown to extend all other soft clustering paradigms [START_REF] Denoeux | Beyond fuzzy, possibilistic and rough: An investigation of belief functions in clustering[END_REF]. Some of the recent advances in evidential clustering are briefly summarized here. The Evidential c-Means (ECM) algorithm [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] is an extension of the hard and fuzzy cMeans, in which prototypes are defined not only for clusters, but also for sets of clusters. A cost function is minimized in turn with respect to the prototypes, and with respect to the credal partition. A version of ECM for dissimilarity data, called RECM, was proposed in [START_REF] Masson | RECM: relational evidential c-means algorithm[END_REF]. In [START_REF] Liu | Credal c-means clustering method based on belief functions[END_REF], another variant of the ECM algorithm (called CCM) was proposed, based on an alternative definition of the distance between a vector and the prototype of a meta-cluster. This modification produces more sensible results in situations where the prototype of a meta-cluster is close to that of singleton cluster. In [START_REF] Zhou | Median evidential c-means algorithm and its application to community detection[END_REF], Zhou et al. introduced yet another variant of ECM, called Median Evidential c-means (MECM), which is an evidential counterpart to the median c-means and median fuzzy c-means algorithms. An advantage of this approach is that it does not require the dissimilarities between objects to verify the axioms of distances. In [START_REF] Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF], the author proposed another evidential clustering method, called Ek-NNclus, which is based on evidential k-nearest neighbor rule [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF]. Evidential clustering has been successfully applied in various fields, including machine prognosis [START_REF] Serir | Evidential evolving Gustafson-Kessel algorithm for online data streams partitioning using belief function theory[END_REF], medical image processing [START_REF] Makni | Introducing spatial neighbourhood in evidential c-means for segmentation of multi-source images: Application to prostate multi-parametric MRI[END_REF][START_REF] Lelandais | Fusion of multi-tracer PET images for dose painting[END_REF][START_REF] Lian | Spatial evidential clustering with adaptive distance metric for tumor segmentation in FDG-PET images[END_REF] and analysis of social networks [START_REF] Zhou | Median evidential c-means algorithm and its application to community detection[END_REF].

The notion of credal partition was first introduced in [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF], together with the first evidential clustering algorithm, called EVCLUS. The EVCLUS algorithm is similar in spirit to multidimensional scaling procedures [START_REF] Cox | Multidimensional scaling[END_REF]. It attempts to build a credal partition such that the plausibility of two objects belonging to the same cluster is higher when the two objects are more similar. This result is achieved by minimizing a stress, or cost function using a gradient-based optimization procedure. A constrained version of EVCLUS allowing for the utilization of prior knowledge about the joint cluster membership of object pairs was later proposed in [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF] under the name CEVCLUS. In the CEVCLUS method, pairwise constraints are formalized in the belief function framework and translated as a penalty term added to the stress function of EVCLUS.

Both EVCLUS and CEVCLUS were shown to outperform state-of-the-art clustering procedures [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF][START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF]. However, their high space and time complexity restricted their application to small datasets with only a few hundred objects. Recently, a new version of EVCLUS, called k-EVCLUS, has been proposed [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF].

k-EVCLUS is based on an iterative row-wise quadratic programming (IRQP) algorithm, which makes it much faster than EVCLUS. It also uses only a random sample of the dissimilarities, which reduces the time and space complexity from quadratic to linear, making it suitable to cluster large datasets.

In this paper, we carry out similar improvements to the CEVCLUS algorithm. We show that the cost function composed of a stress term and a penalty term encoding pairwise constraints can also be minimized using the IRQP algorithm, which is several orders of magnitude faster than the gradient-based procedure used in [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF]. Together with dissimilarity sampling, this modification makes the new version of CEVCLUS (called k-CEVCLUS) applicable to large datasets composed of tens of thousands of objects with pairwise constraints. We also introduce a new constraint expansion strategy, which brings considerable improvements in clustering results when only a few constraints are provided. Altogether, the contributions reported in this paper considerably extend the applicability of constrained evidential clustering to real-world datasets of realistic size.

The rest of this paper is organized as follows. Basic notions on belief functions and credal partitions, as well as the k-EVCLUS and CEVCLUS algorithms are first recalled in Section 2. The new k-CEVCLUS algorithm and the constraint expansion procedure are then described in Section 3, and experimental results are reported in Section 4. Finally, Section 5 concludes the paper.

Background

The purpose of this section is to provide the reader with background information so as to make the paper self-contained. Basic notions of Dempster-Shafer theory are first recalled in Section 2.1, and the concept of credal partition is introduced in Section 2.2. The k-EVCLUS and CEVCLUS algorithms are then presented in Sections 2.3 and 2.4, respectively.

Mass Functions

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 Dempster-Shafer theory, a mass function encodes a piece of evidence about some question of interest, for which the true answer is assumed 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 has a special interpretation: it is a measure of the belief that the true answer might not belong to Ω. As we will see, this quantity is very useful in clustering to identify outliers. A mass function is said to be

• Bayesian if all its focal sets are singletons;

• Logical if it has only one focal set;

• Certain if it is both logical and Bayesian;

• Consonant if its focal sets are nested.

Given a mass function m, the corresponding belief and plausibility functions are defined, respectively, as

Bel(A) = ∅ =B⊆A m(B) and P l(A) = B∩A =∅ m(B),
for all A ⊆ Ω. The quantity Bel(A) represents the degree of total support in A, while P l(A) can be interpreted as the degree to which the evidence is consistent with A.

The degree of conflict [START_REF] Shafer | A mathematical theory of evidence[END_REF] between these two mass functions m 1 and m 2 defined on the same frame Ω is

κ = A∩B=∅ m 1 (A)m 2 (B). (2)
If m 1 and m 2 are mass functions representing evidence about two distinct questions with the same set of possible answers Ω, then the plausibility that the two questions have the same answer is equal to 1 -κ [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF].

Credal Partition

Let O = {o 1 , . . . , o n } be a set of n objets. We assume that each object belongs to at most one of c clusters. The set of clusters is denoted by Ω = {ω 1 , . . . , ω c }. In evidential clustering, the uncertainty about the cluster membership of each object o i is represented by a mass function m i on Ω. The n-tuple M = (m 1 , . . . , m n ) is called a credal partition. The notion of credal partition is very general and it encompasses most other types of soft clustering structures [START_REF] Denoeux | Beyond fuzzy, possibilistic and rough: An investigation of belief functions in clustering[END_REF]. In particular,

• If all mass functions m i are certain, then we have a hard partition, where

object o i is assigned to cluster ω k if m i ({ω k }) = 1.
• If all mass functions m i are Bayesian, then the evidential partition is equivalent to a fuzzy partition; the degree of membership of object o i to cluster ω k is then u ik = m i ({ω k }), for i ∈ {1, . . . , n} and k ∈ {1, . . . , c}.

• If all mass functions m i are logical with a single focal set A i ⊆ Ω, then we get a rough partition. The lower and upper approximations of cluster k can be defined, respectively, as

ω k = {o i ∈ O|A i = {ω k }} and ω k = {o i ∈ O|ω k ∈ A i }.
• If each m i is consonant, then it is equivalent to a possibility distribution, and it can be uniquely represented by the plausibility of the singletons pl ik = P l i ({ω k }) for i ∈ {1, . . . , n} and k ∈ {1, . . . , c}. Each number pl ik is the plausibility that object i belongs to cluster k; these numbers form a possibilistic partition of the n objects.

Because a credal partition is more general than other types of hard or soft partitions, it can be converted into any other type [START_REF] Denoeux | Beyond fuzzy, possibilistic and rough: An investigation of belief functions in clustering[END_REF]. For instance, we obtain a fuzzy partition by defining the degree of membership u ik of object o i to cluster ω k as

u ik = pl ik c =1 pl i . (3)
This fuzzy partition can then be converted to a hard partition by assigning each object to the cluster with the highest membership degree.

k-EVCLUS Algorithm

The k-EVCLUS algorithm [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF][START_REF] Denoeux | evclust: Evidential Clustering[END_REF] is a faster and more efficient version of the EVCLUS algorithm introduced in [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF]. Let D = (d ij ) be an n × n matrix of dissimilarities between object. The basic idea of EVCLUS and k-EVCLUS is to construct a credal partition M = (m 1 , . . . , m n ) in such a way that the degrees of conflict κ ij between any two mass functions m i and m j match the dissimilarities d ij . Therefore, similar objects should be assigned mass functions with low conflict (i.e., a high plausibility of belonging to the same cluster), whereas dissimilar objects should have highly conflicting mass functions (corresponding to a low plausibility of belonging to the same cluster). This principle can be implemented by minimizing a stress function such as

J(M) = η i<j (κ ij -δ ij ) 2 , (4)
where η = i<j δ 2 ij -1 and the δ ij are transformed dissimilarities defined by

δ ij = ϕ(d ij )
, where ϕ is an increasing function from [0, +∞) to [0, 1], such as

ϕ(d) = 1 -exp(-γd 2 ). (5)
In [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], γ is parameter that can be fixed as follows [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. For α ∈ (0, 1), let d 0 = ϕ -1 (1 -α) be the dissimilarity value such that two objects whose dissimilarity exceeds d 0 have a plausibility at least equal to 1 -α. For ϕ defined by (5), we have

γ = -log α/d 2 0 . (6)
We recommend fixing α = 0.05 and leaving d 0 as the only parameter to be adjusted. In practice, d 0 can be set to some quantile of distances d ij (See Section 4.2). In [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], the results of k-EVCLUS have been shown to be quite robust to the choice of d 0 . However, a smaller value of d 0 should generally be selected when the number of clusters is larger. Practical guidelines for tuning d 0 will be presented in Section 4.2.

The EVCLUS algorithm [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] minimizes a stress function similar to (4) using a gradient-based algorithm. In contrast, k-EVCLUS uses the faster IRQP algorithm [START_REF] Ter Braak | Approximating a similarity matrix by a latent class model: A reappraisal of additive fuzzy clustering[END_REF], which consists in minimizing J(M) with respect to each mass function m i at a time. Each iteration of this cyclic coordinate descent strategy amounts to solving a linearly constrained positive least-squares problems, which can be done quite efficiently.

Another important innovation of the k-EVCLUS algorithm is to exploit the redundancies in matrix D by minimizing the sum of the squared error terms (κ ij -δ ij ) 2 for only a subset of the object pairs (i, j). This can be done by choosing some value k < n and randomly selecting, for each objet i, k other objects j 1 (i), . . . , j k (i). We can then minimize the sum of squared errors (κ ijδ ij ) 2 over the pairs (i, j r (i)),

J k (M) = η n i=1 k r=1 (κ i,jr(i) -δ i,jr(i) ) 2 . ( 7
)
As noted in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], the calculation of J k (M) requires only O(nk) operations, against O(n 2 ) for J(M), which makes it possible to apply k-EVCLUS to very large datasets. For small datasets, we can select k = n -1, in which case ( 7) is identical to [START_REF] Cox | Multidimensional scaling[END_REF].

Another important practical issue in the application of k-EVCLUS is the number of focal sets. This number must be controlled to make the method useable for moderate and large values of c. In [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] and [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], very good results have been reported with focal sets limited to the empty set, the singletons of Ω, and the whole set Ω itself. The number f of focal sets is then equal to c + 2, which allows the degrees of conflict κ ij in (4) to be computed in linear time as a function of c, making the method useable to datasets with a large number of clusters. This restriction will be applied in all the experiments reported in Section 4.

CEVCLUS Algorithm

The constrained evidential clustering (CEVCLUS) algorithm [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF] is a variant of EVCLUS that makes it possible to take into account prior knowledge about clusters, in the form of pairwise "must-link" (ML) and "cannot-link" (CL) constraints. A ML constraint is a pair of objects that are know to belong to the same cluster, while a CL constraint is pair of objects that surely belong to different clusters.

Let S ij denote the event that objects i and j belong to the same cluster, and S ij the complementary event. Given mass functions m i and m j about the cluster-membership of objects i and j, the plausibility of S ij and S ij can be computed as follows [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF],

P l ij (S ij ) = 1 -κ ij (8a) P l ij (S ij ) = 1 -m i (∅) -m j (∅) + m i (∅)m j (∅) - c k=1 m i ({ω k })m j ({ω k }). (8b)
Equation (8a) further explains the rationale for stress functions ( 4) and ( 7): when the distance between two objects i and j is large, the plausibility P l ij (S ij ) that they belong to the same cluster should be small, and the degree of conflict κ ij should be large. Now, if we know for sure that two objects i and j belong to the same cluster, then we should impose the constraints P l ij (S ij ) = 1 and P l ij (S ij ) = 0. Conversely, if we know that objects i and j actually belong to different clusters, then we should have P l ij (S ij ) = 1 and P l ij (S ij ) = 0. To find a credal partition M that meets these constraints approximately, the CEVCLUS algorithm minimizes the sum of a stress function such as (4), and a penalization term:

J C (M) = stress + ξ 2(|ML| + |CL|) (J ML + J CL ), (9)
with

J ML = (i,j)∈ML P l ij (S ij ) + 1 -P l ij (S ij ), (10a)
J CL = (i,j)∈CL P l ij (S ij ) + 1 -P l ij (S ij ), ( 10b
)
where ξ is a hyperparameter that controls the trade-off between the stress and the constraints, and ML and CL are the sets of ML and CL constraints, respectively. The second term on the right-hand side of ( 9) equals zero for a credal partition M that meets the constraints exactly. In practice, it is sufficient to make it small enough so that the constraints are met approximately. The CEVCLUS algorithm [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF] minimizes (9) using an iterative gradient-based optimization procedure. As noted in [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF], this algorithm is limited to small datasets. In the next section, we introduce several improvements to CEVCLUS, making it much faster and applicable to very large datasets. We also describe a new constraint expansion procedure allowing us to drastically increase the impact of pairwise constraints.

Constrained k-EVCLUS Algorithm

This section introduces the main contributions of this paper. The new k-CEVCLUS algorithm, a faster and more efficient version of CEVCLUS, will first be presented in Section 3.1, and the constraint expansion method will be described in Section 3.2.

k-CEVCLUS Algorithm

In section, we propose a constrained version of the k-EVCLUS algorithm described in Section 2.3. The resulting algorithm, called k-CEVCLUS, will minimize the following cost function,

J kC (M) = η n i=1 k r=1 κ i,jr(i) -δ i,jr(i) 2 + ξ 2(|ML| + |CL|) (J ML + J CL ), (11)
where, as before, j 1 (i), . . . , j k (i) are k integers randomly selected in 1, 2, . . . , i -1, i + 1, . . . , n. In Eq. ( 11), the first term on the right-hand side is identical to the stress function ( 7) of k-EVCLUS, while the second term is equal to the penalty term [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF] of CEVCLUS. We note that the calculation of J Ck (M) requires O(nk

+ |ML| + |CL|) operations, against O(n 2 + |ML| + |CL|) for CEV- CLUS.
As with CEVLUS, parameter ξ should be set carefully. Selecting a very large value for ξ will enforce the constraints exactly, but will typically make the optimization problem more difficult. A good strategy is to increase ξ gradually, starting from ξ = 0. This strategy will be further discussed in Section 4.2.

To show that the cost function ( 11) can be minimized using the IRQP algorithm, we need to express [START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF] in matrix form. We assume that each mass function m i has at most f focal sets among the set F = {F 1 , . . . , F f }, where F 1 = ∅ and the c singletons {ω k }, k = 1, . . . , c are among the f -1 nonempty subsets {F 2 , . . . , F f }. Mass function m i can then be represented by a vector m i = (m i (F 1 ), . . . , m i (F f )) T of length f , and the credal partition

M = (m 1 , . . . , m n ) can be represented by matrix M = (m 1 , . . . , m n ) T of size n × f .
The degree of conflict (2) between two mass functions m i and m j can be written as

κ ij = m T i Cm j ,
where C is the square matrix of size f with general term

C kl = 1 if F k ∩ F l = ∅, 0 otherwise. ( 12
)
The plausibility P l ij (S ij ) in (8a) can then be written as

P l ij (S ij ) = 1 -m T i Cm j = m T i (1 • 1 T -C)m j ,
where 1 = (1, . . . , 1) T . Before rewriting P l ij (S ij ), we note that the term m i (∅)+ m j (∅) -m i (∅)m j (∅) in the right-hand side of (8b) can be written as m T i Bm j , where B is the following square matrix of size f ,

B =      1 1 • • • 1 1 0 • • • 0 . . . . . . . . . . . . 1 0 • • • 0      , (13)
and the term c k=1 m i ({ω k })m j ({ω k } can be written as m T i Am j , where A is the square matrix of size f with general term

A k = 1 k = , |F k | = 1 0 otherwise. ( 14
)
With these notations, we have

P l ij (S ij ) = 1 -m T i Bm j -m T i Am j = m T i Em j , where E = 1 • 1 T -B -A. (15)
The penalty terms in [START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF] can finally be written as

J ML = (i,j)∈ML m T i (C + E)m j , J CL = (i,j)∈CL m T i (C + E)m j , where C = 1 • 1 T -C and E = 1 • 1 T -E. ( 16
)
With these notations, the stress function ( 11) equals to

J kC (M ) = η n i=1 k r=1 m T i Cm jr(i) -δ i,jr(i) 2 + ρ    (i,j)∈ML m T i (C + E)m j + (i,j)∈CL m T i (C + E)m j    , (17)
where

ρ = ξ [2(|ML| + |CL|)] -1 .
From expression [START_REF] Lingras | Applying rough set concepts to clustering[END_REF], it is clear that J kC (M ) is a quadratic function of each vector m i . Consequently, minimizing J kC (M ) with respect to m i alone while leaving the other vectors m j constant is a quadratic programming problem. This is the underlying principle of the IRQP algorithm [START_REF] Ter Braak | Approximating a similarity matrix by a latent class model: A reappraisal of additive fuzzy clustering[END_REF][START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. The cost function to be minimized as each iteration is

g(m i ) = η M i Cm i -δ i ) 2 + ρ      j∈ML(i) m T j (C + E)   m i +   j∈CL(i) m T j (C + E)   m i    , (18)
where

M i = (m j1(i) , . . . , m j k (i) )
T is the matrix of size k×f whose row r is equal to vector m jr(i) , ML(i) and CL(i) are the sets of objects linked to object i by, respectievely, ML and CL constraints, and δ i is the vector of (δ i,j1(i) , . . . , δ i,j k (i) ) T of transformed dissimilarities between object o i and all sampled objects o jr(i) .

Developing the right-hand side of (18) and rearranging the terms, we obtain

g(m i ) = m T i Σm i + u T m i + c, (19)
with

Σ = ηC T M T i M i C (20a) u = -2ηδ T i M i C + ρ   j∈ML(i) m T j   (C + E) + ρ   j∈CL(i) m T j   (C + E) (20b) c = ηδ T i δ i . (20c)
Minimizing g(m i ) under the constraints m T i 1 = 1 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 cost J kC (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,

e 0 = 1, ( 21a
)
e t = 0.5e t-1 + 0.5 |J t -J t-1 | J t-1 , ( 21b
)
where t is the iteration counter and J t is the value of the cost function at iteration t. The algorithm stops when e t becomes less than some given threshold . The whole procedure is summarized in Algorithm 1.

Another important aspect of the procedure is the initialization of the credal partition matrix M . As the inclusion of a penalization term makes the minimization of (11) more difficult than that of [START_REF] Denoeux | Beyond fuzzy, possibilistic and rough: An investigation of belief functions in clustering[END_REF], initializing the credal partition randomly may not yield optimal results. We recommend initializing the random partition with k-EVCLUS, i.e., ignoring the constraints, before running k-CEVCLUS. Also, better results are obtained by running k-CEVCLUS a first time with a small value of ξ such as ξ = 0.05, before setting ξ to its final value. The tuning of parameters d 0 and ξ will be addressed in greater detail in Section 4.2.

Constraint Expansion

As shown in [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF] and [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF], the performances of clustering algorithms (in terms of proximity to the true partition) get better when the number of constraints increases. In particular, as the number of constraints tends to the total number of objects pairs, the partition found by a clustering algorithm can be expected to tend to the true partition. In some applications, pairwise constraints can be obtained by objective methods; however, they more often need to be elicited by visual inspection of the data, which costs time and money. In particular, for large data sets, pairwise constraints will typically be available only for a tiny proportion of all object pairs. It is thus important to "make the most" out of the small number of constraints we usually have.

For that purpose, we propose a constraint expansion strategy based on the following idea. Out of the n(n -1)/2 object pairs, some are known to belong Algorithm 1 k-CEVCLUS algorithm.

Require: D = (d ij ), ML, CL, F, k, d 0 , ξ, , initial credal partition M γ ← -log 0.05/d 2 0 for all 1 ≤ i < j ≤ n do δ ij ← 1 -exp(-γd 2 ij ) end for η ← i<j δ 2 ij -1
Compute matrices C, B, A, E using ( 12)-( 16) i by minimizing [START_REF] Makni | Introducing spatial neighbourhood in evidential c-means for segmentation of multi-source images: Application to prostate multi-parametric MRI[END_REF] subject to m T i 1 = 1 and m i ≥ 0 Replace row i of M by (m to the same cluster (those in ML), some are known not to belong to the same cluster (those in CL), and the rest have an unknown status. Determining the ML or CL status of unlabeled object pairs can thus be seen as a binary classification problem. Because there is typically only a small proportion of labeled pairs, we cannot reliably classifying all object pairs. We thus propose to classify only those pairs that are similar to one pair in ML or CL. For each pair (o i , o j ) in set S, with S ∈ {ML, CL}, neighboring pairs that are not already labeled will be found and added to S. More precisely, the proposed constraint expansion can be described as follows. Let K be a integer such that K n. We then add the K nearest neighbors of (o i , o j ) to S. This procedure is illustrated in Figure 1, and described formally in Algorithm 2.

if k < n -1 then for i = 1 to n do pick k integers j 1 (i), . . . , j k (i) randomly in {1, . . . , i -1, i + 1, . . . , n} end for else for i = 1 to n do (j 1 (i), . . . , j n-1 (i)) ← (1, . . . , i -1, i + 1, . . . ,
(t) i ) T J t ← J t + g(m (t) i ) end for e t ← 0.5e t-1 + 0.5|J t -J t-1 |/J t-1 end while return Credal partition M = (m (t) 1 , . . . , m (t) n ) T (a) (b) (c)

Numerical Experiments

In this section, we compare the performances of k-CEVCLUS to those of alternative algorithms for constrained evidential clustering. The experimental settings will first be described in Section 4.1, and the tuning of parameters ξ and d 0 will be specifically addressed in Section 4.2. A comparison with alternative clustering methods will then be presented in Section 4.3, and results with large datasets will be reported in Section 4.4. Finally, the efficiency of the constraint expansion procedure will be demonstrated in Section 4.5.

Algorithm 2 Constraint expansion algorithm. 1. The Banana datasets are synthetic data composed of two-dimensional attribute vectors uniformly distributed along intertwined circular segments with standard normal additive noise (Figure 2). This distribution was chosen to generate two clusters separated by a complex boundary, as such clusters are typically difficult to identify without prior information. All other datasets contain real data. The Glass, Iris, Ecoli and Letter were downloaded from the UCI repository1 . Dissimilarities were computed as Euclidean distances in the attribute space for all datasets except for the Zongker data, which already consist of dissimilarities.

Require: D = (d ij ), ML, CL, K ML ← ML, CL ← CL for all S ∈ {ML, CL} do for all (o i , o j ) ∈ S do Find the K NN {o i1 , . . . , o i K } of o i in O N K (o i ) ← {o i , o i1 , . . . , o i K } Find the K NN {o j1 , . . . , o j K } of o j in O N K (o j ) ← {o j , o j1 , . . . , o j K } P K (o i , o j ) ← [(N K (o i ) \ N K (o j )) × (N K (o j ) \ N K (o i ))] \ (ML ∪ CL ) for all (o r , o s ) ∈ P K (o i , o j ) do Compute the dissimilarity ∆ [(o i , o j ), (o r , o s )] = d ir + d js end for Find the K NN {(o r1 , o s1 ), . . . , (o r K , o s K )} of (o i , o j ) in P K (o i , o j ) if S == ML then ML ← ML ∪ {(o r1 , o s1 ), . . . , (o r K , o s K )} else CL ← CL ∪ {(o r1 , o s1 ), . . . , (o r K , o s K )} end if
The Letter dataset is composed of a large number of black-and-white rectangular pixel displays of the 26 capital letters in the English alphabet; each object is characterized by 16 dimensional attributes. As in Refs. [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF][START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF], we only kept three classes corresponding to letters I, J, and L because these letters are hard to recognize. However, the authors of Refs. [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF][START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF] used only 10% of the data. As k-CEVCLUS can deal with large datasets, we used all the data with n = 2263.

The Zongker digit dissimilarity dataset2 , which was also used in Ref. [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], contains similarities between 2000 handwritten digits in 10 classes, based on deformable template matching. As the dissimilarity matrix was initially non symmetric, we symmetrized it by the transformation

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
d ij ← (d ij + d ji )/2.
It should be noted that the dissimilarities are non metric, i.e., they are not Euclidean distances.

Evaluation criteria. For all the datasets considered in this study, some "groundtruth" partition exists. To compare an evidential partition with the true partition, we first converted it to a hard partition using the maximum plausibility rule as explained in Section 2.2, and we computed the Adjusted Rand Index (ARI) between the derived hard partition and the true partition [START_REF] Hubert | Comparing partitions[END_REF]. We recall that the ARI is a chance-adjusted version of the Rand Index (RI), which is a classical measure of similarity between hard partitions [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF]; the ARI is designed in such a way that it takes on the value 0 when the RI equals its expected value for random partitions, and it is equal to 1 when the two partitions being compared are identical. The exact definition of the ARI is this. Consider two partitions X = {X 1 , X 2 , . . . , X r } and Y = {Y 1 , Y 2 , . . . , Y s } of a set with n objects. Let n ij = |X i ∩ Y j | be the number of objects that belong to both X i and

Y j , n i• = |X i | = j n ij the number of objects in X i , and n •j = |Y i | = i n ij
the number of objects in Y j , for i = 1, . . . , r and i = 1, . . . , r. Then, we have

ARI = i,j n ij 2 -   i n i• 2 j n •j 2   n 2 1 2   i n i• 2 + j n •j 2   -   i n i• 2 j n •j 2   n 2 . (22)
The ARI can only be used when a ground truth partition is available. When there is no such reference partition, as it is the case in real applications, some internal quality index has to be used. In [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF], the authors proposed to measure the degree of imprecision of a credal partition by the average nonspecificity, defined by

N * = 1 n log 2 (c) n i=1   A∈2 Ω \∅ m i (A) log 2 |A| + m i (∅) log 2 (c)   . (23)
This measure was shown in [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF][START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF] to be a good internal validity index for credal partitions, allowing us, for instance, to compare credal partitions with different numbers of clusters. Average nonspecificity is comprised between 0 and 1. Smaller values indicate that masses are assigned to non empty focal sets with small cardinality, which is evidence for the adequacy of the credal partition to the data.

Guidelines for Tuning Parameters ξ and d 0

The k-CEVCLUS procedure (Algorithm 1) depends on the following parameters:

• Parameter d 0 in ( 5)-( 6);

• Parameter ξ in (11);

• The number k of dissimilarities taken into account for each object;

• The set F of focal sets;

• The threshold in the stopping criterion [START_REF] Masson | RECM: relational evidential c-means algorithm[END_REF].

As suggested in [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] and [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], we recommend choosing as focal sets the empty set, the singletons and Ω, i.e., F = {∅, {ω 1 }, . . . , {ω c }, Ω}. This choice was made for all the simulations reported in this section. For the stopping criterion, we set = 10 -5 in all our simulations. For small datasets, we recommend using k = n -1. The influence of k for large datasets will be studied in Section 4.4. The most important parameters that need some tuning are d 0 , used to transform dissimilarities, and ξ, which defines the weight of the constraints in the cost function. In this section, we present some experimental results with four datasets (Banana 200 with n = 200, Glass, Iris and Ecoli), from which we derive some guidelines for tuning d 0 and ξ.

Influence of ξ. Table 2 shows the ARI and nonspecificity criteria for nbconst = 100 and nbconst = 200 randomly selected constraints and different values of ξ. As explained in Section 3.1, k-CEVCLUS was first initialized using k-EVCLUS (i.e., with ξ = 0) and run a second time with ξ = 0.05 before being run with a higher value of ξ. Parameter d 0 was set to the 0.9-quantile of the dissimilarities for the Banana, Glass and Ecoli datasets and to the 0.6-quantile for the Iris data. For each dataset and for each value of ξ, we ran k-CEVCLUS 10 times. The average ARI and nonspecificity values are reported in Table 2. From these results, we can see that for both values of nbconst, the average nonspecificity usually gets smaller with larger values of ξ. In contrast, the ARI is not very sensitive to the choice of ξ, particularly for nbconst = 200. Although the best value of ξ differs for different datasets, the value ξ = 0.5 general yields close-tooptimal results considering both ARI and nonspecificity. We thus adopted this value in other experiments, unless otherwise specified.

Influence of d 0 . Parameter d 0 determines the size of each class [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. Typically, d 0 can be set to some quantile q of the dissimilarities D. Table 3 shows results with different values of q, from 0.1 to 1 (by 0.1 increments), with nbconst = 100 and nbconst = 200 randomly chosen constraints. In each experiment, we used ξ = 0.5 as mentioned above. For the Ecoli and Glass datasets, we can see that the ARI gets higher when increasing d 0 , while for the Iris dataset the best ARI is obtained with q = 0.6. In contrast, for the Banana 200 data, the best value of ARI was obtained with the smallest value of d 0 . However, if d 0 is too small, the average nonspecificity is high because most objects are classified as outliers. Similarly, when d 0 is large, such as q = 1, the nonspecificity is also high, because for the objects near the boundary between two clusters, some mass is assigned to the union of the clusters. But for both values of nbconst, the 0.96 (0.16) 0.98 (0.02) 0.87 (0.12) 0.6 0.94 (0.12) 0.92 (0.12) 0.96 (0.01) 0.88 (0.09) 0.7 0.94 (0.10) 0.94 (0.10) 0.97 (0.02) 0.89 (0.06) 0.8 0.91 (0.07) 0.94 (0.09) 0.92 (0.03) 0.91 (0.05) 0.9 0.90 (0.07) 0.91 (0.09) 0.88 (0.06) 0.90 (0.05) 1 0.81 (0.24) 0.92 (0.21) 0.87 (0.21) 0.89 (0.20) average nonspecificity reaches a minimum for some value of q, which is around q = 0.9 for the Banana 200, Glass and Ecoli datasets and q = 0.6 for the Iris data. These results confirm those reported in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], in which it was recommended to start with d 0 = quantile(D, 0.9), but it was also noted that "finding a suitable value of d 0 may sometimes require a trial and error process".

Performance Comparison

In this section, we compare the performances of the k-CEVCLUS to those of two alternative constrained evidential clustering methods: CEVCLUS with gradient-based cost minimization [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF], and the Constrained Evidential c-means (CECM) algorithm [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF]. The CECM algorithm is a prototype-based clustering method for attribute data, adapted from the Evidential c-means (ECM) algorithm [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] to take into account pairwise constraints. Note both CEVCLUS and CECM were shown in [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF] and [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF], respectively, to outperform other relational or attribute constrained clustering methods, such as the constrained Fuzzy Cmeans [START_REF] Grira | Active semi-supervised fuzzy clustering[END_REF] and SSCARD [START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF] algorithms. In the experiments reported in this section, we used k = n -1, so that k-CEVCLUS and CEVCLUS have exactly the same cost function and differ only by the optimization algorithm.

The three methods were compared on the Banana 200, Iris, Glass and Ecoli datasets with different numbers of pairwise constraints nbconst between 0 and 200. All the algorithms were run 20 times for each number of constraints. As suggested in Section 4.2, k-EVCLUS was run twice, with ξ 0 = 0.05 and ξ = 0.5. Parameter d 0 was fixed to d 0 = quantile(D, 0.9) for the Banana 200, Glass and Ecoli datasets and to d 0 = quantile(D, 0.6) for the Iris data. The same parameter values were used for CEVCLUS. For CECM, we used the parameter values as recommended in [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF], i.e., δ = max(D) and ξ = 0.5. All the algorithms were initialized with the corresponding unconstrained method, namely k-EVCLUS for k-CEVCLUS and CEVCLUS and ECM for CECM. Figures 3 and4 show the median as well as the lower and upper quartiles of ARI, computing time and nonspecificity over the 20 runs.

In most cases, k-CEVCLUS and CEVCLUS yield similar results in terms of ARI, as expected. However, when the number of constraints exceeds 100, k-CEVCLUS outperforms CEVCLUS for the Banana 200 (Figures 3(a)) and Glass (Figure 3(b)) datasets. The CECM method generally performs worse than the other two methods, except on the Banana 200 dataset with a small number of constraints (Figure 3(a)). The results obtained by CECM also have much higher variability than those of the two other methods (Figures 3(b), 4(a) and 4(b)).

As far as computing times are concerned, k-CEVCLUS is much faster than CEVCLUS (see Figures 3(c), 3(d), 4(c), 4(d)), which confirms the superiority of the IRQP algorithm over the gradient-based procedure and is consistent with the results in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. The k-CEVCLUS method is also faster than CECM, by a lesser amount.

In terms of average nonspecificity, k-CEVCLUS also outperforms CEVCLUS as it reaches lower values. It also outperforms CECM, except for the Glass data (Figure 3(f)). However, lower nonspecificity values can be obtained by fine-tuning parameters ξ and d 0 . For example, if we set ξ = 1 for the Glass data, the average nonspecificity is only 0.06, as can be seen from Table 2 with nbconst = 200.

In this section, we have shown that k-CEVCLUS is considerably faster than CEVCLUS, while reaching comparable of better values of ARI and nonspecificity. In the next section, we will demonstrate the performances of k-CEVCLUS on large datasets.

Results with Large Datasets

In this section, we focus on the performances of the k-CEVCLUS algorithm applied to large datasets with 2000 to 10,000 objects. For such datasets, it is usually not feasible to store the whole dissimilarity matrix. The approach outlined in Section 3.1 is to use only k n -1 randomly sampled dissimilarities for each object, which reduces the space and time complexity of the stress function calculation from quadratic to linear. The purpose of this section is to verify that this strategy does not negatively impact the performances of the k-CEVCLUS algorithm. We will not attempt any comparison with CECM, as the complexity of this algorithm limits its use to datasets with only a few hundred objects. We applied the k-CEVCLUS algorithm to four datasets: Banana 2000 with 2000 objects, Banana 10,000 with 10, 000 objects, Letter and Zongker. Parameters d 0 was set to quantile(D, 0.9) for the Banana datasets and to quantile(D, 0.8) for the Letter and Zongker datasets. Parameter ξ was set to 0.5 for the Banana datasets and to 0.1 and 0.05, respectively, for the Letter and Zongker datasets. In each case, we computed the ARI, running time and nonspecificity as a function of k for a fixed number of constraints nbconst, and as a function of nbconst for fixed k. The results are shown in Figures 5 to 8.

For all three datasets, we can see that setting k to some value between 200 and 500 yields similar solutions in terms of ARI (Figures 5(a and 8(f)). However, the variation of nonspecificity is smaller than that of ARI.

For the Letter dataset, higher variability of the ARI (Figure 7(b)) and computing time (Figure 7(d)) across repetitions is observed for 1500 to 2000 constraints, due to local minima of the cost function. In general, the optimization problem becomes more difficult with large numbers of objects and constraints, and the algorithm needs to be started several times from different random initial conditions, to avoid being trapped in a local minimum.

Comparing Figures 5(b) and 6(b), we can see that the curves of ARI as a function of nbconst have similar shapes for the Banana datasets with n = 2000 and n = 10, 000 objects. However, with 10,000 objects, we need 10,000 constraints to reach the maximum value of ARI (around 0.88), whereas this value is reached with only 2000 constraints for the smaller dataset. It thus seems that larger datasets require a larger number of constraints, and the number of constraints should be of the same order of magnitude as the number of objects. To test this assumption, we applied k-CEVLUS to Banana datasets with n = 10 5 objects, and found that nbconst = 10 5 were needed to reach a value of ARI around 0.88. In real applications, it may be impractical to obtain as many constraints, especially if they are elicited by experts. This makes the constraint expansion procedure introduced in Section 3.2 even more useful for large datasets. This procedure will be evaluated in the next section.

Experiments with Expanded Constraints

In this section, we study experimentally the constraint expansion method introduced in Section 3.2 (Algorithm 2). We recall that this procedure adds K new constraints for each initial constraint, thus increasing the total number of constraints from nbconst to (K + 1) × nbconst without requesting any additional information from the user. We considered the Banana 2000, Letter and Zongker datasets as in Section 4.4, with the same parameter settings. Figure 9 shows the ARI as a function of the number nbconst of initial constraints, for K ∈ {0, 1, 3, 5, 10}. We can see that, for a given number of initial constraints, better results in terms of ARI can be obtained as K increases. For instance, for the Banana 2000 dataset, when K = 5 and only 500 initial constraints are given (resulting in 3000 expanded constraints), the ARI equals that obtained with 1500 initial constraints (Figure 9(a)). For the Letter dataset, the best ARI value, obtained by 2000 initial constraints, can be obtained with K = 3 and only nbconst = 1100 initial constraints, corresponding 4400 expanded constraints (Figure 9(b)). For the Zongker dataset, the same results can be obtained with 1400 initial constraints or with only 1000 initial constraints and K = 1, resulting in 2000 expanded constraints (Figure 9(c)).

As can be expected, the benefits of expanding the constraints are less remarkable when the initial number of constraints is very large. Also, the difference in ARI between K = 5 and K = 10 is small, which suggests that increasing the value of K beyond 10 will just increase computing time without significantly improving the results. A large value of K might also have a negative impact on the results, as more pairs might be incorrectly labeled as ML or CL constraints. Overall, the very good results are obtained with moderate numbers of initial constraints and K = 5. With this setting, for instance, the ARI can be increased for the Banana 2000 dataset from 0.5 to 0.8 with 500 initial constraints (Figure 9(a)); for the Letter dataset, it can be increased from 0.3 to 0.8 with 1100 constraints 9(b)).

Conclusions

Evidential clustering represents a new direction of research in cluster analysis, aiming at a better representation of cluster-membership uncertainty using Dempster-Shafer mass functions. Until recently, the use of evidential clustering algorithms was limited to small datasets, due to their inherent algorithmic complexity. In particular, the EVCLUS algorithm [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF], which has been shown to perform very well with non-metric dissimilarity data, could only be applied to datasets with a few hundred objects.

In [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], the authors introduced k-EVCLUS, a variant of EVCLUS applicable to to very large datasets, thanks to (1) a new optimization algorithm and (2) random sampling of the the dissimilarity matrix. In this paper, the same ideas have been applied to CEVCLUS, a constrained version of EVCLUS making it possible to take into account prior knowledge in the form of ML and CL constraints [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF]. Contrary to CEVCLUS, the new k-CEVCLUS algorithm can be applied to datasets with several thousands or tens of thousands of objects, which makes it applicable to a wider range of real-world data. Clustering even larger datasets with, e.g., 10 6 objects or more, might require further algorithmic and theoretical developments which are left for further research.

We have also introduced a constraint expansion strategy, which consists in inferring new constraints from initial ones, resulting in drastic improvements of

Figure 1 :

 1 Figure 1: (a) A CL constraint (o i , o j ) ∈ CL, with the K-neighborhoods N K (o i ) and N K (o j ) of o i and o j , respectively (K = 2). (b) The set P K (o i , o j ) of pairs of a neighbor of o i and a neighbor of o j . (c) The K = 2 new CL constraints.

  For any object o ∈ O, let N K (o) denote the set composed of o and its K nearest neighbors (NN) in O. For each pair (o i , o j ) in set S, where S ∈ {ML, CL}, let P K (o i , o j ) be the subset of N K (o i ) × N K (o j ) composed of pairs (o r , o s ) such that: o r = o s , (o r , o s ) ∈ ML and (o r , o s ) ∈ CL. For all pairs (o r , o s ) in P K (o i , o j ), we compute the dissimilarity with (o i , o j ), as the sum of the dissimilarity between o i and o r , and the dissimilarity between o j and o s : ∆ [(o i , o j ), (o r , o s )] = d ir + d js .

Figure 2 :

 2 Figure 2: Banana 200 dataset with n = 200.

Figure 3 :Figure 4 :

 34 Figure 3: Results obtained with k-CEVCLUS (black), CEVCLUS (red) and CECM (green) for the Banana 200 and Glass datasets, with ξ = 0.5 and d 0 = quantile(D, 0.9).

  ), 6(a), 7(a) and 8(a)) and nonspecificity (Figures 5(e), 6(e), 7(e) and 8(e)) as compared to considering the full dissimilarity matrix, while significantly reducing computing time (Figures 5(c), 6(c), 7(c) and 8(c)). When the number of constraints increases for fixed k, the ARI gets higher (Figures 5(b), 6(b), 7(b) and 8(b)) at the cost of a longer running time (Figures 5(d), 6(d), 7(d) and 8(d)). In constrast, nonspecificity monotonically decreases as a function of nbconst for the Banana datasets (Figures 5(f) and 6(f)), but it exhibits a U-shaped curve for the Letter and Zongker datasets (Figures 7(f

  )

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: ARI, computing time and average nonspecificity of k-CEVCLUS as a function of k with nbconst = 2000 ((a), (c), (e)), and as a function of nbconst with k = 200 ((b), (d), (f)) for the Banana 2000 dataset with d 0 = quantile(D, 0.9) and ξ = 0.5. The error bars show the median as well as the lower and upper quartiles over 10 runs of the algorithm.

Figure 8 :

 8 Figure 8: ARI, computing time and average nonspecificity of k-CEVCLUS as a function of k with nbconst = 2000 ((a), (c), (e)), and as a function of nbconst with k = 300 ((b), (d), (f)) for the Zongker dataset with d 0 = quantile(D, 0.8) and ξ = 0.05. The error bars show the median as well as the lower and upper quartiles over 10 runs of the algorithm.

  The datasets used in our experiments are summarized in Table

	end for
	end for
	return ML , CL
	4.1. Experimental Settings
	Datasets.

Table 1 :

 1 Datasets used in the experiments.

	Dataset	Number of objects Number of clusters Number of attributes
	Banana n	n	2	2
	Glass	214	2	9
	Iris	150	3	4
	Ecoli	272	3	7
	Letter	2263	3	16
	Zongker	2000	10	NA

Table 2 :

 2 Average ARI and average nonspecificity as a function of ξ for nbconst = 100 and nbconst = 200, with d 0 = quantile(D, 0.9) for Banana 200, Glass and Ecoli data and d 0 = quantile(D, 0.6) for the Iris data. The best results in terms of ARI are shown in bold.

	nbconst	ξ	Banana 200	Glass	Iris	Ecoli
	100	0	0.38 (0.17)	0.63 (0.21) 0.75 (0.11) 0.79 (0.16)
		0.05 0.48 (0.16)	0.78 (0.19) 0.86 (0.08) 0.85 (0.13)
		0.1	0.59 (0.14)	0.79 (0.17) 0.87 (0.06) 0.86 (0.10)
		0.2	0.70 (0.12)	0.80 (0.14) 0.89 (0.04) 0.87 (0.09)
		0.3	0.69 (0.10)	0.80 (0.13) 0.90 (0.03) 0.86 (0.09)
		0.4	0.70 (0.09)	0.79 (0.11) 0.89 (0.03) 0.87 (0.09)
		0.5	0.73 (0.08)	0.82 (0.11) 0.89 (0.03) 0.87 (0.10)
		0.6	0.69 (0.07) 0.83 (0.11) 0.90 (0.03) 0.86 (0.09)
		0.7	0.70 (0.07)	0.82 (0.10) 0.90 (0.03) 0.86 (0.10)
		0.8	0.73 (0.08)	0.77 (0.09) 0.88 (0.03) 0.85 (0.10)
		0.9 0.75 (0.08) 0.78 (0.10) 0.89 (0.03) 0.85 (0.10)
		1	0.69 (0.08)	0.81 (0.11) 0.88 (0.04) 0.84 (0.09)
	200	0	0.38 (0.17)	0.6 (0.2)	0.76 (0.11) 0.79 (0.16)
		0.05 0.51 (0.15)	0.77 (0.19) 0.87 (0.08) 0.87 (0.13)
		0.1	0.61 (0.14)	0.83 (0.18) 0.93 (0.06) 0.89 (0.11)
		0.2	0.77 (0.12)	0.91 (0.14) 0.97 (0.03) 0.90 (0.08)
		0.3	0.86 (0.10)	0.92 (0.12) 0.95 (0.02) 0.91 (0.06)
		0.4	0.90 (0.09)	0.92 (0.10) 0.96 (0.02) 0.91 (0.05)
		0.5	0.90 (0.07)	0.92 (0.09) 0.97 (0.01) 0.91 (0.05)
		0.6	0.90 (0.06) 0.94 (0.08) 0.97 (0.01) 0.91 (0.05)
		0.7 0.92 (0.05) 0.94 (0.07) 0.97 (0.01) 0.93 (0.05)
		0.8 0.92 (0.04) 0.93 (0.06) 0.96 (0.01) 0.92 (0.05)
		0.9	0.91 (0.04)	0.92 (0.06) 0.97 (0.01) 0.91 (0.05)
		1	0.92 (0.04) 0.94 (0.06) 0.96 (0.01) 0.93 (0.06)

Table 3 :

 3 Average ARI and average nonspecificity as a function of q with d 0 = quantile(D, q) for nbconst = 100 and nbconst = 200, with ξ = 0.5. The best results in terms of average nonspecificity are shown in bold.

	nbconst	q	Banana 200	Glass	Iris	Ecoli
	100	0.1 0.94 (0.33)	0.23 (0.38) 0.57 (0.23) 0.27 (0.45)
		0.2 0.93 (0.31)	0.31 (0.36) 0.91 (0.20)	0.46 (0.4)
		0.3 0.92 (0.27)	0.46 (0.31) 0.93 (0.16) 0.71 (0.34)
		0.4 0.86 (0.23)	0.89 (0.28) 0.95 (0.10)	0.8 (0.27)
		0.5 0.84 (0.21)	0.87 (0.23) 0.91 (0.05)	0.83 (0.2)
		0.6 0.84 (0.17)	0.86 (0.16) 0.91 (0.03) 0.83 (0.15)
		0.7 0.79 (0.13) 0.82 (0.11) 0.83 (0.03) 0.83 (0.11)
		0.8 0.74 (0.09) 0.80 (0.11) 0.65 (0.05) 0.85 (0.09)
		0.9 0.74 (0.08) 0.84 (0.11) 0.68 (0.07) 0.86 (0.09)
		1	0.69 (0.26)	0.76 (0.27)	0.66 (0.2)	0.84 (0.25)
	200	0.1 0.99 (0.21)	0.85 (0.28) 0.93 (0.09) 0.24 (0.22)
		0.2 0.97 (0.19)	0.86 (0.25) 0.97 (0.08) 0.46 (0.20)
		0.3 0.97 (0.17)	0.96 (0.22) 0.98 (0.05) 0.73 (0.18)
		0.4 0.97 (0.15)	0.95 (0.19) 0.99 (0.04) 0.82 (0.14)
		0.5 0.95 (0.13)

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

Available at http://prtools.org/disdatasets/index.html.

clustering results when a moderate number of constraints are initially provided. We note that the same technique could be used with other constrained clustering methods such as CECM [2]. In the future, it would be interesting to investigate the relation and the synergies between this new constraint expansion method and active learning techniques [2,12].

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


Zhi-Gang Su

Thierry Denoeux

Yong-Sheng Hao

Ming Zhao

Evidential K-NN Classification with Enhanced Performance via Optimizing A Class of Parametric Conjunctive t-Rules ☆

Keywords: Evidence theory, Dempster-Shafer theory, belief functions, combination rules, pattern recognition, supervised learning

Dempster's rule of combination is commonly used to pool distinct/independent bodies of evidence in the evidential k-nearest neighbor (K-NN) classifier, which sometimes limits the performance of this classifier. To solve this problem, we propose a class of parametric conjunctive combination rules based on a new family of triangular norms with selectable functions and tunable parameters. We show that the performance of the evidential K-NN classifier can be enhanced via this class of so-called parametric conjunctive t-rules when appropriate functions and parameters are selected.

Numerical simulations validate our conclusions.

Introduction

The last four decades have seen the emergence and development of the theory of belief functions, which has gained increasing interest as a conceptual framework for modeling partial knowledge and reasoning under uncertainty, see [4-7, 26-27, 32-35, 38-39] for example, and the literature therein. Among the applications of this theory, the evidential K-NN classifier has been successfully used in a wide range of classification problems [5, 11, 16-20, 34-36, 39].

In the evidential K-NN classifier, Dempster's rule is commonly used to pool bodies of evidence, due to its simplicity. This rule implicitly requires that the bodies of evidence to be combined are distinct [START_REF] Shafer | Dempster's rule of combination[END_REF][START_REF] Shafer | The problem of dependent evidence[END_REF]. In other words, the information sources should be independent. However, it is difficult to guarantee the independence of information sources in many practical applications. How to enhance the performances of the evidential K-NN classifier via optimizing a class of possibly parametric combination rules to account for dependence of the sources is still an open question.

To relax the distinctness/independence assumption, some alternative combination rules have been proposed, see, for instance [1-3, 6, 9, 13 21-25, 29-30, 33]. (Note that we do not aim to review the literature on combination rules.) Among these alternatives, the cautious rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF] is a conjunctive rule based on the least commitment principle (LCP) [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF].

The LCP stipulates that one should never give more beliefs than justified by the available information; it thus promotes a cautious attitude. The cautious rule can be directly derived from the conjunctive weight function [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], an equivalent representation of a non-dogmatic belief function. After providing a new justification of conjunctive rule in [START_REF] Pichon | Belief functions: Canonical Decompositions and Combination Rules[END_REF], Pichon and Denoeux generalized it and proposed the triangular-norm (t-norm for short) based conjunctive rules, called ☆This work is supported in part by the National Natural Science Foundation of China (No. 51676034), and fully by the Key Project of Yunnan Power Grid Co. Ltd. (YNYJ2016043). Email addresses: zhigangsu@seu.edu.cn (Z.-g. Su); thierry.denoeux@utc.fr (T. Denoeux); haoys@seu.edu.cn (Y.-s. Hao); zming64@163.com (M. Zhao) conjunctive t-rule [START_REF] Pichon | Belief functions: Canonical Decompositions and Combination Rules[END_REF][START_REF] Pichon | T-norm and Uninorm-based combination of belief functions[END_REF][24]. They showed that the cautious rule can be seen as a particular conjunctive t-rule when choosing a particular t-norm defined on (0, +∞], whereas the conjunctive rule belongs to a family of rules defined by selecting a suitable uninorms on (0, +∞] having 1 as neutral element.

As remarked in [START_REF] Dubois | On the unicity of Dempster's rule of combination[END_REF], having only one rule is "not very fortunate in the scope of Artificial Intelligent (AI), where one tries to simulate the human mind rather than force behavior rules issued from formal arguments". Indeed, the descriptive nature of AI calls for more flexibility in the choice of combination rules, provided that those other rules satisfy at least a few basic and reasonable requirements. From this viewpoint, the conjunctive t-rules or any other alternatives should be investigated in depth so as to obtain some new combination rules. In fact, the conjunctive t-rules were formulated using a particular family of t-norms defined on (0, +∞]. Whereas the current conjunctive t-rules seem to have sufficient ability to account for the dependence of bodies of evidence, it will be shown in this paper that some more effort is needed so that these rules can be used to enhance the performance of the evidential K-NN classifier. Motivated by the above considerations, this paper aims to enhance the performance of the evidential K-NN classifier by optimizing a class of parametric combination rules including conjunctive t-rules, called parametric conjunctive t-rules (PCTR). More precisely, a scheme is first proposed to construct a t-norm with selectable functions and tunable parameters. With the help of this new t-norm, a class of parametric conjunctive t-rules is then proposed and applied to pool bodies of evidence in the evidential K-NN classifier. We will show that the proposed parametric conjunctive t-rules can enhance the performance of the evidential K-NN classifier if appropriate functions and parameters are selected.

The rest of this paper is organized as follows. The theory of belief function is first briefly recalled in Section 2. The parametric conjunctive t-rules are proposed after constructing a class of t-norms in Section 3. In Section 4 we conduct some numerical experiments to study the performances of the proposed combination rules and the evidential K-NN classifier. The last section concludes the paper.

Preliminaries: Background on belief functions

In this section, we briefly recall some notions of the theory of belief functions [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Smets | The transferable belief model[END_REF] needed in the rest of the paper. Given a frame of discernment Ω = {ω 1 , ω 2 , ..., ω c }, a mass function or basic belief assignment (BBA) m is defined as a mapping from 2 Ω to [0, 1] such that ( )

1 A m A ⊆Ω =  , (1)
where the subsets A of Ω such that m(A) > 0 are called the focal sets of m.

A BBA is said to be categorical if it has only one focal set. In particular, the vacuous BBA verifies m(Ω) = 1: it corresponds to complete ignorance. A BBA is said to be non-dogmatic if Ω is a focal set. A BBA m is subnormal if the empty set φ is a focal set, and normal otherwise. A subnormal BBA m such that m(φ) < 1 can be transformed into a normal BBA m * by the normalization operation defined as:

( ) ( ) ( ) * , , 1 0, . m A if A m A m otherwise φ φ  ≠ ⊆ Ω  = -    (2)
According to Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF], function m is said to be a simple BBA (SBBA) if it has the following form: m(A) = 1 ̶ w, m(Ω) = w for some A ⊂ Ω and some w ∈ [0, 1]. Smets [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF] defined a generalized SBBA (GSBBA) as a function μ:

2 Ω → (0, +∞) such that ( ) ( ) ( ) { } 1 , , 0, 2 \ , , A w w B B A μ μ μ Ω  = -  Ω =   = ∀ ∈ Ω  (3)
for some A ≠ Ω and w ∈ (0, +∞). A SBBA or GSBBA can be denoted by A w for simplicity. Smets [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF] showed that any non-dogmatic BBA m admits a canonical decomposition as the combination of GSBBAs A w(A) focused on each of the strict subsets A of Ω with weights w(A). Function w: 2 Ω \ {Ω} → (0, +∞) is called the conjunctive weight function associated to m. A BBA is said to be separable if it is canonically decomposed into SBBAs, i.e., if w(A) ≤ 1 for all A.

There are other equivalent representations of a BBA such as the belief, plausibility, and commonality functions. In particular, the commonality function is defined as

( ) ( ), A B q A m B A ⊆ = ⊆ Ω  . (4)
The weights w(A) in Eq. ( 3) can be obtained for every A ⊂ Ω according to ( ) ( ) ( )

1 1 B A A B w A q B -+ - ⊆ = ∏ . ( 5
)
The combination of bodies of BBAs plays a critical role in the theory of belief functions. Let m 1 and m 2 be two BBAs. The conjunctive combination of m 1 and m 2 , denoted by ○ ∩ , results in a new BBA defined as

m 1 ○ ∩ 2 (A) ( ) ( ) 1 2 , . B C A m B m C A ∩ = = ⊆ Ω  (6)
The conjunctive rule allows some mass to be assigned to the empty set. Dempster's rule, denoted by ⊕ , consists in the conjunctive rule followed by normalization [START_REF] Cattaneo | Belief functions combination without the assumption of independence of the information sources[END_REF]. Both rules are commutative, associative and admit the vacuous BBA as a unique neutral element. The conjunctive rule can be expressed using conjunctive weight functions as

m 1 ○ ∩ 2 (A) = ○ ∩ ( ) ( ) 1 2 w A w A A A × ⊂Ω , (7)
where × denotes the product. By using the minimum, denoted by ∧, instead of the product, the cautious rule can be derived for two non-dogmatic BBAs as

m 1 ○ ∧ 2 (A) = ○ ∩ ( ) ( ) 1 2 w A w A A A ∧ ⊂Ω . ( 8
)
Pichon and Denoeux provided a new justification of the conjunctive and cautious combination rules in [24], and proposed the so-called conjunctive t-rules by replacing the minimum ∧ by another t-norm on (0, +∞] such as [START_REF] Pichon | Belief functions: Canonical Decompositions and Combination Rules[END_REF][START_REF] Pichon | T-norm and Uninorm-based combination of belief functions[END_REF] x

 ′ y = 1 , 1 , 1 1 1 1 1 , 1, , ,
x y x y

x y x y

x y o t h e r w i s e

- ∨ ≤          ′ -- - ∧ >                ∧    (9)
for all x, y in (0, +∞], where ˅ denotes the maximum operator, and  and ′  are t-norms on [0, 1] [START_REF] Klement | Triangular norms, Position paper 1: basic analytical and algebraic properties[END_REF].

Finally, the pignistic transformation [START_REF] Smets | The transferable belief model[END_REF] can be used to transform a combined BBA into a probability measure in order to make decision. It is defined as

{ } ( ) ( ) * q m q A m A BetP A ω ω ∈ ⊆Ω =  , ( 10
)
for all ω in Ω.

Main results: Rules and Method

After introducing a family of t-norms and construct methods, a class of parametric conjunctive t-rules will first be proposed from the conjunctive t-rules in Section 3.1. The evidential K-NN classifier based on parametric conjunctive t-rules will then be presented in Section 3.2.

Parametric conjunctive t-rules.

Definition 1 [START_REF] Pichon | T-norm and Uninorm-based combination of belief functions[END_REF] A t-norm on (0, +∞] is a binary operation on (0, +∞] that is commutative, associative, monotonic, and admits +∞ as neutral element.

Generalizing Eq. ( 9), the following proposition provides a scheme to construct a class of t-norm on (0, +∞] from t-norms on [0, 1] as well as some selectable functions.

Proposition 1 Consider an increasing function ( ) g x

1 : [0, 1] → [0, 1] such that g 1 (0) = 0, g 1 (1) = 1, and a strictly decreasing function ( )

g x 2 : [1, +∞] → [0, 1] such that (1) 1 g = 2 , 2 2
( ) lim ( ) 0 x g g x →+∞ +∞ = = . Let 1 2 ( ) g x - be the
inverse function of g 2 (x). Then, the binary operation defined by the following equation is a t-norm on (0, +∞]

x  g i ′ y = ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 2 2 2 , 1 , , 1 ,
, ,

g x g y x y g N N g x N g y x y x y o t h e r w i s e - ∨ ≤    ′ ∧ >   ∧     (11)
where  and ′  are classical positive t-norms on [0, 1] such that x  y > 0, ∀ x > 0, y > 0, and N(x) is the negation

operation on [0, 1] such that N(x) = 1-x.
Proof: See in Appendix.

Remark 1 Proposition 1 provides a scheme to construct t-norms on (0, +∞]. By choosing different functions g i (x) and t-norms  and ′  on [0, 1], infinite families of t-norms (0, +∞] can be obtained. The t-norms  and ′  can be selected, e.g., as the minimum, product, Dubois-Prade, and Frank t-norms defined, respectively, as

( ) ( ) , min , M T x y x y = ,
( )

, P T x y xy = , ( ) { } [ ] , , 0 , 1 max , , DP xy T x y x y λ λ = ∈ , and
( ) ( )( ) 1 1 , log 1 1 x y F T x y λ λ λ λ   - -   = +   -  
with λ >0 and λ ≠ 1. If  = ′  = ∧, then we recover the minimum. It is evident that Eq. ( 9) is a special case of the t-norms (11) with g 1 (x) = x and g 2 (x) = x -1 . There are many choices of functions g i (x), i =1, 2. In this paper, we use the power function g 1 (x) = x β with positive constant β, and exponential or power functions g 2 (x) such that g 2 (x) = e χ(1-x) or g 2 (x)=x -χ with positive constant χ. Fig. 1 shows the curves of g i (x) in some cases. Remark 2 Note that, as will be seen, all BBAs to be combined in the evidential K-NN classification setting are obtained by discounting categorical BBAs and are, therefore, separable. Hence, the t-norm (11) can be simplified as

follows x  g 1  y = ( ) ( ) 1 1 g x g y  , (12)
for all x, y in (0, 1], and t-norm

 on [0, 1].
In what follows, we focus on special case [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF], although some definitions and propositions are still introduced based on Proposition 1, which is interesting for its own sake. The following example illustrates some t-norms constructed using Eq. ( 12).

Example 1

Suppose g 1 (x) = x β and  = T DP . We can have the following t-norm: In the following, we will simplify the notation  g i ′ and  g 1  as  whenever there is no risk of confusion.

x  g 1  y = ( ) [ ] , , , 0,1
With the help of Proposition 1, we are ready to present the parametric conjunctive t-rules.

Proposition 2 Let  be the t-norm defined in Proposition 1, and let w 1 and w 2 be the conjunctive weight functions associated to any two non-dogmatic BBAs m 1 and m 2 . Then, the weight function defined by

w 1 ○  w 2 (A) ( ) ( ) 1 2 , w A w A A = ∀ ⊂ Ω  ,
is a conjunctive weight function associated to some non-dogmatic BBA m 1 ○  w 2 .

Proof: See in Appendix.

Definition 2 (Parametric conjunctive t-rules, PCTR) Let  be the t-norm in Proposition 1, and let w 1 and w 2 be the conjunctive weight functions associated to any two non-dogmatic BBAs m 1 and m 2 . The parametric conjunctive combination of m 1 and m 2 can be calculated according to

m 1 ○  w 2 (A) = m 1 ○  , , i g ′   w m 2 (A) = ○ ∩ ( ) ( ) 1 2 w A w A A A ⊂Ω  . ( 13
)
Remark 3 The t-norm based combination rules in Definition 2 are called parametric conjunctive t-rules. They generalize the conventional conjunctive t-rules by introducing selectable functions g i (x) with tunable parameters. When g 1 (x) = x and g 2 (x) = x -1 , the parametric conjunctive t-rules degenerate to the conventional conjunctive t-rules. As will be seen in Section 4, the selectable functions g i (x) provide more flexibly to deal with non-distinct bodies of evidence.

Remark 4

The parametric conjunctive t-rules have two limitations. First, they do not have the vacuous BBA as neutral element. Second, the BBAs to be combined need to be non-dogmatic as only non-dogmatic BBAs have a unique conjunctive canonical decomposition. In practice, however, it may be argued that most states of belief, being based on imperfect and not entirely conclusive evidence, should be represented by non-dogmatic BBAs even if the mass assigned to Ω is very small.

Evidential K-NN classifier via PCTR

We consider the problem of classifying patterns into c classes. The set of classes is denoted by Ω = {ω 1 ,ω 2 ,…, ω c }.

The available information is assumed to consist of a training set TR

= {(x i , m i ) | i =1, 2, …, n } with d-dimensional
patterns x i and their corresponding class labels represented by mass functions m i ({ω q }) = 1.

Let x be a new vector to be classified on the basis of the information contained in TR. Each pair (x i , m i ) constitutes a distinct body of evidence regarding the class membership of x. If x is "close" to x i , according to the relevant metric d(., .) (e.g., the Euclidean metric), we will be inclined to believe that both vectors belong to the same class. On the contrary, if d(x, x i ) is very large, the consideration of x i will leave us in a situation of almost complete ignorance concerning the class of x. Consequently, this body of evidence may be postulated to induce a BBA m[x|x i ](•) over Ω defined by

( ) ( ) ( ) { } ( ) ( ) , , , 1 , , , 0,
.

x x x x x x q i i q i q i i d A m A d A otherwise αφ ω αφ  =     = - =Ω       ( 14
)
where α is a parameter such that 0< α <1, and φ q is a decreasing function verifying ( )

0 1 q φ = , and
( )

lim 0 i q i d d φ →∞ = . (15)
A popular choice for decreasing function φ q is [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] ( ) ( )

2 exp q i q i d d φ γ = - , (16)
where γ q is a positive parameter associated to class ω q .

As a result of considering each training pattern in turn, we obtain n BBAs that can be combined by using the parametric conjunctive t-rules to synthesize our final belief regarding the class of x.

m TR     x = 1 x x m     ○  , , i g ′   w  ○  , , i g ′   w x x n m     . ( 17
)
Since training patterns situated far from x actually provide very little information, it is sufficient to consider the k-nearest neighbors of x in TR. Furthermore, when m[x|x i ] is simple, we may obtain the following simple expression for

m[x|x i ]: { } ( ) ( ) 1 , x x x x q i i d i q m αφ ω -  =   (18)
Accordingly, [START_REF] Liu | A new belief-based k-nearest neighbor classification method[END_REF] becomes to

K m S     x = ○ ∩ 1 c q= { } q ω  ( ) { } ( ) ( ) ( ) 1 1 , x x x q i i i S K g d αφ ∈ - , (19)
where S K (x) contains the indexes of the k-nearest neighbors of x in TR.

Finally, the predicted label of pattern x can be obtained as

( ) { } ( ) 1 arg max x x q m S q c K BetP ω ω     ≤ ≤ = . ( 20
)
Remark 5 Due to the inequality g 1 (1-αφ q (d i (x,x i ))) ≤ 1, BBAs m[x|x i ] are separable. Hence, the parametric conjunctive t-rules depend neither on the t-norm ′  nor on function g 2 (x) in the classification setting, as stated in Remark 2. In the performance analysis of evidential K-NN classifier, we will focus on the application of ( 12) to optimize parameters in function g 1 (x) and the t-norm. In this case, only parameter in the t-norm needs to be optimized to enhance the performance of the evidential K-NN classifier when using the conventional conjunctive t-rule (i.e., PCTR with g 1 (x) = x, see PCTR-λ in Table 3). This is the main difference between our parametric conjunctive t-rules and the conventional conjunctive t-rules.

Simulations

This section consists of two parts. In Section 4.1, a numerical example is used to show that the true parametric conjunctive t-rule can be recovered by minimizing a distance function. In Section 4.2, we assess the performance of the evidential K-NN classifier with the parametric conjunctive t-rules.

Approximation of a combination rule by a parametric conjunctive t-rule

This example shows how to find an optimal parametric conjunctive t-rule when combining two BBAs. Assume that the BBAs m 1 and m 2 have been provided by two sensors. (Note that m 1 and m 2 are not assumed to be independent, because we know nothing about the dependence of the two sensors.) Expert knowledge regarding the true value of the variable of interest is represented by BBA m e , as shown in Table 1. The BBA m e was artificially constructed by combining m 1 and m 2 using the parametric conjunctive t-rule in which Frank t-norm with parameter λ = 0.5 is used and both g 1 (x) =

x 0.8 and g 1 (x) =e x(x -1) are considered. We wish to find an optimal combination rule with Frank t-norm T F (λ) and selectable function g 1 (x) = x β such that the combination of m 1 and m 2 approaches as close as possible to m e . Parameter λ varies from 0 to 1 with step size 0.1.

The distance between m e and combination m 12 is measured by Jousselme's evidential distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] defined by ( ) ( ) ( )

where superscript T denotes matrix transposition and matrix D is defined by Fig. 3 shows the evidential distance between the artificial BBA and the combination of m 1 and m 2 using PCTR with power function as selectable function. Fig. 3(a) shows that the optimal rule can be exactly found if the selectable function g 1 (x) = x β belongs to the same parametric family as the function used to construct the artificial BBA.

( ) 1, , , . A B A B D A B otherwise A B φ = =   ∩ =   ∪  , 0
Alternatively, it can be seen from Fig. 3(b) that the combination using PCTR with appropriate parameter (i.e., λ = 0.5, β = 1.81) can get very close to the artificial BBA even when expert knowledge is unknown a priori (i.e., a completely unknown selectable function e x(x-1) is used when constructing the artificial BBA). These results show that an optimal rule can be found or approximated through designing selectable functions g i (x) with appropriate parameters, even when nothing about the true combination rule is known in advance. Note that similar results can be obtained for non-separable BBAs.

Performance Evaluation

The objective of this section is to show that the performance of the evidential K-NN classifier can be enhanced by using the parametric conjunctive t-rules. In this section, the function g 1 (x) = x β and parametric t-norm  = T DP (λ) are considered. Note that function g 2 (x) and t-norm ′ cannot play any role in this classification setting, as already remarked in Section 3.2.

To implement the evidential K-NN classifier, practical issues need to be addressed. In particular, parameters k, α, γ q (q = 1, 2, ..., c), β and T DP (λ) need to be preset in advance. There is some literature [34][START_REF] Su | Improved adaptive evidential k-NN rule and its application for monitoring level of coal powder filling in ball mill[END_REF][START_REF] Su | Immune genetic algorithm-based adaptive evidential model for estimating unmeasured parameter: Estimating levels of coal powder filling in ball mill[END_REF][START_REF] Zouhal | An evidence-theoretic k-NN rule with parameter optimization[END_REF] focused on optimizing the parameters k, α and γ q (q = 1, 2, ..., c). However, the results that will be presented in this section are based on the following simple heuristic method [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF]: α = 0.95, and γ q equal to the inverse of the mean Euclidean distance between training patterns belonging to class ω q . The parameter k was set to 7. Hence, we focus on optimizing parameters λ and β.

For convenience, assume that parameter λ takes values in {0, 0.1, 0.2, ..., 1.0}, whereas parameter β varies from 0.5 to 2 by step size 0.1. The optimal parameters λ and β are to maximize the classification accuracy P(λ, β) defined by

( ) ( ) ( ) 1 1 , x n i i i P I u n λ β ω = = -  , ( 22
)
where u i is the true class label of object x i , and I(.) is an indicator function defined by I(0) = 1, and In the experiments reported in this section, eight UCI datasets with continuous attributes were selected, as shown in Table 2, given the fact that the distance measure d i (., .) in the evidential K-NN classifier is sensitive to discrete attributes. The precise class labels in these eight UCI datasets were encoded as categorical BBAs m i , i.e., m i ({ω q }) = 1 if pattern x i belongs to class ω q , otherwise 0.

I(x) = 0 if x ≠ 0.

Experiment 1: Approximate accuracy

This experiment aims to study the performance of the evidential K-NN when parameters (λ, β) take different values.

In the experiment, all eight UCI datasets in Table 2 are considered. For each dataset, the Leave-One-Out (LOO) classification accuracy was computed. More precisely, we left each sample out and used the remaining samples to predict the possible label of this sample with a given pair (λ, β); this procedure was repeated until we had tested all samples. The LOO classification accuracy for each pair (λ, β) can be calculated as the ratio of correctly labeled samples to the total number of samples. The conjunctive, cautious and conjunctive t-rules (i.e., PCTR-λ in Table 3) were also implemented under the same conditions. 3, in which the best results are shown in bold.

From Table 3, it can be seen that the parametric conjunctive t-rules outperform the cautious and conjunctive rules in most cases. This observation suggests that parametric conjunctive t-rules can improve the performance of the evidential K-NN classifier when optimizing the parameters λ and β simultaneously. From Fig. 4, we can see that there is more than one optimal solution in most cases, and optimal LOO classification accuracy can be achieved when parameter β ≠ 1, which indicates that function g 1 (x) has a critical influence on the performance of PCTR.

Experiment 2: Testing accuracy

This second experiment intends to assess the testing/predictive accuracy of the evidential K-NN classifier. In this experiment, we still considered the eight datasets in Table 2. However, a double cross-validation loop strategy [START_REF] Filzmoser | Repeated double cross validation[END_REF] was implemented on each dataset in order to avoid bias in the selection procedure. The procedure is summarized in Fig. 5.

Input: Arbitrary dataset S and the ranges of (λ, β) = [0, 0.1, …, 1.0]×[0.5, 0.6, …, 2.0] ∈R 11×16 .

Repetition Loop: For p = 1 to n REP % n REP is the number of repetition Randomly split S in k 1 non-overlapping folds S (1) , …, S (k1) with possible equal size;

Outer Loop: For i = 1 to k 1 1. Take S (i) as TEST set, and merge the remaining (k 1 -1) folds into S (-i) = S -S (i) as CALIBRATION set;

2. Randomly split the calibration set in k 2 non-overlapping folds C (1) , …, C (k2) with possible equal size;

3. Inner Loop: For j = 1 to k 2 1) Take C (j) as VALIDATION set and the remaining (k 2 -1) folds C (-j) = C -C (j) as TRAINING set;

2) Calculate P (j) ( λ, β) ∈R 11×16 according to [START_REF] Pichon | Belief functions: Canonical Decompositions and Combination Rules[END_REF] for validation set C (j) based on training set C (-j) ;

3) Select (λ*, β*) according to the following standard error-like rule [

where P(λ, β) is a column vector by straightening matrix ( ) ( ) 4. Note that there is sometimes more than one optimal selection according to criterion [START_REF] Pichon | T-norm and Uninorm-based combination of belief functions[END_REF]. In this case, the best performance among these optimal selections is considered. Furthermore, the surfaces of classification accuracies varying with λ and β on these datasets are similar as those in Fig. 4; therefore, they are omitted due to space constraints.

From Table 4, it can be seen that the parametric conjunctive t-rules outperform the conjunctive and cautious rules in most cases. For the diabetes and iono datasets, the mean classification accuracy obtained by PCTR-(λ, β) is a little lower than that obtained using PCTR-λ. When we look into the details, we find that the training accuracy using PCTR-(λ, β) is higher than that by using PCTR-λ, which indicates that there may be over-fitting when learning PCTR-(λ, β). To further investigate the performance of the PCTR-based classifier, we compared it with the popular Evidence-Theoretic k-nearest neighbor classifier with parameter Optimization (ETO) [START_REF] Zouhal | An evidence-theoretic k-NN rule with parameter optimization[END_REF], in which the conjunctive rule is used and parameters k and γ q are optimized rather than fixed. We used the same double cross-validation algorithm as above. As shown in Fig. 6, the PCTR-(λ, β)-base classifier outperforms, or at least is comparable with ETO in most cases even though parameters k and γ q are fixed. Remark 6 When g 1 (x) = x, the PCTR rule can degenerate to the cautious rule, the conjunctive rule or the conventional conjunctive t-rules. Consequently, the PCTR can be at least as good as these rules. However, we can see that, for instance on the datasets diabetes and iono, the PCTR-λ rule has the best performance. This means that there is some over-fitting, even though a standard error-like method (23) has been adopted. Furthermore, the proposed PCTR may not be able to enhance the performance of the evidential K-NN classifier for all datasets. When the conjunctive (t-)rule is not outperformed by PCTR, it may be possible to find other parametric families of rules that perform better, as mentioned in [START_REF] Pichon | Belief functions: Canonical Decompositions and Combination Rules[END_REF].

Conclusions

In this paper, we first introduced a scheme to construct a new family of t-norms with selectable functions satisfying some conditions. Using this family of t-norms, a class of parametric conjunctive t-rules for combining belief functions has been proposed. The parametric conjunctive t-rules, which encompass the cautious and conjunctive rules, can be used to enhance the performance of the evidential K-NN classifier when appropriate selectable functions and tunable parameters are selected.

The performance of the PCTR-based K-NN classifier depends on the choice of the number k of neighbors and on scale parameters γ q . Hence, optimizing parameters k and γ q could bring further classification accuracy improvements.

Furthermore, we used the power function for g 1 (x), but different forms of selectable functions could be investigated as well. Finally, in this paper we optimized parameters (λ, β) using a greedy search procedure, but this strategy is suboptimal. Through global optimization of all parameters in the PCTR rule, it might be possible to further enhance the performance of the evidential K-NN classifier. This research direction is left for future work.

, , g x g y x y g g x g y x y

x y o t h e r w i s e

- ∨ ≤    ′ ∧ >   ∧    ⊥ (24)
Similar as before, the symbol  g i  ⊥′ is shorten as  if no confusions occur in the following proof.

 Commutativity

As can be seen from formula (24), the binary operation  is defined by using classical norms , ⊥′ and ∧. Because of the commutativity of , ⊥′ and ∧, operation  is also commutative.

 Neutral element If x ≤ 1, x  +∞ = x ∧ +∞ = x; If x ≥ 1, x  +∞ = g 2 -1 (g 2 ( x) ⊥′ g 2 (+∞))= g 2 -1 (g 2 ( x) ⊥′ 0)= g 2 -1 (g 2 ( x)) = x.
From the commutativity of , we have +∞  x = x  +∞ = x.

 Monotonicity

Without loss of generality, suppose w ≥ y, x ≥ z.

-Suppose w  x = g 1 (w)g 1 (x), then y  z = g 1 (y)g 1 (z) because of 1 ≥ w ≥ y, 1 ≥ x ≥ z. By the monotonicity of and g 1 (.), we have w  x ≥ y  z.

-Suppose w  x = w ∧ x, then there exist 1 ≥ w or 1 ≥ x, correspondingly, there also exist 1 ≥ y or 1 ≥ z.

⎯ If y  z = y ∧ z, we have w  x = w ∧ x ≥ y ∧ z = y  z because of the monotonicity of ∧;

⎯ If y  z = g 1 (y)  g 1 (z), we have g 1 (y)  g 1 (z) ≤g 1 (y) ∧ g 1 (z) because the minimum ∧ is the maximum t-norm on (0, +∞]. Without loss of generality, suppose w ∧ x = x. We have ⎯ If y ≤ z, then y ∧ z = y. Because x ≥ z, we can obtain x ≥ y ∧ z. Thus, g 1 (w)∧ g 1 (x) ≥g 1 (y) ∧ g 1 (z) ≥g 1 (y)g 1 (z).

⎯ If y > z, then y ∧ z = z. and y ∧ z = z ≥ y  z. Because x ≥z, one has x ≥ y ∧ z. Thus, g 1 (w)∧ g 1 (x) ≥g 1 (y) g 1 (z) -Suppose w  x = g 2 -1 (g 2 (w) ⊥′ g 2 (x)), then we have w ∧ x ≥ 1 and w  x ≥ 1.

⎯ If y  z = g 2 -1 (g 2 (y) ⊥′ g 2 (z)), then w x ≥ y  z due to the monotonicity of ⊥′ and function g 2 ;

⎯ If y  z = y ∧ z, then w x ≥ 1 ≥ y ∧ z = y  z;

⎯ If y  z = g 1 (y)  g 1 (z), together with y ∨ z ≤ 1, then g 1 (y) g 1 (z) ≤ 1. Thus, w  x ≥ 1 ≥ g 1 (y)  g 1 (z).

Thus, we have w  x ≥ y  z.

 Associativity

Without loss of generality, suppose x ≥ y ≥z.

-If x ≤ 1, y ≤ 1, z ≤ 1, then (x  y)  z = (g 1 (x)  g 1 (y))  g 1 (z) = g 1 (x)  (g 1 (y)  g 1 (z)) = x  (y  z).

-If x > 1, y > 1, z > 1, we have (x  y)  z = g 2 -1 (g 2 (x) ⊥′ g 2 (y))  g 2 (z) = g 2 -1 (g 2 (g 2 -1 (g 2 (x) ⊥′ g 2 (y))) ⊥′ g 2 (z)) = g 2 -1 (g 2 (x) ⊥′ g 2 (y) ⊥′ g 2 (z)),

x  ( y  z) = x  g 2 -1 (g 2 (y) ⊥′ g 2 (z)) = g 2 -1 (g 2 (x) ⊥′ g 2 (g 2 -1 (g 2 (y) ⊥′ g 2 (z)))) = g 2 -1 (g 2 (x) ⊥′ g 2 (y) ⊥′ g 2 (z)).

Thus, we have (x  y)  z = x  ( y  z).

-If x > 1 > y ≥ z, then we have

x  (y  z ) = x  (g 1 (y)  g 1 (z)) = x ∧ (g 1 (y)  g 1 (z)) = g 1 (y)  g 1 (z), and (x  y)  z = (x ∧ y)  z = y  z = g 1 (y)  g 1 (z). Thus, (x  y)  z = x  ( y  z). Thus, (x  y)  z = x  (y  z)。 Finally, it is evident that x  y > 0 because of x, y∈(0, +∞]. ▄

Proof of Proposition 2

The proof is similar as that of Proposition 4.3 in [START_REF] Pichon | Belief functions: Canonical Decompositions and Combination Rules[END_REF]. It is given here for completeness.

Firstly, we validate the premise that the minimum on (0, +∞] is the largest . This is evident because any t-norm  on (0, +∞] has +∞ as neutral element and is monotonic. Hence, we have x  y ≤ x  +∞ = x and x  y ≤ +∞  y = y for all x, y ∈(0, +∞]. So, it results in x  y ≤ x ∧ y. Thus, we have w 1 ○  w 2 (A) ≤ w 1 ○ ∧ w 2 (A), A ∀ ⊂ Ω .

From Lemma 1 in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence[END_REF], if m is a non-dogmatic BBA with conjunctive weight function w, and if w′ is a mapping from { } ( )

2 \ 0,
Ω Ω → +∞ such that ( ) ( )

w A w A ′ ≤
for all A ⊂ Ω , then w′ is the conjunctive weight function of some non-dogmatic BBA m′ .

Consequently, w 1 ○  w 2 is a conjunctive weight function since w 1 ○ ∧ w 2 is a conjunctive weight function. ▄

Fig. 1

 1 Fig. 1 Curves of functions (a) g 1 (x) = x β and (b) g 2 (x) = e χ(1-x)

Fig. 2

 2 Fig. 2 Surfaces (top) and contours (bottom) of t-norms in Example 1

Fig. 3

 3 Fig. 3 Evidential distance between m e and combined BBA m 12 using PCTR. (a): true combination rule with selectable function g 1 (x) = x β ; (b): true combination rule with selectable function g 1 (x) =e x(x -1) .

Fig. 4 LOO

 4 Fig. 4 LOO classification accuracy varying with parameters λ and β

4 .

 4 Evaluate the classification accuracy P (i) (λ*, β*) on the test set S (i) ; 5. Average the k 1 test accuracies P (i) (λ*, β*); Output: A group of n REP double cross-validation classification accuracies.

Fig. 5

 5 Fig. 5 Double cross-validation algorithm

Fig. 6

 6 Fig. 6 Comparisons between PCTR-(λ, β) and ETO

-

  If x ≥ y > 1 > z, then we have x  (y  z) = x  (y ∧ z) = x  z = x ∧ z = z, and (x  y) z = g 2 -1 (g 2 (x) ⊥′g 2 (y)) ∧ z = z. Thus, (x  y)  z = x  ( y z)。 -If x = 1 or y=1 or z = 1,suppose x = 1, then we have x  (y  z) = 1  (y  z)= y  z, and (x  y)  z = (1  y)  z = y  z.

Table 1

 1 Artificial BBAs defined on Ω = {a, b, c} with different selectable functions

	A	m 1 (A)	m 2 (A)	m e (A) with different selectable function g 1 (x) g 1 (x) = x 0.8 g 1 (x) =e x(x -1)
	φ	0	0	0	0
	{a}	0	0	0	0
	{b}	0.3	0.4	0.4858	0.7708
	{a, b}	0	0	0	0
	{c}	0	0	0	0
	{a, c}	0	0	0	0
	{b, c}	0.4	0.4	0.3950	0.2176
	Ω	0.3	0.2	0.1192	0.0116

Table 2

 2

		Data description
	No.	Datasets	Abbreviation	Samples	Continuous attributes	Classes
	1	Balance-scale	Balance	626	4	3
	2	Breast cancer Wisconsin Breastw	699	9	2
	3	Diabetes	Diabetes	768	8	2
	4	Ionosphere	Iono	355	34	2
	5	Iris	Iris	153	4	3
	6	Sonar	Sonar	208	60	2
	7	Vehicle	Vehicle	848	18	4
	8	Wine	Wine	178	13	3

Table 3

 3 Optimal LOO classification accuracies of the evidential K-NN classifier *1

	Datasets	Cautious rule	conjunctive rule	PCTR-λ	PCTR-(λ, β)
	Balance	0.6272	0.8767	0.8768	0.8848
	Breastw	0.9678	0.9707	0.9707	0.9736
	Diabetes	0.6680	0.7474	0.7487	0.7539
	Iono	0.9117	0.8917	0.9345	0.9345
	Iris	0.9400	0.9600	0.9600	0.9800
	Sonar	0.8462	0.8269	0.8510	0.8798
	Vehicle	0.6489	0.7222	0.7234	0.7234
	Wine	0.9831	0.9775	0.9888	0.9888

*1. PCTR-λ means that only parameter λ in T DP is optimized when g 1 (x)=x β with β = 1. In this case, PCTR-λ is equivalent to conjunctive t-rule.

Table 4

 4 Classification accuracies estimated by double cross-validation

	Datasets	Cautious rule	Conjunctive rule	PCTR-λ	PCTR-(λ, β)
	Balance	0.6313 ± 0.0050	0.8747 ± 0.0048	0.8750 ± 0.0050	0.8851 ± 0.0050
	Breastw	0.9682 ± 0.0007	0.9712 ± 0.0013	0.9712 ± 0.0012	0.9712 ± 0.0022
	Diabetes	0.6692 ± 0.0082	0.7377 ± 0.0057	0.7464 ± 0.0061	0.7441 ± 0.0064
	Iono	0.9084 ± 0.0053	0.8904 ± 0.0038	0.9380 ± 0.0044	0.9352 ± 0.0052
	Iris	0.9413 ± 0.0028	0.9520 ± 0.0069	0.9527 ± 0.0080	0.9700 ± 0.0085
	Sonar	0.8403 ± 0.0089	0.8067 ± 0.0142	0.8388 ± 0.0118	0.8748 ± 0.0107
	Vehicle	0.6488 ± 0.0087	0.7123 ± 0.0058	0.7170 ± 0.0058	0.7316 ± 0.0059
	Wine	0.9675 ± 0.0099	0.9771 ± 0.0041	0.9804 ± 0.0071	0.9821 ± 0.0058

Acknowledgement

The authors are grateful to the contributions of the editors and two anonymous referees.

Appendix

Proof of Proposition 1

With x, y ∈ [1, +∞], we have g 2 (x), g 2 (y) ∈ (0, 1]. In a similar way,

. By employing the dual operation ⊥′ of ′  and negation operation N, we have

can be rewritten as