Hybrid misclassification minimization

Given two finite point setsA andB in then-dimensional real spaceR ⁿ , we consider the NP-complete problem of minimizing the number of misclassified points by a plane attempting to divideR ⁿ into two halfspaces such that each open halfspace contains points mostly ofA orB. This problem is equivalent to determining a plane {x | x ^T w=} that maximizes the number of pointsx A satisfying inx ^T w>, plus the number of pointsx B satisfyingx ^T w<. 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.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.