ALGORITHMIC GUARANTEES FOR HIERARCHICAL DATA GROUPING: INSIGHTS FROM AVERAGE LINKAGE, BISECTING K-MEANS, AND LOCAL SEARCH HEURISTICS
Agus Santoso, Siti Fatimah Nurhayati · International Journal of Intelligent Data and Machine Learning · 2025
Hierarchical data grouping plays a central role in diverse applications spanning bioinformatics, text mining, image segmentation, and customer behavior analysis. While a multitude of clustering algorithms have been proposed, including agglomerative techniques, divisive strategies, and heuristic optimizations, understanding their algorithmic guarantees and comparative performance remains an ongoing research challenge. This study provides a rigorous examination of the theoretical and empirical properties of three prominent approaches: average linkage clustering, bisecting k-means, and local search heuristics. We analyze their approximation bounds, convergence behaviors, and computational complexities under various objective functions, with particular emphasis on minimizing within-cluster variance and optimizing inter-cluster separation. Through formal proofs and experimental evaluation on benchmark datasets, we demonstrate that average linkage exhibits robust consistency and deterministic outcomes, though at the cost of higher computational overhead. In contrast, bisecting k-means provides scalable performance and favorable partitioning quality in high-dimensional settings, benefiting from recursive binary splitting. Local search heuristics offer flexible trade-offs between accuracy and efficiency, leveraging iterative refinement to escape suboptimal configurations. The findings underscore the importance of algorithm selection tailored to data characteristics and clustering objectives. This work contributes to a deeper understanding of the algorithmic guarantees associated with hierarchical data grouping and offers practical guidance for researchers and practitioners seeking principled, reliable clustering solutions.