Safa Ben Ayed

Zied Elouedi

Eric Lefevre

Exploiting domain-experts knowledge within an evidential process for case base maintenance

Case Base Maintenance (CBM) presents one of the key factors success for Case Based Reasoning (CBR) systems. Thence, several CBM policies are proposed to improve their problem-solving performance and competence. However, to the best of our knowledge, all of them are not able to make use of prior knowledge which can be offered by domain experts, especially that CBR is widely applied in real-life domains. For instance, given symptoms of two different cases in medicine area, the doctor can affirm that these two cases should never follow the same treatment, or conversely. This kind of prior knowledge is presented in form of Cannot-Link and Must-link constraints. In addition, most of them cannot manage uncertainty in cases during CBM. To overcome this shortcoming, we propose, in this paper, a CBM policy that handles constraints to exploit experts' knowledge during case base learning along with managing uncertainty using the belief function theory. This new CBM approach consists mainly in noisy and redundant cases deletion.

Introduction

Case Based Reasoning is a methodology for reasoning through adapting previous experiences to solve new problems. Each success solving operation will be retained for future learning, where an incremental aspect characterizes the case bases evolution [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]. As CBR systems are widely applied within real-life domains, and as they are designed to work over long time frames, the Case Base Maintenance (CBM) becomes a fundamental task to guarantee their success. In fact, CBM has been defined as the field that cares on implementing policies that aim to reach a particular set of performance objectives through revising the content and the organization of case bases [START_REF] Wilson | Maintaining case-based reasoners: Dimensions and directions[END_REF]. Indeed, we note a great interest within current research that addresses issues for growing case bases. For instance, CBM policies may be divided into two strategies, even to the optimization strategy where the deletion is done after optimizing a given evaluation criterion, or to the partition strategy which allows to treat a set of small case bases independently. In the latter strategy, uncertainty about the membership of cases to the different classes (clusters) have also been handled [START_REF] Smiti | SCBM: soft case base maintenance method based on competence model[END_REF] [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF]. However, these CBM policies are not offering the possibility to exploit background knowledge which can be provided by an expert of domain in which the CBR system is deployed. Therefore, we aim, in this paper, to propose a new CBM approach based on an evidential clustering to manage uncertainty about the membership of cases.

Moreover, this approach handles extra-information for cases clustering presented in the form of two types of constraints [START_REF] Wagstaff | Constrained k-means clustering with background knowledge[END_REF]: Must-link constraints which specify that two cases have the same solution and Cannot-link constraints which specify that two solutions cannot belong to the same cluster. To do, we used then the Constrained Evidential C-Means algorithm (CECM) [START_REF] Antoine | CECM: Constrained evidential Cmeans algorithm[END_REF]. The remainder of this paper is organized as follows. Section 2 reviews briefly some CBM approaches based on clustering techniques. Section 3 describes the used constrained evidential clustering technique called CECM. Our new CBM approach will be detailed in Section 4. Throughout Section 5, we discuss experimental settings, the pairwise constraints generation, testing strategy, and results.

Clustering-based CBM policies

Intuitively, when addressing the problem of maintaining a large case base, its decomposition into a number of related closely cases groups appears to be a good solution for their maintenance. Indeed, clustering techniques have been well applied within CBR since the notions of neighborhood and distances between cases are well presented. Actually, there are several works in this way. However, during the rest of this Section, two of them which handle uncertainty regarding the membership of cases to different clusters will be reviewed. The first one is called SCBM noting "Soft case base maintenance method based on competence model" which groups cases within the frame of fuzzy sets theory [START_REF] Zadeh | Fuzzy sets[END_REF]. Then, it tries to detect the right case types to be removed without decreasing the competence of the CBR system. The second policy is named ECTD for "Evidential Clustering and case Types Detection for case base maintenance" which is more able to manage uncertainty using the belief function theory [START_REF] Shafer | A mathematical theory of evidence[END_REF] [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. First, ECTD applies ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] algorithm to group cases and obtain the credal partition of cases along with the different clusters centers. Then, it reasons on the way of detecting four types of cases in order to be able at the end to eliminate noisiness and redundancy. However, techniques used inside these methods do not allow to make use of the background knowledge that helps to guide to the best solution. For this paper, we consider prior knowledge in form of Must-link and Cannot-link constraints. To do, we apply on the case base a constrained evidential clustering technique as presented in the following Section.

Constrained evidential clustering technique: CECM

When dealing with clustering-based CBM policies, it is gainful to express prior knowledge in form of instance level constraints as indicated in the Introduction.

In what follows, we will present CECM through its constraints expression and work standard.

Constraints expression by CECM

Let two objects o i and o j and their associated mass functions m i and m j . The mass function m i×j regarding their joint class membership may be calculated in the Cartesian product Ω 2 = Ω × Ω, as the combination between m i and m j [START_REF] Smets | The transferable belief model[END_REF] such that:

m i×j (A × B) = m i (A) m j (B) , A, B ⊆ Ω, A = ∅, B = ∅ (1a) m i×j (∅) = m i (∅) + m j (∅) -m j (∅) m j (∅) (1b)
Let the subset θ = {(ω 1 , ω 1 ), (ω 2 , ω 2 ), ..., (ω c , ω c )} in Ω 2 (where c is the number of classes) presents the event "The pair of objects o i and o j belong to the same class". Therefore, after calculating the plausibility pl i×j from m i×j , the value pl i×j (θ) = 0 corresponds to a Cannot-link constraint (C) between o i and o j and the value pl i×j (θ) = 0 corresponds to a Must-link constraint (M) between o i and o j .

Objective function and Optimization of CECM

First of all, let mention that CECM [START_REF] Antoine | CECM: Constrained evidential Cmeans algorithm[END_REF] is a variant of ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] algorithm (noisiness is assigned to the empty set partition). The principle of both of them during the evidential clustering is to minimize an objective function in order to maximize distances between objects belonging to different classes and minimizing those belonging to the same one. The objective function for ECM algorithm is defined such that:

J ECM (M, V ) = 1 2 c n [ n i=1 A k =∅ |A k | α m β ik d 2 ik + n i=1 ρ 2 m β i∅ ] (2)
subject to:

j/Aj ⊆Ω,Aj =∅ m ij + m i∅ = 1 ∀i = 1, .., n (3)
where M represents the credal partition of n objects to c clusters, V presents 2 c clusters centers, d ij represents a given distance between o i and o j , ρ and β are two parameters to treat noisy objects, and the coefficient α controls the penalization of degree's allocation to subsets with high cardinality. CECM algorithm shares the same standard of ECM with an additional requirement that pl i×j (θ) (respectively pl i×j (θ)) should be as low as possible if (o i , o j ) ∈ C (respectively (o i , o j ) ∈ M). Consequently, its objective function to be minimized is defined such that:

J CECM (M, V ) = (1 -ξ)J ECM (M, V ) + ξJ CON ST (4)
where the parameter ξ controls the balance between constraints and geometrical model, and J CON ST , which indicates C and M violating cost, is defined such that:

J CON ST = 1 |M| + |C| [ (o i ,o j )∈M pl i×j (θ) + (o i ,o j )∈C pl i×j (θ) ] (5)
To minimize Equation 4, an alternate optimization scheme has been proposed in [START_REF] Antoine | CECM: Constrained evidential Cmeans algorithm[END_REF] aiming to fix the partition matrix M and the centroid matrix V . Furthermore, CECM with adaptive metric (Mahalanobis distance) is proposed to support arbitrary shapes of clusters. More details of optimization will be found on [START_REF] Antoine | CECM: Constrained evidential Cmeans algorithm[END_REF].

Maintaining case bases through Constrained Evidential Clustering and case Types Detection (CECTD)

In this Section, we present the different steps of our CBM approach. To build our case base maintainer, our method applies the constrained evidential clustering analysis, detects cases that should be eliminated from the case base, and performs the maintenance.

Case bases clustering with background knowledge

First, we perform on case bases the CECM constrained evidential clustering as presented in Section 3, where each object is considered as a case and its class presents the solution part of that case. The background knowledge is presented as case-level constraints. Actually, CECM algorithm manages uncertainty by offering clusters centers along with the credal partition which provides the belief degree of cases membership to the different partitions. These two outputs are the source of case types detection strategy.

Case types detection

Several works on the CBM field divide cases into different types according to their role towards to whole case base or their competence for other problems resolution. In this paper, we classify cases into four types [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF][3] such that:

-Noisy cases: They present a distortion of values and cannot be correctly classified in any one of clusters. -Similar cases: They present a number of cases which are so close that they are considered as redundant. -Isolated cases: They are dissimilar and situated in clusters borders.

-Internal cases: They present the center of each group of similar case.

Detect Noisy cases Since CECM algorithm allocates a high belief's degree to the empty set for noisy cases, we propose, as in [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF], to detect them such that:

x i ∈ N C if f m i (∅) > Aj ⊆Ω,Aj =∅ m i (A j ) (6)
where x i presents one case and N C represents the set of all the Noisy cases.

Distinguish between Similar and isolated cases Let c clusters are obtained after cases clustering step. Logically, the majority of cases are situated in the core of each cluster (Similar cases). However, we find some cases which are isolated and far somehow to the cluster's center (Isolated cases). To distinguish between these two types, we compare cluster-case distance to a given threshold (T h k ) which has been defined as the mean of all cases distances to a given cluster's

Threshold of BMDs

Fig. 1. Distinguish between similar and isolated cases within a cluster using a threshold center (see Figure 1). To calculate the distance between a case and cluster's center, we chose to use the following Belief Mahalanobis Distance (BMD) [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF]:

BM D(x i , v k ) = (x i -v k ) T Σ -1 k (x i -v k ) ( 7
)
where v k is the k th cluster's center generated by CECM, and Σ k presents the Belief Covariance Matrix which has been presented in [START_REF] Antoine | CECM: Constrained evidential Cmeans algorithm[END_REF] as follows:

Σ k = n i=1 Aj w k ,Aj ⊆Ω m 2 ij |A j | α-1 (x i -v j )(x i -v j ) T ( 8
)
where k is the cluster's number with k = 1, .., c, m ij and v j are respectively the credal partition and their prototypes defined by CECM. Ultimately, we distinguish between Similar and Isolated cases such that:

x i ∈ SC k if ∃k/BM D(x i , v k ) < T h k IsC Otherwise ( 9
)
where SC k is the set of similar cases, IsC is the set of Isolated ones and the threshold T h k is defined such that:

T h k = x i / ∈N C BM D(x i , v k ) #T otalCases -#N oisyCases (10)
Flag Internal cases From each group of Similar cases, we have to flag an internal case as a representative for covering all of them. Hence, we choose to detect this case as the closest one to each cluster's center using BMD. Hence, they can be formally defined such that:

x i ∈ InC if f ∃k; ¬∃x j /BM D(x j , v k ) < BM D(x i , v k ) ( 11
)
where x i and x j are two cases, and InC represents the set of Internal cases.

Case base maintenance

While maintenance, we aim to remove cases that are dispensable or distorting the problem-solving process. Through this idea, we remove cases detected as Similar in order to eliminate redundancy and improve performance, as well as Noisy cases so as to improve the competence of CBR systems in problem resolution.

Experimental study using artificial constraints

During this Section, we aim to differently generate the pairwise Must-link and Cannot-link constraints, as well as to validate our new CBM method benefit.

Experimental setting

Our new CBM approach has been developed using R-3.3.2 and it is tested on a number of numeric case bases from UCI Repository which are described in Table 1 by their references, number of attributes, size, number of classes and their classes distribution. While developing, default values are taken for the CECM parameters, and the number of clusters and classes were equally taken. Besides, we used CECM with adaptive metric to consider arbitrary clusters' shape.

Pairwise constraints generation

The aim of this subsection is to implement two different ways for artificiallygenerating constraints in conjunction with experiments applied on our method. The idea consists in randomly picking two cases. If they are classified with high degree of certainty (m i (A) > 0.5 with A is a singleton partition), we generate a constraint through their solution (If they have the same solution, we create a Must-link constraint, otherwise we generate a Cannot-Link constraint). Therefore, we perform the following two ways:

-Batch constraints generation (CECTD bat ): Apply ECM algorithm (CECM without constraint), generate a number of constraints equal to 10% of the case base size. Then, apply our CECTD method. -Alternate constraints generation (CECTD alt ): Within the first step of our method, we alternate between running CECM and generating randomly one constraint having high degree of certainty, until reaching 10% of constraints.

Maintenance testing strategy

To measure the effectiveness of our maintaining method, we track the following testing strategy. Each case base is divided into Training set (T r ) and Test set (T s ), and we apply our maintaining method on T r to obtain a modified Training set (T r ). Then, we compute three evaluation criteria as follows:

1. Classify T s from T r using 1-Nearest Neighbor algorithm. Therefore, the classification accuracy to measure the performance is calculated such that:

P CC(%) = # correct classif ications on T s size of T s × 100
2. Measure the Retrieval Time (RT ) as the time spent to classify all cases' instances in T r using 1-NN. 3. Calculate the storage size as the data Retention Rate (RR) of T r comparing to T r as follows:

RR (%) = size of T r size of T r × 100
The final estimation of each evaluation criterion is obtained by averaging ten trials values using 10-Folds cross validation technique.

Experimental results

According to the evaluation criteria mentioned above, we compare our method with its two different ways to generate constraints (CECTD bat and CECTD alt ) to the Initial case base (ICBR) as well as to ECTD method [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF]. Results are therefore shown in Tables 2 and3. Obviously, we tolerate some degradation in accuracy after maintenance at the aim of accelerating cases retrieving task and improving CBR systems performance. Nevertheless, Table 2 shows some improvements in accuracy especially with the alternate version of our approach. For instance, it moves from 80.78% to 82.10% after applying CECTD alt . In parallel, Table 3 presents, in term of cases retention rate and retrieval time, how our approach can notably boost CBR systems. Herein, we note that we were able to reduce more than half of all case bases. For example, "Heberman" dataset were reduced by CECTD alt until almost quarter. Moreover, even with using 1-NN for classification, we clearly note the improvement of retrieval time values particularly comparing to the Initial non-maintained case base, where all of them move from about 0.1 s to about 0.001 s.

Table 1 .

 1 UCI data sets used in our experimental study

	Case base	Reference Attributes Instances Classes Class distribution
	Sonar	SN	60	208	2	97/111
	Ionosphere	IO	34	351	2	226/125
	Heberman	HB	3	306	2	225/81
	Seeds	SD	7	210	3	70/70/70
	Mammographic	MM	6	961	2	516/445
	Banknote authentication	BA	5	1372	2	762/610

Table 2 .

 2 Accuracy evaluation (%)Case bases ICBR ECTD CECTD bat CECTD alt

	SN	80.78 68.31	79.78	82.10
	IO	85.47 79.45	85.00	84.90
	HB	72.88 67.23	70.85	72.88
	SD	90.00 83.16	88.70	90.18
	MM	79.81 72.13	80.01	79.92
	BA	99.12 86.40	88.97	95.14

Table 3 .

 3 Data Retention Rate (%) and Retrival Time (s) evaluationAiming at the performance and learning capability issues that the growing scale of CBR case bases brings, a new CBM approach based on a constrained evidential clustering technique has been developed, in this paper, using two ways for constraints generation with managing uncertainty. Better results are offered, during experiments, when generating constraints one by one alternatively with running CECM.

	CB	ICBR		ECTD		CECTD bat		CECTD alt
		RR	RT	RR	RT	RR	RT	RR	RT
	SN 100	0.1003 48.98	0.0021 48.50	0.0026 46.51	0.0020
	IO 100	0.0094 37.04	0.0017 35.36	0.0017 33.89	0.0015
	HB 100	0.0993 29.72	0.0027 34.52	0.0021 28.14	0.0019
	SD 100	0.0911 44.13	0.0023 45.77	0.0018 43.98	0.0016
	MM 100	0.0852 26.23	0.0014 39.57	0.0016 40.02	0.0022
	BA 100	0.1033 31.82	0.0026 44.54	0.0036 39.15	0.0027
	6 Conclusion


Safa Ben Ayed
email: safa.ben.ayed@hotmail.fr

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

CEC-Model: A new competence model for CBR systems based on the belief function theory

Keywords: case-based reasoning, competence model, cases coverage, belief function theory, uncertainty, clustering

The high influence of case bases quality on Case-Based Reasoning success gives birth to an important study on cases competence for problems resolution. The competence of a case base (CB), which presents the range of problems that it can successfully solve, depends on various factors such as the CB size and density. Besides, it is not obvious to specify the exactly relationship between the individual and the overall cases competence. Hence, numerous Competence Models have been proposed to evaluate CBs and predict their actual coverage and competence on problem-solving. However, to the best of our knowledge, all of them are totally neglecting the uncertain aspect of information which is widely presented in cases since they involve real world situations. Therefore, this paper presents a new competence model called CEC-Model (Coverage & Evidential Clustering based Model) which manages uncertainty during both of cases clustering and similarity measurement using a powerful tool called the belief function theory.

Introduction

Among the main concerns within the knowledge engineering field is to offer techniques aiming to assess informational resources. In particular, the community of Case-Based Reasoning (CBR) provides a specific interest to evaluate case bases since their quality presents the key factor's success of CBR systems. In fact, the higher the quality of this knowledge container, the more "competent" it is. Actually, the competence (or coverage) of a CBR system refers to its cabability to solve target problems. That's why, the notion of case competence is widely used, also, within the field of Case Base Maintenance (CBM), where most of the CBM policies ( [START_REF] Smyth | Competence models and the maintenance problem[END_REF], [START_REF] Smiti | SCBM: Soft Case Base Maintenance method based on competence model[END_REF], [START_REF] Smyth | Building compact competent case-bases[END_REF], [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF], [START_REF] Ben Ayed | DETD: Dynamic policy for case base maintenance based on EK-NNclus algorithm and case Types Detection[END_REF], etc.) do their best to maintain the most competent cases. However, this key evaluation criterion is difficult to predict since the true character of competence within CBR as well as its sources are not well comprehensible [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF]. Moreover, even if we could estimate the competence of an individual case, the estimation of the global case base competence remains complex because of the lack of clarity towards the relationship between local and global competence contribution. By this way, we find several research, over the years, that are interested on case base competence notion, where some of them offer case competence models for CBs evaluation. Typically, case competence models divide cases into competence groups, then estimate cases coverage using similarity measures. Their theoretical contributions are obviously well defended. However, the embedded imperfection in cases was totally neglected within this area, especially that each case refers to one real world experience. Evidently, events and situations occured within our world are full of uncertainty and imprecision. Therefore, we propose, in this paper, a new case competence model, called CEC-Model encoding "Coverage & Evidential Clustering based Model", that aims to accurately evaluate the overall case base coverage using the belief function theory [2] [3]. This theory offers all the necessary tools to manage all the levels of uncertainty in cases. Through Fig. 1, it is straighforward to show the different fields intersection leading to build and construct our new competence model. In a nutshell, CEC-Model divides the case base into groups using the evidential clustering technique called ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. Then, it uses a distance within the belief functions framework that leads, ultimately, to estimate the global coverage of the case base. Like the competence model on which we are based [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] to estimate the relation between local case competence and global CB competence, our CEC-Model makes some assumption; First, we assume that the set of cases in the CB presents a representative sample of the set of target problems. Second, we assume that the problem space is regular, where we are based on the CBR hypothesis "Similar problems have similar solutions". The reminder of this paper is organized as follows. In section 2, we overview the related work of the Competence concept by offering its foundation, defining the basic factors affecting the case base competence, and presenting some competence models. Section 3 offers the basic concepts of the belief function theory as well as the used evidential tools for building our model. Throughout Section 4, our new CEC-Model is described in details through its different steps. Finally, our model is supported in Section 5 using an experimental analysis.

General Outlook on Case-Base Competence

A case base is said to be "effective" when it is able to offer solutions efficiently and successfully to solve as many target problems as possible. To evaluate the case base effectiveness for CBR systems, two criteria are generally used: Performance (Definition 1) and Competence (Definition 2). Definition 1. The Performance is the answer time that is necessary to generate a solution to a target problem. Definition 2. The Competence is the range of target problems that can be successfully solved.

Contrary to the competence, the performance criterion for a case base can be straightforward measured. Hence, we will focus, in the following of this Section, on the competence criterion by presenting its foundations (Subsection 2.1), its influencing factors (Subsection 2.2) and some existing models to predict the overall case base competence (Subsection 2.3).

Case Competence Foundations

When we talk about case competence, two main concepts arise: case Coverage (Definition 3) and case Reachability (Definition 4). Definition 3. The coverage of one case is the set of target problems that this case is able to solve. It is defined formally as follows [START_REF] Smyth | Competence models and the maintenance problem[END_REF]:

CB = {c 1 , .., c n }, c ∈ CB, Coverage(c) = {c ∈ CB/Solves(c, c )} (1)
where CB presents the case base and Solves(c, c ) is the fact that the case c is able to solve the case c .

Definition 4. The reachability of a target problem is the set of cases that can be used to solve it. It is defined such that [START_REF] Smyth | Competence models and the maintenance problem[END_REF]:

CB = {c 1 , .., c n }, c ∈ CB, Reachability(c) = {c ∈ CB/Solves(c , c)} (2)
These two latter definitions are based on the assumption that the case base presents the representative sample of all target problems. In fact, it is impossible in the reality to define and fix the entire set of all the target problems. Besides, in that step, we are not intended to explicitly define the predicate "Solves".

For the sake of clarity regarding Definitions 3 and 4, we illustrate in Fig. 2 an example. Let c 1 , c 2 and c 3 three cases, and their coverage are labeled with 1, 2 and 3 respectively. Therefore, Coverage(c 2 ) = {c 2 , c 3 } and Reachability(c 2 ) = {c 2 , c 1 }. Logically, we assign more interest to cases having a large coverage an a small rechability set. In this paper, we restrict the competence of the case base to its overall coverage. However, the interaction between local competences is necessary to well estimate the entire case base's coverage. Moreover, several factors can influence the prediction of this criterion.

Basic factors influencing case base competence

Building an appropriate competence model requires an awareness on the different factors influencing CB's competence as well as understanding how they affect it. Actually, several factors have been studied in the literature. On the one hand, we find statistical properties such that the CB's size, distribution and density of cases [START_REF] Smyth | Remembering to forget: A Competence-Perserving Deletion Policy for CBR systems[END_REF] [9] [START_REF] Riesbeck | Inside case-based reasoning[END_REF]. On the other hand, the competence is naturally relied to the problem solving properties such as vocabulary, similarity and adaptation knowledge [START_REF] Arshadi | Feature Selection for Improving Case-Based Classifiers on High-Dimensional Data Sets[END_REF] [START_REF] Ayeldeen | Case selection strategy based on K-means clustering[END_REF], as well as individual cases coverage [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] [7] [START_REF] Smyth | Case-base maintenance[END_REF]. Similarly to some other research [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] [9], we focus in this paper to understand and measure this competence through case base size and density factors as well as the coverage concept.

Case Competence Modeling

In the literature, various ways are proposed to model cases competence in order to evaluate the ability of case bases on problem solving. Besides, these models can be the basis of numerous case base maintenance approaches. Hence, we present in what follows three among the most known case competence models.

Model 1: Case Competence Categories [START_REF] Smyth | Remembering to forget: A Competence-Perserving Deletion Policy for CBR systems[END_REF]: Based on the notions of coverage and reachability, Smyth & Keane classify cases according to their competence characterization into four types, where the following Definitions arise. Definition 5. Pivotal cases represent single way to solve a specific problem. They are defined such that:

P ivot(c) if f Reachability(c) -{c} = ∅ (3)
Definition 6. Auxiliary cases are totally subsumed by other cases. They do not influence the global competence at all. Hence, they are defined such that:

Auxiliary(c) if f ∃c ∈ Reachability(c) -{c}/ Coverage(c) ⊂ Coverage(c ) (4)
Definition 7. Spanning cases do not directly influence the CB competence.

They link together regions covered by the two previous types of cases (Pivotal and Auxiliary).

Definition 8. Support cases exist in groups to support an idea. Each support case in a support group provides the same coverage as the other cases belonging to the same group. They are formally defined such that:

Support(c) if f ∃c ∈ Reachability(c) -{c}/Coverage(c ) ⊆ Coverage(c) (5)
For further clarification, and by returning to Fig. 2, we mention according to the four previous Definitions that c 1 represents a Pivotal case, c 2 presents a Spanning case, and c 3 is an Auxiliary case. Concerning Support cases, Fig. 3 illustrates three examples of them that cover the same space.

Model 2: Coverage model based on Mahalanobis Distance and Clustering (CMDC) [START_REF] Smiti | Modeling competence for case based reasoning systems using clustering[END_REF]: Based on the idea that the CB's competence is proportional to individual case's contribution, CMDC defines the overall case base competence as follows:

Comp%(CB) = |1 - K j=1 N i=1 Cov(c ij ) SizeCB | ( 6
)
where K is the number of groups building the CB, N is the size of the j th group, and Cov(c ij ) represents the coverage of case i towards cluster (group) j.

After applying the DBSCAN-GM algorithm [START_REF] Smiti | Dbscan-gm: An improved clustering method based on gaussian means and dbscan techniques[END_REF] for clustering cases belonging to the CB, this model proposes a classification of cases into three types in order to calculate Cov(c ij ) used in Equation 6. The first type concerns Noisy cases where their coverage is null since they are considered as a distortion of values. The second type concerns a closely group of cases existing on the core of one cluster and named Similar cases. The coverage of Similar cases is equal to their cardinality within each group. Finally, Internal cases represent cases that are situated in the border of each cluster. They only cover themselves and their coverage is equal to one (See Fig. 4).

Fig. 4: Cases types defined by CMDC model [START_REF] Smiti | Modeling competence for case based reasoning systems using clustering[END_REF] Actually, this model was the basis of several policies aiming to maintain case bases for CBR systems, such that [START_REF] Smiti | SCBM: Soft Case Base Maintenance method based on competence model[END_REF], [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF], [START_REF] Ben Ayed | DETD: Dynamic policy for case base maintenance based on EK-NNclus algorithm and case Types Detection[END_REF], etc. [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF]: Basically, S&M model tries to estimate the competence by finding and encoding the crucial relationship between individual case (local) and the entire CB (global) competence. To do, S&M identifies the fundamental unit of competence as the competence group of cases.In fact, within a very traditional point of view, this unit was "the case" only. To recognize these groups, authors in [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] define a competence group as the set of cases that have a shared coverage. Formally, this is defined such that:

Model 3: Smyth & McKenna (S&M) model
F or G = {c 1 , .., c p } ⊆ CB, CompetenceGroup(G) if f ∀c i ∈ G, ∃c j ∈ G -{c i } : SharedCoverage(c i , c j ) ∧∀c k ∈ CB -G, ¬∃c l ∈ G : SharedCoverage(c k , c l ) (7)
where

F or c 1 , c 2 ∈ CB SharedCoverage(c 1 , c 2 ) if f Coverage(c 1 ) ∩ Coverage(c 2 ) = ∅ (8)
To ease the concept of competence group, we indicate using Fig. 2 that the different cases c 1 , c 2 and c 3 present only one coverage group since they share their coverage (similarly for Fig. 3).

Furthermore, S&M model allocate a considerable interest to identify Coverage groups since the larger group coverage means a larger ability to solve target problems. By this way, authors in [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] affirm that it is mainly depending on the size and density of cases. Obviously, the first factor is straightforward calculated. However, the density of cases is defined such that:

GroupDensity(G) = c∈G CaseDensity(c, G) |G| (9)
where CaseDensity(c, G) presents the local density of the case c within the group G ⊂ CB, and |G| is the number of cases belonging to G.

Since the coverage of a group must be directly proportional to its size and inversely proportional to its density, the current model defines it as follows:

GroupCoverage(G) = 1 + [ |G| (1 -GroupDensity(G)) ] (10)
Undoubtedly, the proposed contributions to model cases competence are interesting. However, they remain limited by their disability to manage uncertainty within knowledge, especially for real experiences (cases). The next Section presents, therefore, a powerful tool used for this matter called the Belief function theory.

Belief Function Theory: Basic Concepts

The belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] [3], also known by Evidence theory or Dempster-Shafer theory, is a theoretical framework for reasoning under partial and unreliable (uncertain and imprecise) information. It was introduced by Dempster and Shafer [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] [3], and then studied by Smets [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF] [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF]. As a generalization of other uncertainty management theories [START_REF] Feller | An introduction to probability theory and its applications[END_REF] [21] [START_REF] Dubois | Possibility theory. Computational complexity[END_REF], belief function theory proved to be effective in various applications. The rest of this Section will recall the main definitions and concepts and the used tools offered within this theory.

Let ω be a variable taking values in a finite set Ω = {w 1 , .., w K } named the frame of discernment. The mass function m(.), which represents the uncertainty and imprecision knowledge about the actual value of ω, is defined as an application from the power set of Ω (2 Ω ) in [0, 1] and satisfying A⊆Ω m(A) = 1 [START_REF] Arshadi | Feature Selection for Improving Case-Based Classifiers on High-Dimensional Data Sets[END_REF] Actually, m(A) can be viewed as the degree of belief committed exactly to the subset of events A. A is called focal element if m(A) > 0, and the mass function m is equivalent to a probability distribution when all the focal elements are singletons. It is then called Bayesian mass function.

Since two events within the belief function theory are mainly described by their mass functions, it is also interesting to measure the similarity and distance between them. One of the most known and used distances between two pieces of evidence is called the Jousselme Distance of evidence [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]. Given two pieces of evidence m 1 and m 2 on the same frame of discernment, the Jousselme distance between them is defined as follows:

d(m 1 , m 2 ) = 1 2 ( -→ m 1 --→ m 2 ) T D ( -→ m 1 --→ m 2 ) ( 12
)
where D is a 2 K × 2 K matrix whose its elements are calculated as follows:

D(A, B) = 1 if A = B = ∅ |A∩B| |A∪B| ∀ A, B ∈ 2 Ω (13)
To make decision towards the value of ω, the mass function m can be transformed into a pignistic probability distribution BetP [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF] such as:

BetP (A) = B⊆Ω |A ∩ B| |B| m(B) 1 -m(∅) ∀A ∈ Ω (14)
Finally, the decision is made by choosing the variable with the highest BetP value.

Concerning the evidential clustering of n objects, the partial knowledge in that time will concern the membership of objects to clusters. Hence, the frame of discernment Ω, in that case, contains the set of all clusters. Basically, an n × 2 |Ω| credal partition matrix is generated after applying an evidential clustering technique. It offers n mass functions that reflect the membership degrees of belief to each clusters' subset (partition).

The Evidential C-Means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] presents one of the most known evidential clustering techniques. It takes as input the set of n objects and the number K of clusters, and generates as output the credal partition (matrix M ) as well as the prototype (center) of each partition (matrix V ). Like almost of clustering methods, ECM aims to create dense groups by minimizing distances belonging to the same cluster and maximize those belonging to different ones. To do, ECM method intend to minimize the following objective function:

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

j/Aj ⊆Ω,Aj =∅ m ij + m i∅ = 1 ∀i = 1...n (16)
where d ij represents the euclidean distance between the object i and the center of the partition j, the parameter α controls the degree of penalization allocated to partitions with high cardinality, and δ and β are two parameters aiming to treat noisy objects. To minimize the above objective function, an alternation between two steps is performed. The first one consists of supposing that the matrix of centers V is fixed and solving Equation 15 constrained by Equation 16using the Lagrangian technique. Then, the second phase consists to fix the credal partition M and minimize the unconstrained problem defined only by Equation 15.

During this Section, we only focused on the necessary background within the belief function framework that allow to understand our contribution presented hereafter. More details can be found in [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 for quantified belief representation[END_REF], [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF], [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], and [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF].

Coverage & Evidential Clustering based Model (CEC-Model)

The purpose of this Section is to present our new case competence model dedicated for this paper. This model is named CEC-Model and able to manage uncertainty within the base knowledge. It also uses the coverage concept as well as the mathematical relation between the competence of a group and the local competence contribution of its individual cases [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] to provide as output a prediction of the global case base competence. Our model can serve, on the one hand, at evaluating the quality of any given case base. On the other hand, it can be the basis for maintaining case bases by finding, for instance, the combination of cases that offer a maximum rate of global competence offered by CEC-Model.

For the sake of simplicity, the global process followed by our model to reach its objective in estimating the CB competence rate while managing uncertainty is shown in Fig. 5. First of all, we perform the evidential clustering technique to offer a credal partition of cases that allows to manage uncertainty not only towards the membership of cases to clusters, but also towards their membership to all possible subsets of clusters (partitions). At the second level, the credal partition generated during Step 1, which is a way to model cases membership uncertainty, will be used then, during Step 2, to measure the similarity between cases. Besides, it will be transformed using the pignistic probability (Equation 14), during Step 3, to make the decision about the membership of cases to groups. The outcome of both Steps 2 and 3 will serve then to calculate the individual cases densities regarding their groups, the density rate of each group, and the of the different Finally, the global competence rate of overall case base defines the purpose of Step 5, where it is estimated by the average of normalized coverages of all groups composing the case base. In what follows, within the reminder of this Section, we will present in more details every step composing our CEC-Model.

Group cases using

Step 1: Group cases using evidential clustering

In our first Step, we aim to group cases according to their similarities. The more two cases are similar, the more they are able to cover each others. In fact, similarly to several research in competence modeling [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] [14], the idea is that the coverage of one case is defined by the range of cases that are similar to it. Hence, applying a clustering technique based on distances computing offers a simple and reasonable solution to devise the case base into a number of coverage groups. However, the amount of imperfection that is commonly presented in cases knowledge do not allow us to be certain about the membership of cases to the different clusters. For that reason, we make use of the belief function theory and the evidential clustering, more accurately the Evidential C-Means (ECM) technique (see Subsection 3). The idea consists on creating coverage groups with degrees of belief. Finally, the output of this Step is a credal partition containing n pieces of evidence m i describing the belief's degrees of membership.

Step 2: Measure similarity between cases within the evidential framework

At this Step, we aim to take advantage of the offered credal partition to measure the similarities between every couple of cases. A case is therefore characterized by its mass function that defines the membership degrees of belief to every partition of groups. For instance, given three groups G 1 , G 2 and G 3 , the mass function of case c i is presented as a vector where it has the following form:

m i = [m i (∅) m i (G 1 ) m i (G 2 ) m i (G 1 , G 2 ) m i (G 3 ) m i (G 1 , G 3 ) m i (G 2 , G 3 ) m i (Ω)] (17)
Let us remind that the sum of all its elements are equal to one. Now, we have to calculate distances between every two cases through their corresponding pieces of evidence. To do, we choose to use a well known powerful tool within the belief functions community called Jousselme Distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF], which offers results in [0, 1]. Therefore, we build an n×n distances matrix that we called CredDist, where CredDist(c i , c j ) is the result of Jousselme Distance between m i and m j using Equations 12 and Then, the matrix CredSim is generated as follows:

CredSim = Ones -CredDist ( 18
)
where Ones is an n × n matrix filled by 1.

Step 3: Decide the membership of cases to groups

After computing cases distances with taking into account the uncertainty presented in cases, we move on now from the credal level to the pignistic level where we have to make decision about the membership of cases to the different groups.

To do, we transform the mass function of each case to a pignistic probability using Equation 14. Then, we put each case in the group offering the highest pignistic probability value.

Step 4: Estimate the coverage of each group

The challenge of this step consists on finding the best configuration to model the relationship between a local (individual case) and the global (entire CB) competence contributions. As mentioned in Subsection 2.2, several factors are affecting the interaction between them. For our model, and based on [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF], the combination to build the global competence properties of case bases is influenced by two main factors: Size and Density.

As specified in the Introduction, we assume that the problem space is regular. Hence, cases with high density imply a high degree of mutual similarity. Per contra, sparse cases present low degree of mutual similarity. Consequently, our model calculate the local density of a case c towards the group G ⊆ CB in which it belongs as follows:

CaseDensity(c, G) = c ∈G-{c} CredSim(c, c ) |G| -1 (19)
Afterwards, we calculate the density of each group as the average of all its corresponding cases density using Equation 9.

Ultimately, and based on [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF], we define the relationship between the density and the coverage of each group. In fact, dense groups cover smaller target problems space (Density factor). In contrast, groups with higher size cover larger problem space (Size factor). Consequently, we calculate the coverage of each group using Equation 10.

Step 5: Define the global case base competence rate

Last but not least, we aim at estimating the global competence of case bases based on groups coverage computed during the previous step. In S&M model [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF], the global competence is calculated as the sum of all the coverage measurements of groups building the CB. However, we aim in our model to estimate the global competence as a percentage. Then, the proposed global competence rate is calculated as follows:

Comp(CB)% = |Ω| k=1 GroupCov n (G k ) |Ω| ( 20
)
where GroupCov n (G k ) is the normalized coverage of the k th group, defined such that:

GroupCov n (G k ) = GroupCoverage(G k ) -1 |G k | (21)
The demonstration that gives birth to groups coverage normalization formula (and then the global CB competence rate) is presented as follows:

Let Ω be the frame of discernment containing K groups G k . CB = {c 1 , .., c n } is then divided into |Ω| groups: We have: 0

≤ CredSim(c, c i ) ≤ 1 0 ≤ ci∈G-{c} CredSim(c, c i ) ≤ |G| -1 0 ≤ c i ∈G-{c} CredSim(c,ci) |G|-1 ≤ 1 0 ≤ CaseDensity(c, G) ≤ 1 0 ≤ c∈G CaseDensity(c,G) |G| ≤ 1 0 ≤ GroupDensity(G) ≤ 1 1 ≤ 1 + [|G|(1 -GroupDensity(G))] ≤ 1 + |G| 1 ≤ GroupCoverage(G) ≤ 1 + |G| 0 ≤ GroupCoverage(G)-1 |G| ≤ 1 0 ≤ GroupCov n (G) ≤ 1 0 ≤ G∈Ω GroupCov n (G) ≤ |Ω| 0 ≤ G∈Ω GroupCovn(G) |Ω| ≤ 1 0 ≤ Comp(CB) ≤ 1

Experimental Analysis

During the previous Sections, we reviewed the main definitions for competence and coverage modeling, and we proposed a novel model for case bases competence estimation within the frame of belief function theory and evidential clustering. In this Section, we need to support our model using an empirical evidences. The idea is to demonstrate experimentally that our model competence rate predictions are sufficiently match to the actual competence measurements such as the Percentage of Correct Classification (accuracy). Furthermore, it is more reasonable to define the correlation between their values than focusing on which criterion has the highest values. To start, we present the setup of experimentation. Then, we show how to proceed to support our CEC-Model.

Experimental Setup

Our CEC-Model algorithm was developed using Matlab R2015a, and tests were performed on real data sets taken from UCI repository [START_REF] Blake | UCI repository of machine learning databases[END_REF]. In this paper, we share results offered by three data sets 1 that are described in Table 1. In fact, within the context of CBR, attributes are considered as problems description and the class characterizes their solutions. Besides, default values of the ECM algorithm are taken, and the number of clusters is equal to the number of solutions in the CB. Since we will support our model basing on the accuracy criterion, we measure it by applying 10-folds cross validation using the following formula:

P CC(%) = N umber of correct classif ications T otal number of classif ications × 100 [START_REF] Dubois | Possibility theory. Computational complexity[END_REF] where we used the 1-Nearest Neighbor as a classification method.

Evaluation criteria

Our experimental study is divided into two parts, where each one carries on one evaluation criterion. Firstly, we are interested to know the correlation between the actual CB's competence (Accuracy) and the estimated global competence rates predicted by our CEC-Model. The different values are the results of a randomly incremental evolution of case bases. Actually, the higher a positive correlation, the more our model is supported. Hence, we measure this correlation using the Pearson's correlation coefficient [START_REF] Pearson | Mathematical contributions to the theory of evolution. III. Regression, heredity, and panmixia[END_REF] which is bounded between -1 and 1, and defined as follows:

r = n i=1 (a i -a)(b i -b) n i=1 (a i -a) 2 n i=1 (b i -b) 2 (23)
1 Other CBs are offering similar results but are not presented here due to lack of space.

where a i (respectively b i ) are the values of the actual CB's competence (respectively the predicted global competence by CEC-Model), and a (respectively b) presents the mean value of a i (respectively b i ) measurements.

During the second part of our experimentation, we opt to measure the error rate between CEC-Model estimated competence and the PCC values, such that:

Error(%) = |EstimatedComp -P CC| P CC × 100 (24)

Results and discussion

For the first part of our experimentation, results are shown in Fig. 6, where the actual and estimated competence are plotted against the size of three different case bases. These results provide a high support in favor of our CEC-Model. In fact, it seems to be an almost perfect closely relationship between every two curves (problem-solving accuracy and CB's competence), and hence a strong correlation between them. For the sake of precision, we further measured this correlation for every CB using Equation 23and we found high results reflecting a good match between the predicted and the true competence (0.91 for Mammographic Mass, 0.8 for Ionosphere, and 0.83 for Iris). Let us remind that the closer the value to one, the higher the correlation is. In the second results part, we note from Table 2 that our CEC-Model offers close competence estimation to the actual accuracy regarding the totality of the different three tested case bases. Actually, this closeness was measured formally using the error rate criterion (Equation 24), where competitive results were provided comparing to those offered by S&M [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] and CMDC [START_REF] Smiti | Modeling competence for case based reasoning systems using clustering[END_REF] models. For instance, we offered the minimum error rate for Iris data set which is estimated to 0.8%. Besides, the error rate for Mammographic Mass is estimated to environ 5.9%, where it is measured as 21.1% with S&M and environ 13.8% with CMDC (S&M and CMDC models are reviewed in Subsection 2.3).

Conclusion

The evaluation of knowledge resources are regularly a concern of widespread interest in knowledge management systems. In CBR systems, modeling case base competence with managing uncertainty within knowledge is essential to find the real coverage of cases. In this paper, we proposed a new competence model based on a previous work [START_REF] Smyth | Modelling the competence of case-bases. European Workshop on Advances in Case-Based Reasoning[END_REF] with joining the ability to manage all levels of cases membership uncertainty towards groups building the case base, as well as to satisfy the need of imperfection handling when measure similarities and cases density.

To support our model, we tested on data sets from UCI repository [START_REF] Blake | UCI repository of machine learning databases[END_REF] with varying their size. Actually, competence estimations offered by our model are quite closely to the actual competence measurement (Accuracy) with a relatively high positive correlation between them. Since the competence of CBR systems case bases presents the basis of the Case Base Maintenance (CBM) policies, we can, as future work, use our new competence model CEC-Model at the aim of maintaining CBs in order to well detect useless cases for target problems resolution.

Fig. 1 :

 1 Fig. 1: Towards CEC-model

Fig. 2 :

 2 Fig. 2: Concepts of cases Coverage & Reachability

Fig. 3 :

 3 Fig. 3: Example of Support cases towards one Support group

Fig. 5 :

 5 Fig. 5: CEC-Model steps for CB's competence estimation

Fig. 6 :

 6 Fig. 6: Comparing estimated competence using our CEC-Model to the CB's accuracy for Mammographic Mass, Ionosphere, and Iris data sets

Table 1 :

 1 UCI data sets characteristics

	Case base	Attributes Instances Classes Class distribution
	Mammographic Mass	6	961	2	516/445
	Ionosphere	34	351	2	226/125
	Iris	4	150	3	50/50/50

Table 2 :

 2 Results in term of Error rate (%)

	Case base	S&M CMDC CEC-Model
	Mammographic Mass 21.10 13.820	5.928
	Ionosphere	3.544 0.287	1.779
	Iris	4.010 0.927	0.807


Safa Ben Ayed
email: safa.ben.ayed@hotmail.fr

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefèvre
email: eric.lefevre@univ-artois.fr

DETD: Dynamic policy for case base maintenance based on EK-NNclus algorithm and case Types Detection

Keywords: case based reasoning, case base maintenance, belief function theory, uncertainty, clustering, EK-NNclus

Case Based Reasoning (CBR) systems know a success in various domains. Consequently, we find several works focusing on Case Base Maintenance (CBM) that aim to preserve CBR systems performance. Thus, CBM tools are generally offering techniques to select only the most potential cases for problem-solving. However, cases are full of imperfection since they represent real world situations, which makes this task harder. In addition, new problems having substantially new solutions will be found in case bases over the time. Hence, we aim, in this paper, to propose a new CBM approach having the ability to manage uncertainty and the dynamic aspect of maintenance using the evidential clustering technique called EK-NNclus based on belief function theory, where clusters' number is fixed automatically and changes from one maintenance application to another. Finally, the maintenance task is performed through selecting only two types of cases.

Introduction

Case Based Reasoning is an analogy-based problem-solving paradigm which learns from old experiences using a memory called case base [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]. The strength of CBR systems can be summed up through their ability to offer a high-quality solution even with a weak-understanding domains. Besides, CBR systems are characterized by an incremental learning since each solved problem will be stored in order to serve for future problems resolution. There is a wide range of successful CBR applications in several domains such that diagnosis [START_REF] Malek | Design of a case-based reasoning system applied to neuropathy diagnosis[END_REF], design [START_REF] Maher | Case-based reasoning in design[END_REF], help desk [START_REF] Kang | Help desk system with intelligent interface[END_REF], decision support [START_REF] Varshavskii | Analogy-based search for solutions in intelligent systems of decision support integrated models and flexible calculations in artificial intelligence[END_REF], etc. Like all other applications that are designed to work over long period of time, CBR systems need a maintenance task, especially regarding their case bases, since their quality presents the key success of all the system. Actually, the case base of a CBR system should contain only relevant cases in order to improve its competence on problems resolution on the one hand, and its performance by reducing the research time on the other hand. For this reason, case base maintenance operations are generally opting to select from the case base the most competent ones. To obtain that, a number of aspects should be taken into account while maintenance.

First, the maintenance task should take into account the uncertainty aspect. In fact, within real world situations, information are often imprecise, uncertain and/or incomplete. Hence, the most powerful cases in problem resolution cannot be well defined without considering the uncertainty aspect that can be caused by unquantifiable data, user ignorance and/or overlapping of data regions.

Second, CBR systems are exposed with time and with users requirement evolution to new types of solutions for new problems. Hence, the dynamicity in solutions should be managed while the maintenance of case bases which reflects modern and contemporary environment. To manage these solutions along with their problems in the case base, some CBM approaches [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF] [START_REF] Smiti | COID: Maintaining case method based on Clustering, Outliers and Internal Detection[END_REF] [START_REF] Smiti | WCOID: Maintaining Case-Based Reasoning systems using Weighting, Clustering, Outliers and Internal cases Detection[END_REF] opt to partition cases using a clustering technique as a preprocessing task so as to learn from the case base and devise it into a number of small ones. Then, they select the most representative cases from each cluster.

However, the dynamic aspect consists, in our context, on the capacity of the CBM approach to fix dynamically and automatically the number of clusters regardless which time we perform the maintenance. Besides, existing CBM approaches are not offering a dynamic maintenance because they are suitable only for static collections of cases, and their offered maintenance should be accompanied every time by prior information to be well re-applicable. Actually, and to the best of our knowledge, the dynamicity in case bases maintenance for CBR systems is the most neglected aspect in CBM field.

To manage these two aspects while maintenance, we propose, in this paper, a new approach for case base maintenance that uses the belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][9] as one of the most powerful tools for handling uncertainty, more accurately a dynamic evidential machine learning technique called EK-NNclus [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential K-nearest neighbor rule[END_REF].

The rest of this paper is organized as follows. In Section 2, we review some of CBM methods based on clustering technique. The necessary background regarding the belief function theory and the used evidential clustering technique called EK-NNclus [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential K-nearest neighbor rule[END_REF] are offered in Section 3. Section 4 describes the different steps of our proposed approach called DETD for "Dynamic policy for case base maintenance based on EK-NNclus algorithm and case Types Detection". Finally, the experimentation is shown during Section 5.

Case Base Maintenance: Partitioning based policies

Case Base Maintenance represents a fundamental task aiming to give CBR systems the ability to solve effectively new problems within a reasonable time since they are faced to a large number of cases with a continuous evolution [START_REF] Wilson | Maintaining case-based reasoners: Dimensions and directions[END_REF]. Conspicuously, the most intuitively way to deal with large case bases while maintenance is to divide them into a number of small ones. Consequently, it will be easier to handle them. Nevertheless, we find in the literature several policies belonging to other strategies as shown in [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF]. In the remaining of this Section, we review some CBM policies that use the partition strategy, more accurately, the clustering as a machine learning technique.

On the one hand, with considering partition strategy, we find in the literature hard CBM policies that are not able to deal with uncertainty in data. For instance, we cite COID method [START_REF] Smiti | COID: Maintaining case method based on Clustering, Outliers and Internal Detection[END_REF] encoding Clustering, Outliers and Internal case Deletion which is based on a density-based clustering technique for cases gathering and noisy cases detection. Then, it computes cases-clusters distances to flag outliers and internal cases so as to perform the maintenance. As an extention of COID, we find among others, WCOID method [START_REF] Smiti | WCOID: Maintaining Case-Based Reasoning systems using Weighting, Clustering, Outliers and Internal cases Detection[END_REF] which appends a feature weighting technique to give more importance to the most "informative" features in term of problem solving while the maintenance. However, this type of policies is generally reducing the case bases competence since they suffer from their disability to manage uncertainty in cases involving real world situations.

On the other hand, we find a number of CBM policies based on soft clustering techniques which are able to deal with imperfection. Using fuzzy set theory [START_REF] Zadeh | Fuzzy sets[END_REF] for uncertainty management, SCBM method [START_REF] Smiti | SCBM: Soft Case Base Maintenance method based on competence model[END_REF] denoting Soft CBM Competence Based Model was able to handle vagueness in real data by applying foremost the soft clustering technique called Soft DBSCAN-GM (SDG) [START_REF] Smiti | Fuzzy density based clustering method: Soft DBSCAN-GM[END_REF]. Thus, SCBM detects three types of cases in order to maintain case bases by removing noisy and redundant cases. Furthermore, we cite one more CBM policy that tries to deal with all levels of uncertainty in cases, from the complete ignorance to the total certainty, using belief function theory [8] [9]. This approach called ECTD encoding "Evidential Clustering and case Types Detection for case base maintenance". In a nutshell, ECTD approach goes through three main steps: First, it uses the Evidential C-Means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] for the uncertainty management regarding the membership of cases to the different clusters. The partitions centers offered by ECM as well as the different degrees of belief will serve during the second step at the detection of four types of cases: Noisy cases have a high degree of belief to not belonging to any one of clusters, Similar cases are considered as redundant experiences and situated on the core of the different clusters, Isolated cases are situated on clusters borders, so they can only be solved through themselves, and finally Internal cases as the representatives of the different clusters. Ultimately, ECTD accomplishes the maintenance by selecting only cases flagged as Internal or Isolated.

Obviously, ECTD approach [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF] follows a good strategy of maintenance with the ability to manage uncertainty. Besides, it showed practically good results. However, this approach is not able to deal with the dynamic aspect of maintenance where cases are grouped according to their solutions with a predefined and static number of clusters. Hence, it does not take into account the dynamicity of the encountered solutions in the case bases knowing that they contain real experiences. In addition, if the case base contains a high number of distinct solutions categories, ECTD approach suffers from a high complexity when deal-ing with uncertainty towards all possible subsets of solutions. In what follows, we present, therefore, our proposed approach for this paper dealing with these matters, but we offer before that some background related to the belief function theory as well as the used clustering technique.

Background: Belief function theory

In order to manage uncertainty in cases as well as the dynamic aspect of maintenance, our contribution is based on Belief function theory and the evidential clustering technique called EK-NNclus. Hence, we show during this section the basic concepts of this theory as well as the corresponding clustering technique.

Basic concepts

Belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][9] is one of the most used theoretical frameworks for reasoning under uncertainty. It is based on the explicit representation and combination of pieces of evidence. Thus, the problem domain is represented through the frame of discernment (Θ) and containing a finite set of elementary events. Hence, each variable ω takes values from Θ. In this theory, a mass function m represents the uncertain evidence about ω on Θ. Actually, m is the mapping function from the powerset of Θ containing all possible subsets, denoted 2 Θ , to [0, 1] such that:

A⊆Θ m(A) = 1 (1)
where each mass m(A) is the evidence that supports exactly the ascertain ω ∈ A. In particular, if A = Θ, m(Θ) is interpreted as the probability that the evidence does not give us any information about the variable ω from the frame of discernment. If m(A) > 0, the event A is called a focal element. Given a mass function m, the corresponding belief (bel) and plausibility (pl) functions from 2 Θ to [0, 1] are defined such that:

bel(A) = ∅ =B⊆A m(B) ∀A ⊆ Θ (2)
and

pl(A) = A∩B =∅ m(B) ∀A ⊆ Θ (3)
Actually, bel(A) represents the entire belief allocated to support only the event A. However, pl(A) measures the maximum amount of belief that can be assigned to A.

Within belief function theory, several combination rules of evidences can be used. Dempster's rule of combination [START_REF] Shafer | A mathematical theory of evidence[END_REF] is one of the most used ones to combine two pieces of evidence (m 1 and m 2 ) induced from two independent and reliable sources of information. This rule is defined as follows:

(m 1 ⊕ m 2 )(A) = 1 1 -κ B∩C=A m 1 (B) m 2 (C) ( 4
)
where κ is called the conflict of the global combination and defined such that:

κ = A∩B=∅ m 1 (A) m 2 (B) (5)
One of the techniques that allow us to make decision within the belief function framework is the pignistic probabilities transformation and defined as follows:

BetP (A) = B⊆Θ |A ∩ B| |B| m(B) 1 -m(∅) ∀A ∈ Θ (6)
The decision making is therefore done through the variable having the highest pignistic probability.

Evidential clustering: EK-NNclus

Evidential clustering techniques are aiming to generate credal partition for managing uncertainty in cases' membership to clusters. Among the most known ones, we cite Evidential c-means [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], EVCLUS [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] and EK-NNclus [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential K-nearest neighbor rule[END_REF] which is based on EKNN rule [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF].

The Evidential K-Nearest Neighbor (EKNN) rule: In EKNN rule, the knowledge that an object o is distant from an object o j with a value d j produces the following piece of evidence m j on Θ = {ω 1 , ..., ω c }:

m j ({ω k }) = u jk ϕ(d j ) , k = 1, ..., c (7a)
m j (Θ) = 1 -ϕ(d j ) (7b)
where lim d→∞ ϕ(d) = 0, and u jk = 1 if o j is classified in ω k and 0 otherwise.

The K mass functions obtained through the K nearest neighbors are combined then using Dempster's rule as defined in Equations 4 and 5. To make decision about the membership of cases, the combined contour function for l = 1, .., c is defined such that:

pl(ω l ) ∝ j∈N K (1 -ϕ(d j )) 1-u jl (8)
and its logarithm can be written as follows:

ln pl(ω l ) = n j=1 v j u jl + C (9)
where N K denotes the indices set of K nearest neighbors, C is a constant, v j = -ln(1 -ϕ(d j )) if j ∈ N k , and v j = 0 otherwise.

EK-NNclus:

The EK-NNclus algorithm is a decision-directed clustering procedure based on the above EKNN rule. For the initialization step, EK-NNclus starts with a randomly labeled objects (each object exists lonely in one cluster if the number of objects n is not too large, otherwise the number of clusters c will be taken large but lower than n). For objects membership to clusters, we initialize u ik to 1 if the object o i belongs to cluster k and to 0 otherwise. Using EKNN rule, the algorithm's iteration updates the object labels in some randomly order. Then, using Equation 9, the logarithms of the membership plausibilities of each object to each cluster are computed as:

u ik = j∈N K (i) v ij s jk , k = 1, .., c (10)
where N K (i) is the set of indices of the K-NNs of the object o i . The membership of the object o i is then updated according to the highest plausibility such that:

s ik = 1 if u ik = max k u ik 0 Otherwise. (11)
A new iteration is started with a randomly reordered objects if exists at least one object that its label changes. In addition, we note a disappearance of clusters from an iteration to another. Finally, and after the convergence of the number of clusters (demonstrated in [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential K-nearest neighbor rule[END_REF]), the resulting mass function is computed as:

m i = j∈N K (i) m ij (12)
where the different bbas m ij are calculated using Equation 7.

To conclude, EK-NNclus algorithm provides a simpler credal partition compared to other techniques such as ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] and EVCLUS [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] which yield mass functions with 2 Θ focal sets. Hence, EK-NNclus is able to avoid the exponential complexity when treating a large number of clusters and it has lower storage requirement. Actually, Ek-NNclus and ECM are equally effective. However, EK-NNclus has an additional major strength which is its automatically determination of clusters number which converges automatically after a number of iterations.

DETD: The new proposed CBM method

The purpose of our proposed approach is to use a dynamic clustering technique, which fixes automatically the number of clusters for each case base, in order to select carefully cases that should be maintained. So, what types of cases should be retained in a case base? Actually, we define specially the two following types of cases as the same spirit as those defined in [START_REF] Smiti | WCOID-DG: An approach for case base maintenance based on Weighting, Clustering, Outliers, Internal Detection and DBSCAN-Gmeans[END_REF]:

-Isolated cases: They are far to clusters centers but not noises. Hence, they can only solve themselves and no other cases can solve them. For this reason, their deletion from the case base leads to the decrease of their competence in problem resolution. -Internal cases: Each internal case is a representative of a set of similar cases founded in the same cluster. Hence, deleting all similar cases do not affect the case base competence because they are close to each other. However, internal cases must be maintained to cover all of them.

On the opposite side, there are two other types of cases that should be removed, which are noisy and similar cases. In fact, noisy cases are irrelevant and distort the problem resolution process. Otherwise, similar cases are redundant and useless.

Our newly DETD approach aims to well distinguish between these types of cases while managing uncertainty and dynamicity of new occurred solutions over the time. To do that, we detail in what follows its different steps.

Step 1: DYNAMIC Evidential Clustering of cases

To partition the case base, this first step of our proposed CBM policy aims at using the clustering algorithm EK-NNclus (see Subsection 3.2) that response to a number of requirements and is characterized with the following properties:

-Property 1: Managing the uncertainty in cases' descriptions towards their membership to the different clusters as well as the total ignorance about them. -Property 2: Managing the dynamicity in case bases by fixing automatically the number of clusters through stored cases learning. This property is important to well detecting the different groups of similar cases each time we apply the CBM policy. -Property 3: Managing the scalability while handling uncertainty with a large number of clusters or distinct solutions in case bases.

In our context, EK-NNclus is performed on case bases as our first step in order to generate automatically and dynamically from them the different clusters reflecting cases solutions. Besides, it generates the degrees of belief towards the membership of cases to the different clusters as well as to the partition reflecting the total ignorance (the frame of discernment Θ). Indeed, the output offered by EK-NNclus will be exploited thereafter within case types detection steps.

Step 2: Isolated cases detection

To distinguish isolated cases from the whole case base, we have foremost to detect noisy cases in order to be eliminated since they seriously affect computations.

Noisy cases detection Actually, uncertainty management and the credal partition offered by EK-NNclus allow us to detect noisy cases, especially through the degrees of belief assigned to the frame of discernment reflecting the complete ignorance. Accordingly, cases having high degree of belief to be assigned to the total ignorance are flagged as noises [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential K-nearest neighbor rule[END_REF]. Thus, our idea is summed up by detecting noisy cases using the following way:

o i ∈ N oC if f m i (Θ) > Aj ⊂Θ m i (A j ) ( 13
)
where o i is a case instance and N oC represents the set of all the noisy cases.

Isolated cases detection As it was defined earlier, Isolated cases are situated on the borders of the generated clusters. Hence, we detect them as cases having a distance to the different clusters centers higher than a predefined threshold (do not considering cases that already flagged as noisy -N oC-), otherwise they are considered as similar since they are so close to each others. By this way, we follow these different points:

-The center of each cluster is calculated as the mean of cases attributes values in which they belong. The decision about the membership of cases to the different clusters is achieved using the pignistic probability (Equation 6). -The threshold for each cluster is fixed as the mean of distances toward its center with excluding cases flagged as noisy. -To manage uncertainty, also in distances calculation, we compute casesclusters distances using the Belief Mahalanobis Distance (BMD) as has been used in [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF].

Consequently, isolated cases are defined such that:

o i ∈ IsC if ∀ k, BM D(o i , v k ) > T hreshold k (14)
where IsC represents the set of isolated cases, o i is a case instance with o i / ∈ N oC, and v k presents the center of cluster k.

Step 3: Detecting Internal case for each generated cluster

Since an internal case presents a prototype of one cluster, we fix it as the nearest case to the center of each generated cluster. Hence, a case is flagged as internal if it has the shortest Belief Mahalanobis Distance (BMD) [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF] to one cluster's center. Accordingly, we define formally internal cases as follows:

o i ∈ InC if f ∃ k; o j / BM D(o j , v k ) < BM D(o i , v k ) ( 15
)
where o i and o j are two cases instances, v k is the center of cluster k, BM D presents the Belief Mahalanobis Distance [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF] between cases and clusters, and InC presents the set of all internal cases.

Step 4: Updating the case base

By arriving to this last step, we have already detected the types of cases that should be selected and maintained for preserving case bases competence in future problem resolution. Therefore, our proposed approach updates ultimately the case base by holding back isolated and internal cases, and removing all the others. By this way, DETD method can be efficient in case bases alleviation while preserving or rather improving their competence in problem resolution.

Experimental analysis

In this section, our aim is to evaluate the maintenance quality provided by our approach. Hence, we test it using a number of case bases from U.C.I repository of Machine Learning datasets. While developing, default parameters of EK-NNclus [START_REF] Denoeux | EK-NNclus: A clustering procedure based on the evidential K-nearest neighbor rule[END_REF] technique are taken. Thus, we propose to measure our maintaining method's effectiveness through three evaluation criteria as done in [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF], [START_REF] Smiti | COID: Maintaining case method based on Clustering, Outliers and Internal Detection[END_REF], [START_REF] Smiti | WCOID: Maintaining Case-Based Reasoning systems using Weighting, Clustering, Outliers and Internal cases Detection[END_REF] and [START_REF] Smiti | SCBM: Soft Case Base Maintenance method based on competence model[END_REF].

Then, we compare results with those provided by the Initial non-maintained case bases (ICBR) as well as the non-dynamic CBM approach called ECTD [START_REF] Ben Ayed | ECTD: Evidential clustering and case Types Detection for case base maintenance[END_REF].

Evaluation criteria -Storage size [S (%)]:

The percentage of the remaining case base's size after maintenance. Hence, it is the rate of case base size reduction, and defined as follows: S = N umber of cases af ter maintenance N umber of cases bef ore maintenance × 100

-Time [t (s)]: The time of problem resolution exerted on 1-Nearest-Neighbor algorithm. This criterion allows to measure the performance of CBR systems in term of retrieval time reduction. -Accuracy [PCC (%)]: The average percentage of correct classification criterion. It is applied using ten fold cross validation runned in front of 1-Nearest-Neighbor as a classification algorithm. Thus, it is defined such that:

P CC = W ell solved problems T otal solved problems × 100

Dynamic aspect

To evaluate the ability of our approach in handling the dynamic aspect of maintenance, we measure the accuracies dynamically. Drawing to the actual logic provided by CBR systems towards their case bases, we present dynamicity, in our work, through evolving case bases within three consecutive times such that:

-t 1 : We select randomly from the original case base a subset of cases (CB 1 ) with respecting the constraint of containing only two solutions (the minimal number that a case base can contain). -t 2 : We increment CB 1 ' size randomly with a probability to meet new solutions (without reaching the entire case base). -t 3 : We test on the totality of case bases with the totality of their solutions.

Results and discussion

According to the evaluation criteria and the dynamicity aspect defined above, we expose the different results in Tables 1, 2 and 3. Actually, in term of reduction size rate (Table 1), our DETD approach has been able to shrink more than half of all the initial tested case bases that contain the totality of cases (100%). For instance, it provides a reduction rate about 35% for "Iris" data set and 37% for "Ionosphere" data set. Obviously, this is the result of redundant and non relevant cases removing. On the other hand, DETD and ECTD approaches are offering very close reduction rates which vary from about 35% to 50% for both of them. For the retrieval time criterion, it is basically in relation with case bases density involving the storage size criterion. Actually, as shown in Table 2, the retrieval time is remarkably decreasing with the different case bases. For example, it moves on from 0.2825s with ICBR to 0.0062 with the DETD for the "Heberman" data set. Even comparing with ECTD approach, we are noting a slight decreasing of time provided for almost all the different tested case bases. Once our newly approach is able to reduce the case base along with the retrieval time and improves accordingly the CBR systems performance, we should now ascertain to their competence stability in problem resolution through the most important criterion called "Accuracy (PCC)". Actually, its results are shown in Table 3 within a dynamic way as defined in Subsection 5.2. For ECTD approach, we fix the number of clusters equal to the number of solutions appearing during t 1 (K = 2). Indeed, we note that our DETD approach is more able to preserve the competence of CBs, each time we maintain them. For instance, the accuracy provided by DETD while maintaining "Vehicle" data set is almost stable as it moves on from 74.43% (t 1 ) to 74.05% (t 2 ) until 73.55% (t 3 ). However, it is more and more decreasing after applying ECTD (from about 75% (t 1 until 65% (t 3 )). In fact, this is logically explained by the capacity of DETD to handle automatically the number of clusters whereas it is fixed for ECTD and not able to take into account this evolution. Furthermore, we note that DETD and ECTD are providing almost the same results for "Indian", "Ionosphere" and "Heberman" datasets. In fact, it is quite reasonable since they are binary, so the dynamicity in solutions is not really introduced for them. On the other hand, with considering the totality of case bases, we note that the maintained case bases with DETD offer precision even better than non-maintained ones (ICBR) such as for "Glass" data set where it reaches more than 25% of difference in t 2 .

Conclusion

In this paper, we proposed a new case base maintenance method called DETD approach where we focused on exceeding a limitation of some existing CBM policies related to the dynamicity in maintenance. While achieving its main purpose of case base maintenance, our DETD method was able to manage both of uncertainty in cases descriptions using belief function theory tools, and the aspect of dynamicity in CBR systems' case bases using a clustering method that offers a dynamic number of clusters each time we perform the maintenance. Hence, the main idea of our work is summed up by selecting as well as possible only the most relevant types of cases for preserving CBR systems competence and performance. This is actually done, also, through handling uncertainty regarding cases positions towards the different generated clusters. As future work, we aim to propose a dynamic CBM approach in term of real-time mode of maintenance.

Table 1 :

 1 Storage size (S%)

	Case bases	Storage size (S%) ICBR ECTD DETD
	1 Glass	100 % 50 % 46.1 %
	2 Indian	100 % 51.21 % 43.22 %
	3 Ionosphere 100 % 41.03 % 37.42 %
	4 Iris	100 % 38.67 % 35.33 %
	5 Vehicle	100 % 46.12 % 48.93 %
	6 Heberman 100 % 39.87 % 47.07 %

Table 2 :

 2 Retrieval time (s)

	Case bases	Retrieval time (s) ICBR ECTD DETD
	1 Glass	0.0091 0.0050 0.0045
	2 Indian	0.0125 0.0101 0.0083
	3 Ionosphere 0.0156 0.0077 0.0057
	4 Iris	0.0841 0.0068 0.0041
	5 Vehicle	0.0716 0.0063 0.0061
	6 Heberman 0.2825 0.0133 0.0062

Table 3 :

 3 Dynamic aspect influence in maintenance efficiency Glass 76.11 77.15 80.1 61.14 70.4 88.24 86.92 63.64 94.39 2 Indian 75.98 76.33 76.64 73.57 73.22 74.04 75.91 73.78 73.8 3 Ionosphere 78.45 91.03 88.04 82.76 69.71 86.38 86.89 87.5 87.5 4 Iris 100 99.18 98.54 98.75 96.3 99.02 98 92.21 98.28 5 Vehicle 75.12 74.56 74.43 71.89 68.15 74.05 72.34 65.21 73.55 6 Heberman 68.76 77.16 75.36 69.2 59.68 73.45 74.18 76.23 76.23

	Case Bases (CB)	Dynamic Accuracy Evaluation (PCC %) t2 t3 ICBR ECTD DETD ICBR ECTD DETD ICBR ECTD DETD t1
	1