%A Chunhui Chen
%A O. L. Mangasarian
%T Hybrid Misclassification Minimization
%D February 1995
%R 95-05
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X Given two finite point sets \SA and \SB 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 \SA or \SB.
This problem is equivalent to
determining a plane $\{ x \mid x^T w= \gamma \}$ that maximizes the number of
points $x \in $ \SA satisfying $x^T w > \gamma$, plus the number of points
$x \in$ \SB 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.