Graphics Reference
In-Depth Information
•
Repeated-ENN (RENN)
[
165
]—It applies the ENN algorithm repeatedly until
all instances remaining have a majority of their neighbors with the same class.
•
Multiedit
[
47
,
48
]—This method proceeds as follows.
Let
S
=
TR
.
Do
Let
R
=
S
.
Let
S
=∅
and randomly split
R
into
b
blocks:
R
1
, ...,
R
b
,
where
b
>
2
For each
b
i
block
Add to
S
the prototypes from
R
b
i
that are
misclassified using the KNN rule with
R
mod b
.
(
b
i
+
1
)
While
S
=
R
.
•
Relative Neighborhood Graph Edition (RNGE)
[
139
]—A Proximity Graph
(PG),
G
=
(
V
,
E
)
, is an undirected graph with a set of vertices
V
=
TR
, and a set
of edges,
E
, such that
E
if ad only if
t
i
and
t
j
satisfy some neighborhood
relation. In this case, we say that
t
i
and
t
j
are
graph neighbors
. The graph neighbors
of a given point constitute its
graph neighborhood
. The graph neighborhood of a
subset,
S
(
t
i
,
t
j
)
∈
V
, consists of the union of all the graph neighbors of every node in
S
. The scheme of editing can be expressed in the following way.
⊆
1. Construct the corresponding PG.
2. Discard those instances that are misclassified by their graph neighbors (by the
usual voting criterion).
The PGs used are the
Gabriel Graph Edition (GGE)
and the
Relative Neigh-
borhood Graph Edition (RNGE)
.
Gabriel Graph Editing (GGE)
-The
GGE
is defined as follows:
d
2
d
2
d
2
(
t
i
,
t
j
)
∈
E
⇔
(
t
i
,
t
j
)
≤
(
t
i
,
t
k
)
+
(
t
j
,
t
k
),
∀
t
k
∈
T
,
k
=
i
,
j
.
(8.1)
where
d
(
·
,
·
)
be the Euclidean distance.
Relative Nearest Graph Editing (RNGE)
-Analogously, the set of edges in the
RNGE
is defined as follows:
(
t
i
,
t
j
)
∈
E
⇔
d
(
t
i
,
t
j
)
≤
max
(
d
(
t
i
,
t
k
),
d
(
t
j
,
t
k
)),
∀
t
k
∈
T
,
k
=
i
,
j
.
(8.2)
•
Modified Edited Nearest Neighbor (MENN)
[
84
]—This algorithm, similar to
ENN, starts with
S
=
TR
and then each instance
X
i
in
S
is removed if it does
