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

Contents
IEEE Systems, Man and Cybernetics Magazine - April 2020 - Cover1
IEEE Systems, Man and Cybernetics Magazine - April 2020 - Cover2
IEEE Systems, Man and Cybernetics Magazine - April 2020 - Contents
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 2
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 3
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 4
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 5
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 6
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 7
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 8
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 9
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 10
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 11
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 12
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 13
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 14
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 15
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 16
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 17
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 18
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 19
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 20
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 21
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 22
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 23
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 24
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 25
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 26
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 27
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 28
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 29
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 30
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 31
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 32
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 33
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 34
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 35
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 36
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 37
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 38
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 39
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 40
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 41
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 42
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 43
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 44
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 45
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 46
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 47
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 48
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 49
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 50
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 51
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 52
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 53
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 54
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 55
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 56
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 57
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 58
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 59
IEEE Systems, Man and Cybernetics Magazine - April 2020 - 60
IEEE Systems, Man and Cybernetics Magazine - April 2020 - Cover3
IEEE Systems, Man and Cybernetics Magazine - April 2020 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/smc_202010
https://www.nxtbook.com/nxtbooks/ieee/smc_202007
https://www.nxtbook.com/nxtbooks/ieee/smc_202004
https://www.nxtbook.com/nxtbooks/ieee/smc_202001
https://www.nxtbook.com/nxtbooks/ieee/smc_201910
https://www.nxtbook.com/nxtbooks/ieee/smc_201907
https://www.nxtbook.com/nxtbooks/ieee/smc_201904
https://www.nxtbook.com/nxtbooks/ieee/smc_201901
https://www.nxtbook.com/nxtbooks/ieee/smc_201810
https://www.nxtbook.com/nxtbooks/ieee/smc_201807
https://www.nxtbook.com/nxtbooks/ieee/smc_201804
https://www.nxtbook.com/nxtbooks/ieee/smc_201801
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_1017
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0717
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0417
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0117
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_1016
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0716
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0416
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0116
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_1015
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0715
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0415
https://www.nxtbook.com/nxtbooks/ieee/systems_man_cybernetics_0115
https://www.nxtbookmedia.com