A mathematical programming approach to hierarchical clustering

Abstract Hierarchical clustering is a statistical technique for analyzing the existing groups (clusters) within a dataset and constructing a hierarchy of clusters. This is represented by a rooted tree (dendrogram) whose leaves correspond to the data points, and each internal node represents the cluster containing its descendant leaves. Among the methods for performing hierarchical clustering, the agglomerative methods are based on greedy procedures that yield a sequence of nested partitions, where each level of the hierarchy joins two clusters from the lower partition according to a local criterion. In this work, motivated by the lack of exact approaches that guarantee global optimality, we present the first unified mathematical programming formalization of agglomerative approaches for hierarchical clustering. Through computational experiments, we validate the proposed formulations and evaluate, according to different measures commonly used in this context, the dendrograms obtained from the exact solution of the formulations and those produced by the greedy approach. Furthermore, by exploiting the mathematical formulation, we also present a scalable matheuristic algorithm capable of dealing with large-sized datasets.