X-DMM: Fast and Scalable Model Based Text Clustering

Linwei Li, Liangchen Guo, Zhenying He, Yinan Jing, X. Sean WangAAAI 2019 · DOI

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:

  1. 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$).
  2. 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.
  3. 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.
Performance vs. Training Time: X-DMM (with MH) achieves higher performance significantly faster than the baseline GSDMM.

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.
Training Time Comparison: X-DMM and its parallel version consistently outperform GSDMM and FGSDMM+ across various datasets.

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

BibTeX
@inproceedings{li2019x,
  author = {Linwei Li and Liangchen Guo and Zhenying He and Yinan Jing and X. Sean Wang},
  title = {{X-DMM: Fast and Scalable Model Based Text Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33014197},
}
Figure