A bad instance for \texttt{k-means++}

DOI10.1016/J.TCS.2012.02.028MaRDI QIDQ393129zbMATH OpenOpenAlexFDO

Authors Tobias Brunsch, Heiko Röglin

Publication date 16 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.02.028

zbMATH Keywords

\(k\)-means\texttt{k-means++}clustering

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 bad instance for k-means++
• A tight lower bound instance for k-means++ in constant dimension
• Analysis of k-means++ for separable data
• Tight lower bound instances for k-means++ in two dimensions
• \(k\)-means++ under approximation stability

Cites work

• k-means requires exponentially many iterations even in the plane
• Adaptive Sampling for k-Means Clustering
• Clustering to minimize the maximum intercluster distance
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• Least squares quantization in PCM
• NP-hardness of Euclidean sum-of-squares clustering
• Probability Inequalities for Sums of Bounded Random Variables
• Smoothed analysis of the k-means method
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• The local nature of list colorings for graphs of high girth
• The Planar k-Means Problem is NP-Hard

Cited in

(10)

• Clustering stability-based evolutionary K-means
• \(k\)-means++ under approximation stability
• Tight lower bound instances for k-means++ in two dimensions
• A bad instance for k-means++
• Analysis of k-means++ for separable data
• k-means++ under approximation stability
• Approximate Clustering with Same-Cluster Queries
• A tight lower bound instance for k-means++ in constant dimension
• Noisy, Greedy and Not so Greedy k-Means++
• Also for \(k\)-means: more data does not imply better performance

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: A bad instance for \texttt{k-means++}

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