HyEMST: A novel hybrid ellipsoidal framework for robust clustering via maximum spanning trees

Document Type : Research Article

Authors

Department of Computer Science, Tarbiat Modares University, Tehran, Iran

Abstract

Clustering arbitrary-shaped clusters with heterogeneous densities presents a fundamental challenge in unsupervised learning. Traditional approaches emphasize either geometric distance or local density estimation, yet rarely reconcile both perspectives systematically. This paper introduces HyEMST (Hybrid Ellipsoidal Maximum Spanning Tree), a principled framework that unifies distance and density information through an explicit trade-off parameter λ ∈ [0,1]. The proposed methodology comprises five phases: (1) strategic geometric decomposition via K-Means over-segmentation; (2) robust volumetric density estimation using adaptive ridge-regularized covariance; (3) hybrid kernel construction integrating distance and density affinities; (4) topological structure discovery via maximum spanning tree; and (5) adaptive density-aware cluster merging. Theoretically, we establish that regularized covariance-based density estimation preserves density ranking with > 90% accuracy, ensuring reliable merging even for ill-conditioned micro-clusters. Computationally, the approach achieves O(N d2 ) overall complexity. Empirically, HyEMST attains perfect or near-perfect clustering on synthetic benchmarks and demonstrates superior performance compared to representative baselines on real-world datasets. Ablation studies validate the necessity of hybrid integration and confirm the efficacy of each algorithmic component.

Keywords

Main Subjects

References

[1] N. Amroune, M. Benazi, and L. Sayad, An adaptative Eps parameter of DBSCAN algorithm for identifying clusters with heterogeneous density, Comput. Sist. 28 (2024) 465--472.
[2] M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander, OPTICS: Ordering points to identify the clustering structure, SIGMOD Rec. 28 (1999) 49--60.
[3] D. Birant and A. Kut, ST-DBSCAN: An algorithm for clustering spatial--temporal data, Data Knowl. Eng. 60 (2007) 208--221.
[4] A. C. Bryant and K. J. Cios, RNN-DBSCAN: A density-based clustering algorithm using reverse nearest neighbor density estimates, IEEE Trans. Knowl. Data Eng. 30 (2018) 1109--1121.
[5] R. J. G. B. Campello, D. Moulavi, and J. Sander, Density-based clustering based on hierarchical density estimates, in Proc. Pac.-Asia Conf. Knowl. Discov. Data Min. (PAKDD), 2013, 160--172.
[6] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, in Proc. 2nd Int. Conf. Knowl. Discov. Data Min. (KDD'96), 1996, 226--231.
[7] H. Eyvazi and A. Rajaei, Accelerated DBSCAN via parallel, density-aware multi-objective genetic optimization, J. Math. Model. 13(4) (2025) 851--864.
[8] H. Eyvazi, M. Badzohreh, and S. A. Shahrokhi, VelvetFlow: An engineering pipeline for robust multi-density clustering, J. Discrete Math. Appl. 10 (2025) 333--358.
[9] H. He, A clustering algorithm based on grids for core data and adjacency relationships for edge data, Sci. Rep. 15 (2025) 18390.
[10] S. Liu, Y. He, X. Yang, and Z. Yu, INSDPC: A density peaks clustering algorithm based on interactive neighbors similarity, AIMS Math. 10 (2025) 9748--9772.
[11] J. Qian, Y. Zhou, X. Han, and Y. Wang, MDBSCAN: A multi-density DBSCAN based on relative density, Neurocomputing 576 (2024) 127329.
[12] C. Ren, C. Li, Y. Yu, W. Yang, and R. Guo, Density peak clustering algorithm based on weighted mutual K-nearest neighbors, Front. Appl. Math. Stat. 11 (2025) 1598165.
[13] A. Rodriguez and A. Laio, Clustering by fast search and find of density peaks, Science 344 (2014) 1492--1496.
[14] R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Univ. Press, Cambridge, 2018.
[15] M. J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge Univ. Press, Cambridge, 2019.
[16] H. Wang, J. Zhang, Y. Shen, S. Wang, B. Deng, and W. Zhao, Improved density peak clustering with a flexible manifold distance and natural nearest neighbors for network intrusion detection, Sci. Rep. 15 (2025) 8510.
[17] Z. Wang, Z. Ye, Y. Du, Y. Mao, Y. Liu, Z. Wu, and J. Wang, AMD-DBSCAN: An adaptive multi-density DBSCAN for datasets of extremely variable density, in Proc. IEEE Int. Conf. Data Sci. Adv. Anal. (DSAA), 2022, 1--10.
[18] H. Xu and N. Pham, Scalable DBSCAN with random projections, Adv. Neural Inf. Process. Syst. 37 (2024) 27978--28008.
Journal of Mathematical Modeling
Volume 14, Issue 3
August 2026
Pages 953-983

Files

Share

How to cite

Statistics