Isaac Scientific Publishing
Journal of Advances in Applied Mathematics
JAAM > Volume 2, Number 1, January 2017

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

Download PDF  (1092.3 KB)PP. 43-54,  Pub. Date:January 12, 2017
DOI: 10.22606/jaam.2017.21004

Author(s)
Maria A. Ivanchuk, Igor V. Malyk
Affiliation(s)
Department of Biological Physics and Medical Informatics, Bukovinian State Medical University, Ukraine; 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 (Rd ,Hd ) 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
Copyright © 2017 Isaac Scientific Publishing Co. All rights reserved.