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.
Alexandre L. M. Levada (Tue,) studied this question.