{"id":2993,"date":"2014-11-03T12:32:32","date_gmt":"2014-11-03T12:32:32","guid":{"rendered":"https:\/\/irsg.bcs.org\/informer\/?p=2993"},"modified":"2014-11-03T12:32:32","modified_gmt":"2014-11-03T12:32:32","slug":"mining-search-logs-for-usage-patterns-pt-2","status":"publish","type":"post","link":"https:\/\/archive-irsg.bcs.org\/informer\/?p=2993","title":{"rendered":"Mining search logs for usage patterns (pt 2)"},"content":{"rendered":"

\"Expectation<\/a><\/p>\n

In a previous post<\/a> I discussed some initial investigations into the use of unsupervised learning techniques (i.e. clustering) to identify usage patterns in web search logs<\/a>. As you may recall, we had some initial success in finding interesting patterns of user behaviour in the AOL log<\/a>, but when we tried to extend this and replicate a previous study<\/a> of the Excite log<\/a>, things started to go somewhat awry. In this post, we investigate these issues, present the results of a revised procedure, and reflect on what they tell us about searcher behaviour.<\/p>\n

So to recap, last time we got to the point where we\u2019d applied the expectation maximization<\/a> algorithm to a sample of 10,000 sessions from the AOL log, and were hoping to replicate the findings from Dietmar Wolfram\u2019s 2008 study<\/a>. But our results were very different: three clusters instead of four, and some very different patterns. Moreover, our results weren\u2019t even replicable within themselves: a further three samples of 10,000 sessions produced widely different outcomes (7, 10 and 10 clusters respectively). Even increasing the sample size to 100,000 seemed to make little difference (despite the suggestion in Wolfram\u2019s paper that subsets of 50k to 64k sessions should produce stable clusters).<\/p>\n

So why are we seeing such different results? One interpretation may be of course that these insights are indeed an authentic reflection of changes in user behaviour due to differences in context (e.g. a different search engine, time period, demographic, etc.) But before we explore that possibility, we should take steps to discount the effect of other confounding factors. For example, is our data truly representative of the population? Taking a further sample of sessions is a relatively straightforward test of this, and indeed, applying EM to a fresh sample of 10,000 sessions produced the following 4 clusters [note that I have changed the display order of the features to facilitate comparison with Wolfram\u2019s results, and simplified their names]:<\/p>\n

\n
\n
\"Expectation<\/a><\/dt>\n
Expectation Maximization using Wolfram\u2019s 6 features on 10,000 sessions from AOL<\/dd>\n<\/dl>\n<\/div>\n

This outcome seems to offer some interesting insights, but again, it fails to repeat across the other samples; with 5, 6 and 7 clusters produced each time. Moreover, increasing the sample size to 100,000 also fails to produce a stable result, with 7, 13, 6 and 6 clusters produced on each iteration.<\/p>\n

But let\u2019s pause for a moment and examine the pattern in more detail. There is something very odd happening with term popularity now: we see a small cluster (just 3% of the sessions) where this feature seems to be something of an outlier, compressing the remaining traces into a narrow band. Indeed, the phenomenon becomes even more pronounced when we take a sample of 100,000 sessions:<\/p>\n

\n
\n
\"Expectation<\/a><\/dt>\n
Expectation Maximization applied to 100,000 sessions<\/dd>\n<\/dl>\n<\/div>\n

Perhaps this is an artefact of the clustering algorithm? Let\u2019s try XMeans<\/a> instead (which is a variant of kMeans<\/a> where the value for k is determined by the algorithm). In this iteration, XMeans finds a local optimum at k=10, so the number of clusters is different. But the overall pattern, with a small cluster (1% of sessions) representing outlier values for term popularity is again clearly visible:<\/p>\n

\n
\n
\"XMeans<\/a><\/dt>\n
XMeans (k<=10) applied to 100,000 sessions<\/dd>\n<\/dl>\n<\/div>\n

So something else must be at play. It turns out that there is indeed an artefact in the data which is causing this. Long story short, there are a small number of sessions which contain just a single query, consisting solely of the character \u2018-\u2018. Precisely why they are there is a matter for speculation: they may have been the default query in some popular search application, or an artefact of some automated service or API, etc. We\u2019ll probably never know. But sessions like these, along with other robot-generated sessions, aren\u2019t generally helpful when trying to understand human behavioural patterns. Instead, they are best removed prior to analysis. Of course, there are no 100% reliable criteria for differentiating robot traffic from human, and what should be removed is a matter for judgement, often on a case-by-case basis. In this case, including these single character queries appears to be counter-productive.<\/p>\n

So now, with a new sample of 100,000 sessions excluding these outlier queries, we see EM produce the following output:<\/p>\n

\n
\n
\"Expectation<\/a><\/dt>\n
Expectation Maximization applied to a new sample of 100,000 sessions<\/dd>\n<\/dl>\n<\/div>\n

This pattern is much more stable, with four iterations producing 7, 7, 7 and 9 clusters respectively. At this point we can start to speculate on what these patterns may be telling us. For example:<\/p>\n