Authors: Saïd Hanafi Nicola Yanev
Publish Date: 2009/06/23
Volume: 183, Issue: 1, Pages: 25-46
Abstract
The twogroup classification problem consists in constructing a classifier that can distinguish between the two groups In this paper we consider the twogroup classification problem which consists in determining a hyperplane that minimizes the number of misclassified points We assume that the data set is numeric and with no missing data We develop a tabu search TS heuristic for solving this NPhard problem The TS approach is based on a more convenient equivalent formulation of the classification problem We also propose supplementary new intensification phases based on surrogate constraints The results of the conducted computational experiments show that our TS algorithms produce solutions very close to the optimum and require significantly lower computational effort so it is a valuable alternative to the MIP approaches Moreover the tabu search procedures showed in this paper can be extended in a natural way to the general classification problem which consists of generating more than one separating hyperplanes
Keywords: