Malek Bessrour
email: bessrour.malek@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Eric Lefèvre

E-DBSCAN: An evidential version of the DBSCAN method

come

homogeneous local density regions, and to identify noises or outliers.

One of the most widely used density-based techniques is the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], and that goes back to the fact that this algorithm does not require the number of clusters as input.

However, in many data mining clustering applications, sometimes there exist some better partitions of the data that can be as good as the best one found. Let's have data where some points are located in the middle of clusters such as the distance between each point and the other cluster's centers is equal. In this case, many possible solutions exist regarding the membership of those points to the nearest cluster. Therefore, dealing with uncertainty in clustering allows one to properly choose the most interpretable partition from an equivalent set of partitions. Nevertheless, crisp density-based clustering algorithms, such as DBSCAN, fail in detecting and dealing with uncertainty. Therefore, in order to cope with unwanted crisp boundaries, soft density-based clustering techniques have been defined. The fuzzy extensions of DBSCAN generate fuzzy overlapping boundaries clusters by affecting objects to two clusters or more with different membership degrees [START_REF] Ji | Interval-valued possibilistic fuzzy c-means clustering algorithm[END_REF]- [START_REF] Yager | Approximate clustering via the mountain method[END_REF]. A survey regarding the main crisp and fuzzy density-based methods was reported by [START_REF] Ulutagay | Fuzzy and Crisp Clustering Methods Based on The Neighborhood Concept: A Comprehensive Review[END_REF]. Among these fuzzy extensions, we cite Soft DBSCAN [START_REF] Smiti | Soft dbscan: improving dbscan clustering method using fuzzy set theory[END_REF], Fuzzy core DBSCAN [START_REF] Bordogna | Fuzzy core dbscan clustering algorithm[END_REF], Scalable fuzzy neighborhood DBSCAN [START_REF] Parker | Scalable fuzzy Fig. 5: NMI measure for the proposed E-DBSCAN and the other methods on the datasets neighborhood DBSCAN[END_REF], and the Fuzzy extensions of the DBSCAN proposed by [START_REF] Bordogna | Fuzzy extensions of the DBScan clustering algorithm[END_REF].

The evidential clustering, also called credal clustering, is a soft clustering paradigm that extends fuzzy, possibilistic, and rough set clustering. Moreover, these later are sometimes seen as special cases of the evidential clustering [START_REF] Denoeux | Evidential Clustering: A Review[END_REF]. It describes the uncertainty regarding the assignment of objects to clusters using the framework of belief functions [START_REF] Shafer | A mathematical theory of evidence 42[END_REF]. Furthermore, the evidential clustering affects objects to each possible subset of classes with a membership degree defined by a mass function that is between 0 and 1 for each set of clusters. One of the evidential clustering approaches that was proposed is Evclus in [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF]. There are also other methods that have been developed within the theory of belief functions. For instance, we can recall the Evidential C-Means (ECM) method that has been developed to deal with vectorial data [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. In ECM, each object is represented by a mass of belief that is dependent on Abstract-In later years, data have grown enormously and dealing with them to extract information has become a necessity. Data mining is a subfield o f b oth c omputer s cience a nd statistics that aim to extract useful information in a comprehensive structure. The importance of clustering techniques in data mining has lead to the development of many methods in order to deal with data. Among these methods, we name density-based techniques, such as DBSCAN, that partitions data into heterogeneous shapes according to their local densities. DBSCAN can be suitable when handling big data that have noises and outliers. However, the classic DBSCAN method fails in identifying clusters with a variable density distribution and overlapping borders which is accurate in real-world data. In this paper, we propose an unsupervised learning technique in an uncertain context, that combines the DBSCAN method and the framework of the belief function theory, in order to generate clusters having overlapping borders. The proposed evidential clustering method, that we called E-DBSCAN, has the ability to handle cluster membership degree uncertainty of objects by using the belief function theory.

Index Terms-Unsupervised learning, Density-based clustering, DBSCAN, Uncertainty, Belief function theory, Data mining.

I. INTRODUCTION

Clustering techniques have proven their importance in machine learning and data mining, also named data analysis. Data mining is a process that extracts previously unknown patterns from a large quantity of data such as dependencies and groups of data that share close similarities. The idea of clustering is to regroup data into groups or clusters of objects. Objects in one group are similar to each other but dissimilar to the other objects in other groups. The main objective of clustering techniques is to maximize similarities in each cluster (the intra-cluster) and to minimize similarities between clusters (the inter-cluster). Different measures of distances are used to compare between objects such as the Manhattan distance, the Euclidean distance, and the Minkowski distance. These clustering techniques are widely used in many applications as for example marketing [START_REF] Huang | Marketing segmentation using support vector clustering[END_REF], finance [START_REF] Cai | Clustering Approaches for Financial Data Analysis: a Survey[END_REF], m edicine [START_REF] Kerr | Techniques for clustering gene expression data[END_REF], and image processing [START_REF] Dhanachandra | A Survey on Image Segmentation Methods using Clustering Techniques[END_REF]. However, among these applications, some of them require the use of the density-based clustering methods in order to partition data into different shapes and the distance between that object and the space of prototypes. Unlike the classic K-means and the fuzzy K-means algorithms, in ECM prototypes are not only associated to clusters, but also to groups or sets of clusters. The objective of the ECM is to minimize a cost function so that each object has a high mass that is assigned to the cluster that corresponds to the closest prototype to that object. To deal with dissimilarity data, a relational version of the ECM method, called Relational Evidential C-Means (RECM), has been proposed in [START_REF] Masson | RECM: relational evidential c-means algorithm[END_REF]. Specifically, in [START_REF] Masson | RECM: relational evidential c-means algorithm[END_REF], a new notion regarding the Euclidean dissimilarity matrix has been proposed in order to deal with proximity data. Another evidential clustering method called Ek-NNclus was later proposed in [START_REF] Thierry Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF]. In this method, objects are reassigned iteratively to clusters by using the Evidential k-Nearest Neighbors (Ek-NN) rule [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF], and this until a final stable partition is obtained. Ek-NN rule is a classification procedure, based on the nearest neighbors method, that affects a label to an object by taking into account its distances to its k neighbors.

All these methods mentioned above are partition-based methods, however, in literature, there has been no densitybased method proposed within the theory of belief functions. To this extent, we propose a soft version of the densitybased clustering method DBSCAN within the belief theory framework in order to handle the uncertainty of the cluster membership degrees of data.

The rest of this paper is organized as follows. Sections 2 and 3 give an overview of the classic DBSCAN and the belief function theory respectively. Section 4 is dedicated to the description of our method. Section 5 compares our method to existing solutions through the experiments conducted on various datasets. Finally, Section 6 concludes and points to some research opportunities.

II. CLASSIC DBSCAN METHOD

Density-based spatial clustering of applications with noise (DBSCAN), proposed in [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], is considered as one of the wellknown density-based clustering methods. Unlike hierarchical clustering and partition-based techniques, DBSCAN can be very efficient when dealing with arbitrary shaped clusters such as seen in Figure 1.

DBSCAN is based on the concept of reachability that is within a radius, how many neighbors does each point have [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. As a result, it is easier to model clusters with arbitrary shapes. Specifically, DBSCAN assigns each point of the feature space to the clusters that have many points that are close to that point, otherwise it labels them as noises or outliers if their local densities are low, that is to say, their neighbors are below the input radius.

A. DBSCAN parameters

Although, DBSCAN does not require a priori parameter k as number of clusters, it requires two other parameters [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]:

• : radius, specifies how close two points should be one to another in order to be considered neighbors and belong to the same cluster. • MinPts: minimum number of neighbors, specifies the minimum number of points within the radius in order to form a dense region.

B. Parameter estimation

Parameter estimation had become a big problem in every data mining task. To choose good parameters, one needs to understand their use and to have a basic knowledge regarding the data set that is going to be used. Several heuristic studies have been developed to determine DBSCAN parameters. In the following, we recall different methods in literature for MinPts and estimation.

• MinPts: One heuristic approach is to use the natural logarithm function ln(N ) [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], where N is the size of the data set of points to be clustered. Another heuristic approach is to derive the parameter from the number of dimensions (D) in the data set such as MinPts is higher or equal to (D + 1). • : Generally, it is preferable to choose small values.

One heuristic approach [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] is to choose the parameter based on the distances of the dataset. Thus, the k-distance graph is used to find it. Correspondingly, we calculate the mean of the distances of each point to its k nearest neighbors, where k corresponds to MinPts. Then, plot these k-distances in an ascending order and observe a threshold point called a "knee" or a "valley". The value of that knee point corresponds to the optimal parameter.

C. Types of points

Based on these parameters, points can be either classified as core point, as border point, or as outlier [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]:

• Core point: is a point that has at least MinPts neighbors, including itself, within its neighborhood with an radius. • Border point: is a point that is reachable from another point that is a core point, and within its -neighborhood, there exists less than MinPts neighbors. • Noise: is a point that is neither a core point nor a border point. Figure 2 is an illustration of the different types of points where the MinPts is equal to 4. C is a core point surrounded by 4 neighbors represented in green. Blue points like B are border points located within the radius of the green points. Point N does not exist in any radius, thus it represents a noise.

Fig. 2: Type of points in DBSCAN method

By exploring the concepts of density connectivity and density reachability, these parameters and these types of points can be well understood.

D. Reachability

In terms of density, reachability considers a point as being directly reachable from another one if it exists within an distance from it [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF].

• Directly density reachable: An object A is directly density reachable from another object B if A is exists in the -Neighborhood of B and B is a core object.

E. Connectivity

Connectivity is based on a chaining-approach to decide whether a point is located in a particular cluster [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. For instance, object A is density-connected to another object B if there exists an object C such that both A and B are densityreachable from C.

F. Algorithm

The DBSCAN algorithm works iteratively where for each point o selected randomly and not yet visited, if the number of its neighbors is below MinPts, it marks it as a noise, otherwise it affects it to a new cluster and expends the cluster with its neighbors. For each neighbor, DBSCAN checks its -neighborhood and if there exists at least MinPts objects, it expands the cluster with these objects. DBSCAN approach is presented in Algorithms 1 and 2. [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. After that, it was formalized as a theory of evidence by [START_REF] Shafer | A mathematical theory of evidence 42[END_REF] [START_REF] Shafer | A mathematical theory of evidence 42[END_REF]. Then, it was developed as the Transferable Belief Model (TBM) by Smets in the 1980's and 1990's [START_REF] Smets | The transferable belief model and other interpretations of dempster-shafer's model[END_REF]. In this section, we will recall the main concepts of this theory.

A. Frame of discernment

Within the framework of the evidence theory, the frame of discernment regroups all its subsets and is denoted by 2 Ω where each element is called an event or a proposition. The frame of discernment is defined as:

2 Ω = {A, A ⊆ Ω} = {∅, {ω 1 } , {ω 2 } , ..., {ω 1 , ω 2 } , ..., Ω} (1)
Where the empty set ∅ represents the impossible proposition, and the set Ω represents the certain proposition.

B. Basic belief assignment

The basic belief assignment (bba), also called mass function represents the effect of an uncertain evidence on the frame of discernment's all subsets. This function is defined as 2 Ω → [0, 1] such that:

m (∅) = 0 and A⊆Ω m (A) = 1 (2)
where the value m (A), that is named a basic belief mass (bbm), interprets the fraction of evidence that supports exactly the assertion that the actual event ω belongs to A (ω ∈ A) and nothing more specific.

C. Combination rule

In belief function theory, if different information sources of evidence are available we aggregate them using the Dempster rule of combination [START_REF] Shafer | A mathematical theory of evidence 42[END_REF]:

m 1 ⊕m 2 (A) =    B∩C=A m1(B)m2(C) 1- B∩C=∅ m1(B)m2(C) f or A = ∅ and A ⊆ Ω. 0 f orA = ∅. (3)

D. Decision making

In some cases, it is necessary to make a decision based the available evidence that is modelled in bba forms. In this context, pignistic transformation [START_REF] Smets | The transferable belief model and other interpretations of dempster-shafer's model[END_REF] has been introduced to transform belief functions into probability measures, denoted BetP and defined as:

BetP (A) = B⊆Ω |A ∩ B| |B| m(B), ∀A ⊆ Ω. (4)

E. Evidential k-Nearest Neighbors rule

Let Ω = {ω 1 , ..., ω c } be the set of classes or groups, and let d ij be the distance that separates the object o i to be labeled and the object o j that belongs to the class or group ω k(j) with k(j) ∈ {1, . . . , c}. The knowledge about the label of object o j and the distance d ij from o i to o j is taken as a piece of evidence and can be represented, thus, by the mass function in the following:

m ij ({ω k(j) }) = α ij (5)
m ij (Ω) = 1 -α ij (6)
with where ϕ is set to be a non-increasing mapping function such that:

α ij = ϕ(d ij ) (7)
lim d→+∞ ϕ (d) = 0 (8)
In [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF], the author proposed to choose ϕ as:

ϕ (d ij ) = α 0 exp (-γ k(j) d β ij ) (9)
where α 0 and β are constants such that 0 < α 0 < 1 and β ∈ {1, 2, ...}. The distances from object o i to the k objects are, then, considered as k pieces of evidence, thus, mass functions m i are combined by using Dempster's rule in Equation 3 in order to obtain the mass function of the object o i .

In [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF], it was proposed to replace the k parameter in the Ek-NN rule, that refers to the number of neighbors to be considered in the combination rule, with another parameter that refers to a radius that will represent the area to be considered in the combination rule. Let's have a point o i that we would like to calculate its mass function and a given radius parameter , all the points that exist within the area of point o i are taken as pieces of evidence in order to calculate its mass function. Figure 3 represents the difference between the two constraints where in Figure 3 (a), the mass function of point A is calculated by combining the masses of its k neighbors, while in Figure 3 (b), the mass function of point A is calculated by combining the masses of all the points that exist within the radius.

IV. EVIDENTIAL DBSCAN

In this section, we propose our evidential version of DB-SCAN which we call E-DBSCAN. We define it by specifying an approximate value of the radius instead of a crisp numeric parameter . The proposed method consists basically of three steps. Firstly, we determine core points and their neighbors that are within the min , and within the belief function framework, this is the state of total certainty. Thus, we assign these points to their clusters with the equation:

∃ω i ∈ Ω, m ({ω i }) = 1 (10)
Secondly, for each point that exists within the max radius of core points, we assign its membership degree based on its neighbors by following the principle of the Ek-NN rule [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF]. These points are called soft border points. Finally, unlabelled points or outliers that does not exist within max radius of any core point will be assigned to total ignorance class. The proposed method is described in Algorithms 3 and 4.

A. Allocation of soft border points

Soft border points that are between the min radius and the max radius of core points can be assigned to the existing clusters based on their neighbors and the labelled points in the neighbourhood can be seen as a source of evidence. We replace the k parameter of the Ek-NN rule with the max radius following the approach proposed by [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF]. Suppose point o i is a soft border point. Following the principle of label determination processing based on the Ek-NN rule and the radius approach of [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF], [START_REF] Denoeux | Classification Using Belief Functions: Relationship Between Case-Based and Model-Based Approaches[END_REF], for each neighbor o j of o i within the max radius, a mass function m ij representing the membership of o j can be assigned following Equations 5 and 6. In our method, α ij can be determined by the dissimilarity between the soft border point o i and its neighbor o j , that is to say, α is high (respectively low) when d ij is small (respectively big). Thus, α can be set as a decreasing function of d ij :

α ij = exp -γ k(j) d 2 ij ( 11
)
where α 0 from Equation 9is set to 1 as default, β is set to 2 as default, and γ k(j) can be set to the inverse of the mean squared distance between points belonging to class ω k(j) heuristically.

Using the Dempster rule of combination, we can induce border points memberships to clusters by combining the bbas of their neighbors within max radius. Suppose that point o i is a soft border point in overlapping regions, the evidence provided by its k neighbors are in the form of bbas m i1 , ..., m ik and thus the bba for point o i 's cluster membership can be obtained by combining the k pieces of evidence from neighbors.

B. Allocation of the remaining points

The remaining unlabelled points which do not belong to any neiborhood of core points are considered as outliers or noises and will be assigned to total ignorance class.

Figure 4 is an illustration of the E-DBSCAN method where points G and F are core points, B, C, D, E are border points, A is a soft border point, and red points are noisy points. Following the Ek-NN rule, the membership degree of point A is calculated by combining the bbas of its labelled neighbors B, C, D, E, F and G.

V. EXPERIMENTAL STUDY

Within this section, we evaluate our proposed approach in order to prove its effectiveness and feasibility. In subsection A, we present the experimental framework we used and the parameter setup of each data sat. Then, in subsection B, we describe the results as well as a comparison between the proposed method and other existing methods. We first developed our proposed method E-DBSCAN using Python 3.7, then we tested it on classical datasets from the UCI Machine Learning Repository [25] and the "pdfCluster" package [START_REF] Azzalini | The pdfCluster-package[END_REF], also a synthetic dataset from the "EVCLUST" package [START_REF] Denoeux | Evclust: Evidential Clustering[END_REF]. The characteristics of these datasets are summarized in Table I. After that, once the results of the evaluation are established, we compared them with the following crisp and soft methods:

• K-means which is one of the simplest crisp clustering methods and require the number of clusters as input [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. • DBSCAN which is a nonparametric crisp density-based clustering method [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. • ECM which is a soft clustering method based on the belief function theory and require the number of clusters as input [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF]. • Ek-NNclus which is a soft clustering method based on the belief function theory, and requires the number k of neighbors and a scale parameter [START_REF] Thierry Denoeux | EK-NNclus: a clustering procedure based on the evidential k-nearest neighbor rule[END_REF].

We evaluate the results using the Adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF] defined by:

ARI = RI -Expected RI max(RI) -Expected RI (12)
where

RI = T P + T N T P + F P + F N + T N (13)
That measures the similarity between partitions. When two partitions are equal this index equals 1, and when the partitions are completely different this index equals 0. We note that this index only compares hard partitions, i.e., we refer to the pignistic transformation to compare the results with the hard clustering methods. We also used the Normalized Mutual Information (NMI) [START_REF] Streh | Cluster ensembles -A knowledge reuse framework for combining multiple partitions[END_REF] to estimate clustering quality. It is defined by:

N M I(Y, C) = 2 × I(Y, C) H(Y ) + H(C) (14)
Where Y is the class label, C is the cluster label, H(x) is the entropy and I(Y, C) is the Mutual Information between Y and C such that I(Y, C) = H(Y ) -H(Y |C). This index equals 1 for perfect correlation, and equals 0 for no mutual information.

For each dataset, we define the values of the parameters that we set for each algorithm in table II.

B. Experimental results

Results of the ARI measure for the proposed E-DBSCAN and the other methods on all the datasets are shown in Table III. For each couple of dataset and algorithm, we have given the best result.

We can see that the E-DBSCAN method identified correctly the number of clusters for all cases. The Ek-NNclus and the DBSCAN method failed in detecting the correct number of clusters in both Iris and Wine datasets. As measured by the ARI criterion, E-DBSCAN outperformed the other method and gave a better partition quality for all the datasets except the Wine dataset. We can see that ECM gives slightly better results for the Wine dataset, however, the algorithm was initially provided with the correct number of partitions.

Best results of the NMI measure for the proposed E-DBSCAN and the other methods on all the datasets are shown in Figure 5. We can see that our proposed method gives better results for the Iris, Olive oil and Statlog (Heart) datasets and very close results compared to ECM for the Four-classes dataset. However, for the Wine dataset the K-means and the ECM gave better results and this can be explained by the fact that the number of clusters was given as an input which is considered as an extra knowledge regarding the correct number of the cluster partitions.

Comparing computing time results for the soft methods, seen in Table III, we can note that our method is significantly faster than the other soft methods for the Iris and the Wine dataset. However, for the Four-classes and the Olive oil datasets, the other methods were faster, and this can be explained by the high overlapping areas between the clusters

VI. CONCLUSION

In this paper, we developed a new soft clustering method for the Density-Based Spacial Clustering Application with Noise (DBSCAN), that we called Evidential DBSCAN or E-DBSCAN, using the framework of belief function theory. The aim of this method is to model distinct density-based spatial distribution of objects in the feature space. A soft constraint was defined to specify an approximate local density around points in order to handle the cluster membership uncertainty problem and to generate overlapping clusters. Results of the experimental comparison between our proposed method and other state of the art methods over real and synthetic datasets proved a better performance w.r.t the ARI and NMI criteria which highlight the efficiency of our proposal. In future work, a study on the parameter estimation for the E-DBSCAN can be done to enhance, furthermore, its performance.

Fig. 1 :

 1 Fig. 1: Difference between results of K-means (a) and DB-SCAN (b)

Algorithm 1 :

 1 DBSCAN(D, ,MinPts) Input: : radius around a point to form a neighborhood area Input: MinPts: minimum number of neighbors to be be considered as a core point Data: D: Dataset 1 C=0 2 Clusters=∅ 3 forall o ∈ D s.t. o is unvisited do mark o as visited neighborsPts = regionQuery(o, ) if sizeof(neighborsPts) <= MinPts then Mark o as Noise else C = next cluster Clusters = Clusters ∪ expandCluster(o, neighborsPts, C, , MinPts) return Clusters Algorithm 2: expandCluster(o, neighborsPts, C, , MinPts) Input: o: the point that was just marked as visited Input: neighborsPts: the neighborhood of point o Input: C: the current cluster Input: : radius around a point to form a neighborhood area Input: MinPts: minimum number of neighbors to be be considered as a core point 1 add o to cluster C 2 forall o ∈ neighborsPts do if o is not visited then Mark o as visited neighborsPts = regionQuery(o , ) if sizeof(neighborsPts ) > MinPts then neighborsPts = neighborsPts ∪ neighborsPts if o is not yet member of any cluster then add o to cluster C return C III. BELIEF FUNCTION THEORY Belief function theory (also referred to as evidence theory or Dempster-Shafer theory) is a theoretical framework, like the possibility or the probability theories, for reasoning under uncertainty. It was first introduced by Dempster (1967) in the statistical inference's context

Fig. 3 :

 3 Fig. 3: Comparison between the use of the two parameters k and in the calculation of the mass function of an object A

Fig. 4 :

 4 Fig. 4: E-DBSCAN illustration

3 kFour-classes 4 4 k 3 k 2 k

 3432 = {3, . . . , 10} M inP ts = {3, . . . , 10} q=0.9 = {0.3, . . . , 0.5} M in = {0.3, . . . , 0.5} M ax = {0.4, . . . , 0.8} Wine 3 = {40, . . . , 50} M inP ts = 3 M inP ts = 3 q = {0.5, . . . , 0.8} = {30, . . . , 50} M in = {30, . . . , 50} M ax = {45, . . . , 50} = {40, . . . , 60} M inP ts = 20 M inP ts = 20 q = {0.7, . . . , 0.9} = {0.7, . . . , 0.9} M in = {0.7, . . . , 0.9} M ax = {3.5, . . . , 4} Olive oil 3 = {100, . . . , 150} M inP ts = 10 M inP ts = 10 q = {0.7, . . . , 0.9} = {100, . . . , 130} M in = {100, . . . , 130} M ax = {130, . . . , 150} Statlog(Heart) 2 = {30, . . . , 50} M inP ts = {5, . . . , 10} M inP ts = {5, . . . , 10} q = {0.6, . . . , 0.9} = {15, . . . , 25} M in = {15, . . . , 25} M ax = {25, . . . , 35}

TABLE I :

 I Algorithm 4: expandSoftCluster(o, neighborsPts, soft-borderPts, C, M in , M ax , MinPts) Input: o: the point that was just marked as visited Input: neighborsPts: the neighborhood of point o Characteristics of the real datasets.

	Input: soft-borderPts: the soft border neighborhood
	of point o
	Input: C: the current cluster
	Input: M in M ax : soft constraint on the radius around
	a point to define neighbors and border points
	Input: MinPts: minimum number of neighbors to be
	be considered as a core point
	1 add o to cluster C
	2 forall o ∈ neighborsPts do
	if o is not visited then
	Mark o as visited
	neighborsPts = regionQuery(o , M in )
	if sizeof(neighborsPts ) > MinPts then
	neighborsPts = neighborsPts ∪
	neighborsPts
	soft-borderPts = regionQuery(o , M ax )
	\neighborsP ts
	soft-borderPts = soft-borderPts ∪
	soft-borderPts
	if o is not yet member of any cluster then
	add o to cluster C
	return C
	Name	Clusters Attributes Instances
	Iris	3	4	150
	Wine	3	13	178
	Four classes	4	2	400
	Olive Oil	3	8	572
	Statlog(Heart) 2	13	270

TABLE II :

 II Datasets parameters

TABLE III :

 III ARI measure for the proposed E-DBSCAN and the other methods on the datasets

	Dataset	Result K-means DBSCAN	ECM	EK-NNclus E-DBSCAN
		K	3	2	3	6	3
	Iris	ARI	0.730	0.520	0.589	0.188	0.790
		time	0.030	0.062	0.573	0.215	0.211
		K	3	6	3	6	3
	Wine	ARI	0.371	0.281	0.429	0.284	0.364
		time	0.034	0.003	0.687	0.367	0.157
		K	4	4	4	4	4
	Four-classes	ARI	0.734	0.465	0.735	0.728	0.735
		time	0.046	0.004	1.735	0.574	6.528
		K	3	3	3	3	3
	Olive oil	ARI	0.318	0.527	0.328	0.388	0.546
		time	0.054	0.011	1.109	2.569	1.928
		K	2	2	2	4	2
	Statlog(Heart)	ARI	0.030	0.065	0.011	0.060	0.065
		time	0.032	0.006	0.381	0.428	0.027
	in these datasets.


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

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Toward the evaluation of Case Base Maintenance policies under the belief function theory

Keywords: Case-Based Reasoning, Case-Base Maintenance, Competence Evaluation, Uncertainty, Belief Function Theory, Combination

The life cycle of Case-Based Reasoning (CBR) systems implies the maintenance of their knowledge containers for reasons of efficiency and competence. However, two main issues occur. First, knowledge within such systems is full of uncertainty and imprecision since they involve real-world experiences. Second, it is not obvious to choose from the wealth of maintenance policies, available in the literature, the most adequate one to preserve the competence towards problems' solving. In fact, this competence is so difficult to be actually estimated due to the diversity of influencing factors within CBR systems. For that reasons, we propose, in this work, an entire evaluating process that allows to assess Case Base Maintenance (CBM) policies using information coming from both a statistical measure and a competence model under the belief function theory.

Introduction

Case-Based Reasoning (CBR) is a methodology of problem solving that reuses past experiences to solve new problems according to their similarities [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]. Every new solved problem by a CBR system is retained in a memory structure called a Case Base (CB) to serve for future problems resolution. Although the incremental learning of CBR systems presents a strong point, it is not free of drawbacks. In fact, this evolution can be uncontrollable, caused by the retention of redundant and noisy cases which conduct to the degradation of systems' problem-solving competence and performance. For those reasons, the Case Base Maintenance (CBM) field presents the key factor's success of CBR systems. As has been defined in [START_REF] Leake | Categorizing case-base maintenance: dimensions and directions[END_REF], "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". During the last five decades [START_REF] Juarez | Maintenance of case bases: current algorithms after fifty years[END_REF], a wide range of CBM policies have been proposed, even in Machine Learning or CBR communities, that aim to update CBs content in such a way to be performer and more competent to make high quality decisions. Different attempts to classify them have been proposed in different papers [START_REF] Smiti | Overview of Maintenance for Case based Reasoning Systems[END_REF][START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF][START_REF] Lupiani | Evaluating case-base maintenance algorithms[END_REF][START_REF] Chebel-Morello | Case-based maintenance: Structuring and incrementing the case base[END_REF]. One of the simplest categorizations consists at regrouping CBM policies by their ability for uncertainty management (hard and soft). Condensed Nearest Neighbor (CNN) [START_REF] Hart | The condensed nearest neighbor rule[END_REF] and Reduced Nearest Neighbor (RNN) [START_REF] Gates | The reduced nearest neighbor rule[END_REF] present the baseline of the CB maintenance task. For the soft CBM policies, less work have been proposed, where two are implemented within the framework of the belief function theory which are Evidential Clustering and case Types Detection for CBM (ECTD) [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF] and Dynamic policy for CBM (DETD) [START_REF] Ben Ayed | DETD: Dynamic Policy for Case Base Maintenance Based on EK-NNclus Algorithm and Case Types Detection[END_REF].

After performing a maintenance task, the question that arises is whether the original CBR is better, tantamount, or worse than the maintained one. The intuitive answer to this question is to measure the competence of the CB before and after maintenance. Therefore, this allows us to estimate the support degree of the CBM policy as well as its adequacy to be applied. However, estimating the real competence of a given CBR system in problem-solving is a very complex task since this competence depends on many affecting factors, such as statistical and problem solving properties [START_REF] Smyth | Modelling the competence of case-bases[END_REF]. To deal with these problems, available research are even measuring the accuracy of the CBR system using a statistical measure [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF][START_REF] Ben Ayed | Exploiting Domain-Experts Knowledge Within an Evidential Process for Case Base Maintenance[END_REF] or estimating their competence using a competence model [START_REF] Smiti | SCBM: soft case base maintenance method based on competence model[END_REF][START_REF] Smyth | Modelling the competence of case-bases[END_REF]. Some of them are aware of the great importance of managing uncertainty within such knowledge since they reflect real-world situations. Consequently, we aim, in this work, to evaluate CBM policies by offering a support/adequacy degree through combining information coming from an accuracy measure and a competence model. To offer high quality aggregation with managing conflict within both sources' information, and to deal with uncertainty within case knowledge, we use one among the most powerful tools for uncertainty management called the belief function theory.

The rest of the paper is organized as follows. In the next Section, we overview the key factors that affect CBs competence and the two used ways for CBR evaluation. Section 3 presents, then, the basics of the belief function theory, as well as the used tools. Throughout Section 4, our CBM evaluating process is detailed to indicate the adequacy of the used CBM policy and estimate its support degree. In Section 5, we elaborate the experimental study on different CBM policies and using different CBs. Finally, Section 6 concludes the paper and proposes some future work.

Case Base Competence Evaluation

The competence (or coverage) of a CBR system presents the range of problems that it can successfully solve [START_REF] Smyth | Modelling the competence of case-bases[END_REF]. Actually, this criterion cannot be well estimated when we use a simple metric due to the diversity of influencing factors (Subsection 2.1). In the literature, this competence is even estimated using statistical measure such as the accuracy (Subsection 2.2), or using some competence model such as CEC-Model [START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF] (Subsection 2.3).

Key factors affecting CBs competence

Estimating the competence of a CBR system needs an awareness regarding the set of elements that may affect it. Actually, we note that the statistical properties of cases within a CB is highly influencing its ability in covering the problem space. Besides, problem-solving properties are an intuitive influencing factor of CBR systems competence. As done in [START_REF] Smyth | Modelling the competence of case-bases[END_REF][START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF], we can enumerate these factors as follows: CB size * , cases distribution * , density of cases * , cases vocabulary * , Similarity * , and adaptation knowledge3 .

Statistical Measures for CBR evaluation

Some works mention that the precision or the accuracy presents a kind of true competence [START_REF] Smyth | Modelling the competence of case-bases[END_REF] with some limitations. Actually, the competence of a CBR system can be recognized as input problem solving capability with the right solutions. The most common and straightforward practice consists at using a test set from the original CB and applying a classification algorithm4 to solve problems. By this way, we can estimate the competence of the CBR system using statistical measures such as the accuracy as the percentage of correct classifications, the specificity as the true negative rate, and others [START_REF] Mosqueira-Rey | Validation of intelligent systems: a critical study and a tool[END_REF].

Actually this kind of measures have to be taken into account when measuring the competence of a CB. However, it is not sufficient since it does not cover several affected factors. Hence, competence models are also used for this matter.

Competence Models for CBR evaluation

Various competence models have been proposed to take into account different influencing factors. For instance, we find Case Competence Categories Model [START_REF] Smyth | Remembering to forget: a competence-preserving deletion policy for CBR systems[END_REF] which consists at dividing cases into four types so as to fix a maintenance strategy to be followed. However, it is not able to tangibly and mathematically quantify the global competence of the entire CB. Besides, we find Coverage model based on Mahalanobis Distance and clustering [START_REF] Smiti | Modeling competence for case based reasoning systems using clustering[END_REF], that uses a density-based clustering method to distinguish three types of cases on which the overall CB competence depends. However, we cannot well estimate this competence without deeply studying the relation between cases. Although Smyth & McKenna model [START_REF] Smyth | Modelling the competence of case-bases[END_REF] is able to deal with different influencing factors, it suffers from its disability to manage the uncertainty within the real stored situations. Hence, the Coverage & Evidential Clustering based Model (CEC-Model) [START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF] has been proposed in a preliminary work to tackle the problem of uncertainty management while regrouping cases and measuring similarities. Its entire cycle is described in Figure 1. By this way, we use the latter mentioned CEC-Model [START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF], and the

Belief Function Theory: Basic concepts

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], called also Evidence theory, is a mathematical framework for reasoning under partial and unreliable knowledge. This model is basically defined by a frame of discernment Ω which represents a set of a finite elementary events. The major strength of this theory is its ability to model all levels of uncertainty, from the complete ignorance to the total certainty, on a power set 2 Ω which contains all the possible subsets of Ω.

The key point of this theory is the basic belief assignment (bba) m which is defined as follows:

m : 2 Ω → [0, 1] A → m(A) (1)
with m is satisfying the following constraint:

A⊆Ω m(A) = 1 (2)
It aims at allocating to every set A ∈ 2 Ω a degree of belief to represent the partial knowledge about the actual value of y defined on Ω. A mass function is normalized if it assigns to the empty set partition null degree of belief (m(∅) = 0). Contrariwise, the assigned amount of belief to the empty set reflects the flexibility to consider that the value of y may not belong to Ω. The latter situation has usually been used during the evidential clustering to identify noisy instances [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF][START_REF] Antoine | CECM: Constrained evidential c-means algorithm[END_REF], where the frame of discernment Ω defines the set of clusters.

Actually, we often need to calculate the distance between two mass functions defined in the same frame of discernment. To do so, Jousselme Distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] presents one among the most used tools to measure distances between two pieces of evidence. It is defined as follows:

d(m 1 , m 2 ) = 1 2 ( -→ m 1 --→ m 2 ) T D ( -→ m 1 --→ m 2 ) ( 3
)
where D is a square matrix of size 2 K (K = |Ω|), and its elements are calculated such that:

D(A, B) = 1 if A = B = ∅ |A∩B| |A∪B| otherwise (4)
In the framework of belief function theory, various combination rules of evidence have been proposed. The conjunctive rule of combination [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF] is one of the most used ones to combine two pieces of evidence induced from two independent and reliable sources of information. When the normality constraint (m(∅) = 0) is imposed, we may use the Dempster's rule of combination [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF].

Ultimately, to make decision under the belief function theory, we may use the pignistic probability transformation, denoted BetP , which is considered as one of the best ways for decision making. If the mass function is normalized, then BetP is defined as follows:

BetP (y) = x∈A m(A) |A| (5)
where y ∈ Ω and A ⊆ Ω contains y. Since m is normalized, BetP (y) is independent of of the set A that contains y. Otherwise, a preprocessing step of normalization should be applied [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF].

Evidential CBM Evaluating Process

In this Section, we propose an evaluation method for Case Base Maintenance policies that aims to estimate their support/adequacy degree for a given CBR system. Its main idea consists at combining two mass functions reflecting their adequacy. These mass functions are deduced from the improvement degree of competence, extracted respectively from the CEC-Model [START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF] and the accuracy criterion before and after applying the CBM policy. For the sake of clarity, a general depict of the proposed evaluating method is shown in Figure 2.

Two-level original CBR evaluation

First of all, we aim at measuring the competence of the original non-maintained CBR system using both the evidential competence model CEC-Model [START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF] Comp O estimation: The original CB denoted CBR O presents the input of CEC-Model. As shown in Figure 1, it applies the Evidential C-Means (ECM) [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] for cases clustering, Jousselme Distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF] (Equations 3 and 4) for similarity calculation, and pignistic probability transformation (Equation 5) for cases membership decision. Finally, groups coverage and CB competence are estimated through the density and size properties. The output result is bounded in [0, 1], where the more it is near to 1 the more CBR O is considered as competent in solving problems.

Acc O estimation: The accuracy criterion is studied using 10-fold cross validation and the k-NN as a classifier (we chose to take k = 1). To be measured, the original CB is divided into training set (T r = 0.8 × CB) and test set (T s = 0.2 × CB), where T r plays the role of the entire CB and T s contains the set of input problems to be solved from T r. Acc O is therefore calculated as follows:

Acc O = #Correct Classif ications on T s Size of T s (6)

Case Base Maintenance application

After measuring the Original CB competence through the two previous identified sources (competence model and accuracy criterion), we perform on CBR O the CBM policy to be evaluated. Actually, the main purpose of CBM policies is to detect the subset of cases that let a high problem-solving capability. In this step, we may consider the applied policy as a black box and we only focus on its input (CBR O ) and output, which is the maintained CB (CBR M ). By this way, any CBM policy, in the literature, may be applied at the aim to be evaluated, thereafter, by our evaluating process.

Two-level maintained CBR evaluation

Once the CBM policy completes its execution, our next step consists at measuring the edited CB competence using the same tools and settings as the first step to generate Comp M and Acc M values.

Comp M estimation: As previously done, we evaluate the CB using the CEC-Model, whereas that time it is applied to assess the maintained CB (CBR M ) and provide Comp M between 0 and 1.

Acc M estimation: The testing strategy of the accuracy after the maintenance task consists at dividing CBR O into training set T r and test set T s. Then, the used CBM policy is applied on T r to generate an edited training set T r M . Using 1-NN, the accuracy is measured through classifying T s using T r M . Finally, Acc M is obtained by averaging ten trials values using 10-fold cross validation.

Extracting CBM adequacy knowledge from statistical measure and competence model independently

Up to now, we have four different competence estimation values (in [0, 1]) that come from two sources: CEC-Model and Accuracy measure. The first is measuring the competence of CBR O , and the second assesses the quality of the applied CBM task through CBR M . During this step, we highlight the improvement of CBR O against CBR M , in terms of both competence and accuracy. Therefore, we define these two improvements (Imp Comp and Imp Acc ) as follows:

Imp Comp = Comp M -Comp O (7)
and

Imp Acc = Acc M -Acc O (8)
Knowing that their offered values are in [-1, 1], three distinguished situations arise regarding Imp x , where x replaces even Comp or Acc terms:

-If Imp x 1, then a high degree of adequacy is assigned to the applied CBM policy for the CBR system. -If Imp x -1, then the used CBM policy is not adequate at all for the CBR system. -If Imp x 0, then we have no preference regarding the maintenance task.

Knowledge combination under the belief function theory

Based on the situations mentioned above, we build two mass functions on the same frame of discernment which contains two events. The first consists at indicating that the CBM policy is adequate to be applied on a given CBR system, and the second presents its complementary event. Hence, this frame is defined as follows:

Ω = {Adequate, Adequate} (9)
By this way, the mass functions, defined on Ω, indicates the evaluation of the CBM policy. The first m Comp describes the knowledge coming from the improvement in terms of competence, and the second m Acc informs the knowledge originated by the improvement in terms of accuracy. Consequently, we similarly define them as follows:

m Comp                m Comp (∅) = 0 m Comp (Adequate) = Imp Comp If Imp Comp ≥ 0 0 Otherwise m Comp (Adequate) = |Imp Comp | If Imp Comp < 0 0 Otherwise m Comp (Ω) = 1 -|Imp Comp | (10) and m Acc                m Acc (∅) = 0 m Acc (Adequate) = Imp Acc If Imp Acc ≥ 0 0 Otherwise m Acc (Adequate) = |Imp Acc | If Imp Acc < 0 0 Otherwise m Acc (Ω) = 1 -|Imp Acc | (11)
Obviously, knowledge obtained from each source is not perfect. Hence, their aggregation presents an interesting solution to reach more relevant information. For that reason, we opt to synthesize the knowledge obtained in m Comp and m Acc by combining them using tools offered within the evidence theory. Since m Comp and m Acc present normalized mass functions that are defined in the same frame of discernment Ω and induced from two distinct information sources, which are considered to be reliable, we use the conjunctive rule of combination defined in [START_REF] Smets | Application of the transferable belief model to diagnostic problems[END_REF] as follows:

(m Comp ∩ m Acc )(C) =    A∩B=C m Comp (A)m Acc (B) If C = ∅, ∀A, B ∈ Ω 0 Otherwise (12)
In the current work, we are not interested in making decision regarding whether the applied CBM policy is adequate or not, but we aim to estimate the adequacy support degree for the applied maintenance task. To do, we interpret this rate as the pignistic probability of the event "Adequate". Consequently, we measure this probability using Equation 5 in such a way that:

CBM support degree = BetP (Adequate) [START_REF] Ben Ayed | DETD: Dynamic Policy for Case Base Maintenance Based on EK-NNclus Algorithm and Case Types Detection[END_REF] 5 Experimentation

The following experiments aim at projecting our proposal on the maintenance field within CBR systems and use it to evaluate this CBM policies adequacy. In this Section, we present used data and the followed settings during implementation and tests (Subsection 5.1). Offered results and discussion are then provided in Subsection 5.2.

Experimental setup

Our proposed evaluating process of the current work have been tested on five case bases from UCI Machine Learning Repository5 to assess CBM policies available in the literature. These datasets are described in Table 1 in term of size, number of problems attributes, and number of classes or solutions. For every CB, we estimate the support maintenance degree of four CBM policies. We have chosen CNN [START_REF] Hart | The condensed nearest neighbor rule[END_REF] and RNN [START_REF] Gates | The reduced nearest neighbor rule[END_REF] as the most widely used CBM algorithms, as well as ECTD [START_REF] Ben Ayed | ECTD: Evidential Clustering and case Types Detection for case base maintenance[END_REF] and DETD [START_REF] Ben Ayed | DETD: Dynamic Policy for Case Base Maintenance Based on EK-NNclus Algorithm and Case Types Detection[END_REF] as the two existing CBM policies under the belief function theory. These methods have been developed according to their default settings as described in their referenced papers.

Results and discussion

As regards to the study of results offered, in Table 2, by our proposed evaluating process, some particular situations should be pointed out. If the offered support degree is equal to 50%, then the applied CBM method was able to retain exactly the initial competence of the CBR system. The amount above 50 represents the capability rate of the CBM policy to improve that competence. Therefore, the higher this value, the more the CBM policy is adequate to be applied. On the contrary, the amount below 50 reflects the amount of competence degradation after maintenance. In Table 2, we note that almost all the offered CBM support degrees are in [40,60], which means that performed CBM policies slightly reduce or improve the CBR competence in problem-solving. Nevertheless, we remark that CNN and RNN algorithms are not adequate to be applied on some CBs such as "Ionosphere" and "Glass" datasets (25.74% and 29.98% with CNN, and 17.95% and 29.98% with RNN). In our sense, we may tolerate values in [45,50] if other evaluation criteria are improved such as CBR performance and response time 6 . Ultimately, we note that the ECTD policy is the most supported CBM method to be applied on the different tested CBs, where it offers support values equal to 57.27% with "Breast Cancer", 50.84% with "Glass", 47.66% with "Ionosphere", 50.68% with "Indian", and 50.78% with "Sonar". These values indicate that maintenance task applied by ECTD improves the performance of almost all the original tested CBs.

Conclusion

In this paper, a process for evaluating Case Base Maintenance policies is proposed. Its main idea consists at applying a given CBM policy and measuring the CB competence before and after maintenance using both of an evidential competence model and the statistical accuracy measure. The output of these two sources are modeled and aggregated within the belief function framework to offer a high-quality CBM support degree estimation. During the experimentation, this process has been performed on different CBM policies and using different datasets. As future work, we opt to intervene on the opposite sense by setting parameters of some CBM policies at the aim of maximizing the support degree offered by the proposed evaluation process.

Fig. 1 .

 1 Fig. 1. CEC-Model's process

Fig. 2 .

 2 Fig. 2. The proposed CBM evaluating process

  to provide Comp O and the accuracy criterion to provide Acc O .

	Original CBR
	Competence O	Accuracy O
	CBM policy
	Maintained CBR
	Competence M	Accuracy M
	Improvement Comp	Improvement Acc
	Evidential Aggregation
	CBM support degree

Table 1 .

 1 Case bases description

		Case base # instances # attributes # solutions
	1 Breast Cancer	569	32	2
	2	Glass	214	9	6
	3 Ionosphere	351	34	2
	4	Indian	583	10	2
	5	Sonar	208	60	2

Table 2 .

 2 Support degree results of some CBM policies applied on some CBs CB CBM CompO (%) CompM (%) AccO (%) AccM (%) CBM support degree (%)

	Cancer	CNN RNN ECTD	83.44 83.44 83.44	81.52 82.11 83.12	59.39 59.39 59.39	71.45 71.45 74.25	55.08 55.37 57.27
		DETD	83.44	83.06	59.39	70.12	55.18
		CNN	55.86	54.24	87.38	48.33	29.98
	Glass	RNN ECTD	55.86 55.86	54.24 55.18	87.38 87.38	48.33 89.75	29.98 50.84
		DETD	55.86	54.26	87.38	73.81	42.52
	Ionosphere	CNN RNN ECTD DETD	93.86 93.86 93.86 93.86	69.74 68.88 89.17 88.72	86.61 86.61 86.61 86.61	54.46 34.46 86.61 77.53	25.74 17.95 47.66 43.12
	Indian	CNN RNN ECTD	74.22 74.22 74.22	72.12 71.03 73.68	65.26 65.26 65.26	61.88 61.75 67.15	47.30 46.71 50.68
		DETD	74.22	70.13	65.26	59.87	47.05
	Sonar	CNN RNN ECTD	78.11 78.11 78.11	73.87 72.96 76.32	81.28 81.28 81.28	64.22 62.85 84.62	39.71 39.63 50.78
		DETD	78.11	76.01	81.28	78.55	47.31

The factors identified with a star ( * ) are taken into account in the current work.

The (k-NN) classifier is the most used within the CBR community.

https://archive.ics.uci.edu/ml/

Forthcoming research work will carry out with other evaluation criteria.


Malika Ben Khalifa
email: malikabenkhalifa2@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Eric Lefèvre

Multiple criteria fake reviews detection based on spammers' indicators within the belief function theory

Keywords: Online reviews, Fake reviews, Spammers, Multi-criteria evaluation, Uncertainty, Belief function theory

published or not. The documents may come

Multiple criteria fake reviews detection based on spammers' indicators within the belief function theory

Introduction

Nowadays, online reviews are one of the most valuable sources of information for customers. Moreover, they are considerate as the pillars on which companies' reputation is built. Most of consumers believe in checking the reviews given to a product or service before deciding to purchase it. Therefore, companies with high number of positive reviews are lucked to attract a huge number of new consumers and consequently they will achieve significant financial gains. However, negative reviews or lowest rating reviews cause financial losses. Driven by the profit, some companies and brands pay spammers to post fake positive reviews on their own product in order to enhance their e-reputation, not only that but also they try to damage competitors' reputation by posting negative reviews on their products. Consequently, detection of opinion spam actually becomes more and more big concern to protect online opinions, to gain consumer trust and to maintain companies' fair competition. For this reason, in the last years, several methods have been proposed trying to distinguish between the trustful and deceptive reviews. All the first studies rely on the review content using the linguistic aspects and feeling as well as readability and subjectivity [START_REF] Deng | Sentiment analysis based online restaurants fake reviews hype detection[END_REF]. Moreover, other techniques based on the individual words extracted from the review text as features [START_REF] Jindal | Opinion spam and analysis[END_REF], while some others are based on the syntactic and lexical features. It is important to mention that most of the methods based only on the review content can not successfully detect fake reviews cause of the lack of any distinguishing words that can give a definitive clue for classification of reviews as real or fake. Accordingly, detecting spammers can improve spotting spam review, since spammers generally share the same profile history and activity patterns. Hence, we notice the existing of various spammer detection methods in which the graph-theory have been used and most of them have shown promising results [START_REF] Wang | Review graph based online store review spammer detection[END_REF]. Moreover, other methods [START_REF] Fei | Exploiting burstiness in reviews for review spammer detection[END_REF][START_REF] Lim | Detecting product review spammers using rating behaviors[END_REF][START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF] are based on the different features extracted from the reviewer characteristics and behavioral. Furthermore, relying on both spam review detection and spammer detection when analyzing their behaviors is more effective solution for detecting review spam than either approach alone. In this way, we mention works in [START_REF] Fontanarava | Feature Analysis for Fake Review Detection through Supervised Classification[END_REF][START_REF] Rayana | Collective opinion spam detection: Bridging review networks and metadata[END_REF], that exploit both relational data and metadata of reviewers and reviews. Results prove that this kind of methods outperform all others. Although the fake reviews detection is an uncertain problem, no one of these previous works is able to manage uncertainty in the reviews. However, we have proposed some preliminary related works dealing with the uncertainty [START_REF] Ben Khalifa | Fake reviews detection under belief function framework[END_REF][START_REF] Ben Khalifa | Multiple criteria fake reviews detection using belief function theory[END_REF] but these approaches rely only on the review information. In this paper, we propose a novel approach that distinguishes between fake and genuine reviews while dealing with uncertainty in both the review and the reviewer information. As some reviewers prefer judge services or products through different evaluation criteria, our method deals with the different review rating criteria and analyzes the reviewers behaviors under the belief function framework, chosen thanks to its flexibility in representing and managing different types of imperfection. The rest of this paper is organized as follows: In Section 2, we remind the basic concepts of the belief function theory. Then, we elucidate our proposed approach in Section 3. Section 4 discusses the experimental study. Finally, we conclude in Section 5.

Belief Function Theory

The belief function theory is one of the useful theories that handles uncertain knowledge. It was introduced by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] as a model to manage beliefs. The frame of discernment Ω is a finite and exhaustive set of different events associated to a given problem. 2 Ω is the power set of Ω that contains all possible hypotheses. A basic belief assignment (bba) or a belief mass is defined as a function from 2 Ω to [0, 1] that represents the degree of belief given to an element A such that:

-The certain bba represents the state of total certainty and it is defined as follows: m Ω ({ω i }) = 1 and ω i ∈ Ω. -Simple support function: In this case, the bba focal elements are {A, Ω}. A simple support function is defined as the following equation:

m Ω (X) =      w if X= Ω 1 -w if X = A for some A ⊂ Ω 0 otherwise ( 1
)
where A is the focus and w ∈ [0,1].

Moreover, the discounting operation [START_REF] Ling | Combining opinions from several experts[END_REF] allows us to update experts beliefs by taking into consideration their reliability through the degree of trust (1 -α) given to each expert with α ∈ [0, 1] is the discount rate. Accordingly, the discounted bba, noted α m Ω , m Ω becomes:

α m Ω (A) = (1 -α)m Ω (A) ∀A ⊂ Ω, α m Ω (Ω) = α + (1 -α)m Ω (Ω).
(

) 2
Several combination rules have been proposed in the framework of belief function to aggregate a set of bba's provided by pieces of evidence from different experts. Let m Ω 1 and m Ω 2 two bba's modeling two distinct sources of information defined on the same frame of discernment Ω. In what follows, we elucidate the combination rules related to our approach.

1. Conjunctive rule: It was settled in [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF], denoted by ∩ and defined as:

m Ω ∩ (A) = m Ω 1 ∩ m Ω 2 (A) = B∩C=A m Ω 1 (B)m Ω 2 (C), ∀B, C ⊆ Ω 2.
Dempster's rule of combination: This combination rule is a normalized version of the conjunctive rule [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. It is denoted by ⊕ and defined as:

m Ω ⊕ (A) = m Ω 1 ⊕ m Ω 2 (A) = m Ω 1 ∩ m Ω 2 (A) 1-m Ω 1 ∩ m Ω 2 (∅) if A = ∅, ∀A ⊆ Ω, 0 otherwise. (3)
3. T he combination with adapted conf lict rule (CW AC): This combination [START_REF] Lefèvre | How to preserve the confict as an alarm in the combination of belief functions?[END_REF] is an adaptive weighting between the two previous combination rules acting like the conjunctive rule if bbas are opposite and as the Dempster rule otherwise. They use the notion of dissimilarity that is obtained through a distance measure, to ensure this adaptation between all sources.

The CWAC is formulated as follows:

m Ω ↔ (A) = (↔ m Ω i )(A) = D max m Ω ∩ (A) + (1 -D max )m Ω ⊕ (A) (4)
where D max is the maximal value of all the distances, it can be used to find out if at least one of the sources is opposite to the others and thus it may be defined by:

D max = max[d(m Ω i , m Ω j )] where i ∈ [1, M ], j ∈ [1, M ],
M is the total number of mass functions and d(m Ω i , m Ω j ) is the distance measure proposed by Jousselme [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF]:

d(m Ω 1 , m Ω 2 ) = 1 2 (m Ω 1 -m Ω 2 ) t D(m Ω 1 -m Ω 2 )
, where D is the Jaccard index defined by:

D(E, F ) = 1 if E = F = ∅, |E∩F | |E∪F | ∀E, F ∈ 2 Ω \∅
Frequently, we need to fuse two bba s m Ω1 1 and m Ω2 2 that have not the same frame of discernment. So, we apply the vacuous extension of the belief function which extend the frames of discernment Ω 1 and Ω 2 , corresponding to the mass functions m Ω1 1 and m Ω2 2 , to the product space Ω = Ω 1 × Ω 2 . The vacuous extension operation, denoted by ↑ and defined such that:

m Ω1↑Ω1×Ω2 (B) = m Ω1 (A) if B = A × Ω 2 where A ⊆ Ω 1 , B ⊆ Ω 1 × Ω 2 . It transforms each mass to the cylindrical extension B to Ω 1 × Ω 2 .
To determine relation between two disjoint frames of discernment Ω 1 and Ω 2 , the multi-valued mapping may be used. This operation denoted τ , allows us to join together two different frame of discernment the subsets B ⊆ Ω 2 that can match through τ to be a subset

A ⊆ Ω 1 : m Ω1 τ (A) = τ (B)=A m Ω2 (B)
The belief function framework offers various solutions to ensure the decision making. We present the pignistic probabilities, used in our work, denoted by BetP and defined as:

BetP (B) = A⊆Ω |A∩B| |A| m Ω (A) (1-m Ω (∅)) ∀ B ∈ Ω.

Multiple criteria fake reviews detection based on spammers' indicators within the belief function theory

In this following section, we elucidate our novel approach which aims to detect fake reviews. Our method relies on both the reviews and the reviewers information, since gathering behavioral evidence of spammers in more efficient than just identifying review spam only. Moreover, our proposed approach is divided on three parts: Firstly, we deal with the ratings given to various evaluation criteria, to judge a service or a product, in order to determine the reviewers' opinion trustfulness through their degree with compatibility with all others' opinions, this part is based on our previous work in [START_REF] Ben Khalifa | Multiple criteria fake reviews detection using belief function theory[END_REF]. Secondly, trying to obtain more preferment detection, we propose to rely on an other previous work in which we model the reviewers' trustworthiness by analyzing the reviewers' behaviors [START_REF] Ben Khalifa | Spammers detection based on reviewers' behaviors under belief function theory[END_REF].

For that, we adopt the belief function theory to handle uncertainty in the various imprecise reviews and the imperfect reviewers' information. To enhance the detection performance, we combine both the reviewer opinion and the reviewer trustworthiness modeling by mass functions in the third part. These three parts are detailed in the following subsections in which we consider a dataset of N reviewers and q evaluation criteria. Each reviewer R i evaluates a product or a service by giving a rating vote between 1 and 5 stars to each criterion C j .

Modeling the reviewer's opinion trustworthiness

Considering the rating reviews given to different evaluation criteria as inputs, where each vote V ij provided to each criterion C j where j in {1...q} and q the number of evaluation criteria. Therefore, we propose to model uncertainty in these rating reviews by representing each vote into mass function m Ωj ik with Ω j ={1, 2, 3, 4, 5} where each element represents the rating number given by each reviewer R i .

Modeling the uncertain opinion

We think that the reviewer gives always imprecise vote to one value close. Hence, we model this uncertainty by considering, the vote, the vote+1, the vote-1 denoted k, for each rating review (i.e vote) given to each criterion. Hence, we transform the uncertain vote into a mass functions (i.e bba s) such that:

m Ωj ik ({k}) = 1 where k ∈ {V i , V i+1 , V i-1 }.
Then, we propose to take into consideration the reliability degree of each vote V ij based on its similarity with all others' vote provided to the same criterion C j . We also take into account the difference between the vote given by the reviewer and these modeled values ({V i , V i+1 , V i-1 }) denoted by k. For this we apply double discounting in which we transform the mass functions on simple support system. After that, we aggregate the discounted bba representing the given vote using the Dempster rule (Eq.3) in order to model each uncertain vote given to each criterion by one global mass function m Ωj i with i = 1, . . . , N and j = 1, . . . , q. Moreover, we propose to model the whole reviewer's opinion in one joint bba, for that we have to apply the following steps:

-Creating Ω c as the global frame of discernment relative to all criteria which represents the cross product of the different frames Ω j denoted by:

Ω c = Ω 1 × Ω 2 × . . . × Ω q . -Extending the different bba s m Ωj i
to the global frame Ω c to get new bba s m Ωj ↑Ωc i .

-Combining the extended bba s using the Dempster rule of combination.

m Ωc i = m Ω1↑Ωc i ⊕ m Ω2↑Ωc i ⊕ . . . ⊕ m Ωq↑Ωc i
. This bba represents the reviewer's opinion given by the different rating review criteria.

Measure the compatibility between the reviewer opinion and all the others' one

In order to evaluate the opinion provided by each reviewer R i through various criteria C j , we compare it with all others reviewers' opinions. For that, firstly we aggregate all the others review rating given to the same criterion using the CWAC combination rule to obtain one bba, modeling the whole rating reviews given each criterion except the current one. As a consequence, we obtain q (number of evaluation criterion) bba s m Ωj ic . Thus, we combine them to model all reviewers' opinions except the current one in one joint bba. To achieve this, we firstly extend them to the global frame of criteria Ω c to get m Ωj ↑Ωc ic . After that, we aggregate the extend bba s through the Dempster rule of combination. Subsequently, for each reviewer we measure the distance between his provided opinion modeled by m Ωc i and all the others reviewers' opinions represented by m Ωc ic using the distance of Jousselme.

Modeling the reviewer opinion into trustful or not trustful

Since the calculated distance elucidates the average opinion rating deviation from the other reviewers' opinion which one of the most important spam indicator. That's why, more the distance decreases more the given opinion is considerate as trustful. Thus, we propose to transform each distance into new bba under Θ = {t, t) (t for trustful and t for not trustful). In this part, we successfully model the whole reviewers' opinion trustworthiness by mass function m Θ i under the frame of discernment Θ = {t, t}.

Modeling the reviewer spamicity

The average rating deviation from the others rating is considerate as an important indicators in spam review detection field. Despite that, spammers try to mislead readers and the usually post a lot of despite reviews to dominate the majority of the given opinions. Accordingly, it is essential to have recourse to the reviewers' spamicity in order to reinforce the spam reviews detection. In this way, we propose to model uncertainty in the different reviewers information while relying on the spammers indicators. We represent each reviewer R i by two mass functions namely; the reviewer reputation m Ω S RRi and the second one is to model the reviewer helpfulness m Ω S RHi with Ω S = {S, S} where S is spammer and S is not spammer.

Modeling the reviewer reputation

Usually, the innocent reviewers post their opinion when they have already bought new products or used new services. Therefore, their reviews are generally dispersed over time interval and depend on the number of used products or services. However, the spammers post enormous reviews to some particular products in short interval, two or three days (more used in the spammer review detection field), to overturn the majority of the given reviews. Consequently, we construct the reviewer reputation through these two spammers' indicators. Hence, we propose to check the reviewing history of each reviewer Hist Ri contained all past reviews given by each reviewer R i to n discrete products or services. Each reviewer average proliferation is calculated as follows:

AvgP (R i ) = Hist R i n
We assume that if AvgP (R i ) > 3, the reviewer is considered as a potential spammer since generally ordinary reviewers do not give more than three reviews per product [START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF]. Accordingly, the reviewer reputation is then represented by a certain bba as follows:

m Ω S RRi ({S}) = 1 else m Ω S RRi ({S}) = 1
Moreover, we check if the reviews are given in a short time of interval or are distributed all along the reviewing history.

For that, we measure the brust spamicity degree denoted δ i to weaken each reviewer reputation bba by its corresponding reliability degree using the discounting operation. Consequently, we find the discounted bba δi m Ω S RRi which presents the reviewer reputation based on both the reviewer's average proliferation and the brust spamicity.

Modeling the reviewer helpfulness

The reviewer helpfulness is considerate as important spammer indicators. Thus, we extract the Number of Helpful Reviews (N HR) associated to each reviewer in order to check if the reviewer post helpful reviews or unhelpful one to mislead readers. Hence, if the reviewer is suspicious to be spammer (N HR i = 0), thus we model the reviewer helpfulness by a certain bba as follows:

m Ω S RHi ({S}) = 1 else m Ω S RHi ({S}) = 1
We weaken the reviewer helpfulness mass by the non helpfulness degree for each reviewer R i denoted by λ i in order to not treat all the reviewers who give helpful reviews in the same way. Thus, we apply the discounting operation in order to transform the bba into a simple support function λi m Ω S RHi to take into consideration the helpfulness degree. Moreover, spammers usually post extreme ratings [START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF], either highest (5 stars) or lowest (1 star), in order to achieve their objective and dominate the average rating score of products or services. Nonetheless, the innocent reviewers are always not fully satisfied or dissatisfied by the tried products and services. Thus, they not usually post extreme rating. Hence, despite the fact that the reviewer has helpful reviews if they are crowded with extreme rating, his probabilities of being genuine reviewer will assuredly reduce. In order to take this indicator into consideration, we calculate the extreme rating degree denoted γ i , corresponding to each reviewer R i , which is considered as the discounting factor. Then, we weakened an other time the reviewer helpfulness λi m Ω S RHi by its relative reliability degree using the discounting operation. Thus, the obtained discounted λi γi m Ω S RHi modeled the reviewer helpfulness based on both the reviewer helpfulness degree and extreme rating which are an important spammers' indicators.

Combining the both reviewer reputation and helpfulness

With the purpose of representing the whole reviewer trustworthiness. We combine the reviewer bba's reputation δi m Ω S RRi with his helpfulness bba λi γi m Ω S RHi using the Dempster rule of combination under the frame of discernment Ω S . The joint resultant bba m Ω S RTi illustrates each reviewer's the trustworthiness degree.

Distinguishing between the fake and the genuine reviews

As highlighter before, relying on both spam review and spammer review detection become the most effective solution to spot deceptive reviews. For this reason, we combine both the reviewer's opinion trustworthiness modeled by m Θ i with the reviewer spamicity represented by m Ω S RTi in order to make a powerful decision. For doing so, we apply the following steps.

Modeling both the reviewer and his giving opinion trustworthiness

In the interest of modeling both the reviewer and his opinion trustworthiness in one joint bba, we deal with the following steps: First of all, we define the global frame of discernment relative to the reviewer and his opinion trustworthiness. It represents the cross product of the two different frame Θ and Ω S denoted by: Ω RR = Θ × Ω S . Then, we extend all the mass functions m Θ i and m Ω S RSi to the global frame of discernment Ω RR using the vacuous extension in order to get new bba s m Θ↑Ω RR i and m Ω S ↑Ω RR RSi . Finally, we combine these extended bbas using the Dempster combination rule

m Ω RR i = m Θ↑Ω RR i ⊕ m Ω S ↑Ω RR

RSi

to get the joint bba m Ω RR i that represents both the reviewer and his given opinion trustworthiness.

Reviewer and his opinion trustworthiness transfer

In following step, we transfer the m Ω RR i under the product space Ω RR to the frame of discernment Θ D = {f, f } to make decision by modeling the reviewer opinion into fake or not fake. In spam reviews detection field, all the reviews given by the spammers are considered as fake opinion reviews, because spammers are not real consumers and they try sometimes to post reviews compatible with the provided one to avoid being detected by the spam detection methods. For that, a multi-valued operation, denoted τ is applied. The function τ : Ω RR to 2 Θ D rounds up event pairs as follows:

-Masses of pairs that contain at least an element {S} spammer are transferred to fake f ⊆ Θ D as:

m τ ({f }) = τ (SR i )=f m Ω RR i (SR i ), (SR i = A × S) ⊆ Ω RR
-Masses of pairs including at least an element { S} not spammer are transferred to not fake f ⊆ Θ D such that:

m τ ({ f }) = τ (SR i )= f m Ω RR i (SR i ), (SR i = A × S) ⊆ Ω RR
-Masses of event couples with no element in {S, S} are transferred to Θ D as:

m τ (Θ D ) = τ (SR i )=Θ D m Ω RR i (SR i ), (SR i = A × Ω S ) ⊆ Ω RR

Decision making

Finally, we apply the pignistic probability BetP in order to distinguish between the fake and the genuine opinion. Hence, the BetP with the grater value will be considered as the final decision.

Experimentation and Results

Experimentation tools

In our method, we conduct two real datasets collected and used in [START_REF] Mukherjee | What Yelp Fake Review Filter Might Be Doing[END_REF][START_REF] Rayana | Collective opinion spam detection: Bridging review networks and metadata[END_REF] from yelp.com. These datasets are considered as the largest, richest, complete and only labeled datasets in the spam review research. These datasets offer the nearground-truth since they are labeled through the yelp filter classifier, which has been used in many previous works [START_REF] Fontanarava | Feature Analysis for Fake Review Detection through Supervised Classification[END_REF][START_REF] Mukherjee | What Yelp Fake Review Filter Might Be Doing[END_REF][START_REF] Rayana | Collective opinion spam detection: Bridging review networks and metadata[END_REF] as a ground truth thanks to its efficient detection method based on several behavioral features, where recommended (Not filtered) reviews correspond to genuine reviews, and not recommended (filtered) reviews correspond to fake ones. Due to the huge number of reviews, we random sample the two datasets with 10% from the total number of reviews given to three different evaluation criteria (services, cleanliness and food quality). Table 1 introduces the datasets and indicates the ratio of (filtered) fake reviews (and consequently reviewers). Furthermore, we evaluate our method through the three following criteria: accuracy, precision and recall.

Experimental results

As our method proposes a specific classifier able to differentiate between fake and genuine reviews given to overall or multiple evaluation criteria under an uncertain context. We propose to compare it with the state-of-art baselines classifiers; the Support Vector Machine (SVM) and the Naive Bayes (NB) used by most of the spam detection methods [START_REF] Fei | Exploiting burstiness in reviews for review spammer detection[END_REF][START_REF] Lim | Detecting product review spammers using rating behaviors[END_REF][START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF][START_REF] Mukherjee | What Yelp Fake Review Filter Might Be Doing[END_REF]. In order to maintain safe comparison when applying the SVM and NB classifiers, we construct a balancing data (50% of fake reviews and 50% of genuine ones) extracted from our datasets (YelpZip and YelpNYC) to avoid the over-fitting, then we divided into 30% of testing set and 70% of training set and we use the features considered in our proposed method; the rating deviation, the reviewers average proliferation, the brust spamicity degree, the reviews helpfulness and the extreme rating providing by each reviewer. In addition, the final estimation of each evaluation criterion is obtained by averaging ten trials values using 10-Fold cross validation technique. Furthermore, we compare our method with the proposed uncertain classifier Multiple Criteria Belief Fake Reviews Detection (MC-BFRD) [START_REF] Ben Khalifa | Multiple criteria fake reviews detection using belief function theory[END_REF] which relies only on the review rating information. The results are reported in the Table 2.

Our method attends the highest performance detection according to accuracy, precision and recall over-passing the baseline classifier. It reaches an accuracy improvement until 14% with yelpZip and until 10% with yelpNYC data-set compared to SVM. Moreover, the improvement records between the two uncertain classifier (over 20%) confirms the importance of combining both the review and the reviewer features while considering the spammers' indicators in this field. Despite the fact that our approach is based on fewer indicators than yelp's filter classifier, we obtain competitive results (over 92%) thanks to our method ability in handling uncertainty within the different inputs. These encouraging results push us to integrate more behavioral features in our future work that we could improve our results and obtain identical or even better performance than yelp filter.

Conclusion

The spam review is an actual big issue threaten the online reviews. To tackle this problem, we have propose a specific classifier able to deal with uncertainty in the multi-criteria rating reviews and in the reviewer information while analyzing them through the spammers indicators. Our proposed method shows performance in classifying the fake and the innocent reviews while testing with two real data-sets form yelp.com.

Table 1 .

 1 Datasets description

	Datasets	Reviews (filtered %)	Reviewers (Spammer %)	Services (Restaurant or hotel)
	YelpZip 608,598 (13.22%) 260,277 (23.91%)	5,044
	YelpNYC 359,052 (10.27%) 160,225 (17.79%)	923

Table 2 .

 2 Comparative results

	Evaluation Criteria	Accuracy			Precision			Recall
	Methods NB SVM	MC BFRD	Our method	NB SVM	MC BFRD	Our method	NB SVM	MC BFRD	Our method
	YelpZip	64% 78% 70% 91.5% 62% 80% 74% 95%	64% 75% 72.78% 90.1%
	YelpNYC 65% 82.5% 75% 92.77% 65% 86% 83% 96%	70% 84% 80%	91.2%