(271b) Optimization Based Polyhedral Region Approach for MULTI-CLASS DATA Classification Problem

Multi-class data classification is a supervised machine learning problem that involves assigning data to multiple groups. There are various methods for data classification problems that are based on the separation of training sets by means of hyperboxes, hyperplanes and polyhedral regions. Polyhedral approaches are designed for binary classification problem when there are only two classes. We address the multi-class data classification problem by a mixed integer linear programming model (MILP). We split data set of each class into subsets such that the subsets of different classes are separable by a hyperplane. The hyperplanes that separate a subset form a polyhedral region and the regions of different classes are disjoint. A MILP model is used to find the optimal separation by minimizing the total number of regions and misclassified data points. A preprocessing step, which is based on graph theory, is proposed to decompose or simplify the problem considering pairwise separation of classes. We have shown that there is an undirected graph for each dataset representing the linear separability relation of class pairs. Connected components of the graph is formed and MILP model is solved for each connected component with more than one element in the vertex set. We have shown that for the collection of the optimal solutions to the connected components, there is an equivalent optimal solution to the main MILP model. We also present a novel MILP-based algorithm to form the linearly separable subsets. At each iteration we form a subset of samples out of the set of unassigned samples by a MILP model that maximizes the cardinality of the new subset. The generated subset which is linearly separable from the subsets of other classes is removed from the unassigned sample set. The rest of the samples are used for generating new subsets and the algorithm terminates when all the samples are assigned. We have shown that the subsets of different classes generated by the algorithm are linearly separable and can be used to construct a feasible solution to the general MILP model. Furthermore the algorithm can be used to reduce the dataset in few iterations so that MILP model is simplified. We build classifiers based on the convex hulls of the subsets and the polyhedral regions defined by the hyperplanes for the testing phase. The hyperplanes are generated by maximizing the margin as in the support vector machines. We evaluated our approach on 15 artificial datasets and 52 benchmark problems and compared with the methods from the literature. We conclude that our optimization based approach complemented with the proposed classifiers, provides competitive results in terms of prediction accuracy.