TL;DR
This paper introduces "SVD on Clusters" (SVDC), a novel approach to Latent Semantic Indexing (LSI) that aims to improve document similarity measurement by first clustering documents and then applying Singular Value Decomposition (SVD) to these clusters. The authors demonstrate that SVDC can enhance the precision of interdocument similarity compared to traditional LSI methods, particularly when using k-Means for clustering.
What Problem Does This Paper Address?
Traditional information retrieval methods often rely on literal keyword matching, which struggles with the inherent ambiguity of language, such as synonyms (polysemy) and words with multiple meanings (homonymy). Latent Semantic Indexing (LSI), which uses Singular Value Decomposition (SVD) to uncover latent semantic relationships between terms and documents, offers a more robust solution. However, standard LSI methods, while good at representing documents, are sometimes criticized for having low discriminative power, meaning they might not effectively distinguish between subtly different documents. This paper addresses this limitation by proposing a method to improve the discriminative power of LSI.
Methods
The core innovation is SVD on Clusters (SVDC). The authors propose that instead of applying SVD to the entire term-document matrix, it's more effective to first partition the documents into clusters. Then, SVD is applied independently to the submatrices representing each cluster. This approach is theoretically supported by a "divide-and-conquer" strategy, suggesting that approximating submatrices can yield comparable or even better results than direct SVD on the whole matrix.
The paper details two main implementations of SVDC:
- SVDC with k-Means Clustering: This method requires predefining the number of clusters.
- SVDC with SOMs (Self-Organizing Maps) Clustering: This method does not require predefining the number of clusters.
The authors also present algorithms for updating SVDC when new documents or terms are added, aiming to avoid recomputing the entire decomposition.
Datasets
The paper uses two corpora for evaluation:
- English Corpus: A subset of the Reuters-21578 distribution (2,042 documents) from four categories: "crude," "agriculture," "trade," and "interest."
- Chinese Corpus: TanCorpV1.0 (1,200 documents) from four categories: "agriculture," "history," "politics," and "economy."
Key Insights and Ideas
- Clustering Enhances Discriminative Power: The central idea is that documents within a cluster are likely to share more semantic similarity than documents across different clusters. Applying SVD within these more semantically coherent groups can lead to a more precise representation and better discrimination between documents.
- SVD on Clusters as a "Divide and Conquer" Strategy: The authors draw a parallel between their method and divide-and-conquer algorithms, suggesting that breaking down the large term-document matrix into smaller, clustered submatrices can be computationally efficient and effective for LSI.
- Clustering Algorithm Matters: The performance of SVDC is shown to be influenced by the choice of clustering algorithm, with k-Means generally outperforming SOMs in their experiments.
- Updating SVDC: The paper explores methods for incrementally updating the SVDC decomposition, which is crucial for dynamic document collections.
Key Results
- Improved Similarity Measure: Experiments on both English and Chinese corpora showed that SVDC, particularly with k-Means clustering, generally outperformed other SVD-based LSI methods (SVD, SVR, ADE, IRR) in terms of average precision for interdocument similarity.
- k-Means Superiority: SVDC with k-Means consistently achieved better clustering results (measured by F-measure) and higher average precision compared to SVDC with SOMs.
- Updating Performance: SVDC with k-Means demonstrated superior performance over standard SVD in updating scenarios, especially when dealing with new documents. The performance difference became more pronounced as the number of training documents decreased.
Limitations and Future Work
- Clustering Algorithm Impact: The paper acknowledges that the performance of SVDC is significantly dependent on the quality of the clustering. While k-Means performed well, the effectiveness of SOMs was less consistent.
- Robustness: The authors admit that SVDC might not always be a robust approach, as its superiority over standard SVD wasn't always obvious across all categories.
- Future Work: The authors plan to compare SVDC with topic-based methods for LSI, such as Probabilistic Latent Semantic Indexing (PLSI) and Latent Dirichlet Allocation (LDA), to further explore its potential.
Summary updated