Safa Ben

Ayed Larodec

Zied Elouedi
email: zied.elouedi@gmx.fr

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

ECTD: Evidential Clustering and case Types Detection for case base maintenance

Keywords: Case Based Reasoning (CBR), Case Base Maintenance (CBM), uncertainty, belief function theory, clustering, machine learning

The key factor for the success of Case Based Reasoning (CBR) systems is the quality of their case bases as well as the time spent in case retrieval process which is mainly depending on case bases' size. Indeed, the speed of the retrieval process is seriously decreasing when the case base becomes so heavy. To vouch for case bases' quality, a maintenance process must be provided. Hence, a field for Case Base Maintenance (CBM) emerges. However, a lot of works in CBM field suffers from some limitations and they generally reduce case base's competence during maintenance, especially when cases involving imprecise or uncertain information. To deal with these problems, we propose, in this paper, a new CBM approach named ECTD, Evidential Clustering and case Types Detection for case base maintenance, which is able to manage imperfection in cases by using belief function theory. The key idea of ECTD approach is to use machine learning technique, more accurately the evidential c-means (ECM). Then, it divides cases relative to the different partitions of clusters into four types so that we can subsequently perform the case base maintenance.

I. INTRODUCTION

The main objective of Artificial Intelligence (AI) is to conceive systems able to understand, emulate and reproduce human reasoning. Case Based Reasoning is a problem solving paradigm which is, similarly to human being, based on reusing past experiences to solve new problems by assuming that similar problems have similar solutions. Therefore, CBR presents a perfect sample of AI. In CBR systems, a problem is solved after following an entire cycle composed of four phases known by the 4RE [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]: REtrieve, REuse, REvise and REtain. First of all, the CBR system searches in its case base the case(s) having the most similar problem description to the target one by using a similarity measure. Then, it tries to adapt its solution in order to build a new one having the ability to solve the target problem. However, this solution can be inadequate, so it should be revised and validated. Finally, the new problem attached to its proposed solution will be stored in the case base as a new case. Like others, this case will serve for new problem resolution. This incremental evolution of case bases causes a great storage requirement, consequently, a very time consuming retrieval process which leads to the seriously decrease of case bases' performance.

Accordingly, we observe a strongly emergence of the Case Base Maintenance (CBM) field and a great awareness of it's importance towards the learning phase. Materially, it can be explained by the utility of CBR systems and their achieved success in several domains. Thus, CBM has been defined in [START_REF] Wilson | Maintaining case-based reasoners: Dimensions and directions[END_REF] as the process aiming to improve the performance of CBR systems: "Case-base maintenance implements policies for revising the organization or contents (representation, domain contents, accounting information, or implementation) of the case base in order to facilitate future reasoning for a particular set of performance objectives". In fact, we find in the literature several CBM policies aiming to maintain case bases for CBR systems. However, they generally suffer from some weaknesses. For instance, we cite the limitation of their complexity when dealing with large case bases or their disability to manage imperfection in knowledge whereas cases which refer to real world situations are full of uncertainty, which is related to the source of information, and imprecision, which is related to the information itself. To deal with the latter problem, there is a number of theories that can be used. One of the most appropriates theories is the belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] [START_REF] Shafer | A mathematical theory of evidence[END_REF] which presents a powerful tool and accounts for knowledge uncertainty in different levels from the complete ignorance to the total certainty. For these reasons, we propose, in this paper, a new Case Base Maintenance approach named ECTD, encoding "Evidential Clustering and case Types Detection for case base maintenance", able to deal with imperfection in cases descriptions and retain the most competent in problem solving by using belief function theory as well as machine learning techniques, more precisely Evidential c-means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF].

The remainder of this work is organized as follows. In section II, we expose a brief review of CBM policies in the literature. The necessary background related to the theory of belief functions is presented in section III where it provides on the one hand the basic notions of the theory and on the other hand an evidential clustering technique called Evidential c-means [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. Section IV details the different steps of our new proposed ECTD approach. Finally, experiments and results are given in section V.

II. CBM POLICIES: RELATED WORK

In the literature, there are several policies that deal with the case base maintenance and this can only indicate the significance of CBM field towards CBR systems success. Basically, the objective of CBM policies is to reduce the size of case bases in order to cut down the retrieval time. In short, we list some methods that have been made for maintaining case bases by classifying them into four strategies: Data reduction methods based on selection, Selective rule based strategy, Optimization strategy and Partition strategy.

A. Data reduction methods based on selection

The main objective of this class of CBM policies is to select from case bases only the representative cases where their set is able to cover all the rest of cases. For instance, the Condensed Nearest Neighbor approach (CNN) [START_REF] Hart | The condensed nearest neighbor rule (Corresp.)[END_REF] is a data reduction algorithm that selects iteratively case base's prototypes and adds them in a new case base. The idea behind CNN approach is to choose randomly a case from the original case base and test if the edited one can solve it or not. If not, this case will be selected to be added in the edited case base and removed from the original one. In the same road, we mention the Reduced Nearest Neighbor approach (RNN) [START_REF] Gates | The Reduced Nearest Neighbor Rule[END_REF] which is characterized by using the whole case base as an initial reduced set. Then, removing cases until no case from the original case base is misclassified by the remaining cases in the edited case base. Besides, we cite the Selective Nearest Neighbor approach (SNN) [START_REF] Ritter | An algorithm for a selective nearest neighbor decision rule[END_REF] which guarantees the retrieval of the minimal cases subset by improving the mix between CNN and RNN rules. The idea behind this approach is that all cases in the training set must be closer to a case in the selective set than any one in the training set.

B. Selective rule based strategy

Authors in [START_REF] Zhao | A rule based case maintenance method for the performance of CBR classifier[END_REF] proposed an approach for maintaining case bases based on selective rules in order to lead their reduction. This method is divided into two steps: First, applying a method for feature reduction since the CBR is sensitive to inaccurate data such as noises and redundant attributes that can seriously reduce case base's performance. Second, defining selective rules, and only cases satisfying these rules will be selected in order to achieve the dynamic maintenance of CBR systems. These proposed rules concern noisy and redundant cases that we generally aim to remove during case base maintenance.

C. Optimization strategy

Generally, CBM policies that are related to this strategy value cases according to some evaluation criteria which influence the decision making about their deletion or retention. Hence, we highlight some of the most known criteria for evaluating a case base in a CBR system. The first one is the performance of a case bases which is measured by the time spent from the arrival of the new problem until proposing its solution. The second one is the case base's competence which is known as the range of problems that this case base is able to solve. Typically, when we talk about competence criterion, two main concepts arise: the coverage and the reachability. The coverage of one case is the set of all the target problems that this case can successfully solves. However, the reachability of a target problem represents the set of cases that can be used to solve this problem [3] [4].

According to Smiti and Elouedi [START_REF] Smiti | Overview of Maintenance for Case based Reasoning Systems[END_REF], this strategy is divided into two main categories: Standard deletion methods and methods based on case's competence. For the first category, we cite Random Deletion policy (RD) where the principle is to delete cases randomly when a predefined size limitation is exceeded. Besides, we mention Utility Deletion policy (UD) which is based on Minton's utility [START_REF] Minton | Quantitative results concerning the utility of explanationbased learning[END_REF] serving on case performance estimation. Its idea is to delete all cases having a bad performance, consequently, a negative utility. Concerning the second category based on cases' competence and the two corresponding concepts coverage and reachability, we find as example RC-CNN approach which is an hybrid algorithm combining the CNN algorithm to Relative Coverage (RC) metric aiming to quantify competence contribution of cases [START_REF] Smiti | Overview of Maintenance for Case based Reasoning Systems[END_REF]. In the same way, Brighton and Mellish [START_REF] Brighton | On the consistency of information filters for lazy learning algorithms[END_REF] proposed an iterative approach based on the competence criterion for cases deletion called Iterative Case Filtering algorithm (ICF). Its principle is to delete cases having a coverage set size smaller than reachable set size i.e. a case will be deleted if more cases can solve it than it can solve itself.

D. Partition strategy

The greatest strength of CBM policies based on partition strategy is that they divide the original case base into a set of small ones where each one can be treated separately. Generally, these small case bases are created thanks to an unsupervised machine learning technique which is Clustering. This technique is suitable for such problem since a given case can be considered as an individual and the notion of distance between cases is well presented. Thus, we mention 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 aims to select from each cluster only cases influencing case base's quality. First, COID applies DBSCAN [START_REF] Sander | The algorithm GDBSCAN and its application[END_REF] as the density based clustering technique and benefits from its ability to detect noisy cases. Then, it detects internal cases as those having the smallest Euclidean distance to cluster's center. Finally, COID is supposed to detect outliers. Thence, it used Interquartile Rang (IQR) to detect univariate outliers and Mahalanobis distance for multivariate ones. In addition, we can mention some extentions from COID approach such as WCOID [START_REF] Smiti | WCOID: Maintaining Case-Based Reasoning systems using Weighting, Clustering, Outliers and Internal cases Detection[END_REF] which adds a feature weihghting step and WCOID-DG [START_REF] Smiti | WCOID-DG: An approach for case base maintenance based on Weighting, Clustering, Outliers, Internal Detection and Dbsan-Gmeans[END_REF] which combines WCOID with the Gaussian-means clustering technique in order to well estimate the number of clusters. Moreover, we cite examples of soft CBM policies that, to the best of our knowledge, are not numerous. To begin with, we mention simultaneously both of Fuzzy decision tree CBM policy [START_REF] Shiu | Maintaining Case-Based Reasoning Systems Using Fuzzy Decision Trees[END_REF] and Fuzzy-Rough CBM approach [START_REF] Cao | A Fuzzy-Rough Approach for Case Base Maintenance[END_REF] which share the first step consisting of feature weights learning, the second consisting of case base partitioning and the fourth step maintaining the case base by representative cases selection. Concerning the third step, authors in [START_REF] Shiu | Maintaining Case-Based Reasoning Systems Using Fuzzy Decision Trees[END_REF] opt for fuzzy adaptation rule mining, whereas in [START_REF] Cao | A Fuzzy-Rough Approach for Case Base Maintenance[END_REF] authors integrate rough and fuzzy sets theories in order to transfer the case knowledge to adaptation knowledge. For both, this step is the most important since it allows to find non-representative cases for each cluster. Last but not least, we cite the Soft CBM Competence Based Model (SCBM) [START_REF] Smiti | Maintaining Case Based Reasoning Systems Based on Soft Competence Model[END_REF] that uses foremost a soft clustering technique called Soft DBSCAN-GM (SDG) [START_REF] Smiti | Fuzzy density based clustering method: Soft DBSCAN-GM[END_REF] which is based on fuzzy set theory [START_REF] Zadeh | Fuzzy sets[END_REF]. In fact, the purpose of this first step is to create competence groups and facilitate the second one consisting of case types detection (Noisy, Isolated and Similar cases) after computing Fuzzy Mahalanobis Distances between cases and clusters.

E. Critics and discussion

Obviously, there is in the literature a lot of works aiming to maintain case bases for CBR systems as presented during the previous subsections, knowing that they have not been covered exhaustively. Actually, crisp CBM policies can be interesting but they suffer from a major limitation which is presented by their disability in managing imperfection in CBR case bases. Thus, they easily make confusion while making decision about cases deletion or retention since they are full of imperfection. On the other hand, methods managing uncertainty are quite interesting because they are more able to take into account real data related to imperfection. In fact, we already presented some methods that deal with this kind of knowledge such as [START_REF] Shiu | Maintaining Case-Based Reasoning Systems Using Fuzzy Decision Trees[END_REF], [START_REF] Cao | A Fuzzy-Rough Approach for Case Base Maintenance[END_REF] and [START_REF] Smiti | Maintaining Case Based Reasoning Systems Based on Soft Competence Model[END_REF]. However, formalisms used by these methods did not manage or cover all aspects of uncertainty. Therefore, The risk of removing representative cases persists. By this way, our proposal for this paper is to extend this axis by using a theory having the capacity to take into account the overall uncertainty. This theory is the Evidence theory as it will presented in the next section.

III. BACKGROUND RELATED TO EVIDENCE THEORY

In order to be familiar with our contribution in this paper, some background related to the Evidence theory or belief function theory are required. On the one hand, we give an overview on the basic notions and concepts of belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] [START_REF] Shafer | A mathematical theory of evidence[END_REF]. On the other hand, a clustering technique in an evidential frame called Evidential c-means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] will be presented.

A. Belief function theory

Belief function theory, also called Evidence theory or Dempster-Shafer theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] [START_REF] Shafer | A mathematical theory of evidence[END_REF], is a theoretical framework to model and quantify imperfect knowledge whether it is partial or unreliable. For reasoning under uncertainty, the belief function theory has interpreted differently using different models, inter alia Smets's Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF] as a non-probabilistic model.

Let us consider the frame of discernment Θ as a finite set of variables w which refers to K elementary events to a given problem (Θ = {w 1 , w 2 , ..., w K }). The power set of Θ is the set of all the 2 K possible subsets such that:

2 Θ = {∅, {w 1 }, {w 2 }, ..., {w K }, {w 1 , w 2 }, ..., Θ} (1)
The key point of Dempster-Shafer theory is the basic belief assignment (bba) which represents the partial knowledge about the value of w and defined as follows:

m : 2 Θ → [0, 1] A → m(A) (2)
where m satisfies the following constraint:

A⊆Θ m(A) = 1 (3)
An element A of Θ is called a focal element when m(A) > 0, and the set containing all these elements is called a body of evidence (BOE). When each element in BOE is a singleton, m is named a Bayesian bba. On the other hand, when BOE contains only Θ as a focal element, we are in the complete ignorance situation and m is called vacuous belief function. However, when it contains only one singleton of Θ as a focal element, m is presented as a Certain mass function.

A bba function is normalized when the mass given to the empty set is constrained to be zero (m(∅) = 0). In that case, it corresponds to the closed-world assumption [START_REF] Shafer | A mathematical theory of evidence[END_REF]. A contrary explanation is that the frame of discernment Θ can be incomplete and the value of w can be taken outer Θ. Accordingly, the mass of belief that is not linked to Θ can allowed to be strictly positive (m(∅) > 0). That case corresponds to the open world assumption [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF].

If we are faced to distinct pieces of evidence (e.g., m 1 and m 2 ), it is important, also, to show some ways in the literature of bba combination. The most popular combination rule which is proposed by [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] uses the conjunctive sum operation ∩ and defined as follows:

(m 1 ∩ m 2 )(A) = B∩C=A m 1 (B) m 2 (C) ∀A ⊆ Θ (4)
However, the normality constraint (m(∅) = 0) can be recovered by using Dempster's rule of combination where ⊕ represents the notation of its resulting operation such that:

(m 1 ⊕ m 2 )(A) = 1 1 -κ B∩C=A m 1 (B) m 2 (C) (5)
where κ = A∩B=∅ m 1 (A) m 2 (B) is commonly known as the combination global conflict. Ultimately, several solutions have been proposed in the frame of belief function theory in order to guarantee the decision making process. For instance, we cite the pignistic probability, denoted BetP , which is offered by Transferable Belief Model (TBM) and generally considered as a good way for decision making. If the mass function is normalized, then BetP is defined as follows:

BetP (w) = w∈A m(A) |A| ∀w ∈ Θ (6)
If the mass function is unnormalized (m(∅) > 0), then the pignistic transformation must be preceded by a normalization step.

B. Evidential c-means (ECM)

The Evidential c-means (ECM) algorithm is an evidential clustering technique proposed in [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], based essentially on Fuzzy c-means (FCM) algorithm [START_REF] Bezdek | FCM: The fuzzy c-means clustering algorithm[END_REF] and generalizes both of the hard k-means and FCM. The aim of this technique is to assign each object with degrees of belief to the different subsets of clusters from the frame of discernment. In ECM algorithm, like FCM, each cluster w k is presented by its center v k which is a vector defined in object attribute space. However, unlike FCM, one case can belong not only to a singleton cluster but also to a partition of clusters (A j ⊆ Θ) that can be called a meta-cluster and having a cardinality superior than one (|A j | > 1). Correspondingly, the metacluster A j is also represented by a prototype denoted v j and defined as follows:

v j = 1 |A j | K k=1 s kj v k ( 7
)
where K represents the number of clusters, s kj = 1 if w k ∈ A j and s kj = 0 otherwise. As almost of the clustering techniques, the purpose is to maximize the distances of objects belonging to different clusters and minimize those belonging to the same one. Hence, in the evidential framework, ECM applies the same principle by minimizing the following objective function for n objects and K clusters:

J ECM (M, V ) = n i=1 j/Aj =∅,Aj ⊆Θ |A j | α m β ij d 2 ij + n i=1 δ 2 m β i∅ (8) subject to j/Aj ⊆Θ,Aj =∅ m ij + m i∅ = 1 ∀i = 1...n (9)
where M represents the credal partition defined in R n×2 K space, V is the matrix of 2 K clusters centers having p features, m ij denotes m i (A j ) and d ij indicates the euclidean distance between the i th object and the j th partition's prototype. For α, it consists of controlling the degree of penalization for subsets with high cardinality. Finally, β and δ present two parameters for treating noisy objects.

In order to achieve this minimization, an alternation between two phases is applied. The first one consists of supposing that V is fixed and solving Equation 8 constrained by Equation 9 using the Lagrangian where the calculation details are presented in [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. Thus, the resulting optimum of M for every partition A j ⊆ Θ is defined as follows:

m ij = |A j | -α/(β-1) d -2/(β-1) ij A k =∅ |A k | -α/(β-1) d -2/(β-1) ik + δ -2/(β-1) (10)
and

m i∅ = 1 - Aj =∅ m ij ∀i = 1...n (11)
However, for the second phase, we consider M as fixed and an unconstrained minimization problem has to be solved (Equation 8). After the calculation sequence as shown in [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF], the resulting cluster centers matrix V comes from the resolution of the system HV = B, where B is a (K × p) matrix and H is a square (K × K) matrix as they are defined in [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. with the following definition:

B lq = n i=1 x iq Aj w l |A j | α-1 m β ij l = 1...K q = 1..p (12
) and H is a square (K × K) matrix having the following form:

H lk = i Aj ⊇{w k ,w l } |A j | α-2 m β ij k, l = 1...K (13)
IV. ECTD APPROACH Fundamentally, our purpose is to maintain case bases for CBR systems. Especially, we aim to reduce their case bases where uncertainty is handled in order to retain or rather improve as well as possible their competence and performance in problem resolution. To do that, we developed a case base maintenance policy named ECTD for Evidential Clustering and case Types Detection for case base maintenance. Our ECTD approach goes through three main steps as shown in Figure 1. First, it uses an evidential clustering technique in order to assign cases with a degree of belief to clusters or also to partitions of clusters since in the evidential frame clusters are overlapping. Consequently, the uncertainty regarding the membership of cases to the different clusters is well handled. Besides, a large case base can be treated in the form of a number of small ones. Second, and before applying the maintenance, ECTD proposes to partition cases into four types according to their states and positions towards the different clusters and according to their competence towards the entire case base. As presented in Figure 1, ECTD imposes to a case to be even Noisy, Similar, Isolated or Internal. Finally, the maintenance is achieved by removing cases associated to undesirable types which are Noisy and Similar. Hereafter, each step will be detailed independently in order to obtain at the end a general depict of our ECTD approach.

A. First step: Evidential Clustering

During this step, we are supposed to perform an evidential clustering which consists to use the belief function theory in order to handle uncertainty about cases assignment to clusters, where each case can belong to all clusters with a degree of belief. Actually, the evidential clustering of objects which are defined as cases in our frame, bestows a credal partition that allows a case to be assigned to multiple clusters, or rather multiple partitions of clusters which makes it more general than the other theories managing uncertainty. In this context, the evidential clustering technique used in order to generate the credal partition for our Case Base is the Evidential c-means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] such as it was presented in subsection III.B. By this way, ECM presents the first step of our ECTD approach for Case Base Maintenance.

In fact, the output generated by ECM after the convergence of the Equation 8will be exploited during the next step in order to distinguish between the different case types. This output is represented in the credal partition M as shown in Equations 10 and 11 which allow to handle uncertainty by offering the degrees of belief concerning the assignment of cases to the different subsets of clusters where these subsets or partitions are presented by their centers exposed in the matrix V that is also generated by ECM.

B. Second step: Case Types Detection

Drawing on the three case types presented in [START_REF] Smiti | Maintaining Case Based Reasoning Systems Based on Soft Competence Model[END_REF], we define our four types (Noisy, Similar, Isolated and Internal) to which we assign our own definitions. First of all, we are based on the two basic definitions of cases coverage and reachability [START_REF] Smyth | Remembering to forget[END_REF] to exhibit the two following definitions that will argue the different case types distinction and explain the adopted way for maintenance: Definition IV.1. A case x i is said reachable by the case base if there are a set of cases that are very close to it. Definition IV.2. Given a subset of cases which are very close to each others, each case of them can cover all the others. 1) Noisy cases detection: Remembering that our first step has been to apply the clustering technique "Evidential cmeans". Therefore, it generates for each case a degree of assignment to the different partitions of clusters. The idea here for handling Noisy cases is identical to that used in [START_REF] Dave | Characterization and detection of noise in clustering[END_REF] which consisting to allocate a cluster to which we assign noises. By this way, the empty set partition which corresponds to the "open world assumption" is the cluster that will deal in our context with cases representing a distortion of values and cannot be assigned to any one among the set of clusters. Therefore, ECTD considers that cases having a "High" degree of belief to be assigned to the empty set partition are flagged as Noisy. For ECTD approach, a degree of assignment is said "High" if and only if it is greater than the sum of all the other degrees of assignments to other partitions. In other words, a case is flagged as Noisy if there is more belief that this case does not belong to any cluster in the frame of discernment Θ than it does. Regardless of that, noisy objects are generally characterized by their remoteness and isolation to each objects gathering or clustering which argues and defends our assumption about Noisy cases definition. Therefore, ECTD defines Noisy cases as follows:

x i ∈ N C if f m i (∅) > Aj ⊆Θ,Aj =∅ m i (A j ) (14)
where x i is an instance of cases and N C represents the set of all the Noisy cases.

Since the total sum of beliefs towards cases assignment to the different partitions of clusters is constrained to be one (Equation 3), a Noisy case can likewise be defined as follows:

x i ∈ N C if f m i (∅) > 0.5 (15)
Fundamentally, this type of cases represents a burden regarding the entire case base. In fact, they cannot cover neither other cases nor themselves. Besides, they cannot be reachable by others i.e. no other case can solve them. Consequently, this type of cases are generally reducing the case base's competence.

2) Similar and Isolated cases detection: Once ECTD detects Noisy cases, it has now to distinguish between two types of cases from the remaining case base which are named Similar and Isolated. This distinction will be done after handling the different distances to clusters centers. Rationally, the clustering algorithm ECM as presented in subsection III.B makes that the most of cases are located in the centers of clusters. Therefore, the idea consists of measuring the different distances to different clusters prototypes presenting their centers. Hence, cases having a "Large" distance from centers are flagged as Isolated and those having a "Short" distances to one cluster's center is flagged as Similar towards this cluster. This description can be better clarified by Figure 1. However, the question herein is: "How handling distances between cases and clusters centers within an uncertain framework where we should take advantages of the credal partition of cases to all partitions of clusters and not only singleton clusters?" The idea of ECTD herein is to exploit as well as possible the cases assignments degrees to the different clusters that are already provided by ECM algorithm in form of bba functions. As mentioned, we are therefore in charge to calculate cases distances in order to distinguish between those which are situated in clusters' cores and those that are more distant while managing uncertainty. To do that, we adapted the Mahalanobis Distance [START_REF] Mahalanobis | Mahalanobis distance[END_REF] to the belief function theory by using the Belief Covariance Matrix [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF]. Hence, we called this distance as Belief Mahalanobis Distance (BMD). Conspicuously, this distance has many strengths such that:

• It is appropriate with non-uniform distributions and able to support arbitrary shapes of clusters, and not only spherical as it is the case with the Euclidean one. • It takes into account the covariance between variables during distances computing. • It manages so well the uncertainty regarding the membership of cases not only to many clusters but also to many partitions of clusters. Basically, this ability is present thanks to the Belief Covariance Matrix Σ which measures the cluster's covariance matrix in p-dimensional space by returning to all the partitions of clusters in which it belongs.

In fact, for a case base containing n instances of multivariate cases x i defined in p-dimensional space, the Belief Mahalanobis Distance (BMD) to a given cluster is defined as follows:

BM D(x i , v k ) = (x i -v k ) T Σ -1 k (x i -v k ) (16)
where v k is the center of the k th cluster generated during the first step by ECM algorithm whereas Σ k represents the Belief Covariance Matrix [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF] of the k th cluster and it has the following form:

Σ k = n i=1 Aj w k m 2 ij |A j | α-1 (x i -v j )(x i -v j ) T (17)
where A j is a partition of clusters (A j ⊆ Θ) with j = 1, .., 2 K , k is the cluster's number with k = 1, .., K, m ij and v j are respectively the credal partition and the prototypes as defined during the first step by ECM, and by fixing the value of the exponent α, |A j | α serves to penalize the belief's allocation to partitions with high cardinality. Remarkably, this belief covariance matrix [START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF] of the k th cluster exploits the partitions prototypes given during the first step by ECM as well as the credal partition of cases to all subsets containing the cluster k as a focal element in order to well estimate cases dispersion aroud this cluster's center. After calculating the distance matrix of n cases regarding K clusters, the aim now is to fix a threshold with which we will compare these distances in order to decide if it consists of Similar or Isolated cases. For this reason, we first exclude Noisy cases. Then, we compute the threshold of each cluster as the mean of distances towards the center of this cluster. Therefore, ECTD defines this threshold as follows:

T hreshold k = x i / ∈N C BM D(x i , v k ) #T otalCases -#N oisyCases (18)
In fact the intuition behind this proposal is that it indicates how much on average a case is close to the center of the distribution and to compare with it. Besides, we exclude Noisy cases because generally the mean as well as the standard deviation are so sensitive to noisy values. So it can affect seriously the results.

Finally, by taking only cases that have not been flagged as Noisy, we are now able to distinguish between Similar and Isolated cases by using the following form:

x i ∈ SC k if ∃k/BM D(x i , v k ) < T hreshold k IsC Otherwise (19
) where SC k represents the set of similar cases which are situated near to the core of cluster k ("Short" distance) and IsC is the set containing Isolated cases which are more distant ("Large" distance).

3) Internal cases detection: By attaining this phase, we are already flagged each case as one of the following three types: Noisy, Similar or Isolated. However, Similar cases regarding the same cluster are seen as redundant cases. So, we have to vote for only one case for each cluster in order to cover the others after their deletion from the case base. Consequently, our approach chooses to vote for the closest case to each cluster's center and re-flag it as an Internal case. Logically, we obtain finally a number of Internal cases equal to the number of the initial clusters K. Formally, we can define Internal cases such that:

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

C. Third step: Maintenance

The previous elaborated steps concerning the evidential clustering and the detection of the different case types aim at applying effectively the maintenance task. In general, maintenance of CBR systems and especially of case bases may appear in different forms such as removing or updating a number of cases. Indeed, ECTD is interested in cases elimination. Therefore, it consists foremost of deleting cases representing a distortion of values that can lead to the decrease of CBR systems' ability in problem solving. This first type corresponds to cases flagged as Noisy. The second type of cases that have to be removed is Similar since this kind of cases can be seen as redundant cases and can be covered by only one case that is already exposed as Internal. Hence, the main motivation for removing this type of cases is to alleviate the case base and to get a better response time surely without reducing its competence in problem solving. However, we should keeping Isolated cases because they are not reachable by other cases and they can only cover themselves. Besides, their deletion can lead to the risk that some problems can be permanently unsolvable by the case base. Moreover, Internal cases must be retained because they cover all the deleted cases that were situated near to the different clusters centers.

V. EXPERIMENTATION AND RESULTS

For the experimental investigation regarding our new ECTD approach, we developed it using Matlab R2015a and it is tested on six case bases from U.C.I Repository for machine learning data sets with considering only numeric data. These data sets description including their references, number of instances and number of attributes are shown in Table I. While developing, we fixed the initial number of clusters to the original number of classes given in U.C.I Repository and we considered the default parameters of ECM algorithm. Besides, we did not penalize the belief's allocation to partitions with high cardinality by fixing the exponent of penalization α to one. Taking in mind that the main purpose of our ECTD approach is to maintain case bases with preserving or even improving their performance and competence during problem resolution, we propose therefore to measure the ECTD efficiency according to the three following criteria and compare the results with the initial non-maintained case bases that we will call the Initial CBR (ICBR). To calculate the PCC value in our context and comparing between the accuracy of the initial case base and the case base after maintenance, we choose the 1-Nearest Neighbor (1-NN) as a classification algorithm. Then, we performed the method of 10-Fold Cross Validation. • Retrieval time [T(s)]: Since the performance of CBR systems is strongly linked to the time of problem resolution, we choose this criterion as an important one and we applied it around the algorithm 1-NN to measure the classification duration in seconds.

B. Results and discussion

In terms of reduction size, we observe from the results shown in Table II that our ECTD approach has been able to reduce more than half the size of almost all the tested case bases comparing to the initial case bases which contains the totally of cases instances. In fact, for all the tested case bases, ECTD keeps between about 35% and 50 % of cases instances comparing to the Initial CBR (ICBR) with 100%. However, it is still necessary to ascertain their competence towards problem solving after maintenance. Here, we are talking about the accuracy criterion. Similarly, we are faced to an amelioration for all the tested case bases in terms of problem solving or accuracy where the percentage of cases correctly classified by 1-NN is better than that offered by the initial CBR systems as it is shown in Table III. Actually, the accuracy values provided by ECTD are varying between 76.23% for "Heberman" data set and 98.28% for "Iris" data set. However, for ICBR, their values are varying between 74.18% and 98% for the same data sets. Rationally, this slightly accuracy amelioration has occurred thanks to the deletion of noisy cases which mostly affecting case bases competence. Finally, the reduction of the retrieval time values such that presented in Table IV is an expected results since the number of case bases have been reduced by deleting several cases instances. For example, the retrieval time with the data set "Phishing website" passes from about 3.5 seconds to 0.6 seconds since ECTD keeps only about 41% from the initial case base size.

VI. CONCLUSION

In this paper, we presented a new case base maintenance approach able to manage uncertainty in cases called ECTD. Our new method aims to maintain case bases for CBR systems by removing all the cases representing a burden for the case base. The idea is summed up by applying the ECM [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] as an evidential clustering technique on the case base and exploiting the generated bbas corresponding to the different partitions as well as possible in order to distinguish between four types of cases: Noisy, Similar, Isolated and Internal cases. Finally, the case base maintenance is achieved by deleting Noisy cases in order to ameliorate the case base's competence and Similar cases so as to alleviate the case base. As future work, experimentation can carried out using a case study.

Fig. 1 .

 1 Fig. 1. Steps of our ECTD approach


Amel Ennaceur
email: amelnaceur@yahoo.fr

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefevre
email: eric.lefevre@univ-artois.fr

Qualitative AHP Method Based on Multiple Criteria Levels Under Group of Experts

In this paper, we consider a multi-criteria group decision making problem. We propose a novel version of the Analytic Hierarchy Process under the belief function theory. The presented approach uses groups of experts to express their assessments regarding the evaluation criteria and the evaluation alternatives. It considers also more complex multi-criteria decision problems that have multiple criteria levels. The presented method is illustrated with some examples.

Introduction

The multi-criteria decision-making (MCDM) can be defined as a field which refers to making decisions in the presence of multiple and conflicting criteria [START_REF] Zeleny | Multiple Criteria Decision Making[END_REF]. In this research, we focus on one of the most popular MCDM approach, namely the Analytic Hierarchy Process (AHP) [START_REF] Saaty | The Analytic Hierarchy Process[END_REF]. Within the AHP context, many extensions were introduced [START_REF] Utkin | The DS/AHP method under partial information about criteria and alternatives by several levels of criteria[END_REF]. Their main objective is to handle uncertainty under the expert assessments [START_REF] Holder | Some comments on Saaty's AHP[END_REF]. For instance, in some cases, decision maker is unable to express his judgements using crisp numbers and to provide a complete pair-wise comparison procedure. Qualitative AHP is then one of the very useful tools to tackle this drawback [START_REF] Ennaceur | Multi-criteria decision making method with belief preference relations[END_REF].

Even though selecting single expert-based alternatives according to conflicting criteria has received significant attention [START_REF] Zeleny | Multiple Criteria Decision Making[END_REF], handling such problems with group of experts and based on multiple criteria levels is still an open subject. Consequently, many extensions, under the belief function framework, have been introduced [START_REF] Beynon | A method of aggregation in DS/AHP for group decision-making with the non-equivalent importance of individuals in the group[END_REF][START_REF] Utkin | The DS/AHP method under partial information about criteria and alternatives by several levels of criteria[END_REF]. Regarding these methods, the expert may be unable to provide quantitative numbers to describe his opinions. For that reason, we propose to extend the Qualitative AHP into a group decision making context based on multiple criteria levels. In this work, we present additional usefulness of Ennaceur et al.'s method [START_REF] Ennaceur | Multi-criteria decision making method with belief preference relations[END_REF] for handling more complex MCDM problems. In fact, the Qualitative AHP method combines the standard AHP and the belief function theory to adequately model uncertain human judgments and to represent the expert assessment easily. However, in many decision problems, the expert is able to decompose the problem into: goal, criteria, sub-criteria and alternatives. Therefore, an improved version of the Qualitative AHP is proposed to take into account the fact that many multi-criteria problems might be modeled under multiple criteria levels. Moreover, this new approach is extended into a group decision making environment.

The rest of the paper is organized as follows: In Section 2, we introduce the belief function theory. Next, Section 3 describes the Qualitative AHP method. In Section 4 and 5, we detail an improved version of our Qualitative AHP under multiple criteria levels and based on a group decision-maker context. Section 6 concludes this paper.

Belief function theory

For brevity, we will not consider in detail what this model is. The interested reader should refer to [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. We present the basic concepts as interpreted by the Transferable Belief Model (TBM). Let Θ be a finite set of elementary hypotheses, called a frame of discernment. Let 2 Θ be all the subsets of Θ [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The basic belief assignment (bba) is a function m, that represents the portion of belief committed exactly to the event A. The belief function theory offers many interesting tools. The discounting technique allows to take in consideration the reliability of the information source that generates the bba m [START_REF] Smets | Transferable Belief Model for expert judgments and reliability problems[END_REF]. Also, to combine beliefs induced by distinct pieces of evidence, we can use the conjunctive rule of combination [START_REF] Smets | The combination of evidence in the Transferable Belief Model[END_REF]. Moreover, It is necessary when making a decision, to select the most likely hypothesis. One of the most used solutions within the belief function theory is the pignistic probability. More details can be found in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF].

AHP method with belief preference relations

In this section, we consider a revised version of the AHP model, namely Qualitative AHP. To describe the approach, we present its different steps:

Step 1: Model the problem as a hierarchy based on three levels. At the highest level, we find the main objective. Then, in the middle, the sets of criteria Ω = {c 1 , . . . , c n } for evaluating the sets of alternatives Θ = {a 1 , ..., a m }, which will be in the lowest level. Then, we define the subsets of criteria and alternatives. As presented in [START_REF] Ennaceur | Multi-criteria decision making method with belief preference relations[END_REF], we put together criteria (or alternatives) that have the same degree of preference.

Step 2: Establish priorities among the elements of the hierarchy. Each element is paired and compared. In this context, Ennaceur et al. model [START_REF] Ennaceur | Modeling qualitative assessments under the belief function framework[END_REF] is used to transform preferences relations into constraints of an optimization problem. Its resolution, according to an uncertainty measure (UM) [START_REF] Pal | Uncertainty measures for evidential reasoning I: A review[END_REF] generates the most uncertain belief functions. For instance, we consider the criterion based on pair-wise comparison matrix, we get:

Max H(m Ω ) = m Ω (C 1 ) * log 2 (|C 1 |/m Ω (C 1 )) + m Ω (C 2 )log 2 (|C 2 |/m Ω (C 2 )) +... + m Ω (C n ) * log 2 (|C n |/m Ω (C n )) + m Ω (Ω) * log 2 (|Ω|/m Ω (Ω)); s.t. bel Ω (C i ) -bel Ω (C j ) ≥ γ ∀(C i , C j ), C i C j bel Ω (C i ) -bel Ω (C j ) ≤ γ ∀(C i , C j ), C i C j bel Ω (C i ) -bel Ω (C j ) ≥ ε ∀(C i , C j ), C i C j bel Ω (C i ) -bel Ω (C j ) ≥ -ε ∀(C i , C j ), C i ∼ C j bel Ω (C i ) -bel Ω (C j ) ≤ ε ∀(C i , C j ), C i ∼ C j Ci∈F (m Ω ) m Ω (C i ) = 1, m Ω (A) ≥ 0, ∀A ⊆ Ω; m Ω (∅) = 0
where H is the uncertainty measure. The preference relation is represented by the first constraint. Next, the weak preference relation is illustrated by the second and third constraints. The indifference relation corresponds to the fourth and fifth constraints. The expert has to specify the indifference threshold ε and the preference threshold γ as two constants.

Step 3: Assume that criteria weights and alternatives scores are described by a bba defined on the possible responses. Thus, m Ω denotes the criterion bba and m Θ c k denotes the alternative bba, according to c k .

Step 4: Use the pignistic probabilities. At the level of criteria, the bba m Ω is transformed into pignistic probabilities as follows :

BetP Ω (c i ) = Cj ⊆Ω |c i ∩ C j | |C j | m Ω (C j ) (1 -m Ω (∅)) , ∀c i ∈ Ω (1)
Step 5: Consider each pignistic probability (BetP Ω (c i )) as a measure of reliability. For each specific criterion c i , β i is its corresponding measure of reliability. For each i, k = 1, . . . , n:

β i = BetP Ω (c i ) max k BetP Ω (c k ) (2)
Step 6: Synthesize the overall judgment. We have to update the alternatives priorities with their corresponding criteria weight. The obtained bba's are discounted such as:

α m Θ c k (A j ) = β k .m Θ c k (A j ), ∀A j ⊂ Θ (3) α m Θ c k (Θ) = (1 -β k ) + β k .m Θ c k (Θ) (4)
Step 7: Combine the overall bba's to get a single representation by using the conjunctive rule (m Θ = ∩ α m Θ c k ) and choose the best alternatives by computing its pignistic probabilities.

Example Let us consider a problem of buying a car. This case study involves four criteria: Ω = {Style (c 1 ), Price (c 2 ), Fuel (c 3 ), Reliability (c 4 )} and three selected alternatives: Θ = {Peugeot (p), Renault (r), Ford (f )}. The expert has identified three subsets of criteria: {c 1 }, {c 4 } and {c 2 , c 3 }. Along with the qualitative pair-wise comparison, the preference relations defined in Table 1 was obtained. After deriving the criteria weight, the corresponding bba is transformed into pignistic probabilities as presented in Table 1. At the level of alternatives, the same steps is repeated. We move now to the next stage to calculate the reliability measure. We obtain β {c1} = 1, β {c4} = 0.96, β {c3} = 0.6 and beta {c2} = 0.6.

Next, we need to update the alternatives priorities by the criteria weight. The discounted bba's are defined in Table 2.

Table 2. The discounted bba's

α 1 m Θ c 1 (.) α 4 m Θ c 4 (.) α 3 m Θ c 3 (.) α 2 m Θ c 2 (.) {p} 0.505 {p} 0.306 {r} 0.303 {f } 0.303 {p, r, f } 0.495 {r, f } 0.514 {p, r, f } 0.697 {p, r, f } 0.697 {p, r, f } 0.180
The next step is to combine the overall evidences and the alternative ranking is, finally, obtained according to the pignistic transformation. We obtain BetP Θ (p) = 0.410, BetP Θ (r) = 0.295 and BetP Θ (f ) = 0.295.

Qualitative AHP method under multiple criteria levels

At this stage, our main aim is to propose an extension of Qualitative AHP model under multiple levels of criteria. The originality of this work is to introduce a new hierarchy level, namely sub-criteria, in order to handle more complex multicriteria problem. Let us consider a case when there are two criteria levels. Our MCDM problem is defined as follows: Θ = {a 1 , . . . , a m } represents the set of alternatives, Ω = {c 1 , . . . , c n } is a set of criteria. For each criterion, we have Ω l , the set of k l sub-criteria (denoted by sc l j with j = 1, . . . , k l ) corresponding to the criterion c l . For example, the second criterion c 2 has three sub-criteria denoted by sc 2 1 , sc 2 2 and sc 2 3 . We start by computing their relative scores. At each hierarchy level,the expert has to assess the relative importance of each criterion regarding the main objective. His evaluations have to be modeled using preference relations in order to convert them into an optimization problem. A basic belief assignment is computed. The resulting basic belief mass, denoted by m Ω (C j ) (where C j is a single or a group of criteria), has to satisfy the following relation:

Cj ⊆Ω m Ω (C j ) = 1.
The same process is repeated at the sub-criterion level to get the local priorities. Suppose that the j-th criterion is selected by the expert to evaluate its corresponding sub-criteria. The relative bba should satisfy: SC j i ⊆Ωj m Ωj (SC j i ) = 1. where i = 1, . . . , k j with k j is the number of sub-criterion according to the j-th criterion and j = 1, . . . , n.

We move to the alternative level to get m Θ (A k ) (which represents the belief about the subset of alternatives A k regarding each sub-criterion). Now, we calculate the result and synthesize the solution by aggregating all the obtained bba's. Therefore, we must start by computing the global priority of each sub-criterion. Since we know how much the priority of each sub-criterion contributes to the priority of its parent, we can now calculate their global priorities. That will show us the priority of each sub-criterion regarding the goal.

As with Qualitative AHP method, we start by the criterion level. We transform m Ω to its relative pignistic probabilities BetP Ω , since our beliefs are defined on groups of criteria. The same technique is repeated on the sub-criterion level to get the pignistic probabilities. We convert m Ωj into BetP Ωj .

For each sub-criterion, we can now compute its global priority by: GP (sc j i ) = BetP Ω (c j ) * BetP Ωj (sc j i ). Then, to compute the alternatives ranking, we must apply the Qualitative AHP model from step 5 in Section 3, to compute the reliability measures, to update the alternatives priorities and to combine the overall bba's to select the highest alternatives.

Example Let us continue with the same problem. We consider that the criterion c 1 has two sub-criteria sc 1 1 and sc 1 2 . The necessary calculations have already been presented in the previous example. We obtain the following local priorities presented in Table 3. After computing the corresponding BetP Ω1 , we can deduce the global priority as defined in Table 3. In this case, one more step need to be made. In fact, our aim here is to quantify the priority of each criterion regarding the main objective. The global priorities throughout the hierarchy will add up to 1 (see Table 3).

Belief AHP method under multiple criteria levels based on group of experts

In many complex problems, collective decisions are made based on a group of expert. Accordingly, we propose to extend the Qualitative AHP under a group decision-making environment. The objective is then to aggregate evidence from a member of group, to select the most appropriate alternative.

Step 1: Expert weights The main aim of this step is to give weights to experts to quantify their importance. In this case, pair-wise comparison is suggested to generate their importances. We consider the experts as the set of alternatives that are compared regarding the reliability criterion. As presented previously, the belief pair-wise comparison generates a bba, that represents the part of belief committed exactly to each expert. This bba is transformed into a reliability measure, denoted by β i corresponding to expert i.

Step 2: Expert elicitation Each expert starts by identifying all the focal elements. Then, he compares all the identified elements through binary relations. The next step is to transform the obtained assessments into an optimization problem and to generate the least informative bba. A bba (m i ) is generated corresponding to each expert i.

Step 3: Aggregation process We proceed to the aggregation of the obtained bba's. First, we start by the discounting technique. Indeed, the idea is to measure most heavily the bba evaluated according to the most importance expert and conversely for the less important ones. So, each obtained bba is discounted by its corresponding measure of reliability, as follows:

P i (A) = m i (A) * β i , ∀A ⊆ Θ (5)
P i (Θ) = (1 -β i ) + β i .m i (Θ) (6)
where i = 1, . . . , η with η is the number of experts. Then, we move to compute the final decision. An intuitive definition of the strategy to fuse these bba's will be through the conjunctive rule of combination and the ranking of alternatives is obtained using the pignistic probabilities.

Example Let us consider the previous problem with four decision makers. The first step is to assign a degree of importance to each expert. We have β 1 = 1, β 2 = 0.9, β 3 = 0.2 and β 4 = 0.1. After applying the Qualitative AHP method, we obtain Table 4. Next, each bba corresponding to each expert is discounted according to its measure of reliability. Then, we combine the different bba's in order to generate the collective decision. Now, we analyze the different results. At this step, we propose to combine the obtained priority except one, in order to study the influence of the decision made by this expert on the decision of the group. This process is repeated for all the expert priorities. The aim of the process is to identify experts who provide preferences that are significantly different from the group, and to provide these experts with the opportunity to update these preferences to be closer to the majority. The main objective is to show that the best alternative is supported by the majority of expert and there is not a contradictory alternative. We can notice that experts 1 and 2 are considered as reliable sources of information, since they have almost the highest reliability measure. However, experts 3 and 4 are treated as not fully reliable. As we can see, we have the P 1 and P 2 support the same alternative and they consider that the best one is p and the worst is f . However, P 3 and P 4 present a contradictory information.

Consequently, we can notice that by combining the preferences of experts 1, 2 and 3 or experts 1, 2 and 4, have generated almost the same ranking of alternatives (see Table 5). We find that the most preferred alternative is p even if experts 3 and 4 prefer the alternatives r and f respectively. This is because experts 3 and 4 are not considered reliable. Besides, as shown in Table 5, when combining evidences P 1 ∩ P 3 ∩ P 4 or P 2 ∩ P 3 ∩ P 4 , we know that experts 3 and 4 are not fully reliable. Therefore, we can consider only the preference induced from expert 1 and 2 respectively. So, we can conclude that the most preferred alternative is p.

Conclusion

In this paper, we have formulated qualitative AHP method in an environment characterized by imperfection. Our approach deals with qualitative reasoning to model the uncertainty related to experts assessment. The advantage of this newly proposed model is its ability to handle multi-criteria level problem. It is also able to manage more complex problem by solving a multi-criteria group decision making problem. A future research idea is to study the effect of changing the weight of the groups of experts by a sensitivity analysis. In fact, the idea of assigning importance to a group of expert has been investigated, with arguments given as to the need for and against its utilization.

  We obtain: m global ({p}) = 0.070, m global ({r}) = 0.042, m global ({f }) = 0.032, m global ({f, r}) = 0.032, m global ({p, r}) = 0.002, m global (∅) = 0.815 and m global (Θ) = 0.009. The obtained ranking is illustrated as follows: BetP global (p) = 0.395, BetP global (r) = 0.334 and BetP global (f ) = 0.271.

Table 1 .

 1 Preference relations matrix

	Criteria {c1} {c4} {c2, c3}	Subsets of criteria {c1} {c4} {c2, c3} Ω
	{c1}	-			m Ω	0.228 0.218 0.208 0.346
	{c4}	-	-		Criteria	{c1} {c4} {c3} {c2}
	{c2, c3} -	-	-	BetP Ω	0.315 0.305 0.190 0.190

Table 3 .

 3 The local priorities assigned to the criteria and sub-criteria

	Criteria BetP Ω Sub-criteria BetP Ω 1 GP
	c1	0.315	sc 1 1	0.310 0.098
			sc 1 2	0.690 0.217
	c4	0.305		0.305
	c2	0.190		0.190
	c3	0.190		0.190

Table 4 .

 4 The final result using the Qualitative AHP approach regarding each decision maker Alternatives {p} {r} {f } {p, r} {p, f } {r, f } ∅

	Θ

Table 5 .

 5 The final result using the Qualitative AHP approachAlternatives P1 ∩ P2 ∩ P3 BetPP 1 ∩ P 2 ∩ P 3 P1 ∩ P2 ∩ P4 BetP P 1 ∩ P 2 ∩ P 4 P3 ∩ P4 BetPP 1 ∩ P 3 ∩ P 4 P2 ∩ P3 ∩ P4 BetPP 2 ∩ P 3 ∩ P 4

	∅	0.799		0.790
	{p}	0.076	0.400	0.079	0.392
	{r}	0.046	0.334	0.045	0.324
	{f }	0.034	0.266	0.038	0.284
	{f, r}	0.033		0.037
	{p, r}	0.002		0.002
	Θ	0.010		0.009
	Alternatives P1 ∩ ∅ 0.590		0.468
	{p}	0.155	0.406	0.117	0.377
	{r}	0.067	0.307	0.059	0.334
	{f }	0.059	0.287	0.067	0.289
	{f, r}	0.094		0.062
	{p, r}	0.001		0.069
	Θ	0.034		0.158


Sabrine Mallek
email: sabrinemallek@yahoo.fr

Imen Boukhris
email: imen.boukhris@hotmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

Eric Lefevre
email: eric.lefevre@univ-artois.fr

Evidential k-NN for Link Prediction

Keywords: Link prediction, social network, belief function theory, information fusion, evidential k-nearest neighbor, supervised learning

come

Introduction

Link prediction (LP) is an important task in social network analysis and graph mining that plays a major role in the understanding of network evolution. It is a powerful tool with a wide variety of applications such as prediction of protein-protein interactions in bioinformatics [START_REF] Airoldi | Mixed membership stochastic block models for relational data with application to protein-protein interactions[END_REF], construction of recommendation systems for e-commerce [START_REF] Huang | Link prediction approach to collaborative filtering[END_REF], detection of criminals or terrorist cells for security applications [START_REF] Rhodes | Inferring missing links in partially observed social networks[END_REF] or users aid to form new connections in social networks [START_REF] Liben-Nowell | The link prediction problem for social networks[END_REF]. The main goal is to accurately predict the existence of new links between unlinked entities given a state of the network.

Supervised machine learning techniques have been intensively applied to LP. Many classification models successfully addressed link prediction [START_REF] Cukierski | Graph-based features for supervised link prediction[END_REF][START_REF] Hasan | Link prediction using supervised learning[END_REF] (for details, see [START_REF] Hasan | A survey of link prediction in social networks[END_REF]). Indeed, LP can be easily transformed into a two-class classification problem. Given a social network graph G(V, E) where V is the set nodes and E is the set of edges, one can partition the graph into two states by considering the edges that occurred at the time interval [t 0 , t 1 ] as the training set and those belonging to the time interval [t 1 , t 2 ] as the test set. To this end, LP is reformulated into a binary classification problem by assigning class labels to all pairs of nodes such that:

class(u, v|G) = 1 if uv ∈ E 0 if uv / ∈ E
The most straightforward perception for LP is that similar nodes are likely to connect. That is, the challenge is how to evaluate this similarity accurately. From this point of view, we propose, in this paper, a framework that extends the k nearest neighbor (k-NN) classification approach to LP. We draw on the assumption that query links that are similar to links present in the network are likely to exist. Yet, the challenge is to evaluate the degree of support regarding the class membership of the new links. Actually, information given by the nearest neighbors cannot be considered completely trustworthy as a result of uncertainty and imperfection in the data. As pointed out in [START_REF] Adar | Managing uncertainty in social networks[END_REF], realworld networks especially, the large scale ones, are characterized by shifting degrees of uncertainty. Besides, data from real world applications are inherently uncertain, they are frequently incomplete, noisy and sensitive to observation errors. In order to overcome data imperfection issues, k-NN extensions under uncertainty theories have been proposed. For example, fuzzy k-NN algorithm [START_REF] Keller | A fuzzy k-nearest neighbor algorithm[END_REF] is an extension of k-NN based on fuzzy set theory [START_REF] Zadeh | Fuzzy sets[END_REF]. It applies a fuzzy editing that alters the membership of each training sample according to its k nearest neighbors. However, it does not allow to model and deal with imprecise or incomplete information effectively. Another example would be the evidential k-NN (EKNN) [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] based on the belief function theory (BFT) [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], a formal framework for reasoning under uncertainty that permits to manage and model imprecise information accurately.

Obviously, dealing with uncertainty is relatively correlated to the definition of fusion. It is important to determine the properties of objects and the relations among multiple ones. Yet, one has to quantify the uncertainty regarding certain characteristics of an object and the likelihood with which we can say that some elements are related. The BFT allows to carry out such fusion procedures. Furthermore, it enables to pool evidence while being cautious to the sources' reliability. The usage of the BFT to handle uncertainty in networks has been strongly recommended in the literature [START_REF]Constructing and Analyzing Uncertain Social Networks from Unstructured Textual Data[END_REF][START_REF] Dahlin | A method for community detection in uncertain networks[END_REF][START_REF] Svenson | Social network analysis of uncertain networks[END_REF]. In that regard, we extend, in this paper, evidential k-NN proposed by [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] under the belief function framework [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] to address link prediction. The proposed framework combines topological properties and the intuition of the nearest neighbors approach. The similarity is evaluated using structural metrics as features. Each nearest neighbor is considered as a distinct item of evidence supporting the class membership of the query link. Finally, the overall evidence given by the k-nearest neighbors is fused using the belief function theory combination tools. This paper is organized as follows: in the next two sections, we recall related work on link prediction and a brief background on the belief function theory. In Section 4, our proposals for LP based on supervised learning under the belief function theory framework are presented. In Section 5, we report the conducted experiments to test the novel framework. Lastly, conclusions and possible future work are drawn in Section 6.

Related Work on Link Prediction

According to [START_REF] Lu | Link prediction in complex networks: A survey[END_REF], LP approaches can be roughly classified into three groups: probabilistic models, maximum likelihood algorithms and similarity based methods [START_REF] Hasan | A survey of link prediction in social networks[END_REF]. The probabilistic models estimate the likelihood of links existence by building a joint probability distribution representing the graph and applying inference techniques. They are generally based on Markov Networks or Bayesian Networks [START_REF] Getoor | Introduction to statistical relational learning[END_REF]. On the other hand, maximum likelihood approaches concentrate on a given structure across the network (i.e. hierarchical structure, community structure, etc.) and try to fit the most likely structure through maximum likelihood algorithms. Finally, similarity-based algorithms compute similarity scores between the nodes based on some topological properties of the graph. These scores can be easily employed under a supervised learning. They are generic as they do not depend on the network domain and do not require an overall model. Additionally, each similarity score is independent from the others which allows to compute several ones separately and at the same time. They are the simplest of LP algorithms in terms of computational cost. Actually, LP applies to networks which are continuously evolving in size. In many cases, maximum likelihood and probabilistic models cannot even be checked due the large structure of the networks. On that point, similarity-based methods are more convenient since they do not only perform to large graphs but their performance is also impressive. We presented, in previous works [START_REF] Mallek | Evidential link prediction based on group information[END_REF][START_REF] Mallek | The link prediction problem under a belief function framework[END_REF][START_REF] Mallek | An evidential method for multi-relational link prediction in uncertain social networks[END_REF][START_REF] Mallek | Evidential missing link prediction in uncertain social networks[END_REF], LP approaches inspired from similarity-based methods. However, the latter works are applicable to uncertain social networks i.e., edges are attached by uncertainty degrees regarding their existence. They operate merely using the BFT tools. Our proposed framework, in this paper, tackles LP under supervised learning. Furthermore, it applies to social networks without encapsulated uncertainty in their structure.

The similarity-based methods use topological information of the networks. This information is usually grouped into two types: local and global information. The first group of methods computes scores according to node-neighborhoods. An example would be the common neighbors of two nodes [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF]. The intuition is that the more two nodes u and v share many common neighbors the more likely they tend to connect. This makes sense in many real world networks such as friendship networks, as two persons who have many mutual friends are very likely to become friends. In contrast, global information methods employ proximity in the network where two nodes are likely to connect if they are close in the network in distance terms. An example of such algorithms would be the shortest path between two nodes. Yet, these algorithms have higher computational complexity since they require all the topological information which is frequently not completely available. In this paper, we consider the node neighborhood based metrics as they are simple and not costly in computational terms.

For a node u, let τ (u) be the set if its neighbors in the network, called first level neighbors or direct neighbors. The second level neighbors of u, denoted τ (u) 2 , are the nodes connected to the direct neighbors of u. We recall here the most popular local similarity scores that proved their efficiency in many works from literature [START_REF] Liben-Nowell | The link prediction problem for social networks[END_REF][START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF][START_REF] Zhou | Predicting missing links via local information[END_REF]:

-Common Neighbors (CN) [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF] computes the common neighbors between a pair of nodes (u, v). -Jaccard Coefficient (JC) [START_REF] Jaccard | Étude comparative de la distribution florale dans une portion des Alpes et des Jura[END_REF] measures the ratio of the common neighbors of u and v and all their neighbors.

-Adamic Adar measure (AA) [START_REF] Adamic | Friends and neighbors on the web[END_REF] weights all common neighbors of the pair (u, v) and penalizes the ones with high degrees. -Resource Allocation (RA) [START_REF] Zhou | Predicting missing links via local information[END_REF] is inspired from the resource allocation process of networks. For an unlinked pair of nodes (u, v), each common neighbor plays the role of a transmitter of a single resource unit. As such, the similarity between u and v is the amount of resource v collected from u. -Preferential Attachment (PA) [START_REF] Newman | Clustering and preferential attachment in growing networks[END_REF] assumes that the probability that a new edge relate to u is proportional to |τ (u)|. Thus, the score of uv is correlated to the number of neighbors of u and v.

Equations of the presented metrics are given in Table 1.

Table 1. Structural similarity measures based on local topological information between the pair of nodes (u, v) where τ (u) and τ (v) are respectively their sets of neighbors in the graph.

Common Neighbors (CN)

|τ (u) ∩ τ (v)| Adamic Adar (AA) z∈(τ (u)∩τ (v)) 1 log|τ (z)| Jaccard Coefficient (JC) |τ (u)∩τ (v)| |τ (u)∪τ (v)| Resource Allocation (RA) z∈(τ (u)∩τ (v)) 1 |τ (z)| Preferential Attachment (PA) |τ (u)| • |τ (v)|
In this paper, local topological metrics are combined with EKNN to evaluate similarities for LP. A feature set is constructed using structural metrics to determine the nearest neighbors according to a distance measure. The assets of the belief function theory for information fusion are subsequently exploited to pool the information gathered from the nearest neighbors. We present, in the next section, some fundamental basic concepts of the BFT.

Background on the Belief Function Theory

In the belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], a problem is represented by a frame of discernment Ω = {ω 1 , ω 2 , . . . , ω n }, an exhaustive and finite set of mutually exclusive events. A basic belief assignment (bba), denoted by m, represents the knowledge committed to the elements of 2 Ω given a source of information. It is a mapping function m : 2 Ω → [0, 1], such that:

A⊆Ω m(A) = 1 (1)
An element A is called a focal element of the bba m if m(A) > 0. The belief committed to Ω represents the degree of ignorance. A state of total ignorance is defined by m(Ω) = 1. When the bba has at most one focal element A different from Ω, it said to be a simple support function (ssf ) and has the following form [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF]:

m(A) = 1 -ω m(Ω) = ω (2)
for some A ⊂ Ω and ω ∈ [0, 1].

Combining two basic assignments induced from two distinct sources of information over the same frame of discernment into one may be ensured using the conjunctive rule of combination denoted by ∩ . It is defined as [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF]:

m 1 ∩ m 2 (A) = B,C⊆Ω:B∩C=A m 1 (B) • m 2 (C) (3)
The combination rule permits to aggregate evidence by meaningfully outlining a corpus of data and making it simpler. Furthermore, it allows to fuse information induced from single and multiple sources.

Evidential k-nearest neighbors for Link Prediction

The goal is to predict the existence of new links in a network graph G(V, E) where V is the set of nodes and E is the set of edges. The set of classes is Ω = {E, ¬E}, where E points up the existence of a link in G and ¬E its absence. The class of each link in E is assumed to be known with certainty. The available information consists in a training set T = {(e 1 , ω 1 ), . . . , (e |E| , ω |E| )} of single labeled links, where e i ∈ E, i ∈ {0, . . . , |E|} and its corresponding class label is ω i ∈ Ω.

Let e be a new link to be classified, where e may connect the pair of nodes (u, v). Let L 1 be the set of links shared with the direct (1 st level) neighbors of u and v in G, where

|L 1 | = |τ (u)| + |τ (v)|.
Additionally, let L 2 be the set of links unshared with the 2 nd level neighbors of u and v in G, where

|L 2 | = |τ (u) 2 | + |τ (v) 2 |. The set L incorporates L 1 and L 2 .
It is obvious that the class of the links in the set L 1 is E. In contrast, the class of the links in L 2 is ¬E since it includes the links that are not shared between u and v and their respective 2 nd level neighbors. As follows, the nearest neighbors of each unseen link are uncovered thought-out the neighborhood of its end points. Accordingly, instead of comparing each unseen link with all the possible edges in the network, which is computationally not feasible since there are (|V|×(|V|-1)) 2 possible links, it is compared to the neighboring ones. As such, the search space is reduced. Besides, the intuition of node neighborhood approaches is inherently employed as they are exactly intended to find similar nodes. In this context, the authors in [START_REF] Speegle | Extending local similarity indexes with knn for link prediction[END_REF], proposed a framework for LP using k-NN by considering the local similarity indexes to evaluate the similarity with the neighbors. The prediction of an edge uv is made by comparing the neighbors of u to v and vice versa. However, the proposed approach considers the nearest neighbors equally trustworthy. Besides, only one similarity index is considered in k-NN at a time.

In our proposed framework, the evidential k-NN classifier [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] operates in two stages. First, it computes the distances between a test link e and its neighborhood in L and retain the smallest k distances. Subsequently, the evidence given by the k nearest neighbors is combined to get an overview about the global belief regarding the existence of e. The steps are detailed in the following.

At first, one has to determine the k nearest neighbors. For that, we need to define a distance to evaluate the similarity between the edges in the test set and those in the train set. We propose to use the Euclidean distance d(e, e i ) between the link e and its nearest neighbor e i ∈ L by computing the similarities between their connecting nodes as follows:

d(e, e i ) = n j=1 (s j e -s j e i ) 2 (4)
where j is the index of a local similarity metric (e.g, CN, AA, JC, RA, PA), s e and s e i are respectively its values for e and e i and n is the number of local similarities considered.

Each link e i in L represents a piece of evidence that increases our belief about e also belonging to ω i . Yet, this information solely does not provide certain knowledge about the class of e. This situation is modeled in the BFT by simple support functions where only some part of the belief is committed to ω i and the rest is affected to Ω. Therefore, we get the following bba:

m i ({ω i }) = αφ(d i ) m i (Ω) = 1 -αφ(d i ). (5)
where d i = d(e, e i ), α is a parameter such that 0 < α < 1 and φ is a decreasing function. The closer e is to e i according to the distance d, the more likely for e to have same class as e i . In contrast, when e is far from e i , in distance terms, then e i would provide little information regarding the class of e. On that point, the function φ must verify φ(0) = 1 and lim d→∞ φ(d) = 0. Authors in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF] suggest to use the following decreasing function:

φ(d i ) = e (-γd β i ) (6)
where γ > 0 and β ∈ {1, 2, . . . }. β can be arbitrarily fixed to a small value (1 or 2). As a result of considering each nearest neighbor in L as an independent source of evidence regarding the class of the e, we obtain k bba's that can be combined using the conjunctive rule of combination. Thus, a global bba m that synthesizes the belief regarding the existence of e is produced as follows:

m = m 1 ∩ . . . ∩ m k (7)
Finally, decision about the membership of e to one of the classes in Ω is made by comparing m({E}) and m({¬E}). If m({E}) > m({¬E}) then e exists, it is absent otherwise.

Experiments

Experiments are conducted on a real social network component of 1K nodes and 10K edges of the Facebook dataset from [START_REF] Mcauley | Learning to discover social circles in ego networks[END_REF]. Since network data with time information are not usually available, we must settle for the more drastic technique by randomly removing a partition of the edges from the network in order to use them as test set. That is, we remove a random 10% of the edges which we try to predict the existence along with randomly generated false links of the same size using the graph as a source composed by the remaining 90%. The results are obtained by averaging over 10 implementations with independently random divisions of testing set and training set. In order to reduce the computational time, a preprocessing phase is first conducted in which the local similarity scores of all the links from the train and test sets are computed. Evaluation is made according to accuracy which computes the number of correct predictions among all predictions and the precision which takes the fraction of predicted links that are relevant.

Required parameters are α, β, γ for the induced bba's and the number of nearest neighbors k. As discussed in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], the parameters α and β do not have a great influence on the approach performance. Thus, as in [START_REF] Denoeux | A k-nearest neighbor classification rule based on Dempster-Shafer theory[END_REF], α is fixed to 0.95 and β to 1. We tested values of k ranging from 1 to 15. Tests for the optimization of the γ parameter allowed us to set it to the value of 0.12. A comparison with the standard k-NN method (KNN) is carried out, where the class of a link is predicted according to the majority classes of its k nearest neighbors. The results are reported in Fig. 1. It can be seen that both methods have better performances as k increases. Indeed, as we boost the number of nearest neighbors we get more sources of evidence regarding the class membership of the links. Yet, as shown in Fig. 1, performance stops upon reaching a certain threshold. Rather, by increasing excessively the number of nearest neighbors, we get more distant ones (less similar). Consequently, the associated mass functions are close to the state of total ignorance. Thus, they have no impact in the combination and therefore in the prediction. The EKNN based framework has better classification performance than the standard KNN based LP method. It stands to reason that, EKNN performs better for some values of k as a results of taking implicitly the relevance of the information given by the sources into account unlike KNN as it considers all the nearest neighbors equally trustworthy. Although, the results are low for small values of k, it still gives acceptable results i.e., 75% accuracy for k = 3.

In a second stage, we conduct implementations by increasing the number of negative instances (non existing links) at each time to evaluate the behavior of our algorithms to class imbalance scenarios. Actually, LP is a very imbalanced class problem where the number of non existing links is much larger than the existing ones. The same parameters specifications are considered except that k is set to 15. Precision results are presented in Fig. 2 for different negative links number. Measuring precision is very important for evaluating LP since, in many cases, the main goal is to accurately predict the real existing edges. For example, in Facebook, it is more important to not miss actual friends and it does not really matter when unknown friends are recommended. As shown in Fig. 2, EKNN outperforms KNN for most values. Furthermore, the precision plot decreases as more non existing edges are predicted. However, the curve does not fall dramatically but rather slowly reaching 77% for 10K false edges. These good performances are also obtained thanks to the advantages of supervised learning which is permits to center on class boundaries and balance data. As opposed to unsupervised methods which cannot address this imbalance well because they are agnostic to class distributions by nature [START_REF] Lichtenwalter | New perspectives and methods in link prediction[END_REF]. We conjecture that our framework is capable of dealing with the class imbalance problem. Furthermore, it allows us to consider network topology and deal with uncertainty at the same time.

Conclusion

Local similarity measures naturally operate to detect similar nodes which make it simple to extend them to k-NN. In this paper, we propose a framework for link prediction that combines structural local topological properties and the evidential k-NN approach.

Based on the direct and second level neighbors of two unlinked nodes u and v, local similarity indexes are computed and used as features to find their k-nearest neighbors. These latter are considered as items of evidence regarding the class membership of the link uv. Global evidence is pooled using the conjunctive rule of combination from the belief function theory to get an overall information abut new links existence. Tests on real world social network data proved the efficiency of the proposed framework.

It is interesting to note that the novel framework handles skewness in social network data. It is capable of combating class imbalance that characterizes the link prediction task. Furthermore, it shows performance improvement over the baseline KNN which does not take into account uncertainty in the analysis.

A straightforward direction for future research is to take supplementary information into account such as node attributes. Obviously, nodes with similar attribute values are likely to share social relationships i.e., two authors who have the same affiliation and the same research fields. Besides, handling node attributes brings semantics to social connections. Therefore, it is an important source of information that may enhance the link prediction task.

Fig. 1 .

 1 Fig. 1. Results according to the values of k

Fig. 2 .

 2 Fig. 2. Precision results for different negative links number