Adaptive Sampling for k-Means Clustering

DOI10.1007/978-3-642-03685-9_2MaRDI QIDQ3638866zbMATH OpenOpenAlexFDO

Authors Ankit Aggarwal, Amit Deshpande, R. Kannan

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_2

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Recommendations

• A bi-criteria approximation algorithm for \(k\)-means
• A simple \(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
• A local search approximation algorithm for \(k\)-means clustering
• Algorithms and Computation

Cited in

(45)

• Graph summarization with quality guarantees
• A bi-criteria analysis for fuzzy \(C\)-means problem
• The bi-criteria seeding algorithms for two variants of \(k\)-means problem
• An approximation algorithm for the uniform capacitated \(k\)-means problem
• Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
• K-means cloning: adaptive spherical K-means clustering
• The seeding algorithm for k-means problem with penalties
• The seeding algorithms for spherical \(k\)-means clustering
• \(k\)-means++ under approximation stability
• On the \(k\)-means/median cost function
• Tight lower bound instances for k-means++ in two dimensions
• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems
• A bad instance for k-means++
• Core-sets: updated survey
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• A bad instance for \texttt{k-means++}
• k-step adaptive cluster sampling with Horvitz–Thompson estimator
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
• A bi-criteria approximation algorithm for \(k\)-means
• 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
• Approximate Clustering with Same-Cluster Queries
• Greedy minimization of weakly supermodular set functions
• Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
• Semi-supervised k-means++
• The Parallel Seeding Algorithm for k-Means Problem with Penalties
• Selective sampling for approximate clustering of very large data sets
• Noisy, Greedy and Not so Greedy k-Means++
• One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
• Approximation Algorithms for Matroid and Knapsack Means Problems
• The provably good parallel seeding algorithms for the k‐means problem with penalties
• Approximation schemes for k-facility location
• On sampling based algorithms for k-means
• Fully-scalable MPC algorithms for clustering in high dimension
• Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
• Turning big data into tiny data: coresets for unsupervised learning problems
• Improved approximation algorithms for matroid and knapsack means problems
• Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
• Online k-means clustering on arbitrary data streams
• Unexpected effects of online no-substitution k-means clustering
• No-substitution k-means clustering with adversarial order
• Adaptive sampling without replacement of clusters
• Relational algorithms for k-means clustering
• Coresets for weight-constrained anisotropic assignment and clustering
• A cutting plane algorithm for globally solving low-dimensional k-means problems

This page was built for publication: Adaptive Sampling for k-Means Clustering

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