An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering
  The minimum sum-of-squares clustering (MSSC), or k-means type clustering, is
traditionally considered an unsupervised learning task. In recent years, the
use of background knowledge to improve the cluster quality and promote
interpretability of the clustering process has become a hot research topic at
the intersection of mathematical optimization and machine learning research.
The problem of taking advantage of background information in data clustering is
called semi-supervised or constrained clustering. In this paper, we present a
new branch-and-bound algorithm for semi-supervised MSSC, where background
knowledge is incorporated as pairwise must-link and cannot-link constraints.
For the lower bound procedure, we solve the semidefinite programming relaxation
of the MSSC discrete optimization model, and we use a cutting-plane procedure
for strengthening the bound. For the upper bound, instead, by using integer
programming tools, we propose an adaptation of the k-means algorithm to the
constrained case. For the first time, the proposed global optimization
algorithm efficiently manages to solve real-world instances up to 800 data
points with different combinations of must-link and cannot-link constraints and
with a generic number of features. This problem size is about four times larger
than the one of the instances solved by state-of-the-art exact algorithms.
