This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Carrizosa, E. Articles by Plastria, F. Search for Related Content

Optimal Expected-Distance Separating Halfspace

Facultad de Matemáticas, Universidad de Sevilla, 41012 Sevilla, Spain
Department of Mathematics, Operational Research, Statistics and Information Systems for Management, Vrije Universiteit Brussel, B 1050 Brussels, Belgium
ecarrizosa{at}us.es
frank.plastria{at}vub.ac.be

One recently proposed criterion to separate two data sets in discriminant analysis is to use a hyperplane, which minimizes the sum of distances to it from all the misclassified data points. Here all distances are supposed to be measured by way of some fixed norm, while misclassification means lying in the wrong halfspace. In this paper we study the problem of determining such an optimal halfspace when points are distributed according to an arbitrary random vector X in ^d. In the unconstrained case in dimension d, we prove that any optimal separating halfspace always balances the misclassified points. Moreover, under polyhedrality assumptions on the support of X, there always exists an optimal separating halfspace passing through d affinely independent points. These results extend in a natural way when different norms (or a fixed gauge) are used to measure distances, and we allow constraints modeling that certain points are forced to be correctly classified.

Key Words: gauge-distance to hyperplane; separating halfspace; discriminant analysis
History: Received: March 30, 2004; revision received: August 15, 2006;