Building separating concentric balls to solve a multi-instance classification problem

Emilio Carrizosa (ecarrizosaus.es)
José Gordillo (jgordillous.es)
Frank Plastria (Frank.Plastriavub.ac.be)

Abstract: In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class if at least one element is strictly included inside the ball, and it is labelled as negative otherwise. We model this question as a margin optimization problem. Several necessary optimality conditions are derived leading to a polynomial algorithm in fixed dimension. A VNS type heuristic is proposed and experimentally tested.

Keywords: Supervised Classification, Multi-Instance Learning, Mixed-Integer Programming, Variable Neighbourhood Search

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation:

Download: [PDF]

Entry Submitted: 01/31/2008
Entry Accepted: 01/31/2008
Entry Last Modified: 02/04/2008

Modify/Update this entry