A Method of Cluster-Based Indexing of Textual Data

Akiko AizawaCOLING 2002

TL;DR

This paper introduces a novel "micro-clustering" framework for text indexing that simultaneously groups documents, terms, and other attributes into small, overlapping clusters. This approach aims to better handle the scale and sparsity of text data by focusing on localized relationships, offering a more flexible and potentially more interpretable indexing method than traditional global techniques.

What Problem Does This Paper Address?

Traditional information retrieval systems often struggle with the sheer volume and complexity of textual data. Methods like Latent Semantic Indexing (LSI) aim to reduce dimensionality by creating dense, orthogonal vectors, but this can be computationally expensive and may obscure local relationships. Similarly, standard document clustering often creates exclusive partitions or rigid hierarchies, which don't reflect the reality that documents can belong to multiple topics or be associated with various attributes (like authors or keywords) simultaneously. The paper addresses the need for an indexing method that can effectively manage large-scale, sparse text data while embracing the inherent overlap and multi-faceted nature of textual information.

Methods

The core of the paper is the "micro-clustering" framework. Instead of creating global representations or strict partitions, it generates numerous small, overlapping clusters. Each cluster is defined as a combination of a subset of terms (ST) and a subset of documents (SD). The method uses a probabilistic formulation to model the co-occurrence of terms and documents within these micro-clusters. A key innovation is the use of a "discounting" mechanism, similar to those in probabilistic language modeling, which adjusts term frequencies. This discounting allows for a trade-off between averaging probabilities within agglomerated clusters and improving probability estimations by using larger sample sizes. The "fitness" of a cluster is evaluated using an information-theoretic criterion (mutual information), which measures how well the terms and documents within the cluster are associated. Cluster generation involves an iterative process of initiation (starting with a term and expanding to related documents and terms) and improvement (eliminating less significant terms/documents).

Datasets

The experiments were conducted using the NTCIR-J11 Japanese text collection, specifically abstracts of conference papers from five Japanese academic societies: Society of Polymer Science, Japan (SPSJ), Japan Society of Civil Engineers (JSCE), Japan Society for Precision Engineering (JSPE), Ecological Society of Japan (ESJ), and Japanese Society for Artificial Intelligence (JSAI). The dataset comprised 52,867 papers, which were processed to extract nouns and compound nouns. After preprocessing, the dataset contained 772,852 distinct terms across 52,867 documents.

Key Insights and Ideas

  • Embracing Overlap: The paper strongly advocates for overlapping clusters, recognizing that real-world textual data is rarely neatly compartmentalized. This allows documents to be associated with multiple topics or facets simultaneously.
  • Focusing on Local Relationships: By creating small, localized "micro-clusters," the method aims to better capture the nuances of term-document associations, which can be lost in global dimensionality reduction techniques.
  • Simultaneous Attribute Clustering: The framework is designed to cluster not just documents and terms, but also other attributes like authors, enabling a more holistic view of textual information.
  • Discounting for Control: The probabilistic discounting mechanism is a crucial parameter for controlling cluster size and quality, offering a tunable knob for balancing granularity and coverage.
  • Flexibility Beyond Document-Term: The probabilistic formulation is shown to be extensible to more than two attributes, suggesting broad applicability.

Key Results

The experimental results demonstrated that the micro-clustering method could effectively categorize documents based on their originating societies. The effectiveness of the discounting parameter (δ) was highlighted: smaller values of δ led to higher "single society" ratios and "inside-cluster" ratios, indicating better-quality, more focused clusters, albeit with fewer overall clusters. In text categorization tasks, the micro-clustering approach performed comparably to, and in some cases slightly better than, standard methods like naive Bayes, though not quite as well as Support Vector Machines (SVM). The paper also showed that local improvement steps in cluster generation were effective in reducing noise.

Limitations and Future Work

The authors acknowledge that the cluster generation process, particularly the elimination step, is locally optimized and depends on the order of examination. They also note that for comparison purposes, they primarily focused on the document-term feature space, although the framework is applicable to more general cases.

Future work suggested includes:

  • Exploring other discounting techniques from linguistic studies.
  • Developing strategies for initiating clusters by combining different attribute sets (e.g., documents and authors).
  • Establishing methods for evaluating overlapping clusters.
  • Applying the framework to Web document clustering problems.

Summary updated

BibTeX
@inproceedings{aizawa2002method,
  author = {Akiko Aizawa},
  title = {{A Method of Cluster-Based Indexing of Textual Data}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure