×

Minimizing the error of linear separators on linearly inseparable data. (English) Zbl 1243.68158

Summary: Given linearly inseparable sets \(R\) of red points and \(B\) of blue points, we consider several measures of how far they are from being separable. Intuitively, given a potential separator (“classifier”), we measure its quality (“error”) according to how much work it would take to move the misclassified points across the classifier to yield separated sets. We consider several measures of work and provide algorithms to find linear classifiers that minimize the error under these different measures.

MSC:

68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P. K.; Aronov, B.; Chan, T. M.; Sharir, M., On levels in arrangements of lines, segments, planes, and triangles, Discrete Comput. Geom., 19, 315-331 (1998) · Zbl 0899.68106
[2] Agarwal, P. K.; Guibas, L. J.; Har-Peled, S.; Rabinovitch, A.; Sharir, M., Computing the penetration depth of two convex polytopes in 3D, Nordic J. Comput., 7, 227-240 (2000) · Zbl 0977.68088
[3] Arkin, E. M.; Hurtado, F.; Mitchell, J. S.B.; Seara, C.; Skiena, S. S., Some lower bounds on geometric separability problems, Internat. J. Comput. Geom. Appl., 16, 1-26 (2006) · Zbl 1093.68042
[4] Aronov, B.; Har-Peled, S., On approximating the depth and related problems, SIAM J. Comput., 38, 899-921 (2008) · Zbl 1180.68278
[5] Bennett, K. P.; Mangasarian, O. L., Robust linear programming discrimination of two linearly inseparable sets, Optim. Methods Softw., 1, 1, 23-34 (1992)
[6] Blum, M.; Floyd, R. W.; Pratt, V.; Rivest, R.; Tarjan, R., Time bounds for selection, J. Comput. System Sci., 7, 448-461 (1973) · Zbl 0278.68033
[7] Boissonnat, J. D.; Czyzowicz, J.; Devillers, O.; Urrutia, J.; Yvinec, M., Computing largest circles separating two sets of segments, Internat. J. Comput. Geom. Appl., 10, 1, 41-53 (2000) · Zbl 1074.68631
[8] S.A. Cameron, R.K. Culley, Determining the minimum translational distance between two convex polyhedra. In: Proc. Int. Conf. on Robotics and Automation, 1986, pp. 591-596.; S.A. Cameron, R.K. Culley, Determining the minimum translational distance between two convex polyhedra. In: Proc. Int. Conf. on Robotics and Automation, 1986, pp. 591-596.
[9] T.M. Chan, Remarks on the \(k\); T.M. Chan, Remarks on the \(k\)
[10] Chan, T. M., Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus, Internat. J. Comput. Geom. Appl., 12, 67-85 (2002) · Zbl 1152.68659
[11] Chan, T. M., Low-dimensional linear programming with violations, SIAM J. Comput., 34, 879-893 (2005) · Zbl 1075.68092
[12] Chan, T. M., A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries, J. ACM, 57, 3 (2010), Article 16 · Zbl 1327.68314
[13] Chan, T. M., Random sampling, halfspace range reporting, and construction of \(( \leq k)\)-levels in three dimensions, SIAM J. Comput., 30, 561-575 (2000) · Zbl 0963.68207
[14] Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom., 10, 377-409 (1993) · Zbl 0786.68091
[15] Clarkson, K. L., New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195-222 (1987) · Zbl 0615.68037
[16] Clarkson, K. L.; Shor, P. W., Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 387-421 (1989) · Zbl 0681.68060
[17] Cole, R.; Sharir, M.; Yap, C. K., On \(k\)-hulls and related problems, SIAM J. Comput., 16, 61-77 (1987) · Zbl 0637.68074
[18] Cortés, C.; Díaz-Báñez, J. M.; Pérez-Lantero, P.; Seara, C.; Urrutia, J.; Ventura, I., Bichromatic separability with two boxes: a general approach, Journal of Algorithms, Algorithms in Cognition, Informatics and Logic, 64, 2-3, 79-88 (2009) · Zbl 1192.68174
[19] Cristianini, N.; Shawe-Taylor, J., An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods (2000), Cambridge University Press
[20] Dey, T. K., Improved bounds on planar \(k\)-sets and \(k\)-levels, Discrete Comput. Geom., 19, 373-382 (1998) · Zbl 0899.68107
[21] Dobkin, D.; Hershberger, J.; Kirkpatrick, D.; Suri, S., Computing the intersection-depth of polyhedra, Algorithmica, 9, 518-533 (1993) · Zbl 0797.68162
[22] Duda, R.; Hart, P.; Stork, D., Pattern Classification (2001), John Wiley and Sons, Inc. · Zbl 0968.68140
[23] Edelsbrunner, H., (Algorithms in Combinatorial Geometry. Algorithms in Combinatorial Geometry, EATCS Series Monographs in Theoretical Computer Science, vol. 10 (1987), Springer) · Zbl 0634.52001
[24] D. Elizondo, Searching for linearly separable subsets using the class of linear separability method, in: IEEE International Joint Conference on Neural Networks, 2004, pp. 955-960.; D. Elizondo, Searching for linearly separable subsets using the class of linear separability method, in: IEEE International Joint Conference on Neural Networks, 2004, pp. 955-960.
[25] Everett, H.; Robert, J.-M.; van Kreveld, M., An optimal algorithm for the \(( \leq k)\)-levels, with applications to separation and transversal problems, Internat. J. Comput. Geom. Appl., 6, 247-261 (1996) · Zbl 0859.68040
[26] Gajentaan, A.; Overmars, M. H., On a class of \(O(n^2)\) problems in computational geometry, Comput. Geom. Theory Appl., 5, 165-185 (1995) · Zbl 0839.68105
[27] Har-Peled, S., Taking a walk in a planar arrangement, SIAM J. Comput., 30, 1341-1367 (2000) · Zbl 0976.68157
[28] Houle, M. E., Algorithms for weak and wide separation of sets, Discrete Appl. Math., 45, 139-159 (1993) · Zbl 0797.68160
[29] Houle, M. E.; Toussaint, G. T., Computing the width of a set, IEEE Trans. Pattern Anal. Mach. Intell., 10, 761-765 (1988) · Zbl 0659.68067
[30] Hurtado, F.; Noy, M.; Ramos, P. A.; Seara, C., Separating objects in the plane by wedges and strips, Discrete Appl. Math., 109, 109-138 (2000) · Zbl 0967.68160
[31] Karam, A.; Caporossi, G.; Hansen, P., Arbitrary-norm hyperplane separation by variable neighbourhood search, IMA J. Manag. Math, 18, 173-189 (2007) · Zbl 1177.90376
[32] Kim, Y. J.; Lin, M. C.; Manocha, D., Incremental penetration depth estimation between convex polytopes using dual-space expansion, IEEE Trans. Vis. Comput. Graphics, 10, 152-163 (2004)
[33] Y.J. Kim, M.A. Otaduy, M.C. Lin, D. Manocha, Fast penetration-depth computation for physically-based animation, in: Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2002, pp. 23-31.; Y.J. Kim, M.A. Otaduy, M.C. Lin, D. Manocha, Fast penetration-depth computation for physically-based animation, in: Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2002, pp. 23-31.
[34] Matoušek, J.; Sharir, M.; Smorodinsky, S.; Wagner, U., \(k\)-sets in four dimension, Discrete Comput. Geom., 35, 177-191 (2006) · Zbl 1086.68139
[35] Megiddo, N., Linear programming in linear time when the dimension is fixed, J. ACM, 31, 1, 114-127 (1984) · Zbl 0637.90064
[36] O’Rourke, J.; Kosaraju, S. R.; Megiddo, N., Computing circular separability, Discrete Comput. Geom., 1, 1, 105-113 (1986) · Zbl 0598.52008
[37] Overmars, M. H.; van Leeuwen, J., Maintenance of configurations in the plane, J. Comput. System Sci., 23, 166-204 (1981) · Zbl 0474.68082
[38] J. Rico, Dynamic planar convex hull, Ph.D. Dissertation, BRICS, Aarhus, Denmark, 2002.; J. Rico, Dynamic planar convex hull, Ph.D. Dissertation, BRICS, Aarhus, Denmark, 2002.
[39] Roos, T.; Widmayer, P., \(k\)-Violation linear programming, Inform. Process. Lett., 52, 109-114 (1994) · Zbl 0816.90103
[40] Schölkopf, B.; Smola, A. J., Learning with Kernels (2002), The MIT Press
[41] Sharir, M.; Smorodinsky, S.; Tardos, G., An improved bound for \(k\)-sets in three dimensions, Discrete Comput. Geom., 26, 195-204 (2001) · Zbl 0988.52034
[42] Simon, H. U., On the complexity of working set selection, Theoret. Comput. Sci., 382, 3, 262-279 (2007) · Zbl 1127.68087
[43] Tóth, G., Point sets with many \(k\)-sets, Discrete Comput. Geom., 26, 187-194 (2001) · Zbl 0988.52028
[44] G.T. Toussaint, Solving geometric problems with the rotating calipers, in: Proc. IEEE MELECON’83, Athens, Greece, 1983, A10.02/1-4.; G.T. Toussaint, Solving geometric problems with the rotating calipers, in: Proc. IEEE MELECON’83, Athens, Greece, 1983, A10.02/1-4.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.