Groupe d’études et de recherche en analyse des décisions

G-2005-62

Arbitrary-Norm Hyperplane Separation by Variable Neighborhood Search

, et

We consider the problem of separating two sets of points in an Euclidean space with a hyperplane that minimizes the sum of Lp-norm distances to the plane of points lying on the "wrong" side of the plane. A Variable Neighborhood Search heuristic is used to determine the plane coefficients. For a set of examples with L1-norm, L2-norm and L-norm, for which the exact solution can be computed, we show that our algorithm finds it in most cases, and gets good approximations in the others. The use of our heuristic solutions for problems in these norms can dramatically accelerate exact algorithms. Our method can be applied on very large instances that are intractable by exact algorithms. Since the proposed approach works for truly arbitrary norms (other than the traditional L1, L2 and L), we can explore for the first time the effects of the choice of p on the generalization properties of Lp-norm hyperplane separation.

, 22 pages

Ce cahier a été révisé en avril 2006