Towards explaining the speed of k-means

Bodo Manthey; Jan Cornelis van de Pol; F. Raamsdonk; Mariëlle Ida Antoinette Stoelinga

Towards explaining the speed of k-means

Bodo Manthey, Jan Cornelis van de Pol (Editor), F. Raamsdonk (Editor), Mariëlle Ida Antoinette Stoelinga (Editor)

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Professional

101 Downloads (Pure)

Abstract

The $k$-means method is a popular algorithm for clustering, known for its speed in practice. This stands in contrast to its exponential worst-case running-time. To explain the speed of the $k$-means method, a smoothed analysis has been conducted. We sketch this smoothed analysis and a generalization to Bregman divergences.

Original language	Undefined
Pages (from-to)	45-54
Number of pages	10
Journal	Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica
Volume	2011
Publication status	Published - 2011

Keywords

Smoothed Analysis
k-Means method
IR-79466
Clustering
METIS-285231
EWI-21249

Access to Document

http://www.nvti.nl/Newsletter/Nieuwsbrief2011.pdf

Cite this

@article{47a8e718c2be42008f856307ee1c523b,

title = "Towards explaining the speed of k-means",

abstract = "The $k$-means method is a popular algorithm for clustering, known for its speed in practice. This stands in contrast to its exponential worst-case running-time. To explain the speed of the $k$-means method, a smoothed analysis has been conducted. We sketch this smoothed analysis and a generalization to Bregman divergences.",

keywords = "Smoothed Analysis, k-Means method, IR-79466, Clustering, METIS-285231, EWI-21249",

author = "Bodo Manthey and {van de Pol}, {Jan Cornelis} and F. Raamsdonk and Stoelinga, {Mari{\"e}lle Ida Antoinette}",

year = "2011",

language = "Undefined",

volume = "2011",

pages = "45--54",

journal = "Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica",

}

TY - JOUR

T1 - Towards explaining the speed of k-means

AU - Manthey, Bodo

A2 - van de Pol, Jan Cornelis

A2 - Raamsdonk, F.

A2 - Stoelinga, Mariëlle Ida Antoinette

PY - 2011

Y1 - 2011

N2 - The $k$-means method is a popular algorithm for clustering, known for its speed in practice. This stands in contrast to its exponential worst-case running-time. To explain the speed of the $k$-means method, a smoothed analysis has been conducted. We sketch this smoothed analysis and a generalization to Bregman divergences.

AB - The $k$-means method is a popular algorithm for clustering, known for its speed in practice. This stands in contrast to its exponential worst-case running-time. To explain the speed of the $k$-means method, a smoothed analysis has been conducted. We sketch this smoothed analysis and a generalization to Bregman divergences.

KW - Smoothed Analysis

KW - k-Means method

KW - IR-79466

KW - Clustering

KW - METIS-285231

KW - EWI-21249

M3 - Article

VL - 2011

SP - 45

EP - 54

JO - Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica

JF - Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica

ER -