Abstract
In the context of learning theory many efforts have been devoted to developing classification algorithms able to scale up with massive data problems. In this paper the complementary issue is addressed, aimed at deriving powerful classification rules by accurately learning from few data. This task is accomplished by solving a new mixed integer programming model that extends the notion of discrete support vector machines, in order to derive an optimal set of separating hyperplanes for binary classification problems. According to the cardinality of the set of hyperplanes, the classification region may take the form of a convex polyhedron or a polytope in the original space where the examples are defined. Computational tests on benchmark datasets highlight the effectiveness of the proposed model, that yields the greatest accuracy when compared to other classification approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anthony, M.: On data classification by iterative linear partitioning. Discrete Appl. Math. 144, 2–16 (2004)
Astorino, A., Gaudioso, M.: Polyhedral separability through successive LP. J. Optim. Theory Appl. 112, 265–293 (2002)
Berg, C., Christensen, J.P.R., Ressel, P.: Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions. Springer, New York (1984)
Bradley, P.S., Fayyad, U.M., Mangasarian, O.L.: Mathematical programming for data mining: formulations and challenges. INFORMS J. Comput. 11, 217–238 (1999)
Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines (2001)
Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge University Press, Cambridge (2000)
Evgeniou, T., Poggio, T., Pontil, M., Verri, A.: Regularization and statistical learning theory for data analysis. J. Comput. Stat. Data Anal. 38, 421–432 (2002)
Geman, S.: Compositionality. Technical report, Brown University Faculty Bulletin (1999)
Herman, G.T., Yeung, K.T.D.: On piecewise-linear classification. IEEE Trans. Pattern Anal. Mach. Intell. 14, 782–786 (1992)
Hettich, S., Blake, C., Merz, C.: UCI repository of machine learning databases. URL http://www.ics.uci.edu/~mlearn/MLRepository.html (1998)
Kohavi, R.: A study of cross-validation and bootstrap for accuracy estimation and model selection. In: Proceedings of the Fourteenth International Conference on Artificial Intelligence, pp. 1137–1143. Morgan Kaufmann, San Mateo (1995)
Mangasarian, O.: Mathematical programming in data mining. Data Min. Knowl. Discov. 1, 183–201 (1997)
Orsenigo, C., Vercellis, C.: Multivariate classification trees based on minimum features discrete support vector machines. IMA J. Manag. Math. 14, 221–234 (2003)
Orsenigo, C., Vercellis, C.: Discrete support vector decision trees via tabu-search. J. Comput. Stat. Data Anal. 47, 311–322 (2004)
Orsenigo, C., Vercellis, C.: One-against-all multicategory classification via discrete support vector machines. In: Ebecken N., et al. (eds.) Data Mining IV, pp. 255–264. WIT, Ashurst Lodge (2004)
Remshagen, A., Truemper, K.: Algorithms for logic-based abduction. Technical report, University of Texas at Dallas (2002)
Scholkopf, B., Smola, A.J.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and beyond. MIT, Cambridge (2002)
Tikhonov, A.N., Arsenin, V.Y.: Solutions of Ill-Posed Problems. Winston, Washington (1977)
Vapnik, V.: The Nature of Statistical Learning Theory. Springer, New York (1995)
Vapnik, V.: Statistical Learning Theory. Wiley, New York (1998)
Wolberg, W.H., Mangasarian, O.L.: Multisurface method of pattern separation for medical diagnosis applied to breast cytology. Proc. Nat. Acad. Sci. 87, 9193–9196 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by PRIN grant 2004132117.
Rights and permissions
About this article
Cite this article
Orsenigo, C., Vercellis, C. Accurately learning from few examples with a polyhedral classifier. Comput Optim Appl 38, 235–247 (2007). https://doi.org/10.1007/s10589-007-9041-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9041-0