Hybrid Misclassification Minimization

Abstract

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^Tw=y} that maximizes the number of points x E A satisfying x^Tw>Y, plus number of points x E B satisfying X^Tw<y. 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 distance 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