Multi-polytope Machine for Classification

In numerous machine learning applications, there is a preference for classifiers characterized by a polyhedral description, as they are intended for utilization within optimization frameworks or for interpretability purposes. Here, we present a structured classifier designed to cater to downstream decision-making tasks. The classification method is achieved through the process of partitioning the feature domain into clusters and encompassing each cluster within a polytope. We employ a combined approach that integrates semi-supervised k-means with SVM. This unified optimization framework enables the simultaneous generation of multiple polytopes. The central concept involves using a k-means-based clustering method for the clustering step, followed by the utilization of SVM to construct hyperplanes between each pair of clusters. Notably, the clustering process for each class considers classification loss as well as information from other classes when allocating sample points to clusters. We propose an algorithm to solve the integer program. Our numerical experiments demonstrate the competitiveness of the proposed method across a wide spectrum of datasets, exhibiting its efficacy in comparison to existing hyperplane-based classifiers and nonlinear classifiers.