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

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Managing uncertainty during CBR systems vocabulary maintenance using Relational Evidential C-Means

Due to the incremental learning of Case-Based Reasoning (CBR) systems, there is a colossal need to maintain their knowledge containers which are (1) the case base, (2) similarity measures, (3) adaptation, and (4) vocabulary knowledge. Actually, the vocabulary presents the basis of all the other knowledge containers since it is used for their description. Besides, CBR systems store real-world experiences which are full of uncertainty and imprecision. Therefore, we propose, in this paper, a new policy to maintain vocabulary knowledge using one of the most powerful tools for uncertainty management called the belief function theory, as well as the machine learning technique called Relational Evidential C-Means (RECM). We restrict the vocabulary knowledge to be the set of features describing cases, and we aim to eliminate noisy and redundant attributes by taking into account the correlation between them.

Introduction

Case-Based Reasoning (CBR) is a methodology based on solving new problems using past experiences. Actually, each new target problem triggers an entire cycle; In a nutshell, the CBR system (a) retrieves from the Case Base (CB) the most similar case(s). Then, it (b) reuses that case so as to propose an adapted solution. However, this solution can be rejected, so it should be (c) revised. Finally, the confirmed solution with its corresponding problem will be retained in the CB to serve, as a new case, for future problems resolution [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF] (see Figure 1).

Since CBR systems proved over the years a widespread interest in several domains, and since they are designed to work over long time frames, their Knowledge Containers (KC) [START_REF] Richter | Knowledge containers. Readings in Case-Based Reasoning[END_REF] are now the subject of a considerable maintenance targets. There are four KCs in CBR systems: (1) CB, (2) Vocabulary, (3) Similarity measures and (4) Adaptation rules. Their maintenance turns around the field of Case-Based Reasoner Maintenance (CBRM) [START_REF] Wilson | Maintaining Case-Based Reasoners: Dimensions and Directions[END_REF]. In fact, research are maily focused on Case Base Maintenance (CBM) [START_REF] Smiti | SCBM: soft case base maintenance method based on competence model[END_REF], [START_REF] Ben Ayed | ECTD: evidential clustering and case types detection for case base maintenance[END_REF], [START_REF] Ben Ayed | DETD: Dynamic Policy for Case Base Maintenance Based on EK-NNclus Algorithm and Case Types Detection[END_REF], [START_REF] Smiti | WCOID-DG: An approach for case base maintenance based on Weighting, Clustering, Outliers, Internal Detection and Dbsan-Gmeans[END_REF], [START_REF] Ben Ayed | Exploiting Domain-Experts Knowledge Within an Evidential Process for Case Base Maintenance[END_REF] as well as models to estimate CBs competence in problem solving [START_REF] Ben Ayed | CEC-Model: A New Competence Model for CBR Systems Based on the Belief Function Theory[END_REF], [START_REF] Smyth | Modelling the competence of case-bases[END_REF]. However, there is no deep ex-Figure 1. The CBR cycle ploration on maintaining the vocabulary container although it presents the basis of all the other knowledge containers [START_REF] Richter | Knowledge containers. Readings in Case-Based Reasoning[END_REF]. Actually, it needs maintenance for different reasons like context modification and domain overfitting. The most prevalent structure of vocabulary knowledge within CBR is the attribute-value representation [START_REF] Richter | Knowledge containers. Readings in Case-Based Reasoning[END_REF]. Otherwise, other structures may be used such as predicates, set of words, and related constructed. In this work, we present the vocabulary knowledge as the set of features describing cases. Hence, it is relevant to maintain them by keeping only those that improve the competence of CBR systems in problemsolving. Generally, there are two kinds of knowledge that researchers aim to eliminate during maintenance: noisiness and redundancy. Noisy attributes present feature's knowledge that distorts problems solving operations. Redundant attributes have no added-value in offering accurate solutions, and their elimination will improve the performance of the CBR system.

To select relevant features, Attribute Clustering concept [START_REF] Ben Ayed | Maintaining case knowledge vocabulary using a new Evidential Attribute Clustering method[END_REF], [START_REF] Hong | Attribute clustering in high dimensional feature spaces[END_REF], [START_REF] Maji | Fuzzyrough supervised attribute clustering algorithm and classification of microarray data[END_REF] has proved high adequacy in CBR context since it allows to maintain the relation between features, as well as providing a flexibility in term of features substitution. Most of vocabulary maintenance policies are hard i.e they are not able to manage uncertainty within knowledge. Undoubtedly, there is a crucial need to handle imperfection within CBR systems since embedded knowledge refer to real-world experiences, which are generally uncertain and imprecise. Belief function theory or Evidence 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] presents one of the most powerful tools for that matter. Some evidential clustering techniques such as k-evclus and EVCLUS [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF], [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF], have been used in [START_REF] Ben Ayed | Maintaining case knowledge vocabulary using a new Evidential Attribute Clustering method[END_REF] and [START_REF] Ben Ayed | CEVM: Constrained Evidential Vocabulary Maintenance Policy for CBR Systems[END_REF] for features learning. However, other techniques [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] within this theory have been proposed and showed their effectiveness. Therefore, we aim, in this paper, to propose a new policy for vocabulary knowledge maintenance based on assessing the relation between features through correlation measurement and using the Relational Evidential C-Means (RECM) [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] as a machine learning technique. We also aim to show results offered by our policy and compare them to policies using other methods, as well as to the original non-maintained CBR.

The rest of the paper is organized as follows. The next Section defines the vocabulary container, overviews applicable notions for vocabulary maintenance, and present some related works. Section 3 presents tools and fundamental concepts of the belief function theory. During Section 4, we describe in details our proposal for maintaining vocabulary maintenance. Results will be discussed in Section 5. Finally, we end by concluding within Section 6.

Maintaining knowledge within CBR systems

As already mentioned, CBR systems contain different varieties of knowledge that are stored in four knowledge containers, which are Case Base, Similarity measures, Adaptation knowledge, and Vocabulary. These knowledge needs maintenance along the time on account of appearance of noisiness and redundancy as well because context change (see Figure 2).

Before moving and focusing on the literature of vocabulary knowledge and its maintenance to introduce our contribution, for the current work, let briefly present the other three knowledge containers within CBR systems.

Case Base Maintenance. Firstly, to maintain the CB knowledge container which defines the set of stored experiences, we find, in the literature, several policies that are based on different strategies to maintain cases such as:

1) The selection based strategy which contains CBM policies that revise CB's content through the selection of only representative cases that are able to cover the remaining set of cases problems. For instance, the Condensed Nearest Neighbor (CNN) [START_REF] Hart | The condensed nearest neighbor rule[END_REF] presents the baseline of data reduction methods. 2) The optimization based strategy which contains policies that apply maintenance operations according to some evaluation criteria such that:

•

The performance which is quantified by the time spent to solve a target problem,

•

The competence which represents the range of problems that the CB can successfully solves [START_REF] Smyth | Competence models and the maintenance problem[END_REF] Among that policies, Iterative Case Filtering algorithm (ICF) [START_REF] Brighton | On the consistency of information filters for lazy learning algorithms[END_REF] is based on the competence criterion to make decision about cases deletion.

3) The partitioning based strategy which is characterized by giving the ability of treating the original CB in form of small ones, which makes it easier and more effective. Generally, the different subsets of cases are obtained using the clustering as an unsupervised machine learning technique. Actually, cases clustering is widely used within the CBM field due to its approved utility in detecting cases to be maintained. For instance, Evidential Clustering and case Types Detection for case base maintenance method (ECTD) [START_REF] Ben Ayed | ECTD: evidential clustering and case types detection for case base maintenance[END_REF] performs cases evidential clustering technique and, then, selects only cases that their deletion affects the whole CB quality. Some variants of ECTD policies have also been proposed [START_REF] Ben Ayed | DETD: Dynamic Policy for Case Base Maintenance Based on EK-NNclus Algorithm and Case Types Detection[END_REF], [START_REF] Ben Ayed | Exploiting Domain-Experts Knowledge Within an Evidential Process for Case Base Maintenance[END_REF].

Similarity Maintenance. Secondly, Similarity measures are mainly used in CBR during the Retrieve step1 . In the literature, there are several works focusing on the maintenance of similarity, and especially on learning features weighting in similarity measures [START_REF] Stahl | Using evolution programs to learn local similarity measures[END_REF], [START_REF] Stahl | Learning similarity measures: A formal view based on a generalized CBR model[END_REF]. According to authors in [START_REF] Richter | Case-Based Reasoning[END_REF], there are three main maintenance operations if we limit ourselves to weighted linear measures: modify a weight, modify a local measure, and stretch out a measure to a new attribute.

Case Base

Adaptation Maintenance. Thirdly, within this adaptation maintenance area, research has to be so careful in adaptation changes. In fact, a low-quality maintenance may extremely influence the performance of the CB, and consequently the whole CBR system.

Handling adaptation rules is a very intensive knowledge. Consequently, we generally appeal domain-experts interventions for this matter. Nevertheless, there are different works in the context of adaptation learning and maintenance. For instance, an automated mechanism has been proposed in [START_REF] Leake | Acquiring case adaptation knowledge: A hybrid approach[END_REF] to learn some adaptation rules from the different observations in the CB: If descriptions of two cases vary in just few number of features, the core of the adaptation rule is then formed from the differences in those features. Other works are also carried out in this area such that [START_REF] Jarmulak | Using case-base data to learn adaptation knowledge for design[END_REF], [START_REF] Craw | Learning and applying case-based adaptation knowledge[END_REF]. Let us mention that, according to [START_REF] Wilke | Techniques and knowledge used for adaptation during case-based problem solving[END_REF], there are four types of adaptations that can be applied inside CBR systems: 1) Null Adaptation2 : It consists on returning the similar case solution without any modification, 2) Transformational Adaptation: It applies a modification in some parts of the solution description, 3) Generative Adaptation: It generates a solution from scratch. 4) Compositional Adaptation: It combines the three previous types to obtain the reused solution.

Vocabulary Maintenance. According to authors in containers [START_REF] Roth-Berghofer | Mapping goals and kinds of explanations to the knowledge containers of case-based reasoning systems[END_REF], and as shown in Figure 3, the vocabulary is presented as the basis of all the other knowledge. During this Section, we define the vocabulary and the reason of maintenance, along with mentioning some related work and applicable concepts for maintenance.

The need of vocabulary knowledge maintenance

Obviously, there is a need to maintain all knowledge containers within CBR systems since they are designed to work for a long period of time. For instance, let assume that we possess a CBR system with high competence and performance. After a period of time, we may encounter noisy and redundant knowledge as well as some context changes. Hence, the system will know some weaknesses and degradation of competence and/or performance.

In this paper, we are focusing only on maintaining the set of features. In fact, every experience, in our life, can be described with unlimited number of features, where only some of them are considered as representative and able to direct the best solution. Generally, two kinds of features should be removed; noisy attributes which overwrite the smooth learning, and redundant ones which slow CBR system's operations.

Applied concepts for vocabulary maintenance

To maintain CBR vocabulary knowledge, different concepts within the machine learning field have been applied. Among the most used ones for this matter, we cite feature selection and attribute clustering.

Firstly, since we work with structured CBR systems and aim to retain only relevant attributes, the field of Feature Selection (FS) is suitable for such problem. FS is a NP-Hard problem that aims to select only relevant attribute, for some data, that do not contribute to the predictive model's accuracy. Hence, we note some FS methods that have been combined with CBR vocabulary maintenance context [START_REF] Arshadi | Feature Selection for Improving Case-Based Classifiers on High-Dimensional Data Sets[END_REF], [START_REF] Zhu | An integrated feature selection and cluster analysis techniques for case-based reasoning[END_REF], and others that select attributes through allocating weights according to features significance [START_REF] Kononenko | Estimating attributes: analysis and extensions of RE-LIEF[END_REF].

Secondly, the Attribute Clustering (AC) is a suitable way that could be used to maintain vocabulary within CBR context. In fact, AC allows to preserve relation between features which offers a high flexibility to CBR framework since each attribute could be substituted by another one belonging to the same cluster. Consequently, AC has been used in some works [START_REF] Hong | Attribute clustering in high dimensional feature spaces[END_REF], [START_REF] Maji | Fuzzy-rough supervised attribute clustering algorithm and classification of microarray data[END_REF] as a feature selection method for vocabulary maintenance [START_REF] Ben Ayed | Maintaining case knowledge vocabulary using a new Evidential Attribute Clustering method[END_REF].

The concept of AC is similar to objects clustering where similar objects should belong to the same cluster, and inversely. However, similarity between attributes is described in term of relation between them, such as correlation or dependency, which is generally depending on the task objective.

To manage uncertainty within knowledge, from the complete ignorance to the total certainty, we choose to use tools from 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], as presented in the following Section.

Belief function theory

Since our work, elaborated in this paper, aims to manage knowledge imperfection which is naturally embedded within real-world experiences stored in CBR systems, some tools and techniques from the belief function theory are used, in this work, to allow a high-quality vocabulary maintenance. During this Section, the fondamental concepts of the belief function theory, which is named also Demspter-Shafer or Evidence 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], are presented. Besides, the concept of credal partition within the evidential clustering is defined to model the doubt about features assignment to clusters.

Fundamental Concepts

To model and quantify the evidence under the belief function framework, let consider ω a variable that refers to C elementary events for some problem presented by Ω = {ω 1 , ω 2 , ..., ω C }. We call the Ω set by the frame of discernment and the set of all the 2 C possible subsets of the predefined events taking values in Ω by the power set. The power set is therefore defined as follows:

2 Ω = {∅, {ω 1 }, ..., {ω C }, {ω 1 , ω 2 }, ..., {ω 1 , ω C }, ...., Ω} (1)
The main key point of this theory is called the basic belief assignment (bba) which refers to the partial knowledge regarding the real value of ω. It is defined by the following function:

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

B⊆Ω m(B) = 1 (3)
We call an element The basic belief mass m(B), which presents the degree of belief assigned to the hypothesis "ω ∈ B", can be attached to a subset of variables regardless any additive assumption. A bba corresponds to the open world assumption when we allow the assignment of evidence to the empty set partition. That means that Ω is incomplete and the actual value may be taken outside the frame of discernment. This interpretation is meaningful especially in clustering when we aim to distuinguish noisy knowledge [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF], [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF]. Contrariwise, if the bba is normalized (m(∅) = 0), then it corresponds to the closed-world assumption [START_REF] Shafer | A mathematical theory of evidence[END_REF]. If we are interested to move on from unnormalized (m(∅) = 0) to normalized (m(∅) = 0) bba, then the Dempster Normalization can be applied, which consists on dispersing the belief's degrees assigned to the empty set over all the other focal sets such that:

m * (B) =    m(B) 1 -m(∅) if B = ∅ 0 Otherwise (4)
Some useful functions are generally computed through the bba for some reason. For instance, for a given bba m, the corresponding belief (bel), plausibility (pl) and commonality (q) functions are from 2 Ω to [0, 1] and defined by [START_REF] Shafer | A mathematical theory of evidence[END_REF] as follows:

bel(B) = ∅ =D⊆B m(D) ∀B ⊆ Ω (5)
,

pl(B) = B∩D =∅ m(D) ∀B ⊆ Ω (6)
and

q(B) = B⊆D m(D) ∀BΩ (7)
In other words, the belief function bel(B) represents the total belief that one commits to B without committed to B, the plausibility function pl(B) quantifies the maximum amount of belief that could be given to a subset B and the commonality function q(B) represents the total mass that is free to move to every element of B.

The source of evidence providing bbas are often not fully reliable. Hence, a discounting operation [START_REF] Shafer | A mathematical theory of evidence[END_REF] is necessary to update the bba according to the degree of trust assigned to the source. In fact, the discount rate, denoted α ∈ [0, 1], refers to the amount of belief that expert's information is reliable. The updated bba α m is defined as follows:

α m(B) = (1 -α) m(B) f or B = Ω α + (1 -α) m(Ω)
f or B = Ω (8) Let consider two mass functions m 1 and m 2 defined in the same frame of discernment Ω. Hence, the degree of conflict between them may be computed with various ways. One of the most cummon methods is defined, in [START_REF] Shafer | A mathematical theory of evidence[END_REF], as follows: κ = A∩B=∅ m 1 (A) m 2 (B). Authors, in [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF],

demonstrated that if two mass functions m 1 and m 2 quantify evidence regarding two different questions that take values in the same possible answers Ω, then the plausibility that both questions have the same answer is equal to 1 -κ.

At the end, we generally need to make decision after handling beliefs' degrees. Hence, we present one of the most known tools for decision making called the pignistic probability transformation (BetP ). It consists on choosing the hypothesis, regarding a normalized bba m, having the highest value. BetP is therefore defined as follows:

BetP (ω) = ω∈B m(B) |B| ∀ω ∈ Ω (9)
To be able to apply the BetP transformation within the open world assumption (m(∅) = 0), a prefatory step of normalization (Equation 4) has to be performed.

Credal Partition

Handling imperfection using the evidence theory within the clustering problem has known a widespread interest in several work. The clustering is a machine learning technique that aims to organize data according to the similarity between instances. The more the objects are similar, the more they intend to share the same group.

The key point of the evidential clustering problem is known by the Credal Partition, which is close to the fuzzy partition concept but more general. The credal partition is created by assigning degrees of belief not only to singletons of the frame of discernment, but also to all possible subsets of Ω. Within the evidential clustering, the frame of discernment refers to the set of C possible clusters. The uncertainty towards the membership of an object i to a partition of clusters B is presented by a mass function denoted m i (B). Its value supports the hypothesis saying "The actual cluster of instance i belongs to the partition B". That bba quantifies the uncertainty regarding the membership of only one object. When there is n instances, the credal partition will be the set of n -tuple bbas (m 1 , m 2 , ..., m n ).

For a credal partition M = (m 1 , m 2 , ..., m n ), the two following particular cases are of interest [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] • If every m i is a certain bba, then M presents a crisp partition of the frame of discernment Ω, which corresponds to a complete knowledge situation.

•

If every m i is a Bayesian bba, then M presents a fuzzy partition of the frame of discernment of Ω.

Vocabulary maintaining process using Relational Evidential C-Means (RECM)

To remove noisy and redundant attributes from vocabulary knowledge, our proposed policy follows three principle steps as presented in Figure 4, and referred by three arrows. It is mainly based on the RECM machine learning technique that is able to handle relations between features and manage uncertainty within data.

Step 1: Generating relational matrix through studying the correlation between features

Let define the relation between features inversely proportional to the correlation between them. In fact, we aim to express this relation in term of dissimilarity, where the correlation may refer to the similarity between features. Actually, the more two given attributes are correlated, the more they offer the same information and considered as similar. To measure the linear association between two attributes A i and A j , we use the Pearson's correlation coefficient [START_REF] Pearson | Mathematical contributions to the theory of evolution. III. Regression, heredity, and panmixia[END_REF], which is defined such that:

r AiAj = n l=1 (a il -a i ) (a jl -a j ) n l=1 (a il -a i ) 2 n l=1 (a jl -a j ) 2 (10)
where a il and a jl refer respectively to values of attributes A i and A j regarding case l, where a i and a j present their mean values.

Knowing that r AiAj is bounded in [-1, 1], three main situations arise to define the relational matrix.

• If r AiAj 1,
then there is a high correlation (positive) ⇒ similar provided information ⇒ high similarity.

• If r AiAj -1, then there is a high correlation (negative) ⇒ similar provided information ⇒ high similarity.

• If r AiAj 0, then there is no correlation ⇒ different provided information ⇒ high dissimilarity.

As a consequence, the Relational matrix R is defined as: [START_REF] Roth-Berghofer | Mapping goals and kinds of explanations to the knowledge containers of case-based reasoning systems[END_REF] where p presents the total number of features.

R = (1 -|r AiAj |) i, j = 1..p (

Step 2: Learning on attributes using Relational Evidential C-Means (RECM)

During this step, we aim to consider features as objects and cluster them according to their relational matrix previously generated in order to build clusters, where each one contains similar and correlated attributes. Since knowledge are never exact, we express clusters' membership through degrees of belief. To do, we use a powerful technique for this matter called the Relational Evidential C-Means (RECM) [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF].

RECM [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] is a relational version of the basic Evidential C-Means (ECM) [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF], where both are based on an alternate minimization scheme. However, ECM handles vectorial attribute data and RECM handle dissimilarity data.

Let start by presenting ECM and consider n objects described in p feature space, v i is the center that represents a given cluster c i , and v j is the barycenter that represents the partition of clusters C j with C j ⊆ Ω. To derive the credal

Case Base

Measure the correlation

Conclude the relation

Delete noisiness

Remove redundancy Apply RECM technique

J ECM (M, V ) = n i=1 j/Cj =∅,Cj ⊆Ω |C j | α m β ij d 2 ij + n i=1 δ 2 m β i∅ (12) subject to j/Cj ⊆Ω,Cj =∅ m ij + m i∅ = 1 ∀i = 1...n (13)
where m ij denotes m i (C j ) and ∅ refers to noise cluster [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF], [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF] to be at a fixed distance δ from every instance. The exponent α aims at controlling the penalization degree for partitions having high cardinality, while β and δ treat noisiness.

Firstly, as presented in [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF], V is considered as fix and M is updated as follows:

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

m i∅ = 1 - Cj =∅ m ij ∀i = 1...n (15)
Secondly, M is considered fix, and we obtain an unconstrained optimization problem. The resulted V is defined as the solution of the following equation:

HV = U X ( 16
)
where X represents objects data, and H and U are defined, respectively, as follows: [START_REF] Richter | Case-Based Reasoning[END_REF] with x iq is the value of feature q regarding object o i , For RECM, which is applied in our context, we handle dissimilarity data between features. Hence the notation n with ECM will refer here to the number of features p. Let, in this step, denote the already generated relational matrix R by ∆ = (δ ii ) and consider the square matrix W = (w ii ) referring to dot products of features, which is defined as follows:

H lk = i Cj =∅,Cj ⊇{ω l ,ω k } |A j | α-2 m β ij k, l = 1...C (17) and
U li = Cj ω l |A j | α-1 m β ij l = 1...C i = 1..n
W = - 1 2 J∆J ( 19
)
where J = 1 n ee t -I with e = (1, ..., 1) t ∈ R and I is n × n identity matrix.

Last but not least, let consider the matrix Q = (q kk ) (respectively the matrix Z = (z kk )) the matrix of dot products of centers (respectively the matrix of doc products between centers and instances). As demonstrated in [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF], Z and Q are obtained by solving systems of linear equations toward the following equations respectively:

HZ .i = U W .i , (20)
and

HQ .i = U Z i. (21)
Ultimately, let present, in Algorithm 1, the different steps of RECM technique, as presented in [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF], by making use of the previous defined Equations.

Algorithm 1 RECM algorithm [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] Require: -Dissimilarity data;

-The number of clusters C; -The parameters α, β, δ, and ; Ensure: -The credal partition M ; -Clusters centers V ; 1: BEGIN 2: Randomly generate the initial credal partition M (0) ; 3: Initialization: k ←-0; 4: Calculate W using Equation 19; 5: Repeat 6: k ←-k + 1 7: Calculate H (k) and U (k) from M (k-1) using Equations 17 and 18; 8: For i=1..n 9: Calculate the i th column of Z (k) using Equation 20; 10: End For 11: For i=1..C 12: Calculate the i th column of Q (k) using Equation 21; 13: End For 14: Calculate distances d ij from R (k) and Q (k) ; 15: Update M (k) using Equations 14 and 15; 16: Until ||M (k) -M (k-1) || < 17: END

Step 3: Removing noisy and redundant attributes

To reach our objective, we aim, in this step, to keep only representative features by eliminating noisiness and redundancy. We call noisy features those that have a degree of belief to the empty set higher that all the other degrees. They, hence should be removed since they may gravely reduce the competence of the CBR system to solve problems.

Eliminating redundant features consists on selecting only one representative attribute from every cluster and removing the others. We choose to select the nearest feature to the centre of cluster to which it belongs. The decision of attributes membership to clusters has been made using the pignistic probability transformation as defined in Equation 9.

Illustrative example

Let consider knowledge regarding vocabulary container is defined by the set attributes A i with i goes from 1 to 4. Let assume now that the frame of discernment Ω contains two clusters (ω 1 and ω 2 ) and the applied RECM algorithm offers a credal partion M = [m 1 ; m 2 ; m 3 ; m 4 ], where its values are presented in Table 1. From values given in Table 1, we remark that m 2 (∅) > m 2 ({ω 1 }) + m 2 ({ω 2 }) + m 2 ({ω 1 , ω 2 }). Hence, we flag the feature A 2 as noisy according to specifications given by our policy in step 3. By this way, we refresh the vocabulary knowledge by eliminating A 2 . Thereafter, we make a decision regarding the membership of attributes to clusters using Equation 9and we obtain results as shown in Table 2.

We note that A 1 belongs to ω 1 , and A 3 and A 4 belong to ω 2 . Ultimately, we only retain A 1 as an attribute prototype of ω 1 and A 3 as representative of ω 2 to build the new maintained vocabulary knowledge.

Experimentation and results

The main purpose of our experimentation part is to compare results with those offered when we use other evidential learning tools for vocabulary maintenance, as well as to show the effectiveness degree of our proposal that we call REVM for Evidential Vocabulary Maintenance based on RECM [START_REF] Masson | RECM: Relational evidential c-means algorithm[END_REF] technique.

Data and experimental settings

The different policies and tools, presented in this paper, have been implemented using the R software. The original and the maintained CBR systems are tested using six realworld datasets from UCI repository for machine learning 4 . The description of these datasets are presented in Table 3.

During the implementation of some policies, some parameters should be set. The number of clusters (or features p) used by RECM, for every CB, is fixed similarly to those in [START_REF] Ben Ayed | Maintaining case knowledge vocabulary using a new Evidential Attribute Clustering method[END_REF] with the EVM policy. The initial credal partition is randomly set, and the parameter α regarding the cardinality, within function J RECM , is set to 1 which means that we do not penalize clusters' partitions with high cardinality.

Testing strategy and evaluation criteria

During the evaluation, we make use of the most applied classification algorithm within the CBR context: k-Nearest Neighbor (k-NN) 5 .

Two evaluation criteria have been used, in our work, to assess our proposal efficiency. First, the accuracy criterion consists on measuring the competence of the system in term of the Percentage of Correct Classifications (PCC), and defined such as:

P CC(%) = # Correct classif ications # T otal classif ications × 100 (22)
To obtain final estimation of accuracy, we make use of the 10-fold cross validation technique as shown in Figure 5. Second, we use the retrieval time (RT) criterion which refers to the time spent to retrieve and classify problems by the CBR system.

Results and discussion

As shown in Tables 4 and5, we compare results offered by our proposal that we call REVM, denoting RECM based Evidential Vocabulary Maintenance policy, to those given by the non-maintained CBR system (Original-CBR), by a feature selection method called ReliefF [START_REF] Kononenko | Estimating attributes: analysis and extensions of RE-LIEF[END_REF] (CBR-ReliefF), and by the EVM policy [START_REF] Ben Ayed | CEVM: Constrained Evidential Vocabulary Maintenance Policy for CBR Systems[END_REF] which uses EVCLUS [START_REF] Denoeux | EVCLUS: Evidential clustering of proximity data[END_REF] [START_REF] Denoeux | Evidential clustering of large dissimilarity data[END_REF] for learning.

In term of accuracy, we remark, from Table 4, that RECM method offers competitive results, especially comparing to the non maintained CBR system. In fact, we remark that it was able to improve their initial competence rates provided by Original-CBR with all the tested datasets. For instance, it improves the accuracy of "Yest" dataset from 55.32 % (Original-CBR) to 98.98 % (RECM). Comparing to the feature selection method called reliefF (ReliefF-CBR), we note, also, that RECM offers close results. Ultimately, we note that very competitive results are provided with both EVM and our current proposed method RECM. Actually, we note that they are slightly in favor with the Evidential Vocabulary Maintenance method (EVM) 5. We chose to set k to 5 in order to avoid the sensibility to noisiness. In term of retrieval time, we note that the decreasing of the number of instances as well of features may conduct to decrease the research time, which is described in Table 5 in seconds. We remark that results offered after performing vocabulary maintenance are lower than those offered with the original non maintained CBR systems (Original-CBR). With "Ionosphere", "Breast Cancer", and "Heart" datasets, for instance, we note faster cases retrieval with values go, respectively, from 1.942s to 0.902s, from 1.710s to 0.902s, and from 2.103s to 0.789s. However, we also note very close results with the other ReliefF and EVM maintaining methods, which is logic since they offer data described with close number of features. In fact we would like to mention that, it could be affected by tasks executed in the

Conclusion

In this paper, we used the Relational Evidential C-Means (RECM) as a machine learning technique at the aim to maintain vocabulary knowledge within CBR systems by keeping only representative features. The idea consists on studying, first of all, the relation between features through measuring the correlation between them and create the relational matrix. This matrix will then be used to learn on features with managing uncertainty using RECM. Ultimately, the generated credal partition has been analyzed and studied to retain only representative and relevant features to describe case knowledge. During the experimentation, we tested our proposal on six real datasets from different domains provided in UCI repository for machine learning. Offered results showed some improvement of problemsolving competence comparing to those offered by the non maintained CBR systems. Good results are also noted comparing to the feature selection method called ReliefF. However, we remarked very competitive results with the vocabulary maintenance policy, called Evidential Vocabulary Maintenance (ECM), that uses the EVCLUS technique for learning.

Figure 2 .

 2 Figure 2. CBR knowledge maintenance

Figure 3 .

 3 Figure 3. Illustrating the four knowledge containers within CBR systems

Figure 4 .

 4 Figure 4. Steps of Evidential vocabulary maintenance based on RECM technique

Figure 5 .

 5 Figure 5. The principle of 10-fold cross validation

TABLE 1 .

 1 EXAMPLE OF CREDAL PARTITION VALUES

	M	∅	{ω 1 } {ω 2 }	Ω
	m 1	0.05	0.75	0.15	0.05
	m 2	0.65	0.1	0.1	0.15
	m 3	0.1	0.05	0.8	0.05
	m 4	0.2	0.1	0.5	0.2
	TABLE 2. PIGNISTIC PROBABILITY TRANSFORMATION VALUES
			ω 1	ω 2
		BetP 1	0.8158	0.1842
		BetP 2	0.5	0.5
		BetP 3	0.0833	0.9167
		BetP 4	0.25	0.75

TABLE 3 .

 3 4. https://archive.ics.uci.edu CASE BASES DESCRIPTION

		Case base	Ref # instances	# attributes
	1 Ionosphere	IO	351	34
	2	Glass	GL	214	10
	3	WDBC	BC	569	31
	4	German	GR	1000	20
	5	Heart	HR	270	13
	6	Yeast	YS	1484	8

TABLE 4 .

 4 ACCURACY [PCC(%)]which uses the k-EVCLUS technique for learning. Although there is no high difference between these results (they offer almost same accuracy values for four datasets among six), we conclude that k-EVCLUS was more suitable. It may be explained by its high flexibility to handle different types of similarity or relational data, since our strategy considers them to be in term of correlations between features. However, we may tolerate this fact since our current proposal was able to retain or even largely improve the initial competence values.

			Accuracy [PCC(%)]
	Case bases
		Original-CBR ReliefF-CBR	EVM	REVM
	1 IO	85.48 %	84.88 %	88.33 % 86.98 %
	2 GL	97.64 %	98.11 %	98.59 % 98.12 %
	3 BC	60.16 %	96.33 %	96.46 % 96.18 %
	4 GR	64.6 %	73.4 %	73.25 % 73.26 %
	5 HR	57.5 %	62.45 %	62.98 % 60.91 %
	6 YS	55.32 %	99.05 %	99.05 % 98.98 %

TABLE 5 .

 5 RETRIEVAL TIME [T(S)]

			Retrieval time [T(s)]
	Case bases
		Original-CBR ReliefF-CBR	EVM	REVM
	1 IO	1.942	1.188	0.912	0.902
	2 GL	0.967	0.882	0.762	0.604
	3 BC	1.710	1.112	1.013	0.902
	4 GR	1.812	1.213	1.211	1.222
	5 HR	2.103	1.091	1.028	0.789
	6 YS	0.954	0.722	0.724	0.776

In the current research, we use the Euclidean Distance as a retrieve similartity measure inside the nearest neighbor algorithm (it is one of the most used algorithms in CBR systems).

This corresponds to the type of adaptation considered by the current research work.2.1. Vocabulary container definitionTo start, the vocabulary may be defined as the response to the question "Which element of the data structures are used to present fundamental notions?"[START_REF] Richter | Knowledge containers. Readings in Case-Based Reasoning[END_REF]. In fact, the definition of this knowledge is highly depended on knowledge source nature. For object-oriented organization, for instance, attribute-value structure is generally used to define the vocabulary. However, if it consists on more complex types of data like text, sensor data or image, then the vocabulary may be defined differently using predicates, functions, set of words, or related constructs.In the current work, we define the vocabulary of CBR systems by the set of features 3 describing cases.

Feature and Attribute terms are used exchangeably within this paper.


Malika Ben Khalifa
email: malikabenkhalifa2@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

An Evidential Spammer Detection based on the Suspicious Behaviors' Indicators

Keywords: Spammer detection, Online reviews, Fake reviews, Uncertainty, Classification, E-commerce

The e-reputation is the key factor for the success of different companies and organizations. It is mainly influenced by the online reviews that have an important impact on the company's development. In fact, they affect the buying decision of the customer. Due to this attraction, the spammers post deceptive reviews to deliberately mislead the potential customers. Thus, the spammer detection becomes crucial to control the fake reviews, to protect the e-commerce from the fraudsters' activities and to ensure an equitable online competition. In this way, we propose a novel method based on the K-nearest neighbor algorithm within the belief function theory to handle the uncertainty involved by the suspicious behaviors' indicators. Our method relies on several spammers indicators used as features to perform the distinguishing between innocent and spammer reviewers. To evaluate our method performance and robustness, we test our approach on two large real-world labeled datasets extracted from yelp.com.

I. INTRODUCTION

Nowadays, internet gives the opportunity to people everywhere in the world to express and share their opinions and attitudes regarding products or services. These opinions called online reviews become one of the most important source of information thanks to their availability and visibility. They are increasingly used by both consumers and organizations. Positive reviews usually attract new customers and bring financial gain. However, negative ones damage the e-reputation of different business which lead to a loss. Reviewing has changed the face of marketing in this new area. Due to their important impact, companies invest money to overqualify their product to gain insights into readers preferences. For that, they rely on spammers to usually post deceptive reviews; positive ones to attract new customers and negative ones to damage the competitors' e-reputation. These fraudulent activities are extremely harmful for both companies and readers. Hence, detecting and analyzing the opinion spam becomes pivotal to save the e-commerce and to ensure trustworthiness and equitable competition between different products and services. Therefore, different researchers have given a considerable attention to this challenging problem. In fact, several researches [?], [?], [?], [?], [?] have been devoted to develop performing method capable of spotting fake reviews and stopping these misleading actions. These approaches can be classified into three global categories; spam review detection based on the reviews contents and linguistic features, group spammer detection based on the relational indicators and spammer detection.

Since spammers are the chief responsible of the appearance of deceptive reviews, spotting them is surly one of the most essential task in this field. Several approaches addressed this problem [?] and succeed to achieve significant results. The spammer detection techniques can be divided into two global categories; graph based method and behaviors indicators based methods. One of the first studies that relies on the graph representation to detect fake reviews was proposed in [?]. This method attempted a spot of fake reviewers and reviews of online stores. This approach is based on a graph model composed by three types of nodes which are reviewers, reviews and stores. The spamming clues are composed through the interconnections and the relationships between nodes. The detection of these clues is based on the trustiness of reviewers, the honesty of reviews and the reliability of stores. Thanks to these three measures the method generates a ranking list of spam reviews and reviewers. This method was tested on real dataset extracted from resellerratings.com and labeled by human experts judged. However, the accuracy of this method is limited to 49%. Similar study was proposed in [?] based also on the review graph model. This method generates a suspicion score for each node in the review graph and updates these scores based on the graph connectivity using an iterative algorithm. This method was performing using a dataset labeled through human judgment. Moreover, the third graph related approach was introduced by [?] as an unsupervised framework. This method relies on a bipartite network composed by reviewers and products. The review can be positive or negative according to the rating. The method assumes that the spammers usually write positive reviews for a bad products and negative ones for good quality products. The authors use an iterative propagation algorithm as well as the correlations between nodes and assign a score to each vertex and update it using the loopy belief propagation (LBP). This method offers a list of scores to rank reviewers and products in order to get k clusters. Results were compared to two iterative classifiers, where they have shown performance.

The aspect of the behaviors indicators was introduced by [?]

to detect spammers. This method measures the spamming behaviors and accord a score to rank reviewers regarding the rating they give. It is essentially based on the assumption that fake reviewers target specific products and that their reviews rating deviates from the average rating associated to these products. Authors assume that this method achieved significant results. Another method proposed in [?] is based also on the rating behavior of the each reviewer. It focuses on the gap between the majority of the given rating and each reviewer's rating. This method uses the binomial regression to identify spammers. One of the most preferment studies was proposed by [?], which is essentially based on various spammers behavioral patterns. Since the spammers and the genuine reviewers display distinct behaviors, the proposed method models each reviewer's spamicity while observing his actions. It was formulated as an unsupervised clustering problem in a Bayesian framework. The proposed technique was tested on data from Amazon and proves its effectiveness. Moreover, authors in [?] proposed a method to detect the brust pattern in reviews given to some specific products or services. This approach generates five new spammer behavior indicators to enhance the review spammer detection. The authors used the Markov random fields to model the reviewers in brust and a hidden node to model the reviewer spamicity. Then, they rely on the loopy belief propagation framework to spot spammers. This method achieves 83.7% of precision thanks to the spammers behaviors indicators. Since then, behavioral indicators have become an important basis for spammer detection task. These indicators are used in several recent researches [?]. Nevertheless, we believe that the information or the reviewers' history can be imprecise or uncertain. Also, the deceptive behavior of users might be due to some coincidence which make the spammer detection issue full of uncertainty. For these reasons, ignoring such uncertainty may deeply affect the quality of the detection. To manage these concerns, we propose a novel method aims to classify reviewers into spammer and genuine ones based on Knearest neighbors' algorithm within the Belief function theory to deal with the uncertainty involved by the spammer behaviors indicators which are considered as features. It is known as the richest theory in dealing with all the levels of imperfections from total ignorance to full certainty. In addition, it allows us to manage different pieces of evidence, not only to combine them but also to make decision while facing imprecision and imperfections. This theory prove its robustness in this field through our previous methods which achieve significant results [?],[?],[?],[?]. Furthermore, the use of the Evidential K-NN has been based on its robustness in the real world classification problems under uncertainty. We seek to involve imprecision in the spammers behaviors indicators which are considered as the fundamental interest in our approach since they are used as features for the Evidential K-NN. In such way, our method distinguishes between spammers and innocents reviewers while offering an uncertain output which is the spamcity degree related to each user. This paper is structured as follows: In the first section, we present the basic concepts of the belief function theory and the evidential K-nearest neighbors, then we elucidate the proposed method in section 2. Section 3 is consacred for the experimental results and we finish with a conclusion and some future work.

II. BELIEF FUNCTION THEORY

In section, we elucidate the fundamentals of the belief function theory as well as the Evidential K-nearest neighbors classifier.

A. Basics

The belief function theory, called also the Dempster Shafer theory, is one of the powerful theories that handles uncertainty in different tasks. It was introduced by Shafer [?] as a model to manage beliefs.

1) Basic concepts: In this theory, a given problem is represented by a finite and exhaustive set of different events called the frame of discernment Ω. 2 Ω is the power set of Ω that includes all possible hypotheses and it is defined by:

2 Ω = {A : A ⊆ Ω}.
A basic belief assignment (bba) or (a belief mass) represents the degree of belief given to an element A. It is defined as a function m Ω from 2 Ω to [0, 1] such that:

A⊆Ω m Ω (A) = 1. (1)
A focal element A is a set of hypotheses with positive mass value m Ω (A) > 0.

Several types of bba's have been proposed [?] in order to model special situations of uncertainty. Here, we present some special cases of bba's:

• The certain bba represents the state of total certainty and it is defined as follows: m Ω ({ω i }) = 1 and ω i ∈ Ω. • The categorical bba has a unique focal element A different from the frame of discernment defined by: m Ω (A) = 1, ∀A ⊂ Ω and m Ω (B) = 0, ∀B ⊆ Ω B = A. • 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 ( 2
)
where A is the focus and w ∈ [0,1].

2) Belief function: The belief function, denoted bel, includes all the basic belief masses given to the subsets of A. It quantifies the total belief committed to an event A by assigning to every subset A of Ω the sum of belief masses committed to every subset of A. bel is represented as follows:

bel(A) = ∅ =B⊆Ω m Ω (B) (3) bel(∅) = 0 (4)
3) Plausibility function: The plausibility function, denoted pl, calculates the maximum amount of belief that could be provided to a subset A of the frame of discernment Ω. Otherwise, it is equal to the sum of the bbm's relative to subsets B compatible with A.

pl(A) = A∩B =∅ m Ω (B)
(5) 4) Combination Rules: Various numbers of combination rules have been proposed in the framework of belief functions 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 [?], denoted by ∩ and defined as:

m Ω 1 ∩ m Ω 2 (A) = B∩C=A m Ω 1 (B)m Ω 2 (C) (6)
2) Dempster's rule of combination: This combination rule is a normalized version of the conjunctive rule [?].

It is denoted by ⊕ and defined as:

m Ω 1 ⊕m Ω 2 (A) = m Ω 1 ∩ m Ω 2 (A) 1-m Ω 1 ∩ m Ω 2 (∅) if A = ∅, ∀A ⊆ Ω, 0 otherwise. (7) 5)
Decision process: The belief function framework provides numerous solutions to make decision. Within the Transferable Belief Model TBM [?], the decision process is performed at the pignistic level where bba s are transformed into the pignistic probabilities denoted by BetP and defined as:

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

B. Evidential K-Nearest neighbors

The Evidential K-Nearest Neighbors (EKNN) [?] is one of the best known classification methods based in the belief function framework. It performs the classification over the basic crisp KNN method thanks to its ability to offer a credal classification of the different objects. This credal partition provides a richer information content of the classifier's output. Notations

• Ω = {C 1 , C 2 , ..., C N }:
The frame of discernment containing the N possible classes of the problem.

• X i = {X 1 , X 2 , ..., X m }:
The object X i belonging to the set of m distinct instances in the problem. • A new instance X to be classified.

• N K (X): The set of the K-Nearest Neighbors of X.

EKNN method

The main objective of the EKNN is to classify a new object X based on the information given by the training set. A new instance X to be classified must be allocated to one class of the N K (X) founded on the selected neighbors. Nevertheless, the knowledge that a neighbor X belongs to class C q may be deemed d as a piece of evidence that raises the belief that the object X to be classified belongs to the class C q . For this reason, the EKNN technique deals with this fact and treats each neighbor as a piece of evidence that support some hypotheses about the class of the pattern X to be classified. .In fact, the more the distance between X and X i is reduces, the more the evidence is strong. This evidence can be illustrated by a simple support function with a bba such that:

m X,Xi ({C q }) = α 0 exp -(γ 2 q d(X,Xi) 2 ) (9) m X,Xi (Ω) = 1 -α 0 exp -(γ 2 q d(X,Xi) 2 ) (10)
Where;

• α 0 is a constant that has been fixed in 0.95.

• d(X, X i ) represents the Euclidean distance between the instance to be classified and the other instances in the training set. • γ q assigned to each class C q has been defined as a positive parameter. It represents the inverse of the mean distance between all the training instances belonging to the class C q . After the generation of the different bba s by the K-nearest neighbors, they can be combined through the Dempster combination rule as follows:

m X = m X,X1 ⊕ ... ⊕ m X,X K (11)
where {1, ..., K} is the set including the indexes of the K-Nearest Neighbors.

III. PROPOSED METHOD

The idea behind our method is to take into account the uncertain aspect in order to improve detecting the spammer reviewers. For that, we propose a novel approach based on different spammers indicators and we rely on the Evidential K-nearest neighbors which is famous classifier under the belief function framework. In the remainder of this section we will elucidate the different steps of our proposed approach; in the first step we model and calculate the spammers' indicators through the reviewers' behaviors. In the second step, we present the initialization phase. Moreover, the learning phase is detailed in the third step. Finally, we distinguish between the spammers and the innocent reviewers through the classification phase in which we also offer an uncertain input to report the spamicity degree of each reviewer. Figure ?? illustrates our method steps.

A. Step1: Pre-processing phase

As mentioned before, the spammers indicators become one of the most powerful tool in the spammers detection field used in several researches. In this part, we propose to control the reviewers behaviors if they are linked with the spamming activities and thus can be used as features to learn the Evidential KNN classifier in order to distinguish between the two classes spammer and innocent reviewers. We select the significant features used in the previous work [?]. Here, we detail them in two lists; in the first list we elucidate the author

Data extraction

Step1:Pre-processing Extract the suspicious behaviors indicators (Features) Step2: Initialization phase :

Step3: Learning phase

Step4: The reviewer classification features and the second one presents the review features.

To make the equations more comprehensible we present the different notations in the table ??.

Reviewers features: The values of these features are into the interval [0,1]. The more the value is close to 1 the higher the spamicity degree is indicated. 1) Content similarity (CS): Generally, spammers choose to copy reviews from other similar products because, for them, creating a new review is considered as an action that required time. That's why, we assume that it is very useful to detect the reviews' content similarity (using cosine similarity) of the same reviewer. From this perspective and in order to pick up the most unpleasing behavior of spammers, we use the maximum similarity.

f CS (R i ) = max Ri(rj ),Ri(r k )∈Ri(T r) cosine(r j , r k ) (12)
Where R i (r j ) and R i (r k ) are the reviews written by the reviewer R i , and R i (T r) represents all the reviews written by the reviewer R.

2) Maximum Number of Reviews (MNR): Creating reviews and posting them successively in one day display an indication of a deviant behavior. This indicator calculates the maximum number of reviews per day for a reviewer normalized by the maximum value for our full data.

f M N R (R i ) = M axRev(R i ) M ax Ri∈Ri(T r) M axRev(R i ) (13)
3) Reviewing Burstiness (BST): Although authentic reviewers publish their reviews from their accounts occasionally, the opinion spammers represent a non-old-time membership in the site. To this point, it makes us able to take advantage of the account's activity in order to capture the spamming behavior. The activity window, which is the dissimilarity between the first and last dates of the review creation, is used as a definition of the reviewing burstiness. Consequently, if the time-frame of a posted reviews was reasonable, it could mention a typical activity. Nevertheless, posting reviews in a short and nearby burst (τ = 28 days, estimated in [?]), shows an emergence of a spam behavior.

f BST (R i ) = 0 L(R i (r)) -F (R i (r)) > τ L(Ri(r))-F (Ri(r)) τ Otherwise ( 14
)
Where L(R i (r)) represents the last posting date of the review r given by the reviewer R i and F (R i (r)) is first posting date of the review.

4) Ratio of First Reviews (RFR):

To take advantage of the reviews, people lean on the first posted reviews. For this reason, spammers tend to create them at an early stage in order to affect the elementary sales. Therefore, spammers believe that managing the first reviews of each product could empower them to govern the people's sentiments. For every single author, we calculate the ratio between the first reviews and the total reviews. We mean by the first reviews those posted by the author as the first to evaluate the product. Review written by the reviewer R i R i (T r)

f RF R (R) = |R i (r f ) ∈ R i (T r)| R i (T r) (15)
Total number of reviews written by the reviewer R i T r(p)

Total number of reviews on product or service p r(p) Review on product p R i (r(p))

Review given by the reviewer R i to the same product p R i (T r(p))

Total number of reviews given by the reviewer R i to the same product p R i (T r * (p)) Total number of rating reviews given by the reviewer R i to the same product p L(R i (r))

Last posting date of the review written by the reviewer

R i F (R i ))
First posting date of the review written by the reviewer

R i A(p)
The date of the product launch

I i Spamming indicator S mean
The mean score of a given product S

The reviewing score of the reviews given to one product p by the same reviewer R i . Ω = {S, S} The frame of discernment including the spammer and not spammer class Where R i (r f ) represents the first review of the reviewer R i . Review features: These features have a binary values. If the feature value is equal to 1, then it indicates the sapmming. If not, it represents the non-spamming.

5) Duplicate/Near Duplicate Reviews (DUP): As far as they want to enhance the ratings, spammers frequently publish multiple reviews. They tend to use a duplicate/near-duplicate kind of preceding reviews about the same product. We could spotlight this activity by calculating the duplicate reviews on the same product. The calculation proceeding is as following:

f DU P R i (r)) = 1 r ∈ R i (T r(p)) = cosine(R i (r), r) > β 1 0 otherwise (16
) For a review r each author R i on a product p acquires as value 1 if it is in analogy (using cosine similarity based on some threshold, β 1 = 0.7) with another review is estimated in [?].

6) Extreme Rating (EXT): In favor of bumping or boosting a product, spammers often review it while using extreme ratings (1* or 5*). We have a rating scale composed by 5 stars (*).

f EXT (R) = 1 R i (T r * (p)) ∈ {1, 5} 0 R i (T r * (p)) ∈ {2, 3, 4} (17)
Where R i (T r * (p)) represents all the reviews (ratings) given by the reviewer R i to the same product p. 7) Rating Deviation: Spammers aim to promote or demote some target products or services to this point they generate reviews or rating values according the situation. In order to deviate the overall rating of a product, they have to contradict the given opinion by posting deceptive ratings strongly deviating the overall mean.

If the rating deviation of a review exceeds some threshold β2 = 0.63 estimated in [?], this features achieves the value of 1. The maximum deviation is normalized to 4 on a 5-star scale.

f Dev (R) = 1 |S-Smean| 4 > β 2 0 otherwise (18)
Where S mean represents the mean score of a given product and S represents the reviewing score of the reviews given to one product p by the same reviewer R i .

8) Early Time Frame (ETF):

Since the first review is considered as a meaningful tool to hit the sentiment of people on a product, spammers set to review at an early level in order to press the spam behavior. The feature below is proposed as a way to detect the spamming characteristic:

ET F (r, p) = 0 L(R i , p) -A(p) > δ 1 -L(Ri,p)-A(p) δ otherwise ( 19
)
f ET F (r) = 1 ET F (R i , R i (r(p))) > β 3 0 otherwise ( 20
)
Where L(R i , p) represents the last review posting date by the reviewer R i on the product p and A(p) is the date of the product launch. The degree of earliness of an author R i who had reviewed a product p is captured by ET F (R i , R i (r(p))) the threshold symbolizing earliness is about δ = 7 months (estimated in [?]). According the presented definition, we cannot consider the last review as an early one if it has been posted beyond 7 months since the product's launch. On the other hand, the display of a review following the launch of the product allows this feature to reach the value of 1. β 3 = 0.69 is considered as the threshold mentioning spamming and is estimated in [?]. 9) Rating Abuse (RA): To bring up the wrongly use generated from the multiple ratings we adopt the feature of Rating Abuse (RA). Obtaining Multiple rating on a unique product is considered as a weird behavior. Despite the fact that this feature is alike to DUP, it does not focus on the content but rather it targets the rating dimension. As definition, the Rating Abuse, the similarity of the donated ratings by an author for a product beyond multiple ratings by the same author blended by the full reviews on this product.

RA(R i , R i (r(p)) = |R i (T r(p))|(1 - 1 4 max r∈Ri(T r(p)) (r, p)- min r∈Ri(T r(p)) (r, p)) (21)
f RA = 1 RA(R i , R i (r(p)) > β 4 0 otherwise (22)
We should calculate the difference between the two extremes (maximum/minimum) on 5-star scale rating to catch the coherence of high/low rating and to determine the similarity of multiple star rating. The maximum difference between ratings attains as normalized constant 4. Lower values are reached by this feature if, in authentic cases, the multiple ratings where in change (as a result of a healthy use). β 4 = 2.01 is considered as the threshold mentioning spamming and is estimated in [?].

B. Step2: Initialization phase

In order to apply the Evidential K-NN classifier, we should firstly assign values to parameters α 0 et γ 0 to be used in the learning phase. We will start by initializing the parameter α 0 and then computing the second parameter γ Ii while exploiting the reviewer-item matrix. As mentioned in the EKNN procedure [?], the α 0 is initialized to 0.95. The value of the parameter α 0 is assigned only one time while the γ Ii value change each time according to the current items' reviewers. In order ensure the γ Ii computation performance, first of all we must find reviewers having separately exclusive spammers indicators. Based on the selected reviewers, we assign a parameter γ Ii to each indicators I i corresponding to the reviewer R i which will be measured as the inverse of the average distance between each pair of reviewers R i and R j having the same spammers' indicators values. This calculation is based on the Euclidean distance denoted d(R i , R j ) such that:

d(R i , R j ) = n i,j=1 (I (R,i) -I (R,j) ) 2 (23)
Where I (R,i) and I (R,j) correspond to the value of the spammer indicators of the reviewer R to the indicators i and j.

C. Step3: Learning phase

Once the spammers indicators are calculated and the two parameters α 0 and γ Ii have been assigned, we must select a set of reviewers. Then, we compute for each reviewer R j in the database, its distance with the target reviewer R i . Given a target reviewer, we have to spot its K-most similar neighbors, by selecting only the K reviewers having the smallest distances values that is calculated using the Euclidean distance and denoted by dist(R i , R j ).

D. Step4: Classification phase

In this step, we aim to classify a new reviewer into spammer or innocent reviewer. Let Ω = {S, S} where S represents the class of the spammers reviewers and S includes the class of the not spammers (genuine) reviewers.

1) The bba's generation: Each reviewer R I induces a piece of evidence that builds up our belief about the class that he belongs. However, this information does not supply certain knowledge about the class. In the belief function framework, this case is shaped by simple support functions, where only a part of belief is committed to ω i ∈ Ω and the rest is assigned to Ω. Thus, we obtain the following bba:

m Ri,Rj ({ω i }) = α Ri (24) m Ri,Rj (Ω) = 1 -α Ri ( 25
)
Where R i is the new reviewers and R j is its similar reviewer that j = {1..K}, α Ri = α 0 exp (-γ Ii dist(Ri,Rj )) , α 0 and γ Ii are two parameters assigned in the initialization phase and dist(R i , R j ) is the distance between the two reviewers R i and R j computed in the learning phase.

In our case, each neighbor of the new reviewer has two possible hypotheses. It can be similar to a spammer reviewer in which his the committed belief is allocated to the spammer class S and the rest to the frame of discernment Ω. In the other case, it can be near to an innocent reviewer where the committed belief is given to the not spammer class S and the rest of is assigned to Ω. We treat the K-most similar reviewers as independent sources of evidence where each one is modeled by a basic belief assignment. Hence, K different bba's can be generated for each reviewer.

2) The bba's combination: After the generation of the bba's for each reviewer R i , we describe how to aggregate these bba's in order to get the final belief about the reviewer classification. Under the belief function framework, such bba's can be combined using the Dempster combination rule. Therefore, the obtained bba represent the evidence of the K-nearest Neighbors regarding the class of the reviewer. Hence, this global mass function m is obtained as such:

m Ri = m Ri,R1 ⊕ m Ri,R2 ⊕ .... ⊕ m Ri,R K (26)
3) Final classification result and the spamicity degree according: We apply the pignistic probability BetP in order to select the membership of the reviewer R i to one of the classes of Ω and to accord him a spamicity degree. Then, the classification decision is made either the reviewer is a spammer or not. For this, we select the BetP with the grater value. Moreover, we assign to each reviewer even he is not a spammer the spamicity degree which consists on the BetP value of the spammer class. The evaluation in the fake reviews detection problem was always a challenging issue due to the unavailability of the true real world growth data and variability of the features also the classification methods used by the different related work which can lead to unsafe comparison in this field.

Data description

In order to test our method performance, we use two datasets collected from yelp.com. These datasets represent the more complete, largest, the more diversified and general purpose labeled datasets that are available today for the spam review detection field. They are labeled through the classification based on the yelp filter which has been used in various previous works [?], [?], [?], [?], [?] as ground truth in favor of its efficient detection algorithm based on experts judgment and on various behavioral features. Table ?? introduces the datasets content where the percentages indicate the filtered fake reviews (not recommended) also the spammers reviewers. The YelpNYC dataset contains reviews of restaurants located in New York City; the Zip dataset is bigger than the YelpNYC datasets, since it includes businesses in various regions of the U.S., such that New York, New Jersey, Vermont, Connecticut and Pennsylvania. The strong points of these datasets are:

• The high number of reviews per user, which facilities to modeling of the behavioral features of each reviewer. • The miscellaneous kinds of entities reviewed, i.e., hotels and restaurants • Above all, the datasets hold just fundamental information, such as the content, label, rating, and date of each review, connected to the reviewer who generated them. With regard to considering over-specific information, this allows to generalize the proposed method to different review sites. Evaluation Criteria We rely on these three following criteria to evaluate our method: Accuracy, precision and recall and they can be defined as Eqs.??, ??, ?? respectively where T P , T N , F P , F N

P recision = T P (T P + F N )

Recall = T P (T P + F N )

Experimental results

As our method relies on the Evidential KNN classifier to classify the reviewer into spammer and genuine ones. We propose to compare our method with the Support Vector Machine (SVM) and the Naive Bayes (NB) used by most of spammer detection method [?], [?], [?]in this field. Moreover, we propose to compare also with our previous proposed Uncertain Classifier to detect Spammers (UCS) in [?]. Table ?? reports the different results.

Our method achieves the best performance detection according to accuracy, precision and recall over-passing the baseline classifier. We record at best an accuracy improvement over 24% in both yelpZip and yelpNYC data-sets compared to NB and over 19% compared to SVM. Moreover, the improvement records between our two uncertain methods (over 10%) at best, shows the importance of the variety of the features used in our proposed approach. Our method can be used in several fields by different reviews websites. In fact, these websites must block the detected spammers in order to stop the appearance of the fake reviews. Moreover and thanks to our uncertain output which represent the spamicity degree for each reviewer, they can control the behavior of the genuine ones with a high spamicity degree to prevent their tendency to turn into spammers.

V. CONCLUSION

In this work, we tackle the spammer review detection problem and we propose a novel approach that aims to distinguish between the spammer and the innocent reviewers while taking into account the uncertainty in the different suspicious behavioral indicators. Our method shows its performance in detecting the spammers reviewers while according a spamicity degree to each reviewer. Our proposed approach can be useful for different reviews sites in various fields. Moreover, our uncertain input can be used by other methods to model the reliability each reviewer. As future work, we aim to tackle the group spammer aspect in the interest of improving the detection in this field.

  denote True Positive, True Negative, False Positive and False Negative respectively: Accuracy = (T P + T N ) (T P + T N + F P + F N )