6. 1. BELIEF THEORY: BASIC CONCEPTS pages are ranked with respect to their degree of be- lief and a classical technique(support pruned cri- Evidence theory is a powerful tool to handle terion 6)is used to prune the pages that have low problems with uncertain and imprecise data. It upport in the learning database. In other words, was introduced by Dempster and Shafer [15.a to each pair(A, u), a weight P(A, u)is associated reference set U, called universe of the Discourse hich gives the strength of the following assertion: or equally frame of discernment is introduced. It In a session 3, such that < s >= ul,,un represents a set of mutually exclusive alternatives, if A S<s> then u E< s>. p(A, u conveys for instance all the possible values of an attribute. the strength of the relation characterized by the simultaneous presence of the resources of A and u deFinition 4 Let u be a universe of the Dis within a given session. Thus P(A, u) is the condi course. A function m: 24-[0, 1] is called a basic tional probability of u knowing A. If the confidence probability assignement over l if of the rule A= u is not zero, P(A, u)matches (1)m()=0 with the confidence in the rule A= u. Otherwise P(A, u) is set to zero. During a training phase, the values of p(A, u) are pre-computed for given min- imum support minsup and minimum confidence minconf. To each pair (u,)E(u, P(U))the fol- The amount m(A)is called basic value of the lowing weight is associated probability m(A) associated with the event A.It measures the strength of the belief that A will oc- mn(u)=cmf(→{ua) cur. A focal element of a belief function Bel is any subset A Cu such that m(a)>0 and the core In order to respect condition(2)of definition 4 of Bel is the union set of all its focal elements. To it is necessary to normalize: represent the reasons to believe in A, all the quan- tities m(B) such that b C A must be added to m(a) m(A). This leads to define cu mu(e) DEFINITION 5 Let l be a frame of discernment and m be a basic probability assignement over l Thus, coefficients mu are basic probability assign- A belief function over l is a function Bel ments, The valuated recommendation function as- 0,1 defined by sociated with Sce algorithm is the following belief function: Bel(A)=∑m(B Recce(S,u)= w C<s> 6.2. Suggestions by Cumulative Evidence 0 otherwise To each page a hashtable is associated. A key The proposed method relaxes the consecutively for this hashtable is a frequent set w and its cor- hypothesis of the pages within a session. Thus it responding value mu(u), is recorded if it is differ can take into account all the transactions previ- ent from 0. As the model depends on minimum ously occurred in the session. The proposed ap- support and minimum confidence thresholds proach, called Suggestions by Cumulative evidence easily tunable to reach a reasonable size (SCE)is based on the idea that all previously seen pages and their combinations must play a role in the link recommendation decision process. 7. EVALUATION METRICS After a suitable aggregation of all the evidence suggesting that a resource is connected to oth- Recall, precision and coverage measures are gen- ers, the global information on each resource should erally used to assess the efficiency of ORS 3, 16 creases. Thus, for each admissible resource, a However, these measures do not necessarily char- degree of belief that this page may interest the acterize the intent of LRS. In this section,new user, with regard to his history is computed. Then, criteria intended to represent LRS are introduced5 6.1. BELIEF THEORY: BASIC CONCEPTS Evidence theory is a powerful tool to handle problems with uncertain and imprecise data. It was introduced by Dempster and Shafer [15]. A reference set U, called universe of the Discourse or equally frame of discernment is introduced. It represents a set of mutually exclusive alternatives, for instance all the possible values of an attribute. DEFINITION 4 Let U be a universe of the Dis￾course. A function m : 2 U → [0, 1] is called a basic probability assignement over U if: (1) m(∅) = 0 (2) X A⊆U m(A) = 1 The amount m(A) is called basic value of the probability m(A) associated with the event A. It measures the strength of the belief that A will oc￾cur. A focal element of a belief function Bel is any subset A ⊂ U such that m(A) > 0 and the core of Bel is the union set of all its focal elements. To represent the reasons to believe in A, all the quan￾tities m(B) such that B ⊂ A must be added to m(A). This leads to define: DEFINITION 5 Let U be a frame of discernment, and m be a basic probability assignement over U. A belief function over U is a function Bel : 2 U → [0, 1] defined by: Bel(A) = X B⊆A m(B) (1) 6.2. Suggestions by Cumulative Evidence The proposed method relaxes the consecutively hypothesis of the pages within a session. Thus it can take into account all the transactions previ￾ously occurred in the session. The proposed ap￾proach, called Suggestions by Cumulative Evidence (SCE) is based on the idea that all previously seen pages and their combinations must play a role in the link recommendation decision process. After a suitable aggregation of all the evidence suggesting that a resource is connected to oth￾ers, the global information on each resource should increases. Thus, for each admissible resource, a degree of belief that this page may interest the user, with regard to his history is computed. Then, pages are ranked with respect to their degree of be￾lief and a classical technique (support pruned cri￾terion [6]) is used to prune the pages that have low support in the learning database. In other words, to each pair (A, u), a weight p(A, u) is associated which gives the strength of the following assertion: ”In a session →−s , such that < s >=< u1, .., un >, if A ⊆< s > then u ∈< s >”. p(A, u) conveys the strength of the relation characterized by the simultaneous presence of the resources of A and u within a given session. Thus p(A, u) is the condi￾tional probability of u knowing A. If the confidence of the rule A ⇒ u is not zero, p(A, u) matches with the confidence in the rule A ⇒ u. Otherwise, p(A, u) is set to zero. During a training phase, the values of p(A, u) are pre-computed for given min￾imum support minsup and minimum confidence minconf. To each pair (u, w) ∈ (U,P(U)) the fol￾lowing weight is associated: m0 u (w) = conf(w ⇒ {u}) In order to respect condition (2) of definition 4 it is necessary to normalize: mu(w) = m0 u (w) P z⊆U m0 u (z) Thus, coefficients mu are basic probability assign￾ments. The valuated recommendation function as￾sociated with SCE algorithm is the following belief function: RecSCE(→−s , u) = X w⊆<s> mu(w) = 0 otherwise To each page a hashtable is associated. A key for this hashtable is a frequent set w and its cor￾responding value mu(w), is recorded if it is differ￾ent from 0. As the model depends on minimum support and minimum confidence thresholds, it is easily tunable to reach a reasonable size. 7. EVALUATION METRICS Recall, precision and coverage measures are gen￾erally used to assess the efficiency of ORS [3,16]. However, these measures do not necessarily char￾acterize the intent of LRS. In this section, new criteria intended to represent LRS are introduced