Graphics Reference
In-Depth Information
class, even if they are of a different class than
X
i
. The instance is only removed
if its neighbors are at least 60 % sure of their classification. The VSM method
typically uses a fairly large
k
(i.e.,
k
=
10).
•
Decremental Reduction Optimization Procedure Family (DROP)
[
166
]In
order to present these reduction techniques, we need to define some concepts.
Each instance
X
i
has
k
nearest neighbors where
k
is typically a small odd integer.
X
i
also has a nearest
enemy
, which is the nearest instance with a different output
class. Those instances that have
x
i
as one of their
k
nearest neighbors are called
associates
of
X
i
.
DROP1
-Uses the following basic rule to decide if it is safe to remove an instance from the
instance set S (where
S
=
TR
originally):
Remove
X
i
if at least as many of its associates in
S
would be classified correctly
without
X
i
.
The algorithm
DROP1
proceeds as follows.
DROP1 (Training set
TR
): Selection set
S
.
Let
S
TR
.
For each instance
X
i
in
S
:
Find the
k
=
1
nearest neighbors of
X
i
in
S
.
Add
X
i
to each of its lists of associates.
For each instance
X
i
in
S
:
Let
w
+
#
of associates of
X
i
classified
correctly with
X
i
as a neighbor.
Let
w
ith
=
=
#
of associates of
X
i
classified
correctly without
X
i
.
If
w
ithout
ith
Remove
X
i
from
S
.
For each associate
a
of
X
i
Remove
X
i
from
a
's list of neighbors.
Find a new nearest neighbor for
a
.
Add
a
to its new list of associates.
For each neighbor
b
of
X
i
Remove
X
i
from
b
's lists of associates.
ithout
≥
w
Endif
Return
S
.
DROP2
-In this method, the removal criterion can be restated as:
Remove
X
i
if at least as many of its associates in
TR
would be classified correctly
without
X
i
.
