Instance Selection Using Evolutionary Algorithms: An Experimental Study - Advanced Techniques in Knowledge Discovery and Data Mining - page 135

different class from P.A i and P.A i .N k+1 is the same class as P.A i , the removal of P
could cause a previously misclassified instance to be classified correctly.
In essence, this rule tests to see if removing P would degrade leave-one-out
cross-validation generalization accuracy, which is an estimate of the true
generalization ability of the resulting classifier.
5.3.3.2 Decremental Reduction Optimization Procedure 2 (DROP2) [39]
DROP2 resolves the problem of noisy instances that affects DROP1. It solves this
problem by considering the effect of the removal of an instance on all the
instances in the original training set T instead of considering only those instances
remaining in S . In other words, an instance P is removed from S only if at least as
many of its associates - including those that may have already been removed from
S - are classified correctly without it.
Thus, the removal criterion can be restated as:
Remove P if at least as many of its associates in T would be classified correctly
without P .
DROP2 also changes the order of removal of instances. It initially sorts the
instances in S by the distance to their nearest enemy. Instances are then checked
for removal beginning at the instance furthest from its nearest enemy. This tends
to remove instances furthest from the decision boundary first, which in turn
increases the chance of retaining border points.
5.3.3.3 Decremental Reduction Optimization Procedure 3 (DROP3) [39]
DROP2 has one problem. Noisy instances are also “border” points and cause the
order of removal to be drastically changed. One noisy point in the center of a
cluster causes many points in that cluster to be considered border points, and some
of these can remain in S even after the noisy point is removed. DROP3 uses a
noise-filtering pass before sorting the instances in S . This is done using the rule:
Any instance misclassified by its k nearest neighbors is removed.
There are DROP4 and DROP5 algorithms but they offer minimal variations
from DROP3.
5.4 Evolutionary Algorithms
EAs [2], [3], [13] are stochastic search methods that mimic the metaphor of
natural biological evolution. All EAs rely on the concept of a population of
individuals (representing search points in the space of potential solutions to a
given problem), which undergo probabilistic operators such as mutation , selection ,