Supervised Pattern Classification Based on Optimum-Path Forest

We present a supervised classification method which represents each class by one or more optimum-path trees rooted at some key samples, called prototypes. The training samples are nodes of a complete graph, whose arcs are weighted by the distances between the feature vectors of their nodes. Prototypes are identified in all classes and the minimization of a connectivity function by dynamic programming assigns to each training sample a minimum-cost path from its most strongly connected prototype. This competition among prototypes partitions the graph into an optimum-path forest rooted at them. The class of the samples in an optimum-path tree is assumed to be the same of its root. A test sample is classified similarly, by identifying which tree would contain it, if the sample were part of the training set. By choice of the graph model and connectivity function, one can devise other optimum-path forest classifiers. We present one of them, which is fast, simple, multiclass, parameter independent, does not make any assumption about the shapes of the classes, and can handle some degree of overlapping between classes. We also propose a general algorithm to learn from errors on an evaluation set without increasing the training set, and show the advantages of our method with respect to SVM, ANN-MLP, and k-NN classifiers in several experiments with datasets of various types. (C) 2009 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 19, 120-131, 2009; Published online in Wiley InterScience (www.intersciencewiley.com). DOI 10.1002/ima.20188