Sets Clustering

The input to the sets-k-means problem is an integer k≥ 1 and a set P=P1,cdots,Pn of sets in ℝd. The goal is to compute a set C of k centers (points) in ℝd that minimizes the sum sumP∈ P minp∈ P, c∈ Cleft| p-c right|2 of squared distances to these sets. An varepsilon-core-set for this problem is a weighted subset of P that approximates this sum up to 1±varepsilon factor, for every set C of k centers in ℝd. We prove that such a core-set of O(log2n) sets always exists, and can be computed in O(nlogn) time, for every input P and every fixed d,k≥ 1 and varepsilon ∈ (0,1). The result easily generalized for any metric space, distances to the power of z>0, and M-estimators that handle outliers. Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS (1+varepsilon approximation) for the sets-k-means problem that takes time near linear in n. This is the first result even for sets-mean on the plane (k=1, d=2). Open source code and experimental results for document classification and facility locations are also provided.