http:^^www.cs.wisc.edu^dienst^ui^2.0^describe^ncstrl.uwmadison%2fmp-tr-95-05

This data set contains WWW-pages collected from computer science departments of various universities

Server: Dienst V4-1-1 
MIME-version: 1.0
Content-type: text/html

<TITLE>Hybrid Misclassification Minimization </TITLE>
<H2>Hybrid Misclassification Minimization </H2>
 Chunhui Chen and  O. L. Mangasarian<BR>
MP-TR-95-05<BR>
February 1995
<p>
 Given two finite point sets \SA and \SB in the n-dimensional real space <i>R^n</i>, we consider the NP-complete problem of minimizing the number of misclassified points by a plane attempting to divide <i>R^n</i> into two halfspaces such that each open halfspace contains points mostly of \SA or \SB. This problem is equivalent to determining a plane <i>\{ x \mid x^T w= \gamma \}</i> that maximizes the number of points <i>x \in </i> \SA satisfying <i>x^T w > \gamma</i>, plus the number of points <i>x \in</i> \SB satisfying <i>x^T w < \gamma</i>. 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.<P>
<hr><p>
<H2>How to view this document</H2>
<P><UL>
<P>
<LI>Display the <B>whole</B> document in one of the following formats.
<P><UL>
<LI><!WA0><A HREF="http://www.cs.wisc.edu/Dienst/Repository/2.0/Body/ncstrl.uwmadison%2fMP-TR-95-05/postscript">PostScript
</A> 55123 bytes. (compressed on disk, will be sent uncompressed)
</UL>
<BR>
<LI>
<!WA1><A HREF="http://www.cs.wisc.edu/Dienst/UI/2.0/Print/ncstrl.uwmadison%2fMP-TR-95-05">Print or download all or selected pages.
</A></UL>
<HR>
<p>
<BLOCKQUOTE> You are granted permission for the non-commercial reproduction, distribution,display, and performance of this technical report in any format, BUT thispermission is only for a period of 45 (forty-five) days from the most recenttime that you verified that this technical report is still available fromthe Computer Science Department of the University of Wisconsin - Madison underterms that include this permission.  All other rights are reserved by theauthor(s). </BLOCKQUOTE></p><HR><p>
[ <!WA2><A HREF="http://www.cs.wisc.edu/Dienst/UI/2.0/Search">Search</A>
 ]
<HR>
<I><!WA3><img align=left  src="http://www.cs.wisc.edu/Dienst/htdocs/image_gif/sm_ncstrl.gif">NCSTRL</I><br><I>This server operates at UW Madison Computer Sciences Technical Reports .</I> <BR><I>Send email to <!WA4><A HREF="mailto: [e-mail]">[e-mail]</A> </I>