Improving the efficiency of a mixed integer linear programming based approach for multi-class classification problem

• The multi-class classification problem using hyper-boxes is considered.
• We have improved the work of Xu and Papageorgiou (2009).
• The proposed model reduces the training time compared to the primary model.
• The proposed model maintains the accuracy of the primary model in general.
• The order of producing binary variables is reduced according to the number of boxes.

Data classification is one of the fundamental issues in data mining and machine learning. A great deal of effort has been done for reducing the time required to learn a classification model. In this research, a new model and algorithm is proposed to improve the work of Xu and Papageorgiou (2009). Computational comparisons on real and simulated patterns with different characteristics (including dimension, high overlap or heterogeneity in the attributes) confirm that, the improved method considerably reduces the training time in comparison to the primary model, whereas it generally maintains the accuracy. Particularly, this speed-increase is significant in the case of high overlap. In addition, the rate of increase in training time of the proposed model is much less than that of the primary model, as the set-size or the number of overlapping samples is increased.