2013/09/26 by Hao Cheng, Xinhua Zhang, Cheng, Hao +3
Computer Science · Mathematics · Physics and Astronomy · #Advanced Statistical Methods and Models #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Mechanics and Entropy #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1309.6823
Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)
arxiv created 2013/09/26 · openalex publication_date 2013/09/26 · arxiv updated 2013/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaussian or discriminative models and are susceptible to imbalanced clusters. To address these shortcomings, we propose a new class of convex relaxations that can be flexibly applied to more general forms of Bregman divergence clustering. By basing these new formulations on normalized equivalence relations we retain additional control on relaxation quality, which allows improvement in clustering quality. We furthermore develop optimization methods that improve scalability by exploiting recent implicit matrix norm methods. In practice, we find that the new formulations are able to efficiently produce tighter clusterings that improve the accuracy of state of the art methods.