Data mining Web site logs

Related Resources • Past issues of weekly features • Data mining 101 • Text and Web mining    Elsewhere on the Web • Scientio, Inc. • Web Usage Mining with SQL Server 2000

Web site logs are a great source of information about a website in many ways. They're free, they're non-invasive - no installing complicated software to get them, they're secure - i.e. whatever you get out of them belongs to you alone and doesn't have to be shared with some third party, and their anonymous - so there are no civil liberty issues. The problem is that the information in a website log is well hidden. The data is incomplete, jumbled and confusing.
Because of caching the website log is often incomplete. Back when few pages were dynamically created as much as 30% of all accesses were cached somewhere or other. This figure has since decreased, but it's certainly true that some of the individual page accesses to your site will not be in your web logs.
It's not always easy to detect individual user sessions in a web log. If cookies are switched of or unusual browsers are used mistakes can be made in identifying an individual session, and then of course there are the many search-engine robot accesses to filter out. If you run a website, especially one that makes money, marketing information is extremely important. Any other source of marketing information you're likely to use, like surveys, advert click through rates or whatever, have large margins of error. Marketing data is almost always imprecise. Despite the missing information in a web log, as marketing data goes, results inferred from it are extremely accurate!

Inference is the key thing. To extract information from web logs you must infer the start and end of user sessions, you must infer the structure of the website from the log, and you must infer user behaviour from the records of pages visited. Our product, XLog, has been developed to do the above. I'm going to explain how it does it in more detail a bit further on. If this seems suicidal of me, don't worry. XLog is so cheap you'd be mad to write your own, and the really interesting bit - the real-time prediction of user behaviour can only be reproduced with some man-years of effort.

I'm going to limit the following discussion to websites using Microsoft IIS and producing log data in the W3C log file format in order to simplify things somewhat.

Inferring sessions from Web log data

Once upon a time an IP address would uniquely identify an individual computer. Those days are long since passed, since ISPs and large organisations re-use a small bunch of IP addresses continually for outgoing traffic. Web site logs record the IP associated with each access, but if ten customers of AOL are accessing you at the same time, it may be difficult to separate them in the log. Microsoft IIS attempts to leave temporary session identifying cookies on each browser, and this works well if cookies are enabled, but problematically the cookies are only present and therefore recorded on the second access. The first access is vital, because if you've used the W3C log format to store your web log it contains an important piece of information, the referrer.

If you want to know whether your online advert has resulted in a sale, rather than just a lot of traffic that creates no income, you'll want to identify where a session came from. This by the way is the important difference between intelligent software like XLog and the more bean-counter approach. There are lots of web statistics software packages, there's an excellent free one called Analog, but most don't extract this vital information. The presence of the referrer helps the process of identifying sessions. A typical part of the log might look like this:

Time	IP Address	Referrer	Cookies	Page
9:57:00	123.45.67.8	http://www.google.com		Default.asp
9:57:01	98.76.54.32	http://www.yahoo.com		Seconds.asp
9:57:02	123.45.67.8	http://www.myweb.com/default.asp	ID1234567	Books.asp
9:57:10	123.45.67.8	http://www.myweb.com/books.asp	ID1234567	Sales.asp

Because the IP addresses are the same in line 1 and line 3, and because the log records are close together in time, and because the referrer in line 3 matches up with the page in line one we can assume they're the same session. From line 3 we've go the session ID Microsoft has supplied, and so we can continue adding to the session list, inferring accesses to cached pages if the referrers and pages don't match up. Other information, like the browser and operating system values can be used to disambiguate sessions.

So from the above we can infer the session looks like:

XLog scans the web logs looking for activity within the time frame specified by the user and then converts the log data into sessions. To store this for re-use and further processing we use an XML document. The following shows the schema we use:

Inferring web site structure from the Web Log

Once we've identified sessions, we can also identify the structure of the web site, and more importantly how it's accessed. We could use things like FrontPage extensions and such like to do this, but the critical thing is not that there is a link between page1 and page2, but how often people use it, and if they do, do they go on to buy anything? The referrer and page name above give us pairs from which we can create a diagram of the activity in a web site. Displaying this information graphically is quite challenging. We've selected the following format:

The pink blocks on the left represent external referring sites. The blue pages are internal pages, local to the web site. The most popular pages are located along the horizontal centre line and their less visited the further they are from the centre. The leftmost blue box is always the default home page, and boxes to the right of this are ordered in terms of the number of clicks required to get to them from the default page. Links are shaded lines, the darker the more often used, Black straight links take you into the web site, red ones back and to the left, blue to other pages on the same level. The usages and names of each page are included in the box, and clicking on them takes you to the page in a new window.
One of the striking things this diagram shows you is how search engines link to any part of your site they choose, and some never leave potential customers at your front door. There are techniques for dealing with this - automatically redirecting for instance.

Identifying important actions, and what hinders or helps them

Most web sites have a purpose other than just informing. They exist to sell or sign up members or make money somehow. Normally it's possible to associate the goals of the site with the pages of the site. For instance on the Scientio site visitors can download demo versions of products, buy full versions, or read various academic papers, white papers etc. Each of these goals is also associated with a page. There's a download response page, a sales response page, etc. Sessions that contain one or more of these pages are thus sessions where sales occurred, sessions where downloads occurred etc. We call these pages target pages. You can tell XLog what your target pages are for your website. One really interesting analysis, that is just straight statistics rather than anything AI based, is identifying pages that occur more or less frequently in association with these sessions than they do over the general run of sessions.
We calculate a gain figure which is just P(target,page)/P(page) for each combination of targets and general pages. Pages with gains greater than one represent pages that can be assumed to help the achievement of the target, less than one represents pages that may well be the "kiss of death" to achieving your targets.

Measuring Web site stickiness

Once you've identified sessions you have a chance of identifying repeat visitors. This is not the most accurate of our calculations, since we cannot rely on the Session ID, but only on generally repeatable elements of the session, such as browser type, operating system and IP address. The stickiness so measured will underestimate the true value, since visitors may be using another randomly assigned IP address, or may have upgraded the browser or operating system between accesses.

Predicting Web visitor behaviour

This is the really interesting bit. Given our target pages, and given our session data, containing a list of the pages visited and the referring site, can we predict the likelihood of an individual visitor going to one of the targets as they arrive at or move through the site? And if we have multiple target pages, can we segment our visitors into, say, browsers, buyers, down-loaders and academics?
We spent quite a while looking at Bayesian Belief Networks for this purpose. On the surface they seem a good fit, since the structure of the web site gives us good clues as to the likely cause and effect relationships required to create a Bayesian net. Unfortunately, though giving accurate estimates of the likelihood of a page being reached, they proved poor at segmenting. Common targets always swamped uncommon ones, and in the end it was hard to add into the networks the requisite sense of recent history required. We'd expect that the referring page, and perhaps two pages before the current page, and the previous page would all have an impact on the visitors' next choices, yet encoding this information in a Bayes net proved very hard.

In the end we reverted to a tried and tested mechanism from time series prediction to create a working solution.

XML Miner

Another of our products is the XML Miner data-mining component. This can be embedded in applications as a COM object and applies Fuzzy logic rule induction to source data in XML. The learning algorithm performs classic supervised learning, and is particularly good at coping with sparse or ambiguous data. Data types can be categorical or numeric. XML miner is configured by an XML definition file, and creates results in XML using our Metarule schema. These results can easily be converted into English language Ifthen rules using an XSL transform, so you can see what has been learned, and we have three kinds of runtime processor that can re-use the rule set on fresh data and provide predictions.

Data preparation

The classic method for using supervised learning with time series is to construct a delay line to hold the samples of the time series, and to add each new sample to the delay line, passing older samples down the line till they drop off the end. At each stage a new training pattern can be created. Since we assume that the referring site, if known is still relevant up until the end of the session, this is added to each training pattern. We are really most interested in segmentation, i.e. working out which of a range of targets is most likely. Confusingly a single session may contain several or all the targets, or of course none. We decided to ignore the examples where no target was reached, and to deal with multiple targets by creating multiple training patterns.
In cases where the URL of a site is typed straight into a browser, there is no referrer. Also while we are loading the delay line, several of the pattern elements will be empty. This causes problems for many learning algorithms, but XML Miner copes with empty data items, and can still extract useful training material from patterns with only one valid item.
We did however decide to limit our considerations to sessions that had more than 6 page accesses. Most web sites have visitors who wander in and out very quickly. We decided to ignore these as irrelevant.
XML Miner was set up to have n+1 inputs, where n was the length of the delay line, and one output. The "+1" input being for the referrer.

So if a session contained target 1 and target 2, and the delay line length was three, the following would be generated, given a page sequence of ref1, page1, page2, page3,target1, page2, target3.

Referrer	Input1	Input2	Input3	Output
Ref1	Page1	null	null	Target1
Ref1	Page1	null	null	Target2
Ref1	Page2	Page1	null	Target1
Ref1	Page2	Page1	null	Target2
Ref1	Page3	Page2	Page1	Target1
Ref1	Page3	Page2	Page1	Target2
Ref1	Target1	Page3	Page2	Target2
Ref1	Page4	Target1	Page3	Target2

While targets 1 and 2 are in the future, we create training patterns for both, as soon as Target1 occurs it is dropped from the output and patterns are created till all the targets that occur in that session are exhausted.

Measuring success or failure

We decided to train XML Miner repeatedly with different delay line lengths to see which gave the best performance. Each time the rule set created was loaded into one of our runtime processors, XML Rule, and the rule set evaluated on the input side of the training patterns generated the same way as for training. Just as XML Miner handles null inputs, XML rule can create null or don't know outputs when the rule set does not contain enough unambiguous information to make a decision, given the input data. If XML Rule correctly predicted one of the valid targets for that session the pass score was incremented, if it didn't the failure score was incremented, and finally if a don't know was produced the don't know score was incremented. We then tried the system out with several different sets of web logs, selecting five targets that were similarly popular.

The results are interesting:

Delay line length	Pass %	Fail %	Dont Know %
1	60	33	7
2	54.6	21.4	24
3	54.8	19.4	25.76

Now given that we were using 5 randomly selected pages, chosen only for their similar popularity we were very pleased with these results. Its very interesting that there is so much predictability, given human behaviour, and given that we are considering only the sequence of pages. The web sites chosen were ones with high connectivity, so that there were almost always multiple paths to each page, and the pages chosen were in the main body of the sites, not hidden away at the end of long page sequences.
The other interesting thing is that a delay length of 1 gave the best results. Having tried this length with other targets, this time limiting the number to two, we have got an average of 87% correct.

Using the rule set in real time

XML Rule is available both as a COM object and as a .NET assembly. This means it can easily be built into Classic ASP and ASP.Net pages. In both cases it is a simple matter to instantiate an XML Rule for each session, and load the rule sets, and the referrer and page values as they occur.
We are currently re-designing the Scientio Web site, and our intention is to segment visitors as they arrive, into several different classes, such as academic, managerial, Webmaster, etc. and change the order of information on each page according to their segments. If we get the prediction wrong, it might be mildly irritating to always find the information of most use furthest down the page, but as you wander through the site the classification should adapt to your behaviour. Please come and look in the near future!

Andrew N Edmonds PhD
Scientio Inc.