Graphics Reference
In-Depth Information
8.3.1.4 Criteria to Compare Prototype Selection Methods
When comparing PS methods, there are a number of criteria that can be used to
evaluate the relative strengths and weaknesses of each algorithm. These include
storage reduction, noise tolerance, generalization accuracy and time requirements.
•
Storage reduction:
One of the main goals of the PS methods is to reduce storage
requirements. Furthermore, another goal closely related to this is to speed up
classification. A reduction in the number of stored instances will typically yield a
corresponding reduction in the time it takes to search through these examples and
classify a new input vector.
•
Noise tolerance:
Two main problems may occur in the presence of noise. The first
is that very few instances will be removed because many instances are needed to
maintain the noisy decision boundaries. Secondly, the generalization accuracy can
suffer, especially if noisy instances are retained instead of good instances.
•
Generalization accuracy:
A successful algorithm will often be able to significantly
reduce the size of the training set without significantly reducing generalization
accuracy.
•
Time requirements:
Usually, the learning process is done just once on a training
set, so it seems not to be a very important evaluation method. However, if the
learning phase takes too long it can become impractical for real applications.
8.3.2 Prototype Selection Methods
Almost 100 PS methods have been proposed in the literature. This section is devoted
to enumerating and designating them according to a standard followed in this chapter.
For more details on their descriptions and implementations, the reader can read the
next section of this chapter. Implementations of some of the algorithms in Java can
be found in KEEL software [
3
,
4
], described in Chap.
10
of this topic.
Table
8.1
presents an enumeration of PS methods reviewed in this chapter. The
complete name, abbreviation and reference are provided for each one. In the case of
there being more than one method in a row, they were proposed together and the best
performing method (indicated by the respective authors) is depicted in bold.
8.3.3 Taxonomy of Prototype Selection Methods
The properties studied above can be used to categorize the PS methods proposed
in the literature. The direction of the search, type of selection and evaluation of
the search may differ among PS methods and constitute a set of properties which
are exclusive to the way of operating of the PS methods. This section presents the
taxonomy of PS methods based on these properties.
