Graph-Based Nearest Centroid for Image Classification

Alexandre L. M. Levada

doi:10.22456/2175-2745.150723

Authors

Alexandre L. M. Levada Universidade Federal de São Carlos (UFSCar)

DOI:

https://doi.org/10.22456/2175-2745.150723

Keywords:

image classification, nearest centroid classifier, graph-based learning, geodesic distances

Abstract

Image classification is a fundamental task for pattern recognition and computer vision. Many different classifiers have been proposed to overcome the limitations of supervised learning in practical problems. Despite all the efforts, due to the curse of the dimensionality, classifying high-dimensional data still pose a challenge to reasearchers and practitioners from several fields of science. In this paper, we propose a graph-based nearest centroid classifier (Graph-NCC), method for supervised classification that builds a discrete approximation to the data manifold and employs shortest paths to approximate the geodesic distances between sample points. An analysis of the complexity reveals that Graph-NCC is log-linear in the number of samples and linear in the number of edges, showing that the method is quite efficient in comparison to modern supervised classification techniques. We performed computational experiments with real image datasets to demonstrate the effectiveness of Graph-NCC. The obtained results show that the proposed Graph-NCC algorithm is capable of improving the balanced accuracy in comparison to the regular nearest neighbor classifier (NCC). In some cases, the proposed method also overperforms classical machine learning methods, as support vector machines (SVM), k-nearest neighbors classifier (k-NN) and XGBoost.

Downloads

Download data is not yet available.

References

[1] DUDA, R. O.; HART, P. E.; STORK, D. G. Pattern Classification. 2. ed. New York: Wiley, 2001.

[2] THEODORIDIS, S.; KOUTROUMBAS, K. Pattern Recognition. London: Academic Press, 2009.

[3] JAMES, G. et al. An Introduction to Statistical Learning with Applications in Python. Cham: Springer, 2023. (Springer Texts in Statistics).

[4] WEBB, A. R.; COPSEY, K. D. Statistical Pattern Recognition. London: John Wiley & Sons, 2011.

[5] BRAGA-NETO, U. Fundamentals of Pattern Recognition and Machine Learning. Switzerland: Springer, 2020.

[6] NARAYANAN, U. et al. A survey on various supervised classification algorithms. In: 2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS). [S.l.: s.n.], 2017. p. 2118–2124.

[7] SEN, P. C.; HAJRA, M.; GHOSH, M. Supervised classification algorithms in machine learning: A survey and review. In: MANDAL, J. K.; BHATTACHARYA, D. (Ed.). Emerging Technology in Modelling and Graphics. Singapore: Springer Singapore, 2020. p. 99–111.

[8] MRABET, M. A. E.; MAKKAOUI, K. E.; FAIZE, A. Supervised machine learning: A survey. In: 2021 4th International Conference on Advanced Communication Technologies and Networking (CommNet). [S.l.: s.n.], 2021. p. 1–10.

[9] TIBSHIRANI, R. et al. Diagnosis of multiple cancer types by shrunken centroids of gene expression. Proceedings of the National Academy of Sciences, v. 99, n. 10, p. 6567–6572, 2002.

[10] BAWONO, A. H.; BAHTIAR, F. A.; SUPIANTO, A. A. Nearest centroid classifier with outlier removal for classification. Journal of Information Technology and Computer Science, v. 5, n. 1, p. 57–64, Feb. 2020.

[11] BEYER, K. et al. When is nearest neighbor meaningful? In: Proceedings of the 7th International Conference on Database Theory. Jerusalem, Israel: Springer, 1999. (ICDT ’99), p. 217–235.

[12] AGGARWAL, C. C.; HINNEBURG, A.; KEIM, D. A. On the surprising behavior of distance metrics in high dimensional space. In: Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2001. v. 1973, p. 420–434.

[13] CORMEN, T. H. et al. Introduction to Algorithms. 4th. ed. New York, NY, USA: The MIT Press, 2022. ISBN 9780262046305.

[14] GORBAN, A. N.; TYUKIN, I. Y. Blessing of dimensionality: Mathematical foundations of the statistical physics of data. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, Royal Society, v. 376, n. 2118, p. 20170237, 2018.

[15] FEFFERMAN, C.; MITTER, S.; NARAYANAN, H. Testing the manifold hypothesis. Journal of the American Mathematical Society, American Mathematical Society, v. 29, n. 4, p. 983–1049, 2016.

[16] SILVA, V.; TENENBAUM, J. Global versus local methods in nonlinear dimensionality reduction. In: BECKER, S.; THRUN, S.; OBERMAYER, K. (Ed.). Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2002. v. 15.

[17] SILVA, V. de; TENENBAUM, J. B. Global versus local methods in nonlinear dimensionality reduction. In: BECKER, S.; THRUN, S.; OBERMAYER, K. (Ed.). Advances in Neural Information Processing Systems 15. Cambridge, MA, USA: MIT Press, 2003. p. 721–728. Proceedings of the 16th International Conference on Neural Information Processing Systems (NIPS 2002). Disponível em: https://papers.nips.cc/paper/2002/hash/6150ccc62edbce3142a5da63cc42e5e7-Abstract.html.

[18] PEDREGOSA, F. et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, v. 12, p. 2825–2830, 2011. Disponível em: http://jmlr.org/papers/v12/pedregosa11a.html.

[19] ALPAYDIN, E.; ALIMOGLU, F. Pen-Based Recognition of Handwritten Digits. 1996. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5MG6K.

[20] JAIN, A. K.; DUIN, R. P. W.; MAO, J. Statistical pattern recognition: A review. IEEE Computer Society, USA, v. 22, n. 1, p. 4–37, 2000.

[21] ALPAYDIN, E.; KAYNAK, C. Cascading classifiers. Kybernetika, Institute of Information Theory and Automation AS CR, v. 34, n. 4, p. [369]–374, 1998.

[22] SRINIVASAN, A. Statlog (Landsat Satellite). 1993. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C55887.

[23] BRODATZ, P. Textures: A Photographic Album for Artists and Designers. 1966. Dover, New York.

[24] LINSEN, M. K. L. (Ed.). Plant Leaf Classification using Probabilistic Integration of Shape, Texture and Margin Features, v. 798 de 098, (098, v. 798). [S.l.]: ACTA Press, 2013.

[25] THE ORL Database of Faces. 2002. AT&T Laboratories, Cambridge. Disponível em: https://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html.