IEEE Systems, Man and Cybernetics Magazine - April 2020 - 53

Algorithm 4. The GA prototype-selection
algorithm.
Input: X, M, K, W
Output: Reference set S, S 1 X, ;S ; = M.
1	 for i = 1: K do
2		 P (i ) ! choose (A, M ) // random chromosome
3		 fp(i ) ! 1- e (X (P (i )), X ) // population fitness
4	 for gen = 1:W do
5		 O ! 4. // offspring set
6		 for par = 1: K/2 do
7			 p 1 ! choose (P,1) // parent 1
8			 p 2 ! choose (P,1) // parent 2
9			 k ! choose (B,1) // crossover point
10			Swap the tail parts of p 1 and p 2 to create
 offspring o 1 and o 2 . (Tail is from k + 1 to M.
If k = M, no crossover occurs and the offspring
are the parents themselves.)
11			 O ! O , " o 1, o 2 ,
12		 for j = 1: K do
13			 C ! O ( j )
14			 m ! choose (B,1) // index to mutate
15			 C (k ) ! choose (A\C,1) // replace
16			 fo( j ) ! 1- e (X (C ), X ) // offspring fitness
17			 O ( j ) ! C
18			Pool fp and fo and sort in descending order.
 Keep the best K chromosomes from P , O to
be the new population P and store the respective fitnesses as the new fp .
19	Return S = X (P (1)) // the best chromosome

a consistent reference set S (zero errors of 1-NN on
X ) and further reduces it by removing one element at
a time and checking whether the set is still consistent. If not, the element is returned to the set. If the
set is consistent, the element is permanently removed.
The process continues until all the elements have
been checked, and there has been no change to S
(Algorithm 3).
Did you notice? All three winning algorithms are old
and simple. That's my kind of algorithm. We add to this
collection our own baselines and competitors, as ex--
plained next.
◆◆ Hart (1968): Hart's CNN [12] returns a consistent set,
usually with a very good reduction rate. This is the
archetypal condensing algorithm, which gave rise to
the whole condensing branch.
◆◆ Wilson (1972): Wilson's algorithm [13] is the forefather
of the editing branch of prototype-selection. It marks
for deletion all objects of X that are misclassified by
their k nearest neighbors (typically, k = 3). Then, the
marked objects are removed, and the remaining set is
returned as S.
◆◆ MC1 (1994): The MC1 method for prototype selection
[22] is the same as our random search [20]. This is a
	

Table 1. The results from the experiment
with noise-free George data.
Method

Type

Error Rate
(%)

Number of
Prototypes

Time
(s)

1-NN

-

6.68

1,000

0.18

Hart

C

7.9

211

24.93

Wilson

E

7.1

913

0.5

Wilson + Hart

H

8.44

101

22.71

RNGE

E

6.59

921

3.92

RNN

C

8.2

160

27.81

RMHC

H

15.83

10

81.99

RMHC

H

13.31

20

79.27

RMHC

H

10.47

100

83.42

RMHC

H

9.49

200

84.04

MC1

H

20.21

10

75.45

MC1

H

15.62

20

78.8

MC1

H

11.16

100

81.23

MC1

H

9.83

200

83.81

GA

H

12.68

10

76.63

GA

H

8.47

20

77.2

GA

H

6.52

98

84.71

GA

H

6.96

195

82.49

Boldface indicates that the result is in the Pareto front in terms of error-rate/
reference-set size. C: condensing; E: editing; H: hybrid.

Figure 2. The classification regions of the 1-NN with

10% label-noise contamination; the error rate is 18.49%
(or a nice pajama pattern).

brute-force random search whereby we generate T
prototype sets and pick the best among them. The
value of T is chosen in advance.
◆◆ GA (1995): GAs are a perfect fit for prototype selection [20], [32]-[34], [37]. The chromosome can encode
S 3 X storing zero at position i if the ith element of
X is not in S, and one, otherwise. The GA version
that we used here is shown in Algorithm 4. It enables
Ap ri l 2020

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE	

53
IEEE Systems, Man and Cybernetics Magazine - April 2020

Table of Contents for the Digital Edition of IEEE Systems, Man and Cybernetics Magazine - April 2020
