{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T01:45:28Z","timestamp":1781919928080,"version":"3.54.5"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Numerical Algorithms Group"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>K-Means is one of the most used algorithms for data clustering and the usual clustering method for benchmarking. Despite its wide application it is well-known that it suffers from a series of disadvantages; it is only able to find local minima and the positions of the initial clustering centres (centroids) can greatly affect the clustering solution. Over the years many K-Means variations and initialisation techniques have been proposed with different degrees of complexity. In this study we focus on common K-Means variations along with a range of deterministic and stochastic initialisation techniques. We show that, on average, more sophisticated initialisation techniques alleviate the need for complex clustering methods. Furthermore, deterministic methods perform better than stochastic methods. However, there is a trade-off: less sophisticated stochastic methods, executed multiple times, can result in better clustering. Factoring in execution time, deterministic methods can be competitive and result in a good clustering solution. These conclusions are obtained through extensive benchmarking using a range of synthetic model generators and real-world data sets.<\/jats:p>","DOI":"10.1007\/s10994-021-06021-7","type":"journal-article","created":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T19:14:13Z","timestamp":1626117253000},"page":"1975-2003","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["An empirical comparison between stochastic and deterministic centroid initialisation for K-means variations"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3383-6133","authenticated-orcid":false,"given":"Avgoustinos","family":"Vouros","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Langdell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Croucher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eleni","family":"Vasilaki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,7,12]]},"reference":[{"issue":"11","key":"6021_CR1","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1016\/j.patrec.2009.04.013","volume":"30","author":"M Al Hasan","year":"2009","unstructured":"Al Hasan, M., Chaoji, V., Salem, S., & Zaki, M. J. (2009). Robust partitional clustering by outlier and density insensitive seeding. Pattern Recognition Letters, 30(11), 994\u20131002.","journal-title":"Pattern Recognition Letters"},{"key":"6021_CR2","unstructured":"Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for industrial and applied mathematics (pp. 1027\u20131035)"},{"key":"6021_CR3","unstructured":"Asuncion, A., & Newman, D. (2007). Uci machine learning repository."},{"key":"6021_CR4","doi-asserted-by":"crossref","unstructured":"Bilenko, M., Basu, S., & Mooney, R. J. (2004). Integrating constraints and metric learning in semi-supervised clustering. In Proceedings of the twenty-first international conference on Machine learning (p\u00a011). ACM.","DOI":"10.1145\/1015330.1015360"},{"key":"6021_CR5","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.cviu.2014.03.008","volume":"125","author":"A Biswas","year":"2014","unstructured":"Biswas, A., & Jacobs, D. (2014). Active subclustering. Computer Vision and Image Understanding, 125, 72\u201384.","journal-title":"Computer Vision and Image Understanding"},{"key":"6021_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1145\/335191.335388","volume":"29","author":"MM Breunig","year":"2000","unstructured":"Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000). Lof: identifying density-based local outliers. ACM Sigmod Record, 29, 93\u2013104.","journal-title":"ACM Sigmod Record"},{"key":"6021_CR7","unstructured":"Brodinov\u00e1, \u0160., Filzmoser, P., Ortner, T., Breiteneder, C., & Rohm, M. (2017). Robust and sparse k-means clustering for high-dimensional data. Advances in Data Analysis and Classification, 1\u201328."},{"issue":"3","key":"6021_CR8","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1037\/met0000095","volume":"22","author":"MJ Brusco","year":"2017","unstructured":"Brusco, M. J., Shireman, E., & Steinley, D. (2017). A comparison of latent class, k-means, and k-median methods for clustering dichotomous data. Psychological Methods, 22(3), 563.","journal-title":"Psychological Methods"},{"issue":"1","key":"6021_CR9","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.eswa.2012.07.021","volume":"40","author":"ME Celebi","year":"2013","unstructured":"Celebi, M. E., Kingravi, H. A., & Vela, P. A. (2013). A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Systems with Applications, 40(1), 200\u2013210.","journal-title":"Expert Systems with Applications"},{"key":"6021_CR10","unstructured":"Charu, C. A., & Chandan, K. R. (2013). Data clustering: Algorithms and applications."},{"key":"6021_CR11","doi-asserted-by":"crossref","unstructured":"Feldman, D., & Schulman, L. J. (2012). Data reduction for weighted and outlier-resistant clustering. In Proceedings of the twenty-third annual ACM-SIAM symposium on discrete algorithms. Society for industrial and applied mathematics (pp. 1343\u20131354).","DOI":"10.1137\/1.9781611973099.106"},{"issue":"12","key":"6021_CR12","doi-asserted-by":"publisher","first-page":"4743","DOI":"10.1007\/s10489-018-1238-7","volume":"48","author":"P Fr\u00e4nti","year":"2018","unstructured":"Fr\u00e4nti, P., & Sieranoja, S. (2018). K-means properties on six clustering benchmark datasets. Applied Intelligence, 48(12), 4743\u20134759.","journal-title":"Applied Intelligence"},{"key":"6021_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.patcog.2019.04.014","volume":"93","author":"P Fr\u00e4nti","year":"2019","unstructured":"Fr\u00e4nti, P., & Sieranoja, S. (2019). How much can k-means be improved by using better initialization and repeats? Pattern Recognition, 93, 95\u2013112.","journal-title":"Pattern Recognition"},{"issue":"5","key":"6021_CR14","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1016\/j.patcog.2005.09.012","volume":"39","author":"P Fr\u00e4nti","year":"2006","unstructured":"Fr\u00e4nti, P., & Virmajoki, O. (2006). Iterative shrinking method for clustering problems. Pattern Recognition, 39(5), 761\u2013765. https:\/\/doi.org\/10.1016\/j.patcog.2005.09.012.","journal-title":"Pattern Recognition"},{"key":"6021_CR15","doi-asserted-by":"publisher","first-page":"14562","DOI":"10.1038\/srep14562","volume":"5","author":"TV Gehring","year":"2015","unstructured":"Gehring, T. V., Luksys, G., Sandi, C., & Vasilaki, E. (2015). Detailed classification of swimming paths in the morris water maze: Multiple strategies within one trial. Scientific Reports, 5, 14562.","journal-title":"Scientific Reports"},{"key":"6021_CR16","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T. F. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293\u2013306.","journal-title":"Theoretical Computer Science"},{"key":"6021_CR17","doi-asserted-by":"crossref","unstructured":"Hahsler, M., Piekenbrock, M., Arya, S., & Mount, D. (2019). dbscan: Density based clustering of applications with noise (DBSCAN) and related algorithms. https:\/\/github.com\/mhahsler\/dbscan.","DOI":"10.18637\/jss.v091.i01"},{"key":"6021_CR18","unstructured":"Hartigan, J. A. (1975). Clustering algorithms."},{"issue":"1","key":"6021_CR19","first-page":"100","volume":"28","author":"JA Hartigan","year":"1979","unstructured":"Hartigan, J. A., & Wong, M. A. (1979). Algorithm as 136: A k-means clustering algorithm. Journal of the Royal Statistical Society Series C (Applied Statistics), 28(1), 100\u2013108.","journal-title":"Journal of the Royal Statistical Society Series C (Applied Statistics)"},{"issue":"8","key":"6021_CR20","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"AK Jain","year":"2010","unstructured":"Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31(8), 651\u2013666.","journal-title":"Pattern Recognition Letters"},{"issue":"1","key":"6021_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1071\/BT9660127","volume":"14","author":"R Jancey","year":"1966","unstructured":"Jancey, R. (1966). Multidimensional group analysis. Australian Journal of Botany, 14(1), 127\u2013130.","journal-title":"Australian Journal of Botany"},{"key":"6021_CR22","unstructured":"K\u00e4rkk\u00e4inen, I., & Fr\u00e4nti, P. (2002). Dynamic local search algorithm for the clustering problem. Technical Report. A-2002-6, Department of Computer Science, University of Joensuu, Joensuu, Finland."},{"issue":"10","key":"6021_CR23","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1109\/97.329844","volume":"1","author":"I Katsavounidis","year":"1994","unstructured":"Katsavounidis, I., Kuo, C. C. J., & Zhang, Z. (1994). A new initialization technique for generalized lloyd iteration. IEEE Signal Processing Letters, 1(10), 144\u2013146.","journal-title":"IEEE Signal Processing Letters"},{"key":"6021_CR24","unstructured":"Kaufman, L., & Rousseeuw, P. J. (2009). Finding groups in data: an introduction to cluster analysis, (Vol. 344). John Wiley & Sons."},{"issue":"5","key":"6021_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v072.i05","volume":"72","author":"Y Kondo","year":"2016","unstructured":"Kondo, Y., Salibian-Barrera, M., & Zamar, R. (2016). Rskc: An r package for a robust and sparse k-means clustering algorithm. Journal of Statistical Software, 72(5), 1\u201326.","journal-title":"Journal of Statistical Software"},{"key":"6021_CR26","doi-asserted-by":"crossref","unstructured":"Lan, X., Li, Q., & Zheng, Y. (2015). Density k-means: A new algorithm for centers initialization for k-means. In 2015 6th IEEE international conference on software engineering and service science (ICSESS) (pp. 958\u2013961). IEEE.","DOI":"10.1109\/ICSESS.2015.7339213"},{"issue":"1","key":"6021_CR27","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1214\/aos\/1176347978","volume":"19","author":"HP Lopuhaa","year":"1991","unstructured":"Lopuhaa, H. P., & Rousseeuw, P. J. (1991). Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. The Annals of Statistics, 19(1), 229\u2013248.","journal-title":"The Annals of Statistics"},{"key":"6021_CR28","unstructured":"MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability (Vol. 1, pp. 281\u2013297). Oakland, CA, USA"},{"key":"6021_CR29","unstructured":"MATLAB. (2019). version 9.6.0 (R2019a). The MathWorks Inc., Natick, Massachusetts"},{"key":"6021_CR30","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1090\/dimacs\/015\/09","volume":"15","author":"BM Moret","year":"1992","unstructured":"Moret, B. M., & Shapiro, H. D. (1992). An empirical assessment of algorithms for constructing a minimum spanning tree. Computational Support for Discrete Mathematics, 15, 99\u2013117.","journal-title":"Computational Support for Discrete Mathematics"},{"key":"6021_CR31","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.compbiomed.2017.10.014","volume":"91","author":"N Nidheesh","year":"2017","unstructured":"Nidheesh, N., Nazeer, K. A., & Ameer, P. (2017). An enhanced deterministic k-means clustering algorithm for cancer subtype prediction from gene expression data. Computers in Biology and Medicine, 91, 213\u2013221.","journal-title":"Computers in Biology and Medicine"},{"key":"6021_CR32","unstructured":"Numerical Algorithms Group (NAG). (2019). The NAG Toolbox for MATLAB\u00ae. https:\/\/www.nag.com\/"},{"issue":"10","key":"6021_CR33","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1016\/S0167-8655(99)00069-0","volume":"20","author":"JM Pena","year":"1999","unstructured":"Pena, J. M., Lozano, J. A., & Larranaga, P. (1999). An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognition Letters, 20(10), 1027\u20131040.","journal-title":"Pattern Recognition Letters"},{"key":"6021_CR34","unstructured":"R Core Team. (2013). R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria, http:\/\/www.R-project.org\/"},{"issue":"1","key":"6021_CR35","first-page":"27","volume":"5","author":"E Rend\u00f3n","year":"2011","unstructured":"Rend\u00f3n, E., Abundez, I., Arizmendi, A., & Quiroz, E. M. (2011). Internal versus external cluster validation indexes. International Journal of Computers and Communications, 5(1), 27\u201334.","journal-title":"International Journal of Computers and Communications"},{"issue":"6191","key":"6021_CR36","doi-asserted-by":"publisher","first-page":"1492","DOI":"10.1126\/science.1242072","volume":"344","author":"A Rodriguez","year":"2014","unstructured":"Rodriguez, A., & Laio, A. (2014). Clustering by fast search and find of density peaks. Science, 344(6191), 1492\u20131496.","journal-title":"Science"},{"key":"6021_CR37","unstructured":"van Rossum, G. (1995). Python tutorial. Technical Report CS-R9526. Centrum voor Wiskunde en Informatica (CWI), Amsterdam."},{"key":"6021_CR38","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0377-0427(87)90125-7","volume":"20","author":"PJ Rousseeuw","year":"1987","unstructured":"Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53\u201365.","journal-title":"Journal of Computational and Applied Mathematics"},{"key":"6021_CR39","unstructured":"Slonim, N., Aharoni, E., & Crammer, K. (2013). Hartigan\u2019s k-means versus lloyd\u2019s k-means-is it time for a change? In IJCAI (pp. 1677\u20131684)."},{"issue":"2","key":"6021_CR40","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1111\/1467-9868.00293","volume":"63","author":"R Tibshirani","year":"2001","unstructured":"Tibshirani, R., Walther, G., & Hastie, T. (2001). Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2), 411\u2013423.","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"key":"6021_CR41","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.patrec.2020.11.015","volume":"142","author":"A Vouros","year":"2021","unstructured":"Vouros, A., & Vasilaki, E. (2021). A semi-supervised sparse k-means algorithm. Pattern Recognition Letters, 142, 65\u201371.","journal-title":"Pattern Recognition Letters"},{"issue":"6","key":"6021_CR42","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1038\/sj.bjc.6604207","volume":"98","author":"Y Wang","year":"2008","unstructured":"Wang, Y., Miller, D., & Clarke, R. (2008). Approaches to working in high-dimensional data spaces: gene expression microarrays. British Journal of Cancer, 98(6), 1023.","journal-title":"British Journal of Cancer"},{"key":"6021_CR43","unstructured":"Whelan, C., Harrell, G., & Wang, J. (2015). Understanding the k-medians problem. In Proceedings of the international conference on scientific computing (CSC). The Steering Committee of The World Congress in Computer Science, Computer (p. 219)."},{"issue":"490","key":"6021_CR44","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1198\/jasa.2010.tm09415","volume":"105","author":"DM Witten","year":"2010","unstructured":"Witten, D. M., & Tibshirani, R. (2010). A framework for feature selection in clustering. Journal of the American Statistical Association, 105(490), 713\u2013726.","journal-title":"Journal of the American Statistical Association"},{"issue":"4","key":"6021_CR45","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1111\/j.1541-0420.2007.00784.x","volume":"63","author":"M Yan","year":"2007","unstructured":"Yan, M., & Ye, K. (2007). Determining the number of clusters using the weighted gap statistic. Biometrics, 63(4), 1031\u20131037.","journal-title":"Biometrics"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06021-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06021-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06021-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T16:14:12Z","timestamp":1629216852000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06021-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,12]]},"references-count":45,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["6021"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06021-7","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,12]]},"assertion":[{"value":"29 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}