A Method of Cluster-Based Indexing of Textual Data

A Method of Cluster-Based Indexing of Textual Data Akiko Aizawa National Institute of Informatics akiko@nii.ac.jp Abstract This paper presents a framework for cluster- ing in text-based information retrieval systems. The prominent feature of the proposed method is that documents, terms, and other related el- ements of textual information are clustered si- multaneously into small overlapping clusters. In the paper, the mathematical formulation and implementation of the clustering method are briefly introduced, together with some experi- mental results. 1 Introduction This paper is an attempt to provide a view of indexing as a process of generating many small clusters overlapping with each other. Individ- ual clusters, referred to as micro-clusters in this paper, contain multiple subsets of associated el- ements, such as documents, terms, authors, key- words, and other related attribute sets. For ex- ample, a cluster in Figure 1 represents ‘a set of documents written by a specific community of authors related to a subject represented by a set of terms’. Our motivations for considering such clusters are that (i) the universal properties of text- based information spaces, namely large scale, sparseness, and local redundancy (Joachims, 2001), may be better manipulated by focusing on only limited sub-regions of the space; and also that (ii) the multiple viewpoints of infor- mation contents, which a conventional retrieval system provides, can be better utilized by con- sidering not only the relations between ‘doc- uments’ and ‘terms’ but also associations be- tween other attributes such as ‘authors’ within the same unified framework. Based on the background, this paper presents a framework of micro-clustering, within which we adopt a probabilistic formulation of co- ST: a subset of terms SD: a subset of documents SA: a subset of authors A ’cluster’ that represents associations between ST, SA, and SD. Term space Document space Author space Figure 1: Cluster-based indexing of information spaces. occurrences of textual elements. For simplic- ity, we focus primarily on the co-occurrences between ‘documents’ and ‘terms’ in our expla- nation, but the presented framework is directly applicable to more general cases with more than two attributes. 2 Background Issues A view from indexing In information retrieval research, matrix transformation-based indexing methods such as Latent Semantic Indexing (LSI) (Deerwester et al., 1990) have recently become quite com- mon. These methods can be viewed as an es- tablished basis for exposing hidden associations between documents and terms. However, their objective is to generate a compact representa- tion of the original information space, and it is likely in consequence that the resulting orthog- onal vectors are dense with many non-zero ele- ments (Dhillon and Modha, 1999). In addition, because the reduction process is globally op- timized, matrix transformation-based methods become computationally infeasible when deal- ing with high-dimensional data. A view from clustering The document-clustering problem has also been extensively studied in the past (Iwayama and Tokunaga, 1995; Steinbach et al., 2000). The majority of the previous approaches to clus- tering construct either a partition or a hierarchy of target documents, where the generated clus- ters are …

Content truncated to 500 words