PRIFYSGOL BANGOR / B ANGOR UNIVERSITY

Restricted Set Classification: Who is there?, Pattern Recognition
Kuncheva, Ludmila I.; Rodriguez, Juan J.; Jackson, Aaron S.
Pattern Recognition
DOI:
10.1016/j.patcog.2016.08.028
Published: 01/03/2017

Peer reviewed version

Cyswllt i'r cyhoeddiad / Link to publication

Dyfyniad o'r fersiwn a gyhoeddwyd / Citation for published version (APA):
Kuncheva, L. I., Rodriguez, J. J., & Jackson, A. S. (2017). Restricted Set Classification: Who isthere?, Pattern Recognition. Pattern Recognition, 63(C), 158-170.
https://doi.org/10.1016/j.patcog.2016.08.028

Hawliau Cyffredinol / General rights
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or
other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal
requirements associated with these rights.
• Users may download and print one copy of any publication from the public portal for the purpose of private
study or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal ?

Take down policy
If you believe that this document breaches copyright please contact us providing details, and we will remove access to
the work immediately and investigate your claim.

10. Oct. 2024

Restricted Set Classification: Who is there?
Ludmila I. Kunchevaa , Juan J. Rodrı́guezb , Aaron S. Jacksonc
a Bangor University, Dean Street, Bangor Gwynedd, LL57 1UT, United Kingdomb University of Burgos, Escuela Politécnica Superior, Avda. de Cantabria s/n, 09006 Burgos, Spainc The University of Nottingham, NG8 1BB, United Kingdom

Abstract
We consider a problem where a set X of N objects (instances) coming from c classes have to be classified
simultaneously. A restriction is imposed on X in that the maximum possible number of objects fromeach class is known, hence we dubbed the problem who-is-there? We compare three approaches to thisproblem: (1) Independent classification whereby each object is labelled in the class with the largest posterior
probability; (2) A greedy approach which enforces the restriction; and (3) A theoretical approach which, in
addition, maximises the likelihood of the label assignment, implemented through the Hungarian assignment
algorithm. Our experimental study consists of two parts. The first part includes a custom-made chess data
set where the pieces on the chess board must be recognised together from an image of the board. In thesecond part, we simulate the restricted set classification scenario using 96 datasets from a recently collated
repository (University of Santiago de Compostela, USC). Our results show that the proposed approach (3)outperforms approaches (1) and (2).
Keywords: pattern recognition, object classification, restricted set classification, compound decision
problem, chess pieces classification

1. Introduction
One of the standard assumptions in classical pattern recognition is that the data points to be classified
come as an independent, identically distributed (iid) sequence. In many problems, this assumption does
not hold. As an example, imagine the task of classifying all the pieces on a chess board from a bird-view
5

snapshot, without knowledge of the course of the game up to that position. A classifier trained to recogniseeach piece individually will not be aware that, say, there cannot be more than two white bishops on theboard. Thus a white pawn could be misclassified as a white bishop without a penalty. Should the classifier‘know’ the restriction, a mistake of this type will be less likely.

Email addresses: l.i.kuncheva@bangor.ac.uk (Ludmila I. Kuncheva), jjrodriguez@ubu.es (Juan J. Rodrı́guez),aaron.jackson@nottingham.ac.uk (Aaron S. Jackson)

Preprint submitted to Pattern Recognition

June 8, 2017

Consider a classification problem where an instance x may come from one of the c classes in the set
10Ω = {ω1 , . . . , ωc }. Every instance is described by the values of n features, so without loss of generality,x ∈ Rn . Let X = {x1 , . . . , xc } be a set containing exactly one instance from each class. A set-classifier
Dset will label X with a permutation of the c class labels and ensure the best match in terms of classification
accuracy [1, 2]. We refer to this task as “who-is-who”.
This paper extends the above model to the more general case where X consists of m instances, and it is15

known that at most ki instances may belong to class ωi , i = 1, . . . , c. Denoting k = k1 + . . . + kc , we requirethat m ≤ k. The who-is-who task is a special case where ki = 1, i = 1, . . . , c, and m = c.
Simultaneous classification of instances has been studied in various contexts for non-i.i.d data:
1. Compound decision problem. Duda et al. [3] formulate the problem where each class is represented in
X by a specific number of objects but without offering a solution. Taking inspiration from labelling the20

chromosomes in a cell (karyotyping), Slot [4] proposes a solution to this problem through maximising the
log-likelihood of the labelling of X by using 0-1 integer programming.
2. Multiple-instance classification. This problem arises in complex machine learning applications where theinformation about the instances is incomplete or ambiguous [5, 6, 7, 8, 9], for example, in drug activity
prediction [5]. The training examples come in “bags” labelled either positive or negative. For a positive

25

bag, it is known that at least one instance in the bag has a true positive label. For a bag labelled negative,
all instances are known to be negative. The problem is to design a classifier that can label as accurately as
possible an unseen bag of instances.
3. Set classification. In this problem, all the instances in a set are assumed to have come from the same
unknown class [10]. This problem may arise in face recognition where multiple images of the same person’s

30

face are submitted as a set.
4. Relaxation labelling. The m instances in set X should be labelled using the label set Ω. There are
relationships between the classes which are specified by the so-called compatibility coefficients. Iterative
relaxation labelling algorithms have been developed to solve this problem [11, 12].
Collective recognition. Collective recognition [13, 14] can be thought of as a special case of relaxation la-

35belling. The instances within the set are related, so that the dependencies can be used to improve theclassification accuracy. For example, in classifying web pages into topic categories, hyperlinked web pages
are more likely to share common class labels than non-linked pages [14].
Who-is-who can be cast as a relaxation labelling problem. However, the compatibility coefficients enforcing the constraint of one-per-class are such that we cannot take advantage of the existing algorithms. In

40fact, there is an exact algorithm to solve who-is-who, which is preferable to the iterative alternatives.
2

5. Tracking of multiple objects. Simultaneous classification of a set of instances is used in tracking algorithms
for video sequences. For example, a moving object can be regarded as a patchwork of parts [15], a set oftracklets [16] or a structure with connected pieces such as parts of a human face or body [17, 18, 19, 20].
The parts are matched from one image frame to the next. Tracking several people in a video [17, 21,4522] also relies on simultaneous classification. The classification in tracking is dominated by assessing the
spatial location of the object/part using algorithms such as Kalman filter, Probabilistic Data Association
Filter (PDAF) [23, 24], mixture modelling, AdaBoost, particle filters [25, 26], temporal templates [17], the
Hungarian algorithm [27, 28], a game-theory approach [22], a locomotion model [21] and so on.
The appearance-based component (which is the trained classifier in our model) is deemed much less50

important [19]. Indeed, sometimes the objects are indistinguishable, and the only way to identify themis using their predicted and observed locations (for example, monitoring fruit flies [28]). Typically, theappearance-based classifier uses silhouette, texture [17], HSV colour histograms and edge detection [25, 23].
Tracking piglets has been attempted by marking each piglet on the back by a dye pattern [29, 30] thereby
empowering the appearance-based classifier. The simultaneous classification model proposed here can be

55

regarded as an additional tool for improving the tracking accuracy by making a better use of the objects’appearance.
While close, none of the problems and solutions above matches exactly our formulation of the restricted
set classification problem. The closest set-up is the compound decision problem but in our case we allow
for up to ki objects from each class instead of a fixed number. Potential applications of the restricted set

60

classification scenario include automatic attendance registration of students, karyotyping [31, 32, 33, 4],monitoring of animal behaviour (fruit flies [28], piglets [29, 30]), real-time labelling of the players in a game
video stream (football [26], hockey [25]).
The rest of the paper is organised as follows. Section 2 lays out the theory behind the restricted set
classification problem. Experimental results are shown in Section 3, and a conclusion is offered in Section 4.

65

2. The restricted set classification problem
Definition 1. The restricted set classification problem is defined as follows. Let X = {x1 , . . . , xm } be a
set of instances such that at most ki instances come from class ωi ∈ Ω = {ω1 , . . . , ωc }. Find labels for all
elements of X so that the restriction holds.
Note that k1 + . . . + kc = k ≥ m.

70

Definition 2. A base classifier D is a classifier that assigns a class label to an instance x ∈ Rn
D : Rn → Ω.
We also require that D provides estimates of the posterior probabilities P (ω1 |x), . . . , P (ωc |x).
3

(1)

Definition 3. A super-label for set X is any collection of m labels from Ω so that any instance x ∈ X
receives a single label. A super-label will be called consistent if it satisfies the requirement that at most kilabels are equal to ωi , i = 1, . . . , c.
Denote by S the set of all possible super-labels of X. Let P = [pij ] be a matrix of size m × c that75

contains the posterior probability estimates obtained from the base classifier D applied to X. Entry pij isthe estimate of P (ωj |xi ). Let P be the set of all matrices P .
Definition 4. A set classifier Dset assigns a super-label to any set X using the output of classifier D, thatisDset (X, D) : P → S.
80

(2)

We consider two type of estimates of the accuracy of Dset for a given set X:• AT , total accuracy: AT = 1 if all labels are correctly assigned to the instances in X, and AT = 0,otherwise;• AP , partial accuracy: AP is the proportion correctly labelled instances in X.
i. This classifier takes the labels suggested
Definition 5. Independent (Baseline) Set Classifier Dset

85

by D without any modification.
g. Assume that D outputs the true posterior probabilities
Definition 6. Greedy Set Classifier Dset

P (ωi |x), for i = 1 . . . , c and any x ∈ Rn . This classifier labels the set X according to the following
algorithm:
1. Initialise a set V = ∅ to store the assigned object-class pairs.
90

2. Identify the largest posterior probability P (ωj∗ |x∗j ) among the objects and classes not assigned so far.
3. Remove ωj∗ from the list of available classes, and x∗j from the list of available objects, and add the pair
to set V .
4. If there are no class-object pairs left, stop and return V . Else, continue from step 2.
To derive the extended model for simultaneous classification we will first introduce the two special cases:95

the who-is-who [1] and who-is-missing [2].
2.1. Who-is-who?
A set of c objects have to be labelled into c classes so that there is exactly one object in each class. Let
p be the probability that D will label correctly a randomly chosen instance x.
ii
Dset
assumes that all instances are labelled independently. Then the accuracy measures of Dset
arei
AT (Dset) = pc

4

(3)

100

and
i
AP (Dset) = p.

(4)i
The super-label assigned by Dset
may not be consistent, more likely so for larger number of classes c. Itiis possible to improve especially on AP (Dset) by ensuring that the super label is consistent, for example bygapplying Dset.

2.1.1. Two classes
105

Let c = 2 and X = {x1 , x2 }. Without loss of generality, assume that x1 was drawn from the distributionof class ω1 , and x2 from ω2 , hence the true super-label is hω1 , ω2 i. Suppose again that D is the perfectclassifier for the chosen feature space, and therefore we have knowledge of the true posterior probabilities.
To simplify notation, denote P1 = P (ω1 |x1 ) and P2 = P (ω2 |x2 ).
i
The probability that Dset
will give the correct super-label of X isi
AT (Dset(X)) = P r(P1 > 0.5 & P2 > 0.5) .

110

(5)

g
will add to this two more cases. The super-label will be correct also when P1 < 0.5 andHowever, Dset

P2 > 1 − P1 , ensuring that ω2 will be assigned first to x2 , leaving the free label ω1 for x1 . By the same logic,gDset
will be right when P2 < 0.5 and P1 > 1 − P2 . Since the cases are mutually exclusive, the probabilitygwill give the correct super-label of X isthat Dsetg(X))
AT (Dset=

P r(P1 > 0.5 & P2 > 0.5)

115+

P r(P1 < 0.5 & P2 > (1 − P1 ))+P r(P1 > (1 − P2 ) & P2 < 0.5)

(6)

≥

i
AT (Dset(X))(7)

The above expression reduces tog
AT (Dset(X)) = P r(P1 + P2 > 0.5) .

(8)

g
i
As AT (Dset(X)) ≥ AT (Dset(X)) for any X, the inequality is valid across the whole space of pairs (x1 , x2 ).

To visualise the improvement due to the greedy strategy, consider the two-dimensional data set shownin Figure 1. We drew 10,000 random pairs X = {x1 , x2 }; x1 from ω1 and x2 from ω2 .
The true probabilities P1 = P (ω1 |x1 ) and P2 = P (ω2 |x2 ) are used as the coordinate axes in Figure 2120

iwhere points corresponding to the 10,000 pairs are scattered. The region where Dset
gives the correct superglabel is shaded in light grey, and the number of points is shown. The regions where Dset
adds accuracy toithat of Dset
are shaded in dark grey.

5

x1

x2
Figure 1: A two-dimensional data set with 10,000 points in each class.
gi) = 80.80% and AT (Dset) = 7.65 + 7.90 + 80.80 = 96.35%.
For this example, AT (Dset

Proposition 1. [1] For 2-class problems,gi
AP (Dset) > AP (Dset
).

125

(9)

The proof is shown in the Appendix.
The theory about the two-class who-is-who problem has been illustrated by an earlier experimental study
to demonstrate the results’ validity when D is not a Bayes classifier and the posterior probabilities are only
estimates [1].
2.1.2. c classes

130

Let X = {x1 , . . . , xc } be the set of c objects where object xi is drawn from the distribution of class ωi ,independently of the other c − 1 objects. Then the likelihood of a super label S = hs1 , . . . , sc i, si ∈ Ω is
L(S) =cY

P (si |xi )p(xi |ωi ) .

(10)

i=1

Since p(xi |ωi ) does not depend on the super-label S, we can organise it into a multiplicative constant
Qc
PX = i=1 p(xi |ωi ), and rewrite the likelihood as
L(S) = PX

c
Y
i=1

6

P (si |xi ) .

(11)P (ω1 |x1 )
1

765

8080

0.8
0.6

790

0.4

365
0.2
0
0

0.5

1

P (ω2 |x2 )Figure 2: 10,000 random pairs of points with super-label hω1 , ω2 i drawn from the problem in Figure 1. The points are plotted
the space of the true posterior probabilities P (ω1 |x1 ) and P (ω2 |x2 ). The number of points in the respective regions are
displayed.

The set of feasible super-labels is the set of all permutations of the elements of Ω. The optimal super-label
135

S ∗ will be the one maximising the L (equivalently log(L)), that isS ∗ = arg max
S∈I

c
X

log(P (si |xi )) ,

(12)

i=1

g
where I is the set of all permutations of the class labels in Ω. S ∗ . Note that the greedy set classifier Dset

will not guarantee the optimal solution.
hDefinition 7. Hungarian Set Classifier Dset.

This classifier uses the Hungarian assignment algo-∗ 1rithm [34] to find S . . The input to the algorithm is the matrix LP with the logarithms of the poste140

rior probabilities obtained from the individual classifier, and the output is the optimal permutation S ∗ ,guaranteeing the maximum sum of logarithms, as in equation (12).
gih) and AT (Dset) [1].
Previous experiments have shown significant improvement of AT (Dset) over both AT (Dset

2.2. Who-is-Missing?
In this scenario, a set X of k < c objects have to be labelled into c classes so that there is at most145

one object in each class [2]. As the question of interest here is “who-is-missing”, it may be thought thatthe correct assignment of the elements of X is not strictly necessary. However, in order to maximise thelikelihood of discovering the identity of the missing classes, we still need to maximise the likelihood of theassignments of the objects in X. Let S(−) ⊂ Ω and S(+) = Ω \ S(−) be respectively the set of missing and theset of present classes. The probability that S(−) is missing is the same as the probability that S(+) is present.
1 Further developed by Kuhn and Munkres, also known as Kuhn-Munkres algorithm. Proposed originally for c × c matrices,

the Hungarian algorithm has been extended for rectangular matrices [35].

7

150

Therefore, by maximising the log-likelihood of the collection of labels in S(+) , we maximise the probabilityof discovering the correct S(−) . This allows for the who-is-missing problem to be cast as who-is-who.
We create v = c − k dummy objects z1 , . . . , zv , and assign probabilities P (ωi |zj ) = 1/c for all i = 1, . . . , cand j = 1, . . . , v. Thus the matrix with posterior probabilities P is of size c × c, and has v identical rows
with values 1/c. The optimal labelling (eqn (12)) becomes


 
k
v
X
X
1
.
S ∗ = arg max log(P (si |xi )) +
log
S∈I
c
i=1
j=1

155

(13)

The second term can be absorbed into a constant which does not depend on S, and does not affect thehoptimal assignment of labels to X. The Hungarian set algorithm Dset
can be applied to P for finding S ∗ .

The labels assigned to the dummy objects are the missing classes. Note that the value of the constant we
assign in place of the posterior probabilities for the dummy objects does not matter. The same assignment
will be obtained for any value.
160

We carried a set of experiments for the who-is-missing problem [2] with the UCI letter data set and anhimage data set of LEGO parts. The results again strongly favoured the Hungarian set algorithm Dset
beforegiand the independent Dset
set algorithms.
the greedy Dset

2.3. Solution to the restricted set classification problem
Following the naming convention for the two special cases above, we call the restricted set classification165

problem (Definition 1) ‘who-is-there’.
Recall the example of who-is-there where the chess pieces on a board are to be recognised from a birdview snapshot. In this case, there are 12 possible classes (pawn, bishop, knight, castle, king, queen; × 2 forblack and white) and up to 32 objects. The maximum number of objects from each class is fixed by context.
We assume that we don’t have prior knowledge of the moves leading to the current board configuration.

170

To solve the who-is-there problem, we should be looking to maximise the log-likelihood of the superlabel. However, this time the set of classes has to be augmented with ki copies of each class. The posterior
probabilities for the copies are the same as the one in the original column. In addition, the set of objects also
has to be expanded to contain k objects altogether. The k − m dummy objects are assigned 1/c posterior
probabilities for all k possible class labels in the super-label. The resultant matrix P is of size k × k. The

175

example below illustrates this arrangement.
Consider three classes denoted respectively •, 4 and . It is known that X contains at most k = 5
objects where at most 2 are from class •, at most 1 is from class 4 and at most 2 are from class . Supposethat the observed set X contains m = 4 objects with the following posterior probabilities provided by D:

8

Matrix withposteriorprobabilities

Dummy object

Dummy classes

𝐱1
𝐱2
𝐱3
𝐱4
𝐳1

0.53
0.55
0.21
0.50
0.33

0.53
0.55
0.21
0.50
0.33

0.23
0.36
0.50
0.33
0.33

0.24
0.09
0.29
0.17
0.33

0.24
0.09
0.29
0.17
0.33

Figure 3: Construction of matrix P (8 × 8) for the numerical example. The ellipses show the assignment by Dh .

set

180

ObjectP (•|x)

P (4|x)P (|x)

x1

0.53

0.23

0.24

x2

0.55

0.36

0.09

x3

0.21

0.50

0.29

x4

0.50

0.33

0.17

h
We construct P as shown in Figure 3. The assignment resulting from applying Dset
to P is also indicatedin the figure.
h
The Hungarian set classifier Dset
will assign super-label h • 4•i to the four objects in X, amounting

to criterion valueln(0.24) + ln(0.55) + ln(0.50) + ln(0.50) = −3.4112 .
g, on the other hand, will assign super-label h• • 4i, which gives
The Greedy set classifier Dset

ln(0.53) + ln(0.55) + ln(0.50) + ln(0.17) = −3.6978 .
185hBoth super-labels satisfy the constraints but Dset
leads to a higher (better) log-likelihood value comparedgh. This is to be expected as Dset
guarantees the optimal assignment of labels with respect to theto Dsetlog-likelihood criterion.

3. Experiments
Our hypothesis is that, for the restricted set classification problem, both accuracy measures AT and AP
190

g
h
i
should be maximised by applying Dset
compared to applying Dset
and Dset, for various models of the baseclassifier D.

93.1. Chess pieces
For this experiment we used 46 bird-view snapshots of a chess board. Each image was cropped andsquared (Figure 4 (a)), and subsequently split into 64 squares. The task is to identify the chess pieces and195

their positions (Figure 4 (b)). Figure 4 (c) shows examples of the training data for the 13 classes: 12 classes
for the chess pieces and one class for empty squares (denoted by E). Five instances (image tiles) are shown
from each class.

  !
  
                 (a) Bird-view snapshot(b) True positions



E

(c) Examples of the training data
Figure 4: A chess board example

We decided to use the following features on each tile:• Entropy of the grey-level image.
200• Standard deviation of the grey-level image.
• Difference between the mean grey intensity of (i) a square centred at the tile centre, with side equal
to half of the tile side, and (ii) the tile area outside the square.
• 100 grey-level values obtained by resizing the image to 10 × 10 pixels.
10

The experiment was organised as 46-fold cross-validation where one board was left aside in each fold. A
205classifier was trained for each fold, and the posterior probabilities of the testing data were subsequently
calculated. The classifier models which we tried out as base classifier D are shown in Table 1.2
The matrix with the posterior probabilities P was expanded as demonstrated in Figure 3. The three setgihclassifiers: Dset
(B), Dset(G) and Dset
(H) were then applied giving the accuracies shown in Table 1.

Table 1: Averaged partial accuracy AP and averaged total accuracy AT in % for the Baseline (B), Greedy (G) and the
Hungarian (H) set classifiers for the 46-cross-validation experiment for the Chess data. Symbol • after the value in column
Ap -H indicates that H is significantly different from G at p < 0.001, and symbol − means that there is no significant difference.
The largest AP for each classifier type is underlined.

Partial accuracy AP
Classifier

B

G

Nearest neighbour

95.75

96.23

Linear discriminant analysis

79.42

Naı̈ve Bayes

Total accuracy AT

H

B

G

H

96.43 −

32.61

43.48

47.83

80.74

83.19 •

0.00

0.00

0.00

39.64

59.68

64.20 •

0.00

0.00

0.00

Decision tree

87.13

85.67

86.01 −

4.35

4.35

4.35

SVM – linear

89.57

90.18

90.52 −

0.00

2.17

2.17

SVM – radial basis function (RBF)

87.67

88.52

89.50 •

2.17

2.17

2.17

SVM – sigmoid kernel

67.46

67.53

67.46 −

2.17

2.17

2.17

SVM – polynomial kernel

87.57

88.76

88.82 −

0.00

0.00

0.00

Random Forest

91.88

93.00

93.58 •

2.17

19.57

26.09

h
Paired t-test was used to identify any significant differences between AP for the proposed Dset
against210gh
at p < 0.001 for the classifier models. The results favour Dset
which is often the most accurate set
Dset

classifier. The greedy set classifier is the next best, and the baseline set classifier (independent applicationof D) wins only once, for the decision tree classifier. This is likely a result from the notoriously poor
approximation of posterior probabilities by the standard decision tree classifier.
Looking at AT , the only base classifier which can be of any use in recognising the whole set of chess215

pieces for this experiment is the nearest neighbour. Even its accuracy AT is not sufficiently high. For the
purposes of demonstrating the advantage of using a proper set classifier, we chose a difficult task. This canbe observed in the small example of the training set in Figure 4 (c). The position of the camera was suchthat the same type of piece could be seen to “lean” up, down, left or right, so much so that a distinguishingpart of the top of the piece is missing. We did not attempt to analyse whether the background of the piece is
2 Own MATLAB code was used for the nearest neighbour classifier, the naı̈ve Bayes classifier and the random forest ensemble(RF). The MATLAB Statistic Toolbox was used for the linear discriminant classifier, the decision tree classifier and the random
tree base classifier for RF. LibSVM library [36] was used for the multi-class SVM classifiers.

11

220

black or white, and proceed to apply different classifiers accordingly. If the aim of the paper was to recognisecorrectly all the pieces in this restricted set classification problem, we would have opted for multiple cameras,
more elaborate and context-related features, advanced classifiers such as deep learning neural networks, andcalibration of the posterior probabilities. Our experiment is a proof of concept. It demonstrates that the
restricted set classification problem needs special treatment beyond training a standard classifier D and

225

applying it independently to the elements of the set of instances X.
3.2. USC data
3.2.1. The data collection
In the second set of experiments we used a collection of datasets chosen as a testbed for a comprehensive
experimental evaluation of 179 classifiers from 17 families [37]3 . Many of the datasets within the collection

230

are from the UCI Machine Learning Repository [38]. We refer to this repository as USC after the host
university (University of Santiago de Compostela, Spain).
To enable a reasonable formulation of the restricted set classification problem we had to ensure that
there is sufficient variability within each class we sampled from. Otherwise the results would depend too
much on a few instances. Therefore, we reduced the original 121 datasets to 96 datasets, and modified those235

retained according to the following rule. Classes containing less than 50 examples were removed. Hence,
datasets without at least two classes with at least 50 examples in each were discarded from the collection.
The description of the data collection that we used is shown in Table 2.
3.2.2. Experimental protocol
Two fold cross validation, repeated five times, was used to partition the data into training and initial240

testing sets. From each of the ten initial testing sets, 100 runs were carried out. Thus, for each dataset, we
carried out 1000 runs.
In each run, we commence by initialising the set to be labelled by X = ∅. A random integer between 1
and 10 is drawn for each class to serve as the limit on the number of possible objects from that class. Denoteby ki the number of objects allowed for class ωi . Then a second random integer, ri , is drawn between 0 and

245

ki , to determine how many objects from ωi will actually be present in the set X. Note that we include thepossibility of a completely absent class. Next, we add to X ri randomly selected testing objects whose truegihlabel is ωi . After constructing the set X, Dset
(Baseline), Dset
(Greedy) and Dset
(Hungarian) are applied

to find the respective super-labels.
The following set of classifiers were tested as D:
250• Nearest neighbour (1-NN)
3 The repository is available at http://persoal.citius.usc.es/manuel.fernandez.delgado/papers/jmlr/

12

Table 2: Characteristics of the datasets (#E: examples, #F: feautures, #C: classes).
dataset

#E

#F

#C

dataset

#E

#F

#C

abalone

4177

8

3

molec-biol-splice

3190

60

3

acute-inflammation

120

6

2

monks-1556

6

2

acute-nephritis

120

6

2

monks-2

601

6

2

48842

14

2

monks-3554

62annealing

850

31

3

mushroom

8124

21

2

arrhythmia

295

262

2

musk-1

476

166

2

balance-scale

576

4

2

musk-2

6598

166

2

bank

4521

16

2

nursery

12958

8

4

adult

blood

748

4

2

oocytes-merluccius-nucleus-4d

1022

41

2

breast-cancer

286

9

2

oocytes-merluccius-states-2f

1022

25

3

breast-cancer-wisc

699

9

2

oocytes-trisopterus-nucleus-2f

912

25

2

breast-cancer-wisc-diag

569

30

2

oocytes-trisopterus-states-5b

898

32

2
10

car

1728

6

4

optical

5620

62

cardiotocography-10clases

2126

21

10

ozone

2536

72

2

cardiotocography-3clases

2126

21

3

page-blocks

5445

10

4

chess-krvk

28029

6

17

pendigits

10992

16

10

chess-krvkp

3196

36

2

pima

768

8

2

congressional-voting

435

16

2

planning

182

12

2

conn-bench-sonar-mines-rocks

208

60

2

ringnorm

7400

20

2

conn-bench-vowel-deterding

990

11

11

seeds

210

7

3

connect-4

67557

42

2

semeion

1593

256

10

contrac

1473

9

3

soybean

362

35

4

credit-approval

690

15

2

spambase

4601

57

2

cylinder-bands

512

35

2

spect

265

22

2

dermatology

297

34

4

spectf

267

44

2

ecoli

272

7

3

statlog-australian-credit

690

14

2

energy-y1

768

8

3

statlog-german-credit

1000

24

2

energy-y2

768

8

3

statlog-heart

270

13

2

glass

146

9

2

statlog-image

2310

18

7

haberman-survival

306

3

2

statlog-landsat

6435

36

6

hayes-roth

129

3

2

statlog-shuttle

57977

9

5

heart-cleveland

219

13

2

statlog-vehicle

846

18

4

heart-hungarian

294

12

2

steel-plates

1941

27

7

heart-va

107

12

2

synthetic-control

600

60

6

hill-valley

1212

100

2

teaching

102

5

2

horse-colic

368

25

2

thyroid

7200

21

3

ilpd-indian-liver

583

9

2

tic-tac-toe

958

9

2

image-segmentation

2310

18

7

titanic

2201

3

2

ionosphere

351

33

2

twonorm

7400

20

2

iris

150

4

3

vertebral-column-2clases

310

6

2
3

led-display

1000

7

10

vertebral-column-3clases

310

6

letter

20000

16

26

wall-following

5456

24

4

469

100

3

waveform

5000

21

3
3

low-res-spect
lymphography
magic
mammographic
miniboonemolec-biol-promoter

142

18

2

waveform-noise

5000

40

19020

10

2

wine

130

13

2

961

5

2

wine-quality-red

1571

11

4

13006450

2

wine-quality-white

4873

11

5

106

57

2

yeast

1350

8

5

13

• Linear discriminant analysis (LDA)• Naı̈ve Bayes (NB)
• Logistic Regression (LOG)• Decision tree (DT)255

• Random Forest (RF)• Rotation Forest (ROT)
3.2.3. Results
We have prepared a supplementary document which contains the full numerical results from the experiments in seven tables, one for each classifier. Here we reproduce only the table for the decision tree classifier

260(Table 4).
The best and the worst base classifiers. We next give a graphical illustration of the two methods
which appeared to be the weakest and the strongest in our experiment: Naı̈ve Bayes (NB, the weakest)iand Rotation Forest ensemble (ROT, the strongest). Figure 5 (a) shows the improvement on AP of Dsethto the restricted set classification problem. To prepare the plot, we arranged
achieved by applying Dset

265

i
i
h
the datasets in ascending order of AP (Dset). Then we plotted AP (Dset) and AP (Dset) versus the dataset

index. The differences between the two curves are small and not clearly visible, especially for larger values ofi
AP (Dset). Therefore, in order to show the consistency of the improvement, we drew a vertical line upwardsihfrom each point (dataset) where the strict inequality AP (Dset) < AP (Dset) held. Shown above the curveshis the number of datasets out of 96 which satisfy the inequality. For NB, the partial accuracy AP (Dset
) was
270

i
higher than AP (Dset) for all 96 datasets.
gh) and AP (Dset), this time sorting the datasets
In the same way, we plot together the curves for AP (Dsetgon AP (Dset). The graph is shown in Figure 5 (b). This time, there were datasets for which the opposite strictghinequality held, that is, AP (Dset) > AP (Dset). For these datasets, we drew the vertical lines downward,

and show the number of datasets under the curves. For this case, Method H was better than method G in
275

42 comparisons and worse in 13 comparisons, leaving 41 ties. We can apply the sign statistical test whose
p-value signifies reflects the probability that such difference may happen by chance if the two methods are,hin fact, equivalent. For the results plotted in Figure 5 (b), p = 6.66 × 10−5 , suggesting that AP (Dset) isgsignificantly better than AP (Dset).

Figure 5 suggests that, even though AP is not as high as for the remaining baseline classifiers D, the set
280classifier is able to improve on it consistently. Moreover, the Hungarian algorithm should be preferred to
the greedy algorithm for its, albeit small, provably superior accuracy.
14

100

90

Better = 96

G (black) and H (blue) accuracies

B (black) and H (blue) accuracies

100

80
70
60
Worse = 0
50
40
30
20

0

20

40
60
Data set # (sorted by B)

80

80
70
60
Worse = 13
50
40
30
20

100

Better = 42

90

0

20

(a)

40
60
Data set # (sorted by G)

80

100

(b)

Figure 5: Comparison between the partial accuracy AP of: (a) Di

h

g

h

set and Dset , and (b) Dset and Dset for the Naı̈ve Bayesclassifier and USC data collection. Upward vertical lines indicate that method H is strictly better than its counterpart for therespective dataset, and downward vertical line indicate that it is strictly worse. The numbers of datasets which satisfy theinequalities are shown in the respective parts of the plot.

Figure 6 is a matching example to Figure 5 where the based classifier is the Rotation Forest ensemble,
the best overall set classifier. Method H is again making a “clean sweep” against I. This time, however,the number of results where method H is worse than method G rose to 38 versus 55 comparisons in favour285

of method H. This gives p = 0.0180 for the two-tailed sign test, which still supports the claim that there issignificant difference in favour of method H at p < 0.01.
The scaling of the figures was kept the same to allow for a visual comparison of the accuracies. Clearly,
ROT leads to better AP than NB as all curves run higher in Figure 6. The improvement on AP , however,is more pronounced for NB. Part of this may be due to the fact that NB is meant to approximate posterior

290

probabilities (under the feature independence assumption), and gives a ready-made matrix with probabilities
P . Rotation Forest, on the other hand, uses the voting scores as approximation of the posterior probabilities,
which is not ideal, and may compromise the expected improvement on the accuracy of the independent set
classifier I,
Figure 7 contains all the results for the total accuracy AT whereby we require that all elements of X are

295

classified correctly (correct super-label). The p-values for the results in subplots (b) and (d) are respectively
0.0820 and 0.4484. If we consider the right-tailed test with null hypothesis about the medians G ≥ H, andalternative H > G, then the p-value for subplot (b) is 0.0410, hence method H is better than method G at
p < 0.05.
Statistical testing for all results. Table 3 presents a summary of all the results. Given the large number

300

of datasets, we considered it reasonable to display the average accuracies to support the statistical test
15

100

90

Better = 93

80
70
60
Worse = 0
50
40
30
20

0

20

40
60
Data set # (sorted by B)

80

Better = 55

90

G (black) and H (blue) accuracies

B (black) and H (blue) accuracies

100

80
70
60
Worse = 38
50
40
30
20

100

Figure 6: Comparison between the partial accuracy AP of: (a) Di

0

20

40
60
Data set # (sorted by G)

h

g

80

100

h

set and Dset , and (b) Dset and Dset for the Rotation

Forest ensemble and USC data collection. Upward vertical lines indicate that method H is strictly better than its counterpart
for the respective dataset, and downward vertical line indicate that it is strictly worse. The numbers of datasets which satisfy
the inequalities are shown in the respective parts of the plot.

results. Note that we still used the non-parametric sign test for the comparison. The results support theclaim that the set classifier which uses the Hungarian assignment algorithm is consistently better than thetwo rival algorithms. Admittedly, while consistent, the improvement over method G is fairly small, as
evidenced by Figures 5 – 7, where the curves for G and H visibly coincide. This raises up the question of305

whether the Hungarian algorithm is really needed for this task or satisfactory results can be obtained withthe greedy algorithm?
Note that this paper is about the definition of the restricted set classification problem. The crucial partof the proposed solution is the expansion of the probability matrix P . This can be followed by the optimal
assignment algorithm (H) or a good suboptimal assignment algorithm (G).

310

Analysis of the improvement of H over B. Figure 8 illustrates the improvement offered by method
H over the baseline set classifier B for both partial accuracy AP and total accuracy AT . For this example
we used all the results for the seven base classifiers. Each point corresponds to a dataset, so there are
96 × 7 = 672 points scattered in total in each sub-plot. The diagonal line is where the points should lie
if H and B had identical accuracies. The figure shows that, for both AP and AT , H is better than B.

315

Interestingly, the improvement on AP (sub-plot (a)) depends on the base accuracy while the improvement
on AT (sub-plot (b)) is more uniform on the total accuracy of B. The set classifier can correct individual
errors better when the base classifier is not very accurate, and less so when the individual accuracy increases.
This tendency exists but is less pronounced for the total accuracy AT .
In Figure 9 we examine the relationship between the improvement on the partial and the total accu-

320racy. The 672 points obtained from all seven classifier models and all datasets are scattered in the space
16

80

100
Better = 91

G (black) and H (blue) accuracies

B (black) and H (blue) accuracies

100

60

40

20

0
0

Worse = 0

20

40
60
Data set # (sorted by B)

80

80

60

40

20

0
0

100

Better = 23

Worse = 10

20

40
60
Data set # (sorted by G)(a)

Better = 91

G (black) and H (blue) accuracies

B (black) and H (blue) accuracies

100

60

40

20

0
0

100

(b)

100

80

80

Worse = 2

20

40
60
Data set # (sorted by B)

80

80

60

40

20

0
0

100

(c)

Better = 46

Worse = 41

20

40
60
Data set # (sorted by G)

80

100

(d)

Figure 7: Comparison between the total accuracy AT of: (a) method H versus I, (b) method H versus method G for the
Naı̈ve Bayes classifier; (c) method H versus I, (d) method H versus method G for the Rotation Forest ensemble, all for
the USC data collection. Upward vertical lines indicate that method H is strictly better than its counterpart for the respective
dataset, and downward vertical line indicate that it is strictly worse. The numbers of datasets which satisfy the inequalities
are shown in the respective parts of the plot.

17

Table 3: Average partial accuracy AP and total accuracy AT for the three set classifiers (B Baseline, G Greedy and H
Hungarian) for seven base classifier models with the USC data collection. Method H was compared with I and G using thesign test at significance level p < 0.001. The results are shown next to the H columns. The first symbol is the result of the
H/I comparison, and the second symbol, the result from the H/G comparison. A bullet indicates that H is significantly betterthat the other set classifier, and a dash indicates that there is no difference at the chosen significance level.

Total accuracy AT

Classifier

B

G

B

G

Nearest neighbour (1-NN)

76.05

77.57

78.14 • •

30.03

32.55

33.45 • •Linear discriminant analysis (LDA)

73.74

76.86

76.99 • •

27.67

30.97

31.06 • •Naı̈ve Bayes (NB)

72.83

75.86

75.95 • •

25.10

28.50

28.51 • −Logistic Regression (LOG)

75.13

78.43

78.74 • •

29.74

33.65

33.95 • •Decision tree (DT)

77.81

79.85

80.27 • •

32.63

35.60

36.29 • •Random Forest (RF)

81.25

83.57

83.62 • •

40.16

44.03

44.14 • •Rotation Forest (ROT)

82.09

84.69

84.79 • −

42.80

47.05

47.14 • −

80

100

H

100

100

90

90

80

80
Hungarian

HungarianPartial accuracy AP

70

70

60

60

50

50

40
40

60

80

40
40

100

Baseline

H

60
Baseline(a) Partial accuracy AP(b) Total accuracy AT

Figure 8: Improvement of method H over method B for the 96 USC datasets using the all 7 base classifiers.

18

Improvement on total accuracy A T

20

15

10

5

0

−5
−5

0
5
10
Improvement on partial accuracy

15
AP

20

Figure 9: Scatterplot of all datasets for all seven base classifiers in the plane (∆AP , ∆AT ). The blue triangle contains 54% of
all pointshihi(∆AP , ∆AT ) where ∆AP = AP (Dset) − AP (Dset) and ∆AT = AT (Dset) − AT (Dset). The lines of no im-provement are depicted in red. The figure shows that the total accuracy benefits even more than the partial
accuracy (68.6% of the points are above the diagonal line, that is ∆AT > ∆AP ). We identified and outlined
by a triangle a dense region in the diagram containing approximately 54% of all points plotted. For these325

points, a fairly small improvement on the partial accuracy was sufficient to ensure a greater improvementin the total accuracy, justifying overall the restricted set classification approach. Larger improvements on
AP lead to larger improvement on AT too, but for most of these points, ∆AP > ∆AT (that is, the points
lie under the diagonal).
Another interesting observation from the figure is that even for datasets where the partial accuracy of330

method H was worse than that of method method B (left from the line ∆AP = 0), the total accuracy of
method H was still better than that of method B (∆AT > 0). Overall, ∆AT > 0 for 93.75% of the points,∆AT = 0 for 5.95% of the points, and ∆AT < 0 for 0.3% of the points. Note that this set of points includes
all seven base classifiers and all datasets.
Relationship of the improvement of H over B and the number of classes.. Figure 10 plots the335

improvement ∆AP and ∆AT versus the number of classes. The points in the scatterplots again correspondto the datasets using all seven base classifiers.
There is no visible relationship between the number of classes and the improvement of method H against
19

20

15

15

∆ AT

∆ A

P

20

10

5

0
0

10

5

10
20
Number of classes

0
0

30

(a)

10
20
Number of classes

30

(b)

Figure 10: Improvement of H over B for the partial accuracy (∆AP ) and the total accuracy ∆AT ) against the number ofclasses for the respective problems.

method B. The problems with two and three classes make up 75% of the USC collection. It can be expectedthat more is to be gained if we have a large number of classes compared to fewer classes, but this could not
340

be verified with this collection.

4. Conclusion
We propose a solution for the restricted set classification problem which we also call “who-is-there”.
The problem is to classify simultaneously a set of objects into c classes, ω1 , . . . , ωc , knowing that there
is at most ki objects from class ωi . The values of ki are specified in advance and fixed. Our solution is345

to expand the matrix with posterior probabilities given by the classifier so that we cover the possibility
Pc
for k = i=1 ki objects and labels, and apply the Hungarian assignment algorithm on the logarithms of
the posterior probabilities in the expanded matrix. The simpler alternatives which we considered were thestandard approach of applying the trained classifier D individually to each instance in the set X, and agreedy approach where objects and classes are paired and eliminated from the set. Our experimental study

350

validates the proposed approach for various choices of base classifier model D.
We demonstrated that the set classifier is better than the individual classifier for the restricted set
classification problem through a two-part experiment. In the first part, we formulated the problem on achess dataset where the all pieces on a chessboard had to be recognised from a bird-view snapshot. The
second experiment was carried out using the University of Santiago de Compostela collection of 96 data.

355

We constructed restricted set classification problems and applied the proposed solution. The experiments20

hfavoured ensemble classifiers as the base classifier D, and subsequently the Hungarian set classifier Dsetonthe expanded probability matrix.
The scalability of the proposed framework is affected only by the complexity of the Hungarian algorithm.
Training of the base classifier D is the same with or without the restricted set classification framework. The
360

complexity of the Hungarian algorithm for our case is O(k 3 ), where k is the maximum number of objects inthe set. The Hungarian algorithm may be impractical for very large k or when rapid classification is needed,
for example in tracking. In such cases, the greedy set classifier can be used, sacrificing some accuracy AP
and AT .
An interesting question which we intend to address in the future is that about possible dependencies in365

the set of objects X. The instances in X may not be independently drawn from their respective classes.
For example, the snapshot of the chessboard has a certain illumination. When classifying the pieces in theindividual squares cropped from the snapshot, we assume that they are drawn independently from theirrespective classes. In other words, the fact that these sub-images have similar illumination is not currently
accounted for in the theoretical model we propose here.

370

Acknowledgements
This work was partially supported by the Spanish Ministry of Economy and Competitiveness throughproject TIN 2015-67534-P.

Appendix
Proof of Proposition 1

375

Proposition 1. For 2-class problems,gi
AP (Dset) > AP (Dset
).

(14)

i
Proof. For Dset,i
AP (Dset)2
2
1
P r(P1 > 0.5)P r(P2 ≤ 0.5) ×
2
1
P r(P1 ≤ 0.5)P r(P2 > 0.5) ×
2
1(P r(P1 > 0.5) + P r(P2 > 0.5))
2p,= P r(P1 > 0.5)P r(P2 > 0.5) ×
+
+
=
=

21

(15)
(16)
(17)

g
where p is the accuracy of D. For Dset,g
AP (Dset) = P r(P1 > 0.5)P r(P2 > 0.5) ×

380

2
2

+P r(P1 ≤ 0.5)P r(P2 > 0.5)P r(P2 > 1 − P1 ) ×

2
2+P r(P1 > 0.5)P r(P2 ≤ 0.5)P r(P1 > 1 − P2 ) ×

2
.
2

(18)

The ROC curve of a classifier for a two-class problem is constructed by nominating any of the two classes
to be the ‘positive’ class and the other to be the ‘negative’ class. The area under the ROC curve, AU C,
gives the probability that the classifier will rank a randomly chosen positive instance higher than randomly
chosen negative instance [39]. Phrased differently, this is the probability that the classifier will make errors
with less certainty compared to the certainty when assigning a correct label. Formally,
AU C = P r(P1 > 1 − P2 ) = P r(P2 > 1 − P1 ) .

385

(19)

Denote by S1 = P r(P1 > 0.5) the sensitivity of D assuming that class ω1 is the positive class, and by
S2 = P r(P2 > 0.5) the sensitivity of D assuming that class ω2 is the positive class. Theng
AP (Dset) = S1 S2 + (1 − S1 )S2 AU C + S1 (1 − S2 )AU C= S1 S2 + (S1 + S2 − 2S1 S2 )AU C .

(20)

For the Bayes classifier D, whereby the labelling is done by the largest posterior probability, AU C > 0.5.
Therefore,g
AP (Dset) > S1 S2 + (S1 + S2 − 2S1 S2 ) × 0.5
390

=

1
i
(S1 + S2 ) = p = AP (Dset
).
2

22

(21)

Results for the USC data for the decision tree classifier
Table 4: Averaged partial accuracy AP and averaged total accuracy AT in % for the Baseline (B), Greedy (G) and the
Hungarian (H) set classifiers for the decision tree classifier. Symbol • after the value in column H indicates that H issignificantly different from G at p < 0.01. The highest accuracy for each dataset is indicated in boldface.
AP
Classifier

B

G

61.01

acute-inflammation
acute-nephritis

AT
H

B

G

63.06

63.23 −

6.50

7.60

7.60 −

100.00100.00100.00 −100.00100.00100.00 −100.00100.00100.00 −100.00100.00100.00 −

adult

76.34

79.90

79.95 −

28.10

34.80

35.00 −

annealing

90.64

91.60

91.99 −

52.10

56.10

57.50 −

arrhythmia

82.84

84.79

85.41 −

41.70

46.40

47.80 −

balance-scale

85.11

85.52

85.52 −

43.50

45.90

46.10 −

bank

64.79

71.92

71.94 −

18.60

23.90

24.70 −

blood

60.04

68.82

69.92 −

15.90

23.10

25.60 −

breast-cancer-wisc-diag

92.85

92.61

92.95 −

64.70

66.50

67.40 −

breast-cancer-wisc

94.26

94.34

94.32 −

70.50

72.50

72.40 −

breast-cancer

58.66

65.34

66.58 −

11.90

17.50

19.30 −

car

92.04

92.58

92.78 −

46.70

50.20

51.30 −

cardiotocography-10clases

74.96

74.96

74.77 −

0.50

0.60

0.60 −

cardiotocography-3clases

85.53

86.14

86.09 −

34.10

37.60

37.40 −

abaloneH

chess-krvk

73.36

74.25

74.48 •

0.00

0.10

0.10 −

chess-krvkp

98.99

99.04

99.09 −

94.70

95.30

95.70 −

congressional-voting

48.95

62.61

67.07 •

11.80

21.10

26.10 •

conn-bench-sonar-mines-ro

69.99

72.29

72.30 −

19.70

23.10

23.50 −

conn-bench-vowel-deterdin

81.38

81.22

81.60 •

1.70

1.80

1.90 −

connect-4

74.75

77.78

77.79 −

24.70

29.00

29.10 −

contrac

48.18

50.17

50.79 •

2.80

2.90

2.90 −

credit-approval

84.22

84.32

84.32 −

37.90

40.80

40.80 −

cylinder-bands

68.71

70.59

70.67 −

20.20

23.00

22.90 −

dermatology

96.86

96.81

96.93 −

73.40

74.70

74.90 −

ecoli

91.02

91.01

92.10 •

51.70

53.20

56.30 •

energy-y1

93.55

93.90

94.11 −

59.20

63.40

64.80 −

energy-y2

88.81

89.57

89.83 −

39.90

44.20

45.00 −

glass

73.44

75.24

75.70 −

23.10

26.80

27.90 −

haberman-survival

60.01

66.97

68.40 −

14.00

19.30

21.40 •

hayes-roth

61.75

65.71

66.39 −

15.50

19.50

20.30 −

heart-cleveland

68.21

73.01

73.63 •

19.70

24.40

25.40 •

heart-hungarian

76.13

78.80

79.00 −

26.80

31.20

31.90 −

heart-va

54.55

58.22

58.32 −

9.40

11.10

11.40 −

hill-valley

50.59

65.25

70.34 •

14.90

26.10

31.70 •

horse-colic

81.21

82.36

82.58 −

34.40

38.00

38.50 −

ilpd-indian-liver

52.41

63.11

65.28 −

11.60

19.70

22.60 −

image-segmentation

93.57

93.40

93.39 −

29.90

32.00

32.20 −

ionosphere

83.95

83.71

83.78 −

40.70

42.40

42.40 −

iris

92.99

92.73

92.97 −

60.40

62.20

63.20 −

led-display

70.21

70.25

70.20 −

0.10

0.10

0.10 −

Continued on next page23

Table 4 – continued from previous pageAPClassifierBG

letter

84.33

84.04

AT
H

B

G

84.03 −

0.00

0.00

0.00 −

H

low-res-spect

80.94

81.65

81.76 −

23.60

26.40

27.20 −

lymphography

75.82

78.33

78.61 −

27.30

32.00

33.10 −

magic

82.35

83.81

83.78 −

38.60

42.80

42.80 −

mammographic

83.16

84.03

84.27 −

37.10

41.50

42.20 •

miniboone

87.53

87.72

87.72 −

48.60

50.80

50.80 −

molec-biol-promoter

74.64

76.13

76.48 −

28.10

31.00

31.90 −

molec-biol-splice

89.73

89.55

89.45 −

45.30

47.40

47.40 −

monks-1

83.45

86.07

87.22 −

47.00

52.70

54.80 −

monks-2

58.44

67.65

69.38 −

13.60

22.70

25.10 −

monks-3

96.97

97.26

97.32 −

83.30

85.60

85.80 −

mushroom

100.00100.00100.00 −100.00100.00100.00 −musk-1

76.64

77.30

77.79 −

27.80

31.20

32.30 −

musk-2

90.16

90.58

90.64 −

56.70

60.20

60.30 −

nursery

98.36

98.54

98.57 −

83.90

86.10

86.30 −

oocytes-merluccius-nucleu

64.59

68.07

68.11 −

16.20

19.10

19.60 −

oocytes-merluccius-states

83.63

83.30

83.31 −

28.90

30.30

30.60 −

oocytes-trisopterus-nucle

69.67

71.35

71.48 −

18.30

20.10

20.30 −

oocytes-trisopterus-state

85.77

86.15

86.19 −

43.90

47.20

47.60 −

optical

88.81

88.44

88.47 −

5.70

6.20

6.30 −

ozone

57.82

66.25

66.89 −

16.00

21.60

22.70 −

page-blocks

84.40

85.49

86.00 •

26.20

29.30

30.10 −

pendigits

95.13

94.83

94.84 −

27.90

29.10

29.00 −

pima

69.17

72.39

72.77 −

20.20

24.50

25.10 −

planning

51.08

65.87

71.35 •

12.80

25.40

30.80 •

ringnorm

89.81

90.05

90.18 −

53.90

57.30

57.30 −

seeds

90.40

90.55

90.49 −

49.10

51.80

52.20 −

semeion

72.11

71.62

71.73 −

0.10

0.10

0.10 −

soybean

86.94

87.47

87.94 •

28.10

30.90

32.50 •

spambase

90.87

91.19

91.14 −

58.10

61.70

61.80 −

spect

65.84

68.54

69.22 −

15.50

18.90

19.60 −

spectf

70.13

71.11

70.51 −

21.70

23.30

23.70 −

statlog-australian-credit

54.57

57.59

58.14 −

10.30

11.80

12.30 −

statlog-german-credit

62.43

66.31

66.25 −

13.80

16.60

16.60 −

statlog-heart

74.53

76.02

75.77 −

24.10

27.20

27.30 −

statlog-image

95.05

94.96

95.02 −

40.20

41.80

41.90 −

statlog-landsat

82.25

82.04

82.19 −

8.60

9.10

9.50 −

statlog-shuttle

98.15

98.25

98.18 −

79.30

81.00

80.60 −
8.60 −

statlog-vehicle

70.48

71.81

72.00 −

7.30

8.40

steel-plates

71.98

72.57

72.72 −

0.80

1.10

1.10 −

synthetic-control

87.35

86.84

87.24 −

14.20

15.00

15.60 −

teaching

58.33

62.62

62.83 −

9.60

12.70

13.30 −

thyroid

97.59

97.57

97.55 −

82.80

84.20

84.00 −

tic-tac-toe

91.11

91.69

91.64 −

61.00

64.60

64.50 −

titanic

68.37

75.28

76.43 •

22.40

32.50

34.60 •

twonorm

84.40

84.54

84.62 −

40.30

42.90

43.10 −

vertebral-column-2clases

76.37

78.38

78.63 −

29.30

33.30

33.70 −

vertebral-column-3clases

74.11

75.90

75.77 −

16.70

19.50

19.60 −

wall-following

99.13

99.13

99.18 •

90.00

90.50

91.00 −

24

Continued on next page

Table 4 – continued from previous pageAPClassifier

395

B

G

waveform-noise

74.58

74.70

waveform

76.16

wine-quality-red

42.66

wine-quality-white

AT
H

B

G

74.97 −

14.20

15.30

15.70 −

H

76.40

76.68 −

17.10

18.20

18.40 −

46.18

46.54 −

1.00

1.30

1.30 −

42.51

44.73

46.16 •

0.20

0.20

0.30 −

wine

94.15

94.03

94.48 −

71.80

73.60

75.10 •

yeast

57.58

58.41

58.62 −

1.20

1.20

1.20 −

References[1] L. I. Kuncheva, Full-class set classification using the Hungarian algorithm, International Journal of Machine Learning andCybernetics 1 (1) (2010) 53–61. doi:DOI10.1007/s13042-010-0002-z.
[2] L. I. Kuncheva, A. S. Jackson, Who is missing? A new pattern recognition puzzle, in: Intenrational Conference on
400

Statistical, Structural and Syntactic Pattern Recognition (S+SSPR), Vol. LNCS 8621, Springer, Joensuu, Funland, 2014,
pp. 243–252.
[3] R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, 2nd Edition, John Wiley & Sons, NY, 2001.
[4] R. E. Slot, On the profit of taking into account the known number of objects per class in classification methods IT–25(1979) 484–488.

405[5] T. G. Dietterich, R. H. Lathrop, T. Lozano-Perez, Solving the multiple-instance problem with axis-parallel rectangles,
Artificial Intelligence 89 (1997) 31–71.
[6] J. Wang, J.-D. Zucker, Solving the multiple-instance problem: A lazy learning approach, in: In Proceedings 17th International Conference on Machine Learning, 2000, pp. 1119–1125.
[7] O. L. Mangasarian, E. W. Wild, Multiple instance classification via successive linear programming, Journal of Optimization

410

Theory and Applications 137 (2008) 555–568.
[8] Z. Fu, A. Robles-Kelly, J. Zhou, MILIS: multiple instance learning with instance selection, IEEE Transactions on PatternAnalysis and Machine Intelligence 33 (5) (2011) 958–977.
[9] X. Xu, Statistical learning in multiple instance problems, Master’s thesis, University of Waikato, Department of Computer
Science, New Zealand (2003).

415[10] X. Ning, G. Karypis, The set classification problem and solution methods, in: In Proceedings of SIAM Data Mining, 2009,
pp. 847–858.
[11] M. Pelillo, M. Refice, Learning compatibility coefficients for relaxation labeling processes, Pattern Analysis and MachineIntelligence, IEEE Transactions on 16 (9) (1994) 933–945.
[12] A. Rosenfeld, R. A. Hummel, S. Zucker, Scene labeling by relaxation operations, IEEE Transactions on Systems, Man

420

and Cybernetics SMC-6 (6) (1976) 420–433.
[13] L. K. McDowell, K. M. Gupta, D. W. Aha, Cautious inference in collective classification, in: In Processdings of AAAI,
2007, pp. 596–601.
[14] P. Sen, G. M. Namata, Bilgic, L. Getoor, B. Gallagher, T. Eliassi-Rad, Collective classification in network data, AI
Magazine 29 (2008) 93106.

425[15] Y. Amit, A. Trouvé, POP: patchwork of parts models for object recognition, International Journal of Computer Vision75 (2007) 267–282.
[16] R. Kaucic, A. G. A. Perera, G. B. J., Kaufhold, A. Hoogs, A unified framework for tracking through occlusions and acrosssensor gaps, in: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR, Vol. 1, 2005,
pp. 1063–1069.

25

430

[17] I. Haritaoglu, D. Harwood, L. S. Davis, W 4: Real-time surveillance of people and their activities, Pattern Analysis andMachine Intelligence, IEEE Transactions on 22 (8) (2000) 809–830.
[18] A. Mohan, C. Papageorgiou, T. Poggio, Example-based object detection in images by components, Pattern Analysis andMachine Intelligence, IEEE Transactions on 23 (4) (2001) 349–361.
[19] P. F. Felzenszwalb, D. P. Huttenlocher, Pictorial structures for object recognition, International Journal of Computer

435

Vision 61 (1) (2005) 55–79.
[20] B. Heisele, T. Serre, M. Pontil, T. Poggio, Component-based face detection, in: Computer Vision and Pattern Recognition,
2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, Vol. 1, IEEE, 2001, pp. I–657.
[21] T. Zhao, R. Nevatia, Tracking multiple humans in complex situations, Pattern Analysis and Machine Intelligence, IEEE
Transactions on 26 (9) (2004) 1208–1221.

440[22] X. Zhou, Y. Li, B. He, Game-theoretical occlusion handling for multi-target visual tracking, Pattern Recognition 46 (10)(2013) 2670–2684.
[23] C. Rasmussen, G. D. Hager, Probabilistic data association methods for tracking complex visual objects, Pattern Analysis
and Machine Intelligence, IEEE Transactions on 23 (6) (2001) 560–576.
[24] Y. Bar-Shalom, F. Daum, J. Huang, The probabilistic data association filter, Control Systems, IEEE 29 (6) (2009) 82–100.

445[25] K. Okuma, A. Taleghani, N. De Freitas, J. J. Little, D. G. Lowe, A boosted particle filter: Multitarget detection andtracking, in: Computer Vision-ECCV 2004, Springer, 2004, pp. 28–39.
[26] A. Dearden, Y. Demiris, O. Grau, Tracking football player movement from a single moving camera using particle filters,
in: Proceedings of CVMP-2006, IET Press, 2006, pp. 29–37.
[27] P. Konstantinova, A. Udvarev, T. Semerdjiev, A study of a target tracking algorithm using global nearest neighbor

450

approach, in: Proceedings of the International Conference on Computer Systems and Technologies (CompSysTech03),2003.
[28] R. Ardekani, A. Biyani, J. E. Dalton, J. B. Saltz, M. N. Arbeitman, J. Tower, S. Nuzhdin, S. Tavaré, Three-dimensional
tracking and behaviour monitoring of multiple fruit flies, Journal of The Royal Society Interface (2012) rsif20120547.
[29] J. N. Jover, M. Alcañiz-Raya, V. Gómez, S. Balasch, J. Moreno, V. G. Colomer, A. Torres, An automatic colour-based

455

computer vision algorithm for tracking the position of piglets, Spanish Journal of Agricultural Research 7 (3) (2009)535–549.
[30] M. Kashiha, C. Bahr, S. Ott, C. P. Moons, T. A. Niewold, F. O. Ödberg, D. Berckmans, Automatic identification ofmarked pigs in a pen using image pattern recognition, Computers and Electronics in Agriculture 93 (2013) 111–120.
[31] Y. Kamisugi, N. Furuya, K. Iijima, K. Fukui, Computer-aided automatic identification of rice chromosomes by image

460

parameters 1 (3) (1993) 189–196.
[32] D. Ming, J. Tian, Automatic pattern extraction and classification for chromosome images, Journal of Infrared Milli Terahz
Waves 31 (2010) 866–877.
[33] X. Wang, S. Li, H. Liu, M. Wood, W. R. Chen, B. Zheng, Automated identification of analyzable metaphase chromosomes
depicted on microscopic digital images, J Biomed Inform 41 (2) (2008) 264–271.

465[34] H. W. Kuhn, The Hungarian Method for the assignment problem, Naval Research Logistic Quarterly 2 (1955) 83–97.
[35] F. Bourgeois, J.-C. Lassalle, An extension of the Munkres algorithm for the assignment problem to rectangular matrices,
Communications ACM 14 (12) (1971) 802–804.
[36] C.-C. Chang, C.-J. Lin, LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems andTechnology 2 (2011) 27:1–27:27, software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.

470[37] M. Fernández-Delgado, E. Cernadas, S. Barro, D. Amorim, Do we need hundreds of classifiers to solve real world classification problems?, Journal of Machine Learning Research 15 (2014) 3133–3181.
[38] K. Bache, M. Lichman, UCI machine learning repository (2013).

26

URL http://archive.ics.uci.edu/ml[39] T. Fawcett, ROC graphs: Notes and practical considerations for researchers, Tech. Rep. HPL-2003-4, HP Labs, Palo Alto,475

http://www.hpl.hp.com/techreports/2003/HPL-2003-4.pdf (2003).

Vitae

Ludmila I. Kuncheva is a Professor of Computer Science at Bangor University, UK. Her interests include
pattern recognition, and specifically classifier ensembles. She has published two monographs and over 150
research papers. Lucy has won two Best Paper Awards (2006 IEEE TFS and 2003 IEEE TSMC.) She is a480

Fellow of IAPR.
Juan J. Rodrı́guez is an Associate Professor of Computer Science at University of Burgos, Spain. His interests
include data science, pattern recognition and specifically classifier ensembles.
Aaron S. Jackson is currently working toward his PhD degree in Computer Science at Nottingham University,
UK. His interests include pattern recognition, deep learning and computer vision.

27