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

Years passed, technology prospered, and big data
descended upon us. And not only big data. In addition to
the problem of scalability [26]-[28], prototype selection was
facing new challenges [29]: streaming data [30], unlabeled
data, data with concept drift [31], and more. How did random prototype-selection methods fare in the new world

Algorithm 1. The RMHC prototypeselection algorithm.
Input: X, M, T
Output: Reference set S, S 1 X, ;S ; = M
1	 C ! choose (A, M ) // the chromosome to mutate
2	 e ! e (X (C ), X ) // stored error
3	 for
4		
5		
6		
7		

i = 1:T do
C temp ! C.
k ! choose (B,1) // index to mutate
C temp (k ) ! choose (A\C,1) // replace
e temp ! e (X (C temp), X ).

8		 if e temp # e then
C ! C temp; e ! e temp
9			
10	Return S = X (C ).

Algorithm 2. The RNGE prototypeselection algorithm.
Input: X
Output: Reference set S, S 3 X
1	Build G, the RNG for X.
2	Remove all points which are misclassified by their
  immediate neighbors in G.
3	 Return the remaining points as S.

Algorithm 3. The RNN prototype-selection
algorithm.
Input: X
Output: Reference set S, S 3 X
1	 Run Hart's algorithm [12] on X to obtain an initial C.
2	 flag ! true.
3	 while flag do
4		 flag ! false.
5		 for each element i of C do
6			 C l ! C \" i ,. // remove i temporarily
7			 if Cl is consistent then
8				 C ! C l. // remove i permanently
9				 flag ! true.
10	Return S = X (C ).

52	

IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE Apri l 2020

order? Quite well, apparently, especially the evolutionary
algorithms [32]-[34]. Shall we check some of the recent
favorites? Let's see how our random methods manage to
reconstruct George by using as few prototypes as possible.
The Fun Part: Recognizing George
Methods
García et al. [18] and Triguero et al. [19] reviewed, between
them, more than 75 prototype selection and replacement
methods and ran experimental comparisons. Since we have
our hearts set on prototype selection, here are the methods
that García et al. identified as the best (the first-mentioned
method in each group). To simplify the algorithms, I introduce some common concepts and notations:
◆◆ All algorithms take labeled data set X with N objects
as input.
◆◆ We will denote by M the desired number of prototypes that will be an input parameter for some of the
algorithms.
◆◆ T denotes the number of iterations, K represents
the population size, and W designates the number of
generations.
◆◆ We will need two sets of indices A ! " 1, 2, f, N , and
B ! " 1, 2, f, M , .
◆◆ We will also need two functions: e (S, X ), returning
the 1-NN classification error for X when S is used as
the reference set; and choose (Q, m ), returning a random subset of cardinality m sampled without replacement from set Q.
Note that if I is a set of indices of elements of X, we
use X (I ) to denote the subset of X that contains the in--
dexed elements.
◆◆ Random-mutation hill climbing (RMHC) (1994): From
the hybrid family (editing and condensing), RMHC [22]
achieved an excellent trade-off between reduction and
classifier success in the experiments. It is one of the
beautifully elegant random, criterion-driven methods.
(Score!) While the original algorithm's search space is
binary, for the experiment with George, we can indulge
in a less efficient but more straightforward implementation (Algorithm 1).
In our implementation, we evolved several solutions
and picked the best one (subset S).
◆◆ Relative neighborhood-graph editing (RNGE) (1997):
RNGE is an editing-prototype-selection algorithm [35]
classed as the best in its group [18]. The RNG is an
undirected graph defined on X. There is an edge
between p ! X and q ! X if there is no other point
r ! X that is closer to p and q than they are to each
other. The editing algorithm works by building the
RNG of X and removing all points that are misclassified by their immediate neighbors (Algorithm 2).
◆◆ Relative nearest neighbor (RNN) (1972): The RNN
rule [36] was singled out as one of the best two methods in the condensing group [18]. The RNN starts with



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