Evolution Computing Approach To Exploit User Navigational Path Applying Dynamic Prediction

Since 1991 WWW (World Wide Web) concept becomes more popular. It increases use of internet as well as internet users. The wide users’ access information leads us to improve well known strategies for web pre fetching, dynamic user modeling and site customizations to provide or access better performance in internet URL surfing. This paper presents new method to exploit user navigational path behavior to predict, in real-time, future requests. Real time user adaptation avoids the use of statistical techniques on websites or URL logs by adopting the predictive user model. Our new mode adopted from Finite State Machine formalism together with Genetic Algorithm which evolves a population for the same.

1.    Introduction: WWW as a part of best Internets service which is providing a rich interactive environment to an increasingly expanding number of users. In attempting to improve navigation experience over the Internet, several optimization techniques may benefit from the availability of reliable prediction systems, able to foresee the next action of web users. One possible application for predicting user actions is perfecting, that consists of sending to user’s local cache or user’s nearest proxy the documents that are most likely to be requested at the next navigation steps. If the information sent is correct the user perceives a very high navigation speed even using slow connections. Another interesting application of prediction systems is in the currently expanding field of web intelligence, for instance in dynamic site adaptation to users or dynamic customization. In this case users actions are monitored to re-structure pages in a web site in order to reduce the time needed by users to reach useful information, and enhanc-ing site usability. There has been an increasing amount of work on pre-diction models: web log based inference has been focused on prediction models that make best guesses on the user’s next action using information about their previous ones. Recommendation systems rely on a prediction model that infers user’s interest and make recommendations using the extracted information. Two figures of merit are usually adopted, one measuring the frequency with which the sys-tem is able to yield a prediction (applicability) and the other the frequency with which these predictions are correct (precision) [1]. Existing prediction models can be either “point-based” or “path-based”. “Pointbased” prediction models use actions indexed at some time instants to predict the user’s next action based on the currently observed one, in other words they use frequency measures to predict next requests. These models draw on a relatively small amount of information from each session and therefore predictions could be inaccurate. The best results obtained show a pre-diction applicability measure of over 50% and a precision figure around 30% [4][5].
“Path-based” models are built on users previous navi-gation path, they leverage a statistical analysis of user’s actions and can achieve good precision with moderately high applicability using large enough web logs (40% ap-plicability and 60% precision using a 3-gram model) [2]. These approaches are able to predict user actions in sta-tistically static environments, only, i.e., when the statistical characteristics of user actions are constant or evolving very slowly. In this paper we propose a new approach to make reliable predictions in real-time, to be able to react quickly to changes in user habits or in site structure; web -log mining approaches are not applicable in this context so a more powerful predictive modeling of user session is needed. We use an Evolutionary Algorithm to evolve a population of finite state machines (prediction machines) designed to provide a prediction model for user’s next requests at each session. The best machine in the population is used to make predictions, and at the end of each session some machines are mutated, evaluated and a new population is computed, taking into account the information provided by the last session. Our prediction system is well suited to be used in dynamic contexts were pages composing a web site are changing, users change habits and so on. A preliminary version of this approach was presented in [16], where the evolutionary approach to real-time prediction was proposed. This paper present a greatly enhanced version of the algorithm, than now includes support for recombination operators, and has been rewritten with an optimized data structure that reduces memory occupation and CPU time requirements. Also, in this paper we present extensive experimental comparisons with comparable approaches, not yet available in [16]. The organization of the paper is as follows: in the next section, we give a short overview of related works. In section 3 we introduce some basics about our approach while in section 4 we give background information about web session modeling. In the fifth section we illustrate the pro-posed approach to user modeling and prediction, and in the sixth section we present some results. Section 7 draws conclusions.

2.     Concepts of Paper & Related Work: The availability of an increasing amount of information on the World Wide Web inspired a lot of work on user action prediction. Much work has been done in recommendation systems, which provide suggestions for future selection of links based on machine learning or data mining algorithms. An example of recommendation system is the Letizia sys-tem [11] that predicts user navigation actions using forward explorations and the Web Watcher system [12] that anticipates the next selected hyperlink by using a model built through reinforcement learning. Other examples of user behavior prediction systems are the Transparent Search Engine system [7] that evaluates the most suitable documents in a repository using a user model  updated in real time and the Syskill & Webert system [13] that learns to rate pages on the web. “Path-based” systems for web pages prediction (What Next [1] as an example) obtain a model by building sequences of user requests of sufficient length, from a web server log file, and predict the next user action exploiting a statistical analysis of sequence information. The work by Zukerman et al. [4] belongs to this class, where a Markov model is learned using a web server log file as training information (both with respect to the time interval information and the session information), and the predicted documents are then sent to a cache located on  the client side. Lau and Horvitz [6] have characterized user queries with a Bayesian model in order to make predictions on users’ next query based on previous queries and time intervals. Pitkow and Pirolli proposed a Longest Repeating Sequences (LRS) approximation of Kthorder Markov models using N-gram representation of user request. They analyzed two hybrid approaches to extract user patterns from web log data and used these patterns to estimate Kth-order Markov models. Starting from their previous work [14] on user requests characterization they drive conclusion about LRS effectiveness compared with traditional predictive Markov models. The work of Qiang, Haining and Tianyi [3] and the one from Su, Yang, Lu and Zhang [1] fall also in the “path-based” models category. Another approach based on N-gram representation, which takes into account the sequence of precedent request, and the time gap be-tween last received request and desired prediction, is that of Martinez and Karamcheti [17]. The work of X. Sun, Z. Chen et al. [18] improves the traditional n-gram model representation by predicting the next action that lies on the optimal path toward the ultimate goal of each user. Finally it has also to be mentioned the work of S. Gündüz and M.T. Özsu [19] in which predictions are provided starting from a frequent pattern mining approach based on clustering.

3.     Basic Rules: Compared to the systems above, we conceived the prediction system as an online dynamic mechanism, which must be able to adapt itself to changes in a reasonable time. Therefore we don’t focus on web log mining but use live data to create and improve an adaptable prediction system. We formalized a new predictive model for user sessions leveraging the Finite State Machine paradigm. A set of “prediction machines” is defined, evolved and evaluated through an evolutionary algorithm in order to obtain better prediction performance using information gathered from user sessions. Unlike many optimization problems, a predicting next request is characterized by a non-static optimum solution, since the best prediction changes over time, as navigation habits and site structure evolve. We proposed the adoption of an evolutionary algorithm that cultivates a population of individuals that aim at modeling the user session behavior. The relevance of each individual user session is negligible by itself, but all together the sessions force the evolution of a group of prediction models that incorporate global users behavior. The evolutionary part of the prediction system is specially developed for this problem. The most important characteristic of this optimization problem is that the evaluating function (fitness) is time dependent because user habits and site structure may change. In our approach, the fitness function includes the contributions of applicability and precision. Applicability is defined as the ratio of the number of predictions to the number of requests, while precision is the ratio of good predictions to the number of predictions.
Applicability = N Predictions / N Request(1)
Precision = N Perfect_Predictions/N
Predictions………………………...……. (2)
The optimal solution is reached by making a number of good predictions equal to the number of users requests. The unpredictability of user actions is the great problem to deal with.
4.     Web sessions: A web session is a sequence of web requests from a given user. We define a user request Ru as a request to a web server coming from a host over the HTTP protocol [RFC 2616]. A request Ru from user u is considered as valid if and only if the HTTP response code is 2xx (success). We consider the user u as an anonymous entity, approximately identified by a combination of the source IP address and the client cookie. The same person, connecting to the same site at a later time, would be identified as a different user. The application server tracks the client IP and cookie for each incoming request and creates ordered collections of all requests Ru,k coming from the same user. Ru,k is the k-th request coming from user u. All consecutive requests coming from the same user form a session Su. Each new request may be identified as a prosecution of some  already open session, or as a new session, depending on user identification and request time stamps. Web application servers usually define a session timeout Ts (e.g., 20 minutes) to automatically terminate idle sessions: a request is considered as belonging to a user open session Su if the time delay between the last received Ru,k and the preceding r equest Ru,k-1 by same user u is less than Ts. Information about source IP addresses, cookies, or de-tailed timing is not used in the prediction system; there-fore, a user session is simply modeled as a finite ordered sequence Si of n valid user requests R.
Si . {R1, R2... Rn }…………(3)
For each user session Si the optimization algorithm identifies a FSM able to guess next requests, by using in-formation gathered from all previous sessions. The prediction FSM foresees the k-th request Rk in a user session Si given the k-1 previous page visits.
R1, R2... Rk-1 ⇒ Rk (k =1..n)……………......(4)
Rk is the so called “prediction”.

5.     New Approach: The architecture of the prediction system is composed of two modules: an evolutionary algorithm and a request predictor (Figure 1). The evolutionary algorithm, starting from a stream of user sessions Si, evolves a population of prediction machines. The best prediction machine is made available at any time to the request predictor that is able to predict user actions on live sessions. This architecture al-lows web sites to use the request predictor that simply requires interpreting a finite state machine, by meeting scalability and ease of integration demands. On the other hand, the optimization problem is taken over by a parallel process, the evolutionary algorithm, and interaction between the two is limited to providing updated copies of the best prediction machine.
5.1.    User session model: The evolutionary algorithm cultivates a population of user request models with prediction capabilities. Each model is a representation of a set of user sessions, and models the knowledge learned by the system about user behavior. Several user sessions modeling techniques are possible, as an example most statistical approaches to prediction systems use a model called n-gram. An n-gram is a tuple of the form <R1, R2,...,Rn> to indicate request sequences by a group of users visiting a web site. Each component takes on specific values Ri=ri for a specific navigation path taken by a specific user              
                                                        


The basic idea of n-gram modeling relies on finding all frequent sequences of r equests (with length ≤ n). For each requests sequence R1,R2,…,Rk having length k, a prediction is defined as in (4) and the related conditional
Probability can be evaluated as:
          Count( Si = {*,R1 R2  …RK, *})
P(RK R1 R2 R3
 Count( Si = {*,R1 R2  …RK-1, *})
The number of rules of this kind that a prediction algorithm needs to generate is usually large; therefore widely adopted approaches extract these rules dynamically, from a memory data structure. N-gram dimension is directly related to the order of a Markov model. First order Markov models in fact are estimated from 2-grams of the form <R1, R2>. If longer sequences are considered, i.e., if one wants to consider the conditional probability that a specific request rk will be effectively predicted given k-1 requests r1,r2,r3,…rk-1, a kth-order Markov model can be built:
P(rk r1r2r3-1) = Pr(RK =rk  rk-1=rk-1,…,R1 = r1 ……………………………….(6)
In system we designed a new model representing user next requests as a Finite State Machine, called a Pre-diction Machine (Figure 2), with a higher expressive power than n-grams, in fact n-gram models could be easily represented as a specific kind of Prediction Machine. Each state of the machine represents a  prediction, while transitions represent user requests. Prediction Machines are defined over a set of labeled states S (with a labeling function _), a set of labeled transitions T between states (with state transition function _), and an alphabet L. L defines the space of user requests that the machines could predict, defined as the set of all possible valid requests to a site, possibly differentiated by re-quest parameters. Usually L coincides with the set of pages in the site. In the case of site modifications, new symbols appearing in user requests are automatically added to L. The machine accepts the input alphabet L (represented as transition labels) and generates an output alphabet L { } (represented as state labels).
Formally, a prediction machine M takes an incoming session Si of length n and provides a prediction sequence Oi as output, composed of individual predictions Qj. Where Si = {R1,R2,….Rn} Ln  (M, Si)  Oi and Oi = {Q1 Q2, ….Qn} (L { })n

The initial state represents the first prediction. All re-quests in the same session are passed to the prediction ma-chine, and let it evolve through successive states. In each successive state the machine may yield a prediction about the next action. Further details on the definition of Prediction Machines can be found in [16]. All machines thus provide predictions for each user request, and the evolutionary algorithm is charged to evolve and select good ones while destroying the others.

5.2    Evolutionary algorithm: This section presents the evolutionary algorithm used to generate optimal prediction machines starting from a continuous flow of incoming user sessions. The first sub-section summarizes the design principles of the algorithm that were already presented in [16], to which the reader is referred for further details. The remaining sub -sections detail data structures and implementation issues that are critical to the feasibility of the approach and that contribute to solving the problem in real time.
5.2.1 Design:     The evolutionary algorithm goal is to evolve a population of prediction machines using genetic operators like mutation and recombination. We use a steady state evolutionary paradigm E(∝+_). When a user session ends, _ machines are selected for mutation, the resulting ∝+_ population is evaluated and the best ∝ individuals are transferred to the next generation. The selection operator is a Tournament Selection with tournament size of 2, equivalent to a roulette wheel on the linearized fitness [8].

Population P;
Double mutation Probability =0.1;
EA.processSession(Session Su)
{
/* apply operators and
generate _"new individuals*/
for(i=0; i<; i++)
{
Machine machineNew,
machineToMutate;
machineToMutate =
P.selectMachine();
if(random()<mutatio
nProbability)
{
machineNew =
machineToMutate.mutate();
}
else
{
machineNew=machineTo
Mutate.xo
ver
(P.select
Machine()
);
}
P.add(machineNew);
}
/* process
incoming
session */
while (Su.end()
!= true)
{
for(i=0;
i<P.nMachines();
i++)
P.machines(i).evolv
e(Su.request());
Su.next();
}
for(i=0; i<P.nMachines();
i++)
{
P.machines(i).compute
Partial Fitness();
P.machines(i).updateTotalFitness();
}
/* survival of the fittest
*/ P.killLowerFitness
Machines(_);
P.identifyBestPred
ictionMachine();
}
Figure: 3 Pseudo-code of the Evolution Algorithm.
The tournament size fixes the convergence rate of the algorithm; its value is intentionally kept low in order to avoid premature convergence on sub optimal  solutions. Pseudo-code of the algorithm is shown in Fig. 3. Evolutionary operators can be applied to the selected machine a random number of times.  The probability, with which a mutation or a crossover is selected, is fixed by an experimentally determined parameter.
6.     Conclusion: The system we built took use of Genetic Algorithm – an  important branch of AI, to evolve better solution for Exploit User Navigational Path applying Dynamic Prediction as demonstrated and discussed above.
References:
1.    Z. Su, Q. Yang, Y. Lu, H. Zhang, (2000) “WhatNext: A Prediction System for Web Requests using N-gram Sequence Models”, Proceedings of the First International Conference on Web Infor-mation System and Engineering Conference, pp. 200-207.
2.    J. Pitkow, P. Pirolli, (1999) “Mining longest repeating subse-quences to predict World Wide Web surfing”, Proceedings of the Second USENIX Symposium on Internet Technologies and Sys-tems, pp. 139-150.
3.    Y. Qiang, H. Z., Haining, L. Tianyi, (2001) “Mining Web Logs for Prediction Models in WWW Caching and Prefetching”, Knowledge Discovery and Data Mining (Edition),p p. 473-478.
4.    Zuckerman, W. Albrecht, A. Nicholson, (1999) “Predicting user’s request on the WWW”, Proceedings of the Seventh International Conference on User Modeling, pp. 275-284.
5.    D. W. Albrecht, I Zuckerman, A. Nicholson, (1999) “Pre-sending documents on the WWW: A comparative study”, Proceedings of the Sixteenth International Joint Conference on Artificial Intelli-gence (IJCAI-99), Vol.2, pp. 1274-1279.
6.    T. Lau, and E. Horvitz,(1999) “Patterns of search: analyzing and modeling web query refinement”, Proceedings of the Seventh International Conference on User  Modelling, pp. 119-128.
7.    F. Bota, F. Corno, L. Farinetti, G.Squillero, (2002) “A Transparent search Agent for Closed Collections”, International Conference on Advances in Infrastructure for e-Business, e-Education, e-Science, and e-Medicine on the Internet, http://www.ssgrr.it/en/ssgrr2002w/papers/82 .pdf T. Bäck, “Selective Pressure in Evolutionary Algorithms: A Characterization of Selection Mechanism”, Proc. of the First IEEE Conference on Evolutionary Computation, 1994, p. 57-62