Prototype selection for dissimilarity-based classifiers

Elzbieta Pekalska, Elzbieta Pȩkalska, Robert P W Duin, Pavel Paclík

    Research output: Contribution to journalArticlepeer-review


    A conventional way to discriminate between objects represented by dissimilarities is the nearest neighbor method. A more efficient and sometimes a more accurate solution is offered by other dissimilarity-based classifiers. They construct a decision rule based on the entire training set, but they need just a small set of prototypes, the so-called representation set, as a reference for classifying new objects. Such alternative approaches may be especially advantageous for non-Euclidean or even non-metric dissimilarities. The choice of a proper representation set for dissimilarity-based classifiers is not yet fully investigated. It appears that a random selection may work well. In this paper, a number of experiments has been conducted on various metric and non-metric dissimilarity representations and prototype selection methods. Several procedures, like traditional feature selection methods (here effectively searching for prototypes), mode seeking and linear programming are compared to the random selection. In general, we find out that systematic approaches lead to better results than the random selection, especially for a small number of prototypes. Although there is no single winner as it depends on data characteristics, the k-centres works well, in general. For two-class problems, an important observation is that our dissimilarity-based discrimination functions relying on significantly reduced prototype sets (3-10% of the training objects) offer a similar or much better classification accuracy than the best k-NN rule on the entire training set. This may be reached for multi-class data as well, however such problems are more difficult. © 2005 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.
    Original languageEnglish
    Pages (from-to)189-208
    Number of pages19
    JournalPattern Recognition
    Issue number2
    Publication statusPublished - Feb 2006


    • Dissimilarity
    • Nearest neighbor rule
    • Normal density based classifiers
    • Prototype selection
    • Representation


    Dive into the research topics of 'Prototype selection for dissimilarity-based classifiers'. Together they form a unique fingerprint.

    Cite this