Nature-inspired optimum-path forest | Evolutionary Intelligence Skip to main content
Springer Nature Link
Log in

Nature-inspired optimum-path forest

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

Abstract

The Optimum-Path Forest (OPF) is a graph-based classifier that models pattern recognition problems as a graph partitioning task. The OPF learning process is performed in a competitive fashion where a few key samples (i.e., prototypes) try to conquer the remaining training samples to build optimum-path trees (OPT). The task of selecting prototypes is paramount to obtain high-quality OPTs, thus being of great importance to the classifier. The most used approach computes a minimum spanning tree over the training set and promotes the samples nearby the decision boundary as prototypes. Although such methodology has obtained promising results in the past year, it can be prone to overfitting. In this work, it is proposed a metaheuristic-based approach (OPFmh) for the selection of prototypes, being such a task modeled as an optimization problem whose goal is to improve accuracy. The experimental results showed the OPFmh can reduce overfitting, as well as the number of prototypes in many situations. Moreover, OPFmh achieved competitive accuracies and outperformed OPF in the experimental scenarios.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. https://github.com/gugarosa/opytimizer/

  2. https://github.com/jppbsi/LibOPF

  3. We used the standard values proposed by their authors.

  4. https://archive.ics.uci.edu/ml/datasets.html

References

  1. Allène C, Audibert JY, Couprie M, Keriven R (2010) Some links between extremum spanning forests, watersheds and min-cuts. Image Vis Comput 28(10):1460–1471

    Article  Google Scholar 

  2. Bishop C (1995) Neural networks for pattern recognition. Oxford University Press, Oxford

    MATH  Google Scholar 

  3. Chapelle O, Schlkopf B, Zien A (2010) Semi-supervised learning, 1st edn. The MIT Press, London

    Google Scholar 

  4. Cortes C, Vapnik V (1995) Support vector networks. Mach Learn 20:273–297

    Article  MATH  Google Scholar 

  5. Cristianini N, Shawe-Taylor J (2000) An introduction to support vector machines and other kernel-based learning methods. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  6. Falcão A, Stolfi J, Lotufo R (2004) The image foresting transform: theory, algorithms, and applications. IEEE Trans Pattern Anal Mach Intell 26(1):19–29

    Article  Google Scholar 

  7. Geem ZW (2009) Music-inspired harmony search algorithm: theory and applications, 1st edn. Springer, Berlin

    Book  Google Scholar 

  8. Hatamlou A (2013) Black hole: a new heuristic optimization approach for data clustering. Inf Sci 222:175–184

    Article  Google Scholar 

  9. Haykin S (2007) Neural networks: a comprehensive foundation, 3rd edn. Prentice-Hall Inc, Upper Saddle River

    MATH  Google Scholar 

  10. Hayyolalam V, Pourhaji Kazem AA (2020) Black widow optimization algorithm: a novel meta-heuristic approach for solving engineering optimization problems. Eng Appl Artif Intell 87:103249

    Article  Google Scholar 

  11. Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology. Control and artificial intelligence. MIT Press, Cambridge

    Book  Google Scholar 

  12. Iwashita AS, Papa JP, Souza AN, Falcão AX, Lotufo RA, Oliveira VM, de Albuquerque VHC, Tavares JMRS (2014) A path- and label-cost propagation approach to speedup the training of the optimum-path forest classifier. Pattern Recogn Lett 40:121–127

    Article  Google Scholar 

  13. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Global Optim 39(3):459–471

    Article  MATH  Google Scholar 

  14. Papa JP, Falcão AX, Albuquerque VHC, Tavares JMRS (2012) Efficient supervised optimum-path forest classification for large datasets. Pattern Recogn 45(1):512–520

    Article  Google Scholar 

  15. Papa JP, Falcão AX, Suzuki CTN (2009) Supervised pattern classification based on optimum-path forest. Int J Imaging Syst Technol 19(2):120–131

    Article  Google Scholar 

  16. Papa JP, Fernandes SEN, Falcão AX (2017) Optimum-path forest based on k-connectivity: theory and applications. Pattern Recogn Lett 87:117–126

    Article  Google Scholar 

  17. Papa JP, Suzuki CTN, X A (2014) LibOPF: a library for the design of optimum-path forest classifiers . Software version 2.1 Available at http://www.ic.unicamp.br/ afalcao/libopf/index.html

  18. Ponti M, Riva M (2017) An incremental linear-time learning algorithm for the optimum-path forest classifier. Inf Process Lett 126:1–6

    Article  MATH  Google Scholar 

  19. Połap D, Woźniak M (2021) Red fox optimization algorithm. Expert Syst Appl 166:114107

    Article  Google Scholar 

  20. Quinlan JR (1986) Induction of decision trees. Mach Learn 1(1):81–106

    Article  Google Scholar 

  21. Rocha LM, Cappabianco FAM, Falcão AX (2009) Data clustering as an optimum-path forest problem with applications in image analysis. Int J Imaging Syst Technol 19(2):50–68

    Article  Google Scholar 

  22. Rodrigues D, Pereira LAM, Nakamura RYM, Costa KAP, Yang XS, Souza AN, Papa JP (2014) A wrapper approach for feature selection based on bat algorithm and optimum-path forest. Expert Syst Appl 41(5):2250–2258

    Article  Google Scholar 

  23. Rokach L, Maimon O (2005) Top-down induction of decision trees classifiers-a survey. Trans Syst Man Cyber Part C 35(4):476–487

    Article  Google Scholar 

  24. Gustavo H, de Rosa DR, Papa JP (2019) Opytimizer: a nature-inspired python optimizer

  25. Sliii KPFR (1901) On lines and planes of closest fit to systems of points in space. London Edinburgh Dublin Philos Mag J Sci 2(11):559–572

    Article  Google Scholar 

  26. Shi Y (2011) An optimization algorithm based on brainstorming process. Int J Swarm Intell Res 2:35–62

    Article  Google Scholar 

  27. Souza R, Rittner L, Lotufo RA (2014) A comparison between k-optimum path forest and k-nearest neighbors supervised classifiers. Pattern Recogn Lett 39:2–10

    Article  Google Scholar 

  28. Wilcoxon F (1945) Individual comparisons by ranking methods. Biom Bull 1(6):80–83

    Article  Google Scholar 

  29. Yang SS, Karamanoglu M, He X (2014) Flower pollination algorithm: a novel approach for multiobjective optimization. Eng Optim 46(9):1222–1237

    Article  Google Scholar 

  30. Yang XS (2021) Chapter 8-particle swarm optimization. In: Yang XS (ed) Nature-inspired optimization algorithms, 2nd edn. Academic Press, London, pp 111–121

    Chapter  Google Scholar 

  31. Yang XS, Deb S (2010) Engineering optimisation by cuckoo search. Int J Math Modell Numer Optim 1:330–343

    MATH  Google Scholar 

  32. Yang XS, Xingshi H (2013) Firefly algorithm: recent advances and applications. Int J Swarm Intell. https://doi.org/10.1504/IJSI.2013.055801

    Article  Google Scholar 

  33. Zhao W, Zhang Z, Wang L (2020) Manta ray foraging optimization: an effective bio-inspired optimizer for engineering applications. Eng Appl Artif Intell 87:103300

    Article  Google Scholar 

Download references

Acknowledgements

The authors are grateful to FAPESP Grants #2013/07375-0, #2014/12236-1, #2017/25908-6, #2018/21934-5, and #2019/07665-4, CNPq Grants #307066/2017-7 and #427968/2018-6. This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.

Author information

Authors and Affiliations

  1. School of Sciences, UNESP - São Paulo State University, Bauru, Brazil

    Luis Claudio Sugi Afonso, Douglas Rodrigues & João Paulo Papa

Authors
  1. Luis Claudio Sugi Afonso
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Douglas Rodrigues
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. João Paulo Papa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Douglas Rodrigues.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Afonso, L.C.S., Rodrigues, D. & Papa, J.P. Nature-inspired optimum-path forest. Evol. Intel. 16, 317–328 (2023). https://doi.org/10.1007/s12065-021-00664-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-021-00664-0

Keywords

Search

Navigation