University of Bologna

Dipartimento di Elettronica, Informatica e Sistemistica

Publication Database Query

Searched for "ijcnn91:Kov"
Clicking on the number of each publication you can retrieve the bibtex entry. If available, the abstract can be accessed clicking on the title of the work.

A Generalization Technique for Nearest-Neighbor Classifiers

Zs. M. V.-Kovacs and R. Guerrieri


Classifiers based on the k-Nearest neighbors (k-NN) approach have recently received a significant attention because of their simple implementation and absence of training. However, these valuable properties have been somewhat outweighted by the computational cost required to classify a new sample and by the lack of adequate techniques to improve their generalization capabilities, once a training set has been given. This paper addresses these issues and presents a new algorithm which provides nearly optimal generalization capabilities to k-NN classifiers. Its computational cost is a weak function of the dimensionality of the space of the training set and it is not related to any specific formulation of the metric used in the classifier. The asymptotic computational cost of the proposed algorithm is a low-order polynomial of the number of elements in the training set. We also prove that, given a suitable performance measure, each step of the generalization algorithm monotonically improves the performaces of the classifier. Finally, experimental results stemming from the classification of handwritten digits show that the training set provided to the classifier can be reduced by more than one order of magnitude, thus dramatically reducing the CPU time and the memory required to classify new samples.

Microelectronics Group Home Page Staff
Research Activities Teaching Activity
Publications Local Stuff
DEIS Home Page University of Bologna Home Page

External link, Local link, For local sites only, Stiil empty.