Graphics Reference
In-Depth Information
Using this modification, each instance
X
i
in the original training set
TR
continues
to maintain a list of its
k
+
1 nearest neighbors in
S
,evenafter
X
i
is removed from
S
. This means that instances in
S
have associates that are both in and out of
S
, while
instances that have been removed from
S
have no associates.
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.
DROP3
-It is a combination of
DROP2
and
ENN
algorithms.
DROP3
uses a noise-filtering
pass
before
sorting the instances in
S
(Wilson
ENN
editing). After this, it works
identically to
DROP2
.
•
CPruner
[
173
]—First it is necessary to introduce some concepts underlying this
algorithm.
Definition 8.1
For an instance
X
i
in
TR
,the
k
nearest neighbors of
X
i
make up its
k-reachability
set, denoted as
k-reachability
(
X
i
).
Definition 8.2
For an instance
X
i
in
TR
, those instances with similar class label to
that of
X
i
, and have
X
i
as one of their nearest neighbors are called the
k-coverage
set of
X
i
, denoted as
k-coverage
(
X
i
).
Definition 8.3
For instance
X
i
in
TR
,if
X
i
can be classified correctly by
k-
reachability
(
X
i
), then we say
X
i
is
implied
by
k-reachability
(
X
i
), and
X
i
is a
super-
fluous
instance in
TR
.
Definition 8.4
For instance
X
i
in
TR
,
X
i
is a
critical
instance, if the following
conditions holds:
At least one instance
X
j
in
k-coverage
(
X
i
) is not implied by
k-reachability
(
X
j
),
or
After
X
i
is deleted, at least one instance
X
j
in
k-coverage
(
X
i
) is not implied by
k-reachability
(
X
j
).
Definition 8.5
For instance
X
i
in
TR
,if
X
i
is not a superfluous instance and |
k-
reachability
(
X
i
)|
>
|
k-coverage
(
X
i
)|, then
X
i
is a
noisy
instance.
Rule 8.1
Instance pruning rule
For an instance
X
i
in
TR
, if it can be pruned, it must satisfy one of the following
two conditions:
It is a noisy instance;
It is a superfluous instance, but not a critical one.
Rule 8.2
Rule for deciding the order of instances removal
Let H-
k
NN(
X
i
) be the number of the instances of its class in
k
NN(
X
i
), and
D-NE(
X
i
) be the distance of
X
i
to its nearest enemy.
