An efficient incremental algorithm for clustering large datasets

: Lampainen, Jenni; Joki, Kaisa; Karmitsa, Napsu; Mäkelä, Marko M.

Publisher: Springer Science and Business Media LLC

: 2026

Advances in Data Analysis and Classification

: 1862-5347

: 1862-5355

DOI: https://doi.org/10.1007/s11634-025-00661-6

: https://doi.org/10.1007/s11634-025-00661-6

: https://research.utu.fi/converis/portal/detail/Publication/523214179

Clustering is a fundamental task in data mining and machine learning, particularly for analyzing large-scale data. In this paper, we introduce Clust-Splitter, an efficient algorithm based on novel incremental approach and nonsmooth formulation of the the minimum sum-of-squares clustering problem. Particularly, the clustering task is approached through a sequence of three nonsmooth optimization problems: two auxiliary problems used to generate suitable starting points, followed by a main clustering formulation. To solve these problems effectively in very large datasets, the limited memory bundle method (Haarala et al. in Optim Methods Softw 19(6):673–692, 2004) is applied as an underlying solver in Clust-Splitter. We test and evaluate Clust-Splitter on real-world datasets characterized by both a large number of attributes and a large number of data points and compare its performance with several state-of-the-art large-scale clustering algorithms. Experimental results demonstrate the efficiency of the proposed method for clustering very large datasets, as well as the high quality of its solutions, which are on par with those of the best existing methods.

s11634-025-00661-6.pdf

:
The work was financially supported by the Research Council of Finland (projects no. #345804 and #345805 led by Prof. Tapio Pahikkala and Prof. Antti Airola, respectively), and Jenny and Antti Wihuri Foundation. Open Access funding provided by University of Turku (including Turku University Central Hospital).