{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:43:17Z","timestamp":1770493397963,"version":"3.49.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T00:00:00Z","timestamp":1689811200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T00:00:00Z","timestamp":1689811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Big Data"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The k-means, one of the most widely used clustering algorithm, is not only faster in computation but also produces comparatively better clusters. However, it has two major downsides, first it is sensitive to initialize<jats:italic>k<\/jats:italic>value and secondly, especially for larger datasets, the number of iterations could be very large, making it computationally hard. In order to address these issues, we proposed a scalable and cost-effective algorithm, called<jats:italic>R-k-means,<\/jats:italic>which provides an optimized solution for better clustering large scale high-dimensional datasets. The algorithm first selects<jats:italic>O(R)<\/jats:italic>initial points then reselect<jats:italic>O(l)<\/jats:italic>better initial points, using distance probability from dataset. These points are then again clustered into<jats:italic>k<\/jats:italic>initial points. An empirical study in a controlled environment was conducted using both simulated and real datasets. Experimental results showed that the proposed approach outperformed as compared to the previous approaches when the size of data increases with increasing number of dimensions.<\/jats:p>","DOI":"10.1186\/s40537-023-00798-1","type":"journal-article","created":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T15:05:29Z","timestamp":1689865529000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Big data: an optimized approach for cluster initialization"],"prefix":"10.1186","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3259-198X","authenticated-orcid":false,"given":"Marina","family":"Gul","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7412-8531","authenticated-orcid":false,"given":"M. Abdul","family":"Rehman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,20]]},"reference":[{"key":"798_CR1","unstructured":"MacQueen J. Some methods for classification and analysis of multivariate observations. In: Fifth Berkeley symposium on mathematics. Statistics and probability. Berkeley: University of California Press; 1967. p. 281\u201397."},{"issue":"301","key":"798_CR2","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1080\/01621459.1963.10500845","volume":"58","author":"JH Ward Jr","year":"1963","unstructured":"Ward JH Jr. Hierarchical grouping to optimize an objective function. J Am Stat Assoc. 1963;58(301):236\u201344.","journal-title":"J Am Stat Assoc"},{"key":"798_CR3","unstructured":"Ester M, Kriegel HP, Sander J, Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise. In: kdd, vol. 96, No. 34; 1996. p. 226\u201331."},{"issue":"1","key":"798_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"AP Dempster","year":"1977","unstructured":"Dempster AP, Laird NM, Rubin DB. Maximum likelihood from incomplete data via the EM algorithm. J R Stat Soc: Ser B (Methodol). 1977;39(1):1\u201322.","journal-title":"J R Stat Soc: Ser B (Methodol)"},{"key":"798_CR5","unstructured":"Ng A, Jordan M, Weiss Y. On spectral clustering: analysis and an algorithm. In: Advances in neural information processing systems, 14; 2001."},{"issue":"2","key":"798_CR6","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise D, Deshpande A, Hansen P, Popat P. Np-hardness of Euclidean sum-of-squares clustering. Mach Learn. 2009;75(2):245\u20138.","journal-title":"Mach Learn"},{"issue":"8","key":"798_CR7","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"AK Jain","year":"2010","unstructured":"Jain AK. Data clustering: 50 years beyond k-means. Pattern Recogn Lett. 2010;31(8):651\u201366.","journal-title":"Pattern Recogn Lett"},{"issue":"2","key":"798_CR8","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S. Least squares quantization in PCM. IEEE Trans Inf Theory. 1982;28(2):129\u201337.","journal-title":"IEEE Trans Inf Theory"},{"key":"798_CR9","doi-asserted-by":"publisher","first-page":"42280","DOI":"10.1109\/ACCESS.2019.2907885","volume":"7","author":"W Kwedlo","year":"2019","unstructured":"Kwedlo W, Czochanski PJ. A hybrid MPI\/OpenMP parallelization of k-means algorithms accelerated using the triangle inequality. IEEE Access. 2019;7:42280\u201397.","journal-title":"IEEE Access"},{"issue":"5","key":"798_CR10","doi-asserted-by":"publisher","first-page":"2108","DOI":"10.1109\/TIP.2018.2796860","volume":"27","author":"L He","year":"2018","unstructured":"He L, Zhang H. Kernel k-means sampling for Nystr\u00f6m approximation. IEEE Trans Image Process. 2018;27(5):2108\u201320.","journal-title":"IEEE Trans Image Process"},{"issue":"2","key":"798_CR11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10115-018-1183-0","volume":"58","author":"M Ahmed","year":"2019","unstructured":"Ahmed M. Data summarization: a survey. Knowl Inf Syst. 2019;58(2):249\u201373.","journal-title":"Knowl Inf Syst"},{"key":"798_CR12","doi-asserted-by":"publisher","first-page":"42740","DOI":"10.1109\/ACCESS.2018.2852648","volume":"6","author":"M Alhawarat","year":"2018","unstructured":"Alhawarat M, Hegazi M. Revisiting k-means and topic modeling, a comparison study to cluster Arabic documents. IEEE Access. 2018;6:42740\u20139.","journal-title":"IEEE Access"},{"issue":"6","key":"798_CR13","doi-asserted-by":"crossref","first-page":"3097","DOI":"10.1109\/TAP.2018.2820320","volume":"66","author":"X Yang","year":"2018","unstructured":"Yang X, Li Y, Sun Y, Long T, Sarkar TK. Fast and robust RBF neural network based on global k-means clustering with adaptive selection radius for sound source angle estimation. IEEE Trans Antennas Propag. 2018;66(6):3097\u2013107.","journal-title":"IEEE Trans Antennas Propag"},{"key":"798_CR14","doi-asserted-by":"crossref","unstructured":"McCallum A, Nigam K, Ungar LH. Efficient clustering of high-dimensional data sets with application to reference matching. In: Proceedings of the sixth ACM SIGKDD international conference on knowledge discovery and data mining. 2000. p. 169\u201378.","DOI":"10.1145\/347090.347123"},{"issue":"4","key":"798_CR15","first-page":"431","volume":"30","author":"A Oussous","year":"2018","unstructured":"Oussous A, Benjelloun FZ, Lahcen AA, Belfkih S. Big data technologies: a survey. J King Saud Univ Comput Inf Sci. 2018;30(4):431\u201348.","journal-title":"J King Saud Univ Comput Inf Sci"},{"issue":"1","key":"798_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40537-017-0087-2","volume":"4","author":"C Sreedhar","year":"2017","unstructured":"Sreedhar C, Kasiviswanath N, Reddy PC. Clustering large datasets using k-means modified inter and intra clustering (KM-I2C) in Hadoop. J Big Data. 2017;4(1):1\u201319.","journal-title":"J Big Data"},{"key":"798_CR17","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. How much can k-means be improved by using better initialization and repeats? Pattern Recognit. 2019;93:95\u2013112.","journal-title":"Pattern Recognit"},{"key":"798_CR18","unstructured":"Arthur D, Vassilvitskii S. k-means++: the advantages of careful seeding. Technical report, Stanford; 2006."},{"key":"798_CR19","doi-asserted-by":"crossref","unstructured":"Bahmani B, Moseley B, Vattani A, Kumar R, Vassilvitskii S. Scalable k-means++. arXiv preprint. 2012. arXiv:1203.6402.","DOI":"10.14778\/2180912.2180915"},{"issue":"1","key":"798_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-007-0114-2","volume":"14","author":"X Wu","year":"2008","unstructured":"Wu X, Kumar V, Quinlan JR, Ghosh J, Yang Q, Motoda H, McLachlan GJ, Ng A, Liu B, Philip SY, et al. Top 10 algorithms in data mining. Knowl Inf Syst. 2008;14(1):1\u201337.","journal-title":"Knowl Inf Syst"},{"issue":"1","key":"798_CR21","first-page":"27","volume":"5","author":"E Rend\u00f3n","year":"2011","unstructured":"Rend\u00f3n E, Abundez I, Arizmendi A, Quiroz EM. Internal versus external cluster validation indexes. Int J Comput Commun. 2011;5(1):27\u201334.","journal-title":"Int J Comput Commun"},{"key":"798_CR22","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.patcog.2016.12.003","volume":"65","author":"Y Lei","year":"2017","unstructured":"Lei Y, Bezdek JC, Romano S, Vinh NX, Chan J, Bailey J. Ground truth bias in external cluster validity indices. Pattern Recogn. 2017;65:58\u201370.","journal-title":"Pattern Recogn"},{"issue":"3","key":"798_CR23","doi-asserted-by":"publisher","first-page":"6050","DOI":"10.1016\/j.eswa.2008.06.093","volume":"36","author":"J Wu","year":"2009","unstructured":"Wu J, Chen J, Xiong H, Xie M. External validation measures for k-means clustering: a data distribution perspective. Expert Syst Appl. 2009;36(3):6050\u201361.","journal-title":"Expert Syst Appl"},{"issue":"23","key":"798_CR24","doi-asserted-by":"publisher","first-page":"14583","DOI":"10.1007\/s00500-021-06397-7","volume":"25","author":"M Jahan","year":"2021","unstructured":"Jahan M, Hasan M. A robust fuzzy approach for gene expression data clustering. Soft Comput. 2021;25(23):14583\u201396.","journal-title":"Soft Comput"},{"key":"798_CR25","doi-asserted-by":"publisher","first-page":"80716","DOI":"10.1109\/ACCESS.2020.2988796","volume":"8","author":"KP Sinaga","year":"2020","unstructured":"Sinaga KP, Yang MS. Unsupervised k-means clustering algorithm. IEEE Access. 2020;8:80716\u201327.","journal-title":"IEEE Access"},{"key":"798_CR26","unstructured":"Pelleg D, Moore AW, et al. X-means: extending k-means with efficient estimation of the number of clusters. In: Icml. 2000. p. 727\u201334."},{"key":"798_CR27","unstructured":"Hamerly G, Elkan C. Learning the k in k-means. In: Advances in neural information processing systems; 2003. p. 16."},{"issue":"138144.21","key":"798_CR28","first-page":"67","volume":"22","author":"V Faber","year":"1994","unstructured":"Faber V. Clustering and the continuous k-means algorithm. Los Alamos Sci. 1994;22(138144.21):67.","journal-title":"Los Alamos Sci"},{"key":"798_CR29","unstructured":"Bradley PS, Fayyad UM. Refining initial points for k-means clustering. In: ICML. 1998. p. 91\u20139."},{"issue":"11","key":"798_CR30","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1016\/j.patrec.2004.04.007","volume":"25","author":"SS Khan","year":"2004","unstructured":"Khan SS, Ahmad A. Cluster center initialization algorithm for k-means clustering. Pattern Recogn Lett. 2004;25(11):1293\u2013302.","journal-title":"Pattern Recogn Lett"},{"issue":"6","key":"798_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2395116.2395117","volume":"59","author":"R Ostrovsky","year":"2013","unstructured":"Ostrovsky R, Rabani Y, Schulman LJ, Swamy C. The effectiveness of Lloyd-type methods for the k-means problem. J ACM. 2013;59(6):1\u201322.","journal-title":"J ACM"},{"key":"798_CR32","unstructured":"Ailon N, Jaiswal R, Monteleoni C. Streaming k-means approximation. In: NIPS. 2009. p. 10\u20138."},{"key":"798_CR33","doi-asserted-by":"crossref","unstructured":"Li Y, Zhang Y, Tang Q, Huang W, Jiang Y, Xia ST. tk-means: a robust and stable k-means variant. In: ICASSP 2021\u20132021 IEEE international conference on acoustics, speech and signal processing (ICASSP). 2021. p. 3120\u20134.","DOI":"10.1109\/ICASSP39728.2021.9414687"},{"key":"798_CR34","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/s10994-021-05965-0","volume":"110","author":"L Giffon","year":"2021","unstructured":"Giffon L, Emiya V, Kadri H, Ralaivola L. QuicK-means: accelerating inference for K-means by learning fast transforms. Mach Learn. 2021;110:881\u2013905.","journal-title":"Mach Learn"},{"issue":"1","key":"798_CR35","first-page":"87","volume":"44","author":"S Xia","year":"2020","unstructured":"Xia S, Peng D, Meng D, Zhang C, Wang G, Giem E, Wei W, Chen Z. Ball k k-means: fast adaptive clustering with no bounds. IEEE Trans Pattern Anal Mach Intell. 2020;44(1):87\u201399.","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"798_CR36","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.patcog.2018.02.015","volume":"79","author":"H Ismkhan","year":"2018","unstructured":"Ismkhan H. Ik-means\u2212+: an iterative clustering algorithm based on an enhanced version of the k-means. Pattern Recogn. 2018;79:402\u201313.","journal-title":"Pattern Recogn"},{"key":"798_CR37","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2020.106290","volume":"141","author":"S Manochandar","year":"2020","unstructured":"Manochandar S, Punniyamoorthy M, Jeyachitra RK. Development of new seed with modified validity measures for k-means clustering. Comput Ind Eng. 2020;141: 106290.","journal-title":"Comput Ind Eng"},{"key":"798_CR38","doi-asserted-by":"crossref","unstructured":"Zhao W, Ma H, He Q. Parallel k-means clustering based on MapReduce. In: IEEE international conference on cloud computing. 2009. p. 674\u20139.","DOI":"10.1007\/978-3-642-10665-1_71"},{"issue":"12","key":"798_CR39","doi-asserted-by":"publisher","first-page":"3135","DOI":"10.1109\/TPDS.2014.2306193","volume":"25","author":"Y Xu","year":"2014","unstructured":"Xu Y, Qu W, Li Z, Min G, Li K, Liu Z. Efficient k-means++ approximation with MapReduce. IEEE Trans Parallel Distrib Syst. 2014;25(12):3135\u201344.","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"798_CR40","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2020.107023","volume":"152","author":"RM Alguliyev","year":"2021","unstructured":"Alguliyev RM, Aliguliyev RM, Sukhostat LV. Parallel batch k-means for Big data clustering. Comput Ind Eng. 2021;152: 107023.","journal-title":"Comput Ind Eng"},{"key":"798_CR41","unstructured":"H\u00e4m\u00e4l\u00e4inen J, K\u00e4rkk\u00e4inen T, Rossi T. Scalable initialization methods for large-scale clustering. arXiv preprint. 2020. arXiv:2007.11937."},{"issue":"12","key":"798_CR42","doi-asserted-by":"publisher","first-page":"6965","DOI":"10.1007\/s00521-020-05471-9","volume":"33","author":"K Chowdhury","year":"2021","unstructured":"Chowdhury K, Chaudhuri D, Pal AK. An entropy-based initialization method of k-means clustering on the optimal number of clusters. Neural Comput Appl. 2021;33(12):6965\u201382.","journal-title":"Neural Comput Appl"},{"key":"798_CR43","first-page":"1","volume":"38","author":"A Torrente","year":"2020","unstructured":"Torrente A, Romo J. Initializing k-means clustering by bootstrap and data depth. J Classif. 2020;38:1\u201325.","journal-title":"J Classif"},{"issue":"8","key":"798_CR44","doi-asserted-by":"publisher","first-page":"2610","DOI":"10.1007\/s10489-020-01677-5","volume":"50","author":"D Duy-Tai","year":"2020","unstructured":"Duy-Tai D, Van-Nam H. k-PbC: an improved cluster center initialization for categorical data clustering. Appl Intell. 2020;50(8):2610\u201332.","journal-title":"Appl Intell"},{"key":"798_CR45","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.114350","volume":"168","author":"FD Bortoloti","year":"2021","unstructured":"Bortoloti FD, de Oliveira E, Ciarelli PM. Supervised kernel density estimation K-means. Expert Syst Appl. 2021;168: 114350.","journal-title":"Expert Syst Appl"},{"key":"798_CR46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2021.101445","volume":"55","author":"A Fahim","year":"2021","unstructured":"Fahim A. K and starting means for k-means algorithm. J Comput Sci. 2021;55: 101445.","journal-title":"J Comput Sci"},{"key":"798_CR47","doi-asserted-by":"publisher","DOI":"10.1016\/j.measen.2023.100666","volume":"25","author":"AA Abdulnassar","year":"2023","unstructured":"Abdulnassar AA, Nair LR. Performance analysis of Kmeans with modified initial centroid selection algorithms and developed Kmeans9+ model. Meas Sens. 2023;25: 100666.","journal-title":"Meas Sens"},{"key":"798_CR48","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.118656","volume":"211","author":"M Ay","year":"2023","unstructured":"Ay M, \u00d6zbak\u0131r L, Kulluk S, G\u00fclmez B, \u00d6zt\u00fcrk G, \u00d6zer S. FC-Kmeans: fixed-centered K-means algorithm. Expert Syst Appl. 2023;211: 118656.","journal-title":"Expert Syst Appl"},{"key":"798_CR49","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2022.109593","volume":"255","author":"H Li","year":"2022","unstructured":"Li H, Wang J. Collaborative annealing power k-means++ clustering. Knowl-Based Syst. 2022;255: 109593.","journal-title":"Knowl-Based Syst"}],"container-title":["Journal of Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-023-00798-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s40537-023-00798-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-023-00798-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T18:41:46Z","timestamp":1729795306000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofbigdata.springeropen.com\/articles\/10.1186\/s40537-023-00798-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,20]]},"references-count":49,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["798"],"URL":"https:\/\/doi.org\/10.1186\/s40537-023-00798-1","relation":{},"ISSN":["2196-1115"],"issn-type":[{"value":"2196-1115","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,20]]},"assertion":[{"value":"26 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Yes.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"120"}}