Density peaks have proven effective at detecting patterns in datasets with general point distributions. Density peaks are exploited in this work to improve the K-Means and Random Swap algorithms. In particular, a new deterministic seeding method, named Hood, was proposed, which relies on data-point neighborhoods preliminarily built using the k-nearest neighbors (KNN) technique. A corresponding variant of K-Means (Hood-K-Means) was achieved, which is capable of accurate clustering in medium-sized and regularly distributed datasets. To cope with large and multidimensional datasets, an evolutionary version of Hood-K-Means was developed (Evo-Hood-K-Means), which rests on a population of candidate solutions/centroids established through a careful seeding method like K-Means++. The experiments confirmed that applying Hood to such an elitist population favors, in practical cases, the achievement of high-quality clustering. However, to handle both large, complex, and irregularly distributed datasets, a third algorithm based on Hood was developed (Evo-Hood-Random Swap), which replaced K-Means local search refinement of centroids with Random Swap global search on the population. All three algorithms could flexibly work with different objective function costs. They are implemented in parallel Java. In this paper, we described the newly developed algorithms and demonstrated, through a series of clustering experiments on synthetic and realistic datasets, the effectiveness of the achieved tools, which can ensure accurate clustering in limited time. In particular, the clustering results on some known complex and irregular datasets significantly improve upon similar results reported in the literature.
Citation: Libero Nigro. KNN neighborhoods for careful clustering[J]. Applied Computing and Intelligence, 2026, 6(2): 194-222. doi: 10.3934/aci.2026012
Density peaks have proven effective at detecting patterns in datasets with general point distributions. Density peaks are exploited in this work to improve the K-Means and Random Swap algorithms. In particular, a new deterministic seeding method, named Hood, was proposed, which relies on data-point neighborhoods preliminarily built using the k-nearest neighbors (KNN) technique. A corresponding variant of K-Means (Hood-K-Means) was achieved, which is capable of accurate clustering in medium-sized and regularly distributed datasets. To cope with large and multidimensional datasets, an evolutionary version of Hood-K-Means was developed (Evo-Hood-K-Means), which rests on a population of candidate solutions/centroids established through a careful seeding method like K-Means++. The experiments confirmed that applying Hood to such an elitist population favors, in practical cases, the achievement of high-quality clustering. However, to handle both large, complex, and irregularly distributed datasets, a third algorithm based on Hood was developed (Evo-Hood-Random Swap), which replaced K-Means local search refinement of centroids with Random Swap global search on the population. All three algorithms could flexibly work with different objective function costs. They are implemented in parallel Java. In this paper, we described the newly developed algorithms and demonstrated, through a series of clustering experiments on synthetic and realistic datasets, the effectiveness of the achieved tools, which can ensure accurate clustering in limited time. In particular, the clustering results on some known complex and irregular datasets significantly improve upon similar results reported in the literature.
| [1] |
R. Wang, Introduction to machine learning: from math to code, Cambridge: Cambridge University Press, 2026. https://doi.org/10.1017/9781009023870 |
| [2] |
F. Nielsen, Partition-based clustering with k-means, In: Introduction to HPC with MPI for data science, Cham: Springer International Publishing, 2016,163-193. https://doi.org/10.1007/978-3-319-21903-5_7 |
| [3] |
B. Everitt, S. Landau, M. Leese, D. Stahl, Cluster analysis, Hoboken: John Wiley & Sons, Inc., 2011. https://doi.org/10.1002/9780470977811 |
| [4] |
A. Rodriguez, A. Laio, Clustering by fast search and find of density peaks, Science, 344 (2014), 1492-1496. https://doi.org/10.1126/science.1242072 doi: 10.1126/science.1242072
|
| [5] |
P. Fränti, Genetic algorithm with deterministic crossover for vector quantization, Pattern Recogn. Lett., 21 (2000), 61-68. https://doi.org/10.1016/S0167-8655(99)00133-6 doi: 10.1016/S0167-8655(99)00133-6
|
| [6] |
C. Baldassi, Recombinator-k-means: an evolutionary algorithm that exploits k-means++ for recombination, IEEE Trans. Evolut. Comput., 26 (2022), 991-1003. https://doi.org/10.1109/TEVC.2022.3144134 doi: 10.1109/TEVC.2022.3144134
|
| [7] |
L. Nigro, F. Cicirelli, Improving clustering accuracy of K-means and Random Swap by an evolutionary technique based on careful seeding, Algorithms, 16 (2023), 572. https://doi.org/10.3390/a16120572 doi: 10.3390/a16120572
|
| [8] |
L. Nigro, F. Cicirelli, F. Pupo, Genetic elitist approach and density peaks to improve K-Means clustering, Algorithms, 19 (2026), 131. https://doi.org/10.3390/a19020131 doi: 10.3390/a19020131
|
| [9] |
J. MacQueen, Some methods for classification and analysis of multivariate observations, Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967,281-297. |
| [10] |
S. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory, 28 (1982), 129-137. https://doi.org/10.1109/TIT.1982.1056489 doi: 10.1109/TIT.1982.1056489
|
| [11] |
A. Jain, Data clustering: 50 years beyond k-means, Pattern Recogn. Lett., 31 (2010), 651-666. https://doi.org/10.1016/j.patrec.2009.09.011 doi: 10.1016/j.patrec.2009.09.011
|
| [12] |
S. Dasgupta, The hardness of K-means clustering, Technical Report CS2008-0916. |
| [13] |
M. Mahajan, P. Nimbhorkar, K. Varadarajan, The planar k-means problem is NP-hard, Theor. Comput. Sci., 442 (2012), 13-21. https://doi.org/10.1016/j.tcs.2010.05.034 doi: 10.1016/j.tcs.2010.05.034
|
| [14] |
M. Emre Celebi, H. Kingravi, P. Vela, A comparative study of efficient initialization methods for the k-means clustering algorithm, Expert Syst. Appl., 40 (2013), 200-210. https://doi.org/10.1016/j.eswa.2012.07.021 doi: 10.1016/j.eswa.2012.07.021
|
| [15] |
P. Fränti, S. Sieranoja, K-means properties on six clustering benchmark datasets, Appl. Intell., 48 (2018), 4743-4759. https://doi.org/10.1007/s10489-018-1238-7 doi: 10.1007/s10489-018-1238-7
|
| [16] |
P. Fränti, S. Sieranoja, How much can k-means be improved by using better initialization and repeats? Pattern Recogn., 93 (2019), 95-112. https://doi.org/10.1016/j.patcog.2019.04.014 |
| [17] |
A. Vouros, S. Langdell, M. Croucher, E. Vasilaki, An empirical comparison between stochastic and deterministic centroid initialisation for K-means variations, Mach. Learn., 110 (2021), 1975-2003. https://doi.org/10.1007/s10994-021-06021-7 doi: 10.1007/s10994-021-06021-7
|
| [18] |
T. Gonzalez, Clustering to minimize the maximum inter cluster distance, Theor. Comput. Sci., 38 (1985), 293-306. https://doi.org/10.1016/0304-3975(85)90224-5 doi: 10.1016/0304-3975(85)90224-5
|
| [19] |
D. Arthur, S. Vassilvitskii, k-means++: the advantages of careful seeding, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, 1027-1035. |
| [20] |
P. Fränti, Efficiency of Random Swap algorithm, J. Big Data, 5 (2018), 13. https://doi.org/10.1186/s40537-018-0122-y doi: 10.1186/s40537-018-0122-y
|
| [21] |
L. Nigro, F. Cicirelli, P. Fränti, Parallel Random Swap: an efficient and reliable clustering algorithm in Java, Simul. Model. Pract. Th., 124 (2023), 102712. https://doi.org/10.1016/j.simpat.2022.102712 doi: 10.1016/j.simpat.2022.102712
|
| [22] |
S. Sieranoja, P. Fränti, Fast and general density peaks clustering, Pattern Recogn. Lett., 128 (2019), 551-558. https://doi.org/10.1016/j.patrec.2019.10.019 doi: 10.1016/j.patrec.2019.10.019
|
| [23] |
L. Nigro, F. Cicirelli, ParDP: a parallel density peaks-based clustering algorithm, Mathematics, 13 (2025), 1285. https://doi.org/10.3390/math13081285 doi: 10.3390/math13081285
|
| [24] |
M. Du, S. Ding, H. Jia, Study on density peaks clustering based on k-nearest neighbors and principal component analysis, Knowl. -Based Syst., 99 (2016), 135-145. https://doi.org/10.1016/j.knosys.2016.02.001 doi: 10.1016/j.knosys.2016.02.001
|
| [25] |
Q. Zhu, J. Feng, J. Huang, Natural neighbor: a self-adaptive neighborhood method without parameter K, Pattern Recogn. Lett., 80 (2016), 30-36. https://doi.org/10.1016/j.patrec.2016.05.007 doi: 10.1016/j.patrec.2016.05.007
|
| [26] |
Q. Dai, Z. Xiong, J. Xie, X. Wang, Y. Zhang, J, Shang, A novel clustering algorithm based on the natural reverse nearest neighbor structure, Inform. Syst., 84 (2019), 1-16. https://doi.org/10.1016/j.is.2019.04.001 doi: 10.1016/j.is.2019.04.001
|
| [27] |
T. Cover, P. Hart, Nearest neighbor pattern classification, IEEE Trans. Inform. Theory, 13 (1967), 21-27. https://doi.org/10.1109/TIT.1967.1053964 doi: 10.1109/TIT.1967.1053964
|
| [28] |
L. Nigro, F. Cicirelli, Fast clustering convergence by genetic algorithm, In: Intelligent sustainable systems, Singapore: Springer Nature, 2024,331-342. https://doi.org/10.1007/978-981-97-9324-2_27 |
| [29] |
R. Urma, M. Fusco, A. Mycroft, Modern Java in action, New York: Manning Publications Co., 2019. |
| [30] |
V. Subramanian, Functional programming in Java, Dallas: The Pragmatic Bookshelf, 2014. |
| [31] |
L. Nigro, Performance of parallel K-Means algorithms in Java, Algorithms, 15 (2022), 117. https://doi.org/10.3390/a15040117 doi: 10.3390/a15040117
|
| [32] |
P. Rousseeuw, Silhouettes: a graphical aid to the interpretation and validation of cluster analysis, J. Comput. Appl. Math., 20 (1987), 53-65. https://doi.org/10.1016/0377-0427(87)90125-7 doi: 10.1016/0377-0427(87)90125-7
|
| [33] |
M. Rezaei, P. Fränti, Set matching measures for external cluster validity, IEEE Trans. Know. Data Eng., 28 (2016), 2173-2186. https://doi.org/10.1109/TKDE.2016.2551240 doi: 10.1109/TKDE.2016.2551240
|
| [34] |
P. Franti, C. Cariou, Q. Zhao, Cluster overlap as objective function, CMC-Comput. Mater. Con., 85 (2025), 4687-4704. https://doi.org/10.32604/cmc.2025.066534 doi: 10.32604/cmc.2025.066534
|
| [35] |
F. Wang, L. Li, P. Fränti, Avoiding local minima in overlap-based clustering by Random Swap, Systems and Computing, 2 (2026), 1-17. https://doi.org/10.64409/sycom.v2.i1.22 doi: 10.64409/sycom.v2.i1.22
|
| [36] |
P. Fränti, S. Sieranoja, Clustering accuracy, Appl. Comput. Intell., 4 (2024), 24-44. https://doi.org/10.3934/aci.2024003 doi: 10.3934/aci.2024003
|
| [37] |
P. Fränti, M. Rezaei, Q. Zhao, Centroid index: cluster level similarity measure, Pattern Recogn., 47 (2014), 3034-3045. https://doi.org/10.1016/j.patcog.2014.03.017 doi: 10.1016/j.patcog.2014.03.017
|
| [38] |
P. Fränti, M. Rezaei, Generalized centroid index to different clustering models, In: Structural, syntactic, and statistical pattern recognition, Cham: Springer, 2016,285-296. https://doi.org/10.1007/978-3-319-49055-7_26 |
| [39] |
L. Nigro, F. Cicirelli, Clustering performance of a recombinator Hartigan-Wong algorithm, Computers, 15 (2026), 394. https://doi.org/10.3390/computers15060394 doi: 10.3390/computers15060394
|
| [40] |
School of Computing, Clustering basic benchmark, University of Eastern Finland, 2026. Available from: https://cs.uef.fi/sipu/datasets/. |
| [41] |
AT & T, Olivetti facial recognition dataset, Scikit-learn developers, 2026. Available from: https://scikit-learn.org/stable/modules/generated/sklearn.datasets.fetch_olivetti_faces.html#sklearn.datasets.fetch_olivetti_faces. |
| [42] |
F. Nie, Z. Li, R. Wang, X. Li, An effective and efficient algorithm for K-means clustering with new formulation, IEEE Trans. Know. Data Eng., 35 (2023), 3433-3443. https://doi.org/10.1109/TKDE.2022.3155450 doi: 10.1109/TKDE.2022.3155450
|
| [43] |
UCI, UC Irvine machine learning repository, UC Irvine, 2026. Available from: https://archive.ics.uci.edu/ml. |
The A1 dataset, N = 3000, K = 30
The A2 dataset, N = 5250, K = 35
The A3 dataset, N = 7500, K = 50
The S1 dataset
The S2 dataset
The S3 dataset
The S4 dataset
Partitions and centroids of A1
Partitions and centroids of S4
Two example datasets of the G2 family [40]
Birch1 dataset [40]
Birch2 dataset [40]
Birch3 dataset [40]
Partitions and centroids of Jain
Partitions and centroids of R15
Partitions and centroids of PathBased
Detected centroids of D31
The Worms_2d dataset [40]