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

Zied Elouedi
email: zied.elouedi@gmx.fr

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

CEVM: Constrained Evidential Vocabulary Maintenance policy for CBR systems

Keywords: Case-Based Reasoning, Vocabulary Maintenance, Belief Function Theory, Uncertainty, Constrained Attribute Clustering

The maintenance of Case-Based Reasoning (CBR) systems has attracted increasing interest within current research since they proved high-quality results in different real-world domains. This kind of systems stores previous experiences, which are described by a vocabulary (e.g., attributes), incrementally in a case base. Actually, the vocabulary presents one among the most important maintenance targets, since it highly contributes in providing accurate solutions and in improving systems' performance, especially within high-dimensional domains. However, there is no policy, in the literature, that offers the ability to exploit prior knowledge (e.g., given by domain-experts) during the maintenance of features describing cases. In this paper, we propose a flexible policy for the most relevant attribute selection based on the attribute clustering concept. This new policy is able, on the one hand, to manage uncertainty using the belief function theory based tools, and on the other hand, to make use of domain-experts knowledge in form of pairwise constraints: If two attributes offer the same information without any added-value, then a Must-link constraint between them is generated. Otherwise, if there is no relation between them and they offer different information, then a Cannot-link constraint between them is created.

Introduction

Case-Based Reasoning is a methodology of problem-solving that recalls past experiences to solve new problems. It is mainly based on the hypothesis that similar problems have similar solutions with offering the possibility to make some adaptations to the provided solution in order to perfectly match the new problem's characterizations. After the revision of every provided solution, the problem-solution couple is retained as a new case within the Case Base (CB) [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]. Over the last three decades, CBR systems have been more and more utilized and applied in several areas such as medicine [START_REF] Glez-Pea | geneCBR: a translational tool for multiple-microarray analysis and integrative information retrieval for aiding diagnosis in cancer research[END_REF], finance [START_REF] Chuang | Application of hybrid case-based reasoning for enhanced performance in bankruptcy prediction[END_REF], and ecology [START_REF] Lesniak | Cost calculation of construction projects including sustainability factors using the Case Based Reasoning (CBR) method[END_REF].

Obviously, this can only indicate its strength, success and adequacy even with weak-understandable domains. Since CBR systems are now commercially used, the need of their maintenance presents a key issue for overtime success. Hence, more and more research focus on maintaining the different knowlege containers of CBR systems. Actually, there are four knowledge containers, as defined in [START_REF] Richter | Knowledge containers[END_REF], that may be maintained [START_REF] Wilson | Maintaining Case-Based Reasoners: Dimensions and Directions[END_REF] within a CBR system: (1) Case Base, (2) Adaptation, (3) Similarity, and (4) Vocabulary. Obviously, the CB is the elementary container of any CBR system, that several research aimed to maintain [START_REF] Ben Ayed | Exploiting Domain-Experts Knowledge Within an Evidential Process for Case Base Maintenance[END_REF]. However, the vocabulary container also presents one among the most important maintenance targets, since it can seen as the basis of the different CBR's steps to offer solutions. For Structural CBR systems (SCBR), we can restrict the vocabulary knowledge to the set of attributes describing cases. By this way, to maintain vocabulary for CBR systems, we are faced to two main challenges: First, the elimination of redundant attributes in order to improve CBR systems performance, especially within large-scale domains. Second, the removal of noisy attributes so as to help the CBR system to be conducted to the most accurate solution. To tackle these challenges in the best way possible, a crucial need of uncertainty management within CBR systems knowledge arises. In fact, cases stored in every CB involve real-world experiences which are never exact. Hence, they cause ignorance and overlapping data regions during learning. This uncertainty within knowledge is managed only in some research, in the literature, that focus on maintaining CBR systems vocabulary via the automatic analysis of their content. However, these works suffer from their disability to aid their automatic maintaining mechanism when prior knowledge regarding attributes, which can be provided by domain experts, are available. This limitation can be tackled through semi-supervised learning of features, more precisely the semisupervised clustering. It consists, in our settings, at using the pairwise Must-link and Cannot-link constraints on some instances to help the used unsupervised attributes clustering. Since we intend to learn on features, Must-link constraint3 between two features is generated when a prior knowledge affirms that they offer almost the same information. On the contrary, a Cannot-link constraint4 is created when prior knowledge is available to affirm that there is no relation between them. Based on these ideas, we build our new vocabulary maintenance policy named CEVM, for "Constrained Evidential Vocabulary Maintenance policy for CBR systems", which manages uncertainty within the framework of belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], and allows the exploitation of experts knowledge, related to attributes relations, using the constrained evidential dissimilarity-based clustering technique called CEVCLUS [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF]. The remaining of this paper is organized as follows. Section 2 is dedicated to define the vocabulary as a maintenance target in CBR systems with explaining our motivation. The related background on the belief function theory is presented in Section 3. Throughout Section 4, we detail our new established policy aiming at selecting only the most relevant attributes for cases description. We show our experimental study as well as our proposed modes for artificial constraints generation in Section 5. Finally, the Section 6 is dedicated for the conclusion.

Vocabulary maintenance for CBR systems

Obviously, CBR systems are made to operate for a long period of time. However, the change of the context along with the incremental learning through experiences give rise to the need of maintaining the vocabulary that describes cases.

The vocabulary as a knowledge container in a CBR system

The vocabulary knowledge is presented and modeled in [START_REF] Richter | Knowledge containers[END_REF] as the basis of all the other three knowledge containers. In fact, its definition depends mainly on the knowledge source's nature. In this paper, we focus on attribute-value data. However, in non-structural CBR system, more sophisticated methods may be included within the vocabulary container. For our current purpose, we restrict the vocabulary knowledge container to the set of attributes.

The vocabulary as a maintenance target

Every encountered experience in our real life can be described with an infinite number of features. However, only some of them are useful to provide the accurate solution for one problem. As already mentioned, there are basically two types of attributes that should be removed to maintain cases' vocabulary. On the one hand, the set of noisy attributes that their removal from the vocabulary conducts to the improvement of the CBR system's decision making. On the other hand, the set of redundant attributes that we define by the ensemble of high correlated features. Actually, we call them redundant since they offer the same information, and the removal of one of them does not affect the whole CBR system's competence in solving new problems, but it may improve its performance in term of response time. Within the same road, some works, such in [START_REF] Ben Ayed | Maintaining case knowledge vocabulary using a new Evidential Attribute Clustering method[END_REF][START_REF] Arshadi | Feature Selection for Improving Case-Based Classifiers on High-Dimensional Data Sets[END_REF][START_REF] Leake | Flexible feature deletion: compacting case bases by selectively compressing case contents[END_REF], target the vocabulary of CBR systems for maintenance. They are mainly based on selecting the most relevant features, where we cite, for instance, the ReliefF method [START_REF] Kononenko | Estimating attributes: analysis and extensions of RELIEF[END_REF] as one among the baselines of features selection methods. However, existing policies suffer from some weaknesses towards the concepts shown in the following Subsections, where we present our motivation.

Attribute clustering and uncertainty management during vocabulary maintenance

Regrouping attributes according to some proximity data between them can be reached through the attribute clustering concept [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]. Actually, applying this concept during maintaining vocabulary leads to preserve relations between features and offers a high amount of flexibility to the CBR framework, where we can substitute every attribute by any other one belonging to the same cluster.

Similarly to object clustering, we can consider the set of attributes as the set of objects, and regroup them in such a way that features belong to the same cluster are somehow similar. In contrast, attributes belonging to different clusters are dissimilar. However, uncertainty within attributes clustering has to be managed since attributes-values refer to the description of real-world experiences that are full of uncertainty, vagueness, and imprecision. Further, as mentioned in [START_REF] Weber | Fuzzy set theory and uncertainty in case-based reasoning[END_REF], the vocabulary presents one among the origins of uncertainty in CBR framework. That's why, we make use of one among the most powerful tools for this matter called 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], where its basic concepts are shown in Section 3.

Exploiting prior knowledge during vocabulary maintenance

Usually, research that are interested on knowledge extraction learn via the automatic analysis of available data content without giving the possibility to domainexperts or available prior knowledge to intervene inside this process. Within Case-Based Reasoning framework, systems are generally solving problems within some specific domain, where its experts may provide knowledge that are expensively extracted by machine learning methods. Consequently, it is greatly useful to aid the automatic maintenance process through the exploitation of prior knowledge in form of Must-Link and Cannot-Link constraints. This can be done, for instance, inside a constrained machine learning technique.

Belief function theory

To handle uncertainty during the decision making process, we use 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 Dempster-Shafer theory or Evidence theory, which is a powerful mathematical framework used to deal with partial and unreliable information in many fields. We show, during this Section, the fundamental concepts of this theory as well as the evidential clustering and the credal partition concepts.

Fundamental concepts

A belief function model is originally defined by a discrete and finite set of elementary events called the frame of discernment Θ of the problem taken into account. The set 2 Θ is called the power set and contains all the possible subsets of Θ. The basic belief mass (bbm) m Θ is a mapping function from 2 Θ to [0, 1] that assigns to every subset A of Θ a degree of belief reflecting the partial knowledge taken by a variable y defined on Θ, and verifies the constraint A⊆Θ m(A) = 1.

A mass function m is normalized if m(∅) = 0. On the opposite case, the interpretation of the mass assigned to the empty set partition consists at measuring the degree of belief towards the hypothesis saying that y does not belong to Θ. This amount of belief can be useful in clustering to identify noises [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF]. From a given mass function m, the plausibility function is defined, to measure the maximum amount of belief supporting the different subsets in Θ, as follows:

pl(A) = B∩A =∅ m(B) ∀A ⊆ Θ (1)
Given two bbms m 1 and m 2 , defined in the same frame of discernment Θ, the following Equation, proposed in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], presents one among the most known measurements that aim to quantify the degree of conflict between them such that:

κ = A∩B m 1 (A) m 2 (B) (2)
Authors in [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] proved that if two bbms represent evidence regarding two distinct questions and defined in the same frame Θ, then the plausibility that they acquire the same answer is equal to 1 -κ.

Evidential clustering and Credal partition

We call Evidential Clustering the task of regrouping objects5 , according to some attribute-based/dissimilarity-based data, within the frame of belief function theory. In an evidential clustering context, the frame of discernment Θ defines the set of a finite number K of clusters. Besides, the uncertainty regarding the membership of an object o i to the different clusters is modeled by a bbm m i on Θ. If we have n objects, the credal partition is, therefore, the n-tuple composed by n mass functions, such that M = (m 1 , ..., m n ) [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF]. Generally, M is generated after applying an evidential clustering technique to regroup a set of objects according to their similarity while managing the uncertainty in their membership to all the possible partitions of clusters. Since it quantifies uncertainty in a power set space, the credal partition is more general than hard and soft partitions. Nevertheless, it can be converted to any one of these types [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF][START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF]. After generating the credal partition, the decision about the membership may regard the cluster having the highest pignistic probability, which is defined as follows:

BetP (ω) = ω∈A m(A) |A| ∀ω ∈ Θ (3)
In the case of non normalized mass functions, a preprocessing step of normalization for every bbm should beforehand be applied as follows:

m * (A) =    m(A) 1 -m(∅) if A = ∅ 0 Otherwise (4)
After presenting the essential background as well as our motivation, we move on now at detailing our contribution for this paper. first of all, at generating some dissimilarity data, from the CB, between attributes based on the correlation between their values. Second, CEVM regroups the set of attributes using their dissimilarities and with taking advantage of prior knowledge. After managing uncertainty and generating the credal partition by allowing every attribute to belong to all the partitions of clusters with a degree of belief, we make decision about their membership along with removing noisy and redundant features. More details are given during the three following Subsections.

Step 1: Extracting attributes dissimilarity data

The notion of dissimilarity between attributes can be defined, according to the context into account, in term of dependency, correlation, etc. To generate the dissimilarity between attributes, three substeps are followed by our new CEVM policy.

1. Correlation between attributes: In our context, the origins of dissimilarity data between attributes are generated through measuring the correlation between their values. The idea is that if two attributes are highly correlated, then they offer the same information for solving problems. We use the Pearson's Correlation Coefficient [START_REF] Pearson | Mathematical contributions to the theory of evolution[END_REF] so as to measure the linear association between the different values a i and b i of attributes A and B respectively, as follows:

r AB = n i=1 (a i -a)(b i -b) n i=1 (a i -a) 2 n i=1 (b i -b) 2 (5)
where a and b are the mean values of features A and B respectively. The set of correlations between every two features A and B gives rise to a square relational matrix defined as R = (r AB ). 2. Similarity between attributes: All the correlation values in R are bounded between -1 and 1 [START_REF] Pearson | Mathematical contributions to the theory of evolution[END_REF]. If r AB -1, then there is a high negative correlation and a high similarity between A and B since they offer the same information. Similarly, if r AB 1, then there is a high positive correlation and a high similarity between A and B since they offer the same information for learning. However, if r AB 0, then there is no correlation between them, which makes A and B completely dissimilar. As an intuitive consequence, we create the square similarity matrix S = (s AB ) such as:

s AB = |r AB | (6)
3. Attributes dissimilarity data: After measuring the similarity between features, it is straightforward to compute the square dissimilarity matrix D = (d AB ) such that:

d AB = 1 -s AB (7)
By this way, values in D are also in the interval [0, 1].

Step 2: Constrained Evidential Attribute Clustering

When we have some background knowledge, it is so gainful to use them throughout learning. Actually, this is the main principle of semi-supervised learning. This step, that aims at regrouping features according to their similarity, is very important to reach two other objectives during vocabulary maintenance. First, managing the uncertainty in attributes membership to clusters from the complete ignorance to the total certainty using the belief function framework. Secondly, exploiting the prior available knowledge supplied, for instance, by the experts of domain in which the CBR is applied. We used a constrained evidential clustering method based on dissimilarity data between objects6 called Constrained EVidential CLUStering (CEVCLUS) [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF]. It is a variant of EVCLUS [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] that is characterized by its ability to taking into account a prior knowledge in form of two pairwise constraints: The Must-link (ML) constraint which concerns two attributes that belong for sure to the same cluster, and the Cannot-Link (CL) constraint that concerns the pair of attributes that are known to belong to distinct clusters. Given m i and m j two bbms regarding cluster-membership of attributes A i and A j respectively, let pl ij (Θ ij ) refers to their plausibility to belong to the same cluster, and pl ij (Θ ij ) refers to the plausibility of the complementary event. They can be calculated as follows [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF]:

pl ij (Θ ij ) = 1 -κ ij (8a) pl ij (Θ ij ) = 1 -m i (∅) -m j (∅) + m i (∅) m j (∅) - K k=1 m i ({ω k })m j ({ω k }) (8b)
For the sake of clarity regarding the calculation of this plausibility, let mention that it consists at placing ourselves in the Cartesian product Θ 2 = Θ × Θ and combining the two vacuous extensions of m i and m j [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF]. If the resulted combination is denoted by m ij , then pl ij can be computed through m ij using Equation 1.

To construct the credal partition M , the non-constrained EVCLUS [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] algorithm minimizes a stress function, using a gradient based algorithm, similar to:

J(M ) = η i<j (κ ij -δ ij ) 2 (9)
where η = ( i<j δ 2 ij ) -1 , and δ ij = ϕ(d ij ), with ϕ is an increasing function such as ϕ(d) = 1 -exp(-γd 2 ). γ can be calculated as -logα/d 2 0 , with a recommendation to fix α to 0.05 and d 0 , which determines the size of each class, can be set to some quantile of the dissimilarities in D.

The principle of the previous stress function is explained by Equation 8a. It means that if two attributes are too far in term of distance, then they should have a low plausibility to belong to the same cluster, and a large degree of conflict. In our context, if we have prior knowledge that attributes A i and A j surely belong to different clusters, then the constraints pl ij (Θ ij ) = 1 and pl ij (Θ ij ) = 0 are imposed. In contrast, if prior knowledge affirm that they belong to the same cluster, then the constraints pl ij (Θ ij ) = 0 and pl ij (Θ ij ) = 1 are created. By this way, the CEVCLUS algorithm minimizes, using an iterative gradient-based optimization procedure, the following cost function composed by the sum of EVCLUS's stress function [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] and a penalization term:

J C (M ) = stress + ξ 2(|M L| + |CL|) (J M L + J CL ), (10)
with

J M L = (i,j)∈M L pl ij (Θ ij ) + 1 -pl ij (Θ ij ), (11a)
J CL = (i,j)∈CL pl ij (Θ ij ) + 1 -pl ij (Θ ij ), ( 11b
)
where ξ presents the hyper-parameter aiming at arbitrating between the stress function and the constraints.

Step 3: Attribute maintenance

Ultimately, we reach our purpose for cases' vocabulary maintenance through removing noisy and redundant features, and keeping only those that are unique and represent the different generated clusters during the previous step. As shown in Fig. 1, this step is composed by the three following substeps:

1. Removing noisy attributes: Since the previous applied clustering method devotes the empty set partition for noisiness allocation, we eliminate attributes characterized by a high belief's assignment to the empty set partition, such that:

A i ∈ N A if f m i (∅) > Bj ⊆Θ,Bj =∅ m i (B j ) (12)
where A i represents the attribute i, and N A presents the set of all the noisy attributes.

2. Making decision about attributes membership to clusters through the highest pignistic probability value, using Equation 3. 3. Removing redundancy by keeping only one representative attribute for each cluster. This idea gives an amount of flexibility to our policy towards CBR framework: If there is a problem in selecting one representative attribute, then we can re-select and re-flag any other attribute from the same cluster.

Example 1. Let consider some CB's vocabulary described by four attributes A 1 , A 2 , A 3 , and A 4 . Let us suppose, now, that the frame of discernment contains two clusters (Θ = {cluster 1 , cluster 2 }), and the values of the credal partition M = [m 1 ; m 2 ; m 3 ; m 4 ] are given by the previous step as shown in Table 1. First, we note, from Table 1, that m 2 (∅) is higher than m 2 ({cluster 1 }) + flag A 2 as a noisy attribute (A 2 ∈ N A). Consequently, we update the CB's vocabulary by removing the second attribute A 2 . Then, we make decision about attributes membership to clusters using BetP defined in Equation 3. Their corresponding pignistic probability values are shown in Table 2, from which we can conclude that A 1 belongs to cluster 1 , and A 3 and A 4 belong to cluster 2 . Finally, we keep only the attribute A 1 as representative of cluster 1 and the attribute A 3 as representative of cluster 2 to describe the new maintained case base vocabulary.

Experimental analysis using artificial constraints

Throughout this Section, we establish our experimentation and validate our contribution by developing two variants of our CEVM policy that differ by their way in generating artificial constraints 7 .

Constraints generation strategy

Two main modes for Must-link and Cannot-link constraints generation, such in [START_REF] Ben Ayed | Exploiting Domain-Experts Knowledge Within an Evidential Process for Case Base Maintenance[END_REF], are build during our experimental analysis:

-Batch mode for constraints generation (CEVM bat ): It consists at generating simultaneously a number t of constraints (Must-link and Cannot-link ). For instance, we took t equal to 25% of the total number of attributes. We store the list of these constraints in listConst. The activity diagram of CEVM bat is shown in Fig. 2. How we generate a constraint? Actually, we generate artificially a pairwise constraint by handling the uncertainty offered by the credal partition and the pignistic probability transformation (Equation 3). The idea consists at randomly picking two attributes A i and A j and behaving according to the three following situations that may arise:

1. If ∃ a cluster ω/BetP i (ω) > T hresh and BetP j (ω) > T hresh, then generate a Must-link constraint between the attributes A i and A j . 2. If ∀ clusters ω k /|BetP i (ω k )-BetP j (ω k )| > T hresh, then generate a Cannotlink constraint between the attributes A i and A j . 3. Else, go back to randomly picking two attributes.

where T hresh is a threshold that aims to answer to the question: "From which amount of membership certainty in [0, 1], we consider that the attributes A i and A j belong or not to the same cluster?"8 .

Data, evaluation criteria, and experimental settings

Our new CEVM policy has been implemented using Matlab R2015a and the default values for the different CEVCLUS [START_REF] Antoine | CEVCLUS: evidential clustering with instance-level constraints for relational data[END_REF] method's parameters have been taken. CEVM with its two variants have been tested on six data sets from U.C.I Repository9 where the set of attributes are considered as the vocabulary describing cases' problems, and their classes refer to cases' solutions.

In order to assess the efficiency of our new vocabulary maintenance policy, we use the two following evaluation criteria:

-The Percentage of Correct Classifications (P CC), which is defined as follows:

P CC(%) = # Correct classif ications # T otal classif ications × 100 (13)
The PCC criterion refers to the competence of CBR systems in solving new problems. -The Retrieval Time (RT ) Criterion, which measures the time spent to offer all the solutions for the different cases instances. It may refer to the performance of CBR systems.

To solve cases' problems, we use the K-Nearest Neighbor (K-NN) since it presents one among the most used machine learning techniques within the CBR framework. We choose to apply 3-NN so as to avoid the effect of noisy cases during learning. Hence, the RT criterion is exerted around that 3-NN method. To offer the final results towards the PCC, the 10-fold cross validation technique is used.

Results and discussion

In our comparative study, as shown in Table 3, we present results offered by five different sources where two among them present the two variants of our contribution for this paper (CEVM bat and CEVM alt ), and the three others present the non maintained case base (Original-CBR), the reliefF method [START_REF] Kononenko | Estimating attributes: analysis and extensions of RELIEF[END_REF] for feature selection (ReliefF-CBR), and the non-constrained vocabulary maintenance policy EvAttClus [START_REF] Ben Ayed | Maintaining case knowledge vocabulary using a new Evidential Attribute Clustering method[END_REF]. Results in Table 3 are offered after varying the number of clusters, or the number of the selected attributes K, from 3 to 9. The most convenient K for every method and every data set is chosen 10 . In term of accuracy, both of our two variants CEVM bat and CEVM alt offer good results comparing to the other methods as well as to the original nonmaintained case bases (Original-CBR). We note that the alternate mode for constraints generation is more efficient than the batch mode. We can conclude, furthermore, that better results may be offered if we resort to domain experts. In our context, both of CEVM's variants, that are able to make use of prior knowledge in form of constraints, have been able to maintain all the tested CBs' vocabulary with preserving or even improving their competence in solving problems. For example, they offer PCCs equal to 88.79% and 91.34% for "Glass" data set, where ReliefF-CBR and AttEvClus methods offer PCCs equal to 87.38% and 87.98% respectively. These results can only be explained by CEVM strategy's efficiency in detecting noisy and redundant features. In term of retrieval time, we note very competitive results offered by the four vocabulary maintaining policies. However, a slightly higher difference in RT are noted towards Original-CBR. For instance, "Sonar" data set (60 attributes), moved from RT=0.0642 s to RT=0.0079 s with CEVM alt .

Conclusion

In this paper, a new vocabulary maintenance method for CBR systems, called CEVM, with two modes for artificial constraints generation (batch and alternate mode), are proposed. In order to aid its automatic maintaining process, the proposed policies CEVM bat and CEVM alt offer an ability to exploit prior knowledge in form of pairwise constraints within a constrained clustering method. They are also able to manage the uncertainty thanks to the framework of the belief function theory. Finally, the attribute clustering concept for feature selection makes our new CEVM method more flexible for maintaining vocabulary within CBR framework. During experimentation, better results are offered by CEVM alt version than by CEVM bat .

4Fig. 1 .

 1 Fig. 1. Steps and substeps of CEVM policy

Fig. 2 .

 2 Fig. 2. Activity diagram for batch mode constraints generation

Fig. 3 .

 3 Fig. 3. Activity diagram for alternate mode constraints generation

10

  ReliefF-CBR: GL and GR (K = 7); BC (K = 8); SN, IO, and HR (K = 9); EvAttClus: IO (K = 3); HR (K = 5); BC and GR (K = 8); SN and GL (K = 9); CEVM bat : IO (K = 3); HR (K = 4); BC and GR (K = 8); GL and SN (K = 9); CEVM alt : IO (K = 3); HR (K = 4); GR (K = 6); GL (K = 7); SN and BC (K = 8);

Table 1 .

 1 Example of credal partition values ({cluster 2 }) + m 2 ({cluster 1 , cluster 2 }). Then, according to Equation 12, we

	M	∅ {cluster1} {cluster2} {cluster1, cluster2}
	m1 0.05	0.75	0.15	0.05
	m2 0.65	0.1	0.1	0.15
	m3 0.1	0.05	0.8	0.05
	m4 0.2	0.1	0.5	0.2
	m 2

Table 2 .

 2 Pignistic probability transformation values

		cluster1 cluster2
	BetP1 0.8158 0.1842
	BetP2	0.5	0.5
	BetP3 0.0833 0.9167
	BetP4	0.25	0.75

Table 3 .

 3 Accuracy and retrieval time evaluation

	CB	Original-CBR ReliefF-CBR	AttEvClus	CEVM bat	CEVM alt
		PCC(%) RT(s) PCC(%) RT(s) PCC(%) RT(s) PCC(%) RT(s) PCC(%) RT(s)
	1 SN 73.07	0.0642 71.15	0.0078 74.51	0.0082 74.51	0.0081 75.12 0.0079
	2 IO 86.04	0.0223 84.90	0.0121 88.03 0.0085 88.03 0.0082 88.03 0.0087
	3 GL 88.79	0.0141 87.38	0.0089 87.98	0.0093 88.79	0.0092 91.34 0.0081
	4 BC 96.04	0.0199 96.45	0.0097 96.63 0.0097 96.63 0.0098 96.63 0.0099
	5 GR 70.60	0.0319 69.60	0.0119 71.21	0.0122 71.21	0.0123 73.25 0.0121
	6 HR 56.80	0.0276 59.86	0.0089 60.88	0.0081 62.78 0.0078 62.78 0.0071

Two attributes are surely belonging to the same cluster.

Two attributes cannot belong to the same cluster.

In our context, these objects represent the set of features that describe cases.

In our policy, it concerns dissimilarity data between attributes, which are supplied from the previous step.

During the experimentation, different values to set T hresh have been tested. The best results are offered with T hresh = 0.55.

Sonar (SN), Ionosphere (IO), Glass (GL), BreastCancer (BC), German (GR), and Heart (HR): https://archive.ics.uci.edu/ml/


Malika Ben Khalifa
email: malikabenkhalifa2@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Spammers detection based on reviewers' behaviors under belief function theory

Keywords: Online reviews, Spammers, Fake reviews, Uncertainty, Belief function theory

Nowadays, we note the dominance of the online reviews which become an essential factor in customers' decision to purchase a product or service. Driven by the immense financial profits from reviews, some corrupt individuals or organizations deliberately post fake reviews to promote their products or to demote their competitors' products, trying to mislead or influence customers. Therefore, it is crucial to spot these spammers in order to detect the deceptive reviews, to protect companies from this harmful action and to ensure the readers confidence. In this way, we propose a novel approach able to detect spammers and to accord a spamicity degree to each reviewer relying on some spammers indicators while handling the uncertainty in the different inputs through the strength of the belief function theory. Tests are conducted on a real database from Tripadvisor to evaluate our method performance.

Introduction

Online reviews are becoming more prevalent nowadays due to the huge use of social media, opinion-sharing websites, blogs, forms and merchant websites. Consumers rely heavily up on reviews posted on these websites when making decisions about which products or services to purchase online. However, reviews are more than just a way for customers to gather information, but also a powerful source information for companies since positive opinions bring significant financial gains for business and individuals. Moreover, negative reviews not only cause financial loss, but also damage the companies e-reputation. Unfortunately, all this gives an important incentive for fake reviews. So driven by the desire of profit, spammers create fake reviews and posted them everywhere in order to mislead readers, to influence their decisions and to manipulate their opinion mining. Opinions spam may be positive to promote some companies or negative, to their competitive companies, in order to demote them. These review spamming activities make the products and the services identification confusing and complicated. We believe also that more online reviews are used, more spammers will increase and will post more and more deceptive reviews. The spammer detection becomes an essential task since it allows us to stop the appearance of fake opinions. Several methods addressed this problem [START_REF] Heydari | Leveraging quality metrics in voting model based thread retrieval[END_REF][START_REF] Pan | Identifying indicators of fake reviews based on spammers behavior features[END_REF], most of them are graph based approaches. The first study [START_REF] Wang | Review graph based online store review spammer detection[END_REF] proposes a heterogeneous graph model with three types of nodes to define relations between reviewers, reviews, and store. This method used the interrelationship between three based concepts namely; the trustworthiness of reviewers, the honesty of reviews, and the reliability of stores to generate a ranking list of suspicious reviews and reviewers. However, its level of precision amounts to 49% in the fake reviews detection. A similar approach elaborated by authors in [START_REF] Fayazbakhsh | Review spam detection: A network-based approach[END_REF] which also used a review graph. This method calculated a suspicion score for each node in the review graph and then used an iterative algorithm in order to update these scores based on the graph connectivity. This method has higher precision with respect of the conformity along the human judgments. The third graph based approach was elaborated by Akoglu et al. [START_REF] Akoglu | Opinion fraud detection in online reviews by network effects[END_REF], introduced through a bipartite network. The authors proposed a signed inference algorithm for extending loopy belief propagation (LBP). The output of this algorithm is a list of users ranked by score to get clusters with k reviewers and products. This method was compared to two iterative classifiers, where it succeeded in detecting fraudulent users and spot their fake product ratings. Lim et al. [START_REF] Lim | Detecting product review spammers using rating behaviors[END_REF] were the first use behavioral indicators of deceptive reviews to spot spammers. Their proposed method is based on the behavior scoring technique for ranking reviewers by measuring the spamming behaviors. The human judgment is used for the evaluation. As a result, the rating of the target products alternated adequately by removing the most suspicious reviews. Since then, behavioral indicators have become an important basis for spammer detection task. In this way, researchers in [START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF] proposed a method to exploit observed reviewing behaviors in order to detect opinion spammers using a Bayesian inference framework. Moreover, authors in [START_REF] Fei | Exploiting burstiness in reviews for review spammer detection[END_REF] developed an algorithm in order to detect burst patterns in reviews for a specific product. It generated five new spammer behavior features as indicators to used them in review spammer detection. Two types of evaluation are performed: supervised classification and human evaluation. These techniques achieve significant results thanks to the spammers behavior features. Most of these approaches rely on different human evaluators and experts to annotate their data evaluation. Moreover, each method is based on various inputs and aspects. All this won't allow for a safe comparison in this field. In addition, these techniques exhibit some weaknesses fundamentally related to their inability to manage the uncertainty of different reviewers and in reviews information which are often imperfect and imprecise. Ignoring such uncertainty may deeply affect the detection. That is why, treating the uncertainty when dealing with the fake reviewers detection task becomes a widespread interest. In this paper, we propose a novel method that aims to detect spammers based on the reviewer behavior characteristics under the belief function framework. It is known as a rich tool able to manage several pieces of imperfect information, to combine them, besides taking into account the reliability in the different sources providing them, and making decision under uncertainty. Hence, our approach involves imperfections in the different inputs to spot the spammers and offers also an uncertain output. This latter represents the spamicity degree according to each reviewer in order to identify its reliability. The remainder of the paper is structured as follows: We firstly present the belief function theory basic fundamentals in Section 2. Then, Section 3 elucidates our proposed approach. After that, we discuss the experimental results in Section 4. Finally, a conclusion and some future works are described 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 represent beliefs. It is considered as a powerful tool able to deal with uncertainty in different levels and to manage various types of imperfection.

Basic concepts

The frame of discernment Ω is a finite and exhaustive set of different events associated with a given problem, such set Ω is also called the universe of discourse, defined by:

Ω = {ω 1 , ω 2 ..., ω n } (1)
The power set 2 Ω contains all possible hypotheses that formed the union of events, and the empty set ∅ which represents the conflict, defined by:

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

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

Several kinds of bba's have been proposed [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF] in order to express special situations of uncertainty. Here, we underline 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 ( 4
)
Where A is the focus and w ∈ [0,1].

Discounting

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. When, the bba is defined on the set {reliable, not reliable} such that [START_REF] Smets | The transferable belief model for expert judgement and reliability problem[END_REF]:

m(reliable) = 1 -α and m(not reliable) = α (5)
Accordingly, the discounted bba, noted α m Ω , m Ω becomes:

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

Combination Rules

Let m Ω 1 and m Ω 2 two bba's representing two distinct sources of information defined on the same frame of discernment Ω. Various numbers of combination rules have been proposed in the framework of belief function. They were intended to aggregate a set of bba's in order to get the fused information represented by one bba. In what follows, we elucidate those related to our approach.

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 Ω 1 ∩ m Ω 2 (A) = B∩C=A m Ω 1 (B)m Ω 2 (C) (7)

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 map-ping[END_REF]. This rule is characterized by a normalization factor denoted by K and it is defined as:

(m Ω 1 ⊕ m Ω 2 )(A) = K.(m 1 ∩ m Ω 2 (A)) (8)
Where

K -1 = 1 -(m Ω 1 . ∩ m Ω 2 (∅)) and (m Ω 1 ⊕ m Ω 2 )(∅) = 0 (9)

Decision process

Various solutions have been proposed to choose the most suitable decision for a given problem under the belief function framework. In this work, we adopt the pignistic probability proposed by the Transferable Belief Model [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF]. Therefore, it is composed by two level models:

-The credal level where beliefs are defined by bba's then combined.

-The pignistic level where bba's are transformed into pignistic probabilities denoted by BetP and defined as follows:

BetP (B) = A⊆Ω |A ∩ B| |A| m Ω (A) (1 -m Ω (∅)) ∀ B ∈ Ω (10)
3 Spammers detection based on reviewers' behaviors under belief function theory

In this section, we elucidate our novel proposed method which deals with different important spammer indicators in an uncertain context through the belief function theory in order to distinguish between fake reviewers and genuine ones.

Our method relies on the four most important spammer behaviors indicators namely; the reviewers average proliferation, the brust spamicity degree, the reviews helpfulness and the extreme rating providing by each reviewer. Besides, we adopt the belief function theory to model uncertainty within those indicators. Each reviewer R i will be represented by two mass functions (bba's), the first one is to model the reviewer reputation m Ω RRi and the second one is to represent the reviewer helpfulness m RHi with Ω = {S, S} where S is spammer and S is non spammer. Our method follows four main steps detailed in-depth.

Step 1: Reviewer reputation

In the spammer review detection field, it has been proved that ordinary reviewers usually write their comments on several products in almost consistent patterns during different periods [START_REF] Heydari | Leveraging quality metrics in voting model based thread retrieval[END_REF]. Generally, the genuine reviewers post their opinion when they have actually bought new products or used new services. It means that their reviews depend on the number of tested products or services and are also steadily given over time interval. However, spammers are excepted to post a huge number of reviews to limited intended products or services in short time span, say in two or three days. Consequently, these two indicators can construct the reviewer reputation. In this way, we propose to examine the reviewing history for each reviewer Hist Ri defined as the set of all past reviews written by the reviewer R i for n discrete products. The average number of reviews per product is measured through the sum of different reviews given by each reviewer R i and divided by the total number of reviewed products n. The reviewers average proliferation is calculated through the following equation:

AvgP (R i ) = Hist Ri n (11)
If the AvgP (R i ) > 3, we can assume that the reviewer is suspicious to be a potential spammer since generally ordinary reviewers do not give more than three reviews per product. The reviewer reputation is then represented by a certain bba as follows:

m Ω RRi ({S}) = 1 (12)
Else

m Ω RRi ({S}) = 1 ( 13
)
Example 1. Let us consider the case of five reviewers, for which we have some information about their reviewing history, given an overall rating review for a hotel detailed in the Table 1.

We deal with the Reviewer id = 1 So, we calculate the reviewers average proliferation:

AvgP (R 1 ) = Hist R 1 n
= 258 30 = 8.6 Then, we generate the corresponding bba: Moreover, we propose to verify if the reviews are given in a short time of interval or are scattered during the reviewing history.

AvgP (R 1 ) > 3 ⇒ m Ω RR1 ({S}) = 1
In our method, we fix the time interval to three days and we measure the brust spamicity degree α i through the sum of the reviews' number given in less than three days divided by the total number of reviews by each reviewer denoted by T N R i as follows:

α i =
N umber of reviews given by R i in less than 3 days T N R i .

Then, we weaken the reviewer reputation bba by each corresponding reliability degree (i.e., (1 -α i ) or α i ) using the discounting operation (Eq.6) in order to take into consideration the brust spamicity degree. This discounted bba α m Ω RRi represented the reviewer reputation using the reviewers average proliferation and the brust spamicity which are two important spammer indicators.

Example 2. We continue with the previous Example 1, we calculate the brust spamicity degree: α 1 = 200 258 = 0.775 α 1 is the reliability degree for S, hence we apply the discounting operation as follows:

α m Ω RR1 ({S}) = 1 * α 1 = 1 * 0.775 = 0.775 α m Ω RR1 (Ω) = (1 -α 1 ) + α 1 * 0 = 0.225

Step 2: Reviewer helpfulness

The reviewer helpfulness is an important indicator to spot spammers. For this reason, we propose to verify if the reviewer post helpful reviews or unhelpful ones in order to mislead readers. Accordingly, we propose to use the Number of Helpful Reviews (N HR) to indicate the helpful ones associated to each reviewer. Therefore, if (N HR i = 0), the reviewer is suspicious to be spammer, thus we model the reviewer helpfulness by a certain bba:

m Ω RHi ({S}) = 1 ( 15
)
Else

m Ω RHi ({S}) = 1 ( 16
)
We propose to penalize the reviewer helpfulness mass by considering the non helpfulness degree for each reviewer R i denoted by β i . So, we propose this discounting factor as follows:

β i = T N R i -N HR i T N R i (17)
Then, we use the discounting operation in order to update the bba into a simple support function β m Ω RHi . Thus, we take into consideration the helpfulness degree. Generally, customers are not totally satisfied by their consumed products or tested services. Therefore, the innocent reviewer will not usually post extreme rating. However, most spammers perpetually resort to extreme ratings [START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF], either highest (5*) or lowest (1*), in order to achieve their goal of rapidly raising or bringing down, respectively, the mean score of a product. When the reviewer had a lot of helpful reviews but they are full of extreme rating, his chances of being genuine reviewer certainly decrease. In order to take this fact into account, we calculate the extreme rating degree denoted γ i , corresponding to each reviewer R i , which is considered as the discounting factor calculated by the number of the extreme rating divided by the total number of reviews given by each reviewer T N R i as the following equation:

γ i = N ER i T N R i (18)
Where, N ER i is the extreme reviews' number (i.e., N ER i ∈ {1, 5}) given by each reviewer R i . Then, each simple support function represented the reviewer helpfulness β m Ω RHi is weakened again by its relative reliability degree (i.e., (1 -γ i ) or γ i ) through the discounting operation. Thus, this discounted β γ m Ω RHi modeled the reviewer helpfulness based on both the reviewer helpfulness degree and extreme ranting.

Example 3. Let us consider the same Example 1:

-The reviewer helpfulness bba corresponding to R 1 is generated as follows:

Number of helpful reviews= 100

> 0 ⇒ m Ω RH1 ({S}) = 1
-Then, we calculate the corresponding helpfulness degree:

β 1 = 258-100 258 = 0.612
β 1 is the discounting factor S and its reliability degree is (1 -β 1 ). So, we apply the discounting operation as follows:

β m Ω RH1 ({S}) = 1 * (1 -β 1 ) = 0.388 β m Ω RH1 (Ω) = β 1 + (1 -β 1 ) * 0 = 0.612
-After that, we calculate the extreme rating degree for R 1 :

γ 1 = 208 258 = 0.806
γ 1 is the discounting factor S and its reliability degree is (1 -γ 1 ). So, we reapply the discounting operation as follows:

γ β m Ω RH1 ({S}) = 0.388 * (1 -γ 1 ) = 0.388 * (1 -0.806) = 0.075. γ β m Ω RH1 (Ω) = γ 1 + (1 -γ 1 )
* 0.612 = 0.925.

Step 3: Modeling the whole reviewer trustworthiness

In the interest of representing the whole trustworthiness for each reviewer, we aggregate the reviewer bba's reputation α m Ω RRi with his helpfulness bba β γ m Ω RHi using the Dempster combination rule (i.e,

m Ω RTi = α m Ω RRi ⊕ β γ m Ω RHi ).
The output of this aggregation is a combined bba m Ω RTi that represents the whole trustworthiness for each reviewer.

Example 4. Once the bba's representing both the R 1 reputation and helpfulness, calculated in the previous example, are combined we obtain the following bba:

m Ω RT1 ({S}) = 0.761 m Ω RT1 ({S}) = 0.018 m Ω RT1 (Ω) = 0.221

Step 4: According Spamicity degree and Making decision

In order to accord a spamicity degree to each reviewer, we resort the pignistic probability BetP . Then, the decision is made either the author is a spammer or innocent as we select the BetP with the greater value as the final decision.

Example 5. After applying the pignistic probability on the bba calculated in the previous Example 4 and, we found:

BetP ({S}) = 0.872 BetP ({S}) = 0.128
The reviewer R 1 is a spammer with a spamicity degree equal to 0.872.

Experimentation and Results

The evaluation in spam reviews detection problem has been always a significant barrier, due to the absence of true real world growth data. A common alternative, used by various previous works, is using human evaluators and experts in order to label the dataset. However, the human judgement may provide varying verdicts due to the variability in perception and tolerance without forgetting the human subjectivity.

In this paper, we conducted experiments on real dataset then we propose to validate our method behavior by analyzing some results.

Evaluation protocol

Dataset description

In order to evaluate our method, we used a real world dataset extracted from Tripadvisor which is composed by 6200 reviews given by 1420 reviewers. The dataset contains; the reviews, the reviewed restaurants or hotels and the reviewing historic corresponding to each reviewer which is detailed in the Table 2. We propose to label our database through one of the most used clustering method K-means where K = 2 in order to divide it into two classes; spammer and non spammer, relying on some important features used in the literature [START_REF] Fei | Exploiting burstiness in reviews for review spammer detection[END_REF] such as:

-Duplicate/Near Duplicate Reviews -Extreme Rating -Reviewing Burstiness -The helpfulness degree -The average mean rating given by each reviewer

Evaluation Criteria

We evaluate our method according to the three following criteria: Accuracy, precision and recall and they can be defined as Eqs.19, 20, 21 respectively where T P , T N , F P , F N denote True Positive, True Negative, False Positive and False Negative respectively.

Accuracy = (T P + T N ) (T P + T N + F P + F N ) (19)
P recision = T P (T P + F N ) (20)

Recall = T P (T P + F N ) (21)

Experimental results

Our method distinguishes between 229 spammers and 1266 genuine reviewers.

We propose to compare it with state-of-art baselines classifier; the Support Vector Machine SVM and the Naive Bayes NB [START_REF] Heydari | Leveraging quality metrics in voting model based thread retrieval[END_REF][START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF][START_REF] Wang | Review graph based online store review spammer detection[END_REF]. The results are reported in the table 3. Our approach accomplishes the best performance according to accuracy, precision and recall over-passing state-of-art methods. It records at best an accuracy improvement over 30% compared to NB and over 26% compared to SVM.

Method behavior validation

In order to analyze our results, we randomly pick a set of ten reviewers from our Tripadvisor dataset. Table 4 details the reviewers information and presents the results generated by our approach. Our method classifies each reviewer as spammer or innocent by according a spamicity degree to each one. The reviewer id = 21012Z is detected as a spammer with a high spamicity degree (i.e.,0.91) since he gives various non helpful reviews to some target products in short time interval including a lot of extreme rating in order to over-qualify or to damage them. However, the reviewer id = 10001E is classified as innocent with a very low spamicity degree as his reviews contain various helpful ones and few extreme rating. Moreover, they are spread along the reviewing time interval and each one is given to only one product. Taking also the reviewer id = 10012B, almost this one is judged as innocent, he has a high spamicity degree (i.e., 0.47) because most of his reviews are given in less than three days including also some extreme rating, however we can not classified as spammer since he also has several helpful vote and he gives average less than two reviews per product. 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, they can control the behavior of the innocent ones with a high spamicity degree to prevent their tendency to turn into spammers.

Conclusion

In this work, we addressed the spammer review detection problem and proposed a novel approach that manages the uncertainty while using the spammer behavior indicators. Our method shows its ability in distinguishing between fake and innocent reviewers while tuning a spamicity degree for each one. As future work, we aim to improve even more our detection by taking into account the semantic aspects through the analysis of the reviews contents.

Table 1 .

 1 Hotel reviews and reviewers information

	Review	Reviewer id	Total number of reviews	Total number of product or services	Number of Extreme rating	Number of helpful votes	Number of reviews given in less than 3 days.
	5*	1	258	30	208	100	200
	4*	2	30	10	8	25	4
	3*	3	20	12	0	18	2
	5*	4	30	16	22	0	15
	4*	8	100	92	10	88	10

Table 2 .

 2 Example of reviewer history

	The reviewer id
	Total number of reviewed
	restaurants and hotels
	Total number of reviews
	The review rating
	The review time
	Number of helpful ratings

Table 3 .

 3 Comparative results

	Methods	Accuracy Precision Recall
	SVM	0.72	0.71	0.70
	NB	0.67	0.64	0.59
	Our Method 0.98	0.96	0.94

Table 4 .

 4 Reviewers information and results

	Reviewer id	Total number of reviews	Total number of product or services	Number of Extreme rating	Number of helpful vote	Number of than 3 days. reviews given in less	Decision	Spamicity Degree
	10012D	258	30	208	100	100	Spammer 0.87
	10013D	30	10	8	25	4	Innocent 0.02
	10021D	20	12	0	18	2	Innocent 0.11
	10010A	30	16	22	0	15	Spammer 0.68
	10012B	16	12	6	10	9	Innocent 0.47
	20012D	40	30	5	32	5	Innocent 0.02
	18012B	30	3	25	0	28	Spammer 0.99
	21012Z	60	5	20	2	50	Spammer 0.91
	10412E	100	92	10	88	10	Innocent 0.01
	10001E	150	150	10	120	15	Innocent 0.01


Amel Ennaceur
email: amelnaceur@yahoo.fr

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Analytical Network Process Method Under the Belief Function Framework

This paper describes a belief extension of the analytic network process (ANP), a multi-criteria prioritization method to model decision making under uncertain context. The approach accommodates the use of qualitative preference relations as input information in the pairwise comparison matrices. Instead of applying the Saaty?s scale in the prioritization process, a new method, based on the belief function theory, is applied. The proposed approach is illustrated by examples.

Introduction

The Analytic Hierarchy Process (AHP) [START_REF] Saaty | A scaling method for priorities in hierarchical structures[END_REF][START_REF] Saaty | The Analytic Hierarchy Process[END_REF] is one of the most widely used multi-criteria decision making method. This approach assumes that the decision making problem can be structured hierarchically, where each element is independent from all the others.

However, in some situations, strong dependencies between inter-level or intralevel elements may exist. To solve this problem, a supermatrix approach [START_REF] Saaty | Decision making with dependence and feedback: The Analytic Network Process[END_REF] was proposed by Saaty, named the Analytic Network Process (ANP). Its main aim is to extend the AHP method to model interactions and feedback.

Like AHP method, the pairwise comparison technique is used to compute ANP method priorities. Each element is then paired and compared using the Saaty's scale. However, due to the uncertainty on the expert assessments, the crisp pairwise comparison technique in the standard AHP and ANP approaches seems insufficient and imprecise to capture the right assessments of decision makers.

As a way to handle this uncertainty, use of fuzzy set theory has been largely suggested in the literature. Accordingly, several fuzzy ANP methods [START_REF] Asan | A fuzzy Analytic Network Process approach[END_REF][START_REF] Mikhailov | Deriving priorities from fuzzy pairwise comparison judgments[END_REF][START_REF] Mikhailov | Fuzzy Analytic Network Process and its application to the development of decision support systems[END_REF] and fuzzy AHP [START_REF] Laarhoven | A fuzzy extension of Saaty's priority theory[END_REF] have been introduced.

In the same way, under the belief function framework, the AHP method has been extended to handle imperfection. Many AHP extensions were introduced [START_REF] Beynon | An expert system for Multi-Criteria Decision Making using Dempster Shafer theory[END_REF][START_REF] Ennaceur | Handling partial preferences in the belief AHP method: Application to life cycle assessment[END_REF][START_REF] Ennaceur | Multi-criteria decision making method with belief preference relations[END_REF]. Therefore, we propose in this research to combine the ANP method and the belief function theory. A new multicriteria decision making technique that is able to represent decision making under uncertain context. This paper is aimed at presenting a Qualitative ANP approach. The proposed method suggests the use of belief preference relations in the supermatrix [START_REF] Ennaceur | Handling partial preferences in the belief AHP method: Application to life cycle assessment[END_REF][START_REF] Ennaceur | Multicriteria decision making based on qualitative assessments and relational belief[END_REF]. We propose to derive meaningful priorities from qualitative decision structures. Instead of applying the Eigenvector method in the prioritization process, a new model, which obtains crisp priorities from qualitative assessments is applied.

In what follows, we first present some definitions needed for belief function theory. Next, we describe the ANP method in section 3. Then, section 4 details our new multicriteria method, and gives an example to show its application. Finally, section 5 concludes the paper.

Belief Function Theory

In this section, we briefly introduce the belief function theory as interpreted by the Transferable Belief Model (TBM). More Details can be found in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Smets | The application of the Transferable Belief Model to diagnostic problems[END_REF][START_REF] Smets | The Transferable Belief Model[END_REF].

Basic concepts

Let Θ be the frame of discernment representing a finite set of elementary hypotheses related to a problem domain, where 2 Θ is the set of all the subsets of Θ [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF].

The belief assignment (bba), denoted by m, represent the impact of a piece of evidence on the different subsets of Θ. A⊆Θ m(A) = 1.

(

The basic belief mass (bbm), denoted m(A), models the part of belief committed exactly to A. The events having positive bbm's are called focal elements, where F(m) ⊆ 2 Θ is the set of all focal elements of the bba m.

Accordantly, a belief function is defined for A ⊆ Θ and A = ∅ as:

bel(A) = ∅ =B⊆A m(B) and bel(∅) = 0. (2)

Decision making

The TBM proposes two level models. First, the credal level where beliefs are entertained and represented by belief functions. Second, the pignistic level where beliefs are used to make decisions and represented by the so called pignistic probabilities, BetP [START_REF] Smets | The application of the Transferable Belief Model to diagnostic problems[END_REF]:

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

(3)

Uncertainty Measures

In the case of the belief function framework, different uncertainty measures (UM) have been defined, such as [11] [12]:

H(m) = A∈F (m) m(A) log 2 ( |A| m(A) ). (4)
The measure H is aimed at assessing the total uncertainty arising in a body of evidence due to both randomness (ignorance and inconsistency) and nonspecificity associated with a bba.

The measure H attains its global maximum when the bba distributes both randomness and nonspecificity uniformly over the largest possible set of focal elements.

Analytical Network Process method

One of the most known multi-criteria decision making approach is the Analytical Network Process (ANP). The originality of ANP lies in its ability to represent complex decision making problems and to involve dependencies and feedbacks between decision elements.

Unlike AHP, ANP makes no assumptions about the independence of higher level elements from lower level elements and about the independence of the elements within a level (see Figure 1). An AHP hierarchy is based on a main objective, a selected criteria, sub-criteria and decision alternatives, but a network model has cycles connecting its clusters of elements (outer dependence) and loops that connect a cluster to itself (inner dependence).

The main steps of ANP are described in what follows [START_REF] Saaty | Decision making with dependence and feedback: The Analytic Network Process[END_REF].

Construction of the network structure

The ANP process starts by constructing the group of elements and clusters that would best model the problem. Indeed, the elements in terms of criteria, sub-criteria and alternatives are defined and clusters of these elements are respectively formed. So, a network is developed based on the relationships between and within these clusters.

Building pairwise comparaison

Like AHP, the pairwise comparison process is used to model the expert preferences and to estimate the local priorities of the selected criteria, sub-criteria and alternatives.

To represent his assessments, the decision maker has to respond to the following question: Given an element (in the same cluster or in another cluster) or a cluster, how much more does a given element (cluster) of a pair influence that element (cluster) with respect to a criterion? Fig. 1. The difference between a hierarchy and a network models [START_REF] Saaty | Decision making with dependence and feedback: The Analytic Network Process[END_REF] The responses to these questions, the expert use the Saaty's scale, where 1 indicates indifference between the two elements and 9 indicates a strong preference of the element under consideration over the comparison element (see Table 1). Once the pairwise comparisons are completed, a local priority vector is derived for all comparison matrices.

To validate the expert judgments', a consistency index is calculated to check the consistency of the pairwise comparisons matrices.

Construction the supermatrix

When all the local priorities are calculated, these are used to form the supermatrix. In this method, each local priority vectors is entered as a part of some column of a matrix (see Figure 2), Fig. 2. An example of one of the supermatrix block matrices [START_REF] Saaty | Decision making with dependence and feedback: The Analytic Network Process[END_REF] where C m denotes the m th cluster with n m elements (e m1 , e m2 , ..., e mn , where e mn represents the n th element in the m th cluster).

W ij is a priority vector representing the impact of the elements in the i th cluster on the elements in the j th cluster (W ij = 0 if there is no influence between the clusters). Figure 3 illustrates a sample example [START_REF] Yu | A soft computing method for multi-criteria decision making with dependence and feedback[END_REF]. The next step, according to Saaty methodology, is to construct the weighted supermatrix using the component matrix to weight the supermatrix previously assembled.

To calculate the weighted supermatrix is a need to make the matrix stochastic. This condition is necessary for obtaining the resulting limit supermatrix. This matrix is calculated elevating the weighted supermatrix to the n th power. This procedure allows capturing the transmission of influences from all the paths of the network. For example, to obtain indirect influences through a third element, the weighted supermatrix must be powered to the square.

Ranking alternatives

The global priorities can be found in the relevant rows of the normalized limit supermatrix and those elements receiving high priorities deserve more attention.

A qualitative ANP approach

ANP is a well-known MCDM method. that has some drawbacks. Like AHP method, ANP uses a predefined scale. This one cannot handle the problem of uncertainty in the evaluation process. Therefore, the expert needs more than 1 -9 scale to express this imperfection.

As already noted, many ANP extensions were proposed such as Fuzzy ANP. It utilizes interval and fuzzy prioritization methods to represent the pair-wise comparisons matrix and to derive interval or fuzzy local priorities [START_REF] Asan | A fuzzy Analytic Network Process approach[END_REF][START_REF] Mikhailov | Deriving priorities from fuzzy pairwise comparison judgments[END_REF][START_REF] Mikhailov | Fuzzy Analytic Network Process and its application to the development of decision support systems[END_REF].

However, our proposed method, which derives belief priorities from qualitative assessments, can be easily applied to increase the capabilities of the ANP for dealing with inconsistent and uncertain judgments.

In the following, we present a new way of comparisons under the ANP approach and we introduce our suggested solution.

Step 1: Network model

Select and define the hierarchy or network structure including clusters, the candidate criteria, sub-criteria and the selected alternatives. Detailed discussions on every criterion, sub-criterion and alternative have been conducted. These data must be carefully collected to assure the reliably of the model.

Step 2: Dependency and feedback

Identify the dependences among all components of the network and list them in a table in order to define the impacts between each.

Step 3: Pairwise comparison matrices

Construct pairwise comparison matrices of the elements with preference relations.

Like standard ANP, the comparison of elements connected to others follows the same principal and method as in AHP. So, each two elements are compared in terms of dominance with respect to a common aspect. Therefore, instead of using Saaty's scale, the responses to the pairwise comparison questions are scaled on the basis of a flexible way using binary preference relations [START_REF] Ennaceur | Multicriteria decision making based on qualitative assessments and relational belief[END_REF].

For example, to compare criteria to the main objective, the corresponding matrix is shown in Table 2 [START_REF] Ennaceur | Multi-criteria decision making method with belief preference relations[END_REF].

Step 4: Local priorities

Derive relative importance weights (local priorities) from the constructed pairwise comparison matrix using the belief prioritizing method.

Transforming belief functions from qualitative assessments and generating quantitative beliefs have been handled by many works [START_REF] Wong | Representation of qualitative user preference by quantitative belief functions[END_REF][START_REF] Ben Yaghlane | Constructing belief functions from expert opinions[END_REF][START_REF] Ennaceur | Modeling qualitative assessments under the belief function framework[END_REF]. In this study, we consider approaches presented in [START_REF] Ben Yaghlane | Constructing belief functions from expert opinions[END_REF] and [START_REF] Ennaceur | Modeling qualitative assessments under the belief function framework[END_REF].

As we have mentioned, to express his assessments, an expert may use the strict preference ( ) or the indifference (∼) or the weak-preference ( ) or unknown relations.

Based on [START_REF] Ennaceur | Modeling qualitative assessments under the belief function framework[END_REF], these relations are transformed into constraints as follows:

where ε is the smallest gap between two degrees of belief. Its value is a constant defined by the decision maker. Similarly to the preference index ε, γ is the indifference threshold.

After modeling the different preference relations, we introduce the preference relations as an optimization problem whose resolution, according to some uncertainty measures (nonspecificity measures, conflict measures, composite measures), allows the generation of the least informative or the most uncertain belief functions. Therefore, each preference relation is transformed into its corresponding constraint as follows. m(e 1i ) = 1; m(a) ≥ 0; ∀e 1i ⊆ Θ; m(∅) = 0.

M ax

(

) 8
where U M is a measure of uncertainty. In this case, we take the measure of uncertainty H as defined equation 4.

The first constraint models the strict preference. The second and third ones represent the weak preference relation. The fourth and fifth constraints are derived from the indifference relation. ε and γ are a constant specified by the decision maker.

The choice of ε and γ affects whether a binary relationship holds. While selecting an appropriate value is not an easy task, because in most cases there are good reasons for choosing non-zero.

Consequently, the obtained bba provide an estimate of the local priorities for the decision elements being compared. Then, the obtained vector has to be transformed into pignistic probabilities (see Equation 3).

Step 5: Consistency

The quality of the estimation of local priorities highly depends on the consistency of judgments that the decision makers performed throughout the pairwise comparisons. At this level, expert has to evaluate the obtained bba. Thus, the proposed method addresses this problem. In fact, if the preference relations are consistent, then the optimization problem is feasible. Otherwise no solutions will be found. Thus, the expert may be guided to reformulate his assessments.

Step 6: Build Supermatrix

Construct the supermatrix with the obtained priorities in order to form an unweighted supermatrix. In this step, each pignistic probabilities (local priority vectors) computed in the step 4 is entered as a part of a relevant column of the supermatrix.

Then, we follow the same steps as standard ANP. We have to normalize the supermatrix to column stochastic to get the sum of the elements in each column is equal to one.

After that, we limit the weighted supermatrix by raising it to a sufficiently large power (where is an arbitrarily large number) until it converges into a stable supermatrix.

Finally, we aggregate the weights of criteria and the scores of alternatives into final priorities by multiplying the scores by the weights of the control criteria.

Conclusion

This paper presents a new method which combines both the AHP approach and the belief function theory to deal with complex decision making problems. Our solution proposes to handle uncertain pairwise comparison judgments. Thus, using preference relations in all pair-wise comparison matrices has facilitated the elicitation process. In fact, our approach suggests an easier elicitation of expert assessments through the reduction of necessary information and using qualitative information rather than exact numbers. At the same time, our approach handles uncertainty by adopting each obtained priority as a basic belief assignment.

As a further work, we propose to consider uncertainty in the supermatrix calculations to represent the uncertainty associated with the cumulative influence of each element on every other element with which it interacts in the network.

Fig. 3 .

 3 Fig. 3. An illustrative example of a network

e 11 e 12 ⇔

 12 bel(e 11 ) -bel(e 12 ) ≥ γ (5) e 11 e 12 ⇔ ε ≤ bel(e 11 ) -bel(e 12 ) ≤ γ (6) e 11 ∼ e 12 ⇔ |bel(e 11 ) -bel(e 12 )| ≤ ε

Table 1 .

 1 The Saaty rating scale

	Saaty's scale	Definition
	1	Equal importance
	3	Somewhat more important
	5	Much more important
	7	Very much more important
	9	Absolutely more important
	2,4,6,8	Intermediate values

Table 2 .

 2 An example of the pairwise comparison matrix

	e11 e12 . . . emn
	e11 -P12 . . . P1n
	e12 --. . . P2n
	. . . ---. . .
	emn ---

-

In this

Table, P ij is a binary relation. It may be: 1. a strong preference relation 2. a weak preference relation 3. an indifference relation ∼ 4. an unknown relation.

  m U M (m) s.t. bel(e 11 ) -bel(e 12 ) ≥ γ ∀(e 11 , e 12 ) for which e 11 e 12 bel(e 11 ) -bel(e 12 ) ≤ γ ∀(e 11 , b) for which e 11 e 12 bel(e 11 ) -bel(e 12 ) ≥ ε ∀(e 11 , e 12 ) for which e 11 e 12 bel(e 11 ) -bel(e 12 ) ≤ ε ∀(e 11 , e 12 ) for which e 11 ∼ e 12 bel(e 11 ) -bel(e 12 ) ≥ -ε ∀(e 11 , e 12 ) for which e 11 ∼ e 12

	e1i∈F (m)


Malika Ben Khalifa
email: malikabenkhalifa2@gmail.com

Zied Elouedi
email: zied.elouedi@gmx.fr

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

Fake reviews detection under belief function framework

Keywords: Online opinions, Fake reviews, Uncertainty, Belief function theory

Online reviews have become one of the most important sources of customers opinions. These reviews influence potential purchasers to make or reverse decisions. Unfortunately, the existence of profit and publicity has emerged fake reviews to promote or demote some target products. Furthermore, reviews are generally imprecise and uncertain. So, it is a difficult task to uncover fake reviews from the genuine ones. In this paper, we propose a fake reviews detection method using the belief function theory. This method deals with the uncertainty in the given rating reviews and takes into account the similarity with other provided votes to detect misleading. We propose numerical examples to intuitively evaluate our method. Then, to prove its performance, we conducted on a real database. Experimentation shows that the proposed method is a valuable solution for the fake reviews detection problem.

Introduction

During the last years, we notice the emergence of the opinions sharing websites such as Amazon.com, Tripadvisor.com, Yelp.com, PriceGrabber.com, Shopzilla.com and Resellerratings.com, which allow people to share their experiences, feelings, attitudes regarding products, services, business and even political issues. Such opinions, straightforwardly influence potential future customers and companies to make or reserve decisions. Consequently, the increasing of positive reviews number will transform their readers to new customers which will provide significant financial gains. Similarly, negative reviews often cause financial losses. Due to the reviews' dominance power, spammers create fake reviews to deteriorate the online reviews systems and confuse the consumers. This spam review does not reflect the real opinion reviewer's and it is intended for misleading reviewers' readers. It may be supportive in order to over qualify a product or a service or destructive to damage the e-reputation of competitors companies.

Therefore, it is crucial to detect fake reviews in order to protect e-commerce form fraudsters' activities, to ensure customers confidence and to maintain companies' fair competition. As a consequence, spam reviews detection became one of the most challenging problems. Researchers have developed various spam detection techniques in which the major task is distinguishing between fake reviews and truthful ones. A largest number of methods and techniques is proposed to detect spam reviews. Most of these works tried to distinguish between fake and true opinions across the linguistic aspects and feeling [START_REF] Deng | Sentiment analysis based online restaurants fake reviews hype detection[END_REF], as well as the style of writing [START_REF] Banerjee | Applauses in hotel reviews: Genuine or deceptive[END_REF][START_REF] Fusilier | Detection of opinion spam with character n-grams[END_REF], and readability and subjectivity [START_REF] Ong | Linguistic characteristics of shill reviews[END_REF]. Some researchers try to catch the group spammers cause of their ability to manipulate the readers' desires, beliefs and consciousness for both product and service. In [START_REF] Mukherjee | Spotting opinion spammers using behavioral footprints[END_REF], the authors have studied this problem by defining a set of eight indicators that try to detect behavior of the group members such as time and rating deviation. Other studies [START_REF] Kolhe | Fake reviewer groups detection system[END_REF] proposed the score candidate groups using the relationship between groups, individuals and products. Other techniques have focused on spammer detection. Most of them are graph based approaches [START_REF] Akoglu | Opinion fraud detection in online reviews by network effects[END_REF][START_REF] Fayazbakhsh | Review spam detection: A network-based approach[END_REF][START_REF] Wang | Review graph based online store review spammer detection[END_REF] with tree types of nodes namely: review, reviewer and stores. The deviation from overall ratings was used as features in [START_REF] Savage | Detection of opinion spam based on anomalous rating deviation[END_REF][START_REF] Sharma | Review spam detector with rating consistency check[END_REF][START_REF] Xue | Trust-aware review spam detection[END_REF] and all these studies have bring a significant results. An algorithm to detect burst patterns in reviews was proposed in [START_REF] Fei | Exploiting burstiness in reviews for review spammer detection[END_REF]. It generated five new spammer behavior features as indicators to used them in review spammer detection. In addition, an other method, proposed in [START_REF] Heydari | Leveraging quality metrics in voting model based thread retrieval[END_REF], used three detection metrics (Context similarity authors' activeness, Authors' rating behavior) to score each review and detect spam ones. Up to our knowledge, no one of the previous works is able to handle uncertainty in reviewers' votes. In fact, the fake reviews detection is an uncertain problem and involves imperfection concerning given reviews. In this context, we propose a novel method, the belief fake reviews detection (BFRD), based on the belief function theory. Indeed, this theory is able to handle uncertainty and allows to deal with partial and total ignorance. It can manipulate various pieces of information from different sources and also take into account their reliabilities through the discounting operation. Moreover, the similarity between the difference given reviews can be taken into account through the distances proposed under belief function framework and especially without forgetting its powerful on decision making under uncertainty. In addition, our proposed method takes into account the case where we have a lack of information and deals with only the overall rating reviews. The remainder of this paper is structured as follows: In Section 2, we present the belief function theory concepts. Then in Section 3, our proposed method named BFRD, is detailed. Experimentation will be proven through the use of the numerical examples in Section 4. Finally, we conclude in Section 5.

Belief Function Theory

The belief function theory was introduced by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] as a model to represent beliefs. It is considered as an efficient tool able to deal with uncertainty and to manage several types of imperfection. Various interpretations have been proposed from this theory, including the Transferable belief model (TBM) [START_REF] Smets | The combination of evidence in the transferable belief model[END_REF] that we adopt in our work. In this section, we elucidate the crucial basic belief concepts, the discounting operation, some combination rules and the decision process.

Basic concepts

The universe of discourse Ω is a finite and exhaustive set of different events associated to a given problem. Its power set 2 Ω contains all possible hypotheses that formed union of events, and the empty set which represents the conflict, defined by: 2 Ω = {A : A ⊆ Ω}. A basic belief assignment (bba) or a belief mass defined as a function from 2 Ω to [0, 1] such that: A⊆Ω m Ω (A) = 1. Each subset A of Ω, having a strictly positive mass m Ω (A) > 0, is considered as the focal element of the bba. In order to express several types of imperfection, some special bbas were defined:

-A certain bba is defined as follows: m Ω ({ω i }) = 1 and ω i ∈ Ω.

-A vacuous bba is defined as follows: m Ω (Ω) = 1 m Ω (A) = 0 ∀A = Ω. This function models the state of the total ignorance. -A categorical bba is defined as follows:

m Ω (A) = 1 ∀A ⊂ Ω and m Ω (B) = 0 ∀B ⊆ Ω B = A.
This bba has a unique focal element A. -A simple support function is defined as follows:

m Ω (X) =      ω if X = Ω 1 -ω if X = A ∀A ⊂ Ω 0 otherwise (1)
where A is the focal element and ω ∈ [0, 1].

Discounting operation

The discounting operation established by [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] allows us to weaken the masses by the discount rate α ∈ [0, 1] such that (1 -α) is the degree of reliability of a source. Accordingly, the discounted bba, noted m α , becomes:

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

Combination Rules

Let m Ω 1 and m Ω 2 two different bbas defined on the same frame of discernment Ω providing by two distinct and cognitively independent reliable sources. There are several combination rules proposed in the belief function framework, each rule has its specificities and its characteristics. Then, we will present some of the most used ones.

1. Conjunctive rule (CRC): Introduced by Smets [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF], it allows to combine two bbas induced by distinct and reliable sources of information. It is denoted by ∩ and defined as:

m Ω 1 ∩ m Ω 2 (A) = B∪C=A m Ω 1 (B)m Ω 2 (C) (3)
The mass assigned to the empty set quantifies the degree of conflict between the two bbas. 2. Dempster's rule of combination: It is the normalized version of the conjunctive rule where it does not support the existence of a mass on the empty set [START_REF] Dempster | Upper and lower probabilities induced by a multivalued map-ping[END_REF]. It is denoted by ⊕ and defined as:

m Ω 1 ⊕ m Ω 2 (A) = m Ω 1 ∩ m Ω 2 (A) 1-m Ω 1 ∩ m Ω 2 (∅) ifA = ∅, ∀A ⊆ Ω, 0 otherwise. (4)
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] act as the conjunctive rule when the bbas are antonym (it keeps the conflict) and as the Dempster rule when the bbas are similar. 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) (5)
where D max represents 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 )], (6)
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 ), ( 7
)
where D is the Jaccard index defined by:

D(E, F ) = 0 if E = F = ∅, |E∩F | |E∪F | ∀E, F ∈ 2 Ω (8)

Decision Making

The decision making step chooses the most suitable hypothesis for a given problem. The Transferable Belief Model (TBM), proposed by [START_REF] Smets | The transferable belief model for quantified belief representation[END_REF], is composed by both the credal level where beliefs are defined by bbas then combined, and the pignistic level where bbas are transformed into pignistic probabilities denoted by BetP and defined as follows:

BetP (B) = A⊆Ω |A ∩ B| |A| m Ω (A) (1 -m Ω (∅)) ∀ B ∈ Ω (9)
3 The belief fake reviews detection (BFRD)

The proposed method, in this paper, deals with fake reviews detection using the belief function tools. In order to distinguish between fake and genuine reviews, this method only requires the overall rating as an input. Given a dataset of N votes that have different values between 1 and 5 stars (respectively poor, below average, average, good and excellent), each vote V i is associated to a reviewer denoted R i where i is the id of the corresponding one. Our method follows four main steps detailed in-depth.

Modeling reviewer's vote by mass functions

As we adopt the belief function theory in order to model conveniently imperfections in votes, each vote V i will be transformed into a mass function (i.e. bba) m Ω i with Ω ={1, 2, 3, 4, 5} where one of the elements in Ω represents the stars' number given by each reviewer R i . We think that the reviewer is either a spammer or a real customer gives an uncertain vote. We propose to model this uncertainty by considering the vote, the vote-1 and the vote+1 for each given overall rating review. In the upper extreme case (i.e. V i = 5), we model the vote and the vote-1 and in the lower one (i.e. V i = 1) we model the vote and the vote+1. We transform each vote value V i given by the reviewer R i into bbas defined as follows:

m Ω ik ({k}) = 1 where k =      V i V i + 1 V i -1
. In the upper extreme case, k = V i V i -1 and in the lower extreme case, k = V i V i + 1 .

Example 1. Let us consider the case of five reviewers given an overall rating review for an hotel detailed in Table 1.

For

R 1 : m Ω 14 ({4}) = 1; m Ω 15 ({5}) = 1; m Ω 13 ({3}) = 1. For R 3 : m Ω 35 ({5}) = 1; m Ω 34 ({4}) = 1. For R 5 : m Ω 51 ({1}) = 1; m Ω 52 ({2}) = 1.
We propose to model the reliability degree of the reviewer R i by (1 -α i ) where α i is its discounting factor. Its value is between [0, 1], if α i = 0 the reviewer is totally reliable and if α i = 1, it means that the reviewer is totally unreliable and it will not be taken into account. We calculate α i as follows:

α i = Number of votes different from the current vote of R i Total votes' number (10)
So, each vote transformed into mass functions is weakened by its relative reliability degree (1 -α i ) using the discounting operation and consequently changed into simple support functions. Thus, the reliability of the reviewer will be taken into consideration.

Example 2. We continue with the previous Example 1, we calculate the reliability factor for R 1 : α 1 = 3 5 = 0.6. After the discounting operation the bbas are transformed into a mass functions as follows: α1 m Ω 14 ({4}) = (1-0.6) * 1 = 0.4; α1 m Ω 14 ({Ω}) = 0.6+(1-0.6) * 0 = 0.6. α1 m Ω 15 ({5}) = 0.4; α1 m Ω 15 ({Ω}) = 0.6. α1 m Ω 13 ({3}) = 0.4; α1 m Ω 13 ({Ω}) = 0.6.

In addition, we propose to model the distance between the i th given vote value denoted by V i and its corresponding modeled values (vote, vote+1 and vote-1) denoted by k and represented by m ik , in order to not consider them in the same way, by (1 -β ik ) where β ik is its discounting factor. Its value is between [0, 1], if β ik = 0 it means that the vote represents the current vote value and if β ik = 1 it means that the vote is so far from the current vote value. The discounting factor β ik is calculated as follows:

β ik = |V i -k| The maximum vote value (11)
Then, each simple support function associated to each vote given by a review is weakened by its relative reliability degree (1 -β ik ) using the discounting operation.

Example 3. Let us consider the same Example 1, we calculate the discount factor β for the R 1 :

β 14 = |4-4| 5 = 0; β 15 = |4-5| 5 = 0.2; β 13 = |4-3| 5
= 0.2. After the second discounting operation, the bbas are transformed as follows:

α1 β14 m Ω 14 ({4}) = 0.4; α1 β14 m Ω 14 ({Ω}) = 0.6. α1 β15 m Ω 15 ({5}) = 0.32; α1 β15 m Ω 15 ({Ω}) = 0.68. α1 β13 m Ω 13 ({3}) = 0.32; α1 β13 m Ω 13 ({Ω}) = 0.68
Finally, we aggregate each three discounted bbas (two in the extreme cases) representing each given vote using the Dempster rule (Eq.4) in order to represent each given vote by one bba containing four focal elements (three in the extreme cases).

Example 4. After aggregating the discounted votes corresponding to R 1 calculated in Example 3 using the Dempster rule, we found:

m Ω 1 = α1 β14 m Ω 14 ⊕ α1 β13 m Ω 13 ⊕ α1 β15 m Ω 15 m Ω 1 ({4}) = 0.255; m Ω 1 ({5}) = 0.180; m Ω 1 ({3}) = 0.180; m Ω 1 (Ω) = 0.
385. Then this bba will represent the vote (4 stars) given by R 1 .

Distance between the current reviewer's vote and all the other votes' aggregation

In order to evaluate the vote provided by each reviewer, we compared it to all other reviewers' vote as follows:

For each reviewer, we aggregate all the other reviewers' votes represented by bbas using the CWAC combination rule (Eq.5) chosen, because it can cope with the conflict in different votes. The output of this combination is one bba m Ω ci , which represents the whole reviewers' votes except the current one as follows:

m Ω ci = m Ω 1 ↔ m Ω 2 ↔ . . . ↔ m Ω i-1 ↔ m Ω i+1 ↔ . . . ↔ m Ω N .
Then, we calculate the distance d(m Ω i , m Ω ci ) using the distance of Jousselme (Eq.7), in order to measure the similarity between each review's vote and all others.

Example 5. We continue with the previous Example 4 where the current vote corresponds to the first reviewer R 1 , so we aggregate all the reviewers' votes except the first one:

m Ω c1 = m Ω 2 ↔ m Ω 3 ↔ m Ω 4 ↔ m Ω 5 . m Ω c1 (∅) = 0.16; m Ω c1 ({1}) = 0.04; m Ω c1 ({2}) = 0.25; m Ω c1 ({3}) = 0.15; m Ω c1 ({4}) = 0.25; m Ω c1 ({5}) = 0.
15. Then, we apply the Jousselme distance between the first reviewer's vote and all the other ones, we found: d(m Ω 1 , m Ω c1 ) = 0.155.

Construction of a new bba modeling the vote into fake or not fake

The distance measured in the previous step represents the degree of compatibility between the vote and all the other ones' which means that more the distance value decreases more the vote is reliable. So, we propose to transform each distance into a new bba with Θ = {f, f } f = fake and f = not fake as the following equation:

       m Θ ({f }) = γ * 1 1+e -a.ds+ a 2 m Θ ({ f }) = γ * (1 - 1 1+e -a.ds+ a 2 ) m Θ (Θ) = 1 -γ (

Decision making

The decision process is made in this final step and assured by the pignistic probability BetP (Eq.10). The BetP with the greater value is considered as the final decision.

Example 7. After applying the pignistic probability on the bba calculated in the previous Example 6, we found: BetP ({f }) = 0.227; BetP ({ f }) = 0.773. Thus, we assume that the vote given by the first reviewer is a genuine one.

Experimentation and results

In the fake reviews detection, the evaluation is one of the most challenging problems considering the unavailability of the labeled dataset because it is not obvious to distinguish between the fake and the real reviews, even with the knowledge of spammers and no spammers. In this paper, we propose to use the numerical examples to intuitively validate our method.

Figure 1 represents the obtained results in four different examples that are detailed in Table 2, where the reviewers judge a hotel by giving rating stars (denoted by * in Table 2). We deal with one standard case and three particular ones, where the given reviews represent five and two majority class rating stars. We can assume that our method provides logical results with different cases. Then, in order to test our BFRD performance, we used a real database extracted from Tripadvisor. The dataset consists of a 1550 reviewers who express their opinion on "Melia Caribe Tropical hotel" by writing reviews, giving an overall, and vote other criteria. Our proposed method detects 967 fake reviews and 583 genuine ones.

Conclusion

In this paper, we addressed the fake reviews detection problem in an uncertain context through the belief function tools. We proposed to handle uncertainty in the given rating reviews and to evaluate them through their compatibility with all others. In fact, our new method shows effectiveness in distinguishing between the fraudulent reviews and the honest ones. Moreover, this approach can be applied in several fields such as e-commerce and e-business. As future work, we will integrate some other notions like reviewers' trustiness.

  12) with ds = d(m Ω i , m Ω ci ), a = 10 and γ = The standard deviation of all votes The maximum value of the standard deviation Example 6. We transform the Jousselme distance d(m Ω 1 , m Ω c1 ) calculated in the previous Example 5 into a new bba with Θ = {f, f }, we found: m Θ ({f }) = 0.018; m Θ ({ f }) = 0.562; m Θ (Ω) = 0.42.

Fig. 1 .

 1 Fig. 1. The numerical examples' results

Table 1 .

 1 Hotel reviews

	Reviewer Vote
	R1	4 stars
	R2	4 stars
	R3	5 stars
	R4	3 stars
	R5	1 star

Table 2 .

 2 The numerical examples' results

	The numerical		Opinion	Fake rating stars Not fake rating
	examples				stars
		Rating Stars Number of reviewers
		5*	5
	Example 1	4* 3*	5 5	-	5*, 4*, 3*, 2* and 1*
		2*	5
		1*	5
		5*	5
	Example 2	4*	5	-	5* and 4*
	Example 3	5* 1*	5 5	-	5* and 1*
		4*	4
		5*	2
	Example 4	3*	2	2* and 1*	4*, 5* and 3*
		2*	1
		1*	1