This paper presents a novel binary classifier based on two best fitting hyperellipsoids in the feature space, called twin-hyperellipsoidal support vector machine (TESVM). The idea of TESVM is inspired by the minimum volume covering ellipsoid together with twin-hypersphere support vector machine (THSVM) which is a variant of the well-known support vector data description (SVDD). Following the concept of THSVM, TESVM constructs two hyperellipsoids where each hyperellipsoid is closest to one class but also as far as possible from the other class in order to form a decision boundary. The construction of hyperellipsoids in the feature space is also enabled through the use of empirical feature mapping. The experimental results on several artificial as well as standard real-world datasets are provided to demonstrate the performance of TESVM. Particularly, TESVM outperforms its spherical counterpart in term of classification accuracy.
AhipaşaoğluS.D., Fast algorithms for the minimum volume estimator, Journal of Global Optimization62(2) (2015), 351–370.
2.
BedrintsevA.A. and ChepyzhovV.V., Description of the design space by extremal ellipsoids in data representation problems, Journal of Communications Technology & Electronics61(6) (2016), 688–694.
3.
CalafioreG., Approximation of n-dimensional data using spherical and ellipsoidal primitives, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans32(2) (2002), 269–278.
4.
CevikalpH., Best fitting hyperplanes for classification, IEEE Transactions on Pattern Analysis and Machine Intelligence39(6) (2017), 1076–1088.
5.
ChangC.-C. and LinC.-J., LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology2 (2011), 27:1–27:27, http://www.csie.ntu.edu.tw/∼cjlin/libsvm.
6.
CortesC. and VapnikV., Support-vector networks, Machine Learning20(3) (1995), 273–297.
7.
DoliaA., BieT., HarrisC., Shawe-TaylorJ., TitteringtonD.M., The Minimum Volume Covering Ellipsoid Estimation in Kernel-Defined Feature Spaces, In In Machine Learning: ECML Lecture Notes in Computer Science, Vol. 4212, SpringerBerlin Heidelberg, 2006, pp. 630–637
.
8.
DoliaA.N., HarrisC.J., Shawe-TaylorJ.S. and TitteringtonD.M., Kernel ellipsoidal trimming,Data Analysis}, Computational Statistics & Data Analysis52(1) (2007), 309–324.
9.
GlineurF., Master’s thesis, Faculté Polytechnique de Mons, Mons, Belgium, Pattern Separation via Ellipsoids and Conic Programming, 1998.
10.
GotohJ.-Y. and TakedaA., Conditional minimum volume ellipsoid with application to multiclass discrimination, Computational Optimization and Applications41(1) (2008), 27–51.
11.
GrötschelM., LovászL., SchrijverA., Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, Vol. 2, Springer Berlin Heidelberg, Berlin Heidelberg, 1993.
HuangG., ChenH., ZhouZ., YinF. and GuoK., Two-class support vector data description, Pattern Recognition44(2) (2011), 320–329.
14.
KhemchandaniJayadeva R. and ChandraS., Twin support vector machines for pattern classification, IEEE Transactions on Pattern Analysis and Machine Intelligence29(5) (2007), 905–910.
15.
JohnF., Extremum Problems with Inequalities as Subsidiary Conditions, In Traces and Emergence of Nonlinear Programming, GiorgiG. and KjeldsenT.H., eds, Springer, Basel, Basel, 2014, pp. 197–215.
16.
KumarP. and YildirimE., Minimum-volume enclosing ellipsoids and core sets, Journal of Optimization Theory and Applications126(1) (2005), 1–21.
17.
LichmanM., UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, http://archive.ics.uci.edu/ml.
18.
LöfbergJ., YALMIP: A Toolbox for Modeling and Optimization in MATLAB, 2004 IEEE International Symposium on Computer Aided Control Systems Design, 2004, pp. 284–289.
19.
MuT. and NandiA.K., Multiclass classification based on extended support vector data description, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)39(5) (2009), 1206–1216.
20.
PengX. and XuD., A twin-hypersphere support vector machine classifier and the fast learning algorithm, Information Sciences221 (2013), 12–27.
21.
RosenJ.B., Pattern separation by convex programming, Journal of Mathematical Analysis and Applications10(1) (1965), 123–134.
22.
SchölkopfB., MikaS., BurgesC.J.C., KnirschP., MüllerK.R., RätschG. and SmolaA.J., Input space versus feature space in kernel-based methods, IEEE Transactions on Neural Networks10(5) (1999), 1000–1017.
23.
ShaoY.-H., ZhangC.-H., WangX.-B. and DengN.-Y., Improvements on twin support vector machines, IEEE Transactions on Neural Networks22(6) (2011), 962–968.
24.
SunP. and FreundR.M., Computation of minimum-volume covering ellipsoids, Operations Research52(5) (2004), 690–706.
25.
SylvesterJ.J., A question in the geometry of situation, Quarterly Journal of Pure and Applied Mathematics1 (1857), 79.
26.
TaxD.M.J. and DuinR.P.W., Support vector domain description, Pattern Recognition Letters20(11-13) (1999), 1191–1199.
27.
TaxD.M.J. and DuinR.P.W., Support vector data description, Machine Learning54(1) (2004), 45–66.
28.
TeeyapanK., Theera-UmponN. and AuephanwiriyakulS., Ellipsoidal support vector data description, Neural Computing and Applications28(Suppl 1) (2017), 337–347.
29.
TitteringtonD.M., Estimation of correlation coefficients by ellipsoidal trimming, Applied Statistics27(3) (1978), 227–234.
30.
ToddM.J. and YildirimE.A., On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids, Discrete Applied Mathematics155(13) (2007), 1731–1744.
31.
TütüncüR.H., TohK.C. and ToddM.J., Solving semi-definite-quadratic-linear programs using SDPT3, Mathematical Programming95(2) (2003), 189–217.
32.
VapnikV.N., Statistical Learning Theory, Wiley, New York, 1998.
33.
WangK. and XiaoH., Ellipsoidal data description, Neurocomputing238 (2017), 328–339.
34.
WeiX.-K., LiY.-H., LiY.-F. and ZhangD.-F., Enclosing machine learning: concepts and algorithms, Neural Computing and Applications17(3) (2008), 237–243.
35.
YangX.S. and DebS., World Congress on Nature Biologically Inspired Computing (NaBIC), Cuckoo Search via Lévy Flights (2009), 210–214.
36.
ZhangY. and GaoL., On Numerical solution of the maximum volume ellipsoid problem, SIAM Journal on Optimization14(1) (2003), 53–76.
