Arbitrary-norm hyperplane separation by variable neighbourhood search |
| |
Authors: | Karam, Alejandro Caporossi, Gilles Hansen, Pierre |
| |
Affiliation: | 1 HEC Montréal, 300, ch. de la côte-ste-catherine, H3T 2A7 Montréal, Qúebec, Canada, 2 HEC Montréal and GERAD, 300, ch. de la côte-ste-catherine, H3T 2A7 Montréal, Qúebec, Canada |
| |
Abstract: | ** Email: alejandro.karam{at}hec.ca*** Email: gilles.caporossi{at}gerad.ca**** Email: pierre.hansen{at}gerad.ca We consider the problem of separating two sets of points ina Euclidean space with a hyperplane that minimizes the sum ofp-norm distances to the plane of points lying on the wrongside of the plane. A variable neighbourhood search heuristicis used to determine the plane coefficients. For a set of exampleswith L1-norm, L2-norm and L-norm, for which the exact solutioncan be computed, we show that our algorithm finds it in mostcases and gets good approximations in the others. The use ofour heuristic solutions for problems in these norms can dramaticallyaccelerate exact algorithms. Our method can be applied on verylarge instances that are intractable by exact algorithms. Sincethe proposed approach works for truly arbitrary norms (otherthan the traditional 1, 2 and ), we can explore for the firsttime the effects of the choice of p on the generalization propertiesof p-norm hyperplane separation. |
| |
Keywords: | hyperplane separation linear discrimination Lp-norm VNS |
本文献已被 Oxford 等数据库收录! |
|