2019/11/15 by Behzad Kamgar-Parsi, Kamgar-Parsi, Behzad, Behrooz Kamgar-Parsi +1
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Advanced Statistical Methods and Models #Bayesian Methods and Mixture Models #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1911.06741
openalex publication_date 2019/11/15 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In many applications we want to find the number of clusters in a dataset. A\ncommon approach is to use the penalized k-means algorithm with an additive\npenalty term linear in the number of clusters. An open problem is estimating\nthe value of the coefficient of the penalty term. Since estimating the value of\nthe coefficient in a principled manner appears to be intractable for general\nclusters, we investigate "ideal clusters", i.e. identical spherical clusters\nwith no overlaps and no outlier background noise. In this paper: (a) We derive,\nfor the case of ideal clusters, rigorous bounds for the coefficient of the\nadditive penalty. Unsurprisingly, the bounds depend on the correct number of\nclusters, which we want to find in the first place. We further show that\nadditive penalty, even for this simplest case of ideal clusters, typically\nproduces a weak and often ambiguous signature for the correct number of\nclusters. (b) As an alternative, we examine the k-means with multiplicative\npenalty, and show that this parameter-free formulation has a stronger, and less\noften ambiguous, signature for the correct number of clusters. We also\nempirically investigate certain types of deviations from ideal cluster\nassumption and show that combination of k-means with additive and\nmultiplicative penalties can resolve ambiguous solutions.\n