A novel piecewise linear classifier based on polyhedral conic and max-min separabilities. (English) Zbl 1263.65051

Summary: An algorithm for finding piecewise linear boundaries between pattern classes is developed. This algorithm consists of two main stages. In the first stage, a polyhedral conic set is used to identify data points which lie inside their classes, and in the second stage we exclude those points to compute a piecewise linear boundary using the remaining data points. Piecewise linear boundaries are computed incrementally starting with one hyperplane. Such an approach allows one to significantly reduce the computational effort in many large data sets. Results of numerical experiments are reported. These results demonstrate that the new algorithm consistently produces a good test set accuracy on most data sets comparing with a number of other mainstream classifiers.


65K05 Numerical mathematical programming methods
90C25 Convex programming


Full Text: DOI


[1] Astorino A, Gaudioso M (2002) Polyhedral separability through successive LP. J Optim Theory Appl 112(2):265–293 · Zbl 1049.90039
[2] Asuncion A, Newman D (2007) UCI machine learning repository. http://www.ics.uci.edu/mlearn/MLRepository.html
[3] Bagirov AM (1999) Minimization methods for one class of nonsmooth functions and calculation of semi-equilibrium prices. In: Progress in optimization: contribution from Australasia. Kluwer Academic, Norwell, pp 147–175
[4] Bagirov AM (2002) A method for minimization of quasidifferentiable functions. Optim Methods Softw 17(1):31–60 · Zbl 1040.90038
[5] Bagirov AM (2005) Max–min separability. Optim Methods Softw 20(2–3):271–290
[6] Bagirov AM, Ugon J (2005) Supervised data classification via max–min separability. In: Continuous optimisation: current trends and modern applications. Springer, Berlin, pp 175–208. Chap 6 · Zbl 1115.90043
[7] Bagirov AM, Ugon J (2006) Piecewise partially separable functions and a derivative-free method for large-scale nonsmooth optimization. J Glob Optim 35:163–195 · Zbl 1136.90515
[8] Bagirov AM, Karasozen B, Sezer M (2008) Discrete gradient method: derivative-free method for nonsmooth optimization. J Optim Theory Appl 137:317–334 · Zbl 1165.90021
[9] Bagirov AM, Ugon J, Webb D, Karasözen B (2011a) Classification through incremental max–min separability. Pattern Anal Appl 14:165–174
[10] Bagirov AM, Ugon J, Webb D (2011b) An efficient algorithm for the incremental construction of a piecewise linear classifier. Inf Syst 36:782–790 · Zbl 06016917
[11] Bobrowski L (1991) Design of piecewise linear classifiers from formal neurons by a basis exchange technique. Pattern Recognit 24(9):863–870
[12] Demyanov VF (2005) Mathematical diagnostics via nonsmooth analysis. Optim Methods Softw 20(2–3):191–212
[13] Gasimov RN, Ozturk G (2006) Separation via polyhedral conic functions. Optim Methods Softw 21(4):527–540 · Zbl 1113.90095
[14] Michie D, Spiegelhalter DJ, Taylor CC, Campbell J (eds) (1994) Machine learning, neural and statistical classification. Ellis Horwood, Upper Saddle River
[15] Orsenigo C, Vercellis C (2007) Accurately learning from few examples with a polyhedral classifier. Comput Optim Appl 38(2):235–247 · Zbl 1133.68420
[16] Palm H (1990) A new piecewise linear classifier. In: Proceedings 10th international conference on pattern recognition, vol 1, pp 742–744
[17] Park Y, Sklansky J (1989) Automated design of multiple-class piecewise linear classifiers. J Classif 6:195–222 · Zbl 0698.62061
[18] Schulmeister B, Wysotzki F (1994) The piecewise linear classifier DIPOL92. In: Bergadano F, Raedt LD (eds) Proceedings of the European conference on machine learning, Catania, Italy. Springer, New York, pp 411–414
[19] Sklansky J, Michelotti L (1980) Locally trained piecewise linear classifiers. IEEE Trans Pattern Anal Mach Intell 2(2):101–111 · Zbl 0443.62046
[20] Tenmoto H, Kudo M, Shimbo M (1998) Piecewise linear classifiers with an appropriate number of hyperplanes. Pattern Recognit 31(11):1627–1634 · Zbl 1274.68395
[21] Witten IH, Frank E (2005) Data mining: practical machine learning tools and techniques, 2nd edn. Morgan Kaufmann, San Francisco · Zbl 1076.68555
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.