A Generalized Framework for Predictive Clustering and Optimization
Aravinth Chembu Scott Sanner
Clustering is a powerful and extensively used data science tool. While
clustering is generally thought of as an unsupervised learning technique, there
are also supervised variations such as Spath's clusterwise regression that
attempt to find clusters of data that yield low regression error on a
supervised target. We believe that clusterwise regression is just a single
vertex of a largely unexplored design space of supervised clustering models. In
this article, we define a generalized optimization framework for predictive
clustering that admits different cluster definitions (arbitrary point
assignment, closest center, and bounding box) and both regression and
classification objectives. We then present a joint optimization strategy that
exploits mixed-integer linear programming (MILP) for global optimization in
this generalized framework. To alleviate scalability concerns for large
datasets, we also provide highly scalable greedy algorithms inspired by the
Majorization-Minimization (MM) framework. Finally, we demonstrate the ability
of our models to uncover different interpretable discrete cluster structures in
data by experimenting with four real-world datasets.