DEFINING TOPIC BOUNDARIES IN SEARCH ENGINE TRANSACTION LOGS USING GENETIC ALGORITHMS

Abstract

This study proposes to use genetic algorithms for defining the topic boundaries in search of engine transaction logs. Users are interested in multiple topics during a search session, and genetic algorithms are used in this study to determine whether a search engine user has changed topics during a session. Sample data logs from FAST and Excite search engines were analyzed. The findings show that genetic algorithms are fairly successful in identifying topic continuations and shifts in search engine transaction logs.

It is a challenge to develop effective information retrieval algorithms and interpret user information-seeking behavior, since people have different and changing information needs, and they utilize different information-searching strategies to solve their information problems (Gremett 2006). One of the challenges in information-seeking behavior is new topic identification or session identification. New topic identification or session identification is discovering when the user has switched from one topic to another during a single search session (He, Goker, and Harper 2002). In order to find useful patterns in user sessions, it is necessary to group the queries on the transaction logs into clusters. After the query clusters have been identified, the common usage patterns of search engine users can be discovered by statistical tools (Huang, Yao, and An 2006).

It is important to identify when the user has changed topics to design clustering algorithms and query recommendation algorithms. In addition, it is a very difficult problem to identify user sessions in common access computer centers, such as libraries and PC labs. When a new user accesses the computer, he/she might begin using the search engine with a new topic compared to the previous user. In this case, a topic change occurs, although it might seem that the user is the same (since the computer's IP has not changed). If this topic change is identified, search engines might offer more successful results to the user, by adjusting their ranking and clustering algorithms according to the changing needs of different users. Other implications of session and new topic identification, in terms of personalized web services, web caching systems, and website design, are well-documented by Huang, Peng, An, and Schuurmans (2004).

New topic identification, session identification, and query clustering studies generally analyzed the queries semantically. Defining topic boundaries by relying on semantics of query terms are “dangerously circular” and conceal the persistence of users' long-term information needs (Murray, Lin, and Chowdhury 2006). It is also quite a challenge to determine the topics of user queries looking at the few keywords that a user enters as a query. An alternative approach for session identification or automatic new topic identification is nonsemantic methodologies, where the statistical characteristics of queries, such as query duration or search pattern are used to estimate an upcoming topic change. Hence, nonsemantic methodologies aim to understand that a user has changed topics during a session without looking at the context of the queries, instead of considering the statistical characteristics of the queries. The initial indications of the relationship between statistical characteristics of queries and topic change were shown in Spink et al. (2002a) and Goker and He (2000). Ozmutlu (2006) also showed that the statistical characteristics of queries, such as time interval and search pattern of queries, have a statistically significant effect on topic changes.

Several nonsemantic methodologies, primarily based on learning algorithms, have been previously applied for new topic identification and session identification, such as the Demspter–Shafer Theory (Ozmutlu and Cavdur 2005a; Ozmutlu, Cavdur, and Ozmutlu 2006), neural networks (Ozmutlu and Cavdur 2005b; Ozmutlu, Cavdur, Ozmutlu, and Spink 2004a), but room for improvement exists. A new nonsemantic methodology for fast and successful automatic topic identification would be a valuable contribution to the field of information science.

In this study, we apply genetic algorithms to perform automatic new topic identification of search engine user queries. The queries are categorized with respect to their statistical characteristics. The statistical characteristics are a time interval and search pattern of queries. After the queries are categorized, genetic algorithms are applied to determine whether new queries contain a topic shift or a continuation compared to the previous query. It is also one of the objectives of the article to determine the parameter set for genetic algorithms that will provide the best performance values for automatic new topic identification through elaborate experimental design and analysis of variance.

The layout of the article is as follows: We initially present the literature review related to new topic identification, followed by the description of the research design, results, and the conclusion.

RELATED STUDIES

There are many large-scaled studies on web search engine transaction logs, such as those of Silverstein, Henzinger, Marais, and Moricz (1999), Spink, Bateman, and Jansen (1999), Spink et al. (2002b), and Ozmutlu, Ozmutlu, and Spink (2004b). The number of studies on content analysis is few, the reason generally being the effort required to manually process the queries for topic identification; however, content analysis is a growing area (Pu, Chuang, and Yang 2002). Some researchers, such as Silverstein et al. (1999) and Spink, Wolfram, Jansen, and Saracevic (2001) have performed content analysis of search engine data logs at the term and topical level, and concluded that the popular topics are pornography, entertainment, and e-commerce. Other topic-related studies include Shen, Dumais, and Horvitz (2005), who used marginal models, Markov models, and time-specific Markov models to investigate the transition from one topic to another. It is also a known fact in information retrieval that users might be interested in multiple topics during a single search session, which is called multi-tasking. In terms of information retrieval, multi-tasking is “the process of searches over time in relation to more than one, possibly evolving, set of information problems” (Spink et al. 2002a). Spink et al. (2002a) and Ozmutlu, Ozmutlu, and Spink (2003) show that 11.4% of Excite users and 31.8% of FAST users performed multi-tasking searches, respectively.

Since there might be several topics in a single-user session, it might be important to divide a user session into query clusters. Beeferman and Berger (2000) and Wen, Nie, and Zhang (2002) applied query clustering that uses search engine query logs including click-through data, which provides the documents that the user have selected as a result of the search query. Pu et al. (2002) developed an automatic classification methodology to classify search queries into broad subject categories. They formed a subject taxonomy and fit each search query into one of the categories in the taxonomy. Zhu, Greiner, and Haubl (2003) proposed a link-based system that generates queries from terms contained in the previously accessed documents. Muresan and Harper (2004) proposed a topic-modeling system for developing mediated queries. They performed a statistical analysis of terms in documents available in a source collection and a statistical representation of the lexicographic model of the query. Recently, Liu, Croft, Oh, and Hart (2004) and Metzler and Croft (2005) used support vector machines (SVMs) to classify queries in different groups. Results showed that SVMs achieved recognition accuracy around 80% for queries.

Session identification is an important problem, since it is difficult to identify web user sessions. A single IP address might not mean a single user, due to dynamic IP applications and use of search engines at common-access computer centers such as libraries, computer labs, etc. (Jansen, Spink, Blakely, and Koshman 2007). The most commonly used session identification method is timeout, but it is difficult to set the time threshold (Huang et al. 2004; Cooley, Mobasher, and Srivastava 1999). Search engine researchers have also used cookies, along with IP addresses, for user and session identification. The advantages and disadvantages of these approaches have been discussed in detail in Jansen et al. (2007). Essentially, session identification and new topic identification are equivalent problems. Since different users from a single IP might be differentiated by the topic change that occurs from user to user; the session identification problem can also be solved by successful new topic identification.

As mentioned in the introduction, natural language processing techniques have not yet been successfully applied on search engine transaction logs. One promising approach to the problem of session identification or new topic identification is to use nonsemantic methodologies. In such an approach, queries can be categorized in different topic groups with respect to their statistical characteristics, such as the time-interval between subsequent queries or the reformulation of queries. There are several studies adapting such an approach. He et al. (2002) proposed a topic identification algorithm that uses the Dempster-Shafer Theory (Shafer 1976). Their algorithm automatically identifies topic changes using statistical data from web search logs. He et al.'s (2002) approach was replicated on Excite search engine data (Ozmutlu and Cavdur 2005a) and FAST search engine data (Ozmutlu et al. 2006). The main finding of these studies was that the idea of using query patterns and time-intervals in identifying topic shifts is valuable, but can be improved. In order to improve the performance of new topic identification Ozmutlu et al. (2004a) and Ozmutlu and Cavdur (2005b) applied artificial neural networks to define boundaries of separate topics in the same session, and identified topic shifts fairly successfully. Ozmutlu (2006) found that the effect of the characteristics of web search queries on the occurrence of topic shifts/continuations is statistically significant. Furthermore, Ozmutlu, Ozmutlu, and Buyuk (2007) applied conditional probabilities to perform automatic new topic identification. These methods have applied session or new topic identification successfully; room for improvement exists, however. The methodologies in these articles have estimated too many topic shifts and as a result the precision of topic shift estimation was rather low. There is a need for a fast and efficient new topic identification that can successfully apply new topic identification.

METHODOLOGY

Research Design

New topic identification is performed on two datasets in this study: the FAST transaction log and the Excite transaction log. The FAST search engine (http://www.alltheweb.com) provided a query log of 1,257,891 for our analysis. Queries were collected from 12:00 AM (Norwegian time) on February 6, 2001 for 24 hours until 12:00 AM February 7, 2001. In the FAST data log structure, the entries are given in the order they arrive. FAST assigns a new user ID to every new user. It is possible to identify new sessions through a user ID and each query contains three fields:

• 1) Identification: anonymous code assigned by the search engine server to a user;

• 2) Time of day: in hours, minutes, and seconds;

• 3) Query: user terms as entered.

We selected a sample of 963 sessions from the entire dataset using Poisson sampling (Ozmutlu, Spink, and Ozmutlu 2002). It is necessary to select entire sessions, since the aim of the study is to perform automatic topic identification within sessions. The 963 sessions consisted of 10,007 queries. The sample size was not kept very large, since evaluation of the performance of the algorithm would require a human expert to go over all the queries. Poisson sampling provides a basis for sampling from large-scale data logs, such as the FAST search query log, while preserving the characteristics of the main dataset (Ozmutlu et al. 2002). Poisson sampling algorithms select sample points from a certain dataset by skipping a random number of observations that are distributed according to a Poisson process versus systematic sampling algorithms skipping a constant number of observations. The Poisson sampling process is a useful random sampling process, which includes properties such as unbiased sampling, proportional sampling, comparability of heterogeneous Poisson sampling arrivals, and flexibility on the stochastic arrival process from which the sample is selected. Due to the well-established property of stochastic science, the Poisson arrival see time averages (PASTA) property, Poisson sampling can be applied to any kind of stochastic arrival process (Wolff 1982), which is the most important property for the applicability of Poisson sampling on the web search query data logs, since there is no information on the type of stochastic arrival process of the web query sessions (Ozmutlu et al. 2002).

The second search query log used in this study comes from the Excite search engine (http://www.excite.com) located in the USA. The data was collected on May 4, 2001 and consists of 1.7 million for our analysis. We selected a sample of 3592 sessions (10,256 queries) using Poisson sampling.

We use the following concepts in the study (Spink et al. 2001):

• (1) Query: a set of one or more search terms; it may include advanced search features such as logical operators and modifiers.

• (2) Session: the entire set of queries by the same user over time. A session could be as short as one query or contain many unique and repeat queries.

Notation

The notation used in this study is below, and is similar to the notation used in previous studies of new topic identification (Ozmutlu et al. 2004a, 2006; Ozmutlu and Cavdur 2005a, 2005b).

Topic shift: A change from one topic to another between queries within a single-user session

Topic continuation: Staying on the same topic from one query to another within a single-user session

• N _shift : Number of queries labeled as topic shifts by genetic algorithms

• N _contin : Number of queries labeled as topic continuation by genetic algorithms

• N _{true shift} : Number of queries labeled as topic shifts by manual examination of human expert

• N _{true contin} : Number of queries labeled as topic continuation by manual examination of human expert

• N _{shift & correct} : Number of queries labeled as topic shifts by genetic algorithms and by manual examination of human expert

• N _{contin & correct} : Number of queries labeled as topic continuation by genetic algorithms and by manual examination of human expert

Type A error: This type of error occurs in situations where queries on same topics are considered as separate topic groups.

Type B error: This type of error occurs in situations where queries on different topics are grouped together into a single topic group.

Some useful formulation related to the above notation is as follows:

Precision (P) and Recall (R) are used in this study to measure the performance of new topic identification using genetic algorithms. Interpreted in terms of topic shifts, as in Ozmutlu et al. (2004a, 2006) and Ozmutlu and Cavdur (2005a, 2005b), precision (P _shift ) is the correctly estimated number of shifts by genetic algorithms among all the shifts marked by genetic algorithms (Equation (5)), and recall (R _shift ) is the correctly estimated number of shifts by genetic algorithms among all the shifts marked by the human expert (Equation (6)). On the other hand, interpreted in terms of topic continuations, precision (P _contin ) is the correctly estimated number of continuations by genetic algorithms among all the continuations marked by genetic algorithms (Equation (7)) and recall (R _contin ) is the correctly estimated number of continuations by genetic algorithms among all the continuations marked by the human expert (Equation (8)). The fifth measure, F _{β_shift} combines P _shift and R _shift to provide a single parameter to compare different results and to be consistent with previous studies. β is varied in this study between 1.3 and 1.7 to determine its best level in terms of performance measures. The sixth measure, fitness function F _{β_contin} (Equation (10)), combines P _contin and R _contin into a single value. The formulations of these measures are as follows:

Proposed Methodology

In this section, we present the methodology based on genetic algorithms to perform automatic new topic identification based on statistical characteristics of search queries, such as search patterns and time-interval of queries. The initial steps of the methodology, i.e., evaluation by human expert, separating the data into two sets, identification of search pattern, and time interval of each query in the dataset, can be found in previous articles by Ozmutlu et al. (2004a, 2006), and Ozmutlu and Cavdur (2005a,b). However they are also briefly explained in this article for readers' convenience.

Evaluation by human expert: The actual topic shifts and continuations in the 10,000 query FAST and Excite datasets are identified and marked by a human expert.

Separating the data into two sets: The data is separated to two approximately equal-sized sections. The first section of the datasets is used to apply genetic algorithms to match topic shifts and continuations with query categories and the second section is used to test the results obtained with the first section of the dataset, i.e., test the performance of genetic algorithms as a new topic identification methodology. The two halves of the datasets are approximate halves and might not be equal in size (as seen in the FAST dataset) to keep the entirety of user sessions. The Excite dataset is divided into two equal portions as a coincidence. Sizes of the datasets are given in Table 1.

TABLE 1 Size of the Datasets Used in the Study

Search engine	Excite	FAST
Entire dataset	1.7 million	1,257,891
Sample set	10,256	10,007
1st half of the sample set	5128 queries	4997 queries
2nd half of the sample set	5128 queries	5010 queries

Identification of search pattern and time-interval of each query in the dataset: Each query in the transaction logs is categorized in terms of its search pattern and time-interval. Ozmutlu (2006) showed that time-interval and search pattern of queries have a statistically significant effect on topic shifts. The classification of the search patterns is based on terms of the consecutive queries within a session. The time-interval is the difference of the arrival times of two consecutive queries. The categories of time-intervals are determined with respect to the length of the difference of the arrival times of two consecutive queries. The categorization of time-interval and search pattern remains similar to those of Ozmutlu and Cavdur (2005a,b) and Ozmutlu et al. (2004a, 2006).

The search patterns are automatically identified by a computer program. The logic for the automatic search pattern identification can be summarized in Figure 1 (Ozmutlu et al. 2004a, 2006; Ozmutlu and Cavdur 2005a,b). We use seven categories of search patterns in this study which are as follows: Ozmutlu et al. (2004a, 2006) and Ozmutlu and Cavdur (2005a,b). We also provide examples for each search pattern:

FIGURE 1 Search pattern identification algorithm.

Unique (New): the second query has no common term compared to the first query:

Next Page (Browsing): the second query requests another set of results on the first query:

Generalization: all of the terms of second query are also included in the first query but the first query has some additional terms:

Specialization: all of the terms of the first query are also included in the second query but the second query has some additional terms:

Reformulation: some of the terms of the second query are also included in the first query but the first query has some other terms that are not included in the second query. This means that the user has added and deleted some terms of the first query:

Relevance feedback: the second query has zero terms (empty) and it is generated by the system when the user selects the choice of “related pages”:

Others: If the second query does not fit any of the above categories, it is labeled as other. Any nonempty query listed after an initial empty query, such as relevance feedback belongs to the “others” category. Note that if this pattern observed on an intermediate query in a session, this property does not hold:

The categories of time-intervals are determined with respect to the length of the difference of the arrival times of two consecutive queries and are similar to those used in Ozmutlu et al. (2004a, 2006) and Ozmutlu and Cavdur (2005a,b). We use seven categories of time-intervals for a query: 0–5 minutes, 5–10 minutes, 10–15 minutes, 15–20 minutes, 20–25 minutes, 25–30 minutes, 30+ minutes.

Applying Genetic Algorithms for automatic new topic identification of search engine transaction logs: Recall that the first section of the datasets is used to apply genetic algorithms to match topic shifts and continuations with query categories. After the query categories are matched with topic shifts and continuation, the queries in the second portion of the dataset are tagged as topic shift or continuation according to the results obtained in the first portion of the dataset.

To apply such an approach, the genetic algorithm framework is modeled to solve the new topic identification problem, and match query categories with the binary information of topic shifts and continuations. There are two statistical characteristics of the transaction log queries—time-interval and search pattern—each with seven levels. We propose to use a combination of these two statistical characteristics, which yields 49 categories of queries, and any query in the transaction log falls into one of these categories. For example: Time Interval_1&Search Pattern_1; Time Interval_1&Search Pattern_2;…..; Time Interval 7&Search Pattern_7. Considering these categories, we modeled a genetic algorithm framework with 49 chromosomes. Each chromosome is labeled as 1 (topic shift exists) or 0 (no topic shifts). The gene structure for the problem is in Figure 2.

FIGURE 2 Structure of the chromosomes.

MATLAB is used to model and run the genetic algorithm structure used in the study. Some of the parameters are kept at the default values of MATLAB, unless there is necessary reason to change them. Other parameters are varied to determine the best set of parameters for the study. The parameters of the genetic algorithm structure used in the study are as follows:

• – Population type: bit string since the problem involves a binary output, i.e., topic shift or continuation. The chromosomes take the value of 0 or 1 based on whether there is a topic shift or continuation involved with the query.

• – Population size: 50

• – Fitness scaling: the current genes are presented in a rank-scaling fashion in the new generations, MATLAB default.

• – Selection rule: Stochastic uniform, MATLAB default.

• – Crossover rule: Scattered. MATLAB default.

We believe that the mutation and crossover fractions and the “ß” value in the fitness function are important parameters in the performance of automatic new topic identification, and there are no specific values assigned to these parameters in literature. Therefore, we preferred to make an elaborate experimental design, where these parameters are varied systematically. These parameters and their values that are used in the experimental design are as follows:

• – Mutation fraction: In literature, we have observed values between %0.5 and %10 for this parameter. Considering that there are 49 chromosomes in each gene; we have chosen the values of (%2.1 pertaining to 1 chromosome out of 49, %4.2 pertaining to 2 chromosomes out of 49, %6.3 pertaining to 3 chromosomes out of 49.

• – Crossover fraction: In literature, we have observed values between %50 and %95 for this parameter. Consequently, we have chosen four values for crossover fraction between these levels; 0.6, 0.7, 0.8, and 0.9.

• – β value: Several values for “ß” have been used in information science literature for the performance measure of F _ß. In our previous studies, we have used the values of 1.2, 1.3, and 1.5 to provide the best results for new topic identification. In this study, we choose to vary “ß” between 1.3 and 1.7, and use the values of 1.3, 1.4, 1.5, 1.6, 1.7 for “ß.”

A full fractional experimental design can be used to determine the effect of these parameters on the performance of new topic identification. A full fractional factorial design entails 60 run points (3∗4∗5). Sixty run points are replicated for both the Excite and the FAST datasets. The genetic algorithm applications were always terminated based on the change in the values of the fitness function (amount of change in the fitness function was around 0,000001 from one iteration to the next).

After the query categories are assigned with either topics or continuations as a result of applying genetic algorithms on the first portion of the dataset, the second portion of the datasets are tagged with the topic continuation or shift base don the results of genetic algorithms. For example, if in the first portion of the dataset a query of the category Time Interval_1&Search Pattern_1 is marked as a continuation. Whenever we meet a query of the same category in the second portion of the dataset, it is also marked as a continuation. Similarly, if in the first portion of the dataset a query of the category Time Interval_1&Search Pattern_5 is marked as a shift, whenever we meet a query of the same category in the second portion of the dataset, it is also marked as a shift. The results of the tests on the second half of the Excite 2001 and FAST datasets are in Tables 2 and 3, respectively.

TABLE 2 Experimental Design Results for the Excite 2001 Dataset

Run	Mutation fraction	Çrossover fraction	ß	Type A error	Type B error	N shift	N contin	P shift	R shift	F ß(shift)
1	%2.1	0.6	1.3	196	41	427	2967	0,541	0,8493	0,7008
2	%2.1	0.6	1.4	196	41	427	2967	0,541	0,8493	0,7122
3	%2.1	0.6	1.5	216	35	453	2941	0,5232	0,8713	0,7232
4	%2.1	0.6	1.6	216	35	453	2941	0,5232	0,8713	0,7341
5	%2.1	0.6	1.7	216	35	453	2941	0,5232	0,8713	0,744
6	%2.1	0.7	1.3	196	41	427	2967	0,541	0,8493	0,7008
7	%2.1	0.7	1.4	196	41	427	2967	0,541	0,8493	0,7122
8	%2.1	0.7	1.5	216	35	453	2941	0,5232	0,8713	0,7232
9	%2.1	0.7	1.6	216	35	453	2941	0,5232	0,8713	0,7341
10	%2.1	0.7	1.7	216	35	453	2941	0,5232	0,8713	0,744
11	%2.1	0,8	1.3	196	41	427	2967	0,541	0,8493	0,7008
12	%2.1	0,8	1.4	196	41	427	2967	0,541	0,8493	0,7122
13	%2.1	0,8	1.5	216	35	453	2941	0,5232	0,8713	0,7232
14	%2.1	0,8	1.6	216	35	453	2941	0,5232	0,8713	0,7341
15	%2.1	0,8	1.7	216	35	453	2941	0,5232	0,8713	0,744
16	%2.1	0.9	1.3	196	41	427	2967	0,541	0,8493	0,7008
17	%2.1	0.9	1.4	197	41	428	2966	0,5397	0,8493	0,7114
18	%2.1	0.9	1.5	216	35	453	2941	0,5232	0,8713	0,7232
19	%2.1	0.9	1.6	216	35	453	2941	0,5232	0,8713	0,7341
20	%2.1	0.9	1.7	216	35	453	2941	0,5232	0,8713	0,744
21	%4.2	0.6	1.3	196	41	427	2967	0,541	0,8493	0,7008
22	%4.2	0.6	1.4	196	41	427	2967	0,541	0,8493	0,7122
23	%4.2	0.6	1.5	216	35	453	2941	0,5232	0,8713	0,7232
24	%4.2	0.6	1.6	216	35	453	2941	0,5232	0,8713	0,7341
25	%4.2	0.6	1.7	216	35	453	2941	0,5232	0,8713	0,744
26	%4.2	0.7	1.3	196	41	427	2967	0,541	0,8493	0,7008
27	%4.2	0.7	1.4	196	41	427	2967	0,541	0,8493	0,7122
28	%4.2	0.7	1.5	216	35	453	2941	0,5232	0,8713	0,7232
29	%4.2	0.7	1.6	216	35	453	2941	0,5232	0,8713	0,7341
30	%4.2	0.7	1.7	216	35	453	2941	0,5232	0,8713	0,744
31	%4.2	0,8	1.3	196	41	427	2967	0,541	0,8493	0,7008
32	%4.2	0,8	1.4	196	41	427	2967	0,541	0,8493	0,7122
33	%4.2	0,8	1.5	216	35	453	2941	0,5232	0,8713	0,7232
34	%4.2	0,8	1.6	216	35	453	2941	0,5232	0,8713	0,7341
35	%4.2	0,8	1.7	216	35	453	2941	0,5232	0,8713	0,744
36	%4.2	0.9	1.3	196	41	427	2967	0,541	0,8493	0,7008
37	%4.2	0.9	1.4	196	41	427	2967	0,541	0,8493	0,7122
38	%4.2	0.9	1.5	216	35	453	2941	0,5232	0,8713	0,7232
39	%4.2	0.9	1.6	216	35	453	2941	0,5232	0,8713	0,7341
40	%4.2	0.9	1.7	216	35	453	2941	0,5232	0,8713	0,744
41	%6.3	0.6	1.3	196	41	427	2967	0,541	0,8493	0,7008
42	%6.3	0.6	1.4	196	41	427	2967	0,541	0,8493	0,7122
43	%6.3	0.6	1.5	216	35	453	2941	0,5232	0,8713	0,7232
44	%6.3	0.6	1.6	216	35	453	2941	0,5232	0,8713	0,7341
45	%6.3	0.6	1.7	216	35	453	2941	0,5232	0,8713	0,744
46	%6.3	0.7	1.3	196	41	427	2967	0,541	0,8493	0,7008
47	%6.3	0.7	1.4	196	41	427	2967	0,541	0,8493	0,7122
48	%6.3	0.7	1.5	216	35	453	2941	0,5232	0,8713	0,7232
49	%6.3	0.7	1.6	216	35	453	2941	0,5232	0,8713	0,7341
50	%6.3	0.7	1.7	216	35	453	2941	0,5232	0,8713	0,744
51	%6.3	0,8	1.3	196	41	427	2967	0,541	0,8493	0,7008
52	%6.3	0,8	1.4	196	41	427	2967	0,541	0,8493	0,7122
53	%6.3	0,8	1.5	216	35	453	2941	0,5232	0,8713	0,7232
54	%6.3	0,8	1.6	216	35	453	2941	0,5232	0,8713	0,7341
55	%6.3	0,8	1.7	216	35	453	2941	0,5232	0,8713	0,744
56	%6.3	0.9	1.3	196	41	427	2967	0,541	0,8493	0,7008
57	%6.3	0.9	1.4	196	41	427	2967	0,541	0,8493	0,7122
58	%6.3	0.9	1.5	216	35	453	2941	0,5232	0,8713	0,7232
59	%6.3	0.9	1.6	216	35	453	2941	0,5232	0,8713	0,7341
60	%6.3	0.9	1.7	216	35	453	2941	0,5232	0,8713	0,744

TABLE 3 Experimental Design Results for the FAST Dataset

Run	Mutation fraction	Çrossover fraction	ß	Type A error	Type B error	N shift	N contin	P shift	R shift	F ß(shift)
1	%2.1	0.6	1.3	523	7	826	3658	0,3668	0,9774	0,6038
2	%2.1	0.6	1.4	523	7	826	3658	0,3668	0,9774	0,6256
3	%2.1	0.6	1.5	523	7	826	3658	0,3668	0,9774	0,6463
4	%2.1	0.6	1.6	527	6	831	3653	0,3658	0,9806	0,6662
5	%2.1	0.6	1.7	527	6	831	3653	0,3658	0,9806	0,6848
6	%2.1	0.7	1.3	523	7	826	3658	0,3668	0,9774	0,6038
7	%2.1	0.7	1.4	523	7	826	3658	0,3668	0,9774	0,6256
8	%2.1	0.7	1.5	527	6	831	3653	0,3658	0,9806	0,6464
9	%2.1	0.7	1.6	527	6	831	3653	0,3658	0,9806	0,6662
10	%2.1	0.7	1.7	527	6	831	3653	0,3658	0,9806	0,6848
11	%2.1	0,8	1.3	523	7	826	3658	0,3668	0,9774	0,6038
12	%2.1	0,8	1.4	523	7	826	3658	0,3668	0,9774	0,6256
13	%2.1	0,8	1.5	527	6	831	3653	0,3658	0,9806	0,6464
14	%2.1	0,8	1.6	527	6	831	3653	0,3658	0,9806	0,6662
15	%2.1	0,8	1.7	527	6	831	3653	0,3658	0,9806	0,6848
16	%2.1	0.9	1.3	523	7	826	3658	0,3668	0,9774	0,6038
17	%2.1	0.9	1.4	523	7	826	3658	0,3668	0,9774	0,6256
18	%2.1	0.9	1.5	527	6	831	3653	0,3658	0,9806	0,6464
19	%2.1	0.9	1.6	527	6	831	3653	0,3658	0,9806	0,6662
20	%2.1	0.9	1.7	527	6	831	3653	0,3658	0,9806	0,6848
21	%4.2	0.6	1.3	523	7	826	3658	0,3668	0,9774	0,6038
22	%4.2	0.6	1.4	523	7	826	3658	0,3668	0,9774	0,6256
23	%4.2	0.6	1.5	527	6	831	3653	0,3658	0,9806	0,6464
24	%4.2	0.6	1.6	527	6	831	3653	0,3658	0,9806	0,6662
25	%4.2	0.6	1.7	527	6	831	3653	0,3658	0,9806	0,6848
26	%4.2	0.7	1.3	523	7	826	3658	0,3668	0,9774	0,6038
27	%4.2	0.7	1.4	523	7	826	3658	0,3668	0,9774	0,6256
28	%4.2	0.7	1.5	527	6	831	3653	0,3658	0,9806	0,6464
29	%4.2	0.7	1.6	527	6	831	3653	0,3658	0,9806	0,6662
30	%4.2	0.7	1.7	527	6	831	3653	0,3658	0,9806	0,6848
31	%4.2	0,8	1.3	523	7	826	3658	0,3668	0,9774	0,6038
32	%4.2	0,8	1.4	523	7	826	3658	0,3668	0,9774	0,6256
33	%4.2	0,8	1.5	523	7	826	3658	0,3668	0,9774	0,6463
34	%4.2	0,8	1.6	527	6	831	3653	0,3658	0,9806	0,6662
35	%4.2	0,8	1.7	527	6	831	3653	0,3658	0,9806	0,6848
36	%4.2	0.9	1.3	523	7	826	3658	0,3668	0,9774	0,6038
37	%4.2	0.9	1.4	523	7	826	3658	0,3668	0,9774	0,6256
38	%4.2	0.9	1.5	527	6	831	3653	0,3658	0,9806	0,6464
39	%4.2	0.9	1.6	527	6	831	3653	0,3658	0,9806	0,6662
40	%4.2	0.9	1.7	527	6	831	3653	0,3658	0,9806	0,6848
41	%6.3	0.6	1.3	523	7	826	3658	0,3668	0,9774	0,6038
42	%6.3	0.6	1.4	523	7	826	3658	0,3668	0,9774	0,6256
43	%6.3	0.6	1.5	527	6	831	3653	0,3658	0,9806	0,6464
44	%6.3	0.6	1.6	527	6	831	3653	0,3658	0,9806	0,6662
45	%6.3	0.6	1.7	527	6	831	3653	0,3658	0,9806	0,6848
46	%6.3	0.7	1.3	523	7	826	3658	0,3668	0,9774	0,6038
47	%6.3	0.7	1.4	523	7	826	3658	0,3668	0,9774	0,6256
48	%6.3	0.7	1.5	523	7	826	3658	0,3668	0,9774	0,6463
49	%6.3	0.7	1.6	527	6	831	3653	0,3658	0,9806	0,6662
50	%6.3	0.7	1.7	527	6	831	3653	0,3658	0,9806	0,6848
51	%6.3	0,8	1.3	523	7	826	3658	0,3668	0,9774	0,6038
52	%6.3	0,8	1.4	523	7	826	3658	0,3668	0,9774	0,6256
53	%6.3	0,8	1.5	527	6	831	3653	0,3658	0,9806	0,6464
54	%6.3	0,8	1.6	527	6	831	3653	0,3658	0,9806	0,6662
55	%6.3	0,8	1.7	527	6	831	3653	0,3658	0,9806	0,6848
56	%6.3	0.9	1.3	523	7	826	3658	0,3668	0,9774	0,6038
57	%6.3	0.9	1.4	523	7	826	3658	0,3668	0,9774	0,6256
58	%6.3	0.9	1.5	527	6	831	3653	0,3658	0,9806	0,6464
59	%6.3	0,9	1,6	527	6	831	3653	0,3658	0,9806	0,6662
60	%6.3	0,9	1,7	527	6	831	3653	0,3658	0,9806	0,6848

After the runs are completed, analysis of variance is performed to test whether the factors considered in the experimental design have a statistically significant effect on the performance measures of new topic identification. The performance measures used for ANOVA are N _shift , N _contin , Type A error and Type B error. Other performance measures such as P, R, and F _ß are functions of N _shift , N _contin , Type A error, and Type B error. Two factor interactions are also considered in the study which makes a total of six factors. The hypotheses for testing the effect of the design factors and two factor interactions are in the following equation:

If H ₀ cannot be rejected, it is concluded that a factor's effect on the performance measure is not statistically significant. If H ₀ is rejected, it is concluded that a factor's effect on the performance measure is statistically significant. Then, the factor combinations providing the best fitness function value can be determined and used for new topic identification.

RESULTS AND DISCUSSION

At first glance, it is beneficial to recognize the true characteristics of the transaction logs as the human expert analyzed them. When the human expert evaluated the 10,256 Excite query dataset, 6001 topic continuations and 663 topic shifts were found. Eliminating the last query of each session leaves 6664 queries to be included in the analysis. There are 2879 topic continuations/391 topic shifts in the first half, and 3122 topic continuations/272 topic shifts in the second half of the dataset. The structure of the dataset in terms of the number of sessions and the number of queries included in the analysis can be seen in Table 4.

TABLE 4 Topic Shifts and Continuations in the Excite and FAST Datasets as Evaluated by Human Experts

	Total number of queries	Number of sessions	No. of queries considered for genetic algorithms	Total number of shifts marked by the human expert	Total no. of continuations marked by the human expert
1st half of dataset	5128-Excite 2001	1858-Excite 2001	3270-Excite 2001	391-Excite 2001	2879-Excite 2001
	4997-Fast	437-Fast	4560-Fast	386-Fast	4174-Fast
2nd half of dataset	5128-Excite 2001	1734-Excite 2001	3394-Excite 2001	272-Excite 2001	3122-Excite 2001
	5010-Fast	526-Fast	4484-Fast	310-Fast	4174-Fast
Entire dataset	10256-Excite 2001	3592-Excite 2001	6664-Excite 2001	663-Excite 2001	6001-Excite 2001
	10007-Fast	963-Fast	9044-Fast	696-Fast	8348-Fasts

When the human expert evaluated the FAST dataset, 8348 topic continuations and 696 topic shifts were found. Eliminating the last query of each session leaves 9044 queries to be included in the analysis. In the first half of the dataset (4997 queries), there were 437 user sessions. Thus 4560 queries of the first half of the dataset are used for computing transition probabilities. Out of 4560 queries, there are 4174 topic continuations and 386 topic shifts. In the second half of the dataset, there were 5010 queries and 526 user sessions. Eliminating the last query of each session leaves 4484 queries to be included in the analysis. Out of 4484 queries, 4174 were topic continuations, whereas 310 were topic shifts.

After investigating the results of genetic algorithms application in Tables 2 and 3, we observe that the genetic algorithm yields similar results across different values of the design factors crossover fraction and design fraction. The value of the F _ß(shift) performance measure primarily changes based on the value of the ß parameter. In both datasets, the runs yielding the best values for F _ß(shift) were runs 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, and 60, where ß equals 1.7. The result of these runs is shown in Table 5. For smaller values of ß, such as 1.3 and 1.4, Type A errors seem to decrease and Type B errors seem to increase, and the number of queries marked as shifts also seem to decrease. This result is due to the formulation of F _ß, which puts more emphasis on Type B errors than Type A errors. The importance of Type B errors is a subjective issue, and an extensive study should be conducted to develop different performance measures than F _ß; but this is an area of further research.

TABLE 5 The Results of the Best Run for Genetic Algorithm on the Excite and FAST Datasets

Dataset	Origin of results	Queries included in analysis	No. of topic shifts	No. of topic continuations	Correctly estimated number of shifts	Correctly estimated number of continuations	Type A error	Type B error	P shift	R shift	P contin	R contin	F ß(shift)	F ß(contin)
Excite 2001	GAs	3394	N shift  = 453	N contin  = 2941	N shift&correct  = 237	N contin&correct  = 2906	216	35	0.52	0.87	0.988	0.930	0.744	0.947
	Human expert	3394	N trueshift  = 272	N truecontin  = 3122	–	–	–	–	–	–	–	–	–	–
FAST	GAs	4484	N shift  = 831	N contin  = 3653	N shift&correct  = 304	N contin&correct  = 3647	527	6	0.37	0.98	0.998	0.874	0.6848	0.908
	Human expert	4484	N trueshift  = 310	N truecontin  = 4174	–	–	–	–	–	–	–	–	–	–

For the Excite dataset, we observe that genetic algorithm application marked 2941 queries as topic continuation, whereas the human expert identified 3122 queries as topic continuation. Similarly, the genetic algorithm approach marked 453 queries as topic shifts, whereas the human expert identified 272 queries as topic shifts. 237 out of 272 topic shifts are identified correctly, yielding an R _shift value of 0.8713, and 2906 out of 2133 topic continuations are identified correctly, yielding an R _contin value of 0.93. These results demonstrate that the topic shifts were estimated fairly correctly and topic continuations were estimated almost entirely correct by genetic algorithms. On the other hand, the genetic algorithm application yielded 453 topic shifts, when actually there are 272 topic shifts, giving a value of 0.52 for P _shift . Although this result means that the genetic algorithm approach overestimates the number of topic shifts, it still yields the best results for P _shift , compared to previous studies with other datasets. Similarly, the value F _ß(shift) is the highest ever obtained for any dataset, 0.744. Recalling that the research objective of this study was overcoming the problems of the previous studies, we can conclude that genetic algorithms might have the potential to improve the performance of new topic identification in terms of shift-based measures, which were fairly problematic in previous studies. In terms of topic continuations P _contin was 0.99, i.e., almost all the topic continuations marked by the genetic algorithms approach were correct. For the FAST dataset, we observe the values of 0.37 for P _shift , 0.98 for R _shift , 0.87 for R _contin , and 0.99 for P _contin . The overestimation of topic shifts is still a problem with the FAST dataset; continuation-based measures, however, provided satisfactory results.

As mentioned in the methodology section, analysis of variance is performed after the runs are completed. The analysis of variance yields the results listed in Tables 6 and 7 for the Excite and FAST datasets, respectively.

TABLE 6 ANOVA for the Excite 2001 Dataset, Analyzing the Effect of Statistical Characteristics of Queries on New Topic Identification Performance

	Dependent variables
	N shift				N contin				Type A error				Type B error
Source of variation	Sum of squares	Degrees of freedom	Mean square	F	SS	Df	MS	F	SS	df	MS	F	SS	df	MS	F
Mutation fr.	0	1	0	0	0	1	0	0	0,03	1	0,03	0,0011	0	1	0	0
Crossover fr.	0	1	0	0	0	1	0	0	0,03	1	0,03	0,0011	0	1	0	0
ß	7285,2	1	7285,2	159,7	7285,2	1	7285,2	159,7	4308,0	1	4308,0	159,79	388,8	1	388,8	158,7
Mut∗cross	0	1	0	0	0	1	0	0	0,04	1	0,04	0,0015	0	1	0	0
Mut∗ ß	0	1	0	0	0	1	0	0	0,01	1	0,01	0,00037	0	1	0	0
Cross∗ ß	0	1	0	0	0	1	0	0	0,01	1	0,01	0,00037	0	1	0	0
Error	2418,8	53	45,6		2418,8	53	45,6		1428,9	53	26,96		129,6	53	2,45
Total	9704,2	59			9704,2	59				59	5737			59

TABLE 7 ANOVA for the FAST Dataset, Analyzing the Effect of Statistical Characteristics of Queries on New Topic Identification Performance

	Dependent variables
	N shift				N contin				Type A error				Type B error
Source of variation	Sum of squares	Degrees of freedom	Mean square	F	SS	Df	MS	F	SS	df	MS	F	SS	df	MS	F
Mutation fr.	0	1	0	0	0	1	0	0	0	1	0	0	0	1	0	0
Crossover fr.	0.75	1	0.75	0.397	0.75	1	0.75	0.397	0.48	1	0.48	0.397	0.03	1	0.03	0.0397
ß	270	1	270	143.08	270	1	270	143.08	172,8	1	172.8	143.05	10.8	1	10.8	143.05
Mut∗cross	0.5	1	0.5	0.265	0.5	1	0.5	0.265	0.32	1	0.32		0.02	1	0.02	0
Mut∗ ß	0	1	0	0	0	1	0	0	0	1	0	0	0	1	0	0
Cross∗ ß	0	1	0	0	0	1	0	0	0	1	0	0	0	1	0	0
Error	100	53	1887		100	53	1887		64	53	1208	0.265	4	53	0.0755	0.265
Total		59				59				59				59

The critical F value used in this study is F _{0, 05, 1, 53} ≈ ∼4.02. ANOVA confirms the results that we have reached by initially observing the results in Tables 2 and 3. The ß factor in the fitness function of the genetic algorithm has a statistically significant effect on the performance measures of new topic identification. Increasing values of ß, increases N _shift and Type A errors, but decreases N _contin and Type B error. The other factors do not have an effect on the dependent variables and on F _ß(shift), the fitness function. The performance of new topic identification with genetic algorithms is directly affected from the ß value, since F _ß(shift) is the fitness function. Genetic algorithms might have provided different or better results with alternative fitness functions. As mentioned in the previous paragraphs, it is an important line of research to develop alternative performance measures for automatic new topic identification specifically, and information science generally. Then, new topic identification with genetic algorithms should be performed with alternative fitness functions. This is an area of further research.

CONCLUSION AND FURTHER RESEARCH

New topic identification and session identification are important problems in information science. This study proposes to apply genetic algorithms to automatically define topic boundaries in a user session by using statistical characteristics of queries, such as time-intervals and query reformulation patterns. Transaction logs from the FAST and Excite search engines are used. An elaborate experimental design scheme was used to determine the best set of parameters of the genetic algorithm to optimize the performance measures of new topic identification. As a result of genetic algorithms, the performance measures yielded fairly satisfactory results, especially for the Excite dataset. The overestimation of topic shifts still exists for the FAST dataset, but stays at moderate values for the Excite dataset. Genetic algorithms have performed very well for continuation-based measures on both datasets. Therefore, we conclude that genetic algorithms are fairly successful in automatic identification of topic shifts and continuations in search engine data logs, and have a promising application potential in information science. Future work includes solving the problem of overestimation of topic shifts, improving the other performance measures, and integrating genetic algorithms as the automatic new topic identification tool in information retrieval and search engine algorithms.

This research has been funded by TUBITAK, Turkey, and is a National Young Researchers Career Development Project 2005, fund number 105M320, “Application of Web Mining and Industrial Engineering Techniques in the Design of New Generation Intelligent Information Retrieval Systems.”