《电子商务 E-business》阅读文献：link recommender systems- the suggestions by cululative evidence approach

Link recommender systems: The suggestions by Cumulative evidence A proach ean-Yves delort a, bernadette bouchon- Meunier a Computer Science Laboratory(LIP6) Paris 6 University 8, rue du Capitaine Scott 75015 Paris, France E-mail: JJean-Yoes. Delort, Bernadette. Bouchon-Meunierl alip6 fr The increasing interest of website designers in customization technologies has stimulated recommender system researches. This paper deals with link recommender systems(LRS). LRS are tools intended to support and assist the users during their navigation on the Internet or on a specific website. lrs differ from object recommender systems(ORS) which are tools intended to make the user buy or access resources. If ORS efficiency depends on the number of times the users have followed the recommendation proposed by the system, LrS can neither be evaluated nor compared, with respect to this only criteria. LRS suffer from the uncertainty of the available information about the user navigation behaviors and preferences. This paper introduces a new LRS intended to take this uncertainty into account in the recommendation process. Then, the issue of the evaluation of lrs is addressed and a some general features of LRS are put forward and discussed. Then, the proposed approach is compared with two other link recommendation algorithms. The proposed approach provides good results when evaluated with respect to ORS criteria and appears to be the best tested approach in the context of link recommendation Keywords: Recommender systems, Links, Uncertainty 1 INTRODUCTION areoftenusedbyretailerssuchasamAzon.com, to suggest future purchases. The purposes of LRS The increasing interest of website designers in are different. LRS aim at supporting or assisting customization technologies has stimulated recom- users when they are browsing on a specific web- mender system researches(RS). Online recom- site or on the Internet. For instance. a lrs coule be designed to help the users not to get lost when menders can be distinguished into two categories: they are browsing in a large and depth website. In Object recommender systems(ORS)and Link rec- this paper, we focus on LRS intended to a support ommender systems(LRS). ORS aim at providing user while they are browsing on a given website suggestions on a set of resources such as products or news. They are intended to motivate or encour The evaluation process of LRs is more complex than the ors one Indeed OrS can be evaluated age users to follow them. Then, a set (or a lis with respect to their ability to predict the next of related objects matching the user's current in- user clicks. This ability can be precisely and easily terests is proposed. Preferences are often, but not computed. Conversely, LRS are harder to compar for instance, to which extent a Rs helps the user ambiguous(i.e. the users intents or preferences can to feel comfortable on the website and not to get lost on it? ser votes in favor of, or against the objects. For In general, the making of user profiles and the instance, if a user buys a product, this is very likely extraction of user's preferences is based on a pre- to mean a user implicit vote in favor of the it. ORs processing step taking as an input the transaction Jean-Yves Delort. All rights reserved

1 Link Recommender Systems: The Suggestions by Cumulative Evidence Approach Jean-Yves Delort a , Bernadette Bouchon-Meunier a a Computer Science Laboratory (LIP6) Paris 6 University 8, rue du Capitaine Scott 75015 Paris, France E-mail: {Jean-Yves.Delort,Bernadette.Bouchon-Meunier}@lip6.fr The increasing interest of website designers in customization technologies has stimulated recommender system researches. This paper deals with link recommender systems (LRS). LRS are tools intended to support and assist the users during their navigation on the Internet or on a specific website. LRS differ from object recommender systems (ORS) which are tools intended to make the user buy or access resources. If ORS efficiency depends on the number of times the users have followed the recommendation proposed by the system, LRS can neither be evaluated, nor compared, with respect to this only criteria. LRS suffer from the uncertainty of the available information about the user navigation behaviors and preferences. This paper introduces a new LRS intended to take this uncertainty into account in the recommendation process. Then, the issue of the evaluation of LRS is addressed and a some general features of LRS are put forward and discussed. Then, the proposed approach is compared with two other link recommendation algorithms. The proposed approach provides good results when evaluated with respect to ORS criteria and appears to be the best tested approach in the context of link recommendation. Keywords: Recommender systems, Links, Uncertainty 1. INTRODUCTION The increasing interest of website designers in customization technologies has stimulated recom￾mender system researches (RS). Online recom￾menders can be distinguished into two categories: Object recommender systems (ORS) and Link rec￾ommender systems (LRS). ORS aim at providing suggestions on a set of resources such as products or news. They are intended to motivate or encour￾age users to follow them. Then, a set (or a list) of related objects matching the user’s current in￾terests is proposed. Preferences are often, but not necessarily, explicit votes. When behaviors are not ambiguous (i.e. the users intents or preferences can easily be understood) they will be interpreted as user votes in favor of, or against the objects. For instance, if a user buys a product, this is very likely to mean a user implicit vote in favor of the it. ORS are often used by retailers, such as Amazon.com, to suggest future purchases. The purposes of LRS are different. LRS aim at supporting or assisting users when they are browsing on a specific web￾site or on the Internet. For instance, a LRS could be designed to help the users not to get lost when they are browsing in a large and depth website. In this paper, we focus on LRS intended to a support user while they are browsing on a given website. The evaluation process of LRS is more complex than the ORS one. Indeed ORS, can be evaluated with respect to their ability to predict the next user clicks. This ability can be precisely and easily computed. Conversely, LRS are harder to compare: for instance, to which extent a RS helps the user to feel comfortable on the website and not to get lost on it? In general, the making of user profiles and the extraction of user’s preferences is based on a pre￾processing step taking as an input the transaction Jean-Yves Delort. All rights reserved

set recorded by the Hypertext Transfer Protocol A frequent assumption with LRS is that a user server. This leads. because of the draw ccess to a page implies an implicit vote in fa- backs of this protocol, to an uncertain represent vor of this page. LRS approach is more general tion of the user 's behavior and of his choices han the object one, and such Rs can be deployed This paper makes the following contributions: on any website because algorithms just need al- First SCE, an original link recommendation algo- ways available data. Mobasher et al. [12 pioneered rithm that handles uncertainty in user sessions is LRS research. They proposed two LRS algorithms. presented. It is based on Dempster-Shafer theory The former uses frequent association rules between of evidence [15. Then, general features of LRS are URLs within the same sessions. while the latter introduced and discussed. One of their advantage clusters similar user sessions. However the algo- is that they can be expressed as numerical values rithms they proposed have not been evaluated nor which can be compared. Finally, the proposed al- any evaluation methodology has been proposed gorithm is compared with two other link recom- Letizia [11] is an agent to assist users when they are browsing on the Internet. The system com- evaluation criteria s well as with the new ones. The bines two different recommendation strategies: In proposed approach is shown to provide good re- one hand it tries to predict the next user clicks and sults when evaluated with respect to ORs criteria on the other hand it takes into account heuristics and appears to be the best tested approach in the inferring user interests from their browsing behav context of link recommendation Breese 3 and Spiekerman [16 have introduced 2. RELATED WORKS alternate evaluation strategies for ORS. Yet, the proposed approaches were still highly connected to the abilities of the rs to make accurate predic Recommender systems tend to be distinguished tions. On the contrary, the issue of the LRS eval- into two classes: content-based RS use the con- uation implies cognitive factors. For instance to tent of the items(or some information related to which extent a rS helps the user to feel comfort them)to suggest links or objects(for instance the able on the website and not to get lost on it textual content or metadata such as annotations) Collaborative RS are trying to find similarities be- At the same time of Rs researches. the out. comes of works on prefetching have highlighted tween the users' behaviors and interests in order the efficiency of user navigation models on a to decide which recommendations to make. Exam- web site. Prefetcher systems try to predict the ples of content-based RS are search engines and examples of collaborative RS are the Alexa! sys- next resources that a visitor will request immedi- tem or the groupLens system [10. Alexa is also ately after. This can be very efficient if the pages an example of LRS: it provides a"What's re- are dynamically made because they can be pre- lated"service that suggests Web pages or web- generated Prefetcher objectives are closed to ORS sites with respect to common points discovered be but surprisingly they have not been used for a rec- tween the user's behavior and the database of all ommendation purpose. In this paper an interest the alexa users' navigation behaviors Another ex into one of the most used and efficient user nav- ample of collaborative RS, but of the Ors kind igation model is taken. The markovian approach is the grouplens project that recommends mes- has been extensively studied as a user navigation model(14,6, 13. It is based on a graph the states of ges in a newsgroup. The Surfen [7] project is a which represent the last k resources accessed by a RS close to Alexa. Each client sends to a server its navigation history. Then a recommendation engine uses the whole user browsing history database to compute recommendations and send them back to link with respect to the k last pages he has seen. the clients. Balabanovic [2 has proposed an ORS The main drawback of this statistical representa ing advantage of the content as well, ning at tak- tion is its extreme memory complexity when k and ased on a collaborative algorithm ai the number of pages increases. However this pa- per will also demonstrated that this approach is efficient when used by an ORs

2 set recorded by the Hypertext Transfer Protocol (HTTP) server. This leads, because of the draw￾backs of this protocol, to an uncertain representa￾tion of the user’s behavior and of his choices. This paper makes the following contributions: First SCE, an original link recommendation algo￾rithm that handles uncertainty in user sessions is presented. It is based on Dempster-Shafer theory of evidence [15]. Then, general features of LRS are introduced and discussed. One of their advantage is that they can be expressed as numerical values which can be compared. Finally, the proposed al￾gorithm is compared with two other link recom￾mendation algorithms with respect to the ORS evaluation criteria s well as with the new ones. The proposed approach is shown to provide good re￾sults when evaluated with respect to ORS criteria and appears to be the best tested approach in the context of link recommendation. 2. RELATED WORKS Recommender systems tend to be distinguished into two classes: content-based RS use the con￾tent of the items (or some information related to them) to suggest links or objects (for instance the textual content or metadata such as annotations). Collaborative RS are trying to find similarities be￾tween the users’ behaviors and interests in order to decide which recommendations to make. Exam￾ples of content-based RS are search engines and examples of collaborative RS are the Alexa1 sys￾tem or the GroupLens system [10]. Alexa is also an example of LRS: it provides a “What’s re￾lated” service that suggests Web pages or web￾sites with respect to common points discovered be￾tween the user’s behavior and the database of all the Alexa users’ navigation behaviors. Another ex￾ample of collaborative RS, but of the ORS kind, is the GroupLens Project that recommends mes￾sages in a newsgroup. The Surflen [7] project is a RS close to Alexa. Each client sends to a server its navigation history. Then a recommendation engine uses the whole user browsing history database to compute recommendations and send them back to the clients. Balabanovic [2] has proposed an ORS based on a collaborative algorithm aiming at tak￾ing advantage of the content as well. 1http://www.alexa.com A frequent assumption with LRS is that a user access to a page implies an implicit vote in fa￾vor of this page. LRS approach is more general than the object one, and such RS can be deployed on any website because algorithms just need al￾ways available data. Mobasher et al. [12] pioneered LRS research. They proposed two LRS algorithms. The former uses frequent association rules between URLs within the same sessions, while the latter clusters similar user sessions. However the algo￾rithms they proposed have not been evaluated nor any evaluation methodology has been proposed. Letizia [11] is an agent to assist users when they are browsing on the Internet. The system com￾bines two different recommendation strategies: In one hand it tries to predict the next user clicks and on the other hand it takes into account heuristics inferring user interests from their browsing behav￾ior. Breese [3] and Spiekerman [16] have introduced alternate evaluation strategies for ORS. Yet, the proposed approaches were still highly connected to the abilities of the RS to make accurate predic￾tions. On the contrary, the issue of the LRS eval￾uation implies cognitive factors. For instance to which extent a RS helps the user to feel comfort￾able on the website and not to get lost on it? At the same time of RS researches, the out￾comes of works on prefetching have highlighted the efficiency of user navigation models on a web site. Prefetcher systems try to predict the next resources that a visitor will request immedi￾ately after. This can be very efficient if the pages are dynamically made because they can be pre￾generated. Prefetcher objectives are closed to ORS but surprisingly they have not been used for a rec￾ommendation purpose. In this paper an interest into one of the most used and efficient user nav￾igation model is taken. The markovian approach has been extensively studied as a user navigation model[14,6,13]. It is based on a graph the states of which represent the last k resources accessed by a user called active windows. Transition matrix ex￾presses the probability that a user will click on a link with respect to the k last pages he has seen. The main drawback of this statistical representa￾tion is its extreme memory complexity when k and the number of pages increases. However this pa￾per will also demonstrated that this approach is efficient when used by an ORS

3. UNCERTAIN DATA of the IP address is not sufficient to know exactly if the user is a single person or not. Indeed, if the 3.1. Hypertert Transfer Protocol terminal is used by more than one person, or a set of users access the Internet via a gateway, the One of the reasons of the success and popularity Ip address recorded by the Http server will be of the Internet is probably that the mainly used the same. In the sequel, we will use indistinctly protocol Http lets the users remain anonymous the terms user and client to refer to any terminal As a counterpart of this, if we want to add person- that makes requests to a server and which can be cause available data on the users are scarce. fur- To relieve the load of the server, a request is thermore,ashttpdoesnotmaintainpersistentmadeonlyiftheresourceisneitherintheclient connection, it is neither possible to know what the cache nor in a proxy server or the document needs page the user is currently viewing nor it is possible to be refreshed. Thus, nothing guarantees that to be sure that the user is still viewing a page of some pages have been accessed more than once, the website or that some urls not recorded in the log file With the introduction of client-side stored in- have been accessed. The cache client keeps in mem- formation(the cookies)user profiling has become ory the previously seen pages in order not to have possible. Nevertheless, due to privacy reasons the to require resources that have recently been ac- right of using cookies depends on the user ac- cessed. In the same vein, proxy servers act like a ceptance. Yet, the users are often reluctant to be unique shared client cache among a set of users. tracked while they are browsing on a website. A Provided one of the users accessed the resources great deal of personalization services use the link they will be directly sent to any other users con- structure (the dependency graph), the resources nected to the same proxy and who is willing to and meta-descriptions(if they exist), and above access these same documents. These transaction allthehttpuseraccesslogfileeaChlineofit vill not be reported to the Web server. Thanks to contains the minimum pieces of information for a the local cache and the proxy servers, the number transaction between a client and the server to oc- of requests is tremendously reduced. However this cur. It is described by, at least 1 performance improvement has a cost: it goes with a loss of information since the moves and current the client ip addres positions in the website of the users are then un- the requested URL the protocol version, the transaction status2 Finally, another problem comes from the fact that the users never explicitly vote for or against the resources they access. The starting point is Depending on the Http protocol version ad- thus to choose a way to decide whether he liked ditional information can be sent, such as the re them or not, with respect to his behavior. The gen- FERRER which indicates the previous resource erally accepted hypothesis is to consider that each accessed by a user on his browser before his last time a document is accessed it means an implicit request. The REFERRER is an interesting data vote in favor of it which can be used to improve the retrieving pro- cess of the user accessed pages 4. USER SESSIONS 3. 2. Uncertain data 4. 1. Notations Because of dynamic IP addressing, it is not al- ways possible to recognize a user because he may A resource domain referrers to a set of ccessible by users and is denoted by l. A ses- ferent IP addresses. Besides, the unique knowledge sion is a suite of transactions which have occurred for some time between a client and a server. A A number. for instance 200 for OK 200" and 404 for ransa can be ented by a tuple t Not found404” (ID, URL, DATE,.where t ID is the user id

3 3. UNCERTAIN DATA 3.1. Hypertext Transfer Protocol One of the reasons of the success and popularity of the Internet is probably that the mainly used protocol, HTTP lets the users remain anonymous. As a counterpart of this, if we want to add person￾alization services to a website, we are bridled be￾cause available data on the users are scarce. Fur￾thermore, as HTTP does not maintain persistent connection, it is neither possible to know what the page the user is currently viewing nor it is possible to be sure that the user is still viewing a page of the website. With the introduction of client-side stored in￾formation (the cookies) user profiling has become possible. Nevertheless, due to privacy reasons the right of using cookies depends on the user ac￾ceptance. Yet, the users are often reluctant to be tracked while they are browsing on a website. A great deal of personalization services use the link structure (the dependency graph), the resources and meta-descriptions (if they exist), and above all, the HTTP user access log file. Each line of it contains the minimum pieces of information for a transaction between a client and the server to oc￾cur. It is described by, at least [1]: – the client IP address, – the requested URL, – the protocol version, – the transaction status2 , – the date and time. Depending on the HTTP protocol version ad￾ditional information can be sent, such as the RE￾FERRER which indicates the previous resource accessed by a user on his browser before his last request. The REFERRER is an interesting data which can be used to improve the retrieving pro￾cess of the user accessed pages. 3.2. Uncertain data Because of dynamic IP addressing, it is not al￾ways possible to recognize a user because he may have accessed the same website by means of dif￾ferent IP addresses. Besides, the unique knowledge 2A number, for instance 200 for ”OK 200” and 404 for ”Not Found 404”. of the IP address is not sufficient to know exactly if the user is a single person or not. Indeed, if the terminal is used by more than one person, or a set of users access the Internet via a gateway, the IP address recorded by the HTTP server will be the same. In the sequel, we will use indistinctly the terms user and client to refer to any terminal that makes requests to a server and which can be labeled with a unique identifier. To relieve the load of the server, a request is made only if the resource is neither in the client cache nor in a proxy server or the document needs to be refreshed. Thus, nothing guarantees that some pages have been accessed more than once, or that some URLs not recorded in the log file have been accessed. The cache client keeps in mem￾ory the previously seen pages in order not to have to require resources that have recently been ac￾cessed. In the same vein, proxy servers act like a unique shared client cache among a set of users. Provided one of the users accessed the resources, they will be directly sent to any other users con￾nected to the same proxy and who is willing to access these same documents. These transaction will not be reported to the Web server. Thanks to the local cache and the proxy servers, the number of requests is tremendously reduced. However this performance improvement has a cost: it goes with a loss of information since the moves and current positions in the website of the users are then un￾certain. Finally, another problem comes from the fact that the users never explicitly vote for or against the resources they access. The starting point is thus to choose a way to decide whether he liked them or not, with respect to his behavior. The gen￾erally accepted hypothesis is to consider that each time a document is accessed it means an implicit vote in favor of it. 4. USER SESSIONS 4.1. Notations A resource domain referrers to a set of resources accessible by users and is denoted by U. A ses￾sion is a suite of transactions which have occurred for some time between a client and a server. A transaction can be represented by a tuple t = (ID,URL, DATE, ...) where t.ID is the user id

t URL is the requested URL and t DATE is the ion. In this situation. the user will be considered transaction time. These three data uniquely iden- to be still present on the site. Then s is called an tify any possible transaction. In the sequel, the active session and the user will be said to be ar letters t and u will be used when dealing with active user transactions and resources respectively. de- notes the set of all possible sequences of consecu- tive transactions ofl. We call length of the session 5. RECOMMENDATION ALGORITHMS s, and we note s the length of the sequence t1,..., tn > The symbol is an abbrevia- We call recommendation function any proce tion of the sequence taking as an input a session s and giving as an 4.2. User sessions DEFINITION 1 A recommendation function on a The concept of user session is often used to re- resource domain l is a multivaluated function fer to the relations between the users information 3→P( needs and their interactions: it represents a set of accessed pages related to the same search activ- 3一→Rec()={u1,…p} ity. Most session boundaries detection algorithms The set Rec(s)is called the recommendation of are based on a time constraint between the access the session s time of the resources within the same session 9, 4 Recommendation processes are often based on Content-based approach have also been proposed a function that associates a weight with each re- Generally, the cohesion between the elements source of u. This weight conveys the degree of like- within a session depends on four relations linking liness that the resource is a good or a bad recom mendation the transactions together 1. all the transactions where request by the DEFINITION 2 Given a domainu, s the set of u. a valuated recommendation 2. all URLs belong to the same resource do- function is a function Recval defined by (3×l4)→→[0,1 3. the transactions occurred in a row and 4. there exists an additional temporal relation (s,u)→ Rectal(s,u) The value RecVal(s, u) is called weight of the Usually the last condition comes down to a max- recommendation of u. A recommendation is a set imum time span between the transactions. It can of pages ofl having the highest Recval value be To-static, if the time span between the first to When a recommender system cannot give a re and the last accessed document t cannot exceed a given number To of seconds ommendation, then it outputs the empty set deFINITION 3 Given a domain l, a recommen- tn DATE≤to.DATE+7o dation function Rec and that a recommendation succeeds if It can also be chosen T1-dynamic which means that the time span between two consecutive transac- Rec(3)≠ tions cannot exceed a given number Ti of seconds vi=2.n,t计+1.DATE≤ ti DATE+n1 6. MANAGING UNCERTAINTY WITH EVIDENCE THEORY Let s = be a user session, sup- pose that a new request tp+l occurres, then the In this section the fundamentals of evidence the. concatenation of sequences of transactions s and ory are outlined. Then, the Suggestion by Cumu ,denoted by s. is still a ses- lative Evidence(SCe) algorithm is introduced

4 t.URL is the requested URL and t.DATE is the transaction time. These three data uniquely iden￾tify any possible transaction. In the sequel, the letters t and u will be used when dealing with transactions and resources respectively. de￾notes the set of all possible sequences of consecu￾tive transactions of U. We call length of the session →−s , and we note |→−s | the length of the sequence . The symbol is an abbrevia￾tion of the sequence . 4.2. User sessions The concept of user session is often used to re￾fer to the relations between the users’ information needs and their interactions: it represents a set of accessed pages related to the same search activ￾ity. Most session boundaries detection algorithms are based on a time constraint between the access time of the resources within the same session [9,4]. Content-based approach have also been proposed [5]. Generally, the cohesion between the elements within a session depends on four relations linking the transactions together: 1. all the transactions where request by the same user, 2. all URLs belong to the same resource do￾main, 3. the transactions occurred in a row and 4. there exists an additional temporal relation on the transactions. Usually the last condition comes down to a max￾imum time span between the transactions. It can be τ0-static, if the time span between the first t0 and the last accessed document tn cannot exceed a given number τ0 of seconds: tn.DATE ≤ t0.DATE + τ0 It can also be chosen τ1-dynamic which means that the time span between two consecutive transac￾tions cannot exceed a given number τ1 of seconds: ∀i = 2..n, ti+1.DATE ≤ ti .DATE + τ1 Let →−s = be a user session, sup￾pose that a new request tp+1 occurres, then the concatenation of sequences of transactions →−s and , denoted by →−s . is still a ses￾sion. In this situation, the user will be considered to be still present on the site. Then →−s is called an active session and the user will be said to be an active user. 5. RECOMMENDATION ALGORITHMS We call recommendation function any process taking as an input a session →−s and giving as an output a subset (possibly empty) of U. DEFINITION 1 A recommendation function on a resource domain U is a multivaluated function: →− S −→ P(U) →−s 7−→ Rec(→−s ) = {u1, .., up} The set Rec(→−s ) is called the recommendation of the session →−s . Recommendation processes are often based on a function that associates a weight with each re￾source of U. This weight conveys the degree of like￾liness that the resource is a good or a bad recom￾mendation. DEFINITION 2 Given a domain U, →− S the set of all the sessions on U, a valuated recommendation function is a function RecV al defined by: RecV al : ( →− S × U) −→ [0, 1] (→−s , u) 7−→ RecV al(→−s , u) The value RecV al(→−s , u) is called weight of the recommendation of u. A recommendation is a set of pages of U having the highest RecV al value. When a recommender system cannot give a rec￾ommendation, then it outputs the empty set. DEFINITION 3 Given a domain U, a recommen￾dation function Rec and a session →−s , we will say that a recommendation succeeds if: Rec(→−s ) 6= ∅ 6. MANAGING UNCERTAINTY WITH EVIDENCE THEORY In this section the fundamentals of evidence the￾ory are outlined. Then, the Suggestion by Cumu￾lative Evidence (SCE) algorithm is introduced

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 = ul,,un represents a set of mutually exclusive alternatives, if A S then u E. 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 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 introduced

5 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 =, if A ⊆ then u ∈”. 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⊆ 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

and modelized DEFiNITiON 7 Let l be a resource domain. Rec a sake of simplicity, assume that s, = t1,…,tn> is a session and p≤n, then RecP w a session. Let us consider a prefix of s, t1, . ti> with l n, the so-called degree of sta- ility of re c on ne sesszon s between t and tu+1 7. 1. RECALL PRECISION AND COVERAGE s defined by the number. The following definition sums up sical evaluation measures used when evalua ORS maz(lRec! l, Recs+D Previous works on prefetching have discovered DEFINITION 6 Let l be a resource domain, Rec a recommendation function, s a session of size n a relation between the frequency of requests te Web documents and their rank of popularity, it and l0 then: Pwc- with B typically close to 1. Such dis- tributions imply that, usually, few resources con- The validity of Rec! is given by centrate the interest of the users it can be ex pected that the pages recommended by a lrs do val( Recd)=Rec! n(tu+1, . tn) not differ too much from this law. It is important that the pages well ranked by their frequency are also recommended in a high proportion. The Most A covered recommendation is said precise if: Frequent Pages ratio is thus defined by the num- ber of frequently recommended pages over the to val(recs)>0 tal number of recommended pages. However, a RS cannot only focus on most frequent The recall of a covered recommendation i pages because useful information is not always contained in most frequent pages. The Kullback- val(Red Leibler divergence(KLD)is well suitable to as- Recal sess the difference between the distributions of the accessed and recommended pages. To compute The coverage (resp. precision )of a set of he KLD, the probabilities Plearn(u) are computed mendations is the average number of recommenda- over the learning database that expresses the prob- tions which were covered (resp. precise). The recall bility that a page u will be requested. During of a set of recommendations is the mean of their the testing step, the corresponding distributions test are computed over the set of sessions. TI Kullback-Leibler divergence is given by the folle 7.2. STABILITY, MOST FREQUENT PAGES ing formula AND KL. D IBm,P)=∑kg(=0)×Pm( The degree of stability between two consecu- u∈L ive recommendations is defined by the number of common suggestions between them. The lower The higher this number, the less representative of this value. the more unstable the recommenda- the user navigation behavior the recommendations tion function is and the more abruptly suggestions are evolve. Theoretically once the system has under stood the user information needs and navigation 8. TESTS AND DISCUSSION style the recommendation sets should not vary too much. Thus this degree should stabilize to a value This section presents first the testing datasets close to 1 Then. the two others link recommendation algo-

6 and modelized. In a sake of simplicity, assume that →−s = is a session and p ≤ n, then Recp s will denote the set Recp s = Rec(). 7.1. RECALL, PRECISION AND COVERAGE The following definition sums up the classical evaluation measures used when evaluating ORS. DEFINITION 6 Let U be a resource domain, Rec a recommendation function, →−s a session of size n and l ≤ n. – A recommendation Recl s is covered, if: |Recl s | > 0 – The validity of Recl s is given by: val(Recl s ) = |Recl s ∩ (tl+1, ..,tn)| – A covered recommendation is said precise if: val(Recl s ) > 0 – The recall of a covered recommendation is: val(Recl s ) |Recl s | The coverage (resp. precision) of a set of recom￾mendations is the average number of recommenda￾tions which were covered (resp. precise). The recall of a set of recommendations is the mean of their recalls. 7.2. STABILITY, MOST FREQUENT PAGES AND K.L.D. The degree of stability between two consecu￾tive recommendations is defined by the number of common suggestions between them. The lower this value, the more unstable the recommenda￾tion function is and the more abruptly suggestions evolve. Theoretically once the system has under￾stood the user information needs and navigation style the recommendation sets should not vary too much. Thus this degree should stabilize to a value close to 1. DEFINITION 7 Let U be a resource domain, Rec a recommendation function and →−s = a session. Let us consider a prefix of →−s , with l < n, the so-called degree of sta￾bility of Rec on the session →−s between tl and tl+1 is defined by the number: |Recl s ∩ Recl+1 s | max(|Recl s |, |Recl+1 s |) Previous works on prefetching have discovered a relation between the frequency of requests to Web documents and their rank of popularity, it is known as the Zipf’s law [8]. Let us denote by ζ the rank of popularity (with regard to its frequency) of a resource and P the frequency of occurrence, then: P ∼ ζ −β with β typically close to 1. Such dis￾tributions imply that, usually, few resources con￾centrate the interest of the users. It can be ex￾pected that the pages recommended by a LRS do not differ too much from this law. It is important that the pages well ranked by their frequency are also recommended in a high proportion. The Most Frequent Pages ratio is thus defined by the num￾ber of frequently recommended pages over the to￾tal number of recommended pages. However, a RS cannot only focus on most frequent pages because useful information is not always contained in most frequent pages. The Kullback￾Leibler divergence (KLD) is well suitable to as￾sess the difference between the distributions of the accessed and recommended pages. To compute the KLD, the probabilities Plearn(u) are computed over the learning database that expresses the prob￾ability that a page u will be requested. During the testing step, the corresponding distributions Ptest are computed over the set of sessions. The Kullback-Leibler divergence is given by the follow￾ing formula: I(Plearn, Ptest) = X u∈U log  Plearn(u) Ptest(u)  ×Plearn(u) The higher this number, the less representative of the user navigation behavior the recommendations are. 8. TESTS AND DISCUSSION This section presents first the testing datasets. Then, the two others link recommendation algo-

rithms will be compared with the Sce ap- account in the prediction process. The valuated proach are presented. Finally, the results are given recommendation function is trained over a session set D. To do so, the probability PD(s, u) that a link u will be accessed with regard to the last M 8. 1. DATASETS ransactions of the session sed is considered The valuated recommendation function given by Three Http user access log files have been con Recvalngr(S, u)=pd(s, u) is the expression sidered. The interest of these logs is that they are of the final recommendation function. Given the include different users' information seeking behav number of pages on the websites we consider and iors and interests. The first one considered is the because of the problem of representation for the World Cup Soccer 98 official website. Note that the N-GRAM model. we have chosen N=l content of these website was highly dynamically In[12, Mobasher et al. propose an algorithm generated and thus the content of documents hav based on frequent association rules between the re- ng the same URL was likely to change in a few sources of sessions. Their algorithm is also based hours. For instance, the content of the homepage on a distance factor between the nodes of the changed more than once a day during the contest dependency graph. This factor is particularly in- The second log considered belongs to Music Ma- teresting because it prompts the recommendation chines. This website address people interested i professional audio devices. The last user access log from the last one accessed. Thus. recommenda- file comes from the website of ClarkNet. an US tions allow to save clicks to access the relevant in- internet access provider formation. They introduce the Physical distance Each log file was split up into two subsets of transactions. the former used to train the models between two nodes ul and u2, d(u1, u2) which and the latter used to test them. Once the use- is the minimal length of the path between ul and 12. Then they define a physical distance be- less transactions filtered(made up audio and vi- tween an active session s and a resource ui for sual materials requested because they were linked the graph G=d(ui, uj ). Eventually the distance fac- utes(see table 1). Because of the problems due to or between a link u and a session s is aches and proxy servers only the first instance of ldf(a, s)=log(dist(u, 3, G))+l ifu each URL in the sessions was kept. For training as well as for testing, the only sessions with a size 0 otherwise between 4 and 30 were kept(which correspond to more than 99% of the total number of extracted Mobasher et al.'s algorithm can be expressed sessions for any log file considered) more easily with the following valuated recommen- dation function: 8. 2. COMPARISON WITH OTHER LINK RecMoB(s, u)=conf(=u)*ldf(u, w) RECOMMENDER ALGORITHMS 0 otherwise We have compared the SCE algorithm with where conf( ul) depends on the thresh two others methods. The first one is adapted olds minsup and minconf from a classical prefetching approach based on N-GRAM model. It is an adaptation we made in order to show that even if prefetching algorithms 8.. RESULTS AND DISCUSSION have good precision and recall they do not neces- sarily fulfill conditions making a recommender sys- tem to be good In N-GRAM models, the only For each dataset, recommendation process starts last N pages of an active session are taken into when the tested active sessions have a size larger than 2. Table 2 summarizes the measures previ- SloGfilesavailableathttp://repository.cs.vt.eduan ously defined 4 and the three graphics in Table 3 http://www.cs.washingtonedu/research/adaptive/ show the average stability of each recommendation

7 rithms that will be compared with the SCE ap￾proach are presented. Finally, the results are given and discussed. 8.1. DATASETS Three HTTP user access log files have been con￾sidered3 . The interest of these logs is that they are include different users’ information seeking behav￾iors and interests. The first one considered is the WorldCup Soccer 98 official website. Note that the content of these website was highly dynamically generated and thus the content of documents hav￾ing the same URL was likely to change in a few hours. For instance, the content of the homepage changed more than once a day during the contest. The second log considered belongs to Music Ma￾chines. This website address people interested in professional audio devices. The last user access log file comes from the website of ClarkNet, an US internet access provider. Each log file was split up into two subsets of transactions, the former used to train the models and the latter used to test them. Once the use￾less transactions filtered (made up audio and vi￾sual materials requested because they were linked the requested pages), the sessions were extracted with a τ1-dynamic algorithm with τ1 = 5 min￾utes (see table 1). Because of the problems due to caches and proxy servers only the first instance of each URL in the sessions was kept. For training as well as for testing, the only sessions with a size between 4 and 30 were kept (which correspond to more than 99% of the total number of extracted sessions for any log file considered). 8.2. COMPARISON WITH OTHER LINK RECOMMENDER ALGORITHMS We have compared the SCE algorithm with two others methods. The first one is adapted from a classical prefetching approach based on N −GRAM model. It is an adaptation we made in order to show that even if prefetching algorithms have good precision and recall they do not neces￾sarily fulfill conditions making a recommender sys￾tem to be good. In N − GRAM models, the only last N pages of an active session are taken into 3Log files available at http://repository.cs.vt.edu and http://www.cs.washington.edu/research/adaptive/. account in the prediction process. The valuated recommendation function is trained over a session set D. To do so, the probability PD(→−s , u) that a link u will be accessed with regard to the last N transactions of the session →−s ∈ D is considered. The valuated recommendation function given by RecV alNGR(→−s , u) = PD(→−s , u) is the expression of the final recommendation function. Given the number of pages on the websites we consider and because of the problem of representation for the N − GRAM model, we have chosen N = 1. In [12], Mobasher et al. propose an algorithm based on frequent association rules between the re￾sources of sessions. Their algorithm is also based on a distance factor between the nodes of the dependency graph. This factor is particularly in￾teresting because it prompts the recommendation function to favor pages which are the farthest from the last one accessed. Thus, recommenda￾tions allow to save clicks to access the relevant in￾formation. They introduce the Physical distance between two nodes u1 and u2, d(u1, u2) which is the minimal length of the path between u1 and u2. Then they define a physical distance be￾tween an active session →−s and a resource ui for the graph G = by: dist(ui ,→−s , G) = minuj∈ d(ui , uj ). Eventually the distance fac￾tor between a link u and a session →−s is: ldf(u, →−s ) = log(dist(u, →−s , G)) + 1 if u 6∈ = 0 otherwise Mobasher et al.’s algorithm can be expressed more easily with the following valuated recommen￾dation function: RecMOB(→−s , u) = conf(⇒ {u}) ∗ ldf(u, w) = 0 otherwise where conf(⇒ {u}) depends on the thresh￾olds minsup and minconf. 8.3. RESULTS AND DISCUSSION For each dataset, recommendation process starts when the tested active sessions have a size larger than 2. Table 2 summarizes the measures previ￾ously defined 4 and the three graphics in Table 3 show the average stability of each recommendation

M. Machines W.C. Soccer ClarkNet otal transactions 1193531.654892 Total different IPs 18.037 17.835 54324 Total different pages 104s45 12.994 16814 Total sessions for training7.714 8.736 10334 Average size of sessions 6.9 1 Features of log files Word Cup Soccer Music machines NGR MOB SCE GR MOB SCE NGR MOB SCE 54% 6185%6861%5805%489%4092%4023%66%527%48% Cov x Pre58.76%43.22%57.46%42.14%409%33:79%65.73%42%39% 36.1%46.44%34.2%36.4%3202%28.28%39.47%42.4%|39.9% MFP624%9108%9217%1876%802%763%54%8614%84% 1.12 function between the second and twentieth pages that MOB and Sce are more tolerant to uncer tainty resulting from the order of the transactions It can be seen that NGR always has the high inside active sessions but they also respect much est precision rate. This has the following explana tion: NGR is a purely statistical approach which better the user s preference given by the mfP ra tries to predict the following pages of the active tio. It is worth noting that sce is the most sta- window. In contrast. MOB and Sce. two associa- ble one. MOB's stability with WordCup is dif- tion rules based algorithms, are able to recommend ferent from Music Machines and ClarkNet's ones pages that had great chances to be seen before the This is due to the Ars ratio differences. At each last one accessed. This can give the user alternate step, MOB recommends links among a small set interesting ways to consider the documents he has of admissible resources(that is why ARS ratio is accessed.However,as they are defined, precision low), thus pages are frequently the same. With the and recall do not take it into account Secondly, it can be observed that association rule World Cup Soccer dataset, the amount of admissi- approaches are able to reach an excellent level of ble pages is high(ARS ratio is high), and thus it stability, whereas NGR stability is low. The first can be seen that the behavior becomes less stable eason is that N-gram model relies although still better than NGRs one tive window which implies that recommendations With regard to coverage, SCE has the best KLD it makes have been computed on short-term ob It means that Sce is the recommendation function servations. Recommendations are computed with out taking into account the whole information con- which loses the less information from the learning tained in the sessions. In addition, results show database. with its high mfp our algorithm ofter recommends frequently it is alse close to the user s behavior thanks to Kld and ARS=Average Recommendation Set Size, MFP=Most Frequent Pages(at least 20.1%), KL=Kullback-Leibler eventually, it has rather good recall, precision and

8 M. Machines W.C. Soccer ClarkNet Total transactions 359.853 1.193.353 1.654.882 Total different IPs 18.037 17.835 54324 Total different pages 4.970 1.014 8845 Total sessions 8.859 12.994 16814 Total sessions for training 7.714 8.736 10334 Total sessions for testing 1.145 4.258 6480 Average size of sessions 8.4 6.9 6.1 Table 1 Features of log files WordCup Soccer Music Machines ClarkNet NGR MOB SCE NGR MOB SCE NGR MOB SCE Cov 95% 63% 99% 86 % 10% 84% 99% 54% 94% Pre 61.85% 68.61% 58.05% 48.98% 40.92% 40.23% 66.4% 52.7% 48% Cov x Pre 58.76 % 43.22 % 57.46 % 42.14 % 4.09 % 33.79% 65.73% 42% 39% Rec 36.1% 46.44% 34.2% 36.4% 32.02% 28.28% 39.47% 42.4% 39.9% ARS 4.62 4.71 5 4.54 2.75 4.75 4.33 3.12 4.73 MFP 62.4% 91.08% 92.17% 18.76% 80.2% 76.33% 54% 86.14% 82.4% KL 2.78 0.84 1.2 2.5 0.41 1.08 2.64 0.75 1.12 Table 2 Results function between the second and twentieth pages in the sessions. It can be seen that NGR always has the high￾est precision rate. This has the following explana￾tion: NGR is a purely statistical approach which tries to predict the following pages of the active window. In contrast, MOB and SCE, two associa￾tion rules based algorithms, are able to recommend pages that had great chances to be seen before the last one accessed. This can give the user alternate interesting ways to consider the documents he has accessed. However, as they are defined, precision and recall do not take it into account. Secondly, it can be observed that association rule approaches are able to reach an excellent level of stability, whereas NGR stability is low. The first reason is that N-GRAM model relies on an ac￾tive window which implies that recommendations it makes have been computed on short-term ob￾servations. Recommendations are computed with￾out taking into account the whole information con￾tained in the sessions. In addition, results show 4Cov=coverage, Pre=Precision, Rec=recall, ARS=Average Recommendation Set Size, MFP=Most Frequent Pages (at least ≥ 0.1%), KL = Kullback-Leibler divergence. that MOB and SCE are more tolerant to uncer￾tainty resulting from the order of the transactions inside active sessions but they also respect much better the user’s preference given by the MFP ra￾tio. It is worth noting that SCE is the most sta￾ble one. MOB’s stability with WordCup is dif￾ferent from Music Machines and ClarkNet’s ones. This is due to the ARS ratio differences. At each step, MOB recommends links among a small set of admissible resources (that is why ARS ratio is low), thus pages are frequently the same. With the WorldCup Soccer dataset, the amount of admissi￾ble pages is high (ARS ratio is high), and thus it can be seen that the behavior becomes less stable although still better than NGR’s one. With regard to coverage, SCE has the best KLD. It means that SCE is the recommendation function which loses the less information from the learning database. With its high MFP our algorithm often recommends frequently accessed pages, it is also close to the user’s behavior thanks to KLD and eventually, it has rather good recall, precision and coverage

algorithm, SCe as well as NGR are efficient as a ORS. Three new Lrs evaluation criteria were also World Cup Soccer troduced. with respect to these criteria the best esults are given by the Sce algorithm Working out the following multiobjective prob- 0.8 STC lem is a challenge we are currently working on: 0.6 How to automatically tune the Lrs with respect to expected values of the criteria that would bo chosen a priori by the website designer? 0.2 0 2468101214161820 [1HypertextTransferProtocol-http:/1.1,Rfc2616, June. 1999. Music Machines 2 M. Balabanovic. An adaptive web page recommenda- editors, Proceedings of the First Intemational Confer- ence on Autonomous Agents(Agents 97), pages 378- 0.8 York. 5-8. 1997. ACM Press 0.6 3 J S Breese, D Heckerman, and C Kadie. Empirical analysis of predictive algorithms for collaborative fil- 0.4 tering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Madison, WI. pages 43-52, July 1998 0.2 [4 R. Cooley, B Mobasher, and J Srivastava. Data prepa 2468101214161820 5 J-Y. Delort, B. Bouchon-Meunier, and M. Rifqi. A content-based approach of shift of focus detection in www navigation(under submission), 2003 ClarkNet [6] M. Deshpande and G Karypis Selective markov mod els for predicting web-pages accesses. In Ist SIAM 0.8 [7X. Fu, J. Budzik, and K J. Hammond. Mining naviga- tion history for recommendation. In Proceedings of In- 0.6 telligent User Interfaces, ACM Press, pages 106-112, 0.4 [8 s Glassman. A caching relay for the world wide web Proceedings of the First International World wide 02比 Web Conference. pages 69-76, 1994. 9 D. He and A. Goker. Detecting session boundaries 0 from web user logs. In Proceedings ofof the BCs- 2468101214161820 IRSG 22nd Annual Colloquium on Information Re- Average stability degrees of N-GRAM, MOB and ScE 10J Konstan and al. Grouplens: Applying collaborative filtering to usenet news. Communications of the ACM, 11 H. Lieberman. Letizia: An agent that assists web 9. CONCLUSION browsing. In Proceedings 14 th International Confer ence Artificial intelligence(IJCAl), 1995. The uncertainty about the user navigation be- [12]B Mobasher R. Cooley, and Srivastave. Aut personalization based on web usage mining, technica haviors is the main drawback that prevents the de- report tr99010. Technical report, Department of Com- ployment of LRS. Results show that the proposed puter Science, DePaul University, 1999

9 0 0.2 0.4 0.6 0.8 1 2 4 6 8 10 12 14 16 18 20 WorldCup Soccer ’NGR’ ’MOB’ ’STC’ 0 0.2 0.4 0.6 0.8 1 2 4 6 8 10 12 14 16 18 20 Music Machines ’NGR’ ’MOB’ ’SCE’ 0 0.2 0.4 0.6 0.8 1 2 4 6 8 10 12 14 16 18 20 ClarkNet ’NGR’ ’MOB’ ’STC’ Table 3 Average stability degrees of N-GRAM, MOB and SCE 9. CONCLUSION The uncertainty about the user navigation be￾haviors is the main drawback that prevents the de￾ployment of LRS. Results show that the proposed algorithm, SCE as well as NGR are efficient as a ORS. Three new LRS evaluation criteria were also introduced. With respect to these criteria the best results are given by the SCE algorithm. Working out the following multiobjective prob￾lem is a challenge we are currently working on: How to automatically tune the LRS with respect to expected values of the criteria that would be chosen a priori by the website designer? References [1] Hypertext Transfer Protocol – HTTP/1.1, RFC 2616, June, 1999. [2] M. Balabanovic. An adaptive web page recommenda￾tion service. In W. L. Johnson and B. Hayes-Roth, editors, Proceedings of the First International Confer￾ence on Autonomous Agents (Agents’97), pages 378– 385, New York, 5–8, 1997. ACM Press. [3] J. S. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative fil￾tering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Madison, WI, pages 43–52, July 1998. [4] R. Cooley, B. Mobasher, and J. Srivastava. Data prepa￾ration for mining world wide web browsing patterns. Knowledge and Information Systems, 1(1):5–32, 1999. [5] J.-Y. Delort, B. Bouchon-Meunier, and M. Rifqi. A content-based approach of shift of focus detection in www navigation (under submission), 2003. [6] M. Deshpande and G. Karypis. Selective markov mod￾els for predicting web-pages accesses. In 1st SIAM Data Mining Conference, 2001. [7] X. Fu, J. Budzik, and K. J. Hammond. Mining naviga￾tion history for recommendation. In Proceedings of In￾telligent User Interfaces, ACM Press, pages 106–112, 2000. [8] S. Glassman. A caching relay for the world wide web. Proceedings of the First International World Wide Web Conference, pages 69–76, 1994. [9] D. He and A. Goker. Detecting session boundaries from web user logs. In Proceedings of of the BCS￾IRSG 22nd Annual Colloquium on Information Re￾trieval Research, 2000. [10] J. Konstan and al. Grouplens : Applying collaborative filtering to usenet news. Communications of the ACM, 40(3):77–87, 1997. [11] H. Lieberman. Letizia: An agent that assists web browsing. In Proceedings 14 th International Confer￾ence Artificial intelligence (IJCAI), 1995. [12] B. Mobasher, R. Cooley, and J. Srivastave. Automatic personalization based on web usage mining, technical report tr99010. Technical report, Department of Com￾puter Science, DePaul University, 1999

[13]J.E. Pitkow and P. Pirolli. Mining longest repeated sequences to predict world wide web surfing. In [14 R. R. Sarukkai. Link prediction and path analysis us- ng markov chains. In Proceedings of the gth Interna- tional World wide web Conference, 2000 [15]G. Shafer. A mathematical theory of evidence. Prince- ton University Press, 1974. [16 S Spiekermann and M. Christ. Strategic design of in- teractive recommender ns. In Third Berlin In- ternet Economics Workshop, May 2000

10 [13] J. E. Pitkow and P. Pirolli. Mining longest repeated subsequences to predict world wide web surfing. In Proceedings of the Second USENIX Symposium on In￾ternet Technologies and Systems, 1999. [14] R. R. Sarukkai. Link prediction and path analysis us￾ing markov chains. In Proceedings of the 9th Interna￾tional World Wide Web Conference, 2000. [15] G. Shafer. A mathematical theory of evidence. Prince￾ton University Press, 1974. [16] S. Spiekermann and M. Christ. Strategic design of in￾teractive recommender systems. In Third Berlin In￾ternet Economics Workshop, May 2000