k-means++: the advantages of careful seeding. Arthur, D. & Vassilvitskii, S. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, of SODA '07, pages 1027–1035, New Orleans, Louisiana, January, 2007. Society for Industrial and Applied Mathematics. abstract bibtex The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is Θ(logk)-competitive with the optimal clustering. Preliminary experiments show that our augmentation improves both the speed and the accuracy of k-means, often quite dramatically.
@inproceedings{arthur_kmeans_2007,
address = {New Orleans, Louisiana},
series = {{SODA} '07},
title = {k-means++: the advantages of careful seeding},
isbn = {978-0-89871-624-5},
shorttitle = {k-means++},
abstract = {The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is Θ(logk)-competitive with the optimal clustering. Preliminary experiments show that our augmentation improves both the speed and the accuracy of k-means, often quite dramatically.},
urldate = {2020-02-18},
booktitle = {Proceedings of the eighteenth annual {ACM}-{SIAM} symposium on {Discrete} algorithms},
publisher = {Society for Industrial and Applied Mathematics},
author = {Arthur, David and Vassilvitskii, Sergei},
month = jan,
year = {2007},
pages = {1027--1035},
}
Downloads: 0
{"_id":"zjTDL4PZNFZhPY7Xq","bibbaseid":"arthur-vassilvitskii-kmeanstheadvantagesofcarefulseeding-2007","author_short":["Arthur, D.","Vassilvitskii, S."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","address":"New Orleans, Louisiana","series":"SODA '07","title":"k-means++: the advantages of careful seeding","isbn":"978-0-89871-624-5","shorttitle":"k-means++","abstract":"The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is Θ(logk)-competitive with the optimal clustering. Preliminary experiments show that our augmentation improves both the speed and the accuracy of k-means, often quite dramatically.","urldate":"2020-02-18","booktitle":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms","publisher":"Society for Industrial and Applied Mathematics","author":[{"propositions":[],"lastnames":["Arthur"],"firstnames":["David"],"suffixes":[]},{"propositions":[],"lastnames":["Vassilvitskii"],"firstnames":["Sergei"],"suffixes":[]}],"month":"January","year":"2007","pages":"1027–1035","bibtex":"@inproceedings{arthur_kmeans_2007,\n\taddress = {New Orleans, Louisiana},\n\tseries = {{SODA} '07},\n\ttitle = {k-means++: the advantages of careful seeding},\n\tisbn = {978-0-89871-624-5},\n\tshorttitle = {k-means++},\n\tabstract = {The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is Θ(logk)-competitive with the optimal clustering. Preliminary experiments show that our augmentation improves both the speed and the accuracy of k-means, often quite dramatically.},\n\turldate = {2020-02-18},\n\tbooktitle = {Proceedings of the eighteenth annual {ACM}-{SIAM} symposium on {Discrete} algorithms},\n\tpublisher = {Society for Industrial and Applied Mathematics},\n\tauthor = {Arthur, David and Vassilvitskii, Sergei},\n\tmonth = jan,\n\tyear = {2007},\n\tpages = {1027--1035},\n}\n\n\n\n","author_short":["Arthur, D.","Vassilvitskii, S."],"key":"arthur_kmeans_2007","id":"arthur_kmeans_2007","bibbaseid":"arthur-vassilvitskii-kmeanstheadvantagesofcarefulseeding-2007","role":"author","urls":{},"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/howcanoewang","dataSources":["qAPjQpsx8e9aJNrSa","z5vjAHmuibbBBnvdc"],"keywords":[],"search_terms":["means","advantages","careful","seeding","arthur","vassilvitskii"],"title":"k-means++: the advantages of careful seeding","year":2007}