Skip to main content
SpringerLink
Log in

Lightweight Nearest Convex Hull Classifier

  • MATHEMATICAL METHOD IN PATTERN RECOGNITION
  • Published:
Pattern Recognition and Image Analysis Aims and scope Submit manuscript

Abstract—

A new type of classifier, the lightweight nearest convex hull (LNCH) classifier, is proposed. It is called lightweight due to the simplicity of its algorithm. It is based on a new method for estimating the proximity of the test point to the convex hull of a class in the case when the test point intersects convex hulls of the classes. The concept of the penetration depth of a point into a convex hull is used. Proximity is determined based on the analysis of extreme points projected on the direction vector from this point to the centroid of the class. A decision rule for multiclass problems is derived for the LNCH classifier using a new method for estimating the proximity. The results of experimental studies on synthesized numerical data and on real data for breast cancer diagnosis are given. The results indicate higher recognition accuracy of the LNCH classifier compared to other types of classifiers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1.
Fig. 2.
Fig. 3.

Similar content being viewed by others

REFERENCES

  1. G. Nalbantov and E. Smirnov, “Soft nearest convex hull classifier,” in Proc. 19th European Conf. on Artificial Intelligence (ECAI-2010), Ed. by H. Coelho, R. Studer, and M. Wooldridge (IOS Press, Amsterdam, 2010), pp. 841–846. https://doi.org/10.3233/978-1-60750-606-5-841

  2. X. Zhou and Y. Shi, “Nearest neighbor convex hull classification method for face recognition,” in Computational Science — ICCS 2009, Part II, Ed. by G. Allen, J. Nabrzyski, E. Seidel, , Lecture Notes in Computer Science (Springer, Berlin, 2009), Vol. 5545, pp. 570–577.

    Google Scholar 

  3. J. Qing, H. Huo, and T. Fang, “Nearest convex hull classifiers for remote sensing classification,” Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci. XXXVII (Part B7), 589–594 (2008).

    Google Scholar 

  4. V. N. Vapnik, The Nature of Statistical Learning Theory, 2nd ed. (Springer, New York, 2000).

    Book  MATH  Google Scholar 

  5. R. Weller, New Geometric Data Structures for Collision Detection and Haptics, in Springer Series on Touch and Haptic Systems (Springer, Cham, 2013). https://doi.org/10.1007/978-3-319-01020-5

    Google Scholar 

  6. M. C. Lin, D. Manocha, and Y. J. Kim, “Collision and proximity queries”, in Handbook of Discrete and Computational Geometry, 3rd ed., Ed. by J. E. Goodman, J. O’Rourke, and C. D. Tóth (CRC Press, Boca Raton, FL, 2018), pp. 1029–1056.

    Google Scholar 

  7. S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, and K. R. K. Murthy, Improvements to Platt’s SMO Algorithm for SVM Classifier Design, Technical Report CD-99-14 (Control Division, Dept. of Mechanical and Production Engineering, National University of Singapore, 1999).

  8. Breast Cancer Wisconsin (Original) Data Set, UCI Machine Learning Repository. https://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+(original)

  9. A. P. Nemirko, “Multidimensional data visualization based on the minimum distance between convex hulls of classes,” Pattern Recogn. Image Anal. 28 (4), 712–719 (2018). https://doi.org/10.1134/S1054661818040247

    Article  Google Scholar 

  10. C. J. C. Burges, “A tutorial on Support Vector Machines for pattern recognition,” Data Mining Knowl. Discovery 2 (2), 121–167 (1998).

    Article  Google Scholar 

  11. K. P. Bennett and E. J. Bredensteiner, “Duality and geometry in SVM classifiers,” in Proc. 17th Int. Conf. on Machine Learning (ICML’00) (Morgan Kaufmann, San Francisco, 2000), pp. 57–64.

Download references

Funding

This study was supported in part by the Russian Foundation for Basic Research, project nos. 18-07-00264 and 18-29-02036.

Author information

Authors and Affiliations

  1. St. Petersburg Electrotechnical University LETI, St. Petersburg, Russia

    A. P. Nemirko

Authors
  1. A. P. Nemirko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. P. Nemirko.

Ethics declarations

The author declares that he has no conflicts of interest.

Additional information

Anatolii Pavlovich Nemirko. Graduated from St. Petersburg Electrotechnical University LETI in 1967. Since 1986, has worked as a professor at the Department of Bioengineering Systems at the same university. Received doctoral degree in 1986 and professor degree in 1988. Scientific interests: pattern recognition, processing and analysis of biomedical signals, intelligent biomedical systems. Author of more than 300 scientific publications including 90 papers and five monographs. Board member of the International Association of Pattern Recognition and member of the editorial board of the Pattern Recognition and Image Analysis.

Translated by O. Pismenov

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nemirko, A.P. Lightweight Nearest Convex Hull Classifier. Pattern Recognit. Image Anal. 29, 360–365 (2019). https://doi.org/10.1134/S1054661819030167

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S1054661819030167

Keywords:

Search

Navigation