# Ensemble pruning via an integer programming approach with diversity
constraints

Marcelo Antônio Mendes Bastos1 Humberto Brandão César de Oliveira2 Cristiano
Arbex Valle1

###### Abstract

Ensemble learning combines multiple classifiers in the hope of obtaining
better predictive performance. Empirical studies have shown that ensemble
pruning, that is, choosing an appropriate subset of the available classifiers,
can lead to comparable or better predictions than using all classifiers. In
this paper, we consider a binary classification problem and propose an integer
programming (IP) approach for selecting optimal classifier subsets. We propose
a flexible objective function to adapt to desired criteria of different
datasets. We also propose constraints to ensure minimum diversity levels in
the ensemble. Despite the general case of IP being NP-Hard, state-of-the-art
solvers are able to quickly obtain good solutions for datasets with up to
60000 data points. Our approach yields competitive results when compared to
some of the best and most used pruning methods in literature.

1Departamento de Ciência da Computação,
Universidade Federal de Minas Gerais,
Belo Horizonte, MG, Brasil
<EMAIL_ADDRESS>
2 Departamento de Ciência da Computação,
Universidade Federal de Alfenas,
Alfenas, MG, Brazil
<EMAIL_ADDRESS>
Keywords: ensemble learning, ensemble pruning, integer programming, diversity

##  1 Introduction

Ensemble learning is a popular technique in the domain of machine learning. An
ensemble is defined as the aggregation of multiple classifications into a
single final decision. It is generally accepted in literature that the
precision of an ensemble tends to improve when compared to the behaviour of
individual classifiers (Zhang et al., 2006).

Well known aproaches for efficiently generating ensembles include Bagging
(bootstrap aggregating) (Breiman, 1996) and Boosting (Freund and Schapire,
1997). The latter gave rise to popular variations such as Random Forests
(Breiman, 2001) and extreme gradient boosting (Chen and Guestrin, 2016). A
general feature of these approaches is that all classifiers are considered in
the aggregation. There are, however, theoretical and empirical studies which
have shown that pruning an ensemble by selecting a subset of the classifiers
can lead to comparable or better predictions (Lu et al., 2010; Zhang et al.,
2006).

In this work we tackle the ensemble pruning problem by introducing an integer
programming (IP) approach for choosing an optimal subset of binary
classifiers. Our formulation optimises a weighted function of the patterns in
the binary confusion matrix. This provides enough flexibility to ensure
suitable optimisation criteria dependent on the properties of the underlying
dataset. As our objective is performance-based we also introduce linear
constraints that ensure minimum diversity levels in the ensemble.

Despite several techniques for ensemble pruning having been previously
proposed, we believe that our approach contributes to the current knowledge in
the field. IP modelling is a flexible tool, adaptable to particularities of
different problems. One of the most important advantages in applying this tool
to ensemble pruning is being able to combine performance and diversity
criteria. Moreover an IP framework provides an exact method, as opposed to
most algorithms in literature which are generally suboptimal.

The general IP problem is NP-Hard, however decades of research in algorithmic
techniques have led to state-of-the-art solvers which are able to effectively
solve several industrial-sized problems. In this paper we show that with such
solvers we can find good solutions to relatively large problems in reasonable
computational times.

We compare our formulation to a full ensemble and six other well-known methods
in literature. We report competitive results for publicly available datasets
ranging from 195 to 60000 data points.

The remainder of this paper is organised as follows. In Section 2 we give a
brief overview of existing methods in ensemble learning. In Section 3 we
present our optimisation approach and in Section 4 we amend it to enforce
minimum diversity levels. Our computational experiments are shown in Section 5
and in Section 6 we present our concluding remarks.

##  2 Literature review

The first step in an ensemble process is to generate a set of distinct
classifiers that is hopefully precise and diverse. Highly correlated
classifiers may hinder the potential benefit of using an ensemble.

Several techniques for ensuring diversity in classifiers have been proposed
(Duin, 2002; Cruz et al., 2018). These include randomising classifiers, tuning
parameters (e.g. pruning level in decision trees) or exploring different
architectures (e.g. number of hidden layers in multi-layer perceptron neural
networks). Combining distinct classifier models into heterogeneous ensembles
is also a popular approach. Other diversification techniques include training
classifiers with different distributions of the training set (e.g. the
aforementioned Bagging and Boosting techniques) and with distinct subsets of
features.

The next step is selecting an appropriate subset of the available classifiers.
This selection can be static or dynamic. In dynamic selection, different
subsets are chosen for different data points. The reasoning is that certain
subsets may be more specialised in different parts of the feature space. For
more details we refer the reader to (Britto et al., 2014; Cruz et al., 2018).
Most works however apply static selection, where a single subset is chosen.
Static selection policies can be based on ranking, clusters and optimisation.

Ranking methods sort classifiers according to a fitness function. In general
they greedily increase the subset size. In Kappa pruning (Margineantu and
Dietterich, 1997), every pair of classifiers is sorted according to a
statistical measure of agreement. Pairs with the lowest agreement levels are
selected. Reordering techniques (Martínez-Muñoz and Suárez, 2006, 2007) in
bagging classifiers have been used to build subensembles of increasing size.
Tsoumakas et al. (2004) rank heterogeneous classifiers according to a
significance index. Dai and Han (2016) proposed a dynamic programming approach
to improve the computational efficiency of these methods.

Cluster methods first apply a clustering algorithm to separate classifiers
according to some similarity measure and then prune each cluster separately to
increase general diversity. Known clustering algorithms include k-means
(Lazarevic and Obradovic, 2001; Qiang et al., 2005), where similarity is based
on Euclidean distance, and hierarchical agglomerative clustering (Giacinto et
al., 2000), which employs probabilities. Different policies for choosing the
number of clusters (Giacinto et al., 2000; Lazarevic and Obradovic, 2001) have
also been suggested.

Several optimisation methods for ensemble pruning have also been proposed,
with most offering approximate solutions. The most popular method is hill
climbing, which has been applied with several different fitness functions.
Some are based on performance (Fan et al., 2002; Caruana et al., 2004) (e.g.
accuracy), others on diversity (Margineantu and Dietterich, 1997; Tang et al.,
2006; Partalas et al., 2008). Two examples of diversity-based fitness
functions are Complementariness (Martınez-Muñoz and Suárez, 2004) and
Concurrency (Banfield et al., 2005). Partalas et al. (2010) proposed the
Uncertainty Weighted Accuracy, which as the name suggests takes into account
uncertainty by weighting differently the importance of data points considered
“easy” and “hard” to predict. Partalas et al. (2006) employed a reinforcement
learning-based approach for a greedy method based on diversity. Zhang et al.
(2006) and Xu et al. (2012) proposed semi-definite programming approaches
which consider trade-offs between accuracy and diversity.

The last step in the procedure is combining classifiers into a single
prediction, which is usually done through majority voting. For further details
we refer the reader to (Kittler et al., 1998).

##  3 Formulation

Consider a binary classification problem where data points belong to classes 1
(positive) or 0 (negative). In this section we present an IP formulation for
choosing an optimal subset of binary classifiers.

Let $\mathcal{K}=\\{1,\ldots,K\\}$ be the set of classifiers. Let
$\mathcal{N}_{0}=\\{1,\ldots,N_{0}\\}$ and
$\mathcal{N}_{1}=\\{1,\ldots,N_{1}\\}$ be the sets of negative and positive
data points respectively, with $N=N_{0}+N_{1}$ being the total number of data
points. Consider a $N_{1}\times K$ matrix $B$ where $\beta_{ik}=1$ if
classifier $k\in\mathcal{K}$ correctly classified data point
$i\in\mathcal{N}_{1}$ as positive, $\beta_{ik}=0$ if it mistakenly classified
$i$ as negative. Accordingly consider a $N_{0}\times K$ matrix $A$ where
$\alpha_{jk}=0$ if classifier $k\in\mathcal{K}$ correctly classified data
point $j\in\mathcal{N}_{0}$ as negative, $\alpha_{jk}=1$ if $j$ was mistakenly
classified as positive.

Suppose $\mathcal{S}\subseteq\mathcal{K}$ is a set of $S$ classifiers selected
to compose a given pruned ensemble. For any data point
$i\in\mathcal{N}_{1},\sum_{s\in\mathcal{S}}\beta_{is}$ is the number of
correct positive classifications within $\mathcal{S}$. Accordingly, for any
data point $j\in\mathcal{N}_{0},\sum_{s\in\mathcal{S}}\alpha_{js}$ represents
the number of (wrong) positive classifications within $\mathcal{S}$.

We define a threshold $0\leq L\leq S$ such that for a given data point
$i\in\mathcal{N}_{1}$, $\sum_{s\in\mathcal{S}}\beta_{is}>L$ implies that the
ensemble classifies $i$ as positive. If $\sum_{s\in\mathcal{S}}\beta_{is}\leq
L$, then $i$ is classified by the ensemble as negative. Similarly for
$j\in\mathcal{N}_{0}$, $\sum_{s\in\mathcal{S}}\alpha_{js}>L$ implies a
positive ensemble classification and $\sum_{s\in\mathcal{S}}\alpha_{js}\leq L$
implies a negative ensemble classification. For instance, if $S=10$ and $L=5$,
then the ensemble classifies a data point as positive if at least 6 individual
classifications are positive. If 5 or less are positive, then the ensemble
classifies that data point as negative.

In our formulation we let the optimisation define both $\mathcal{S}$ and $L$.
Hence we include $L$ as a general integer variable representing the
classification threshold and binary variables $x_{k}=1$ if classifier
$k\in\mathcal{K}$ is chosen to compose the ensemble ($x_{k}=0$ otherwise).

|  | Predicted
---|---|---
|  | 1 | 0
Actual | 1 | $T^{+}$ | $F^{-}$
0 | $F^{+}$ | $T^{-}$
Table 1: Binary classification confusion matrix

Consider the binary confusion matrix given in Table 1, where
$T^{+},F^{-},T^{-}$ and $F^{+}$ are the total number of classifications of
each possible pattern. For each patterns we assign weights
$W_{T}^{+},W_{T}^{-},W_{F}^{+},W_{F}^{-}\in\mathbb{R}$, and the objective
function is defined by the weighted sum
$W_{T}^{+}T^{+}+W_{F}^{-}F^{-}+W_{T}^{-}T^{-}+W_{F}^{+}F^{+}$.

For modelling this weighted sum we define binary variables
$t^{+}_{i},f^{-}_{i}$ if the ensemble classification of $i\in\mathcal{N}_{1}$
is respectively a true positive or false negative. Similarly we define binary
variables $t^{-}_{j},f^{+}_{j}$ if the ensemble classification of
$j\in\mathcal{N}_{0}$ is a true negative or false positive. The IP formulation
that optimises a weighted sum of the patterns in the binary confusion matrix
is given below:

$\max\sum_{i=1}^{N_{1}}(W_{T}^{+}t^{+}_{i}+W_{F}^{-}f^{-}_{i})+\sum_{j=1}^{N_{0}}(W_{T}^{-}t^{-}_{j}+W_{F}^{+}f^{+}_{j})$
(1)

subject to

$\displaystyle(L+1)-\sum_{k=1}^{K}x_{k}\;\beta_{ik}$
$\displaystyle\leq(K+1)(1-t^{+}_{i}),$ $\displaystyle\forall
i\in\mathcal{N}_{1}$ (2) $\displaystyle\sum_{k=1}^{K}x_{k}\;\beta_{ik}-L$
$\displaystyle\leq(K+1)t^{+}_{i},$ $\displaystyle\forall i\in\mathcal{N}_{1}$
(3) $\displaystyle t^{+}_{i}+f^{-}_{i}$ $\displaystyle=1,$
$\displaystyle\forall i\in\mathcal{N}_{1}$ (4)
$\displaystyle\sum_{k=1}^{K}x_{k}\;\alpha_{jk}-L$ $\displaystyle\leq
K(1-t^{-}_{j}),$ $\displaystyle\forall j\in\mathcal{N}_{0}$ (5)
$\displaystyle(L+1)-\sum_{k=1}^{K}x_{k}\;\alpha_{jk}$ $\displaystyle\leq
Kt^{-}_{j},$ $\displaystyle\forall j\in\mathcal{N}_{0}$ (6) $\displaystyle
f^{+}_{j}+t^{-}_{j}$ $\displaystyle=1,$ $\displaystyle\forall
j\in\mathcal{N}_{0}$ (7) $\displaystyle x_{k}$ $\displaystyle\in\mathbb{B}$
$\displaystyle\forall k\in\cal{K}$ (8) $\displaystyle t^{+}_{i},f^{-}_{i}$
$\displaystyle\in\mathbb{B}$ $\displaystyle\forall i\in\mathcal{N}_{1}$ (9)
$\displaystyle t^{-}_{j},f^{+}_{j}$ $\displaystyle\in\mathbb{B}$
$\displaystyle\forall j\in\mathcal{N}_{0}$ (10) $\displaystyle 0\leq L$
$\displaystyle\leq K,$ (11) $\displaystyle L$ $\displaystyle\in\mathbb{Z}$
(12)

Constraints (2) ensure that a positive data point $i\in\mathcal{N}_{1}$ has
$t^{+}_{i}=1$ if the number of individual positive classifications exceeds
$L$. Conversely, constraints (3) ensure that $t^{+}_{i}=0$ if the number of
individual positive classifications is no more than $L$. Constraints (4)
ensure that either $t^{+}_{i}=1$ or $f^{-}_{i}=1$. Constraints (5) guarantee
that a negative data point $j\in\mathcal{N}_{0}$ has $t^{-}_{j}=0$ if the
number of positive classifications exceeds $L$. Otherwise, constraints (6)
make sure that $t^{-}_{j}=1$. Constraints (7) ensure that either $f^{+}_{j}=1$
or $t^{-}_{j}=1$. Constraints (8-12) define variables bounds.

###  3.1 Objective function

For some classification problems, it may be desirable to optimise some
patterns instead of others. For instance, in an investment decision, investing
in the wrong project may cause bankruptcy while not investing in a promising
project may be seen as a regretful but acceptable lost opportunity. In this
case prioritising the minimisation of $F^{+}$ is desirable. The weights in
Equation (1) provide flexibility for defining optimisation criteria depending
on the characteristics of the dataset at hand (such as being highly
imbalanced). A few examples are outlined below.

Accuracy is defined as $\frac{T^{+}+T^{-}}{N}$. As $N$ is constant we can
maximise accuracy by defining weights $W_{T}^{+}=W_{T}^{-}=1$ and
$W_{F}^{+}=W_{F}^{-}=0$. Notice that if we choose this objective then
constraints (3) and (6) are redundant as maximising positive weights
$W_{T}^{+}$ and $W_{T}^{-}$ ensure that $t^{+}_{i}=1$ and $t^{-}_{i}=1$ if
allowed by constraints (2) and (5). Similarly recall is defined as
$\frac{T^{+}}{T^{+}+F^{-}}=\frac{T^{+}}{N_{1}}$ and can be maximised by
setting $W_{T}^{+}=1$ and $W_{T}^{-}=W_{F}^{+}=W_{F}^{-}=0$ (with constraints
(3) being redundant).

Now consider $\theta=\frac{N_{1}}{N}$ as the dataset imbalance level. If, for
instance, $\theta\leq 1-\epsilon$ for small $\epsilon$, a high accuracy can be
achieved by classifying every data point as positive. For imbalanced datasets
a possibly useful configuration of objective function (1) is by setting
weights $W_{T}^{+}=(1-\theta)$, $W_{T}^{-}=\theta$ and
$W_{F}^{+}=W_{F}^{-}=0$.

##  4 Diversity

As mentioned before many ensemble pruning algorithms employ diversity
criteria. Our proposed formulation optimises a performance measure, and in
this section we introduce a way to control diversity with linear constraints.

We consider a diversity measure called Pairwise Failure Crediting (PFC),
proposed originally by Chandra and Yao (2006), chosen due to satisfactory
performance in imbalanced datasets (Bhowan et al., 2012; Fernandes et al.,
2015). PFC measures how diverse an individual classifier is from the remaining
classifiers in the ensemble.

PFC is calculated as follows. For each classifier $k$, we compute a failure
pattern (FP). A FP is a string of 0’s and 1’s with length $N$. A ‘0’ in the
string means that the classifier failed to correctly predict the corresponding
data point and a ‘1’ means that it predicted the data point correctly
(irrespective of its real value). Once we have all failure patterns we take
any two classifiers $k$ and $l$ and calculate their Hamming distance. The
Hamming distance between same-length strings is the number of different
characters in the same positions. For example, if
$\text{FP}_{k}=\\{0011011101\\}$ and $\text{FP}_{l}=\\{0110001110\\}$, the
Hamming distance between $k$ and $l$ is 5 (characters 2, 4, 6, 9 and 10
differ). Next, we sum all failures by both classifiers - that is, we sum the
number of zeros in both strings which, in the example, is 9. The failure
credit (FC) between $k$ and $l$ is obtained by dividing the Hamming distance
by the sum of failures. In the example, $\text{FC}_{kl}=5/9$. For every pair
$k,l\in\mathcal{K}$ we compute $\text{FC}_{kl}$.

Consider again $\mathcal{S}$ as a set of $S\leq K$ classifiers that are
selected to compose an ensemble. We assume without loss of generality that
classifiers in $\mathcal{S}$ are indexed by $k=1,\ldots,S$. Their PFC values
are given by:

$\displaystyle\text{PFC}_{k}$ $\displaystyle=\frac{\sum_{l=1,l\neq
k}^{S}\text{FC}_{kl}}{S-1}$ $\displaystyle k\in\cal{S}$

A (maximum) value of 1 in $\text{PFC}_{k}$ means that $k$ classifies all data
points differently from every other classifier in the ensemble, and a
(minimum) value of 0 means that $k$ is identical to all other classifiers.
Both extreme cases imply that all other classifiers are identical among
themselves.

For ensuring minimum desired diversity levels, we propose two approaches: (i)
the minimum PFC value of any individual classifier is at least a certain
threshold $0\leq\tau\leq 1$ in order to prevent very similar pairs of
classifiers and (ii) the average PFC value of the ensemble must be at least a
certain threshold $0\leq\gamma\leq 1$ to ensure an overall good level of
diversity. Clearly we must have $\gamma\geq\tau$.

We add the following new decision variables. Let $y_{kl}=1$ if both
classifiers $k$ and $l$ have been selected to be part of the ensemble, and
$y_{kl}=0$ if at most one of $k$ and $l$ is chosen to compose the ensemble.
This adds $\binom{K}{2}$ extra variables (for every possible pair $k,l$). For
simplicity, both $y_{kl}$ and $y_{lk}$ denote the exact same variable. The
following constraints ensure that $y_{kl}$ takes the correct values:

$\displaystyle y_{kl}$ $\displaystyle\geq x_{k}+x_{l}-1$ $\displaystyle\forall
k,l\in\mathcal{K},k<l$ (13) $\displaystyle y_{kl}$ $\displaystyle\leq x_{k}$
$\displaystyle\forall k,l\in\mathcal{K},k<l$ (14) $\displaystyle y_{kl}$
$\displaystyle\leq x_{l}$ $\displaystyle\forall k,l\in\mathcal{K},k<l$ (15)
$\displaystyle y_{kl}$ $\displaystyle\geq 0$ $\displaystyle\forall
k,l\in\mathcal{K},k<l$ (16)

Notice that there is no need for the $y_{kl}$ variables to be binary. As both
$x_{k}$ and $x_{l}$ are binary, $y_{kl}$ must have integer values in any
integer solution.

We can then rewrite the PFC equation using variables $x_{k}$ and $y_{kl}$:

$\displaystyle\text{PFC}_{k}$ $\displaystyle=\frac{\sum_{l=1,l\neq
k}^{K}\text{FC}_{kl}\;y_{kl}}{\sum_{m=1}^{K}x_{m}-1}$ $\displaystyle\forall
k\in\mathcal{K}$

The term $\sum_{m=1}^{K}x_{m}$ is the cardinality of the ensemble and any non-
selected classifier $k$ (with $x_{k}=0$) has a PFC value of 0 (as all
$y_{kl}=0,l\neq k$).

The following linear constraints ensure that every classifier has a minimum
PFC value of $\tau$:

$\displaystyle\sum_{\begin{subarray}{c}l=1\\\ l\neq
k\end{subarray}}^{K}\text{FC}_{kl}\;y_{kl}$
$\displaystyle\geq\tau\Big{(}\sum_{m=1}^{K}x_{m}-1\Big{)}-K\tau(1-x_{k})$
$\displaystyle\forall k\in\mathcal{K}$ (17)

The term $K\tau(1-x_{k})$ ensures that the constraints above are only enforced
if classifier $k$ is chosen to compose the ensemble.

The following nonlinear constraint ensures that the average PFC of the
ensemble is at least $\gamma$:

$\displaystyle\frac{1}{\sum_{m=1}^{K}x_{m}}\;\frac{\sum_{k=1}^{K}\sum_{l=1,l\neq
k}^{K}\text{FC}_{kl}\;y_{kl}}{\sum_{m=1}^{K}x_{m}-1}$
$\displaystyle\geq\gamma$ (18)

Observe that in Equation (18) the FC value of every pair is added twice. We
use this fact to linearise this expression. For a given subset $\mathcal{S}$,
the average PFC $\mu_{\text{PFC}}$ is given by:

$\displaystyle\mu_{\text{PFC}}$
$\displaystyle=\frac{1}{S}\sum_{k=1}^{S}\frac{\sum_{l=1,l\neq
k}^{S}\text{FC}_{kl}}{S-1}$
$\displaystyle=\frac{1}{S(S-1)}\sum_{k=1}^{S}\sum_{\begin{subarray}{c}l=1\\\
l\neq k\end{subarray}}^{S}\text{FC}_{kl}$
$\displaystyle=\frac{2}{S(S-1)}\sum_{k=1}^{S-1}\sum_{l=k+1}^{S}\text{FC}_{kl}$
$\displaystyle=\frac{1}{\binom{S}{2}}\sum_{k=1}^{S-1}\sum_{l=k+1}^{S}\text{FC}_{kl}=\mu_{\text{FC}}$

where $\mu_{\text{FC}}$ denotes the average FC value of all pairs in the
ensemble. We conclude that $\mu_{FC}=\mu_{PFC}$, that is, the average PFC
among all classifiers in the ensemble is equal to the average FC among all
pairs.

If $S$ classifiers are selected in the ensemble, then the number of $y_{kl}$
variables that take value 1 is exactly $\binom{S}{2}$. Therefore we can ensure
that the average PFC value is at least $\gamma$ with the following linear
constraint:

$\displaystyle\sum_{k=1}^{K-1}\sum_{l=k+1}^{K}\text{FC}_{kl}\;y_{kl}$
$\displaystyle\geq\gamma\sum_{k=1}^{K-1}\sum_{l=k+1}^{K}y_{kl}$ (19)

The expanded formulation with minimum diversity levels is given by maximising
(1) subject to (2)-(17) and (19). It requires $\binom{K}{2}$ extra variables
and a similar number of extra constraints, which could lead it to be more
computationally demanding. However we observed empirically in Section 5.3 that
the inclusion of such constraints causes a negligible decrease in solution
quality.

##  5 Computational experiments

In this section we outline the computational experiments used to evaluate the
proposed formulation. We used 9 publicly available datasets, outlined in Table
2111All datasets used in this paper can be found at the UCI Machine Learning
Repository (Lichman, 2021), and ranging from $N=195$ to $N=60000$. We also
include a column with the value of the imbalance parameter $\theta$.

###  5.1 Description of the experiments

We prepared 10 different heterogeneous classifier models. Each model was
instantiated a number of times with different random seeds and parameters. We
set $K$ as multiples of 10 in order to have an equal number of instantiations
of each classifier. For instance, if $K=60$, we have 6 classifiers of each
model. In our experiments, reported below, we used $K=\\{40,60,80,100\\}$.
Each classifier produces, as output, a probability of a data point being
positive. This probability is rounded to define matrices $A$ and $B$. A more
thorough description of the classifiers can be found in the supplementary
material accompanying this paper.

For evaluating performance we used a stratified 10-fold cross-validation
procedure. The $N$ data points are initially shuffled randomly and the dataset
is split into 10 folds. At each iteration, one of the folds is left out as an
independent set (unseen by the algorithms). The results presented below are
based solely in this set. The other 9 folds, comprising 90% of the original
dataset, are joined and further split into two sets: a training set,
containing 63% of the data points, is used to optimise the individual
classifiers. A validation set, comprising the remaining 27% data points, is
used to optimise the ensemble algorithms.

The procedure above is repeated 10 times: in each we vary the random seeds
required to both shuffle the dataset and initialise the individual
classifiers. For each value of $K$ and for each instance shown in Table 2, we
run 100 experiments: 10 random initialisations $\times$ 10 folds. For ensuring
reproducibility of our results, we have made all necessary data publicly
available. A link can be found in the supplementary material.

Table 2: Selected datasets from the UCI Machine Learning Repository (Lichman, 2021) Identifier | Dataset name | Features | $N$ | $N_{0}$ | $N_{1}$ | $\theta$
---|---|---|---|---|---|---
PRK |  Parkinsons | 23 | 195 | 48 | 147 | 0.77
MSK |  Musk (Version 1) | 168 | 476 | 269 | 207 | 0.44
BCW |  Breast Cancer Wisconsin | 32 | 569 | 357 | 212 | 0.37
QSR |  QSAR biodegradation | 41 | 1055 | 356 | 699 | 0.66
DRD |  Diabetic Retinopathy Debrecen | 20 | 1151 | 540 | 611 | 0.53
SPA |  Spambase | 57 | 4601 | 2788 | 1813 | 0.39
DEF |  Default of credit card clients | 24 | 30000 | 23364 | 6636 | 0.22
BMK |  Bank Marketing | 21 | 41188 | 36548 | 4640 | 0.11
APS |  APS Failure at Scania Trucks | 171 | 60000 | 59000 | 1000 | 0.02

###  5.2 Benchmarks

To evaluate our formulation, we compare it to seven other approaches: Full
(non-pruned) Ensemble (FE), Reduced-Error Prunning with Backfitting (Friedman
and Stuetzle, 1981) (hereby Backfitting or BFT), Kappa pruning (Margineantu
and Dietterich, 1997) and four different hill climbing based methods. Due to
space constraints we report here only results for only four approaches. The
full results are available in the supplementary material accompanying this
paper. All benchmarks classify data points based on majority voting.

Backfitting aims to maximise accuracy by following a greedy approach with
revision. Initially, the classifier subset $S$ is empty. At each iteration,
the algorithm adds to $S$ a classifier $s$ such that the accuracy of
$S\cup{s}$ is maximised. This process is repeated until a predefined number
$M$ of classifiers is added to $S$. Ties are broken arbitrarily. Whenever a
classifier is added, the greedy choice is revised through a local search
procedure. Each classifier in the ensemble is iteratively replaced by another
previously left out. If the overall accuracy is improved, the method starts
again with the new subset $S$. The local search stops after 100 iterations or
whenever no classifier is able to improve the solution, whichever happens
first. Backfitting requires the ensemble subset size to be fixed. For a fairer
comparison, we varied $M$ within 20% and 80% of $K$. The best in-sample
results are used to evaluate the independent set.

Kappa pruning follows a similar procedure, but with two notable differences:
there is no revision of the greedy choice and it optimises the
$\kappa$-statistic (Cohen, 1960), a diversity measure of statistical agreement
between any two classifiers. Both Backfitting and Kappa pruning require the
ensemble subset size to be fixed. For a fairer comparison, we varied $M$
within 20% and 80% of $K$. The best in-sample results are used to evaluate the
independent set.

The other benchmarks use the forward version of the hill climbing search
algorithm, and they differ only in the selected fitness function. In all four
methods, the first iteration selects the individual classifier with maximum
accuracy, regardless of the fitness function chosen. In the following
iterations, classifiers are greedily added so as to maximise the selected
fitness. This process is repeated until all classifiers are added to $S$. In
the end, the chosen ensemble is the one with the best accuracy over all the
ensembles iteratively created. As opposed to the other benchmarks, direct hill
climbing does not define the ensemble size a priori. The fitness functions
chosen are the same as tested by Partalas et al. (2010): Accuracy,
Complementariness (Martınez-Muñoz and Suárez, 2004), Concurrency (Banfield et
al., 2005) and Uncertainty Weighted Accuracy (Partalas et al., 2010). We refer
to them as HC-ACC, HC-CON, HC-COM and HC-UWA.

In the experiments reported below we compare our formulation to BFT, two hill
climbing methods, HC-CON and HC-UWA (which had a better performance when
compared to HC-ACC and HC-COM) and FE (Full Ensemble). The complete set of
results is reported in the supplementary material. All algorithms are allowed
to run for a maximum of 5 minutes.

###  5.3 Solving the formulation

0-1 IP is notoriously computationally difficult. Its feasibility version is
one of Karp’s 21 NP-complete problems (Karp, 1972). Modern day solvers however
can effectively solve large instances of several different IP problems by
employing a combination of techniques (such as branch-and-bound and cutting
planes). From an optimisation point of view, important considerations are (i)
up to what size are modern solvers able to optimally solve our formulation
within a reasonable time limit, and (ii) if the limit is reached prior to
proving optimality, how large are the optimality gaps and how quickly does the
solver find “good enough” solutions?

While searching for these answers and studying traditional IP techniques in
order to improve computational performance is within the scope of our current
and future work, we have opted, due to limited space, to refrain from further
discussing them. We however observed in practice that, with a time limit of
only 5 minutes, we were able to either optimally solve or terminate the
algorithm with small optimality gaps for all instances. These gaps are shown
in Table 3.

Table 3: Average optimality gaps and corresponding standard deviations (in %). Instance | 27% of $N$ | No diversity | With diversity
---|---|---|---
Avg. | Std. | Avg. | Std.
PRK | 26 | 0.0 | 0.0 | 0.0 | 0.0
BCW | 129 | 0.0 | 0.0 | 0.0 | 0.0
MSK | 154 | 0.0 | 0.0 | 0.0 | 0.0
QSR | 285 | 0.0 | 0.0 | 0.0 | 0.1
DRD | 311 | 4.3 | 2.0 | 6.1 | 1.8
SPA | 1242 | 0.0 | 0.0 | 0.2 | 0.2
DEF | 8100 | 6.7 | 0.4 | 6.9 | 0.4
BMK | 11121 | 5.4 | 0.3 | 5.5 | 0.2
APS | 16200 | 0.1 | 0.0 | 0.1 | 0.0

This table summarises the average gaps and their respective standard
deviations for experiments reported below in Table 4 with $K=100$. The “No
diversity” column corresponds to F1 in that table, and only constraints
(2)-(12) are used. The “With diversity” column corresponds to F3, which uses
constraints (2)-(17) and (19). The largest instance, APS, had average gaps of
only 0.1% in both cases. The hardest instance was DEF (6.7% and 6.9%). The
only case where a difference was notable was for the DRD instance (4.3% and
6.1%).

In our view, even the hardest instances were still relatively close to
optimality considering the short computational time. For this reason, in all
computational experiments reported below, we set a time limit of 5 minutes. If
the time limit is reached, we halt the solver and retrieve the best solution
available at that point. We employed CPLEX 12.8 (CPLEX Optimizer, 2021) with
default parameters as the IP solver and we run all experiments in an Intel
Core(TM) I7-7700 @ 3.60GHz with 32GB of RAM, using 8 cores and having Linux as
the operating system.

###  5.4 Accuracy

In our first suite of experiments we set weights $W_{T}^{+}=W_{T}^{-}=1$ and
$W_{F}^{+}=W_{F}^{-}=0$, that is, we seek to maximise classification accuracy
regardless of the dataset imbalance level. To evaluate both the formulation
introduced in Section 3 and the diversity constraints introduced in Section 4,
we propose three different configurations.

In the first we employ only constraints (2)-(12), without enforcing diversity
- we refer to this configuration as F1. The other two configurations, F2 and
F3, enforce minimum diversity levels in the hope of preventing possible
overfitting of the training and validation sets. In F2 we set $\tau=0$ and
$\gamma=\frac{\text{PFC}_{\text{min}}+\text{PFC}_{\text{avg}}}{2}$, where
$\text{PFC}_{\text{min}}$ and $\text{PFC}_{\text{avg}}$ are the minimum
individual PFC among all classifiers and the average PFC value of the full
ensemble. So in F2 we only constrain the overall average PFC value. In F3 we
also set $\tau=\text{PFC}_{\text{min}}$, so restricting individual PFC values
as well as the average PFC.

Table 4: Out-of-sample average accuraries and standard deviations. Dataset | $K$ | F1 | F2 | F3 | BFT | HC-CON | HC-UWA | FE
---|---|---|---|---|---|---|---|---
Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std.
PRK | 40 | 0.9066 | 0.0145 | 0.9134 | 0.0136 | 0.9114 | 0.0130 | 0.9041 | 0.0156 | 0.9118 | 0.0152 | 0.9098 | 0.0183 | 0.9014 | 0.0066
| 60 | 0.9036 | 0.0124 | 0.9089 | 0.0103 | 0.9084 | 0.0113 | 0.8999 | 0.0146 | 0.9083 | 0.0176 | 0.9089 | 0.0195 | 0.8994 | 0.0088
| 80 | 0.9051 | 0.0144 | 0.9052 | 0.0124 | 0.9056 | 0.0131 | 0.9015 | 0.0084 | 0.9048 | 0.0167 | 0.9129 | 0.0223 | 0.9004 | 0.0091
| 100 | 0.9036 | 0.0154 | 0.9070 | 0.0202 | 0.9042 | 0.0183 | 0.9020 | 0.0080 | 0.9089 | 0.0174 | 0.9120 | 0.0213 | 0.8959 | 0.0092
BCW | 40 | 0.9664 | 0.0051 | 0.9689 | 0.0052 | 0.9690 | 0.0054 | 0.9652 | 0.0058 | 0.9680 | 0.0032 | 0.9671 | 0.0050 | 0.9632 | 0.0058
| 60 | 0.9676 | 0.0043 | 0.9701 | 0.0036 | 0.9703 | 0.0038 | 0.9671 | 0.0056 | 0.9696 | 0.0045 | 0.9680 | 0.0040 | 0.9629 | 0.0056
| 80 | 0.9643 | 0.0057 | 0.9673 | 0.0032 | 0.9673 | 0.0032 | 0.9660 | 0.0049 | 0.9710 | 0.0048 | 0.9701 | 0.0049 | 0.9629 | 0.0051
| 100 | 0.9618 | 0.0052 | 0.9676 | 0.0036 | 0.9676 | 0.0040 | 0.9673 | 0.0047 | 0.9710 | 0.0052 | 0.9692 | 0.0049 | 0.9627 | 0.0056
MSK | 40 | 0.9109 | 0.0110 | 0.9165 | 0.0093 | 0.9127 | 0.0090 | 0.9117 | 0.0122 | 0.9238 | 0.0092 | 0.9192 | 0.0126 | 0.8896 | 0.0100
| 60 | 0.9119 | 0.0086 | 0.9129 | 0.0092 | 0.9115 | 0.0091 | 0.9083 | 0.0136 | 0.9230 | 0.0103 | 0.9177 | 0.0114 | 0.8869 | 0.0097
| 80 | 0.9192 | 0.0097 | 0.9208 | 0.0078 | 0.9208 | 0.0076 | 0.9163 | 0.0117 | 0.9291 | 0.0090 | 0.9207 | 0.0096 | 0.8894 | 0.0099
| 100 | 0.9196 | 0.0066 | 0.9192 | 0.0075 | 0.9188 | 0.0085 | 0.9098 | 0.0135 | 0.9299 | 0.0081 | 0.9215 | 0.0077 | 0.8885 | 0.0096
QSR | 40 | 0.8740 | 0.0041 | 0.8731 | 0.0038 | 0.8742 | 0.0047 | 0.8719 | 0.0046 | 0.8734 | 0.0049 | 0.8733 | 0.0040 | 0.8706 | 0.0033
| 60 | 0.8755 | 0.0056 | 0.8756 | 0.0045 | 0.8740 | 0.0055 | 0.8710 | 0.0050 | 0.8736 | 0.0077 | 0.8725 | 0.0051 | 0.8692 | 0.0039
| 80 | 0.8715 | 0.0047 | 0.8728 | 0.0047 | 0.8740 | 0.0033 | 0.8747 | 0.0045 | 0.8731 | 0.0062 | 0.8747 | 0.0055 | 0.8706 | 0.0025
| 100 | 0.8722 | 0.0054 | 0.8757 | 0.0027 | 0.8732 | 0.0042 | 0.8729 | 0.0050 | 0.8724 | 0.0040 | 0.8738 | 0.0060 | 0.8705 | 0.0028
DRD | 40 | 0.7401 | 0.0060 | 0.7405 | 0.0091 | 0.7389 | 0.0075 | 0.7415 | 0.0080 | 0.7418 | 0.0077 | 0.7467 | 0.0070 | 0.7086 | 0.0080
| 60 | 0.7458 | 0.0114 | 0.7462 | 0.0096 | 0.7448 | 0.0104 | 0.7475 | 0.0100 | 0.7480 | 0.0086 | 0.7497 | 0.0068 | 0.7110 | 0.0077
| 80 | 0.7449 | 0.0063 | 0.7412 | 0.0054 | 0.7437 | 0.0068 | 0.7464 | 0.0060 | 0.7501 | 0.0065 | 0.7492 | 0.0070 | 0.7094 | 0.0078
| 100 | 0.7401 | 0.0083 | 0.7459 | 0.0054 | 0.7442 | 0.0065 | 0.7441 | 0.0065 | 0.7486 | 0.0079 | 0.7516 | 0.0056 | 0.7114 | 0.0076
SPA | 40 | 0.9529 | 0.0014 | 0.9534 | 0.0013 | 0.9534 | 0.0013 | 0.9529 | 0.0008 | 0.9535 | 0.0012 | 0.9523 | 0.0011 | 0.9476 | 0.0010
| 60 | 0.9533 | 0.0013 | 0.9542 | 0.0015 | 0.9537 | 0.0017 | 0.9535 | 0.0014 | 0.9547 | 0.0014 | 0.9534 | 0.0012 | 0.9469 | 0.0007
| 80 | 0.9538 | 0.0018 | 0.9536 | 0.0020 | 0.9536 | 0.0014 | 0.9532 | 0.0014 | 0.9554 | 0.0016 | 0.9536 | 0.0018 | 0.9468 | 0.0008
| 100 | 0.9535 | 0.0018 | 0.9538 | 0.0016 | 0.9537 | 0.0016 | 0.9530 | 0.0014 | 0.9557 | 0.0012 | 0.9537 | 0.0015 | 0.9467 | 0.0006
DEF | 40 | 0.8206 | 0.0005 | 0.8205 | 0.0005 | 0.8204 | 0.0005 | 0.8206 | 0.0004 | 0.8205 | 0.0005 | 0.8211 | 0.0004 | 0.8207 | 0.0004
| 60 | 0.8205 | 0.0005 | 0.8204 | 0.0005 | 0.8206 | 0.0003 | 0.8207 | 0.0003 | 0.8204 | 0.0004 | 0.8211 | 0.0004 | 0.8205 | 0.0006
| 80 | 0.8203 | 0.0006 | 0.8206 | 0.0006 | 0.8206 | 0.0008 | 0.8203 | 0.0004 | 0.8206 | 0.0004 | 0.8212 | 0.0003 | 0.8203 | 0.0004
| 100 | 0.8202 | 0.0004 | 0.8200 | 0.0003 | 0.8205 | 0.0006 | 0.8206 | 0.0004 | 0.8205 | 0.0004 | 0.8213 | 0.0003 | 0.8201 | 0.0004
BMK | 40 | 0.9178 | 0.0004 | 0.9171 | 0.0006 | 0.9170 | 0.0006 | 0.9166 | 0.0006 | 0.9168 | 0.0007 | 0.9173 | 0.0005 | 0.9143 | 0.0007
| 60 | 0.9175 | 0.0005 | 0.9173 | 0.0006 | 0.9173 | 0.0006 | 0.9167 | 0.0003 | 0.9170 | 0.0007 | 0.9173 | 0.0005 | 0.9134 | 0.0007
| 80 | 0.9174 | 0.0007 | 0.9174 | 0.0007 | 0.9172 | 0.0005 | 0.9165 | 0.0006 | 0.9169 | 0.0009 | 0.9173 | 0.0006 | 0.9131 | 0.0005
| 100 | 0.9176 | 0.0004 | 0.9174 | 0.0005 | 0.9173 | 0.0007 | 0.9167 | 0.0004 | 0.9168 | 0.0007 | 0.9173 | 0.0008 | 0.9124 | 0.0006
APS | 40 | 0.9937 | 0.0002 | 0.9938 | 0.0002 | 0.9938 | 0.0002 | 0.9936 | 0.0002 | 0.9938 | 0.0001 | 0.9938 | 0.0002 | 0.9929 | 0.0001
| 60 | 0.9938 | 0.0002 | 0.9938 | 0.0002 | 0.9938 | 0.0002 | 0.9936 | 0.0002 | 0.9937 | 0.0001 | 0.9938 | 0.0001 | 0.9925 | 0.0001
| 80 | 0.9939 | 0.0001 | 0.9938 | 0.0001 | 0.9938 | 0.0001 | 0.9936 | 0.0002 | 0.9938 | 0.0001 | 0.9937 | 0.0002 | 0.9925 | 0.0001
| 100 | 0.9938 | 0.0001 | 0.9939 | 0.0001 | 0.9939 | 0.0001 | 0.9937 | 0.0002 | 0.9938 | 0.0001 | 0.9938 | 0.0001 | 0.9925 | 0.0001
Average: | 0.8985 | 0.0049 | 0.8997 | 0.0045 | 0.8993 | 0.0046 | 0.8979 | 0.0049 | 0.9012 | 0.0052 | 0.9009 | 0.0055 | 0.8894 | 0.0041

Table 4 presents the results for the 9 datasets and four different values of
$K$. For each algorithm, we include two columns: the average (Avg.) and
standard deviation (Std.) of the out-of-sample accuracy, calculated with the
data points in the independent set. We remind the reader that each entry in
the table represents the average accuracy of 100 different runs. A bold value
in any of the first three Avg. columns means that our formulation obtained a
higher average than all four benchmarks. The last row gives an overall average
value of the corresponding column. We also present, in Table 5, the average
rank per value of $K$ across all datasets. The ranking procedure (Demšar,
2006) works as follows. For each dataset, the best performing algorithm gets
rank 1.0, the second best gets rank 2.0, and so on. If multiple algorithms
tie, they are assigned the average of their ranks.

Table 5: Average ranks of accuracies $K$ | F1 | F2 | F3 | BFT | HC-CON | HC-UWA | FE
---|---|---|---|---|---|---|---
40 | 3.82 | 3.74 | 3.79 | 4.04 | 3.71 | 3.66 | 5.25
60 | 3.82 | 3.70 | 3.76 | 4.03 | 3.66 | 3.66 | 5.39
80 | 3.82 | 3.80 | 3.75 | 4.09 | 3.54 | 3.58 | 5.42
100 | 3.91 | 3.72 | 3.72 | 4.07 | 3.55 | 3.56 | 5.48
Avg: | 3.84 | 3.74 | 3.75 | 4.06 | 3.61 | 3.61 | 5.38

All methods in the tables have, as primary objective, maximising accuracy. The
results suggest that while the formulation is overall competitive, it was
slightly outperformed by HC-CON and HC-UWA - both in terms of average accuracy
and average rank. Still, with the exception of FE, the difference between BFT
(worst performing) and HC-CON (best performing) was 0.33% in terms of average
overall accuracy and 0.45 in terms of average rank. Adding diversity
constraints to our formulation also had a small beneficial impact in improving
average accuracy and reducing the average ranking. In 11 out of the 36 cases,
F2 outperformed all benchmarks.

Both HC methods had a higher dispersion of accuracies than BFT and our
formulation. Moreover adding diversity in F2 and F3 helped reduce that
dispersion. While adding diversity resulted in a small improvement, further
studies on either better enforcing these constraints or proposing new
constraints based on alternative diversity measures remain as future work.
Since our proposed method is exact in nature (although limited to 5 minutes),
in the supplementary material we discuss in more details the effects of
overfitting.

###  5.5 Balanced accuracy

Several of the datasets used in this work are imbalanced and so accuracy may
not be the best comparison metric among the methods. In this section, we use
an alternative metric called Balanced Accuracy (BA), which weighs equally the
accuracy of positive data points and the accuracy of negative data points. BA
is a more appropriate measure for imbalanced datasets (Brodersen et al., 2010)
and is given by:

$\displaystyle\text{BA}=\frac{\frac{T^{+}}{T^{+}+F^{-}}+\frac{T^{-}}{T^{-}+F^{+}}}{2}=\frac{\frac{T^{+}}{N_{1}}+\frac{T^{-}}{N_{0}}}{2}$
(20)

With regards to our formulation we analyse the performance of two different
weights assignments in (1). Here we do not use any diversity constraints - we
employ F1 as defined earlier and a modified F1 where we maximise the
$\theta$-weighted configuration suggested in Section 3.1. In fact, Theorem 1
shows that maximising BA is equivalent to maximising the $\theta$-weighted
function.

###### Theorem 1

Maximising the $\theta$-weighted configuration is equivalent to maximising
balanced accuracy.

###### Proof 1

Following the definition of the $\theta$-weighted function in Section 3.1,
objective function $z$ can be written as:

$\displaystyle\max z$
$\displaystyle=\bigg{(}1-\frac{N_{1}}{N}\bigg{)}T^{+}+\frac{N_{1}}{N}T^{-}$

where $T^{+}=\sum_{i=1}^{N_{1}}t^{+}_{i}$, $T^{-}=\sum_{j=1}^{N_{0}}t^{-}_{j}$
and $\theta=\frac{N_{1}}{N}$. As $N=N_{0}+N_{1}$ it follows that:

$\displaystyle\max\;\;\;z$
$\displaystyle=\frac{N_{0}}{N}T^{+}+\frac{N_{1}}{N}T^{-}$ $\displaystyle\max
Nz$ $\displaystyle=N_{0}T^{+}+N_{1}T^{-}$ $\displaystyle\max\;\,cz$
$\displaystyle=\frac{T^{+}}{N_{1}}+\frac{T^{-}}{N_{0}}$

where constant $c=\frac{N}{N_{1}N_{0}}>0$. If $c>0$, the optimal solution does
not depend on it since it is only a scaling factor in the solution value. That
is valid also for $c=2$ as in (20), and thus maximising the $\theta$-weighted
function is equivalent to maximising balanced accuracy.

Tables 6 and 7, which have the same structure as Tables 4 and 5, show the
results. We did not rerun the experiments for the accuracy version of F1 nor
for the benchmarks, rather we used the same ensemble subsets to calculate the
corresponding balanced accuracies.

Table 6: Balanced Accuracy averages and standard deviations Dataset | $K$ | F1 |  F1 ($\theta$-weighted) | BFT | HC-CON | HC-UWA | FE
---|---|---|---|---|---|---|---
Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std. | Avg. | Std.
PRK | 40 | 0.8478 | 0.0328 | 0.8582 | 0.0289 | 0.8523 | 0.0177 | 0.8643 | 0.0286 | 0.8548 | 0.0290 | 0.8308 | 0.0110
| 60 | 0.8467 | 0.0242 | 0.8545 | 0.0181 | 0.8364 | 0.0242 | 0.8611 | 0.0309 | 0.8552 | 0.0310 | 0.8237 | 0.0158
| 80 | 0.8464 | 0.0290 | 0.8514 | 0.0204 | 0.8433 | 0.0169 | 0.8547 | 0.0244 | 0.8615 | 0.0331 | 0.8264 | 0.0146
| 100 | 0.8487 | 0.0306 | 0.8557 | 0.0266 | 0.8416 | 0.0103 | 0.8599 | 0.0283 | 0.8598 | 0.0320 | 0.8154 | 0.0120
BCW | 40 | 0.9645 | 0.0057 | 0.9668 | 0.0050 | 0.9581 | 0.0066 | 0.9624 | 0.0040 | 0.9608 | 0.0056 | 0.9566 | 0.0077
| 60 | 0.9666 | 0.0052 | 0.9675 | 0.0037 | 0.9608 | 0.0064 | 0.9638 | 0.0047 | 0.9620 | 0.0041 | 0.9564 | 0.0073
| 80 | 0.9646 | 0.0054 | 0.9651 | 0.0044 | 0.9601 | 0.0059 | 0.9655 | 0.0053 | 0.9647 | 0.0059 | 0.9562 | 0.0069
| 100 | 0.9625 | 0.0050 | 0.9631 | 0.0056 | 0.9616 | 0.0059 | 0.9658 | 0.0052 | 0.9642 | 0.0055 | 0.9562 | 0.0073
MSK | 40 | 0.9103 | 0.0102 | 0.9104 | 0.0083 | 0.9071 | 0.0133 | 0.9216 | 0.0090 | 0.9167 | 0.0129 | 0.8844 | 0.0108
| 60 | 0.9108 | 0.0080 | 0.9094 | 0.0084 | 0.9047 | 0.0143 | 0.9207 | 0.0103 | 0.9153 | 0.0124 | 0.8815 | 0.0102
| 80 | 0.9179 | 0.0100 | 0.9164 | 0.0075 | 0.9121 | 0.0124 | 0.9259 | 0.0095 | 0.9176 | 0.0101 | 0.8841 | 0.0105
| 100 | 0.9180 | 0.0071 | 0.9162 | 0.0058 | 0.9056 | 0.0143 | 0.9268 | 0.0083 | 0.9184 | 0.0082 | 0.8833 | 0.0102
QSR | 40 | 0.8574 | 0.0066 | 0.8645 | 0.0049 | 0.8496 | 0.0052 | 0.8533 | 0.0063 | 0.8505 | 0.0044 | 0.8432 | 0.0037
| 60 | 0.8604 | 0.0072 | 0.8639 | 0.0052 | 0.8467 | 0.0051 | 0.8533 | 0.0101 | 0.8503 | 0.0057 | 0.8407 | 0.0040
| 80 | 0.8559 | 0.0046 | 0.8649 | 0.0038 | 0.8515 | 0.0050 | 0.8532 | 0.0072 | 0.8530 | 0.0059 | 0.8421 | 0.0025
| 100 | 0.8563 | 0.0050 | 0.8648 | 0.0052 | 0.8477 | 0.0049 | 0.8530 | 0.0048 | 0.8521 | 0.0063 | 0.8419 | 0.0030
DRD | 40 | 0.7407 | 0.0056 | 0.7434 | 0.0062 | 0.7465 | 0.0078 | 0.7443 | 0.0080 | 0.7499 | 0.0073 | 0.7117 | 0.0079
| 60 | 0.7463 | 0.0115 | 0.7437 | 0.0088 | 0.7520 | 0.0098 | 0.7508 | 0.0089 | 0.7531 | 0.0068 | 0.7145 | 0.0075
| 80 | 0.7457 | 0.0064 | 0.7468 | 0.0046 | 0.7503 | 0.0057 | 0.7525 | 0.0065 | 0.7525 | 0.0072 | 0.7126 | 0.0077
| 100 | 0.7404 | 0.0088 | 0.7466 | 0.0093 | 0.7479 | 0.0063 | 0.7506 | 0.0075 | 0.7551 | 0.0057 | 0.7148 | 0.0075
SPA | 40 | 0.9493 | 0.0018 | 0.9513 | 0.0023 | 0.9478 | 0.0012 | 0.9490 | 0.0015 | 0.9478 | 0.0015 | 0.9415 | 0.0013
| 60 | 0.9498 | 0.0016 | 0.9514 | 0.0020 | 0.9489 | 0.0018 | 0.9503 | 0.0015 | 0.9491 | 0.0015 | 0.9405 | 0.0008
| 80 | 0.9504 | 0.0021 | 0.9521 | 0.0018 | 0.9488 | 0.0017 | 0.9512 | 0.0017 | 0.9493 | 0.0020 | 0.9403 | 0.0009
| 100 | 0.9500 | 0.0022 | 0.9517 | 0.0025 | 0.9485 | 0.0020 | 0.9515 | 0.0015 | 0.9493 | 0.0018 | 0.9402 | 0.0008
DEF | 40 | 0.6633 | 0.0022 | 0.6949 | 0.0023 | 0.6507 | 0.0011 | 0.6543 | 0.0024 | 0.6559 | 0.0009 | 0.6507 | 0.0011
| 60 | 0.6643 | 0.0020 | 0.6973 | 0.0021 | 0.6491 | 0.0018 | 0.6541 | 0.0017 | 0.6556 | 0.0009 | 0.6490 | 0.0012
| 80 | 0.6662 | 0.0014 | 0.6985 | 0.0016 | 0.6484 | 0.0020 | 0.6553 | 0.0009 | 0.6557 | 0.0011 | 0.6484 | 0.0011
| 100 | 0.6661 | 0.0019 | 0.6992 | 0.0014 | 0.6482 | 0.0018 | 0.6542 | 0.0020 | 0.6560 | 0.0007 | 0.6473 | 0.0012
BMK | 40 | 0.7731 | 0.0055 | 0.8607 | 0.0015 | 0.7331 | 0.0038 | 0.7453 | 0.0027 | 0.7462 | 0.0025 | 0.6993 | 0.0039
| 60 | 0.7763 | 0.0049 | 0.8662 | 0.0019 | 0.7338 | 0.0028 | 0.7477 | 0.0029 | 0.7469 | 0.0019 | 0.6883 | 0.0038
| 80 | 0.7765 | 0.0055 | 0.8684 | 0.0015 | 0.7322 | 0.0046 | 0.7477 | 0.0028 | 0.7469 | 0.0018 | 0.6822 | 0.0036
| 100 | 0.7794 | 0.0053 | 0.8694 | 0.0012 | 0.7363 | 0.0040 | 0.7478 | 0.0029 | 0.7479 | 0.0018 | 0.6762 | 0.0031
APS | 40 | 0.8690 | 0.0062 | 0.9382 | 0.0040 | 0.8404 | 0.0057 | 0.8532 | 0.0051 | 0.8513 | 0.0046 | 0.8155 | 0.0037
| 60 | 0.8715 | 0.0062 | 0.9386 | 0.0037 | 0.8392 | 0.0047 | 0.8523 | 0.0052 | 0.8506 | 0.0040 | 0.8015 | 0.0033
| 80 | 0.8731 | 0.0039 | 0.9395 | 0.0038 | 0.8398 | 0.0045 | 0.8535 | 0.0033 | 0.8500 | 0.0040 | 0.8021 | 0.0037
| 100 | 0.8735 | 0.0053 | 0.9416 | 0.0041 | 0.8447 | 0.0064 | 0.8562 | 0.0040 | 0.8513 | 0.0032 | 0.8006 | 0.0032
Average: | 0.8433 | 0.0080 | 0.8665 | 0.0063 | 0.8313 | 0.0069 | 0.8397 | 0.0075 | 0.8383 | 0.0076 | 0.8111 | 0.0057
Table 7: Average ranks of balanced accuracies $K$ | F1 | F1 | BFT | HC-CON | HC-UWA | FE
---|---|---|---|---|---|---
|  | ($\theta$-weighted) |  |  |  |
40 | 2.98 | 2.37 | 3.94 | 3.33 | 3.43 | 4.95
60 | 2.88 | 2.45 | 3.97 | 3.29 | 3.40 | 5.02
80 | 2.92 | 2.39 | 3.97 | 3.25 | 3.38 | 5.09
100 | 2.97 | 2.41 | 4.00 | 3.20 | 3.36 | 5.06
Avg: | 2.94 | 2.40 | 3.97 | 3.27 | 3.39 | 5.03

As opposed to the results shown in Section 5.4, here our formulation with both
objective functions outperformed the benchmarks. Moreover, using the
$\theta$-weighted function as objective resulted in consistent outperformance
over F1 and all the benchmarks, with better overall average accuracy, lower
dispersion and better ranks, especially for the larger (and more imbalanced)
datasets. F1 ($\theta$-weighted) outperformed all benchmarks in 22 out of 36
cases. We also note that it had worse performance than the benchmarks in MSK
and DRD, which are the most balanced datasets. These results suggest that
being able to configure the objective function according to the
characteristics of the dataset at hand can be highly beneficial.

##  6 Conclusions and future directions

In this work we proposed an IP approach for the problem of selecting a subset
of classifiers in ensemble learning. The objective is to maximise a weighted
function of the patterns in the confusion matrix. In order to combine
performance and diversity criteria, we also proposed linear constraints to
enforce minimum diversity levels. We observed that state-of-the-art solvers
can find good solutions in reasonable computational times for the chosen
publicly available datasets. The IP approach is, in our view, able to provide
a flexible exact algorithm (with regards to both the choice of performance
metric and desired diversity levels) which can also be used as a heuristic if
short computational time limits are required. This approach has the additional
advantage of providing bounds on optimal values.

We compared our formulation to seven well-known benchmarks. We used a
stratified 10-fold cross validation procedure and evaluated the effect of
enforcing minimum diversity levels and varying the weights assignments of the
objective function. In our view the results suggest that our approach is
competitive and its flexibility can be beneficial when adapting to datasets
with different characteristics. To help future research all the data required
to reproduce our results is made available as supplementary material.

As future work we intend to experiment with different criteria and larger
datasets. We also intend to research IP techniques and formulation-based
heuristics for both finding good solutions quickly and solving the formulation
faster. Other lines of research include the study of alternative linear
diversity constraints based on different criteria.

## References

  * Banfield et al. [2005] Robert E. Banfield, Lawrence O. Hall, Kevin W. Bowyer, and W.Philip Kegelmeyer.  Ensemble diversity measures and their application to thinning.  _Information Fusion_ , 6(1):49–62, 3 2005.  ISSN 15662535.  doi: 10.1016/j.inffus.2004.04.005.
  * Bhowan et al. [2012] Urvesh Bhowan, Mark Johnston, Mengjie Zhang, and Xin Yao.  Evolving diverse ensembles using genetic programming for classification with unbalanced data.  _IEEE Transactions on Evolutionary Computation_ , 17(3):368–386, 2012.  doi: 10.1109/TEVC.2012.2199119.
  * Breiman [1996] L. Breiman.  Bagging predictors.  _Machine Learning_ , 24(2):123–140, 1996\.  doi: 10.1007/BF00058655.
  * Breiman [2001] L. Breiman.  Random forests.  _Machine Learning_ , 45(1):5–32, 2001\.  doi: 10.1017/CBO9781107415324.004.
  * Britto et al. [2014] A. S. Britto, R. Sabourin, and L. E.S. Oliveira.  Dynamic selection of classifiers - a comprehensive review.  _Pattern Recognition_ , 47(11):3665–3680, 2014.  doi: 10.1016/j.patcog.2014.05.003.
  * Brodersen et al. [2010] Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M Buhmann.  The balanced accuracy and its posterior distribution.  In _2010 20th international conference on pattern recognition_ , pages 3121–3124. IEEE, 2010.  doi: 10.1109/ICPR.2010.764.
  * Caruana et al. [2004] Rich Caruana, Alexandru Niculescu-Mizil, Geoff Crew, and Alex Ksikes.  Ensemble selection from libraries of models.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 18. ACM, 2004.  doi: 10.1145/1015330.1015432.
  * Chandra and Yao [2006] A. Chandra and X. Yao.  Ensemble learning using multi-objective evolutionary algorithms.  _Journal of Mathematical Modelling and Algorithms_ , 5(1):417–445, 2006.  doi: 10.1007/s10852-005-9020-3.
  * Chen and Guestrin [2016] T. Chen and C. Guestrin.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 785–794. ACM, 2016.  doi: 10.1145/2939672.2939785.
  * Cohen [1960] J. Cohen.  A coefficient of agreement for nominal scales.  _Educational and psychological measurement_ , 20(1):37–46, 1960.
  * CPLEX Optimizer [2021] CPLEX Optimizer.  IBM. Available from https://www.cplex.com, last accessed April 1st, 2021\.
  * Cruz et al. [2018] R. M. O. Cruz, R. Sabourin, and G. D. C. Cavalcanti.  Dynamic classifier selection: Recent advances and perspectives.  _Information Fusion_ , 41(May):195–216, 2018.  doi: 10.1016/j.inffus.2017.09.010.
  * Dai and Han [2016] Q. Dai and X. Han.  An efficient ordering-based ensemble pruning algorithm via dynamic programming.  _Applied Intelligence_ , 44(4):816–830, 2016.  doi: 10.1007/s10489-015-0729-z.
  * Demšar [2006] Janez Demšar.  Statistical comparisons of classifiers over multiple data sets.  _The Journal of Machine Learning Research_ , 7:1–30, 2006.  doi: 10.5555/1248547.1248548.
  * Duin [2002] R. P. W. Duin.  The combining classifier: to train or not to train?  _Object recognition supported by user interaction for service robots_ , 2(c):765–770, 2002.  doi: 10.1109/ICPR.2002.1048415.
  * Fan et al. [2002] Wei Fan, Fang Chu, Haixun Wang, and Philip S. Yu.  Pruning and dynamic scheduling of cost-sensitive ensembles.  In _AAAI/IAAI_ , pages 146–151, 2002.
  * Fernandes et al. [2015] Everlandio RQ Fernandes, André CPLF de Carvalho, and André LV Coelho.  An evolutionary sampling approach for classification with imbalanced data.  In _IJCNN’15. International Joint Conference on Neural Networks._ , pages 1–7. IEEE, 2015.  doi: 10.1109/IJCNN.2015.7280760.
  * Freund and Schapire [1997] Y. Freund and R. E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of Computer and System Sciences_ , 55(1):119–139, 1997.  doi: 10.1006/jcss.1997.1504.
  * Friedman and Stuetzle [1981] J. H. Friedman and W. Stuetzle.  Projection pursuit regression.  _Journal of the American statistical Association_ , 76(376):817–823, 1981.  doi: 10.1080/01621459.1981.10477729.
  * Giacinto et al. [2000] G. Giacinto, F. Roli, and G. Fumera.  Design of effective multiple classifier systems by clustering of classifiers.  In _Proceedings 15th International Conference on Pattern Recognition. ICPR-2000_ , volume 2, pages 160–163. IEEE, 2000.  doi: 10.1109/ICPR.2000.906039.
  * Karp [1972] R. M. Karp.  _Reducibility among Combinatorial Problems_ , pages 85–103.  Springer US, Boston, MA, 1972.  doi: 10.1007/978-1-4684-2001-2_9.
  * Kittler et al. [1998] J. Kittler, M. Hatef, R. P. W. Duin, and J. Matas.  On combining classifiers.  _IEEE transactions on pattern analysis and machine intelligence_ , 20(3):226–239, 1998.  doi: 10.1109/ICPR.1996.547205.
  * Lazarevic and Obradovic [2001] Aleksandar Lazarevic and Zoran Obradovic.  Effective pruning of neural network classifier ensembles.  In _IJCNN’01. International Joint Conference on Neural Networks._ , volume 2, pages 796–801. IEEE, 2001.  doi: 10.1109/IJCNN.2001.939461.
  * Lichman [2021] M. Lichman.  UCI Machine Learning Repository.  Available from http://archive.ics.uci.edu/ml, last accessed April 1st, 2021.
  * Lu et al. [2010] Z. Lu, X. Wu, X. Zhu, and J. Bongard.  Ensemble pruning via individual contribution ordering.  In _Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 871–880. ACM, 2010.  doi: 10.1145/1835804.1835914.
  * Margineantu and Dietterich [1997] D. D. Margineantu and T. G. Dietterich.  Pruning adaptive boosting.  In _Proceedings of the 14th International Conference of Machine Learning_ , volume 97, pages 211–218. Citeseer, 1997.  doi: 10.1007/11875581_39.
  * Martínez-Muñoz and Suárez [2006] G. Martínez-Muñoz and A. Suárez.  Pruning in ordered bagging ensembles.  In _Proceedings of the 23rd International Conference on Machine Learning_ , pages 609–616. ACM, 2006.  doi: 10.1145/1143844.1143921.
  * Martínez-Muñoz and Suárez [2007] G. Martínez-Muñoz and A. Suárez.  Using boosting to prune bagging ensembles.  _Pattern Recognition Letters_ , 28(1):156–165, 2007.  doi: 10.1016/j.patrec.2006.06.018.
  * Martınez-Muñoz and Suárez [2004] Gonzalo Martınez-Muñoz and Alberto Suárez.  Aggregation ordering in bagging.  In _Proc. of the IASTED International Conference on Artificial Intelligence and Applications_ , pages 258–263. Citeseer, 2004.  doi: 10.1.1.146.3650.
  * Partalas et al. [2006] Ioannis Partalas, Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas.  Ensemble pruning using reinforcement learning.  In _Hellenic Conference on Artificial Intelligence_ , pages 301–310. Springer, 2006.  doi: 10.1007/11752912_31.
  * Partalas et al. [2008] Ioannis Partalas, Grigorios Tsoumakas, and Ioannis Vlahavas.  Focused ensemble selection: A diversity-based method for greedy ensemble selection.  _Frontiers in Artificial Intelligence and Applications_ , 178:117–121, 2008.  doi: 10.3233/978-1-58603-891-5-117.
  * Partalas et al. [2010] Ioannis Partalas, Grigorios Tsoumakas, and Ioannis Vlahavas.  An ensemble uncertainty aware measure for directed hill climbing ensemble pruning.  _Machine Learning_ , 81(3):257–282, 2010\.  doi: 10.1007/s10994-010-5172-0.
  * Qiang et al. [2005] Fu Qiang, Hu Shang-Xu, and Zhao Sheng-Ying.  Clustering-based selective neural network ensemble.  _Journal of Zhejiang University-Science A_ , 6(5):387–392, 2005.  doi: 10.1631/jzus.2005.A0387.
  * Tang et al. [2006] E Ke Tang, Ponnuthurai N Suganthan, and Xin Yao.  An analysis of diversity measures.  _Machine learning_ , 65(1):247–271, 2006\.  doi: 10.1007/s10994-006-9449-2.
  * Tsoumakas et al. [2004] G. Tsoumakas, I. Katakis, and I. Vlahavas.  Effective voting of heterogeneous classifiers.  In _European Conference on Machine Learning_ , pages 465–476. Springer, 2004.  doi: 10.2147/JPR.S129139.
  * Xu et al. [2012] L. Xu, B. Li, and E. Chen.  Ensemble pruning via constrained eigen-optimization.  In _2012 IEEE 12th International Conference on Data Mining_ , pages 715–724. IEEE, 2012.  doi: 10.1109/ICDM.2012.97.
  * Zhang et al. [2006] Y. Zhang, S. Burer, and W. N. Street.  Ensemble pruning via semi-definite programming.  _Journal of Machine Learning Research_ , 7(Jul):1315–1338, 2006.  doi: 10.1016/j.jasms.2006.06.007.