Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models

Area of Science:

• Machine Learning
• Computational Statistics
• Data Mining

Background:

• Bayesian nonparametrics offer flexible probabilistic models where model complexity is data-driven.
• Small-variance asymptotic analysis simplifies complex Bayesian nonparametric algorithms.
• Existing methods primarily focus on static datasets, failing to capture temporal data dynamics.

Purpose of the Study:

• To extend small-variance asymptotic analysis to dynamic Bayesian nonparametric models.
• To develop algorithms for clustering temporally evolving data with Markov structures.
• To address the limitations of batch models in capturing time-varying latent structures.

Main Methods:

• Applied small-variance asymptotic analysis to the maximum a posteriori filtering problem.
• Developed D-Means, an iterative algorithm for spherical, linearly separable clusters.
• Derived SD-Means, a spectral clustering algorithm from a kernelized relaxation.

Main Results:

• Introduced two novel clustering algorithms: D-Means and SD-Means.
• Demonstrated significant improvements in computational cost compared to existing algorithms.
• Showcased enhanced clustering accuracy on datasets with evolving cluster structures.

Conclusions:

• D-Means and SD-Means effectively capture temporal evolution in data clusters.
• The developed algorithms provide a computationally efficient and accurate alternative for dynamic clustering.
• Small-variance analysis is a viable technique for creating efficient algorithms for time-varying Bayesian nonparametric models.