Answers are grounded in this paper and cite their sources.
K-means clustering is computationally efficient per iteration but highly sensitive to the choice of initial centers. This preprint presents Budgeted Weighted Two-Level K-Means (BWTL-KM), an initialization framework designed for large-scale clustering. The proposed method partitions the dataset into disjoint subsets, constructs local representatives under a fixed global budget, weights these representatives by their assigned populations, and performs weighted meta-clustering followed by a single full-data Lloyd refinement. The representative budget is explicitly controlled independently of the number of output clusters, subject to the budget being at least the number of clusters. The paper provides a conditional objective bound relating local quantization error to meta-clustering quality, alongside an analysis of computational complexity. Experimental evaluation includes 990 successful runs across six large-scale datasets, with up to approximately 2.05 million observations. In seven-method comparisons, BWTL-KM with a representative budget of 250 achieves the best average ranks for SSE, Calinski–Harabasz, and silhouette, while the 500-representative variant performs best on Davies–Bouldin. A separate comparison shows that three-restart K-means++ retains stronger aggregate clustering quality, while BWTL-KM with 125 representatives achieves lower average runtime and fewer final Lloyd iterations. These findings suggest that BWTL-KM is a competitive, quality-oriented initialization alternative for large-scale K-means clustering, while highlighting the trade-offs among representative budget, solution quality, and computational cost.
No takes yet. Share an insight, caveat, or question.
Fatemeh Gholami Ghahdarijani (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: