TY - JOUR

T1 - Universum Selection for Boosting the Performance of Multiclass Support Vector Machines Based on One-versus-One Strategy

AU - Songsiri, Patoomsiri

AU - Cherkassky, Vladimir

AU - Kijsirikul, Boonserm

PY - 2018/11/1

Y1 - 2018/11/1

N2 - We propose a novel framework to enhance the performance of the one-versus-one support vector machine by using Universum. For solving a multiclass classification problem, one-versus-one is one of the state-of-the-art algorithms, which constructs N(N−1)/2 binary classifiers for an N-class problem. Each binary classifier is originally learned by two classes of data as positive and negative classes while the other N−2 remaining classes are ignored, even if they might also represent a hidden concept of the application domain and can help to boost the performance of the classifier. Vapnik et al. [20, 21] introduced Universum binary support vector machines to enable the use of samples that do not belong to positive and negative classes and called these samples Universum samples. However, not all Universum samples can be helpful; moreover, improper selection of Universum samples can prevent the construction of an effective binary classifier. For the construction of a Universum binary classifier in the one-versus-one strategy, there are 2N−2 candidate subsets of classes of Universum data; a proper selection of them can be difficult, based on the number of classes. We design an algorithm to obtain a suitable subset of classes of Universum data by applying the proposed performance measure that reflects the properties of Universum data relative to labeled training data. This measure is based on the analysis of the projection of Universum data onto the normal direction vector of the standard binary SVM hyperplane. We demonstrate experimentally that our proposed strategy outperforms existing methods.

AB - We propose a novel framework to enhance the performance of the one-versus-one support vector machine by using Universum. For solving a multiclass classification problem, one-versus-one is one of the state-of-the-art algorithms, which constructs N(N−1)/2 binary classifiers for an N-class problem. Each binary classifier is originally learned by two classes of data as positive and negative classes while the other N−2 remaining classes are ignored, even if they might also represent a hidden concept of the application domain and can help to boost the performance of the classifier. Vapnik et al. [20, 21] introduced Universum binary support vector machines to enable the use of samples that do not belong to positive and negative classes and called these samples Universum samples. However, not all Universum samples can be helpful; moreover, improper selection of Universum samples can prevent the construction of an effective binary classifier. For the construction of a Universum binary classifier in the one-versus-one strategy, there are 2N−2 candidate subsets of classes of Universum data; a proper selection of them can be difficult, based on the number of classes. We design an algorithm to obtain a suitable subset of classes of Universum data by applying the proposed performance measure that reflects the properties of Universum data relative to labeled training data. This measure is based on the analysis of the projection of Universum data onto the normal direction vector of the standard binary SVM hyperplane. We demonstrate experimentally that our proposed strategy outperforms existing methods.

KW - Support vector machine (SVM)

KW - Universum support vector machine (USVM)

KW - multi-class classification

KW - one-versus-one

UR - http://www.scopus.com/inward/record.url?scp=85050922078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050922078&partnerID=8YFLogxK

U2 - 10.1016/j.knosys.2018.05.025

DO - 10.1016/j.knosys.2018.05.025

M3 - Article

AN - SCOPUS:85050922078

VL - 159

SP - 9

EP - 19

JO - Knowledge-Based Systems

JF - Knowledge-Based Systems

SN - 0950-7051

ER -