Hybrid misclassification minimization

Given two finite point sets A and B in the n-dimensional real space R(n), we consider the NP-complete problem of minimizing the number of misclassified points by a plane attempting to divide R(n) into two halfspaces such that each open halfspace contains points mostly of A or B. This problem is equivalent to determining a plane {x \ x(T) w = gamma} that maximizes the number of points x is an element of A satisfying x(T) w > gamma, plus the number of points x is an element of B satisfying x(T) w < gamma. A simple but fast algorithm is proposed that alternates between (i) minimizing the number of misclassified points by translation of the separating plane, and (ii) a rotation of the plane so that it minimizes a weighted average sum of the distances of the misclassified points to the separating plane. Existence of a global solution to an underlying hybrid minimization problem is established. Computational comparison with a parametric approach to solve the NP-complete problem indicates that our approach is considerably faster and appears to generalize better as determined by tenfold cross-validation.