Maximum Margin One Class Support Vector Machines for multiclass problems

Many applications require the ability to identify data that is anomalous with respect to a target group of observations. To tackle this problem, one possible approach is to use one class classification methods because of their ability to reject outliers. However, it is also possible to use standard multiclass classification by exploiting the negative data to infer a description of the target class. In this paper, we propose a modified Maximum Margin One Class SVM method as a discriminative framework to deal with multiclass problems. To this end, we present Maximum Margin One Class SVM coupled with the constraints of binary SVM detection (OC2). For each class, we aim to define a closed boundary around the target class such that the corresponding domain includes the target class elements as much as possible, while it minimizes the chance of accepting outliers and objects from the other classes. Because of the closure of decision boundaries, our method also allows detection of data belonging to potentially new clusters. Within the framework of decomposition methods and to deal with large data sets, we introduce a fast algorithm for optimizing OC2 which uses an efficient heuristic for selecting the working set. Our gradient based algorithm relies on the analytical recursive computation of the objective function, the gradient and the solution. The optimal step size is also obtained analytically. This algorithm is tested on simulated and benchmark data. (C) 2011 Elsevier B.V. All rights reserved.