$\varepsilon$-Coresets for Clustering (with Outliers) in Doubling Metrics
Preprint
Abstract
We study the problem of constructing $\varepsilon$-coresets for the $(k, z)$-clustering problem in a doubling metric $M(X, d)$. An $\varepsilon$-coreset is a weighted subset $S\subseteq X$ with weight function $w : S \rightarrow \mathbb{R}_{\geq 0}$, such that for any $k$-subset $C \in [X]^k$, it holds that $\sum_{x \in S}{w(x) \cdot d^z(x, C)} \in (1 \pm \varepsilon) \cdot \sum_{x \in X}{d^z(x, C)}$. We present an efficient algorithm that constructs an $\varepsilon$-coreset for the $(k, z)$-clustering problem in $M(X, d)$, where the size of the coreset only depends on the parameters $k, z, \varepsilon$ and the doubling dimension $\mathsf{ddim}(M)$. To the best of our knowledge, this is the first efficient $\varepsilon$-coreset construction of size independent of $|X|$ for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of $M(X, d)$ and the shattering dimension (or VC-dimension) of the range space induced by the distance $d$. Such a relation was not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small $(1\pm\epsilon)$-distortion of the distance function $d$, and consider the notion of $\tau$-error probabilistic shattering dimension, we can prove an upper bound of $O( \mathsf{ddim}(M)\cdot \log(1/\varepsilon) +\log\log{\frac{1}{\tau}} )$ for the probabilistic shattering dimension for even weighted doubling metrics. We believe this new relation is of independent interest and may find other applications. We also study the robust coresets and centroid sets in doubling metrics. Our robust coreset construction leads to new results in clustering and property testing, and the centroid sets can be used to accelerate the local search algorithms for clustering problems.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- A PTAS for the Steiner Forest Problem in Doubling Metrics2016
- Local Search Yields a PTAS for k-Means in Doubling Metrics2016
- Efficient Classification for Metric DataIEEE Transactions on Information Theory, 2014
- Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or DegreeAlgorithmica, 2013
- A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling MetricsDiscrete & Computational Geometry, 2011
- Small Hop-diameter Sparse Spanners for Doubling MetricsDiscrete & Computational Geometry, 2008
- Bounded geometries, fractals, and low-distortion embeddings2004
- Improved Bounds on the Sample Complexity of LearningJournal of Computer and System Sciences, 2001
- Nearest Neighbor Queries in Metric SpacesDiscrete & Computational Geometry, 1999
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995