Discriminant error correcting output codes based on spectral clustering | Pattern Analysis and Applications Skip to main content
Springer Nature Link
Log in

Discriminant error correcting output codes based on spectral clustering

  • Theoretical Advances
  • Published:
Pattern Analysis and Applications Aims and scope Submit manuscript

Abstract

Error correcting output codes (ECOCs) is a powerful framework to solve the multi-class problems. Finding the optimal partitions with maximum class discrimination efficiently is a key point to improve its performance. In this paper, we propose an alternative and efficient approach to obtain the partitions which are discriminative in the class space. The main idea of the proposed method is to transform the partition in the class space into the cut for an undirected graph using spectral clustering. In addition to measuring the class similarity, the confusion matrix with a pre-classifier is used. Our method is compared with the classical ECOC and DECOC over a synthetic dataset, a set of UCI machine learning repository datasets and one face recognition application. The results show that our proposal is able to obtain comparable or even better classification accuracy while reducing the computational complexity in comparison with the state-of-the-art coding methods.

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

References

  1. Mathias M, Timofte R, Benenson R, Gool LV (2013) Traffic sign recognition—how far are we from the solution? International joint conference on neural networks (IJCNN), ESAT-PSI/iMinds, University of Leuven, Leuven, Belgium, pp 1–8

  2. Dehzangi O, Ma B, Chng ES, Li H (2012) Discriminative feature extraction for speech recognition using continuous output codes. Pattern Recogn Lett 33:1703–1709

    Article  Google Scholar 

  3. Windeatt T, Ardeshir G (2003) Boosted ECOC ensembles for face recognition. Pattern Recogn 35(4):165–168

    Google Scholar 

  4. Yu J, Rui Y, Tang YY, Tao D (2014) High-order distance-based multiview stochastic learning in image classification. IEEE Trans Cybern 44(12):2431–2442. doi:10.1109/TCYB.2014.2307862

    Article  Google Scholar 

  5. Yu J, Rui Y, Chen B (2014) Exploiting click constraints and multi-view features for image re-ranking. IEEE Trans Multimed 16(1):159–168. doi:10.1109/TMM.2013.2284755

    Article  Google Scholar 

  6. Yu J, Rui Y, Tao D (2014) Click prediction for web image reranking using multimodal sparse coding. IEEE Trans Image Process 23(5):2019–2032. doi:10.1109/TIP.2014.2311377

    Article  MathSciNet  Google Scholar 

  7. Tao D, Lin X, Jin L, Li X (2015) Principal component 2-D long short-term memory for font recognition on single Chinese characters. IEEE Trans Cybern. doi:10.1109/TCYB.2015.2414920

    Google Scholar 

  8. Tao D, Li X, Wu X, Maybank SJ (2007) General tensor discriminant analysis and gabor features for gait recognition. IEEE Trans Pattern Anal Mach Intell 29(10):1700–1715. doi:10.1109/TPAMI.2007.1096

    Article  Google Scholar 

  9. Anand R, Mehrotra K, Mohan CK, Ranka S (1995) Efficient classification for multiclass problems using modular neural networks. IEEE Trans Neural Netw 6(1):117–124

    Article  Google Scholar 

  10. Clark P, Boswell R (1991) Rule induction with CN2: Some recent improvements. In: Kodratoff Y (ed) Machine LEARNING—EWSL-91, vol 482., Lecture Notes in Computer ScienceSpringer, Berlin, pp 151–163

    Chapter  Google Scholar 

  11. Dietterich T, Bakiri G (1995) Solving multiclass learning problems via error-correcting output codes. J Artif Intell Res 2(1):263–268

    MATH  Google Scholar 

  12. Pujol O, Radeva P, Vitria J (2006) Discriminant ECOC: a heuristic method for application dependent design of error correcting output codes. IEEE Trans Pattern Anal Mach Intell 28(6):1007–1012

    Article  Google Scholar 

  13. Escalera S, Tax DMJ, Pujol O, Radeva P, Duin RPW (2008) Subclass problem-dependent design for error-correcting output codes. IEEE Trans Pattern Anal Mach Intell 30(6):1041–1053. doi:10.1109/TPAMI.2008.38

    Article  Google Scholar 

  14. Ali-Bagheri M, Ali-Montazer G, Kabir E (2013) A subspace approach to error correcting output codes. Pattern Recogn Lett 34:176–184

    Article  Google Scholar 

  15. Angel-Bautista M, Escalera S, Baro X, Pujol O (2014) On the design of an ECOC-Compliant Genetic Algorithm. Pattern Recogn 47:865–884

    Article  Google Scholar 

  16. Crammer K, Singer Y (2002) On the learnability and design of output codes for multiclass problems. Mach Learn 47:201–233

    Article  MATH  Google Scholar 

  17. Masulli F, Valentini G (2003) Effectiveness of error correcting output coding methods in ensemble and monolithic learning machines. Pattern Anal Appl 6:285–300. doi:10.1007/s10044-003-195-9

    Article  MathSciNet  Google Scholar 

  18. Garcia-Pedrajas N, Fyfe C (2008) Evolving output codes for multiclass problems. IEEE Trans Evol Comput 12(1):93–106. doi:10.1109/TEVC.2007.894201

    Article  Google Scholar 

  19. Ali-Bagheri M, Gao Q, Escalera S (2013) A genetic-based subspace analysis method for improving error-correcting output coding. Pattern Recogn 46:2830–2839

    Article  Google Scholar 

  20. Valentini G (2000) Upper bounds on the training error of ECOC SVM ensembles. Technical Report DISI-TR-00-17, Dipartimento di Informatica e Science dell’ Informazione, Universita di Genova

  21. Kong E, Dietterich TG (1995) Error-correcting output coding correct bias and variance. In: The XII international conference on machine learning, San Francisco, CA, pp. 313–321

  22. Zhang X, Liang L, Shum HY (2009) Spectral error correcting output codes for efficient multiclass recognition. In: IEEE 12th international conference on computer vision (ICCV)

  23. Duda RO, Hart PE, Stork DG (2001) Pattern classification. Wiley, New York

    MATH  Google Scholar 

  24. Luxburg UV (2007) A tutorial on spectral clustering. Stat Comput 17(4):395–416. doi:10.1007/s11222-007-9033-z

    Article  MathSciNet  Google Scholar 

  25. Wang X, Yao X, Zhou J (2012) An approach of constructing ECOC adaptively based on confusion matrix. In: 2nd international conference on computer science and network technology, ChangChun, China

  26. Asuncion A, Newman D (2007) UCI machine learning repository. University of California, Irvine, School of Information and Computer Sciences

    Google Scholar 

  27. Samaria F, Harter A (1994) Parameterization of a stochastic model for human face identification. In: IEEE workshop on applications of computer vision. Sarasota (Florida)

  28. Escalera S, Pujol O, Radeva P (2010) ECOCs library. J Mach Learn Res 11:661–664

    Google Scholar 

  29. Griffin P, Holub G, Perona AD The Caltech 256, Caltech Technical Report. http://www.vision.caltech.edu/Image_Datasets/Caltech256

  30. The ImageNet. http://www.image-net.org

  31. Demsar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30

    MathSciNet  MATH  Google Scholar 

  32. Weiss GM, Provost F (2003) Learning when training data are costly: the effect of class distribution on tree induction. J Artif Intell Res 19:315–354

    MATH  Google Scholar 

  33. Duin RPW, Juszczak P, Paclik P, Pekalska E, de Ridder D, Tax DMJ, Verzakov S (2007) PRTools4.1, a matlab toolbox for pattern recognition. Delft University of Technology

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Air Force Engineering University, Changle East Road, Xi’an, 710051, China

    Aijun Xue, Xiaodan Wang, Yafei Song & Lei Lei

Authors
  1. Aijun Xue
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Xiaodan Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Yafei Song
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Lei Lei
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Aijun Xue.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xue, A., Wang, X., Song, Y. et al. Discriminant error correcting output codes based on spectral clustering. Pattern Anal Applic 20, 653–671 (2017). https://doi.org/10.1007/s10044-015-0523-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10044-015-0523-x

Keywords