Introduction
Text clustering is a cornerstone of modern data mining, yet it remains challenged by the high dimensionality and sparsity of real-world text. While model-based approaches like the Dirichlet Multinomial Mixture (DMM) offer high accuracy for short texts, their computational cost often prohibits scaling to large datasets. The standard collapsed Gibbs sampling (GSDMM) is inherently sequential and scales poorly with document length and cluster count.
X-DMM addresses these bottlenecks through a high-performance framework that achieves up to a 10x speedup over state-of-the-art methods. By integrating mathematical indexing optimizations, Metropolis-Hastings sampling, and GPU-based parallelization, X-DMM enables scalable text clustering without compromising accuracy.
Methodology
The X-DMM framework is built upon three primary optimizations designed to reduce computational complexity and enable hardware acceleration:
- Index-based Optimization: By utilizing a symmetric Dirichlet prior, the authors simplify the sequential multiplications in the DMM probability formula. This transformation allows for constant-time lookups of pre-calculated values, shifting complexity from the total word count ($L$) to the number of unique words ($U$).
- Metropolis-Hastings (MH) Sampling: Recognizing that cluster distributions stabilize as the model nears convergence, X-DMM employs an MH sampler. This uses proposal distributions from previous iterations to reduce complexity from $O(K \cdot U)$ to approximately $O(U)$, where $K$ is the number of clusters.
- Parallelization via Uncollapsed Gibbs Sampling: To overcome the sequential limitations of collapsed Gibbs sampling, X-DMM "uncollapses" the sampler. By treating cluster parameters and document assignments as independent steps, the algorithm becomes "embarrassingly parallel," facilitating efficient implementation on GPUs via CUDA.
Experimental Evaluation
The researchers benchmarked X-DMM against several baselines (GSDMM, FGSDMM+) using five diverse datasets: 20ng (standard newsgroups), ohsumed (medical abstracts), QA (question-answering), Reuters (news articles), and a large-scale NYTimes dataset (300,000 documents).
Key Results and Discussion
The experimental results demonstrate that X-DMM's optimizations provide massive efficiency gains while maintaining clustering quality, as measured by Normalized Mutual Information (NMI).
- Efficiency and Speedup: On the NYTimes dataset, MH sampling alone provided a 4.0x to 4.8x speedup. When combined with GPU parallelization, X-DMM outperformed the previous state-of-the-art by an order of magnitude on datasets like ohsumed.
- Scalability: The parallel implementation demonstrated nearly linear speedup relative to the number of processors, indicating strong potential for even larger-scale applications.
- Accuracy Preservation: Despite the use of uncollapsed samplers and MH approximations, X-DMM maintains the same NMI scores as traditional GSDMM, proving that speed does not come at the cost of quality.
Conclusion and Future Work
X-DMM represents a significant step forward in making model-based text clustering practical for large-scale data. While the current indexing optimization requires a symmetric Dirichlet prior, the authors show this is a minimal constraint for most text clustering tasks. Future work may involve extending these optimizations to more complex topic models like Latent Dirichlet Allocation (LDA) and exploring performance on even larger labeled datasets.
Summary updated