查看文章

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 …