k-Means has polynomial smoothed complexity

David Arthur; Bodo Manthey; Heiko Röglin

doi:10.1109/FOCS.2009.14

k-Means has polynomial smoothed complexity

David Arthur, Bodo Manthey, Heiko Röglin

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

74 Citations (Scopus)

131 Downloads (Pure)

Abstract

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

Original language	Undefined
Title of host publication	Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)
Editors	D.A. Spielman
Place of Publication	Los Alamitos
Publisher	IEEE Computer Society
Pages	405-414
Number of pages	10
ISBN (Print)	978-0-7695-3850-1
DOIs	https://doi.org/10.1109/FOCS.2009.14
Publication status	Published - 2009
Event	The 50th Annual IEEE Symposium on Foundations of Computer Science 2009 - Renaissance Hotel Downtown Atlanta, Atlanta, United States Duration: 24 Oct 2009 → 27 Oct 2009 Conference number: 50 https://www.cc.gatech.edu/focs2009/

Publication series

Name
Publisher	IEEE Computer Society Press

Conference

Conference	The 50th Annual IEEE Symposium on Foundations of Computer Science 2009
Abbreviated title	FOCS 2009
Country/Territory	United States
City	Atlanta
Period	24/10/09 → 27/10/09
Internet address	https://www.cc.gatech.edu/focs2009/

Keywords

METIS-266490
IR-70194
Smoothed analyis
Clustering
Probabilistic Analysis
k-Means
k-Means clustering
k-Means method
EWI-16979

Access to Document

10.1109/FOCS.2009.14

http://doi.ieeecomputersociety.org/10.1109/FOCS.2009.14

Cite this

@inproceedings{18cebabb0e76419aba90c692df83e5f8,

title = "k-Means has polynomial smoothed complexity",

abstract = "The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.",

keywords = "METIS-266490, IR-70194, Smoothed analyis, Clustering, Probabilistic Analysis, k-Means, k-Means clustering, k-Means method, EWI-16979",

author = "David Arthur and Bodo Manthey and Heiko R{\"o}glin",

year = "2009",

doi = "10.1109/FOCS.2009.14",

language = "Undefined",

isbn = "978-0-7695-3850-1",

publisher = "IEEE Computer Society",

pages = "405--414",

editor = "D.A. Spielman",

booktitle = "Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)",

address = "United States",

note = "null ; Conference date: 24-10-2009 Through 27-10-2009",

url = "https://www.cc.gatech.edu/focs2009/",

}

Arthur, D, Manthey, B & Röglin, H 2009, k-Means has polynomial smoothed complexity. in DA Spielman (ed.), Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)., 10.1109/FOCS.2009.14, IEEE Computer Society, Los Alamitos, pp. 405-414, The 50th Annual IEEE Symposium on Foundations of Computer Science 2009, Atlanta, Georgia, United States, 24/10/09. https://doi.org/10.1109/FOCS.2009.14

k-Means has polynomial smoothed complexity. / Arthur, David; Manthey, Bodo; Röglin, Heiko.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009). ed. / D.A. Spielman. Los Alamitos : IEEE Computer Society, 2009. p. 405-414 10.1109/FOCS.2009.14.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - k-Means has polynomial smoothed complexity

AU - Arthur, David

AU - Manthey, Bodo

AU - Röglin, Heiko

N1 - Conference code: 50

PY - 2009

Y1 - 2009

N2 - The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

AB - The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

KW - METIS-266490

KW - IR-70194

KW - Smoothed analyis

KW - Clustering

KW - Probabilistic Analysis

KW - k-Means

KW - k-Means clustering

KW - k-Means method

KW - EWI-16979

U2 - 10.1109/FOCS.2009.14

DO - 10.1109/FOCS.2009.14

M3 - Conference contribution

SN - 978-0-7695-3850-1

SP - 405

EP - 414

BT - Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)

A2 - Spielman, D.A.

PB - IEEE Computer Society

CY - Los Alamitos

Y2 - 24 October 2009 through 27 October 2009

ER -