Apparatus and method for discovering context groups and document categories by mining usage logs

[0002] This invention pertains to text retrieval systems. More particularly, this invention relates to data mining systems and methods for discovering context groups and document categories by mining usage logs.

[0003] Text retrieval systems are concerned with locating documents relevant to a user's information needs from a collection of documents. The user describes their information needs using a query consisting of a number of words. Text retrieval systems compare the query with the documents in the collection and return the documents that are likely to satisfy the information needs. The intelligence of a text retrieval engine relates to the ability to determine how relevant a document is to a given query. Computation of the relevance largely depends on the words used and operators used in a given query. Generally, the chances of retrieving a document are high if queries contain words that occur in the documents the user wishes to retrieve. However, the words users use to describe concepts in their queries are often different than the words authors use to describe the same concepts in the documents. It has been found through experiments that two people use the same term to describe an object less than 20% of the time. The problem which results from this inconsistent word usage is referred to as a word mismatch problem. The problem is more severe for short queries than for long elaborate queries because as queries get longer, there is more chance that some important words will occur in both the query and the relevant documents.

[0004] The word mismatch problem is often solved by computing relationships between words in a given domain. In response to a query, the text retrieval system returns not only those documents that contain the words in the query, but also those documents that contain their related word as given by the word relationships. Word relationships are usually computed by some form of corpus analysis and by using domain knowledge. For example, stemming, a popular method to compute word relationships, reduces words to common roots. As a result, documents containing morphological variants of the query words are also included in the response. Another popular approach of computing word relationships is to use manual or automatically generated thesauri. Manual thesauri are built using human experience and expertise, and hence, are costly to build. Previously, corpus analysis has been used to generate a thesaurus automatically from the content of documents. Automatic construction of thesauri is based on a well-known hypothesis call the “association hypothesis” which states that related terms in the corpus tend to co-occur in documents. “Association hypothesis” can capture word relationships that are specific to the corpus. However, generating a thesaurus automatically from the entire corpus is very expensive if the corpus contains millions of documents. It is also hard to maintain if documents are frequently added to the corpus.

[0005] Recently, it has been shown that word relationships computed from the top n documents relevant to a query outperformed the thesaurus generated from the entire corpus. Relevance of a document to a given query is computed by the text retrieval system, solely based on the words that appear in the query and the document and may not conform to the user's opinion of relevance.

[0006] Capturing relationships between keywords by automatic thesaurus construction has previously been studied extensively. Some of the earliest work in automatic thesaurus construction was based on term clustering. According to this work, related terms are grouped into clusters based upon co-occurrence of the terms in the corpus. Terms that co-occur with one or more query terms are used in query expansion. Previously, it has been proposed that expansion terms must co-occur with all query terms in order to achieve higher retrieval effectiveness. Techniques have been proposed that do not require analyzing all documents in the corpus for computing the thesaurus. Expansion terms are obtained by co-occurrence analysis of all query terms in a query Q and other terms from top-ranked documents (or all documents) in the result of Q.

[0007] Therefore, there exists a need to improve the completeness of information that is mined and a need to address word mismatch problems incurred with prior art techniques based on historical information mined from usage logs. Usage logs record data about the queries submitted by users and the documents retrieved by users.

[0008] An apparatus and method are provided for discovering context groups and document categories by mining usage logs of users.

[0009] According to one aspect, an apparatus is provided for relating user queries and documents. The apparatus includes a client, a server, a communications pathway, and a database. The client is configured to enable a user to submit user queries to locate documents. The server has a data mining mechanism configured to receive the user queries and generate information retrieval sessions. The communications pathway extends between the client and the server. The database is provided in communication with the client and the server. The database stores data in the form of usage logs generated from the information retrieval sessions generated by a user at the client. The data mining mechanism includes a clustering algorithm operative to identify context groups and usage categories. The data mining mechanism is operative to identify query contexts associated with individual queries from the usage logs, partition the queries into context groups having similar contexts, and compute multiple context groups associated with specific query keywords from the usage logs.

[0010] According to another aspect, a method is provided for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system. The method includes: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users.

[0011] According to yet another aspect, a method is provided for relating user queries and documents using usage logs from retrieval sessions from a text retrieval system. The method includes: identifying contexts associated with a user query comprising at least one specific query keyword; identifying user queries having similar query contexts; partitioning user queries into groups based upon similarity of the query contexts; merging the groups to compute multiple contexts associated with specific query keywords; and applying a clustering algorithm to identify similar query contexts based upon the query keywords to generate context groups that associate keywords with documents accessed by users.

[0012] Preferred embodiments of the invention are described below with reference to the following accompanying drawings depicting examples embodying the best mode for practicing the invention.

[0013] FIG. 1 is a schematic block diagram illustrating a text retrieval system for mining usage logs.

[0014] FIG. 2 is an exemplary format for a usage log, in this case a retrieval system log, for the text retrieval system of FIG. 1.

[0015] FIG. 3 is an exemplary list of documents that are selectively accessible by a user from a database, and from which usage logs are generated each time a user accesses such documents.

[0016] FIG. 4 is an exemplary list of retrieval sessions from a user accessing the list of documents in FIG. 3.

[0017] FIG. 5 is an exemplary query graph for the usage log generated by the retrieval sessions of FIG. 4.

[0018] FIG. 6 is an exemplary graph of features and one vector for each query context of FIG. 5.

[0019] FIG. 7 is a state diagram for a multiple-level context directed acyclic graph (DAG).

[0020] This disclosure of the invention is submitted in furtherance of the constitutional purposes of the U.S. Patent Laws “to promote the progress of science and useful arts”. U.S. Constitution, Article 1, Section 8.

[0021] An apparatus and method are provided for mining usage logs to discover context groups and document categories when conducting user queries or retrieval sessions. A new text retrieval mechanism is utilized having an infrastructure that uses retrieval system logs organized as retrieval sessions. Keyword associations and document categories are computed from user logs.

[0022] Reference will now be made to a preferred embodiment of Applicant's invention. One exemplary implementation is described below and depicted with reference to the drawings comprising a text retrieval mechanism that, in one embodiment, is implemented over a network. While the invention is described via a preferred embodiment, it is understood that the description is not intended to limit the invention to this embodiment, but is intended to cover alternatives, equivalents, and modifications such as are included within the scope of the appended claims.

[0023] In an effort to prevent obscuring the invention at hand, only details germane to implementing the invention will be described in great detail, with presently understood peripheral details being incorporated by reference, as needed, as being presently understood in the art.

[0024] FIG. 1 illustrates a data mining apparatus identified generally by reference numeral 10. According to one construction, apparatus 10 is implemented over a communication pathway 12 within a client/server network environment 14 which include client 16 and server 18. A client/server network environment 14 includes communication pathway 12, which in one form includes a network 20. Also, according to one construction, network 20 is a local area network. Additionally, or optionally, such local area network 20 is provided within the Internet 22. Accordingly, network 20 can also include the Internet 22. According to an even further construction, Internet 22 is the World Wide Web (WWW) 24.

[0025] This invention proposes a novel and powerful approach to solving the previously described word mismatch problem incurred with prior art techniques based on historical information. Many systems usually record the user interactions in a log for purposes such as debugging. For example, many systems record user interaction over the world wide web (WWW) in web server logs. Such logs contain valuable information about past user interactions. The ability to gather user experiences, or requests, from these logs is a powerful tool. The gathering of this information is unobtrusive, or is not readily noticeable from the users perspective. User actions are simply recorded, and the user is not required to do anything special. Once these user actions have been recorded in logs, the actions can also be recreated by accessing the logs in order to understand user behavior.

[0026] Obviously, information recorded in the logs depends on the functionality of the system and what user and/or system actions are logged, or recorded, in the logs. For a text retrieval system, logs may contain, for each user query, the query itself, the number of documents from the collection that satisfy the query, the documents opened by the user, any feedback information on the relevance of the query, or other similar information. Past user behavior which is recorded in text retrieval system logs can be effectively exploited in order to bridge the gap between the keywords used to express users' problems and the documents that are relevant to the problem. By analyzing the usage, an attempt can be made to understand the intent of the keywords that have been entered by the user based on the documents which were actually read or reviewed by the user.

[0027] For example, suppose it is determined by reviewing usage logs that one user submitted the query “pfs” (which stands for portable file system in HP UX), then perused the same set of documents as another user whose query was “cdrom”. Then, we may conclude that “pfs” and “cdrom” are synonyms. Another scenario comes about where two users have previously issued identical queries, say, “pfs”, but have then gone on to read different documents, as evidenced by each user's usage logs. For example, one user has read documents associated with “pfs” and “mount”, and the other user has read documents related to “pfs” and “fail”. For this particular example, we can assume that there are at least two different contexts associated with the keyword “pfs”.

[0028] Applicant's technique implements a “log relationship method” in order to mine (or locate) relationships between queries and/or keywords and documents using the text retrieval system's logs. In particular, for each keyword appearing in the log, the log relationship method identifies the following: a) all keywords it is related to; b) different contexts associated with this keyword; and c) a set of relevant documents for each context associated with this keyword.

[0029] The log relationship method described in greater detail below captures and summarizes past user interaction from the logs. Typically user queries tend to focus only on a subset of documents in the corpus at any given time. Therefore, the information mined from the logs is inherently incomplete compared to corpus analysis. On the other hand, logs record valuable information about preferred keywords used to access documents, and the relationship between documents/keywords as perceived by users. Such information cannot be obtained from corpus analysis.

[0030] A. Retrieval System Logs

[0031] It is assumed that retrieval system logs will be organized as retrieval sessions. A retrieval session is understood to include all information pertaining to one user query and is represented by the query itself. For purposes of this disclosure, the phrases “user query” and “retrieval session” will be used interchangeably. It will be assumed that a retrieval session contains the query itself, the number of documents found to satisfy the query, and the list of document “ids”, or identifiers, retrieved by the user for reading, which we refer to as the list of opened document ids.

[0032] FIG. 2 illustrates an exemplary format for a retrieval system log. In FIG. 2, q_is are queries, n_iis the number of documents found in the document collection matching q_i, and d_is are opened document ids for the corresponding q_is, where i=1, 2, 3.

[0033] It is assumed that the log retrieval system does not contain any relevance feedback information. This is a reasonable assumption because explicit feedback is hard to obtain. However, various heuristics can be used in order to assign a relevance ranking to a document in the logs. It will be assumed that a document is relevant to a particular query if a user opened this document for reading. The length of time this document was read can also be considered in order to decide if it was relevant, if the log records timestamps for each action. The longer the document was left open, the higher is its relevance rank. Also, there exist scenarios where the last document read by a user is most relevant to the query, assuming that the log records the order in which a user opened the documents. Currently, a document is considered to be relevant to a query if the user opens this document for reading.

[0034] In practice, a user may submit multiple queries in an attempt to solve the same problem. Subsequent queries may be refinements of the initial query. It is currently assumed that each query is a separate session. This technique can be extended to the case where each retrieval session includes multiple queries, or a user problem rather than a single query.

[0035] B. Approach

[0036] The computation of contexts associated with specific keywords is a two-step process. In the first step, which is hereafter referred to as the context discovery step, queries having similar context are partitioned into groups. In the next step, which is hereafter referred to as the context merge step, these groups are merged in order to compute multiple contexts associated with query keywords. The following sections illustrate the implementation of the technique.

[0037] C. Context Discovery

[0038] The retrieval system log is configured to contain user retrieval sessions. Each retrieval session includes the user query that initiated the retrieval session, the number of documents that match the query, and the list of opened document identifiers (ids). Since user queries are typically short, queries cannot be used alone to arrive at the context the user had in mind when they issued the query. This difficulty is furthered by the fact that different keywords may be used in a manner intended to mean the same concept. However, the specific document ids that have been identified as being opened by the user provide valuable information about the intentions of the user at the time they submitted the query.

[0039] In order to identify contexts that are associated with a query, clustering techniques are used. Let O_idenote the set of opened document ids associated with query q_i. We say that two queries q_iand q_jare related if O_i∩O_j≧k where k is specified by the user. In order to group all queries with similar contexts, a query graph G(V,E) is defined. G is an undirected graph with a vertex for each query in the retrieval system log. There is an edge between q_iand q_jif q_iand q_jare related.

[0040] For purposes of this disclosure, a “query context” is defined as a set of all the queries that belong to a connected component of G. Also for purposes of this disclosure, a “relevant document set” is defined as being associated with a query context Q, where Q={q_l, . . . , q_p}, is denoted by rel-doc (Q).

[0041] D. Context Merge

[0042] The above-described context discovery step is operative to group queries solely based on the corresponding sets of opened document ids. Hence, even though two queries contain the same keywords, they may belong to different contexts. In order to discover multiple contexts of keywords, query contexts are merged if they contain similar keywords. What finally results is a set of context groups where each context group contains one or more query contexts.

[0043] Clustering techniques are applied in order to identify similar query contexts. Query contexts are clustered based on keywords. Each query context is first represented as a vector in a high-dimensional space; the clustering algorithm is applied to the vector.

[0044] Selecting features: Let Q_l. . . Q_jbe the query contexts computed by the context discovery step. Let Q=∪_i=l.Q_i. Let W be the set of all words in Q. Stop words or non-content bearing words such as and, or from W are eliminated. Then the words in Ware stemmed in order to reduce words to their common roots. Let the final set of words be W′ and let|W′| be m. The words in W′ are used as features for the clustering algorithm.

[0045] The following conditions are applied when converting query contexts into vectors in m-dimensional space: Let W′={w_l, . . . w_m}. Let V_i=<v_l, . . . v_m>be the m-dimensional vector representing query context Q_i. Let T_ibe the total number of words in Q_i(after eliminating stop words). Let f_lbe the occurrence frequency of w_lin Q_i. Then, v_p(1≦p≦m)=f_p|T_i. Additionally, v_p=0 if w_p∉Q_i.

[0046] According to one implementation for a clustering algorithm, a Self-Organizing Map clustering (SOM) algorithm is applied to the vectors. The SOM algorithm orders the input vectors onto a map such that similar vectors lie near, or proximate, each other. The map typically consists of a regular grid of units and each unit is assigned a model vector. Each input vector v is mapped to the unit u_iwhose model vector best represents the input vector. For example, the Euclidean distance between the model vector corresponding to u_iand v is the smallest among all units. Then, the model vector of u_ias well as its neighboring units are updated so that the updated model vectors learn to represent the data sample more accurately. Details of the SOM algorithm are described in greater detail with reference to Self-Organizing Maps, by T. Kohonen, Springer Series in Information Sciences, Vol. 30, Springer, 1995. Such reference is herein incorporated by reference as indicating details of a SOM algorithm presently understood in the art.

[0047] E. Example

[0048] FIG. 3 illustrates an exemplary list of documents that are selectively accessible by a user from a database, and from which mining usage logs are generated each time a user accesses such documents.

[0049] FIG. 4 illustrates an exemplary list of retrieval sessions from a user accessing the list of documents depicted in FIG. 3.

[0050] As was discussed above, k is the number of opened document ids that two queries must have in common in order to be related. For purposes of this example, suppose k=1. The query graph for the resulting usage log is shown in FIG. 5. Based on the query graph, the query contexts can be identified as the following:

[0051] Query context Q₁: {A,B}.

[0052] Query context Q₂: {C}.

[0053] Query context Q₃: {D,E}.

[0054] Query context Q₄: {F}.

[0055] The query contexts are then clustered in order to form context groups.

[0056] FIG. 6 shows the features and one vector for each query context Q₁, . . . , Q₃. For this example, when the vectors are clustered, it is assumed that there are two context groups:

[0057] Context group C₁: {Q₁,Q₂,Q₄}.

[0058] 1. Multiple contexts of “pfs”: {{pfs, cdrom}, {pfs, mount, oracle}}.

[0059] 2. Multiple contexts of “oracle” and “mount”: {{pfs, mount, oracle}, {oracle, mount, fail}}.

[0060] Context group C₂: {Q₃}.

[0061] 1. A context of “swinstall” and “hang”: {swinstall, hang}.

[0062] In this section, a technique is described for making use of context groups that are discovered from the usage logs. Context groups and query contexts capture the associations among keywords and also with documents accessed by users and are therefore used to compute relevant document categories. One technique for using these context groups is described below.

[0063] A. Multi-level Context DAG

[0064] Each context group is represented as a directed acyclic graph which is referred to as a “multi-level context DAG”. Suppose a context group C contains query contexts Q_l, . . . , Q_p. Let CBW(Q_i) denote the set of content-bearing words in Q_i. The multi-level context DAG of C contains a node for each non-empty set of content-bearing words that can be obtained by intersecting CBW sets of one or more query contexts in C. Consequently, there is a node for each CBW(Q_i). There is an edge from node A to B in the DAG if A is a proper subset of B. All the nodes on the DAG corresponding to the query contexts are referred to as “query context nodes”. All other nodes are referred to as “general context nodes”.

[0065] A set of documents is attached to each node in a multi-level context DAG. The document sets associated with query context nodes are the corresponding rel-docs sets from the context discovery steps. The document set associated with a general context node is the union of the document sets associated with each of its children.

[0066] A multiple, or multi-level, context DAG captures the context associated with documents, from most general to most specific. The most general context associated with a document may be referred to as a “category”. A query context is the most specific content, and hence, query context nodes usually have a smaller set of documents associated with them. As the scope of query contexts is expanded by creating general context nodes, the number of documents may potentially increase.

[0067] Multi-level context DAGs are used in order to enable browsing. As shown in FIG. 7, multi-level DAGs are displayed to a user. When a user clicks on a displayed node, all documents and the keyword set associated with that node are displayed to the user.

[0068] The above-described one implementation of Applicant's technique provides a new apparatus and method for computing keyword associations and document categories from usage logs. According to prior art techniques, keyword associations were computed primarily based on corpus analysis. The present technique proves significantly better compared to the traditional approach for the following reasons.

[0069] First, for large document collections, corpus analysis is very expensive. The log relationship method does not depend on the size of the document collection, and hence is a scalable approach.

[0070] Secondly, only a small portion of documents are accessed at any given point of time. The log relationship method focuses only on these documents.

[0071] Finally, the most important advantage of the log relationship is that it tries to capture the user's intent and vocabulary by analyzing his/her behavior through the logs. This kind of information can never be collected by corpus analysis.

[0072] In compliance with the statute, the invention has been described in language more or less specific as to structural and methodical features. It is to be understood, however, that the invention is not limited to the specific features shown and described, since the means herein disclosed comprise preferred forms of putting the invention into effect. The invention is, therefore, claimed in any of its forms or modifications within the proper scope of the appended claims appropriately interpreted in accordance with the doctrine of equivalents.