Database Reference
In-Depth Information
5.3.2 Instance-Based Learning Algorithms
Instance-based learning techniques essentially work by keeping typical attribute
examples for each class.
5.3.2.1 Model Class Selection (MCS) [7]
The idea of this algorithm is to keep track of how many times each instance was
one of the
k
nearest neighbors of another instance and whether its class matched
that of the instance being classified. If the number of times it was wrong is greater
than the number of times it was correct, then it is thrown out.
5.3.2.2 Shrink Algorithm [20]
Kibbler and Aha presented an algorithm that starts with
S
=
T
and then removes
any instances that would still be classified correctly by the remaining subset. This
is similar to the reduced nearest neighbor (RNN) rule, except that it only considers
whether the removed instance would be classified correctly, whereas RNN
considers whether the classification of other instances would be affected by the
instance's removal. Like RNN and many of the other algorithms, it retains border
points, but unlike RNN, this algorithm is sensitive to noise.
5.3.3 Ordered Removal
This section presents a collection of new heuristics used to decide which instances
to keep and which instances to remove from a training set. Unlike most previous
methods, these algorithms take careful note of the order in which instances are
removed. The first three methods, DROP1-3, were previously introduced by the
authors under the name RT1-3, respectively.
5.3.3.1 Decremental Reduction Optimization Procedure 1 (DROP1) [39]
DROP1 uses the following basic rule to decide if it is safe to remove an instance
from the instance set (where
S
=
T
originally):
Remove
P
if at least as many of its associates in
S
would be classified correctly
without
P
.
To see if an instance
P
can be removed using this rule, each associate (each
instance that has
P
as one of its neighbors) is checked to see what effect the
removal of
P
would have on it. Removing
P
causes each associate
P.A
i
to use its
k
+ 1 nearest neighbor (
P.A
i
.N
k+1
) in place of
P
. If
P
has the same class as
P.A
i
and
P.A
i
.N
k+1
has different than
P.A
i
, this weakens its classification and could
cause
P.A
i
to be misclassified by its neighbors. On the other hand, if
P
is a
Search WWH ::
Custom Search