QCS: A system for querying, clustering and summarizing documents

Abstract

Information retrieval systems consist of many complicated components. Research and development of such systems is often hampered by the difficulty in evaluating how each particular component would behave across multiple systems. We present a novel integrated information retrieval system—the Query, Cluster, Summarize (QCS) system—which is portable, modular, and permits experimentation with different instantiations of each of the constituent text analysis components. Most importantly, the combination of the three types of methods in the QCS design improves retrievals by providing users more focused information organized by topic.

We demonstrate the improved performance by a series of experiments using standard test sets from the Document Understanding Conferences (DUC) as measured by the best known automatic metric for summarization system evaluation, ROUGE. Although the DUC data and evaluations were originally designed to test multidocument summarization, we developed a framework to extend it to the task of evaluation for each of the three components: query, clustering, and summarization. Under this framework, we then demonstrate that the QCS system (end-to-end) achieves performance as good as or better than the best summarization engines.

Given a query, QCS retrieves relevant documents, separates the retrieved documents into topic clusters, and creates a single summary for each cluster. In the current implementation, Latent Semantic Indexing is used for retrieval, generalized spherical k-means is used for the document clustering, and a method coupling sentence “trimming” and a hidden Markov model, followed by a pivoted QR decomposition, is used to create a single extract summary for each cluster. The user interface is designed to provide access to detailed information in a compact and useful format.

Our system demonstrates the feasibility of assembling an effective IR system from existing software libraries, the usefulness of the modularity of the design, and the value of this particular combination of modules.

Introduction

Information retrieval (IR) systems provide users with a vast amount of reference material. Along with this tremendous access comes the challenge of effectively presenting the user with relevant information in response to a query. When using an IR engine to search through electronic resources, simple queries often return too many documents, including many that are not relevant to the intended search. For instance, there are several million documents on the World Wide Web pertaining to “Michael Jordan.” Most of these concern the basketball star, so it is difficult to find information about the television personality, the jazz musician, the mathematician, or the many others who share that name. It would be useful to have a system that could overcome this limitation.

One approach is to cluster the documents after retrieval and present a synopsis of each cluster so that a user can choose clusters of interest. This is the motivation for our Query, Cluster, Summarize (QCS) system, which performs the following tasks in response to a query:

• retrieves relevant documents,

• separates the retrieved documents into clusters by topic, and

• creates a summary for each cluster.

Our implementation of the QCS system partitions the code into portable modules, making it easy to experiment with different methods for handling the three main tasks listed above. In our current implementation of the QCS system, we use existing software libraries for each task. Throughout this paper, we discuss our choices for each of the modules used, but note that it is possible to exchange individual modules with other methods. Our goal in this work is to produce short summaries (∼100 words) for clusters of documents organized by topic and listed in descending order of relevance to a user’s query.

Many existing retrieval systems focus on organizing individual documents related to a query by using one or more ranking algorithms to order the retrieved documents. For example, Google uses its hyperlink analysis algorithm called PageRank to order documents retrieved from web-based collections (Google, 2006). The combination of link analysis and text-based topic analysis employed by the ExpertRank (Teoma) algorithm in the Ask search engine (Search & Median, 2006) results in implicit topic clustering. In such systems, short extractions of the documents containing one or more of the query terms are displayed to users.

Examples of retrieval systems employing clustering algorithms for organizing sets of retrieved documents include Velocity/Clusty (Vivisimo, 2006), Infonetware/RealTerm (Infogistics, 2001), WiseNut (LookSmart, 2006), Accumo (Accumo, 2006), iBoogie (CyberTavern, 2006), and the KartOO and Ujiko systems (KartOO, 2006). These systems organize the documents into clusters and generate a list of keywords associated with each cluster. The latter two systems also present graphical representations of the resulting clusters. As with the retrieval systems above, these systems also present document extractions containing one or more query terms; the only summary presented is a list of keywords.

Much of the recent research on automatic text summarization systems is available in the proceedings of the 2001–2006 Document Understanding Conferences.¹ The focus of these conferences is the evaluation and discussion of summarization algorithms and systems in performing sets of tasks on several types of document collections. Several tasks included in previous DUC evaluations focused on multidocument summarization for clusters of documents, and our participation in these evaluations led to the development of QCS.

Previous work on using a combination of clustering and summarization to improve IR is summarized in Radev, Fan, and Zhang (2001). Of existing IR systems employing this combination, QCS most resembles the NewsInEssence system (Radev, Blair-Goldensohn, Zhang, & Raghavan, 2001) in that both systems can produce multidocument summaries from document sets clustered by topic. However, NewsInEssence is designed for IR from HTML-linked document sets while QCS has been designed for IR from generic document sets.

Another system that leverages clustering and summarization for information organization similarly to QCS is the Columbia Newsblaster system (McKeown et al., 2002). Newsblaster, like NewsInEssence, is a web-based system which crawls news websites and then clusters and summarizes the news stories, but it does not currently accept queries. Recently, the value of summarization to users in IR has been demonstrated by Maña-López, de Beunaga, and Gómez-Hidalgo (2004), whose study showed increases in user recall of retrieved information when clustering and summarization were included in the output of the IR system.

We have used QCS for information retrieval in two information domains: biomedical abstracts from the US National Library of Medicine’s MEDLINE database, discussed in Dunlavy, Conroy, O’Leary, and O’Leary (2003), and newswire documents from the 2002–2004 DUC evaluations, discussed here.

In Section 2, we discuss our choices for each of the components of the QCS system. An example of use of the QCS system is presented in Section 3. Section 4 presents results of experiments evaluating some of the components of the implementation, and we conclude in Section 5.