Violaine Antoine
email: violaine.antoine@uca.fr

Jose A Guerrero

Jiarui Xie

Fast Semi-supervised Evidential Clustering

Keywords: Evidential clustering, label constraints, constrained clustering, theory of belief functions, optimization

Semi-supervised clustering is a constrained clustering technique that organizes a collection of unlabeled data into homogeneous subgroups with the help of domain knowledge expressed as constraints. These methods are, most of the time, variants of the popular k-means clustering algorithm. As such, they are based on a criterion to minimize. Amongst existing semi-supervised clusterings, Semi-supervised Evidential Clustering (SECM) deals with the problem of uncertain/imprecise labels and creates a credal partition. In this work, a new heuristic algorithm, called SECM-h, is presented. The proposed algorithm relaxes the constraints of SECM in such a way that the optimization problem is solved using the Lagrangian method. Experimental results show that the proposed algorithm largely improves execution time while accuracy is maintained.

Introduction

Clustering is a knowledge discovery approach that aims at grouping objects according to a notion of similarity based on the characteristics of the objects.

Clustering algorithms are divided into two families: hierarchical clustering that builds a hierarchy of clusters and partitional clustering that generates disjoint subsets of the data. Partitional clustering methods include k-means and its variants that try to minimize an intraclass inertia with respect to constraints on the partition. The k-means algorithm, which assigns an object to a unique cluster, has been shown to be useful in various domains such as Internet of Things [START_REF] Tsai | Seira: An effective algorithm for iot resource allocation problem[END_REF], time series [START_REF] Sun | A decomposition-clustering-ensemble learning approach for solar radiation forecasting[END_REF], recommender systems [START_REF] Bilge | A scalable privacy-preserving recommendation scheme via bisecting k-means clustering[END_REF][START_REF] Zahra | Novel centroid selection approaches for kmeans-clustering based recommender systems[END_REF], among others. However, the obtained partition, called hard or crisp partition, is unable to express uncertainties regarding the class membership of an object. Such information is particularly interesting in case, for instance, of overlapped classes. Thus, modifications of the k-means algorithm have been proposed in order to generate a soft partition. The most popular extension corresponds to the Fuzzy c-means (FCM) that produces a probabilistic partition. It has been applied in many applications [START_REF] Li | 3d magnetization inversion using fuzzy c-means clustering with application to geology differentiation[END_REF][START_REF] Xue | Application of fuzzy c-means clustering to prtr chemicals uncovering their release and toxicity characteristics[END_REF][START_REF] Dongdong | Semantic clustering fuzzy c means spectral model based comparative analysis of cardiac color ultrasound and electrocardiogram in patients with left ventricular heart failure and cardiomyopathy[END_REF][START_REF] Anter | An improved fast fuzzy c-means using crow search optimization algorithm for crop identification in agricultural[END_REF]. Other variants, such as Possibilistic c-means and Rough k-means, use possibilities and rough set theories respectively to handle more precisely uncertainties. A more general variant, called evidential c-means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy cmeans algorithm[END_REF], is based on the theory of belief functions. It generates a credal partition that encompasses hard, probabilistic, and rough partitions [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on dempster-shafer theory[END_REF]. The algorithm allows to obtain a rich representation of the uncertainties related to the data. As a consequence, it has been used in various applications [START_REF] Lian | Spatial evidential clustering with adaptive distance metric for tumor segmentation in fdg-pet images[END_REF][START_REF] Ayed | ECTD: evidential clustering and case types detection for case base maintenance[END_REF][START_REF] Abdelkhalek | An evidential clustering for collaborative filtering based on users' preferences[END_REF] and several extensions of ECM have been proposed ever since. The RECM algorithm has been developed to handle dissimilarity data [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF]. The ECMdd is a medoid-based variant of ECM [START_REF] Zhou | ECMdd: Evidential c-medoids clustering with multiple prototypes[END_REF]. The CCM method considers metaclusters to reduce misclassification [START_REF] Lui | Credal c-means clustering method based on belief functions[END_REF] and the DEC algorithm extends CCM by providing a dynamic edited framework [START_REF] Zhang | Dynamic evidential clustering algorithm[END_REF]. Evidential clustering also comprises EVCLUS [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF], a method that searches for a credal partition minimizing the discrepancy between the object pairwise distances and the conflict obtained by their mass functions. A faster optimization of EVCLUS has been proposed in [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF].

Clustering algorithms create groups with no other information than the characteristics of the data. However, it has been shown that introducing some background knowledge in a clustering process can highly improve the clustering solution [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF][START_REF] Grira | Semi-supervised fuzzy clustering with pairwise-constrained competitive agglomeration[END_REF]22,[START_REF] Antoine | Semi-supervised fuzzy c-means variants: a study on noisy label supervision[END_REF]. Such methods, called semi-supervised clustering or constrained clustering, express prior information as constraints. The most famous types of constraints correspond to instance-level constraints: the mustlink constraint, which specifies that two objects should be in the same class, the cannot-link constraint, which indicates that two objects are in different classes, and finally, the label constraint, which directly assigns an object into a class. Recently, various semi-supervised evidential clustering algorithms have been proposed for pairwise (i.e must-link and cannot-link) constraints [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][START_REF] Li | k-CEVCLUS: constrained evidential clustering of large dissimilarity data[END_REF][START_REF] Xie | On a new evidential c-means algorithm with instancelevel constraints[END_REF][START_REF] Denoeux | NN-EVCLUS: neural network-based evidential clustering[END_REF] and for label constraints [START_REF] Antoine | Evidential seed-based semi-supervised clustering[END_REF][START_REF] Antoine | On evidential clustering with partial supervision[END_REF][START_REF] Xie | On a new evidential c-means algorithm with instancelevel constraints[END_REF][START_REF] Denoeux | NN-EVCLUS: neural network-based evidential clustering[END_REF]. The evidential framework is used to express imprecision for label constraints and allows for any type of instance-level constraints, as for evidential clustering, to generate a credal partition. However, the integration of instance-level constraints implies a greater optimization complexity. Thus, [START_REF] Li | k-CEVCLUS: constrained evidential clustering of large dissimilarity data[END_REF] proposes a new optimization scheme on CEVCLUS [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF], a version of EVCLUS handling pairwise constraints. This method, named k-CEVCLUS, iteratively optimizes for each instance their mass function using a quadratic programming solver. k-CEVCLUS has been generalized by NN-EVCLUS [START_REF] Denoeux | NN-EVCLUS: neural network-based evidential clustering[END_REF] which uses a neural network trained to find the mass functions which minimize the difference between conflicts and the pairwise distances. The NN-EVCLUS algorithm copes with both pairwise and label constraints.

Although the pairwise constraints are more general, the label constraint is often available and provides more information. Thus, many k-means variants using label constraints have been proposed [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF][START_REF] Basu | Semi-supervised clustering by seeding[END_REF][START_REF] Antoine | Evidential seed-based semi-supervised clustering[END_REF]. Amongst them, the SECM algorithm [START_REF] Antoine | Evidential seed-based semi-supervised clustering[END_REF][START_REF] Antoine | On evidential clustering with partial supervision[END_REF] corresponds to the extension of ECM for fuzzy labels.

Its goal is twofold: guide the clustering algorithm towards a better solution and take advantage of the richness of information available with credal partition to make decisions.

Similarly to any semi-supervised variants of k-means [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF], the SECM algorithm adds a penalty term into the objective function in order to take into account the label constraints. Such penalty term complicates the criterion and leads to an increase in the computing time spent for its resolution. Thus, we propose to relax some constraints of the SECM objective function in order to create a new heuristic. The new algorithm, called SECM-h, increases the convergence speed of minimization while keeping a clustering solution close to the solution produced by the exact approach, i.e. SECM.

The rest of the paper is organized as follows. Section 2 recalls the necessary background on the theory of belief functions and the extensions of k-means leading to the evidential c-means. Then, the SECM algorithm is detailed. Section 3 depicts the SECM-h algorithm, a new approach to minimize SECM. The interest of the method is presented in Section 4 with some experiences on real data sets. Section 5 concludes the paper and gives some perspectives.

Preliminaries

Evidential clustering is based on the Dempster-Shafer theory or theory of belief functions. Then, to make this paper self-contained, a reminder of some important definitions and results of the Dempster-Shafer theory is presented in this section.

Theory of Belief Functions

In order to provide the belief function framework used in the following sections, we present the following definitions based on [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Smets | The transferable belief model[END_REF]. Definition 1. A frame of discernment, Ω = {ω 1 , . . . , ω c }, is said to be a set of all possible states that correspond to the interpretation of a finite propositional language.

Let a proposition be represented by a variable ω which is assumed to take values in Ω, then the partial knowledge regarding such proposition can be represented by a basic belief assignment defined as follows:

Definition 2. Let m : 2 Ω → [0, 1] be a mass function. If m verifies: Aj ⊆Ω m(A j ) = 1. ( 1
)
then, m is called basic belief assignment ( bba).

In order to interpret the mass functions, a major focus on the positive degree, i.e. m(A j ) > 0, of belief is performed which lead us to the following definition.

Definition 3. Let A j ∈ Ω such that m(A j ) > 0, then A j is said to be a focal set of m.
Special cases arise depending on which focal sets are actives [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF]. As such, if focal sets only consist of singletons, then the mass function is said to be Bayesian. If the whole belief is allocated to a unique singleton, then the bba is considered as certain. Finally, if m(Ω) = 1, then it represents a total uncertainty about the real state of ω.

Originally in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], Equation ( 1) is constrained with m(∅) = 0. Such mass function, called a normal bba, assumes that one state in Ω corresponds to the actual value of ω, leading to a closed-world assumption [START_REF] Smets | The transferable belief model[END_REF]. Inversely, if there exists the possibility that ω / ∈ Ω, then the empty set can be a focal set. This open-world assumption can be interpreted as the belief given to other states not included in Ω.

A bba can be transformed into a normal bba by transferring the empty set belief to all the other sets A j ⊆ Ω [START_REF] Smets | The transferable belief model[END_REF]:

m * (A j )    m(Aj ) 1-m(∅) if A j = ∅, 0 otherwise.
In [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF], it has been shown that various measures can be associated with a given bba. Amongst them, the plausibility function pl(A j ) : 2 Ω → [0, 1] allows to quantify the amount of possibility that A j includes the real state ω.

pl(A j )

A ⊆Ω,Aj ∩A =∅ m(A ) ∀A j ⊆ Ω.
The probability function BetP (ω) : Ω → [0, 1] provides from a bba a pignistic probability distribution:

BetP (ω) ω∈A m * (A ) |A | ∀ω ⊆ Ω.
where |A | denotes the cardinality of A ⊆ Ω.

Evidential c-Means algorithm (ECM)

Evidential C-Means (ECM) is a clustering algorithm for object data introduced in [START_REF] Masson | ECM: An evidential version of the fuzzy cmeans algorithm[END_REF] which is based on the concept of credal partition defined as follows:

= (m 1 , • • • , m n ) T ∈ R n×2 c is called the credal partition of X.
As discussed in [START_REF] Masson | ECM: An evidential version of the fuzzy cmeans algorithm[END_REF], a credal partition is a generalization of well-known data partitions such as: hard, fuzzy, and possibilistic. It allows to represent the uncertainty and imprecision regarding the cluster membership of each object

x i ∈ X. ECM assumes that each cluster ω k is represented by a prototype or barycenter v k ∈ R p and the set of all prototypes is defined as the collection

V = {v k }.
Since ECM is a credibilistic variant of Fuzzy C-Means (FCM) [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms, Advanced Applications in Pattern Recognition[END_REF],

then the evidential clustering problem has been stated in [START_REF] Masson | ECM: An evidential version of the fuzzy cmeans algorithm[END_REF], [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF] as finding the credal partition M that minimizes the following cost function:

J ECM (M, V, S) = n i=1 Aj ⊆Ω,Aj =∅ |A j | α m β ij d 2 ij + n i=1 δ 2 m β i∅ , (2)
subject to

Aj ⊆Ω,Aj =∅ m ij + m i∅ = 1 ∀i ∈ {1, n} (3)
m ij ≥ 0 ∀i ∈ {1, n}, ∀A j ⊆ Ω. ( 4
) det(S k ) = 1 ∀k ∈ {1, c} (5)
where m ij = m i (A j ) corresponds to the mass of the object i allocated to the subset A j , m i∅ defines more particularly the mass for the object i allocated to the empty set, α ≥ 1 is a parameter that allows controlling the degree of imprecision of the partition, β > 1 is used to penalize a high level of uncertainty on the partition, δ is a positive constant parameter that controls the importance given to the empty set, S k is the covariance matrix of the k th cluster, and d ij is the Mahalanobis distance defined as:

d 2 ij = x i -v j 2 Sj = (x i -v j ) T S j (x i -v j ) . (6)
Let v j be the prototype for the subset A j such that

v j 1 |A j | c l=1 s lj v l ∀A j ∈ Ω,
with

s lj =    1 if ω l ∈ A j , 0 otherwise.
The set S = {S 1 , . . . S c } designates the covariance matrices for the clusters and S j represents the evidential covariance matrix for the j th prototype. It is defined as:

S j 1 |A j | ω k ∈Aj S k ∀A j ∈ Ω.
The optimal solution is obtained using a Gauss-Seidel type optimization method. First, V and S are assumed to be fixed, in order to obtain the solution of the constrained problem [START_REF] Sun | A decomposition-clustering-ensemble learning approach for solar radiation forecasting[END_REF] with respect to M. The optimality of M is obtained with

m ij = |A j | -α/(β-1) d -2/(β-1) ij A k =∅ |A k | -α/(β-1) d -2/(β-1) ik + δ -2/(β-1) ∀i = {1, n} ∀A j = ∅,
and

m i∅ = 1 - Aj =∅ m ij ∀i = {1, n}.
Following the successive displacement optimization method, M and S are assumed to be fixed and the optimality of V is obtained as the solution of the linear system

HV = B, (7)
where B ∈ R c×p is given by

B q = n i=1 x iq Aj =∅ |A j | α-1 m β ij s j ∀ = {1, c} ∀q = {1, p}, (8)
and H ∈ R c×c is given by:

H k = n i=1 Aj =∅ |A j | α-2 m β ij s j s kj ∀k, = {1, c}. (9)
Finally, M and V are assumed to be fixed in order to obtain the optimal solution for (2) w.r.t. S. To do so, the following change of variable is defined

Σ k n i=1 Aj ω k |A j | α-1 m β ij (x i -v j ) (x i -v j ) T ∀k = {1, c}. (10)
Then, the optimal solution for S is given by

S k = det(Σ k ) 1/p Σ -1 k . (11)
ECM provides sufficient conditions to find the optimal credal partition on object data. However, it does not take into account previous knowledge which is present in many real clustering applications. Such knowledge often takes the form of labeled data.

Semi-supervised ECM (SECM)

It is known that data labeling is usually carried out by experts. However, experts often face the problem of labeling objects for which they are not fully certain of the class they belong to. Then, in [START_REF] Antoine | On evidential clustering with partial supervision[END_REF], a method to handle imprecise but certain labels is presented. An imprecise label on an object i is expressed with a subset A j ⊂ Ω, |A j | ≥ 1 such that the real class of x i belongs to A j . The consistency between this imprecise label subset A j and the bba m i assigned to object i is evaluated using the T ij measure defined as follows:

T ij T i (A j ) = A ⊆Ω,Aj ∩A =∅ |A j ∩ A | r 2 |A | r m i , ∀i ∈ {1, n}, A j ⊆ Ω. ( 12
)
Such measure favors degrees of belief containing the constrained subset A j or a part of it as well as subsets with low cardinalities. The r ≥ 0 parameter controls the degree of precision expected for the object i: high values of r penalize subsets with high cardinalities whereas low values of r allow high value of T ij for subsets with high cardinalities. If r = 0, T ij corresponds to the plausibility that the object x i belongs to A j .

Notice that T ij = 1 when belief is assigned for an object i that belongs to a cluster in the subset A j . Inversely, T ij = 0 when no belief is assigned for an object i to belong to a cluster in A j , i.e., x i / ∈ A j .

To illustrate the behavior of the T ij measure, let us consider DiamondK3, a synthetic data set composed of 15 points that needs to be divided into three groups (cf. Figure 1(a)). An execution of the ECM algorithm with α = 1, Let us suppose that we know that object 6 belongs to ω 1 and object 13 belongs either to ω 1 or to ω 3 , but not to ω 2 . Such partial knowledge can be traduced into the following constraints: x 6 ∈ {ω 1 } and x 13 ∈ {ω 1 , ω 3 }. The T ij measure allow us to quantify the degree of agreement between the constraint and the mass function obtained by ECM. The highest is the measure, the better the constraint is respected.

β = 2,
To better understand the concept, Table 1 presents a set of possible mass functions for the object 6 and the subsequent computation of T 6 ({ω 1 }) using r = 1, and then with r = 0, i.e. P l 6 ({ω 1 }). The first case fully respects the constraint x 6 ∈ {ω 1 }, giving T 6 ({ω 1 }) = P l 6 ({ω 1 }) = 1 whereas case 4 totally ignores the constraints, giving T 6 ({ω 1 }) = P l 6 ({ω 1 }) = 0. The second and the third case partially respect the constraint, since the bba is allocated to subsets containing ω 1 . When r = 1, the more the cardinality of the subset, the lower the value of T 6 ({ω 1 }). With the plausibility measure, any partial information gives

P l 6 ({ω 1 }) = 1.
This means that a partial respect of the constraint is considered with r = 1 and P l i (A j ). Columns ω j,l show the mass assigned to subset {ω j , ω l }.

m 6 (A j ) ∅ ω 1 ω 2 ω 3 ω 1,2 ω 1,3 ω 2,3 Ω T 6 ({ω 1 }) P l 6 ({ω 1 }) case 1 0 1 0 0 0 0 0 0 1 1 case 2 0 0 0 0 1 0 0 0 1/2 1 case 3 0 0 0 0 0 0 0 1 1/3 1 case 4 0 0 1 0 0 0 0 0 0 0
Table 2 shows different possible mass function for the object 13. As it can be observed, the plausibility measure ensures the partial respect of the constraints.

When r = 1, T ij is null when no focal sets contains ω 1 and/or ω 3 . Conversely, T ij > 0 when there exists degree of belief on a subset including at least ω 1 or ω 3 . The measure favors subset with a low cardinality. For the same amount of subsets, for example in Table 2 {ω 1 , ω 2 } and {ω 1 , ω 3 }, a higher value is given to subsets containing the most of classes in the constraint, i.e. here {ω 1 , ω 3 }.

Table 2: Possible mass functions for object x 13 constrained on {ω 1 , ω 3 } and calculation of T ij with r = 1 and P l i (A j ). Columns ω j,l show the mass assigned to subset {ω j , ω l }.

m 13 (A j ) ∅ ω 1 ω 2 ω 3 ω 1,2 ω 1,3 ω 2,3 Ω T 13 ({ω 1 , ω 3 })P l 13 ({ω 1 , ω 3 }) case 1 0 1 0 0 0 0 0 0 1 1 case 2 0 0 0 0 0 1 0 0 √ 2/2 1 case 3 0 0 0 0 1 0 0 0 1/2 1 case 4 0 0 0 0 0 0 0 1 1/3 1 case 5 0 0 1 0 0 0 0 0 0 0
The T ij measure is used to define the following penalty term:

J s n i=1 Aj ⊆Ω,Aj =∅ b ij (1 -T ij ), such that b ij =    1 if x i is constrained by A j , 0 otherwise. 10
The problem of semi-supervised evidential clustering is then defined as finding the 3-tuple (M, V, S) that minimizes the following cost function

J SECM (M, V, S) = (1 -γ) 1 2 c n J ECM (M, V, S) + γ 1 s J s (M), (13)
subject constraints (3)- [START_REF] Li | 3d magnetization inversion using fuzzy c-means clustering with application to geology differentiation[END_REF]. The s parameter is the number of constraints, 1 2 c n and 1 s are coefficients to balance the two terms 1 and γ ∈ [0, 1] the coefficient to control the tradeoff between the objective function of ECM and the constraints.

In order to lighten the notations, we define ξ and χ such as:

ξ (1 -γ) 1 2 c n , (14)
χ γ 1 s , (15)
and

c j |A j ∩ A | r 2 |A j | r . (16)
Using ( 14)-( 16), the objective function ( 13) can be rewritten as:

J SECM (M, V, S) = ξ   n i=1 Aj =∅ |A j | α m β ij d 2 ij + n i=1 δ 2 m β i∅   +χ   n i=1 Aj ⊆Ω,Aj =∅ b ij   1 - Aj ∩A =∅ c j m i     . ( 17
)
When the β parameter is set to 2, the minimization problem in (17) becomes a quadratic optimization problem with linear constraints which is solved using classical methods [START_REF] Ye | An extension of Karmarkar's algorithm and the trust region method for quadratic programming[END_REF][START_REF] Ye | On affine scaling algorithms for nonconvex quadratic programming[END_REF].

Heuristic Semi-supervised Evidential Clustering

Optimization scheme

The SECM problem discussed in the previous section can also be solved using a heuristic approach. Indeed, heuristic methods have been used in optimization 1 Providing that the distances between objects and centroids are less or equal to 1. This can be done using a data normalization method, e.g. min-max scaling.

problems to improve the algorithm's execution time [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF][START_REF] Grira | Semi-supervised fuzzy clustering with pairwise-constrained competitive agglomeration[END_REF]. Such methods usually result in a trade off between execution time and optimality, completeness and/or accuracy.

As discussed in section 2.3, the SECM problem has been solved using a

Gauss-Seidel optimization method to find the 3-tuple (V, S, M) that minimizes the cost function [START_REF] Abdelkhalek | An evidential clustering for collaborative filtering based on users' preferences[END_REF]. Then, let us recall that the optimal centers of gravity V are found using [START_REF] Dongdong | Semantic clustering fuzzy c means spectral model based comparative analysis of cardiac color ultrasound and electrocardiogram in patients with left ventricular heart failure and cardiomyopathy[END_REF] while the covariance matrix S are obtained using [START_REF] Lian | Spatial evidential clustering with adaptive distance metric for tumor segmentation in fdg-pet images[END_REF]. The credal partition M can be found using both exact and heuristic methods which are discussed in the following sections.

Exact optimization

In order to obtain the credal partition M using an exact method, let V and S be constant and the β parameter of the cost function be set to 2. Let m i ∈ R 1×2 c be the mass for object x i and the focal sets in the first term of [START_REF] Zhang | Dynamic evidential clustering algorithm[END_REF] be rewritten in matrix form,

G i ∈ R n2 c ×n2 c , using G ij    δ 2 if A j = ∅ |A j | α d 2 ij otherwise.
Developing J s , the second term in [START_REF] Zhang | Dynamic evidential clustering algorithm[END_REF], we obtain

J s = n i=1 Aj ⊆Ω,Aj =∅ b ij - n i=1 A ⊆Ω m ij ( Aj ⊆Ω b ij c j ), with b ij    1 if x i is constrained to A j and A ∩ A j = ∅, 0 otherwise.
Finally, the label constraints can also be written in matrix form F i ∈ R 1×2 c as:

F i      0 if A = ∅ - Aj ⊆Ω b ij c j otherwise, and
f i Aj b ij .
Then, the objective function ( 17) can be rewritten as follows:

J SECM (M) = ξ n i=1 m T i G i m i + χF T i m i + χf i . ( 18
)
which can be solved using the well known sequential quadratic programming method [START_REF] Ye | An extension of Karmarkar's algorithm and the trust region method for quadratic programming[END_REF][START_REF] Ye | On affine scaling algorithms for nonconvex quadratic programming[END_REF].

Heuristic Optimization

In order to improve algorithm execution time we propose a heuristic algorithm that relaxes constraint (4). It eases the optimization problem for the update of the mass m ij . However, constraints (3) and ( 4) together imply that 0 ≤ m ij ≤ 1 ∀i ∈ {1, n}, ∀A j ⊆ Ω. Thus, removing constraint (4) allows m ij ∈ R. As it will be discussed later in this section, the case m ij < 0 only appears on constrained objects x i , for subsets A j violating the constraints. As a consequence, to respect constraint (3), the case m ij > 1 appears for subsets A j = A j respecting the label constraint. Since constraint ( 3) is respected and constraint (4) should be restored to comply with the definition (2) of a mass function, negative elements m ij can be set to 0 and the negative quantity of belief can be used as a coefficient to equivalently lower the other masses. This is achieved using the following mass re-assignment:

m * ij =    mij 1+ai if m ij > 0, 0 otherwise, ∀i = 1 . . . n, ∀A j ⊆ Ω (19)
such that

a i = - Aj ⊆Ω min(m ij , 0).
The optimal credibilistic partition can be found using the Lagrangian multiplier method.

L(M, λ 1 , . . . , λ n ) = J SECM - n i=1 λ i   Aj ⊆Ω,Aj =∅ m ij + m i∅ -1   .
The derivatives w.r.t. m i,j and m i∅ are:

∂L ∂m ij = ξ2|A j | α m ij d 2 ij -χ   Aj ∩A =∅ c lj b ij   -λ i , ∂L ∂m i∅ = 2ξδ 2 m i∅ -λ i .
Annulating the derivatives gives

m ij = λ i 2ξ 1 |A j | α d 2 ij + χ   Aj ∩A =∅ c lj b ij   2ξ|A j | α d 2 ij , (20)
m i∅ = λ i 2ξδ 2 . ( 21
)
Solving ∂L ∂λi = 0, we obtain:

        Aj ⊆Ω,Aj =∅ λ i 2ξ 1 |A j | α d 2 ij + χ   Aj ∩A =∅ c lj b ij   2ξ|A j | α d 2 ij         + λ i 2ξδ 2 = 1, λ i 2ξ = 1 - Aj ⊆Ω,Aj =∅ χ   Aj ∩A l =∅ c lj b ij   2ξ|A j | α d 2 ij -1 Aj ⊆Ω,Aj =∅ |A j | α d 2 ij -1 + δ -2 .
Replacing λi 2ξ in [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF] and [START_REF] Grira | Semi-supervised fuzzy clustering with pairwise-constrained competitive agglomeration[END_REF] enables to obtain the update equations:

m ij = 1 - A l ⊆Ω,A l =∅ χ   A l ∩A l =∅ c ll b ij   2ξ|A l | α d 2 il -1 |A j | α d 2 ij A l ⊆Ω,A l =∅ |A l | α d 2 il -1 + δ -2 + χ   Aj ∩A l =∅ c lj b ij   2ξ|A j | α d 2 ij , (22)
and

m i∅ = 1 - Aj ⊆Ω,Aj =∅ m ij . (23)
As discussed above, since constraint (4) has been relaxed and as it can be seen Equation ( 22), the update of the mass m ij can be negative. This can occur only for constrained objects. Indeed, negative values only appear in the first term, when the second term of the numerator is higher than 0, which is only possible for some b ij = 1, i.e. when there exists a constraint on x i . This behavior can be controlled by reducing the value of the coefficient χ.

The solution for the semi-supervised Evidential clustering problem is summarized in Algorithm 1.

Algorithm 1 SECM H Require: data X, number of classes c and subsets

A j ⊆ Ω Ensure: credal partition M, centroids V, covariance matrices S k ← 0 Initialize V k randomly, initialize S to identity matrices. repeat k ← k + 1
Compute distances using [START_REF] Xue | Application of fuzzy c-means clustering to prtr chemicals uncovering their release and toxicity characteristics[END_REF].

Update credibilistic partition M k using ( 22) and ( 23).

Correct M k to respect contraints (4) using eq. ( 19).

Update cluster centroids V k using eq. ( 7).

Update covariance matrix S k using eq. [START_REF] Lian | Spatial evidential clustering with adaptive distance metric for tumor segmentation in fdg-pet images[END_REF].

until V k -V k-1 < ε 3.4.

Complexity analysis

The complexity of SECM H is defined by the sum of the complexity of the different steps in the loop. The difference with ECM resides in the update of the credal partition. Let f be the number of focal elements such that f = 2 c if all subsets are used. A reduction of this value can be achieved by privileging specific subsets, for instance, f = c + 2 when only singletons, Ω, and the empty set are selected.

• The computation of the Mahalanobis distance Equation ( 6) is performed in O(p 2 nf ). If the covariance matrices are fixed to identity matrices, i.e.

a Euclidean distance has been chosen, then the complexity is decreased to O(pnf ).

• The complexity for update of the credal partition Equations ( 22) and ( 23) is O(nf ). The correction using Equation ( 19) requires at the worst case nf operations. The overall complexity of the three equations is then O(nf ). This also corresponds to the complexity of the update of the credal partition for the ECM algorithm [START_REF] Zhou | ECMdd: Evidential c-medoids clustering with multiple prototypes[END_REF].

• To compute the update of the cluster centroids V k Equation ( 7), it is first necessary to compute matrices B, Equation ( 8), which requires cpnf operations and H, Equation ( 9), which requires c 2 nf operations. Since our implementation uses a QR decomposition, its implies a complexity of

O(c 3 ) if c ≤ p, O(p 3 ) otherwise.
The resulting complexity of the overall sub-steps is O(cpnf + c 2 nf + min(c, p) 3 ).

• Finally, the complexity of the covariance matrix, Equation [START_REF] Lian | Spatial evidential clustering with adaptive distance metric for tumor segmentation in fdg-pet images[END_REF], that is When the exact optimization is used to update of credal partition, i.e. a sequential quadratic programming method on Equation ( 17), the complexity is

O(n 3 f 3 )[37]
. Thus, the overall complexity of SECM with an adaptive distance using an exact optimization (named

SECM E ) is O(kp 2 nf + kn 3 f 3 + kc 2 nf + k min(c, p) 3 + kcp 2 nf
). Considering that n p and n c, the complexity becomes O(kn 3 f 3 + k min(c, p) 3 ).

Results

Experimental protocol

To illustrate the effectiveness of the proposed clustering method, we carried out a series of experiments using data sets coming from the UCI repository [START_REF] Dua | UCI machine learning repository[END_REF].

The characteristics of the data sets are shown in Table 3. The performance of the evidential clustering method is measured using the Adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF] that takes values in [0, 1]. The ARI is based on the pairwise comparisons of the crisp partition P with a second crisp partition P * . A perfect match between P and P * is reflected by the ARI equal to 1. In our context, the P partition is obtained by first converting the credal partition M into a fuzzy partition U using the pignistic transformation. Then, the objects are assigned to clusters with the maximum of pignistic probability.

In order to determine the closeness of credal partitions, Denoeux [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on dempster-shafer theory[END_REF] proposed a Credal Rand Index (CRI), where CRI ∈ [0, 1] and CRI=1 means that the compared partitions are identical. More precisely, we employ the CRI related to the similarity index with a Jousselme's distance.

In the framework of semi-supervised clustering, we also assess the performance of the clustering methods using well-known classification measures such as Precision, Recall, and F 1 score. These measures are computed as in [START_REF] Goutte | A probabilistic interpretation of precision, recall and f-score, with implication for evaluation[END_REF] and generalized for multiclass. The precision quantifies from the number of objects predicted in a class how many are really in that class, whereas the recall indicates the fraction of objects in a class that is correctly assigned in that class.

The F 1 score is the harmonic mean of the precision and the recall.

The SECM E and SECM H algorithms take into account prior information in the form of label constraints which may be imprecise. First, a percentage of the real labels of the data sets are selected to obtain the set L s of hard labeled instances with no imprecision, also called single set. This percentage varies from 0 to 30%. Note that given a percentage p 1 allowing to obtain L sp 1 , the set L sp 2 of a higher percentage p 2 > p 1 is created such that L sp 1 ⊂ L sp 2 in order to better illustrate the interest of adding constraints. A single set is only composed of hard and clean labels. However, in a real application, these labels can be noisy.

Thus, we introduced 20% of noise into the L s set to form a hard noisy label set referred to as L n . Finally, the imprecision on the class membership of an object is simulated by the concatenation of L s and L n , leading to the double set L d that contains 20% of objects constrained to two classes. Notice that L d is a set of imprecise labels but not noisy since for every labeled object, the real class is present in L d . The generation of the different sets of labels is resumed in Figure 2.

The evidential clustering algorithms SECM E and SECM H are compared with the most similar semi-supervised clustering algorithms that provide a hard partition (SKMEANS [START_REF] Basu | Semi-supervised clustering by seeding[END_REF]) and a fuzzy partition (SFCM [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF][START_REF] Antoine | Semi-supervised fuzzy c-means variants: a study on noisy label supervision[END_REF]). Default parameters for the evidential methods are α = 1, β = 2, δ 2 = 100 and γ = 0.5.

The exponent α is set to 1 as [START_REF] Masson | ECM: An evidential version of the fuzzy cmeans algorithm[END_REF] to allow enough imprecision in the credal partition. The coefficient of fuzzification β is equivalently fixed for SFCM on the fuzzy partition. As discussed in [START_REF] Masson | ECM: An evidential version of the fuzzy cmeans algorithm[END_REF], setting the δ parameter is difficult since it strongly depends on the data. In this work, we set δ parameter to a high value as no outliers exist in the data sets. The parameter γ, which controls the tradeoff between constraints and the data structure has been tested with values varying from 0.1 to 0.7. It is set by default for SFCM, SECM E , and SECM H to 0.5 in order to be balanced.

The imprecise information contained in the double set L d is exploited by SECM using constraints on subsets. However, this information cannot be taken by SKMEANS and must be transformed into uncertain information for SFCM.

Indeed, SFCM only allows objects to be constrained to single classes with degrees of probability. Thus, we chose to set a probability of {0.5, 0.5} for each object having imprecision between two classes. Note that the meaning of the information is slightly different as it represents precise information, although uncertain [START_REF] Smets | Imperfect information: Imprecision and uncertainty[END_REF].

Since SKMEANS, SFCM, and SECM are semi-supervised variants of kmeans, they all need a random initialization of the centroids and labels as prior Xeon(R) CPU E5-2670 v2 @ 2.50 GHz.

Influence of the γ parameter

The γ parameter is a coefficient set between 0 and 1 that allows giving more or less importance to the respect of the constraints. Tables 4 and5 present several values of γ tested with SECM E and SECM H using 30% of single or doble constraints. The results correspond to the average of the ARI on the whole data sets and the average of the ARI on unconstrained objects only (ARIu). The constraint set (i.e. L s or L d ) and the algorithm (i.e. SECM E or SECM H ) does not seem to be parameters that influence the choice of γ. We can also remark that no significant differences in behavior exist between the ARI and the ARIu. It can be observed that the best γ value mostly depends on the data set.

Ionosphere, which has an extended region of overlapped classes, shows better performances with a low value of γ whereas LettersIJL, that has more prolate ellipsoids, has better results with a high value of γ.

Two schemes are possible when applying a SECM: 1) the overall structure of the data is already well defined with the unlabeled data and only overlapped areas between several clusters need the constraints to be less fuzzy. 2) the global structure found with unlabeled data is not the desired solution and the constraints must help to lead the algorithm towards this solution. In the first case, the γ value should be low to preserve the discovered structure. In the second case, the γ needs to be large enough to force the global structure towards a new different one. For the rest of the paper, we suppose that no prior information is available regarding the characteristics of the data sets. Thus, γ is fixed to 0.5.

Interest of the constraints

Adding constraints allows either to guide a clustering algorithm towards a desired solution or to refine a partition solution. To show the first behavior, let us consider a synthetic data set named GaussK2 that needs to be classified into two groups. The data points with ground truth class labels are shown Figure 3. The interest of label constraints on real data sets is summarized in Table 6 using the precision (P), the recall (R), the F 1 score, and the Adjusted Rand Index (ARI).

As it can be observed, there exist little differences between the precision and the recall except for Columns that is characterized by unbalanced classes.

The low recall on Column when no constraint exists means that the clustering algorithm had difficulties, for each class, to correctly identify objects inside. As shown Table 6, the gap between precision and recall is reduced with constraints and both of the measures are improved. We can conclude that label constraints help to better classify objects. In terms of performances, few differences are also observed between SECM H and SECM E . Finally, the F 1 score and the ARI follow the same trend: the more constraints are added, the better the accuracy.

Experiments were also conducted on the L d set and the results lead to a similar analysis.

r parameter

The r parameter controls for labels constraints the penalization given to subsets with high cardinalities. Two values are tested: r = 1, which is the default setting of SECM , and r = 0, which is identical to replacing the T ij terms by plausibilities. Thus, in the following experiments, this version is referred to as SECM pl. Experiments are conducted on the L s , L d and L n sets for a various percentage of constraints. Results are presented Table 7.

As expected, best performances are obtained with the most informative set, i.e. the L s set, and the lower performances a retrieved by the noisy set L n .

In the details, we can observe that for the L s and the L d sets, SECM works better for Column and Iris whereas SECM pl find better results for Ionosphere. To resume, the best performances mostly depends on the data sets.

On the contrary, SECM pl has most of the time better performances than SECM using the L n set. Indeed, r = 0 let for constrained objects equal possibilities on subsets with various cardinalities. If the label corresponds to a noise and is in contradiction with the data structure, the algorithm will favor subsets with high cardinalities, i.e. subsets that include both the label and the cluster guessed with the data structure. and SECM E have similar performances. The performance has been evaluated using the ARI measure, after a transformation of the credal partition into a hard partition. In order to study more precisely the difference between the SECM H and SECM E using similar parameters, the closeness between credal partitions is computed with the CRI.

Algorithms comparison

The SECM H and SECM pl H algorithms using γ = 0.5 are compared to SF CM and SKM EAN S algorithms. The SKM EAN S method [START_REF] Basu | Semi-supervised clustering by seeding[END_REF] is the semi-supervised k-means variant that handles crisp labels as prior information and generates a hard partition. The SF CM [START_REF] Pedrickz | Fuzzy clustering with partial supervision[END_REF] is the fuzzy variant of SKM EAN S: it allows a probability on the labels and returns a fuzzy partition.

First, the L s set is used. For SF CM , we set a probability to 1 for all constrained objects. The average ARIs varying with the percentage of constraints for all data sets are presented in Figure 6. The performances show that integrating label constraints leads to better define the clustering partition desired whatever the semi-supervised clustering algorithm. However, a decrease in performance can appear, as it can be seen for SECM pl H on Wine. This result is known to possibly occur when constrained objects are only in an overlapped area between classes [START_REF] Wagstaff | When is constrained clustering beneficial, and why?[END_REF].

Column Ionosphere Iris

As it can be seen, the SECM algorithms bring good results on the data sets compared to the other algorithms except for the Wine data set.

A similar experiment is performed on the L d set to compare semi-supervised clustering methods. The SKM EAN S algorithm is excluded since it can only take crisp labels. For the SF CM algorithm, the imprecisions included in the L d set and defined for an object by a subset of two labels are transformed into an uncertainty between the couple of labels by setting the probabilities of both labels to 0.5. Figure 7 presents the average ARI with respect to the percentage of constraints for all data sets. The results show that SECM outperforms most of the time SF CM . This good performance for evidential semi-supervised clustering is explained by its ability to handle the imprecision coming from the background knowledge.

Column Ionosphere Iris

Conclusion

The SECM algorithm is a semi-supervised clustering variant of ECM based on the theory of belief functions. As such, it is capable of handling uncertainty and imprecision of the background knowledge and provides a credal partition that allows expressing imprecision and uncertainty regarding the assignment of objects to clusters. The SECM method, which is based on the minimization of an objective function, introduces prior knowledge in the form of label constraints. The optimization problem is solved using a Gauss-Seidel type method, with an alternate update of the masses and the cluster centroids. In this paper, a relaxation of constraints is proposed to fasten the optimization. The new heuristic, referred to as SECM-h, differs from the classical SECM as it provides a direct update formula for the masses. Experimental tests show that SECM-h achieves the same performance as its exact solution counterpart at a much lower execution time cost. Further investigations have also been conducted on the parameters of SECM H and SECM E and a comparison with other semi-supervised clustering algorithms has been performed. Results show good performance of the SECM algorithms compared to other algorithms. Future work includes extending the ideas exposed in this paper to evidential semi-supervised clustering methods that handle pairwise constraints [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF] or both labels and pairwise constraints [START_REF] Xie | On a new evidential c-means algorithm with instancelevel constraints[END_REF].

Definition 4 .

 4 Let Ω = {ω 1 , • • • , ω c } be the set of all possible clusters for the set of objects X = {x i ∈ R p } ∀i = 1, .., n and m i a mass function defined in Ω. Then, the collection M

and δ 2

 2 = 100 provides us a credal partition, the main masses of which are presented in Figure1(b). As it can be seen, the highest beliefs on the clusters ω 1 and ω 2 are correctly recovering the points 1 to 10 and the highest beliefs on the last cluster ω 3 are assigned to the points 12 to 15. Point 6, located between two classes, has all its mass allocated to the subset {ω 1 , ω 2 }.

Figure 1 :

 1 Figure 1: DiamondK3 data set (a) and a sample of the mass functions obtained using ECM (b).

  used only when adaptive distances are chosen, is O(cp 3 ) due to the computation of the inverse of Σ k . The computation of Σ k , Equation[START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on dempster-shafer theory[END_REF], requires cp 2 nf operations.As a result, the SECM H algorithm using adaptive distances has a complexity of O(kc 2 nf + k min(c, p) 3 + kcp 3 + kcp 2 nf ) where k represents the number of iterations reached before convergence. When using a Euclidean distance, the complexity is O(kcpnf + kc 2 nf + k min(c, p)3 ). Considering that n p and n c, the complexity for both distances becomes O(knf + k min(c, p) 3 ).

Figure 2 :

 2 Figure 2: Generation of noisy and double labels. Gray numbers represent an example of the sets given three classes {1, 2, 3}.

  information. With the view to making performance comparisons, the same initializations are applied for each algorithm and the same set of labels are used.An experiment consists of 100 trials of an algorithm. Results present the average and confidence interval measures (as the constraint sets are different for each trial). A trial is characterized by 5 executions of the algorithm with different initialization of the centroids. The final partition kept is the one with the minimum objective function. The experiments were performed on an Intel(R)

Figure 3 :

 3 Figure 3: GaussK2 data set. Symbols represents the ground truth class labels.

Figure 4 (

 4 Figure 4 (b)) allows to obtain a vertical boundary and an ARI equal to 1.

Figure 4 :

 4 Figure 4: Contour surfaces of the credal partition obtained by (a) ECM and (b) SECM. Centroids for singletons and the universe are designed by crosses and stars. Label constraints are highlighted in red.

Figure 5

 5 Figure 5 illustrates the objective function values during the process of 100 execution of SECM on the L s set for Iris and Wine. Similar results are obtained with the other data sets. As it can be remarked, the iteration number is lower for the SECM H algorithm and the minimum values of the objective function are reached by the SECM E algorithm.

  ± 0.0 0.51 ± 0.01 0.6 ± 0.0 0.0 ± 0.0 0.51 ± 0.01 10 1447.3 ± 1.3 74.7 ± 2.0 0.35 ± 0.01 1447.9 ± 1.3 63.1 ± 2.0 3.74 ± 0.05 20 1476.8 ± 0.9 137.6 ± 1.6 0.41 ± 0.00 1477.6 ± 0.9 132.5 ± 1.5 3.70 ± 0.04 30 1488.6 ± 0.8 175.0 ± 1.6 0.43 ± 0.00 1489.1 ± 0.8 173.5 ± 1.6 3.71 ± 0.04 Wine 0 0.1 ± 0.0 0.0 ± 0.0 0.49 ± 0.02 0.1 ± 0.0 0.0 ± 0.0 0.49 ± 0.02 10 191.6 ± 1.3 28.2 ± 1.8 0.23 ± 0.01 184.4 ± 1.0 1.6 ± 0.5 0.96 ± 0.02 20 215.7 ± 1.2 44.6 ± 1.5 0.21 ± 0.01 210.5 ± 1.2 14.0 ± 1.1 0.94 ± 0.04 30 236.3 ± 1.1 65.9 ± 1.6 0.19 ± 0.00 232.7 ± 1.1 36.3 ± 1.5 0.89 ± 0.03 Iris Wine

Figure 5 :

 5 Figure 5: Objective function value of SECM (Ls set, γ = 0.5 and r = 1) varying with the iteration number. X-axis uses a logarithmic scale.

Figure 6 :

 6 Figure 6: Algorithms comparison on the Ls set. The average of the ARI and the confidence interval is given on 100 trials.

Figure 7 :

 7 Figure 7: Algorithms comparison on the L d set.

Table 1 :

 1 Possible mass functions for object x 6 constrained on {ω 1 } and calculation of T i (A j )

Table 3 :

 3 A quick view of UCI data sets involved.

	Name	# objects # attributes # classes # objects per classes
	Column	310	6	3	{60,150,100}
	Ionosphere	351	34	2	{225, 126}
	Iris	150	4	3	{50, 50, 50}
	LettersIJL	227	16	3	{81, 72, 74}
	Wdbc	5569	30	2	{357,212}
	Wine	178	13	3	{59, 71, 48}

Real labels are known for all data sets. LettersIJL refers to the Letters data set where only three classes are kept and the number of instances is reduced by randomly selecting 10% of them per class, as it has been done in [22]. Since Column, Wdbc and Wine are a data sets characterized by great variations of scale amongst the attributes, we use a standardization method to avoid unequal contributions of the features during the clustering process. The Mahalanobis distance has been used for all data sets except for Column, Wdbc and Wine that use the Euclidean distance as they have spherical shaped groups.

Table 4 :

 4 Influence of the γ parameter with 30% of constraints and r = 1. Standard deviations are shown in brackets, confidence intervals are between 0.00 and 0.01.

				Ls set			L d set
			SECM H	SECM E	SECM H	SECM E
			ARI ARIu	ARI ARIu	ARI ARIu	ARI ARIu
		0.1	0.50	0.39	0.52	0.40	0.45	0.36	0.48	0.39
			[0.04] [0.05]	[0.03] [0.03]	[0.05] [0.05]	[0.04] [0.04]
		0.3	0.57	0.43	0.58	0.44	0.54	0.42	0.54	0.43
	Column	0.5	[0.03] [0.04] 0.58 0.44 [0.03] [0.04]	[0.03] [0.04] 0.58 0.44 [0.03] [0.04]	[0.03] [0.04] 0.55 0.43 [0.03] [0.04]	[0.03] [0.03] 0.54 0.43 [0.03] [0.03]
		0.7	0.58	0.44	0.57	0.43	0.55	0.43	0.54	0.43
			[0.03] [0.04]	[0.03] [0.04]	[0.03] [0.04]	[0.03] [0.03]
		0.1	0.71	0.62	0.71	0.62	0.70	0.62	0.69	0.61
			[0.04] [0.05]	[0.03] [0.05]	[0.03] [0.04]	[0.03] [0.04]
	Ionosphere	0.3 0.5 0.7	0.67 [0.04] [0.05] 0.55 0.58 0.44 [0.04] [0.05] 0.54 0.38	0.66 [0.04] [0.05] 0.54 0.57 0.43 [0.04] [0.05] 0.52 0.36	0.65 [0.03] [0.05] 0.56 0.57 0.46 [0.04] [0.05] 0.53 0.41	0.64 [0.04] [0.05] 0.55 0.56 0.44 [0.04] [0.05] 0.51 0.38
			[0.04] [0.05]	[0.04] [0.05]	[0.04] [0.06]	[0.04] [0.05]
		0.1	0.92	0.89	0.93	0.90	0.92	0.89	0.92	0.89
			[0.03] [0.05]	[0.03] [0.05]	[0.04] [0.05]	[0.04] [0.05]
		0.3	0.92	0.89	0.93	0.89	0.92	0.89	0.92	0.89
			[0.03] [0.05]	[0.03] [0.04]	[0.03] [0.05]	[0.04] [0.06]
	Iris	0.5	0.92 [0.03] [0.05] 0.89	0.93 [0.03] [0.05] 0.90	0.92 [0.03] [0.05] 0.89	0.91 [0.04] [0.06] 0.88
		0.7	0.92	0.89	0.93	0.90	0.92	0.89	0.92	0.89
			[0.03] [0.05]	[0.03] [0.05]	[0.04] [0.05]	[0.03] [0.05]

Table 5 :

 5 Influence of the γ parameter with 30% of constraints and r = 1. Standard deviations are shown in brackets, confidence intervals are between 0.00 and 0.01.

				Ls set			L d set
			SECM H	SECM E	SECM H	SECM E
			ARI ARIu	ARI ARIu	ARI ARIu	ARI ARIu
		0.1	0.65	0.56	0.65	0.57	0.63	0.55	0.63	0.55
			[0.05] [0.06]	[0.05] [0.06]	[0.06] [0.07]	[0.06] [0.07]
		0.3	0.72	0.62	0.72	0.62	0.69	0.60	0.69	0.60
	LettersIJL	0.5 0.7	[0.05] [0.06] 0.75 0.65 [0.05] [0.06] 0.76 0.66	[0.05] [0.06] 0.75 0.65 [0.05] [0.07] 0.77 0.68	[0.05] [0.07] 0.72 0.63 [0.06] [0.07] 0.73 0.65	[0.05] [0.07] 0.72 0.63 [0.06] [0.07] 0.74 0.65
			[0.05] [0.07]	[0.05] [0.07]	[0.06] [0.08]	[0.06] [0.08]
		0.1	0.70	0.69	0.70	0.69	0.70	0.69	0.70	0.69
			[0.01] [0.02]	[0.01] [0.02]	[0.01] [0.02]	[0.01] [0.02]
		0.3	0.72	0.69	0.73	0.69	0.72	0.69	0.72	0.69
			[0.01] [0.02]	[0.01] [0.02]	[0.01] [0.02]	[0.01] [0.02]
	Wdbc	0.5	0.76 [0.02] [0.02] 0.69	0.76 [0.02] [0.03] 0.70	0.74 [0.02] [0.02] 0.69	0.75 [0.02] [0.03] 0.69
		0.7	0.79	0.70	0.79	0.72	0.77	0.70	0.77	0.71
			[0.02] [0.03]	[0.02] [0.03]	[0.02] [0.03]	[0.02] [0.03]
		0.1	0.91	0.89	0.91	0.90	0.91	0.89	0.91	0.90
			[0.01] [0.03]	[0.01] [0.03]	[0.02] [0.03]	[0.01] [0.03]
		0.3	0.92	0.88	0.91	0.88	0.91	0.88	0.91	0.88
			[0.02] [0.03]	[0.02] [0.03]	[0.02] [0.03]	[0.02] [0.03]
	Wine	0.5	0.92 [0.02] [0.03] 0.88	0.92 [0.03] [0.04] 0.88	0.91 [0.02] [0.04] 0.88	0.91 [0.02] [0.03] 0.88
		0.7	0.92	0.88	0.92	0.88	0.91	0.88	0.91	0.88
			[0.03] [0.04]	[0.03] [0.04]	[0.03] [0.04]	[0.03] [0.04]

Table 6 :

 6 Interest of the constraints using Ls set, γ = 0.5 and r = 1. Standard deviations are shown in brackets, confidence intervals are between 0.00 and 0.02.

					SECM H				SECM E
			P	R	F 1	ARI	P	R	F 1	ARI
	Column	0 10 0.76 0.73 0.74 0.43 [0.04] 0.65 0.48 0.52 0.23 [0.00] 20 0.81 0.79 0.79 0.51 [0.03]	0.65 0.48 0.52 0.23 [0.00] 0.75 0.71 0.72 0.41 [0.05] 0.81 0.79 0.79 0.51 [0.03]
		30 0.84 0.82 0.83 0.58 [0.03]	0.84 0.82 0.83 0.58 [0.03]
	Ionosphere	0 10 0.87 0.87 0.86 0.53 [0.06] 0.69 0.56 0.55 0.01 [0.05] 20 0.87 0.87 0.87 0.54 [0.05] 30 0.89 0.88 0.88 0.58 [0.04]	0.69 0.56 0.55 0.01 [0.05] 0.86 0.86 0.86 0.51 [0.06] 0.87 0.87 0.86 0.53 [0.04] 0.88 0.88 0.88 0.57 [0.04]
		0	0.87 0.86 0.86 0.67 [0.01]	0.87 0.86 0.86 0.67 [0.01]
	Iris	10 0.94 0.93 0.93 0.82 [0.07] 20 0.97 0.96 0.96 0.90 [0.05]	0.94 0.93 0.93 0.83 [0.07] 0.97 0.97 0.97 0.90 [0.05]
		30 0.97 0.97 0.97 0.92 [0.03]	0.98 0.97 0.97 0.93 [0.03]
	LettersIJL	0 10 0.83 0.82 0.82 0.56 [0.08] 0.56 0.50 0.49 0.07 [0.04] 20 0.88 0.88 0.88 0.68 [0.06] 30 0.91 0.91 0.91 0.75 [0.05]	0.56 0.50 0.49 0.07 [0.04] 0.83 0.83 0.82 0.56 [0.08] 0.88 0.88 0.88 0.68 [0.06] 0.91 0.91 0.91 0.75 [0.05]
	Wdbc	0 10 0.93 0.93 0.93 0.72 [0.01] 0.92 0.92 0.92 0.69 [0.00] 20 0.93 0.93 0.93 0.74 [0.02]	0.92 0.92 0.92 0.69 [0.00] 0.93 0.93 0.93 0.73 [0.02] 0.93 0.93 0.93 0.75 [0.02]
		30 0.94 0.94 0.94 0.76 [0.02]	0.94 0.94 0.94 0.76 [0.02]
		0	0.96 0.96 0.96 0.88 [0.01]	0.96 0.96 0.96 0.88 [0.01]
	Wine	10 0.96 0.96 0.96 0.87 [0.04] 20 0.97 0.97 0.97 0.90 [0.03] 30 0.97 0.97 0.97 0.92 [0.02]	0.96 0.96 0.96 0.88 [0.03] 0.97 0.96 0.96 0.89 [0.03] 0.97 0.97 0.97 0.92 [0.03]

Table 7 :

 7 Influence of the r parameter, γ = 0.5. Average ARI and its standard deviation in brackets are shown, confidence intervals are between 0 and 0.03.

			Ls set	L d set	Ln set
			SECM H	SECM pl H	SECM H	SECM pl H	SECM H	SECM pl H
	Column	0 10 0.43 [0.04] 0.28 [0.02] 0.23 [0.00] 0.23 [0.00] 20 0.51 [0.03] 0.37 [0.04]	0.23 [0.00] 0.23 [0.00] 0.42 [0.04] 0.27 [0.01] 0.49 [0.04] 0.34 [0.03]	0.23 [0.00] 0.23 [0.00] 0.37 [0.04] 0.25 [0.02] 0.41 [0.04] 0.28 [0.03]
		30 0.58 [0.03] 0.48 [0.04]	0.55 [0.03] 0.43 [0.04]	0.43 [0.03] 0.33 [0.03]
	Ionosphere	10 20 30	0.53 [0.06] 0.57 [0.04] 0.54 [0.05] 0.59 [0.04] 0.58 [0.04] 0.61 [0.04]	0.01 [0.05] 0.54 [0.06] 0.57 [0.04] 0.55 [0.04] 0.58 [0.04] 0.57 [0.04] 0.60 [0.04]	0.01 [0.05] 0.01 [0.05] 0.22 [0.13] 0.41 [0.10] 0.32 [0.07] 0.40 [0.06] 0.35 [0.04] 0.38 [0.04]
		0	0.67 [0.01] 0.67 [0.01]	0.67 [0.01] 0.67 [0.01]	0.67 [0.01] 0.67 [0.01]
	Iris	10 0.82 [0.07] 0.77 [0.07] 20 0.90 [0.05] 0.86 [0.06]	0.82 [0.07] 0.76 [0.07] 0.89 [0.05] 0.85 [0.07]	0.51 [0.14] 0.62 [0.08] 0.58 [0.10] 0.61 [0.08]
		30 0.92 [0.03] 0.89 [0.05]	0.92 [0.03] 0.88 [0.06]	0.59 [0.08] 0.58 [0.07]
		0	0.07 [0.04] 0.07 [0.04]	0.07 [0.04] 0.07 [0.04]	0.07 [0.04]	0.07[0.04]
	Letters	10 20 30	0.56 [0.08] 0.55 [0.08] 0.68 [0.06] 0.67 [0.05] 0.75 [0.05] 0.74 [0.05]	0.54 [0.08] 0.52 [0.09] 0.65 [0.06] 0.65 [0.06] 0.72 [0.06] 0.71 [0.05]	0.38 [0.09] 0.39 [0.10] 0.47 [0.08] 0.48 [0.08] 0.51 [0.06] 0.51 [0.05]
	Wdbc	0 10 20	0.69 [0.00] 0.69 [0.00] 0.72 [0.01] 0.72 [0.01] 0.74 [0.02] 0.75 [0.02]	0.69 [0.00] 0.69 [0.00] 0.72 [0.01] 0.71 [0.01] 0.73 [0.01] 0.74 [0.01]	0.69 [0.00] 0.69 [0.00] 0.67 [0.02] 0.66 [0.01] 0.70 [0.02] 0.68 [0.02]
		30	0.76 [0.02] 0.76 [0.02]	0.74 [0.02] 0.75 [0.02]	0.71 [0.02] 0.71 [0.02]
		0	0.88 [0.02] 0.88 [0.02]	0.88 [0.02] 0.88 [0.02]	0.88 [0.02] 0.88 [0.02]
	Wine	10 20 30	0.87 [0.04] 0.90 [0.02] 0.90 [0.03] 0.91 [0.02] 0.92 [0.02] 0.93 [0.02]	0.87 [0.03] 0.90 [0.02] 0.89 [0.03] 0.91 [0.02] 0.91 [0.02] 0.92 [0.02]	0.79 [0.04] 0.84 [0.02] 0.77 [0.03] 0.79 [0.02] 0.73 [0.03] 0.74 [0.02]
	4.5. Credal partition analysis
		Experiments conducted on previous subsection have shown that SECM H

  Table 8 presents the results on the L s set. It can be concluded that there exists no significant difference between SECM H and SECM E .

Table 8 :

 8 CRI (mean[std]) between SECM H and SECM E using Ls set, γ = 0.5 and r = 1.

	data set	10	20	30
	Column	0.970[0.004] 0.961[0.004] 0.963[0.005]
	Ionosphere 0.988[0.002] 0.987[0.002] 0.987[0.002]
	Iris	0.989[0.005] 0.989[0.007] 0.988[0.009]
	Letters	0.998[0.001] 0.995[0.001] 0.988[0.002]
	Wdbc	0.996[0.000] 0.994[0.001] 0.991[0.001]
	Wine	0.993[0.001] 0.997[0.001] 0.986[0.002]
	4.6. Optimization analysis

A study concerning the optimization performances of SECM E and SECM H is performed. Table

9

presents the average and for the objective function, the penalization J s , and the CPU time in seconds obtained by the two algorithms using a various number of constraints with the L s set.

Results clearly show that the penalty term value and the objective function value are minimal with SECM E . However, the difference between the objective function of SECM E and SECM H can be considered as insignificant since the two algorithms give equivalent clustering performances. On the other hand, the computation time of SECM H is at least two times lower than SECM E .

The same experiments have been conducted on the L d set. Although the CPU time is slightly larger than for the L s set, the same interpretations can be deduced: SECM H is faster than SECM E and SECM E achieves the lowest objective function values.

Table 9 :

 9 Analysis of the Optimization performances of SECM using Ls set, γ = 0.5 and r = 1.

				SECM H			SECM E
			J SECM	Js (×10 -3 )	CPU (s)	J SECM	Js (×10 -3 )	CPU (s)
	Column	0 10 20	0.0 ± 0.0 110.1 ± 1.4 61.4 ± 2.3 0.10 ± 0.01 0.0 ± 0.0 0.30 ± 0.01 124.7 ± 0.9 73.4 ± 1.5 0.08 ± 0.00	0.0 ± 0.0 86.6 ± 0.9 104.1 ± 0.7	0.0 ± 0.0 0.30 ± 0.01 1.1 ± 0.6 5.31 ± 0.64 6.8 ± 0.8 1.97 ± 0.14
		30	135.9 ± 0.9 81.9 ± 1.3 0.11 ± 0.00	118.3 ± 0.8 14.6 ± 0.8 1.42 ± 0.04
	Ionosphere	0 10 20 30	0.2 ± 0.0 237.1 ± 0.5 252.7 ± 0.8 13.0 ± 0.5 0.78 ± 0.01 0.0 ± 0.0 2.56 ± 0.2 1.6 ± 0.2 1.03 ± 0.03 266.2 ± 0.8 29.6 ± 0.9 0.69 ± 0.01	0.2 ± 0.0 236.6 ± 0.5 251.6 ± 0.7 265.2 ± 0.8 24.9 ± 0.8 1.45 ± 0.03 0.0 ± 0.0 2.56 ± 0.20 0.0 ± 0.0 2.57 ± 0.07 7.0 ± 0.4 1.69 ± 0.04
		0	0.0 ± 0.0	0.0 ± 0.0 1.94 ± 0.06	0.0 ± 0.0	0.0 ± 0.0 1.94 ± 0.06
	Iris	10 20	10.8 ± 0.1 11.8 ± 0.1	0.7 ± 0.2 0.95 ± 0.05 0.9 ± 0.2 0.63 ± 0.03	10.4 ± 0.0 11.3 ± 0.1	0.0 ± 0.0 3.27 ± 0.14 0.0 ± 0.0 2.26 ± 0.09
		30	12.5 ± 0.1	1.1 ± 0.2 0.51 ± 0.02	12.0 ± 0.1	0.0 ± 0.0 1.92 ± 0.07
	LettersIJL	0 10 20	0.2 ± 0.0 420.5 ± 1.4 25.4 ± 1.3 3.01 ± 0.22 0.0 ± 0.0 7.61 ± 0.63 463.	0.2 ± 0.0 415.4 ± 1.3	0.0 ± 0.0 7.61 ± 0.63 0.3 ± 0.1 7.07 ± 0.78

0 ± 1.5 56.0 ± 1.6 2.17 ± 0.11 461.1 ± 1.5 37.1 ± 1.5 4.60 ± 0.

19 30

493.1 ± 1.5 100.0 ± 2.2 2.15 ± 0.13 492.5 ± 1.5 92.4 ± 2.