Hybrid misclassification minimization |
| |
Authors: | Chunhui Chen O L Mangasarian |
| |
Institution: | (1) Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, 53706 Madison, WI, USA |
| |
Abstract: | Given two finite point setsA andB in then-dimensional real spaceR
n
, we consider the NP-complete problem of minimizing the number of misclassified points by a plane attempting to divideR
n
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|