Graphics Reference
In-Depth Information
Fig. 8.3
PS taxonomy
8.4 Description of Methods
Algorithms for IS may be classified in three type groups: condensation algorithms,
edition algorithms and hybrids.
8.4.1 Condensation Algorithms
This set includes the techniques which aim to retain the points which are closer to
the decision boundaries, also called border points.
Considering their search direction they can be classified as:
8.4.1.1 Incremental
•
Condensed Nearest Neighbor (CNN)
[
83
]—This algorithm finds a subset
S
of
the training set
TR
such that every member of
TR
is closer to a member of
S
of
the same class than to a member of
S
of a different class. It begins by randomly
selecting one instance belonging to each output class from
TR
and putting them in
S
. Then each instance in
TR
is classified using only the instances in
S
. If an instance
is misclassified, it is added to
S
, thus ensuring that it will be classified correctly.
This process is repeated until there are no instances in
TR
that are misclassified.
This algorithm ensures that all instances in
TR
are classified correctly, though it
does not guarantee a minimal set.