An Efficient Branch-and-Bound Algorithm for Exact Clustering via Relational Decisions

Clustering is a fundamental technique in data analysis. Its main goal is grouping observations into distinct subsets based on similarities. However, algorithm complexity has encouraged researchers to seek new approaches for modeling and solving clustering problems. Pairwise Clustering refers to the set of decisions that determine whether two observations are assigned to the same cluster. Cluster assignment, in contrast, refers to assigning data to specific clusters. This paper proposes an innovative branch-and-bound method to solve the clustering problem. It utilizes the Pairwise Clustering concept to efficiently explore the solution space, helping to identify and prevent duplicate solutions. As a result, the number of implicitly computed solutions is greatly reduced, and algorithm speed increases. Unlike traditional methods, the proposed solution reduces the solution space by maintaining a constant number of observations while increasing the number of clusters. This feature allows the algorithm to perform well in problems with many clusters. The Iris dataset is used to evaluate the proposed algorithm. Computational experiments indicate that it achieves optimal clustering results while substantially reducing computational effort. The results show that the algorithm exhibits an inverse sensitivity to the number of clusters, achieving greater efficiency as the cluster count increases relative to conventional methods.