TL;DR
This paper introduces a novel "divisive" algorithm for clustering words in text data, aiming to reduce dimensionality while preserving crucial information for classification. Unlike previous "agglomerative" methods, their approach optimizes a global information-theoretic criterion, leading to faster computation and improved classification accuracy, especially with limited training data.
What Problem Does This Paper Address?
Text classification, a fundamental task in natural language processing, is often hampered by the extremely high dimensionality of text data. Document representations, typically using a "bag-of-words" model, can result in thousands of features (words). This high dimensionality poses a significant challenge for many machine learning algorithms, including Support Vector Machines (SVMs), leading to increased computational cost and potential overfitting. While feature selection methods aim to mitigate this, they can discard useful information. Feature clustering, which groups words into a smaller set of "word clusters," offers a promising alternative for dimensionality reduction. However, existing clustering algorithms are often "agglomerative" (building clusters incrementally) and can be computationally expensive and yield sub-optimal results. This paper addresses the need for a more efficient and effective feature clustering method that explicitly optimizes information preservation.
Methods
The authors propose a Divisive Information-Theoretic Feature Clustering Algorithm. The core of their approach lies in:
- Information-Theoretic Framework: They derive a global objective function based on the generalized Jensen-Shannon divergence to measure the quality of word clusters. This criterion aims to minimize the loss of mutual information between words and classes after clustering.
- Divisive Clustering: Instead of merging clusters (agglomerative), their algorithm starts with initial clusters and iteratively refines them by splitting and reassigning words. This divisive approach is inspired by k-means but uses Kullback-Leibler (KL) divergence as the distance metric.
- Optimization: The algorithm is designed to monotonically decrease the objective function, guaranteeing convergence to a local minimum. It simultaneously minimizes "within-cluster Jensen-Shannon divergence" (making clusters internally coherent) and maximizes "between-cluster Jensen-Shannon divergence" (making clusters distinct).
- Hard Clustering: The algorithm performs "hard clustering," meaning each word is assigned to exactly one cluster, which helps in reducing model size.
Datasets
The authors evaluated their algorithm on two datasets:
- 20 Newsgroups: A standard benchmark dataset for text classification, containing approximately 20,000 articles from 20 different Usenet discussion groups.
- Dmoz Data: A dataset collected from the Open Directory Project, featuring a 3-level hierarchy of HTML documents. They specifically used a subset related to "Science" and crawled internal nodes, resulting in a 3-deep hierarchy with 49 leaf-level nodes.
Key Insights and Ideas
- Divisive vs. Agglomerative: The paper highlights that a divisive approach, optimizing a global criterion, can be more effective and efficient than greedy agglomerative methods for feature clustering.
- Information-Theoretic Optimality: Using Jensen-Shannon divergence as a global objective function provides a principled way to measure and optimize the quality of word clusters for classification.
- KL-Divergence as a Metric: Employing KL-divergence within a k-means-like framework is shown to be effective for clustering distributions (word-class probabilities).
- "Natural" Algorithm Emergence: The information-theoretic objective function naturally suggests an iterative algorithm that re-partitions words based on their similarity to cluster distributions and then re-computes cluster distributions.
- Benefits for Sparse Data: Feature clustering, especially with this information-theoretic approach, proves highly beneficial when training data is scarce, leading to more robust estimates and higher accuracy.
Key Results
- Speed: The divisive algorithm is significantly faster than agglomerative approaches. For example, on the 20 Newsgroups dataset with 100 clusters, their algorithm took 2.29 minutes, while an agglomerative approach took 80.16 minutes.
- Accuracy: The proposed Divisive Clustering algorithm consistently achieved higher or comparable classification accuracies compared to agglomerative methods (ADC, AIB) and feature selection methods (Information Gain, Mutual Information), especially at lower numbers of features/clusters.
- Information Preservation: The fraction of mutual information lost was significantly lower with Divisive Clustering compared to ADC, indicating better preservation of class-relevant information.
- Sparse Data Performance: On sparse training data (2% of the dataset), Divisive Clustering showed a substantial improvement (up to 12%) in classification accuracy over feature selection methods.
- Hierarchical Classification: The algorithm demonstrated effectiveness in hierarchical classification, allowing for high accuracies with very few features per internal node.
Limitations and Future Work
- Local Optima: The algorithm is guaranteed to converge to a local minimum, and finding the global minimum is NP-complete.
- Choice of Cluster Number: An important topic for future exploration is determining the optimal number of word clusters, for which the authors suggest applying the Minimum Description Length (MDL) principle.
- Soft Clustering: The paper focuses on "hard" clustering. The authors plan to experimentally evaluate the trade-off between soft and hard clustering and how soft clustering affects classification accuracy and model size.
- Feature Weighting and Combination: Future work includes exploring feature weighting and combining feature selection with clustering strategies.
- Larger Scale Experiments: Conducting experiments on larger hierarchical web data is planned to further evaluate the classifier's effectiveness.
- Local Search Strategies: Investigating local search strategies to improve the quality of local optima achieved by the divisive algorithm is also a future direction.
- Applications: The information-theoretic clustering algorithm can be applied to other applications involving non-negative data.
Summary updated