| Peer-Reviewed

Necessary and Sufficient Conditions of ε-Separability

Received: 13 September 2016     Accepted: 28 October 2016     Published: 21 November 2016
Views:       Downloads:
Abstract

In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.

Published in International Journal of Theoretical and Applied Mathematics (Volume 2, Issue 2)
DOI 10.11648/j.ijtam.20160202.11
Page(s) 28-34
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

ε-nets, Separability, Quasiconvexity

References
[1] Haussler D. and Welzl E. “Epsilon-nets and simplex range queries”, Discrete Comput. Geom., 1987, №2, p.p. 127–151.
[2] 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.
[3] Gärtner B., Hoffmann M. Computational Geometry, http://www.ti.inf.ethz.ch/ew/lehre/CG12/lecture/CG%20lecture%20notes.pdf.
[4] Hausler S. VC Dimension. A Tutorial for the Course Computational Intelligence, http://www.igi.tugraz.at/lehre/CI.
[5] Kulkarni J., Govindarajan S. “New -Net Constructions”, Canadian Conference on Computational Geometry (CCCG), 2010, P.P.159-162.
[6] 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, 1990, P.P. 16–22.
[7] Ivanchuk M.A., Malyk I.V. “Solving the Classification Problem Using ε-nets”, Cybernetics and Systems Analysis, Vol.52, Iss.4 (2016), p.p. 613-622.
[8] M. A. Ivanchuk, I. V. Malyk “Using ε-Nets for Linear Separation of Two Sets in a Euclidean Space R d “ , Cybernetics and Systems Analysis, Vol.51, Iss.6, 2015, P.P. 965-968. - DOI 10.1007/s10559-015-9789-7.
[9] Embrechts P., Hofert M. “A note on generalized inverses”, Mathematical Methods of Operations Research , 2013, 77(3), 423-432.
[10] Boyd S., Vandenberghe L. Convex Optimization, Cambridge University Press, 2009, 716 p.
Cite This Article
  • APA Style

    Maria A. Ivanchuk, Igor V. Malyk. (2016). Necessary and Sufficient Conditions of ε-Separability. International Journal of Theoretical and Applied Mathematics, 2(2), 28-34. https://doi.org/10.11648/j.ijtam.20160202.11

    Copy | Download

    ACS Style

    Maria A. Ivanchuk; Igor V. Malyk. Necessary and Sufficient Conditions of ε-Separability. Int. J. Theor. Appl. Math. 2016, 2(2), 28-34. doi: 10.11648/j.ijtam.20160202.11

    Copy | Download

    AMA Style

    Maria A. Ivanchuk, Igor V. Malyk. Necessary and Sufficient Conditions of ε-Separability. Int J Theor Appl Math. 2016;2(2):28-34. doi: 10.11648/j.ijtam.20160202.11

    Copy | Download

  • @article{10.11648/j.ijtam.20160202.11,
      author = {Maria A. Ivanchuk and Igor V. Malyk},
      title = {Necessary and Sufficient Conditions of ε-Separability},
      journal = {International Journal of Theoretical and Applied Mathematics},
      volume = {2},
      number = {2},
      pages = {28-34},
      doi = {10.11648/j.ijtam.20160202.11},
      url = {https://doi.org/10.11648/j.ijtam.20160202.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtam.20160202.11},
      abstract = {In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.},
     year = {2016}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Necessary and Sufficient Conditions of ε-Separability
    AU  - Maria A. Ivanchuk
    AU  - Igor V. Malyk
    Y1  - 2016/11/21
    PY  - 2016
    N1  - https://doi.org/10.11648/j.ijtam.20160202.11
    DO  - 10.11648/j.ijtam.20160202.11
    T2  - International Journal of Theoretical and Applied Mathematics
    JF  - International Journal of Theoretical and Applied Mathematics
    JO  - International Journal of Theoretical and Applied Mathematics
    SP  - 28
    EP  - 34
    PB  - Science Publishing Group
    SN  - 2575-5080
    UR  - https://doi.org/10.11648/j.ijtam.20160202.11
    AB  - In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.
    VL  - 2
    IS  - 2
    ER  - 

    Copy | Download

Author Information
  • Department of Biological Physics and Medical Informatics, Bucovinian State Medical University, Chernivtsi, Ukraine

  • Department of the System and Analysis and Insurance Financial Mathematics, Yuriy Fedkovych Chernivtsi National University, Chernivtsi, Ukraine

  • Sections