K-variates++: More Pluses in the K-means++

By Richard Nock, Raphaël Canyasse, Roksana Boreli, Frank Nielsen. 2016

24 citations recorded by the source corpus.

k-means++ seeding has become a de facto standard for hard clustering algorithms. In this paper, our first contribution is a two-way generalisation of this seeding, k-variates++, that includes the sampling of general densities rather than just a discrete set of Dirac densities anchored at the point locations, and a generalisation of the well known Arthur-Vassilvitskii (AV) approximation guarantee, in the form of a bias+variance approximation bound of the global optimum. This approximation exhibits a reduced dependency on the "noise" component with respect to the optimal potential -- actually approaching the statistical lower bound. We show that k- variates++ reduces to efficient (biased seeding) clustering algorithms tailored to specific frameworks; these include distributed, streaming and on-line clustering, with direct approximation results for these algorithms. Finally, we present a novel application of k-variates++ to differential privacy. For either the specific frameworks considered here, or for the differential privacy setting, there is little to no prior results on the direct application of k-means++ and its approximation bounds--state of the art contenders appear to be significantly more complex and / or display less favorable (approximation) properties. We stress that our algorithms can still be run in cases where there is no closed form solution for the population minimizer. We demonstrate the applicability of our analysis via experimental evaluation on several domains and settings, displaying competitive performances vs state of the art.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, methodology): “Other DP K-means algorithms exist in both the TCM [4, 8, 43, 46, 48, 53] and LM [47, 52, 54, 57] which improve on our two non-hybrid K-means algorithms.”
Locally Private k-Means Clustering (2019, methodology): “[25] also designed a private variant for the k-means++ algorithm.”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, methodology): “We will first give a detailed description on the real-world and synthetic datasets we are using, and then provide additional details on the comparison to existing works including (Nock et al., 2016) and (Su et al.”
Locally Private k-Means in One Round (2021, background): “…topic (Blum et al., 2005; Nissim et al., 2007; Feldman et al., 2009; Gupta et al., 2010; Mohan et al., 2012; Wang et al., 2015; Nissim et al., 2016; Nock et al., 2016; Su et al., 2016; Feldman et al., 2017; Balcan et al., 2017; Nissim and Stemmer, 2018; Huang and Liu, 2018; Nock et al., 2016;…”