A simple D ^2-sampling based PTAS for k-means and other clustering problems

DOI10.1007/978-3-642-32241-9_2MaRDI QIDQ2914307zbMATH OpenOpenAlexFDO

Authors Ragesh Jaiswal, Amit Kumar, Sandeep Sen

Publication date 25 September 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.4206

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: Given a set of points $Psubsetmathbb{R}^d$, the $k$-means clustering problem is to find a set of $k$ {em centers} $C=c_1,\mathrm{...},c_k,c_{i}inmathbb{R}^d,$ such that the objective function $su{m}_{xinP}d(x,C{)}^2$, where $d(x,C)$ denotes the distance between $x$ and the closest center in $C$, is minimized. This is one of the most prominent objective functions that have been studied with respect to clustering. $D^2$-sampling cite{ArthurV07} is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points $Psubseteqmathbb{R}^d$, the first point is chosen uniformly at random from $P$. Subsequently, a point from $P$ is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled points. $D^2$-sampling has been shown to have nice properties with respect to the $k$-means clustering problem. Arthur and Vassilvitskii cite{ArthurV07} show that $k$ points chosen as centers from $P$ using $D^2$-sampling gives an $O(logk)$ approximation in expectation. Ailon et. al. cite{AJMonteleoni09} and Aggarwal et. al. cite{AggarwalDK09} extended results of cite{ArthurV07} to show that $O(k)$ points chosen as centers using $D^2$-sampling give $O(1)$ approximation to the $k$-means objective function with high probability. In this paper, we further demonstrate the power of $D^2$-sampling by giving a simple randomized $(1+epsilon)$-approximation algorithm that uses the $D^2$-sampling in its core.

Recommendations

• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Improved analysis of D^2-sampling based PTAS for k-means and other clustering problems
• Adaptive Sampling for k-Means Clustering
• A local search approximation algorithm for \(k\)-means clustering
• On variants of k-means clustering

Cited in

(7)

• Preclustering algorithms for imprecise points
• Metric 1-median selection: query complexity vs. approximation ratio
• A lower bound for metric 1-median selection
• Adaptive Sampling for k-Means Clustering
• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
• Improved analysis of D^2-sampling based PTAS for k-means and other clustering problems
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems

This page was built for publication: A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914307)