Journal of Advances in Applied Mathematics

ε-Nets of Two Sets and Their Application to the Classification Problem

Download PDF (1092.3 KB) PP. 43 - 54 Pub. Date: January 1, 2017

DOI: 10.22606/jaam.2017.21004

Author(s)

Maria A. Ivanchuk^*
Department of Biological Physics and Medical Informatics, Bukovinian State Medical University, Ukraine
Igor V. Malyk
Department of the System Analysis and Insurance and Financial Mathematics, Yuriy Fedkovych Chernivtsi National University, Ukraine

Abstract

The separation algorithm of linear two sets using their ε-nets in the range space (R^d ,H^d ) is proposed in the paper. The algorithm is illustrated by two examples for normal and uniform distributions. The set of possible values of ε and its properties are considered in the manuscript.

Keywords

Epsilon-nets, sets’ separation, linear classification

References

[1] Aronov B., Ezra E., Sharir M. “Small-size epsilon-nets for axis-parallel rectangles and boxes”, Symposium on Theory of Computing, 2009, P.P. 639–648

[2] Christopher J.C. Burges “A Tutorial on Support Vector Machines for Pattern Recognition”, Data Mining and Knowledge Discovery, 2(2), 1998, P.121–167.

[3] Embrechts P., Hofert M. A note on generalized inverses Mathematical Methods of Operations Research , 2013, 77(3), 423-432

[4] G?rtner B., Hoffmann M. Computational Geometry, http://www.ti.inf.ethz.ch/ew/lehre/CG12/lecture/CG%20le cture %20notes.pdf

[5] Hausler S. VC Dimension. A Tutorial for the Course Computational Intelligence, http://www.igi.tugraz.at/lehre/ CI

[6] Haussler D. and Welzl E. “Epsilon-nets and simplex range queries”, Discrete Comput. Geom., 1987, №2, P.P. 127–151

[7] Ivanchuk M. A. , Malyk I. V. “ Using ε -Nets for Linear Separation of Two Sets in a Euclidean Space Rd”, Cybernetics and Systems Analysis, Vol.51, Issue 6 (2015), P. 965-968.

[8] Ivanchuk Maria A., Malyk Igor V. “Building expert medical prognostic systems using Voronoi diagram”, Hindawi Publishing Corporation. - International Journal of Computational Mathematics, Volume 2015, Article ID 415146, 4 pages. – DOI 10.1155/2015/415146

[9] Ivanchuk Mariya A., Malyk Igor V. “Separation of convex hulls as a way for modeling of systems of prediction of complications in patients”, Journal of Automation and Information Sciences, 2015, Vol.47, Issue 4, P.78-84, DOI: 10.1615/JAutomatInfScien.v47.i4.80

[10] Kulkarni J., Govindarajan S. “New ε-Net Constructions”, Canadian Conference on Computational Geometry (CCCG), 2010, P.P.159-162

[11] Matousek J., Seidel R., Welzl E. “How to Net a Lot with Little:Small ε-Nets for Disks and Halfspaces” In Proc. sixth annual symposium on Computational geometry, P.P. 16–22, 1990

[12] Tucker H.G. “A Generalization of the Glivenko-Cantelli Theorem”, The Annals of Mathematical Statistics, Vol. 30, No. 3, Sep., 1959, pp. 828-830