×

zbMATH — the first resource for mathematics

An effective method to determine whether a point is within a convex hull and its generalized convex polyhedron classifier. (English) Zbl 1453.68154
Summary: A convex polyhedron classifier that encloses the minority class using a combination of hyperplanes is potentially effective in imbalanced classification. To construct an easy-to-use convex polyhedron classifier, this paper first presents a theoretical foundation for determining whether a point is within the convex hull of a finite point set. This foundation corresponds to a geometric method in which the result is expressed as a separating hyperplane. If the given point and the given convex hull are located on either side of the learned hyperplane, this indicates that the point is outside of the convex hull. Otherwise, the conclusion that the point is within the convex hull can be obtained. As a generalization of the geometric method, a convex polyhedron classifier is further proposed for binary classification. If two finite point sets are polyhedrally separable, a series of hyperplanes can be learned as a combined (piecewise linear) classifier, which surrounds a point set that is inside using a convex polyhedron and excludes the other point set that is outside. Experimental results on twelve real-world datasets show that the proposed classifier is generally better than the other two piecewise linear classifiers. Moreover, a comparison with several types of support vector machines confirms its competitiveness.
MSC:
68T05 Learning and adaptive systems in artificial intelligence
52B55 Computational aspects related to convexity
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T10 Pattern recognition, speech recognition
Software:
LIBSVM; SHOGUN; UCI-ml
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, U.; Barkai, N.; Notterman, D. A., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, Cell Biol., 96, 12, 6745-6750 (1999)
[2] Andrew, A. M., Another efficient algorithm for convex hulls in two dimensions, Inf. Process. Lett., 9, 5, 216-219 (1979) · Zbl 0423.68032
[3] Astorino, A.; Gaudioso, M., Polyhedral separability through successive LP, J. Optim. Theory Appl., 112, 2, 265-293 (2002) · Zbl 1049.90039
[4] Bagirov, A. M., Max-min separability, Optim. Methods Softw., 20, 2-3, 277-296 (2005) · Zbl 1129.90059
[5] New York, NY, 1-32
[6] Bennett, K. P.; Bredensteiner, E. J., Duality and geometry in SVM classifiers, Proceeding of the 17th International Conference on Machine Learning., 57-64 (2000), Morgan Kaufmann Publishers Inc.
[7] Borwein, J.; Lewis, A. S., Convex Analysis and Nonlinear Optimization: Theory and Examples (2010), Springer Science & Business Media
[8] Chai, B. B.; Huang, T.; Zhuang, X., Piecewise linear classifiers using binary tree structure and genetic algorithm, Pattern Recogn., 29, 11, 1905-1917 (1996)
[9] Chan, T. M., Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete Comput. Geometry, 16, 4, 361-368 (1996) · Zbl 0857.68111
[10] Chang, C. C.; Lin, C. J., LIBSVM: A library for support vector machines, ACM Trans. Intell. Syst. Technol. (TIST), 2, 3, 27 (2011)
[11] Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geome., 10, 4, 377-409 (1993) · Zbl 0786.68091
[12] Crisp, D. J.; Burges, C. J.C., A geometric interpretation of ν-SVM classifiers, Proceedings of the Advances in Neural Information Processing Systems, 244-250 (2000)
[13] Ding, S.; Nie, X.; Qiao, H., A fast algorithm of convex hull vertices selection for online classification, IEEE Trans. Neural Netw. Learn. Syst., 29, 4, 792-806 (2018)
[14] Franc, V.; Hlavá̆c, C. V., An iterative algorithm learning the maximal margin classifier, Pattern Recogn., 36, 9, 1985-1996 (2003) · Zbl 1045.68115
[15] A. Frank, A. Asuncion, UCI machine learning repository, 2010URL http://archive.ics.uci.edu/ml.
[16] Univ. Sheffield, Dept[R]. ACSE, ACSE-TR-752
[17] Golub, T. R.; Slonim, D. K.; Tamayo, P., Molecular classification of cancer: class discovery and class prediction by gene expression monitoring, Science, 286, 5439, 531-537 (1999)
[18] Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar set, Inf. Process. Lett., 1, 4, 132-133 (1972) · Zbl 0236.68013
[19] Gu, X.; Chung, F.; Wang, S., Fast convex-hull vector machine for training on large-scale ncRNA data classification tasks, Knowl. Based Syst., 151, 149-164 (2018)
[20] Herman, G. T.; Yeung, K. T.D., On piecewise-linear classification, IEEE Trans. Pattern Anal. Mach. Intell., 7, 782-786 (1992)
[21] T.K. Ho, E.M. Kleinberg, Building projectable classifiers of arbitrary complexity, Proceeding of the 13th International Conference on Pattern Recognition, IEEE 2 (1996) 880-885.
[22] Jarvis, R. A., On the identification of the convex hull of a finite set of points in the plane, Inf. Process. Lett., 2, 1, 18-21 (1973) · Zbl 0256.68041
[23] Kantchelian, A.; Tschantz, M. C.; Huang, L., Large-margin convex polytope machine, Adv. Neural Inf. Process. Syst., 3248-3256 (2014)
[24] Keerthi, S. S.; Shevade, S. K.; Bhattacharyya, C.; Murthy, K. R., A fast iterative nearest point algorithm for support vector machine classifier design, IEEE Trans. Neural Netw., 11, 1, 124-136 (2000)
[25] 1949-196 · Zbl 1102.68628
[26] Li, W.; Hu, J., Geometric approach of quasi-linear kernel composition for support vector machine, Proceeding of the International Joint Conference on Neural Networks (IJCNN), 1-7 (2015), IEEE
[27] Li, Y.; Leng, Q., Alternating multiconlitron: a novel framework for piecewise linear classification, Pattern Recogn., 48, 3, 968-975 (2015) · Zbl 1373.68354
[28] Li, Y.; Leng, Q.; Fu, Y., Cross kernel distance minimization for designing support vector machines, Int. J. Mach. Learn. Cybern., 8, 5, 1585-1593 (2017)
[29] Li, Y.; Leng, Q.; Fu, Y., Growing construction of conlitron and multiconlitron, Knowl. Based Syst., 65, 1, 12-20 (2014)
[30] Li, Y.; Liu, B.; Yang, X.; Fu, Y.; Li, H., Multiconlitron: a general piecewise linear classifier, IEEE Trans. Neural Netw., 22, 2, 276-289 (2011)
[31] Liu, Z.; Liu, J. G.; Pan, C.; Wang, G., A novel geometric approach to binary classification based on scaled convex hulls, IEEE Trans. Neural Netw., 20, 7, 1215-1220 (2009)
[32] López, J.; Barbero, A.; Dorronsoro, J. R., Clipping algorithms for solving the nearest point problem over reduced convex hulls, Pattern Recogn., 44, 3, 607-614 (2011) · Zbl 1209.68417
[33] López, J.; Dorronsoro, J. R., A common framework for the convergence of the GSK, MDM and SMO algorithms, Proceedings of the 20th International Conference on Artificial Neural Networks, 82-87 (2010), Springer, Berlin: Springer, Berlin Heidelberg
[34] Manwani, N.; Sastry, P. S., Learning polyhedral classifiers using logistic function, Proceedings of the 2nd Asian Conference on Machine Learning, 17-30 (2010)
[35] Mavroforakis, M. E.; Sdralis, M.; Theodoridis, S., A geometric nearest point algorithm for the efficient solution of the SVM classification task, IEEE Trans. Neural Netw., 18, 5, 1545-1549 (2007)
[36] 2
[37] Mavroforakis, M. E.; Theodoridis, S., A geometric approach to support vector machine (SVM) classification, IEEE Trans. Neural Netw., 17, 3, 671-682 (2006)
[38] Mitchell, B. F.; Dem’yanov, V. F.; Malozemov, V. N., Finding the point of a polyhedron closest to the origin, SIAM J. Control, 12, 1, 19-26 (1974) · Zbl 0277.52007
[39] Nalbantov, G. I.; Groenen, P. J.F.; Bioch, J. C., Nearest Convex Hull Classification (2006), Erasmus University Rotterdam, Erasmus School of Economics (ESE) Econometric Institute Research Papers (EI 2006-50)
[40] Orsenigo, C.; Vercellis, C., Accurately learning from few examples with a polyhedral classifier, Comput. Optim. Appl., 38, 2, 235-247 (2007) · Zbl 1133.68420
[41] Peng, X.; Wang, Y., Geometric algorithms to large margin classifier based on affine hulls, IEEE Trans. Neural Netw. Learn. Syst., 23, 2, 236-246 (2012)
[42] Platt, J. C., Fast training of support vector machines using sequential minimal optimization, Advances in Kernel Methods, 185-208 (1999), MIT Press
[43] Raviv, D.; Hazan, T.; Osadchy, M., Hinge-minimax learner for the ensemble of hyperplanes, J. Mach. Learn. Res., 19, 1-30 (2018) · Zbl 1407.68414
[44] Sklansky, J.; Michelotti, L., Locally trained piecewise linear classifiers, IEEE Trans. Pattern Anal. Mach. Intell., 2, 101-111 (1980) · Zbl 0443.62046
[45] Sonnenburg, S.; Rätsch, G.; Schäfer, C., Large scale multiple kernel learning, J. Mach. Learn. Res., 7, 1531-1565 (2006) · Zbl 1222.90072
[46] G. Takács, Convex polyhedron learning and its applications, Ph.D thesis, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics, 2009.
[47] Wang, D.; Zhang, X.; Fan, M., Hierarchical mixing linear support vector machines for nonlinear classification, Pattern Recogn., 59, 255-267 (2016) · Zbl 1414.68083
[48] Wang, Z.; Chen, S.; Sun, T., Multik-MHKS: a novel multiple kernel learning algorithm, IEEE Trans. Pattern Anal. Mach. Intell., 30, 2, 348-353 (2008)
[49] D. Webb, Efficient piecewise linear classifiers and applications, Ph.D thesis, Graduate School of Information Technology and Mathematical Sciences, University of Ballarat, 2010.
[50] Zhou, Y.; Jin, B.; Spanos, C. J., Learning convex piecewise linear machine for data-driven optimal control, Proceedings of the 14th International Conference on Machine Learning and Applications (ICMLA), 966-972 (2015), IEEE
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.