Optimal Expected-Distance Separating Halfspace
Open Access
- 1 August 2008
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 33 (3) , 662-677
Abstract
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.Keywords
This publication has 22 references indexed in Scilit:
- A representation of bivariate extreme value distributions via norms on $ \mathbb{R}^{2} $Extremes, 2006
- Interpolation of Lipschitz functionsJournal of Computational and Applied Mathematics, 2005
- Universal nonuniform random vector generator based on acceptance-rejectionACM Transactions on Modeling and Computer Simulation, 2005
- Generalized Goal Programming: polynomial methods and applicationsMathematical Programming, 2002
- Quantile functions for multivariate analysis: approaches and applicationsStatistica Neerlandica, 2002
- Arbitrary-norm separating planeOperations Research Letters, 1999
- On a Geometric Notion of Quantiles for Multivariate DataJournal of the American Statistical Association, 1996
- Dual Cones, Dual Norms, and Simultaneous Inference for Partially Ordered MeansJournal of the American Statistical Association, 1996
- Minimax Designs in Linear Regression ModelsThe Annals of Statistics, 1995
- Geometrical properties of the Fermat-Weber problemEuropean Journal of Operational Research, 1985