A linear programming solution to data description and novelty classification
About this article
Abstract
Many real-world problems require the detection of abnormal instances of a physical process, and methods inspired by the Support Vector Machines have been developed that model reference or normal data well. These methods serve as a fundamental step to enable the classification of new data as normal or abnormal. They imply the solution of a quadratic programming problem, which can present difficulties in finding solutions with standard methods and program solvers when the number of points becomes large. In this paper, we present an approach that was developed in a different context and that leads to a linear programming problem to attain the computational advantages of a linear environment.
References
[1] D.M.J. Tax, R.P.W. Duin, Support vector data description, Machine Learning, vol. 54, pp.45-66 (2004)
[2] B. Scholkopf, J.C. Platt, J. Shawe-Taylor, A.J. Smola, R.C. Williamson, Estimating the support of a high-dimensional distribution, Microsoft Research Corp., Technical Report MSR-TR-99-87 (1999)
[3] B.E. Boser, I.M.Guyon, V.Vapnik, A training algorithm for optimal margin classifiers, Proceedings Fifth ACM Workshop on Computational Learning Theory, Pittsburgh (1992)
[4] R. Ragona, A minimax Chebyshev approach to optimal binary classification, International Journal of Applied Mathematical Research, 2 (2) 175-187 (2013)
[5] G.A. Korn, T.M. Korn, Mathematical handbook for scientist and engineers, McGraw-Hill Book Company, 1968
View more references (9)
[6] N. Cristianini, J. Shawe-Taylor, An introduction to support vector machines, Cambridge University Press, 2004
[7] C.J.C. Burges, A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery, 2, 121–167 (1998)
[8] A. N. Tikhonov, V. Y. Arsenin. Solution of ill-posed problems, Winston & Sons, 1977
[9] R. Tibshirani, Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B 58 (1): 267–288 (1996)
[10] Bache, K. & Lichman, M. (2013). UCI Machine Learning Repository, at: http://archive.ics.uci.edu/ml. Irvine, CA: University of California, School of Information and Computer Science.
[11] LPSolve IDE, freely available at: http://lpsolve.sourceforge.net/5.5/IDE.htm.
[12] John W. Chinneck, Practical optimization: a gentle introduction (2012), freely available at http://www.sce.carleton.ca/faculty/chinneck/po.html
[13] C. Campbell, K.P. Bennet, A linear programming approach to novelty detection, Neural Information Processing Systems, volume 13, pages 395-401 (2000).
[14] E. Pekalska, D.M.J. Tax, R.P.W. Duin, One-class LP classifier for dissimilarity representations, Advances in Neural Information Processing Systems, pages 761-768, (2002)