# Handling Imbalanced Datasets Through Optimum-Path Forest

Leandro Aparecido Passos∗ Danilo S. Jodas∗ Luiz C. F. Ribeiro∗ Marco Akio
Andre Nunes de Souza  João Paulo Papa  Department of Computing, São Paulo
State University
Av. Eng. Luiz Edmundo Carrijo Coube, 14-01, Bauru, 17033-360, Brazil
email:{leandro.passos, luiz.felix<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Electrical Engineering, São Paulo State University
Av. Eng. Luiz Edmundo Carrijo Coube, 14-01, Bauru, 17033-360, Brazil
email<EMAIL_ADDRESS><EMAIL_ADDRESS>
∗Authors contributed equally.

###### Abstract

In the last decade, machine learning-based approaches became capable of
performing a wide range of complex tasks sometimes better than humans,
demanding a fraction of the time. Such an advance is partially due to the
exponential growth in the amount of data available, which makes it possible to
extract trustworthy real-world information from them. However, such data is
generally imbalanced since some phenomena are more likely than others. Such a
behavior yields considerable influence on the machine learning model’s
performance since it becomes biased on the more frequent data it receives.
Despite the considerable amount of machine learning methods, a graph-based
approach has attracted considerable notoriety due to the outstanding
performance over many applications, i.e., the Optimum-Path Forest (OPF). In
this paper, we propose three OPF-based strategies to deal with the imbalance
problem: the $\text{O}^{2}$PF and the OPF-US, which are novel approaches for
oversampling and undersampling, respectively, as well as a hybrid strategy
combining both approaches. The paper also introduces a set of variants
concerning the strategies mentioned above. Results compared against several
state-of-the-art techniques over public and private datasets confirm the
robustness of the proposed approaches.

###### keywords:

Imbalanced data, Oversampling, Undersampling, Optimum-Path Forest

††journal: Knowledge-based Systems

##  1 Introduction

Imbalanced class distribution in a dataset represents a major concern for the
effectiveness of many machine learning models since they might be prone to
assign new samples to the majority class at the detriment of the minority one.
Current baseline strategies adopted to tackle the imbalance issue include: (i)
improve the classification model to make it more robust regarding minority
class [1, 2], and (ii) change of the dataset distribution to match the number
of samples in each class. Regarding the latter strategy, the balancing of the
dataset consists of either reducing the samples of the majority class or
including new synthetic samples to the minority class, denoting the task of
undersampling and oversampling, respectively.

Many studies addressed oversampling techniques to tackle imbalanced datasets
in practical applications [3, 4, 5, 6, 7, 8, 9, 10, 11, 12], including the
well-known Synthetic Minority Over-sampling Technique (SMOTE) [13] and its
variations borderline-SMOTE1 and borderline-SMOTE2 [14], the Adaptive
Synthetic (ADASYN) [15], the Combined Synthetic Oversampling and Undersampling
Technique (CSMOUTE), the LR-SMOTE [16], and the Class Decomposition SMOTE
(CDSMOTE) [17], to cite a few. Although widely used to handle the class
imbalance in machine learning problems, the major shortcoming of SMOTE is the
introduction of noise data in the majority class samples since the labels
among all classes are not considered in the interpolation process.
Furthermore, several clustering-based oversampling techniques exist in the
literature, with particular reference to ones such as Majority Weighted
Minority Oversampling Technique (MWMOTE) [18], $k$-means SMOTE [19], Self-
Organizing Map Oversampling (SOMO) [20] and Agglomerative Hierarchical
Clustering (AHC) [21].

Considering the undersampling strategies, one can mention the nearest
neighbor-based approaches, in which the majority class samples are kept or
removed by considering their nearest samples of the minority class. NearMiss
family methods [22] and the Condensed Nearest Neighbor (CNN) [23] are examples
of undersampling approaches based on nearest neighbors. However, the main
drawback of Near Miss methods regards the holding of majority samples only in
cases where the number of minority class neighbors is large. Condensed Nearest
Neighbor, although proposed to reduce the computational cost of the K-Nearest
Neighbor (KNN) method, still suffers from outliers and the overlapping among
classes. In a similar manner, Koziarski [24] introduced a Radial-Based
Undersampling (RBU) approach, obtaining promising results. Further, Cervellera
and Macciò [25] introduced a Voronoi diagram-based approach to perform either
under or oversampling through a Gaussian Mixture Model.

To deal with the issues mentioned above for both oversampling and
undersampling tasks, this paper proposes a novel framework extending the
Optimum Path Forest (OPF) algorithm capabilities to handle the problem of
imbalanced datasets. The motivation for such an approach lies in the
competence of the OPF attributes to tackle a wide variety of problems, such as
supervised classification [26, 27, 28], clustering [29], and anomaly detection
[30]. Further, it has been successfully employed to solve problems concerning
intricate data distribution [31], and to improve other techniques, such as the
radial basis function neural networks [32] and the brainstorm optimization
algorithm [33], to cite a few.

Regarding the oversampling task, Passos et al. [34] proposed the Oversampling
Optimum Path Forest ($\text{{O}}^{2}$PF), an unsupervised OPF-based approach
that captures intrinsic characteristics of minority class samples through
clustering approaches, and afterward generates new synthetic samples using a
Gaussian distribution over the mean and the covariance matrix of each cluster.
This last step is conceived to guarantee the variability of the new synthetic
samples while enforcing them to share similar characteristics with the real
ones. Moreover, this paper introduces four variations of the method,
considering different policies for generating new samples.

Concerning the undersampling approach, the proposed OPF-based framework for
data imbalance introduces the Optimum Path Forest-based approach for
undersampling, the so-called OPF-US, which concerns in removing samples that
are more likely to lead the classifier to ill decision boundaries. To such an
extent, the supervised OPF is employed to capture the importance of the
majority class samples via the k-fold cross-validation approach considering
five splits of the training set. After the training phase, a rank score
representing the prediction of a validation sample is assigned to each
training sample in a k-fold cross-validation iteration. At the final stage,
the training samples are ordered by the ascending order of their average rank
scores, being the majority class samples with lower ranks removed from the
training set until it is fully balanced. Furthermore, this work also
introduces three variants of OPF-US, which adopt different policies regarding
the samples to be pruned. Besides, it also proposes three hybrid approaches
considering the tasks of data undersampling and oversampling.

Different from the approaches mentioned above, whose primary focus consists of
aggregating variants of the SMOTE into existing clustering algorithms, or even
using existing clustering techniques, this paper shows a different approach to
explore the potential of a fully OPF-based method for oversampling and
undersampling tasks. Therefore, the main contributions of this paper are
fourfold, listed as follows:

  * 1.

to propose four variations of the oversampling algorithm $\text{O}^{2}$PF,
i.e., $\text{O}^{2}$PF Radius Interpolation, $\text{O}^{2}$PF Mean
Interpolation, $\text{O}^{2}$PF Prototype, and $\text{O}^{2}$PF Weight
Interpolation;

  * 2.

to propose four OPF-based methods for data undersampling, i.e., OPF-US, OPF-
US1, OPF-US2, and OPF-US3;

  * 3.

to propose three hybrid approaches combining both OPF-based methods for
undersampling and oversampling, i.e., OPF-US1-$\text{O}^{2}$PF, OPF-
US2-$\text{O}^{2}$PF, and OPF-US3-$\text{O}^{2}$PF;

  * 4.

to foster the literature regarding methods to deal with imbalanced datasets,
since it establishes new state-of-the-art methods to tackle the problem.

This paper is organized as follows: Section 2 presents the theoretical basis
of the Optimum Path Forest algorithm for supervised and unsupervised
classification purposes. Further, Section 3 describes the theory behind the
undersampling and oversampling of imbalanced datasets via OPF. Sections 4 and
5 provide the methodology and the experimental results, respectively. Finally,
Section 6 states the conclusions and future work.

##  2 Theoretical Background

This section introduces the main concepts regarding the supervised and
unsupervised Optimum-Path Forest.

###  2.1 Supervised Optimum-Path Forest

The supervised version of the Optimum-path Forest [26, 27] can be defined as a
graph-based classifier that assumes each data sample as a node, and the
connection between each pair of samples as an edge in the graph. Additionally,
the model selects the most representative samples, i.e., prototypes, to
compete among themselves in order to provide optimum-path costs to the
remaining samples in a conquering-like process. Therefore, the training
process is accomplished by the minimization of the path-cost function
$f_{max}$, as follows:

$\displaystyle f_{max}(\langle\bm{q}\rangle)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}0&\mbox{if $\bm{q}\in{\cal P}$,}\\\
+\infty&\mbox{otherwise}\end{array}\right.$ (3) $\displaystyle
f_{max}(\phi_{\bm{q}}\cdot\langle\bm{q},\bm{u}\rangle)$ $\displaystyle=$
$\displaystyle\max\\{f_{max}(\phi_{\bm{q}}),d(\bm{q},\bm{u})\\},$ (4)

where ${\cal P}$ denotes the set prototypes, $\phi_{\bm{q}}$ denotes a
sequence of adjacent samples, i.e., a path, starting from a root in ${\cal P}$
and with terminus at sample ${\bm{q}}$, and $d(\bm{q},\bm{u})$ represents the
distance between samples $\bm{q}$ and $\bm{u}$. Moreover,
$\phi_{\bm{q}}\cdot\langle\bm{q},\bm{u}\rangle$ stands for the concatenation
between the path $\phi_{\bm{q}}$ and the edge $\langle\bm{q},\bm{u}\rangle$.
In a nutshell, $f_{max}(\phi_{\bm{q}})$ stands for the maximum distance among
adjacent samples in the path $\phi_{\bm{q}}$.

Let ${\cal P}^{\ast}\subseteq{\cal P}$ be the set of prototypes that minimize
the error during training, which can be found by computing the Minimum
Spanning Tree over the training set and selecting adjacent samples with
different labels. The training step is performed by assigning an optimum cost
$C(\bm{u})$ to each sample $\bm{u}\in{\cal V}$, where ${\cal V}$ stands for
the training set, i.e.:

$C(\bm{u})=\min_{\forall\bm{q}\in{\cal
V}}\\{\max\\{C(\bm{q}),d(\bm{q},\bm{u})\\}\\},$ (5)

where $\bm{q}$ stands for the training sample that conquered $\bm{u}$. The
classification step is performed by finding out the training sample that
offers the optimum-path cost to each test sample in a similar fashion to
Equation 5. Algorithm 1 implements the training procedure mentioned above.

1

Input: A training set ${\cal V}$, set of prototypes ${\cal
P}^{\ast}\subseteq{\cal V}$, map of training set labels $\lambda$, and
distance function $d$.

Output: Predecessor map $O$, path-cost map $C$, and label map $L$.

Auxiliary: Priority queue $Q$, and variable $cst$.

2

3for  _all $\bm{q}\in{\cal V}$_ do

4 $O(\bm{q})\leftarrow nil$, $C(\bm{q})\leftarrow+\infty$;

5

6for  _all $\bm{q}\in{\cal P}^{\ast}$_ do

7 $C(\bm{q})\leftarrow 0$, $L(\bm{q})=\lambda(\bm{q})$, $Q\leftarrow\bm{q}$;

8

9while  _$Q\neq\emptyset$_ do

10 Remove from $Q$ a sample $\bm{q}$ such that $C(\bm{q})$ is minimum;

11

12 for  _each sample $\bm{u}\in{\cal V}$ such that $\bm{q}\neq\bm{u}$ and
$C(\bm{u})>C(\bm{q})$_ do

13 $cst\leftarrow\max\\{C(\bm{q}),d(\bm{q},\bm{u})\\}$;

14 if  _$cst <C(\bm{u})$_ then

15 if  _$C(\bm{u})\neq+\infty$_ then Remove $\bm{u}$ from $Q$;

16 $L(\bm{u})\leftarrow L(\bm{q})$, $O(\bm{u})\leftarrow\bm{q}$,
$C(\bm{u})\leftarrow cst$, $Q\leftarrow\bm{u}$;

17

return _$[O,C,L]$_

Algorithm 1 Supervised OPF training algorithm

Lines $1-4$ initialize the cost map by assigning zero cost to the prototypes
(Lines $3-4$) and a high cost to the remaining nodes (Lines $1-2$). Besides,
all samples have their predecessors set to $nil$, and the prototypes are
inserted into the priority queue $Q$. Notice the main loop in Lines $5-11$
concerns the core of the OPF algorithm. A sample with minimum cost is removed
from $Q$, and its neighborhood is analyzed: if the cost $cst$ offered to a
neighboring sample $\bm{u}$ is lower than its current cost, it receives the
label assigned to $\bm{q}$, and it is further added to its optimum-path tree
(Line $11$). Groups of samples from the same class might be represented by
multiple optimum-path trees, and there must be at least one per class.

Considering the implementation provided in Algorithm 1, Lines $1-4$ take
$(\theta(\left|{\cal V}\right|)+\theta(\left|{\cal
P}^{\ast}\right|))\in\theta(\left|{\cal V}\right|)$ steps. In Lines $5-11$,
$\theta(\left|{\cal V}\right|)$ training samples are added to the priority
queue $Q$, each one removed once. Therefore, the loop is executed
$\theta(\left|{\cal V}\right|)$ times. Additionally, once the model employs a
binary heap to implement the priority queue, Line $6$ has complexity of
$O(\log\left|{\cal V}\right|)$. Moreover, considering the process is performed
over a complete graph, the inner loop presented in Lines $7-11$ runs
$\theta(\left|{\cal V}\right|)$ times. Thereinafter, the final complexity for
training is $\theta(\left|{\cal V}\right|^{2})$. The classification step can
be performed in $\theta(\left|{\cal V}\right|.\left|{\cal J}\right|)$, where
$\left|{\cal J}\right|$ represents the test set size. However, Papa et al.
[27] showed it can be performed in $O(\left|{\cal V}\right|.\left|{\cal
J}\right|)$.

###  2.2 Unsupervised Optimum-Path Forest

In its unsupervised version, the Optimum-Path Forest performs clustering by
representing each training sample as a graph node. Such samples are connected
to their $k$-nearest neighbors and the arcs are weighted according to the
distance between them. Further, each node is weighted by a probability density
function (pdf), as follows:

$\displaystyle\rho(\bm{q})$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi\psi^{2}}k}\sum_{\forall\bm{u}\in{\cal
A}_{k}(\bm{q})}\exp\left(\frac{-d^{2}(\bm{q},\bm{u})}{2\psi^{2}}\right),$ (6)

where ${\cal A}_{k}(\bm{q})$ denotes the $k$-neighborhood of sample $\bm{q}$,
$\psi=\frac{m_{w}}{3}$, and $m_{w}$ is the maximum weight among all edges in
the graph.

The probability density is estimated similarly to a Parzen-window. Such a
procedure requires discovering the optimum number of nearest neighbors
${k^{\ast}\in\\{1\leq k_{\max}\leq|{\cal V}|\\}}$, where $k_{max}$ denotes a
hyperparameter that is commonly computed by finding $k^{\ast}$ that minimizes
the graph cut over ${\cal V}$.

The model establishes a set of prototypes ${\cal P}$ composed of one element
per maximum of the pdf, and $\bm{u}$ is assigned to the path whose minimum
density value along it is maximum, i.e.:

$\displaystyle f_{min}(\langle\bm{u}\rangle)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\rho(\bm{u})&\mbox{if $\bm{u}\in{\cal
P}$}\\\ \rho(\bm{u})-\delta&\mbox{otherwise,}\end{array}\right.$ (9)
$\displaystyle
f_{min}(\langle\phi_{\bm{q}}\cdot\langle\bm{q},\bm{u}\rangle\rangle)$
$\displaystyle=$ $\displaystyle\min\\{f_{min}(\phi_{\bm{q}}),\rho(\bm{u})\\},$
(10)

where $\delta$ is small constant. Algorithm 2 implements the unsupervised
Optimum-Path Forest algorithm.

1

Input: Graph ${\cal G}=({\cal V},{\cal A}_{k})$.

Output: Predecessor map $O$, path-cost map $C$, and cluster label map $L$.

Auxiliary: Priority $Q$, and variables $cst$ and $l\leftarrow 1$.

2

3for  _all $\bm{q}\in{\cal V}$_ do

4 Compute $\rho(\bm{q})$ using Equation 6;

5 $O(\bm{q})\leftarrow nil$, $C(\bm{q})\leftarrow\rho(\bm{q})-\delta$,
$Q\leftarrow\bm{q}$;

6

7while  _$Q\neq\emptyset$_ do

8 Remove from $Q$ a sample $\bm{q}$ such that $C(\bm{q})$ is maximum;

9 if  _$O(\bm{q})=nil$_ then

10 $L(\bm{q})\leftarrow l$, $l\leftarrow l+1$, and
$C(\bm{q})\leftarrow\rho(\bm{q})$;

11

12 for  _all $\bm{u}\in{\cal A}_{k}(\bm{q})$ such that $C(\bm{u})<C(\bm{q})$_
do

13 $cst\leftarrow\min\\{C(\bm{q}),\rho(\bm{u})\\}$;

14 if  _$cst >C(\bm{u})$_ then

15 $L(\bm{u})\leftarrow L(\bm{q})$, $O(\bm{u})\leftarrow\bm{q}$,
$C(\bm{u})\leftarrow cst$;

16 Update position of $\bm{u}$ in $Q$;

17

return $[O,C,L]$

Algorithm 2 OPF Clustering algorithm

Lines $1-3$ initialize the variables and insert all samples in the priority
queue $Q$. The main loop, implemented in Lines $4-11$, is responsible for the
conquering process. It first removes a sample $\bm{q}$ from $Q$ with maximum
path value in Line $5$: if $\bm{q}$ has not been conquered by any other sample
(Line $6$), it is then considered a prototype. Therefore, its connectivity
value is reset to $\rho(\bm{q})$ (Line $7$) and a new distinct cluster label
is assigned to it for optimum-path propagation. The inner loop in Lines $8-12$
evaluates samples in the neighborhood of $\bm{q}$ to which $\bm{q}$ can offer
a better connectivity value. In this case (Line $10$), then the predecessor,
label and cost maps of $\bm{u}$ are updated accordingly (Lines $11-12$).

Considering the implementation provided by Algorithm 2, there is a need to
first find $k^{\ast}\in[1,k_{max}]$ that represents the size of the
neighborhood used to compute the density of each node (Equation 6). Rocha et
al. [29] proposed to find $k^{\ast}$ that minimizes the graph cut over the
training set. Using any standard data structure, such an operation takes
$\theta(\left|{\cal V}\right|^{2})$ steps, and the whole process takes
$\theta(k_{max}\left|{\cal V}\right|^{2})$ operations. Since $k_{max}\in
O(\left|{\cal V}\right|)$ is usually enough in most situations, the final
complexity to find $k^{\ast}$ is given by $\theta(\left|{\cal V}\right|^{2})$.

Lines $1-3$ take $\theta(\left|{\cal V}\right|)$ operations, while the loop in
Lines $4-12$ removes each sample only once. Therefore, it runs over
$\theta(\left|{\cal V}\right|)$ iterations. Implementing the priority queue
$Q$ as a binary heap, we can execute Line $5$ in $O(\log\left|{\cal
V}\right|)$ steps. Besides, Lines $8-12$ take $O(k^{\ast})$ operations, thus
ending up in $O(\left|{\cal V}\right|(\log\left|{\cal
V}\right|+k^{\ast})=O(\left|{\cal V}\right|\log\left|{\cal
V}\right|)+O(k^{\ast}\left|{\cal V}\right|)$ operations concerning the main
loop. In practice, this complexity nails down to $O(\left|{\cal
V}\right|\log\left|{\cal V}\right|)$. The final complexity concerning
unsupervised OPF is given by $\theta(\left|{\cal V}\right|^{2})+O(\left|{\cal
V}\right|\log\left|{\cal V}\right|)$, which is in practice $\theta(\left|{\cal
V}\right|^{2})$.

##  3 Proposed Approaches

This section describes the proposed framework based on the Optimum-Path Forest
to tackle imbalanced datasets using oversampling and undersampling strategies.

###  3.1 Undersampling with Optimum-Path Forest

The OPF-US employs a straightforward concept of ranking samples according to
their importance during training for further pruning the less relevant ones.
The whole process can be defined into two main steps: (i) training standard
OPF using Algorithm 1, and then (ii) assigning a score to each training sample
during a validation step.

Assigning scores is straightforward using the OPF algorithm, as demonstrated
by Fernandes and Papa [35]. During validation, we computed how many times a
training sample labeled a validation node correctly. On the other hand, in the
case of misclassification, that training sample will have its score penalized.
Basically, training samples are assigned zero scores, which are then
incremented by one unit in case of correct classification, or decreased by one
unit otherwise. In the end, each training sample will possess a score that
somehow encodes its importance in the conquering process. Finally, samples are
ranked in ascending order considering their scores, and the less-ranked
samples are pruned from the training set until it is fully balanced, i.e., the
number of samples from the two classes are equal. Notice only samples from the
majority class are pruned. Additionally, such an approach considers binary
datasets only, but it can be readily extended to multi-class scenarios.

1

Input: A training set ${\cal V}$, a validation set ${\cal T}$, map of training
set labels $\lambda$, map of validation set labels $\omega$, number of samples
to be removed $n_{r}$, set of prototypes ${\cal P}^{\ast}\subseteq{\cal V}$,
and distance function $d$.

Output: Undersampled training set ${\cal V}^{\star}$.

Auxiliary: Score map $S(\bm{q})=0,\forall\bm{q}\in{\cal V}$, predecessor
$O^{\prime}$, cost $C^{\prime}$ and label $L^{\prime}$ maps concerning the
training set, label map $L$ regarding the validation set, as well as the
lower-scored majority samples from training set $\hat{\cal V}$.

2

3$[O^{\prime},C^{\prime},L^{\prime}]\leftarrow$ Algorithm 1(${\cal V},{\cal
P}^{\ast},\lambda,d$);

4

5for  _each $\bm{t}\in{\cal T}$_ do

6 Let $\bm{s}^{\ast}\in{\cal V}$ be the sample that conquers $\bm{t}$
(Equation 5);

7 $L(\bm{t})\leftarrow L^{\prime}(\bm{s}^{\ast})$;

8 if  _$\omega(\bm{t})=L(\bm{t})$_ then

9 $S(\bm{s}^{\ast})\leftarrow S(\bm{s}^{\ast})+1$;

10 else $S(\bm{s}^{\ast})\leftarrow S(\bm{s}^{\ast})-1$;

11

12$\hat{\cal V}\leftarrow$ $n_{r}$ lower-scored majority class samples from
${\cal V}$ according to $S$;

13 ${\cal V}^{\star}\leftarrow{\cal V}\backslash\hat{\cal V}$;

return ${\cal V}^{\star}$

Algorithm 3 OPF-US Algorithm

Algorithm 3 implements the proposed method for undersampling purposes. Line
$1$ performs the training step of standard OPF, while the loop in Lines $2-7$
provides a given training sample $\bm{s}^{\ast}$ a score. Line $3$ finds the
training sample that conquers $\bm{t}$, and Line $4$ assigns the label of
$\bm{s}^{\ast}$ to it. Line $5$ checks whether sample $\bm{t}$ has been
classified correctly (score is increased in Line $6$) or not (score is
decreased in Line $7$). Later, in Line $8$, $\hat{\cal V}$ receives the
$n_{r}$ lower-scored samples of the majority class from ${\cal V}$, in which
$n_{r}$ stands for the difference between the number of samples from the
majority and minority classes. Finally, in Line $9$, such samples are removed
from the original training dataset.

Figure 1 glances the rationale behind the OPF-US working mechanism, where the
blue dots stand for the majority class samples. The main idea is to remove
training samples that do not contribute or add little to the classification of
unseen samples (represented here as the green dots). Solid blue dots denote
low-ranked samples, which are likely to be located in regions that figure some
degree of overlap between classes. Therefore, by pruning such samples, we
expect the number of misclassifications to drop considerably.

Figure 1: Illustration of the OPF-US process: translucent blue dots denote the
training set standard majority class samples, while solid blue dots stand for
the ones that misclassfied some minority class samples from the validation set
(illustrated as ‘X’ symbols in red). Light green dots represent minority class
samples from the validation set classified correctly. Notice that solid blue
samples are likely to be pruned in the proposed undersampling procedure.

####  3.1.1 OPF-US Computational Complexity

OPF-US complexity is, in large part, governed by the OPF classifier
complexity. According to Section 2.1, Line $1$ takes $\theta(\left|{\cal
V}\right|)$ steps. Further, Lines $2-7$ implement the main loop, which
requires $\theta(\left|{\cal T}\right|)$ runs. Besides, Line $3$ takes
$O(\left|{\cal V}\right|)$ steps, while the remaining lines (i.e., $4-7$)
figure a constant complexity, i.e., $\theta(1)$. Therefore, the whole loop
requires $O(\left|{\cal V}\right|.\left|{\cal T}\right|)$ computations.

Line $8$ extracts the majority samples from ${\cal V}$ according to their
scores, thus generating a smaller set $\hat{\cal V}$. Samples are sorted using
any traditional algorithm with complexity $\theta(\left|{\cal
V}\right|\log\left|{\cal V}\right|)$, for further removing the $n_{r}$ lower-
scored samples to $\hat{\cal V}$. This last step takes $\theta(n_{r})$. In
practice, Line $8$ takes $\theta(\left|{\cal V}\right|\log\left|{\cal
V}\right|)$ steps. Finally, in Line $9$, ${\cal V}^{\star}$ receives ${\cal
V}\backslash\hat{\cal V}$, which is performed in $\theta(\left|{\cal
V}\right|-\hat{\cal V}|)$ steps since both sets are sorted already. The final
complexity of the OPF-US algorithm is then given by $\theta(\left|{\cal
V}\right|)^{2}+\theta(\left|{\cal V}\right|\log\left|{\cal V}\right|)$, i.e.,
$\theta(\left|{\cal V}\right|)^{2}$.

####  3.1.2 OPF-US Variations

Despite the naive OPF-US, we also propose three variations for undersampling
purposes using the Optimum-Path Forest: (i) OPF-US1; (ii) OPF-US2; and the
(iii) OPF-US3. These techniques are described as follows:

  1. 1.

OPF-US1: remove samples from the majority class with negative scores only;

  2. 2.

OPF-US2: remove samples from the majority class with scores lower or equal to
zero; and

  3. 3.

OPF-US3: remove all samples with negative scores.

###  3.2 Oversampling with Optimum-Path Forest

Additionally to the OPF-US, the OPF algorithm can also be modified to perform
oversampling, hereinafter called Oversampling Optimum-Path Forest
($\text{O}^{2}$PF). In this case, one is concerned with generating new
training examples for the minority class while enforcing their diversity and
plausibility, i.e., new samples should share relevant characteristics with the
real ones. To fulfill that purpose, $\text{O}^{2}$PF employs the unsupervised
OPF to group training samples first and then estimate a Gaussian distribution
for each cluster111Clustering by OPF considers the groups can be modeled by
Gaussian distributions, but it is not limited to that.. With the parameters of
the model in hand, we can generate new samples accordingly.

Let ${\cal B}=\\{b_{1},b_{2},\dots,b_{c}\\}$ be the set of clusters computed
by unsupervised OPF, as described in Section 2.2. Also, Let $n_{s}$ be the
number of samples to be generated by the model, which are distributed
proportionally to the cluster’s size (i.e., the number of samples). Therefore,
the more dense the cluster, the higher the number of synthetic samples
generated within it. As such, some low-density clusters may not be able to
produce new samples. Such steps aim at fostering diversity among to-be-created
examples while keeping their distribution. Moreover, a new sample $\bm{z}$ can
be generated as follows:

$\bm{z}\sim\mathcal{N}(\bm{\mu}_{i},\bm{\Sigma}_{i}),$ (11)

where $\bm{\mu}_{i}$ and $\bm{\Sigma}_{i}$ denote the parameters of cluster
$b_{i}\in{\cal B}$.

To summarize, the proposed $\text{O}^{2}$PF algorithm consists of three
phases:

  1. 1.

To identify each cluster within the class to be oversampled.

  2. 2.

For each cluster $b_{i}\in{\cal B}$, we compute its mean vector $\bm{\mu}_{j}$
and covariance matrix $\bm{\Sigma}_{j}$.

  3. 3.

To generate new samples for each cluster based on the previous parameters.

It is worth mentioning that the last two steps can be parameterized, yielding
variants of the proposed method, as discussed in Section 3.2.2. Algorithm 4
implements $\text{O}^{2}$PF.

1

Input: Graph ${\cal G}_{s}=({\cal L},{\cal A}_{k})$ containing the minority
class training samples such that ${\cal L}\subset{\cal V}$, and the number
$n_{s}$ of synthetic samples to be generated.

Output: Set of minority class synthetic samples ${\cal L}^{\prime}$.

Auxiliary: Predecessor map $O$, path-cost map $C$, and cluster label map $L$,
and variables $tmp$ and $ctr$.

2

3$[O,C,L]\leftarrow$Algorithm 2$({\cal G}_{s})$;

4 ${\cal L}^{\prime}\leftarrow\emptyset$; $ctr\leftarrow 0$; ${\cal
B}\leftarrow$ load clusters;

5 for  _each $i\in\\{1,2,\ldots,\left|{\cal B}\right|\\}$ and $ctr<n_{s}$_ do

6 Compute the mean $\bm{\mu}_{i}$ and covariance matrix $\bm{\Sigma}_{i}$;

7 $tmp\leftarrow\left\lfloor\frac{\left|b_{i}\right|}{\left|{\cal
L}\right|}\times n_{s}\right\rfloor$;

8 for  _$1$ to $tmp$_ do

9 Generate sample $\bm{z}\sim\mathcal{N}(\bm{\mu}_{i},\bm{\Sigma}_{i})$;

10 ${\cal L}^{\prime}\leftarrow{\cal L}^{\prime}\cup\\{\bm{z}\\}$;
$ctr\leftarrow ctr+1$;

11

return ${\cal L}^{\prime}$

Algorithm 4 $\text{O}^{2}$PF Algorithm

Line $1$ performs data clustering using unsupervised OPF, and Line $2$
initializes the set of synthetic samples and the set of clusters. The main
loop (Lines $3-8$) is responsible for computing the cluster parameters (i.e.,
mean and covariance matrix), the number of samples to be generated according
to the cluster’s size (Line $5$), and sampling from the distributions (Lines
$6-8$). Finally, Line $9$ outputs the set of generated samples ${\cal
L}^{\prime}$.

####  3.2.1 $\text{O}^{2}$PF Computational Complexity

Considering the implementation provided by Algorithm 4, Line $1$ takes
$\theta(\left|{\cal L}\right|^{2})$ operations according to Section 2.2, while
Line $2$ takes $\theta(\left|{\cal L}\right|)$ operations using a linked list.
The main loop in Lines $3-9$ runs over $O(\left|{\cal B}\right|)$ iterations,
and the inner loop in Lines $6-8$ takes $n_{s}$ steps only once. Similarly,
Line $4$ also takes $\theta(\left|{\cal L}\right|)$ steps only once.
Therefore, the complexity of Lines $3-8$ is given by $O(\theta(\left|{\cal
L}\right|+n_{s})$. Last but not least, the final complexity of
$\text{O}^{2}$PF is given by $\theta(\left|{\cal
L}\right|^{2})+O(\theta(\left|{\cal L}\right|+n_{s})$, i.e.,
$\theta(\left|{\cal L}\right|^{2})$.

####  3.2.2 $\text{O}^{2}$PF Variations

Unsupervised learning by OPF aims to cluster the dataset in such a way that
groups of samples that share some degree of similarity are connected in the
feature space. Standard $\text{O}^{2}$PF estimates a Gaussian distribution for
each cluster computing the mean value and the covariance of the samples within
that cluster. In this paper, we also explored different methodologies to model
the data distribution for each cluster, as well as the approach to sampling
new data. As such, this paper also proposes four $\text{O}^{2}$PF variants,
described as follows:

  1. 1.

$\text{O}^{2}$PF Radius Interpolation ($\text{O}^{2}$PFRI): it replaces the
cluster mean by its geometric median $\bm{g}$, thus ideally making the model
more robust to outliers. Further, the sampling process is replaced by a radius
interpolation, i.e., each new instance is generated by randomly selecting the
$r$-th sample $\bm{x}_{r}\in{\cal V}$ in the cluster and interpolating it as
follows: ${\bm{z}^{\prime}=\beta\bm{x}_{r}}+(1-\beta)\bm{g}$, such that
${\beta\sim\mathcal{U}(0,\left[1+d(\bm{g},\bm{x}_{r})\right]^{-1})}$. Notice
$\bm{g}$ is updated after the generation of each new sample222In this paper,
$d(\cdot,\cdot)$ stands for the Euclidean distance, but any other
distance/similarity function can be used..

  2. 2.

$\text{O}^{2}$PF Mean Interpolation ($\text{O}^{2}$PFMI): after generating the
new sample $\bm{z}$, it is further interpolated with its nearest neighbor
$\bm{p}$ within the cluster as follows:
$\bm{z}^{\prime}=(1-\alpha)\bm{p}+\alpha\bm{z}$, in which
$\alpha\sim\mathcal{U}(0,1)$.

  3. 3.

$\text{O}^{2}$PF Prototype ($\text{O}^{2}$PFP): instead of using the cluster’s
mean as a parameter of the Gaussian distribution, as employed by standard
$\text{O}^{2}$PF, we use the prototype sample of that cluster instead. The
sampling process remains the same one used by $\text{O}^{2}$PF.

  4. 4.

$\text{O}^{2}$PF Weight Interpolation ($\text{O}^{2}$PFWI): it employs a
strategy that weights each sample according to its density (Equation 6).
Therefore, the cluster’s mean stands for the weighted average of its samples.
The sampling process remains the same one used by $\text{O}^{2}$PFMI.

###  3.3 Hybrid approaches

Despite the approaches introduced in this work, we also propose three hybrid
models that combine data undersampling and oversampling. The rationale behind
these models is to first remove less important samples (i.e., instances that
may lead to misclassification) for further generating new data that is likely
to be more reliable and adherent to the data distribution.

  1. 1.

OPF-US1-$\text{O}^{2}$PF: it removes samples from majority class with negative
scores using OPF-US1 for further oversampling using $\text{O}^{2}$PF.

  2. 2.

OPF-US2-$\text{O}^{2}$PF: it removes samples from majority class with negative
scores using OPF-US2 for further oversampling using $\text{O}^{2}$PF.

  3. 3.

OPF-US3-$\text{O}^{2}$PF: it removes all samples with negative scores using
OPF-US3 for further oversampling using $\text{O}^{2}$PF.

##  4 Methodology

This section presents the datasets and the experimental setup adopted in the
paper.

###  4.1 Datasets

The experiments are evaluated over three groups of applications that usually
suffer from imbalanced datasets: (i) dissolved gas analysis (comprises faults
on power transformers), (ii) a collection of medical-related datasets obtained
from UCI [36], and (iii) a compilation of general-purpose datasets, also
obtained from UCI.

####  4.1.1 Dissolved Gas Analysis Datasets

The Dissolved Gas Analysis (DGA) in insulating oil is a widely used method for
incipient fault interpretation in large oil-filled power transformers. For
fault diagnosis, there are $7$ main attributes to be observed, which are types
of gases produced by oil and cellulose decompositions from thermal and
electrical stresses that occur with equipment. The data used to create this
dataset was obtained from IEC TC10 [37], a Brazilian private power
distribution company [38, 39, 40], as well as from scientific articles
concerning DGA analysis [41]. The data is divided into three main classes:
normal (i.e., no-fault) samples ($1,012$ instances), thermal fault ($57$
instances), and electrical fault ($74$ instances). Finally, this data is
combined into six binary fault subsets to evaluate the proposed method,
described as follows:

  * 1.

1069_5gt and 1069_7gt: both subsets are composed of $1,069$ samples, where
$1,012$ ($94.67\%$) denote normal samples, while $57$ ($5.33\%$) represent
thermal faults333The 1069_5gt, 1086_5ge, and 1143_5gte datasets comprise five
types of gases, i.e., $H_{2}$, $CH_{4}$, $C_{2}H_{2}$, $C_{2}H_{4}$, and
$C_{2}H_{6}$. On the other hand, the 1069_7gt, 1086_7ge, and 1143_7gte
datasets are composed of the five gases mentioned before plus $CO$ and
$CO_{2}$..

  * 2.

1086_5ge and 1086_7ge: both subsets are composed of $1,086$ samples, where
$1,012$ ($93.19\%$) denote normal samples, while $74$ ($6.81\%$) represent
electrical faultsfootnote 3.

  * 3.

1143_5gte and 1143_7gte: both subsets are composed of $1,143$ samples, where
$1,012$ ($93.19\%$) denote normal samples, while $131$ ($11.46\%$) represent
thermal and electrical faultsfootnote 3.

####  4.1.2 Medical-related Datasets

We know that most medical datasets suffer from imbalance. In this paper, we
compiled several public datasets from different applications, described as
follows:

  * 1.

Wisconsin Breast Cancer Database (WBCD) Prognostic444Available at
https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Prognostic).:
it regards predicting a sample as recurrent or non-recurrent type of cancer
based on $32$ features. There are $198$ samples, being $151$ ($76.3\%$) non-
recurrent and $47$ ($23.7\%$) recurrent.

  * 2.

WBCD Diagnostic I555Available at
http://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+(diagnostic).:
it concerns classifying a tumor as benignant or malignant based on $32$
features as well. There are $569$ instances, from which $357$ ($63.7\%$) are
benign and $212$ ($37.3\%$) are malignant.

  * 3.

WBCD Diagnostic II666Available at
http://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Original).: it
corresponds to labeling each instance from a total of $699$ samples as benign
or malignant tumor. Each sample comprises $9$ features and each class contains
$458$ ($65.5\%$) and $241$ ($34.5\%$) samples, respectively.

  * 4.

Diabetic Retinopathy Debrecen (DRD)777Available at
https://archive.ics.uci.edu/ml/datasets/Diabetic+Retinopathy+Debrecen+Data+Set.:
it regards predicting whether an image contains signs of diabetic retinopathy
or not based on $19$ variables. The dataset contains $1,151$ samples, from
which $611$ ($53.1\%$) are positive and $540$ ($46.9\%$) are negative.

  * 5.

Cervical Cancer (CC)888Available at
https://archive.ics.uci.edu/ml/datasets/Cervical+cancer+%28Risk+Factors%29.:
it comprises $858$ samples from biopsies composed of $32$ features each. The
dataset is significantly skewed, with $55$ $(6.4\%)$ positive and $803$
($93.6\%$) negative samples.

  * 6.

Mammographic Mass (MM)999Available at
https://archive.ics.uci.edu/ml/datasets/Mammographic+Mass.: it concerns
predicting whether a mammographic mass is benign or malignant based on $6$
features. The dataset contains $516$ ($53.7\%$) benign and $445$ ($46.3\%$)
malignant samples, comprising $961$ samples.

####  4.1.3 General-Purpose Datasets

We also considered a set of datasets from different domains to evaluate the
proposed approaches, as follows:

  * 1.

Indian Liver (IL)101010Available at
https://archive.ics.uci.edu/ml/datasets/ILPD+(Indian+Liver+Patient+Dataset).:
it consists of predictions of liver diseases in $583$ individuals. The dataset
is composed of $416$ patients and $167$ individuals that are affected by
diseases. Each sample is composed of $10$ numerical attributes.

  * 2.

Secom111111https://archive.ics.uci.edu/ml/datasets/SECOM.: it is omposed of
$1,567$ samples from a semiconductor manufacturing process with $591$ features
each, where $104$ samples denote fail in a manufacturing testing procedure,
and the remaining $1,463$ passed in the test.

  * 3.

Seismic Bumps (SB)121212https://archive.ics.uci.edu/ml/datasets/seismic-
bumps.: it comprises $2,584$ samples with $19$ features from predictions of
dangerous seismic activities in underground coal mining, where $2,414$ samples
stand for negative predictions and $170$ for positive ones.

  * 4.

Spam131313https://archive.ics.uci.edu/ml/datasets/Spambase.: it regards spam
classification in e-mails. This dataset is slightly imbalanced, from which
$2,788$ are non-spam samples ($60.6\%$) and $1,813$ samples represent spam
($39.4\%$), totaling $4,601$ samples and $57$ numerical attributes.

  * 5.

Vertebral Column
(VC)141414https://archive.ics.uci.edu/ml/datasets/Vertebral+Column.: it
concerns the classification of orthopedic exams from column injuries
comprising $100$ samples from regular ($32.3\%$) and $210$ from abnormal
column ($67.7\%$), totaling $310$ samples with $6$ numerical attributes each.

  * 6.

Wilt151515https://archive.ics.uci.edu/ml/datasets/Wilt.: it regards the
prediction of diseased trees using numerical attributes acquired from a series
of Quickbird images. The dataset contains $4,839$ samples with $5$ features
each, where $4,578$ samples relate to non-diseased trees and only $261$
samples of diseased ones.

###  4.2 Experimental Setup

The paper employs three main approaches for dealing with imbalanced datasets
through OPF-based methods, i.e., oversampling, undersampling, and hybrid
methodologies considering undersampling followed by oversampling. For each
group of datasets, we compare the standard $\text{O}^{2}$PF and its variants
against seven state-of-the-art methods for dataset oversampling, i.e., SMOTE
[13], borderline SMOTE [14], ADASYN [15], AHC [21], MWMOTE [18], SOMO [20],
and KMeansSMOTE [19]. Similarly, we also compare standard OPF-US and its three
variants against five state-of-the-art baselines considered for data
undersampling, i.e., CNN [23], NearMiss-1 [22], NearMiss-2 [22], NearMiss-3
[22] and Radial-Based Undersampling [24]. Finally, the techniques that
obtained the best results are compared against themselves and three other
hybrid methods that combine OPF-US and $\text{O}^{2}$PF. The work adopted the
well-known F1 score for comparison purposes since it considers a weighted
average of the precision and recall, thus proper for evaluating imbalanced
datasets. Besides, we used standard datasets as baselines, and the recognition
rates are computed using the OPF classifier since it is a parameterless and
determinist approach. However, any other supervised technique could be used as
well.

Regarding the data pre-processing step, datasets with missing values were
filled with the average value of those respective features. Further, all
datasets were normalized using the standard scaler, which subtracts the mean
from each sample and scales it to unit variance. Moreover, all datasets were
randomly split into training, validation, and testing sets, with proportions
of $70\%$, $15\%$, and $15\%$, respectively. Such a configuration was chosen
empirically.

Considering the $\text{O}^{2}$PF, the validation set is employed to fine-tune
$k_{max}\in[5,10,20,30,40,50]$ parameter that maximizes the performance. A
similar approach was employed to find the best number of neighbors
$k\in[5,6,7,8,9,10]$ considering SMOTE, borderline SMOTE, ADASYN, MWMOTE, and
k-means SMOTE. Regarding the $k$-means SMOTE, the optimal number of clusters
$c\in[1,2,3,4,5,6,7,8,9,10]$ was found to maximize the performance of the
model. Regarding the Radial-based undersampling method, we adjusted parameter
$\gamma\in[0.001,0.01,0.1,1.0,10.0,100.0]$ in a similar fashion to the one
proposed by Koziarski [24]. Besides, SOMO employs the best set of parameters
defined by the authors, and AHC is parameterless.

For each dataset, the whole process was repeated during $20$ runs to compute
the mean recognition rates and standard deviations, and further perform
statistical analysis using the Wilcoxon signed-rank test [42] with $5\%$ of
significance. Finally, the code employed in this work was implemented in
Python161616Available at: https://github.com/Leandropassosjr/OpfImb and based
on the OPFython library [43, 44].

##  5 Experiments

This section discusses the experiments using the methodology presented earlier
concerning the proposed oversampling and undersampling approaches. For the
sake of explanation, the bolded values denote the most accurate F1 scores
according to the Wilcoxon signed-rank test with $5\%$ of significance.
Similarly, values underlined stand for the highest average F1 score overall
(absolute value) considering each dataset.

###  5.1 Oversampling Results

Results shown in Table 2 indicate the mean F1 score obtained after applying
the oversampling approaches to the problem of fault detection in power
transformers. One can observe the proposed approaches performed similarly to
the state-of-the-art baseline techniques. One can highlight $\text{{O}}^{2}$PF
and $\text{{O}}^{2}$PFRI, as well as two baselines, i.e., AHC and SOMO, which
obtained the best results in five out-of-six datasets. Moreover, half of the
best overall results were obtained by $\text{{O}}^{2}$PF-based approaches,
i.e., over 1069_5gt, 1143_5gte, and 1143_7gte datasets, while ADASYN, MWMOTE,
and $k$-means SMOTE produced the less significative performances. However, one
advantage of $\text{{O}}^{2}$PF and its variants concerns their number of
parameters, as presented in Table 1. Although SMOTE and ADASYN figure only one
parameter, they did not perform well in this context.

Table 1: Number of parameters for each oversampling technique.

Technique | Number of parameters
---|---
OPF-based ones | $1$
SMOTE [13] | $1$
Borderline SMOTE [14] | $2$
ADASYN [15] | $1$
AHC [21] | $0$
MWMOTE [18] | $3$
SOMO [20] | $1$
$k$-means SMOTE [19] | $2$

Table 2: Average F1 score values considering the oversampling tasks over DGA
datasets.

Technique / Dataset | 1069_5gt | 1069_7gt | 1086_5ge | 1086_7ge | 1143_5gte | 1143_7gte
---|---|---|---|---|---|---
$\text{{O}}^{2}$PF | $\bm{0.7282\pm 0.1116}$ | $\bm{0.6249\pm 0.1097}$ | $0.7328\pm 0.1052$ | $\bm{0.5501\pm 0.0950}$ | $\bm{0.7981\pm 0.0526}$ | $\bm{0.6871\pm 0.0822}$
$\text{O}^{2}$PFMI | $\bm{0.7198\pm 0.1101}$ | $0.5982\pm 0.1066$ | $0.6965\pm 0.1068$ | $\bm{0.5478\pm 0.1103}$ | $\bm{0.7866\pm 0.0695}$ | $\bm{0.6812\pm 0.0814}$
$\text{O}^{2}$PFRI | $\bm{0.7115\pm 0.0896}$ | $\bm{0.6798\pm 0.1005}$ | $0.7485\pm 0.1089$ | $\bm{0.5453\pm 0.1001}$ | $\underline{\bm{0.8095\pm 0.0570}}$ | $\bm{0.6857\pm 0.0875}$
$\text{O}^{2}$PFP | $\underline{\bm{0.7394\pm 0.0961}}$ | $0.6091\pm 0.1249$ | $0.6886\pm 0.1366$ | $\bm{0.5629\pm 0.1207}$ | $\bm{0.8029\pm 0.0752}$ | $\bm{0.6918\pm 0.0941}$
$\text{O}^{2}$PFWI | $0.7038\pm 0.1090$ | $0.5925\pm 0.0802$ | $0.6956\pm 0.1190$ | $\bm{0.5596\pm 0.1131}$ | $0.7843\pm 0.0770$ | $\underline{\bm{0.6922\pm 0.0885}}$
SMOTE [13] | $\bm{0.7053\pm 0.0894}$ | $0.5352\pm 0.0946$ | $0.6932\pm 0.1402$ | $0.5257\pm 0.1030$ | $0.7550\pm 0.0774$ | $\bm{0.6597\pm 0.0928}$
Borderline SMOTE [14] | $0.6892\pm 0.0794$ | $0.5977\pm 0.1151$ | $0.7119\pm 0.1213$ | $\underline{\bm{0.5698\pm 0.1066}}$ | $0.7469\pm 0.0701$ | $\bm{0.6862\pm 0.0812}$
ADASYN [15] | $0.6553\pm 0.0845$ | $0.5065\pm 0.1061$ | $0.6494\pm 0.1297$ | $0.5013\pm 0.0776$ | $0.7093\pm 0.0855$ | $0.6448\pm 0.0742$
AHC [21] | $\bm{0.7110\pm 0.0832}$ | $\bm{0.6690\pm 0.1048}$ | $\bm{0.7500\pm 0.1066}$ | $\bm{0.5645\pm 0.0981}$ | $0.7915\pm 0.0572$ | $\bm{0.6920\pm 0.0786}$
MWMOTE [18] | $\bm{0.7003\pm 0.1162}$ | $0.5334\pm 0.1073$ | $0.6779\pm 0.1115$ | $0.5029\pm 0.0788$ | $0.7477\pm 0.0751$ | $0.6343\pm 0.0739$
SOMO [20] | $\bm{0.7087\pm 0.0915}$ | $\underline{\bm{0.6830\pm 0.1035}}$ | $\underline{\bm{0.7659\pm 0.0992}}$ | $\bm{0.5369\pm 0.1063}$ | $0.7996\pm 0.0590$ | $\bm{0.6714\pm 0.0908}$
$k$-means SMOTE [19] | $0.6824\pm 0.1122$ | $0.5466\pm 0.1045$ | $0.6941\pm 0.1264$ | $0.5096\pm 0.0888$ | $0.7338\pm 0.0762$ | $\bm{0.6693\pm 0.0832}$

Table 3 presents the results over medical datasets, in which
$\text{{O}}^{2}$PF-based approaches obtained the best overall results in four-
out-of-six datasets. Statistically speaking, the proposed approaches obtained
the best results in all datasets. On the other hand, although MWMOTE performed
better than before (i.e., Table 2), it comprises more parameters than any
other technique.

Table 3: Average F1 score values considering the oversampling tasks over
medical datasets.

Technique / Dataset | Diagnostic | Diagnostic II | Prognostic | DDR | CC | MM
---|---|---|---|---|---|---
$\text{{O}}^{2}$PF | $\bm{0.9290\pm 0.0227}$ | $\underline{\bm{0.9240\pm 0.0290}}$ | $0.4034\pm 0.1282$ | $\underline{\bm{0.6125\pm 0.0354}}$ | $\bm{0.5666\pm 0.1437}$ | $\bm{0.6497\pm 0.0524}$
$\text{O}^{2}$PFMI | $\bm{0.9311\pm 0.0288}$ | $0.9129\pm 0.0329$ | $0.4096\pm 0.1043$ | $0.5813\pm 0.0476$ | $\bm{0.5667\pm 0.1308}$ | $0.6382\pm 0.0656$
$\text{O}^{2}$PFRI | $\bm{0.9321\pm 0.0238}$ | $0.9143\pm 0.0357$ | $\underline{\bm{0.4589\pm 0.1064}}$ | $0.5804\pm 0.0489$ | $0.5178\pm 0.1362$ | $\bm{0.6616\pm 0.0596}$
$\text{O}^{2}$PFP | $\bm{0.9312\pm 0.0238}$ | $0.9126\pm 0.0343$ | $0.4242\pm 0.1430$ | $0.5784\pm 0.0485$ | $0.5255\pm 0.1401$ | $0.6333\pm 0.0744$
$\text{O}^{2}$PFWI | $\bm{0.9324\pm 0.0248}$ | $0.9175\pm 0.0303$ | $\bm{0.4110\pm 0.1186}$ | $0.5804\pm 0.0495$ | $\underline{\bm{0.5774\pm 0.1263}}$ | $\bm{0.6313\pm 0.0819}$
SMOTE [13] | $\bm{0.9330\pm 0.0198}$ | $\bm{0.9170\pm 0.0331}$ | $0.4112\pm 0.1330$ | $0.5799\pm 0.0465$ | $\bm{0.5673\pm 0.0900}$ | $\bm{0.6591\pm 0.0545}$
Borderline SMOTE [14] | $0.9231\pm 0.0278$ | $0.9080\pm 0.0353$ | $0.4175\pm 0.1266$ | $0.5803\pm 0.0460$ | $\bm{0.5414\pm 0.1109}$ | $\underline{\bm{0.6710\pm 0.0479}}$
ADASYN [15] | $\bm{0.9264\pm 0.0285}$ | $\bm{0.9196\pm 0.0315}$ | $\bm{0.4366\pm 0.1413}$ | $0.5734\pm 0.0469$ | $\bm{0.5675\pm 0.0905}$ | $\bm{0.6631\pm 0.0567}$
AHC [21] | $\bm{0.9340\pm 0.0229}$ | $\bm{0.9210\pm 0.0352}$ | $0.4150\pm 0.1286$ | $\bm{0.5990\pm 0.0421}$ | $\bm{0.5240\pm 0.1209}$ | $\bm{0.6435\pm 0.0588}$
MWMOTE [18] | $\bm{0.9305\pm 0.0264}$ | $\bm{0.9223\pm 0.0302}$ | $0.4211\pm 0.1147$ | $0.5827\pm 0.0462$ | $\bm{0.5528\pm 0.1215}$ | $0.6349\pm 0.0643$
SOMO [20] | $\underline{\bm{0.9359\pm 0.0246}}$ | $\bm{0.9167\pm 0.0318}$ | $0.4028\pm 0.1328$ | $0.5804\pm 0.0478$ | $\bm{0.5121\pm 0.1306}$ | $0.6224\pm 0.0627$
$k$-means SMOTE [19] | $\bm{0.9345\pm 0.0273}$ | $0.9142\pm 0.0298$ | $\bm{0.4197\pm 0.1092}$ | $0.5757\pm 0.0468$ | $\bm{0.5575\pm 0.0774}$ | $\bm{0.6505\pm 0.0556}$

$\text{O}^{2}$PFMI obtained promising results over the general-purpose
datasets, once it obtained the most accurate overall results in half of the
datasets, as well as the best results in five-out-of-six datasets considering
the Wilcoxon analysis, together with three other $\text{O}^{2}$PF-based
approaches and four baselines, as shown in Table 4. Despite the statistical
similarity, the average values obtained by $\text{O}^{2}$PF-based approaches
are, in general, slightly better than the baselines.

Table 4: Average F1 score values considering the oversampling tasks over
general-purpose datasets. Symbol ‘-’ denotes the implementation provided did
not performed properly.

Technique / Dataset | Indian Liver | Secom | Seismic Bumps | Spam | Vertebral Column | Wilt
---|---|---|---|---|---|---
$\text{{O}}^{2}$PF | $\bm{0.4850\pm 0.0566}$ | $\bm{0.1536\pm 0.0357}$ | $\bm{0.1970\pm 0.0877}$ | $\bm{0.8712\pm 0.0144}$ | $\bm{0.6651\pm 0.1290}$ | $0.5189\pm 0.0507$
$\text{O}^{2}$PFMI | $\underline{\bm{0.4972\pm 0.0615}}$ | $\bm{0.1572\pm 0.0366}$ | $\underline{\bm{0.1987\pm 0.0808}}$ | $\underline{\bm{0.8740\pm 0.0132}}$ | $\bm{0.6524\pm 0.1333}$ | $0.6162\pm 0.0466$
$\text{O}^{2}$PFRI | $0.4516\pm 0.0625$ | $\bm{0.1383\pm 0.0340}$ | $0.1578\pm 0.0784$ | $\bm{0.8683\pm 0.0149}$ | $\bm{0.6518\pm 0.1388}$ | $\bm{0.6599\pm 0.0627}$
$\text{O}^{2}$PFP | $\bm{0.4791\pm 0.0731}$ | $\underline{\bm{0.1664\pm 0.0696}}$ | $\bm{0.1913\pm 0.0779}$ | $\bm{0.8721\pm 0.0128}$ | $\bm{0.6497\pm 0.1400}$ | $0.5661\pm 0.0891$
$\text{O}^{2}$PFWI | $\bm{0.4925\pm 0.0489}$ | $\bm{0.1557\pm 0.0375}$ | $\bm{0.1870\pm 0.0695}$ | $\bm{0.8718\pm 0.0177}$ | $\bm{0.6612\pm 0.1323}$ | $0.6256\pm 0.0460$
SMOTE [13] | $\bm{0.4699\pm 0.0652}$ | $\bm{0.1577\pm 0.0358}$ | $0.1581\pm 0.0588$ | $\bm{0.8706\pm 0.0155}$ | $\bm{0.6703\pm 0.1276}$ | $\underline{\bm{0.6677\pm 0.0498}}$
Borderline SMOTE [14] | $\bm{0.4769\pm 0.0551}$ | $\bm{0.1542\pm 0.0313}$ | $\bm{0.1751\pm 0.0676}$ | $0.8664\pm 0.0156$ | $\bm{0.6670\pm 0.1369}$ | $\bm{0.6616\pm 0.0471}$
ADASYN [15] | $\bm{0.4723\pm 0.0738}$ | $\bm{0.1531\pm 0.0390}$ | $0.1656\pm 0.0674$ | $0.8664\pm 0.0114$ | $\bm{0.6702\pm 0.1386}$ | $\bm{0.6659\pm 0.0555}$
AHC [21] | $0.4645\pm 0.0666$ | $\bm{0.1415\pm 0.0294}$ | $0.1580\pm 0.0786$ | $\bm{0.8710\pm 0.0158}$ | $\bm{0.6680\pm 0.1407}$ | $\bm{0.6575\pm 0.0537}$
MWMOTE [18] | $\bm{0.4700\pm 0.0739}$ | $\bm{0.1501\pm 0.0381}$ | $0.1754\pm 0.0650$ | $\bm{0.8728\pm 0.0183}$ | $\underline{\bm{0.6751\pm 0.1217}}$ | $\bm{0.6593\pm 0.0541}$
SOMO [20] | $0.4297\pm 0.1224$ | - | - | $\bm{0.8729\pm 0.0162}$ | $\bm{0.6623\pm 0.1376}$ | -
$k$-means SMOTE [19] | $\bm{0.4841\pm 0.0601}$ | $\bm{0.1583\pm 0.0363}$ | $0.1653\pm 0.0603$ | $\bm{0.8704\pm 0.0177}$ | $\bm{0.6625\pm 0.1250}$ | $\bm{0.6607\pm 0.0496}$

###  5.2 Undersampling Results

Table 6 shows the results concerning the undersampling strategies over DGA
datasets. The performance of OPF-US3 is paramount since it obtained the best
overall results in all datasets. Additionally, one can notice that none of the
baselines were capable of obtaining at least statistically similar results.
Table 5 presents the number of parameters of each technique, which is one of
the main advantages regarding the supervised OPF classifier with complete
graph.

Table 5: Number of parameters for each undersampling technique.

Technique | Number of parameters
---|---
OPF-based ones | $0$
CNN [23] | $1$
RBU [24] | $1$
NearMiss-1 [22] | $1$
NearMiss-2 [22] | $1$
NearMiss-3 [22] | $1$

Table 6: Average F1 score values considering the undersampling tasks over DGA
datasets.

Technique / Dataset | 1069_5gt | 1069_7gt | 1086_5ge | 1086_7ge | 1143_5gte | 1143_7gte
---|---|---|---|---|---|---
OPF-US | $0.5250\pm 0.0776$ | $0.3593\pm 0.0900$ | $0.4846\pm 0.0976$ | $0.3023\pm 0.0825$ | $0.6645\pm 0.0720$ | $0.5184\pm 0.0951$
OPF-US1 | $\bm{0.7053\pm 0.1063}$ | $\bm{0.6760\pm 0.1076}$ | $0.7666\pm 0.0964$ | $0.5357\pm 0.1024$ | $0.7798\pm 0.0750$ | $0.6748\pm 0.0955$
OPF-US2 | $\bm{0.7224\pm 0.1057}$ | $\bm{0.6488\pm 0.1074}$ | $0.7663\pm 0.0920$ | $0.5228\pm 0.0951$ | $\bm{0.7802\pm 0.0727}$ | $0.6450\pm 0.0975$
OPF-US3 | $\underline{\bm{0.7274\pm 0.0995}}$ | $\underline{\bm{0.6853\pm 0.1131}}$ | $\underline{\bm{0.8071\pm 0.0883}}$ | $\underline{\bm{0.5970\pm 0.1073}}$ | $\underline{\bm{0.7969\pm 0.0728}}$ | $\underline{\bm{0.6960\pm 0.0964}}$
CNN [23] | $0.4214\pm 0.2313$ | $0.2657\pm 0.0894$ | $0.4653\pm 0.1714$ | $0.3342\pm 0.1576$ | $0.5003\pm 0.1559$ | $0.4512\pm 0.1123$
RBU [24] | $0.3699\pm 0.2335$ | $0.2221\pm 0.1515$ | $0.4112\pm 0.2359$ | $0.1847\pm 0.0868$ | $0.3619\pm 0.2264$ | $0.3138\pm 0.1268$
NearMiss-1 [22] | $0.3875\pm 0.1482$ | $0.1467\pm 0.0483$ | $0.2586\pm 0.0556$ | $0.1384\pm 0.0304$ | $0.4288\pm 0.0905$ | $0.3007\pm 0.0461$
NearMiss-2 [22] | $0.0862\pm 0.0189$ | $0.1017\pm 0.0366$ | $0.1306\pm 0.0297$ | $0.1236\pm 0.0336$ | $0.2063\pm 0.0356$ | $0.2352\pm 0.0665$
NearMiss-3 [22] | $0.2871\pm 0.1712$ | $0.1334\pm 0.0564$ | $0.1638\pm 0.0387$ | $0.1247\pm 0.0318$ | $0.4420\pm 0.2282$ | $0.2727\pm 0.0417$

Results obtained over the medical datasets, provided in Table 7, describe a
scenario pretty much similar to the one mentioned above, i.e., OPF-US-based
approaches obtained the best results, with one standing out, i.e., OPF-US2.
Moreover, as well as in the DGA datasets, none of the baselines were capable
of obtaining statistically similar results.

Table 7: Average F1 score values considering the undersampling tasks over
medical datasets.

Technique / Dataset | Diagnostic | Diagnostic II | Prognostic | DDR | CC | MM
---|---|---|---|---|---|---
OPF-US | $\bm{0.9317\pm 0.0236}$ | $\bm{0.9334\pm 0.0228}$ | $\bm{0.4165\pm 0.1161}$ | $\underline{\bm{0.6879\pm 0.0304}}$ | $0.5260\pm 0.1203$ | $\bm{0.7032\pm 0.0564}$
OPF-US1 | $\bm{0.9259\pm 0.0251}$ | $\bm{0.9314\pm 0.0256}$ | $\bm{0.4040\pm 0.1487}$ | $0.6375\pm 0.0349$ | $\bm{0.5539\pm 0.1298}$ | $\bm{0.6911\pm 0.0566}$
OPF-US2 | $\underline{\bm{0.9319\pm 0.0230}}$ | $\underline{\bm{0.9359\pm 0.0214}}$ | $\underline{\bm{0.4360\pm 0.1303}}$ | $0.6768\pm 0.0339$ | $\underline{\bm{0.6088\pm 0.1544}}$ | $\underline{\bm{0.7223\pm 0.0578}}$
OPF-US3 | $\bm{0.9275\pm 0.0260}$ | $\bm{0.9311\pm 0.0269}$ | $0.3457\pm 0.1514$ | $0.6190\pm 0.0408$ | $\bm{0.5443\pm 0.1151}$ | $\bm{0.7173\pm 0.0499}$
CNN [23] | $0.8854\pm 0.0485$ | $0.8753\pm 0.0397$ | $0.3858\pm 0.1233$ | $0.6184\pm 0.0477$ | $0.3021\pm 0.1339$ | $0.6816\pm 0.0620$
RBU [24] | $\bm{0.9185\pm 0.0345}$ | $0.9101\pm 0.0327$ | $0.3601\pm 0.1418$ | $0.5798\pm 0.0466$ | $0.4053\pm 0.1140$ | $0.6565\pm 0.0489$
NearMiss-1 [22] | $0.9187\pm 0.0266$ | $0.9071\pm 0.0271$ | $0.3849\pm 0.1099$ | $0.5706\pm 0.0444$ | $0.3208\pm 0.0935$ | $0.6592\pm 0.0462$
NearMiss-2 [22] | $0.9182\pm 0.0264$ | $0.9086\pm 0.0331$ | $0.3742\pm 0.1309$ | $0.5773\pm 0.0485$ | $0.3531\pm 0.0778$ | $0.6734\pm 0.0475$
NearMiss-3 [22] | $0.9070\pm 0.0296$ | $0.9041\pm 0.0333$ | $0.3835\pm 0.1444$ | $0.5682\pm 0.0476$ | $0.1518\pm 0.0414$ | $0.6852\pm 0.0449$

Table 8 highlights that baseline methods performed slightly better over the
general-purpose datasets than in the other groups (Tables 6 and 7). In this
case, they reached results at least statistically similar to the best ones in
two datasets, i.e., Indian Liver and Vertebral Column. However, OPF-based
undersampling approaches are again paramount in the context, reaching the
highest average F1 values in all datasets, as well as statistically similar
results among themselves in most cases.

Table 8: Average F1 score values considering the undersampling tasks over
general-purpose datasets.

Technique / Dataset | Indian Liver | Secom | Seismic Bumps | Spam | Vertebral Column | Wilt
---|---|---|---|---|---|---
OPF-US | $\underline{\bm{0.5043\pm 0.0520}}$ | $\underline{\bm{0.1915\pm 0.0472}}$ | $\bm{0.1711\pm 0.0435}$ | $0.8691\pm 0.0157$ | $\bm{0.6415\pm 0.1210}$ | $0.3112\pm 0.0363$
OPF-US1 | $\bm{0.4829\pm 0.0668}$ | $0.1532\pm 0.0639$ | $\bm{0.1772\pm 0.0721}$ | $0.8751\pm 0.0158$ | $\bm{0.6553\pm 0.1392}$ | $\underline{\bm{0.6495\pm 0.0601}}$
OPF-US2 | $\bm{0.4975\pm 0.0492}$ | $\bm{0.1729\pm 0.0526}$ | $\underline{\bm{0.1917\pm 0.0663}}$ | $0.8680\pm 0.0159$ | $\bm{0.6353\pm 0.1247}$ | $\bm{0.6424\pm 0.0515}$
OPF-US3 | $0.4258\pm 0.0550$ | $0.1027\pm 0.0683$ | $0.1454\pm 0.0630$ | $\underline{\bm{0.8817\pm 0.0140}}$ | $\underline{\bm{0.6664\pm 0.1215}}$ | $\bm{0.6416\pm 0.0668}$
CNN [23] | $\bm{0.4826\pm 0.0668}$ | $0.1651\pm 0.0496$ | $0.1246\pm 0.0385$ | $0.8196\pm 0.0282$ | $\bm{0.6476\pm 0.1328}$ | $0.4054\pm 0.0846$
RBU [24] | $0.4599\pm 0.0555$ | $0.1253\pm 0.0305$ | $0.1270\pm 0.0426$ | $0.8558\pm 0.0170$ | $\bm{0.6447\pm 0.1197}$ | $0.1314\pm 0.0445$
NearMiss-1 [22] | $0.4077\pm 0.0661$ | $0.1716\pm 0.0539$ | $0.1451\pm 0.0284$ | $0.8511\pm 0.0147$ | $\bm{0.6340\pm 0.1508}$ | $0.1188\pm 0.0168$
NearMiss-2 [22] | $0.4762\pm 0.0501$ | $0.1512\pm 0.0562$ | $0.0945\pm 0.0218$ | $0.8480\pm 0.0138$ | $0.6195\pm 0.1348$ | $0.1127\pm 0.0134$
NearMiss-3 [22] | $\bm{0.5008\pm 0.0610}$ | $0.1265\pm 0.0304$ | $0.1064\pm 0.0247$ | $0.8186\pm 0.0189$ | $\bm{0.6604\pm 0.1257}$ | $0.2625\pm 0.0438$

###  5.3 Best Results and Hybrid Approaches

This section compares the F1 score values over the original datasets (i.e.,
without any sample generation) and the best techniques considering both
oversampling and undersampling tasks. Moreover, it also compares the results
with three proposed hybrid models that employ an undersampling operation
followed by an step approach, i.e., OPF-US1-$\text{{O}}^{2}$PF, OPF-
US2-$\text{{O}}^{2}$PF, and OPF-US3-$\text{{O}}^{2}$PF.

Considering the DGA scenario, Table 9 shows that OPF-US3-$\text{{O}}^{2}$PF
provided the best results in general, comprising the most accurate overall
values in half of the cases, as well as results statistically similar to the
best in all scenarios. Besides, OPF-US3 also performed remarkably well,
obtaining the best results according to the Wilcoxon signed-rank test in five
datasets, and the most accurate overall results in two.

Table 9: F1 score values concerning the best approaches from Tables 2 and 6
and hybrid versions over the DGA datasets.

Technique / Dataset | 1069_5gt | 1069_7gt | 1086_5ge | 1086_7ge | 1143_5gte | 1143_7gte
---|---|---|---|---|---|---
OPF (ORIGINAL) | $0.7087\pm 0.0915$ | $\bm{0.6804\pm 0.1032}$ | $0.7659\pm 0.0992$ | $0.5330\pm 0.1028$ | $\bm{0.8008\pm 0.0603}$ | $0.6697\pm 0.0909$
$\text{{O}}^{2}$PF | $\bm{0.7282\pm 0.1116}$ | $\bm{0.6249\pm 0.1097}$ | $0.7328\pm 0.1052$ | $0.5501\pm 0.0950$ | $\bm{0.7981\pm 0.0526}$ | $0.6871\pm 0.0822$
$\text{O}^{2}$PFRI | $0.7115\pm 0.0896$ | $\bm{0.6798\pm 0.1005}$ | $0.7485\pm 0.1089$ | $0.5453\pm 0.1001$ | $\underline{\bm{0.8095\pm 0.0570}}$ | $0.6857\pm 0.0875$
$\text{O}^{2}$PFP | $\bm{0.7394\pm 0.0961}$ | $0.6091\pm 0.1249$ | $0.6886\pm 0.1366$ | $\bm{0.5629\pm 0.1207}$ | $\bm{0.8029\pm 0.0752}$ | $0.6918\pm 0.0941$
$\text{O}^{2}$PFWI | $0.7038\pm 0.1090$ | $0.5925\pm 0.0802$ | $0.6956\pm 0.1190$ | $\bm{0.5596\pm 0.1131}$ | $0.7843\pm 0.0770$ | $0.6922\pm 0.0885$
Borderline SMOTE [14] | $0.6892\pm 0.0794$ | $0.5977\pm 0.1151$ | $0.7119\pm 0.1213$ | $\bm{0.5698\pm 0.1066}$ | $0.7469\pm 0.0701$ | $0.6862\pm 0.0812$
SOMO [20] | $0.7087\pm 0.0915$ | $\bm{0.6830\pm 0.1035}$ | $0.7659\pm 0.0992$ | $0.5369\pm 0.1063$ | $0.7996\pm 0.0590$ | $0.6714\pm 0.0908$
OPF-US | $0.5250\pm 0.0776$ | $0.3593\pm 0.0900$ | $0.4846\pm 0.0976$ | $0.3023\pm 0.0825$ | $0.6645\pm 0.0720$ | $0.5184\pm 0.0951$
OPF-US3 | $\bm{0.7274\pm 0.0995}$ | $\underline{\bm{0.6853\pm 0.1131}}$ | $\underline{\bm{0.8071\pm 0.0883}}$ | $\bm{0.5970\pm 0.1073}$ | $\bm{0.7969\pm 0.0728}$ | $0.6960\pm 0.0964$
OPF-US1-$\text{{O}}^{2}$PF | $0.7317\pm 0.1050$ | $0.5807\pm 0.0982$ | $0.7260\pm 0.1038$ | $0.5669\pm 0.1077$ | $\bm{0.7956\pm 0.0639}$ | $0.6895\pm 0.0731$
OPF-US2-$\text{{O}}^{2}$PF | $0.7007\pm 0.1084$ | $0.5878\pm 0.0945$ | $0.7369\pm 0.1061$ | $0.5093\pm 0.1021$ | $0.7737\pm 0.0800$ | $0.6489\pm 0.0885$
OPF-US3-$\text{{O}}^{2}$PF | $\underline{\bm{0.7718\pm 0.0854}}$ | $\bm{0.6673\pm 0.1120}$ | $\bm{0.8030\pm 0.1025}$ | $\underline{\bm{0.6198\pm 0.1010}}$ | $\bm{0.8060\pm 0.0715}$ | $\underline{\bm{0.7325\pm 0.0743}}$

Regarding the medical datasets, Table 10 shows that the overwhelming majority
of the best results were obtained by the OPF-based undersampling and hybrid
approaches, followed by $\text{O}^{2}$PF variants. Regarding the baselines,
the only succeeded case was obtained through SOMO over the Diagnostic dataset.

Table 10: F1 score values concerning the best approaches from Tables 3 and 7
and hybrid versions over the medical datasets.

Technique / Dataset | Diagnostic | Diagnostic II | Prognostic | DDR | CC | MM
---|---|---|---|---|---|---
OPF (ORIGINAL) | $0.9290\pm 0.0241$ | $0.9086\pm 0.0331$ | $0.4136\pm 0.1363$ | $0.6140\pm 0.0348$ | $0.4900\pm 0.1414$ | $0.6359\pm 0.0829$
$\text{{O}}^{2}$PF | $\bm{0.9290\pm 0.0227}$ | $0.9240\pm 0.0290$ | $0.4034\pm 0.1282$ | $0.6125\pm 0.0354$ | $\bm{0.5666\pm 0.1437}$ | $0.6497\pm 0.0524$
$\text{O}^{2}$PFRI | $\bm{0.9321\pm 0.0238}$ | $0.9143\pm 0.0357$ | $\underline{\bm{0.4589\pm 0.1064}}$ | $0.5804\pm 0.0489$ | $0.5178\pm 0.1362$ | $0.6616\pm 0.0596$
$\text{O}^{2}$PFWI | $\bm{0.9324\pm 0.0248}$ | $0.9175\pm 0.0303$ | $\bm{0.4110\pm 0.1186}$ | $0.5804\pm 0.0495$ | $\bm{0.5774\pm 0.1263}$ | $0.6313\pm 0.0819$
Borderline SMOTE [14] | $0.9231\pm 0.0278$ | $0.9080\pm 0.0353$ | $0.4175\pm 0.1266$ | $0.5803\pm 0.0460$ | $0.5414\pm 0.1109$ | $0.6710\pm 0.0479$
SOMO [20] | $\underline{\bm{0.9359\pm 0.0246}}$ | $0.9167\pm 0.0318$ | $0.4028\pm 0.1328$ | $0.5804\pm 0.0478$ | $0.5121\pm 0.1306$ | $0.6224\pm 0.0627$
OPF-US | $\bm{0.9317\pm 0.0236}$ | $\bm{0.9334\pm 0.0228}$ | $\bm{0.4165\pm 0.1161}$ | $\underline{\bm{0.6879\pm 0.0304}}$ | $0.5260\pm 0.1203$ | $\bm{0.7032\pm 0.0564}$
OPF-US2 | $\bm{0.9319\pm 0.0230}$ | $\bm{0.9359\pm 0.0214}$ | $\bm{0.4360\pm 0.1303}$ | $0.6768\pm 0.0339$ | $\bm{0.6088\pm 0.1544}$ | $\bm{0.7223\pm 0.0578}$
OPF-US1-$\text{{O}}^{2}$PF | $\bm{0.9291\pm 0.0278}$ | $\underline{\bm{0.9366\pm 0.0243}}$ | $\bm{0.4259\pm 0.1602}$ | $0.6250\pm 0.0392$ | $\bm{0.5852\pm 0.1142}$ | $0.6949\pm 0.0709$
OPF-US2-$\text{{O}}^{2}$PF | $\bm{0.9341\pm 0.0230}$ | $\bm{0.9357\pm 0.0200}$ | $\bm{0.4276\pm 0.1360}$ | $0.6569\pm 0.0319$ | $\bm{0.5991\pm 0.1433}$ | $\underline{\bm{0.7314\pm 0.0413}}$
OPF-US3-$\text{{O}}^{2}$PF | $\bm{0.9304\pm 0.0256}$ | $\bm{0.9343\pm 0.0255}$ | $0.3799\pm 0.1230$ | $0.6164\pm 0.0395$ | $\underline{\bm{0.6094\pm 0.1012}}$ | $\bm{0.7232\pm 0.0515}$

Finally, Table 11 exhibits the results considering the best
oversampling/undersampling approaches, as well as the hybrid models,
concerning the general-purpose datasets. Such results confirm the behavior
observed above in the other groups of datasets, i.e., better results are
provided by OPF-based undersampling and hybrid models, followed by
$\text{{O}}^{2}$PF and its variations.

Table 11: F1 score values concerning the best approaches from Tables 4 and 8
and hybrid versions over the general-purpose datasets.

Technique / Dataset | Indian Liver | Secom | Seismic Bumps | Spam | Vertebral Column | Wilt
---|---|---|---|---|---|---
OPF (ORIGINAL) | $0.4532\pm 0.0709$ | $0.1533\pm 0.0645$ | $0.1611\pm 0.0806$ | $0.8683\pm 0.0144$ | $\bm{0.6557\pm 0.1388}$ | $\bm{0.6411\pm 0.0658}$
$\text{{O}}^{2}$PF | $\bm{0.4850\pm 0.0566}$ | $0.1536\pm 0.0357$ | $0.1970\pm 0.0877$ | $0.8712\pm 0.0144$ | $\bm{0.6651\pm 0.1290}$ | $0.5189\pm 0.0507$
$\text{O}^{2}$PFMI | $\bm{0.4972\pm 0.0615}$ | $0.1572\pm 0.0366$ | $0.1987\pm 0.0808$ | $0.8740\pm 0.0132$ | $\bm{0.6524\pm 0.1333}$ | $0.6162\pm 0.0466$
$\text{O}^{2}$PFP | $\bm{0.4791\pm 0.0731}$ | $\bm{0.1664\pm 0.0696}$ | $0.1913\pm 0.0779$ | $0.8721\pm 0.0128$ | $\bm{0.6497\pm 0.1400}$ | $0.5661\pm 0.0891$
SMOTE [13] | $\bm{0.4699\pm 0.0652}$ | $0.1577\pm 0.0358$ | $0.1581\pm 0.0588$ | $0.8706\pm 0.0155$ | $\bm{0.6703\pm 0.1276}$ | $\underline{\bm{0.6677\pm 0.0498}}$
MWMOTE [18] | $0.4700\pm 0.0739$ | $0.1501\pm 0.0381$ | $0.1754\pm 0.0650$ | $0.8728\pm 0.0183$ | $\underline{\bm{0.6751\pm 0.1217}}$ | $\bm{0.6593\pm 0.0541}$
OPF-US | $\underline{\bm{0.5043\pm 0.0520}}$ | $\underline{\bm{0.1915\pm 0.0472}}$ | $0.1711\pm 0.0435$ | $0.8691\pm 0.0157$ | $0.6415\pm 0.1210$ | $0.3112\pm 0.0363$
OPF-US1 | $\bm{0.4829\pm 0.0668}$ | $0.1532\pm 0.0639$ | $0.1772\pm 0.0721$ | $0.8751\pm 0.0158$ | $\bm{0.6553\pm 0.1392}$ | $\bm{0.6495\pm 0.0601}$
OPF-US2 | $\bm{0.4975\pm 0.0492}$ | $\bm{0.1729\pm 0.0526}$ | $\bm{0.1917\pm 0.0663}$ | $0.8680\pm 0.0159$ | $0.6353\pm 0.1247$ | $0.6424\pm 0.0515$
OPF-US3 | $0.4258\pm 0.0550$ | $0.1027\pm 0.0683$ | $0.1454\pm 0.0630$ | $0.8817\pm 0.0140$ | $\bm{0.6664\pm 0.1215}$ | $\bm{0.6416\pm 0.0668}$
OPF-US1-$\text{{O}}^{2}$PF | $\bm{0.5032\pm 0.0556}$ | $0.1528\pm 0.0386$ | $0.1985\pm 0.0889$ | $0.8775\pm 0.0171$ | $\bm{0.6579\pm 0.1328}$ | $0.5299\pm 0.0467$
OPF-US2-$\text{{O}}^{2}$PF | $\bm{0.4989\pm 0.0489}$ | $0.1605\pm 0.0442$ | $\bm{0.2152\pm 0.0694}$ | $0.8707\pm 0.0130$ | $0.6330\pm 0.1207$ | $0.4929\pm 0.0538$
OPF-US3-$\text{{O}}^{2}$PF | $\bm{0.4807\pm 0.0528}$ | $\bm{0.1541\pm 0.0459}$ | $\underline{\bm{0.2297\pm 0.0770}}$ | $\underline{\bm{0.8848\pm 0.0133}}$ | $\bm{0.6718\pm 0.1219}$ | $0.5387\pm 0.0422$

###  5.4 Discussion

The experiments conducted in the paper, which comprised a total of $18$
datasets and divided into three groups, i.e., DGA, medical, and general-
purpose, confirm the efficiency and robustness of the proposed OPF-based
models for oversampling, compared against seven state-of-the-art methods, and
undersampling tasks, compared against five state-of-the-art approaches, as
well as the three hybrid approaches.

In general, $\text{{O}}^{2}$PF and its variants outperformed the baselines
considering the oversampling methods in most cases, stressing that the general
performance of standard $\text{{O}}^{2}$PF and some variations performed
better than others according to each group of datasets. Concerning the
undersampling tasks, OPF-US and its variations obtained promising results,
outperforming all state-of-the-art approaches in virtually any scenario.

An additional round of experiments was conducted in the previous section,
where the best oversampling and undersampling techniques are compared against
the OPF-based hybrid models. One can observe that both undersampling and
hybrid approaches compete for the best results, leaving little space for
oversampling or the baseline techniques.

We understand that creating samples is more complicated than just removing
them in imbalanced scenarios. Also, we are not eliminating any sample but the
less relevant ones according to a ranked list of scores. On the other hand,
oversampling methods may change the distribution of data when the synthetic
samples are generated, ending up in a more complicated classification task.

Regarding the hybrid models, they were statistically similar to undersampling
approaches in most cases. However, for some datasets, the hybrid models
outperformed by far the second-best techniques. We can highlight some results
over DGA datasets in Table 9, e.g., 1069_5gt, in which OPF-US3-O2OPF obtained
an F1 score of $0.77$, and the second-best one achieved $0.73$. Similar
behaviors can be observed in 1143_7gte and Seismic Bumps datasets as well.

Such results lead us to believe that oversampling is essential, but we first
need to sanitize data, e.g., counterfeit samples, to avoid their propagation
towards the synthetic samples. Since OPF explores the strength of connectivity
among samples in the feature spaces no matter they are distant or not, it can
learn data distribution better than others in some situations.

###  5.5 Visual Analysis of Data Distribution

In this section, we showed the feature space provided by the proposed
approaches is well behaved, ending up in better recognition rates. Figure 2
illustrates this behavior for three datasets, i.e., one per group of
applications, where the leftmost column denotes the 1069_5gt dataset, in the
middle one can report to the Cervical Cancer dataset, and the rightmost column
stands for the Spam dataset. For the sake of visualization, we applied the
well-known t-SNE [45] approach for 2-D data transformation. Moreover, the rows
correspond to different scenarios: original dataset in the first row,
oversampling through $\text{O}^{2}$PF in the second row, undersampling through
OPF-US in the third row, and undersampling followed by oversampling using OPF-
US3-$\text{O}^{2}$PF in the fourth row.

Considering 1069_5gt dataset, despite the label imbalance and some minority-
class outliers (Figure 2a), it presents a reasonably well-behaved feature
space. Such an effect is maximized by the oversampling approach in Figure 2d,
thus providing more accurate results. On the other hand, pruning majority-
class samples do not seem to improve the classification performance in this
case (see Figure 2g and OPF-US results in Table 9), since minority-class
outliers became more significant in the reduced set of samples. However,
pruning the minority-class outliers (see OPF-US3 results in Table 9) seems to
reverse this situation. Moreover, applying the OPF-US3 followed by an
oversampling approach (Figure 2j and and OPF-US3-$\text{{O}}^{2}$PF results in
Table 9) stands for the ideal scenario, obtaining the best overall results.

Cervical Cancer shows itself as a dataset highly imbalanced whose original
samples from both classes may look overlapped (Figure 2b). However, the pruned
version depicted in Figure 2h seems to promote a distribution were data
separability is straightforward. Further, the hybrid approach benefits from
such a phenomenon, thus obtaining the most accurate overall results, as
observed in Tables 7 and 10.

Although the imbalance presented in the Spam dataset is less incisive, it
presents some similarities with 1069_5gt regarding minority-class outliers
among majority class samples, as observed in Figure 2c. However, a hybrid
approach, where the less significative samples from majority class are pruned
and several samples from minority class are properly created, appears to be
the best approach for the problem, as presented in Table 11.

(a) (b) (c)

(d) (e) (f)

(g) (h) (i)

(j) (k) (l)

Figure 2: The leftmost column denotes the 1069_5gt dataset, the middle one
stands for the Cervical Cancer dataset, and the rightmost column represents
the Spam dataset. Further, the first row denotes the original datasets, the
second row represents oversampling through $\text{O}^{2}$PF, undersampling
through OPF-US is depicted in the third row, and undersampling followed by
oversampling using OPF-US3-$\text{O}^{2}$PF is illustrated in the fourth row.

##  6 Conclusions

This paper tackled the problem of handling imbalanced datasets proposing
several Optimum-Path Forest-based techniques for both data oversampling and
undersampling. More specifically, the paper proposes four $\text{O}^{2}$PF-
based oversampling variations, i.e., $\text{O}^{2}$PFRI, $\text{O}^{2}$PFMI,
$\text{O}^{2}$PFP, and $\text{O}^{2}$PFWI, as well as four undersampling
approaches, i.e., OPF-US and its variations OPF-US1, OPF-US2, and OPF-US3.
Moreover, we also proposed three hybrid models, which combine standard
$\text{O}^{2}$PF with OPF-US1, OPF-US2, and OPF-US3.

An in-depth section of experiments conducted over $18$ datasets composed of
distinct imbalance degrees, and considering $7$ state-of-the-art approaches
for oversampling and $5$ other techniques for undersampling purposes,
validates the effectiveness of the proposed methods, stressing the
undersampling and hybrid methods, which overwhelmingly outperformed the
baselines.

Regarding future works, we plan to extend the techniques to deal with multiple
labels. Besides, we also intend to consider other variations of the supervised
OPF classifier.

## Acknowledgments

The authors are grateful to FAPESP grants #2020/12101-0, #2013/07375-0,
#2014/12236-1, #2017/02286-0, #2018/21934-5, #2019/07665-4, and #2019/18287-0,
as well as CNPq grants #307066/2017-7, and #427968/2018-6.

## References

## References

  * [1] R. O’Brien, H. Ishwaran, A random forests quantile classifier for class imbalanced data, Pattern Recognition 90 (2019) 232–249.  doi:https://doi.org/10.1016/j.patcog.2019.01.036.
  * [2] C. Chen, A. Liaw, L. Breiman, et al., Using random forest to learn imbalanced data, Tech. Rep. 666, University of California, Berkeley (July 2004).
  * [3] L. Wang, H. Cheng, Z. Zheng, A. Yang, X. Zhu, Ponzi scheme detection via oversampling-based long short-term memory for smart contracts, Knowledge-Based Systems 228 (2021) 107312.  doi:https://doi.org/10.1016/j.knosys.2021.107312.
  * [4] N. Jiang, N. Li, A wind turbine frequent principal fault detection and localization approach with imbalanced data using an improved synthetic oversampling technique, International Journal of Electrical Power & Energy Systems 126 (2021) 106595.  doi:https://doi.org/10.1016/j.ijepes.2020.106595.
  * [5] W. C. Sleeman IV, B. Krawczyk, Multi-class imbalanced big data classification on spark, Knowledge-Based Systems 212 (2021) 106598.  doi:https://doi.org/10.1016/j.knosys.2020.106598.
  * [6] K. Oksuz, B. C. Cam, S. Kalkan, E. Akbas, Imbalance Problems in Object Detection: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence 43 (10) (2021) 3388–3415.  doi:10.1109/TPAMI.2020.2981890.
  * [7] X. Jing, X. Zhang, X. Zhu, F. Wu, X. You, Y. Gao, S. Shan, J. Yang, Multiset Feature Learning for Highly Imbalanced Data Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence 43 (1) (2021) 139–156.  doi:10.1109/TPAMI.2019.2929166.
  * [8] C. Huang, Y. Li, C. L. Chen, X. Tang, Deep Imbalanced Learning for Face Recognition and Attribute Prediction, IEEE Transactions on Pattern Analysis and Machine Intelligence 42 (11) (2020) 2781–2794.  doi:10.1109/TPAMI.2019.2914680.
  * [9] G. Kovács, An empirical comparison and evaluation of minority oversampling techniques on a large number of imbalanced datasets, Applied Soft Computing 83 (2019) 105662.  doi:https://doi.org/10.1016/j.asoc.2019.105662.
  * [10] R. Malhotra, S. Kamal, An empirical study to investigate oversampling methods for improving software defect prediction using imbalanced data, Neurocomputing 343 (2019) 120–140.  doi:https://doi.org/10.1016/j.neucom.2018.04.090.
  * [11] I. Cordón, S. García, A. Fernández, F. Herrera, Imbalance: Oversampling algorithms for imbalanced classification in r, Knowledge-Based Systems 161 (2018) 329–341.  doi:https://doi.org/10.1016/j.knosys.2018.07.035.
  * [12] J. A. Sáez, B. Krawczyk, M. Woźniak, Analyzing the oversampling of different classes and types of examples in multi-class imbalanced datasets, Pattern Recognition 57 (2016) 164–178.  doi:https://doi.org/10.1016/j.patcog.2016.03.012.
  * [13] N. V. Chawla, K. W. Bowyer, L. O. Hall, W. P. Kegelmeyer, SMOTE: Synthetic Minority Over-sampling Technique, Journal of Artificial Intelligence Research 16 (2002) 321–357.  doi:https://doi.org/10.1613/jair.953.
  * [14] H. Han, W.-Y. Wang, B.-H. Mao, Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning, in: Advances in Intelligent Computing, Vol. 3644, Springer Berlin Heidelberg, Berlin, Heidelberg, 2005, pp. 878–887.  doi:https://doi.org/10.1007/11538059_91.
  * [15] H. He, Y. Bai, E. A. Garcia, S. Li, ADASYN: Adaptive synthetic sampling approach for imbalanced learning, in: 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), IEEE, 2008, pp. 1322–1328.  doi:10.1109/IJCNN.2008.4633969.
  * [16] X. Liang, A. Jiang, T. Li, Y. Xue, G. Wang, LR-SMOTE — An improved unbalanced data set oversampling based on K-means and SVM, Knowledge-Based Systems 196 (2020) 105845.  doi:https://doi.org/10.1016/j.knosys.2020.105845.
  * [17] E. Elyan, C. F. Moreno-Garcia, C. Jayne, CDSMOTE: class decomposition and synthetic minority class oversampling technique for imbalanced-data classification, Neural Computing and Applications 33 (7) (2021) 2839–2851.  doi:https://doi.org/10.1007/s00521-020-05130-z.
  * [18] S. Barua, M. M. Islam, X. Yao, K. Murase, MWMOTE–Majority Weighted Minority Oversampling Technique for Imbalanced Data Set Learning, IEEE Transactions on Knowledge and Data Engineering 26 (2) (2014) 405–425.  doi:10.1109/TKDE.2012.232.
  * [19] G. Douzas, F. Bacao, F. Last, Improving imbalanced learning through a heuristic oversampling method based on k-means and SMOTE, Information Sciences 465 (2018) 1––20.  doi:https://doi.org/10.1016/j.ins.2018.06.056.
  * [20] G. Douzas, F. Bacao, Self-Organizing Map Oversampling (SOMO) for imbalanced data set learning, Expert Systems with Applications 82 (2017) 40–52.  doi:https://doi.org/10.1016/j.eswa.2017.03.073.
  * [21] G. Cohen, M. Hilario, H. Sax, S. Hugonnet, A. Geissbuhler, Learning from imbalanced data in surveillance of nosocomial infection, Artificial Intelligence in Medicine 37 (1) (2006) 7–18, intelligent Data Analysis in Medicine.  doi:https://doi.org/10.1016/j.artmed.2005.03.002.
  * [22] I. Mani, I. Zhang, kNN approach to unbalanced data distributions: a case study involving information extraction, in: Proceedings of Workshop on Learning from Imbalanced Datasets, Vol. 126, 2003.
  * [23] P. Hart, The condensed nearest neighbor rule (corresp.), IEEE Transactions on Information Theory 14 (3) (1968) 515–516.  doi:10.1109/TIT.1968.1054155.
  * [24] M. Koziarski, Radial-based undersampling for imbalanced data classification, Pattern Recognition 102 (2020) 107262.  doi:https://doi.org/10.1016/j.patcog.2020.107262.
  * [25] C. Cervellera, D. Macciò, Voronoi tree models for distribution-preserving sampling and generation, Pattern Recognition 97 (2020) 107002.  doi:https://doi.org/10.1016/j.patcog.2019.107002.
  * [26] J. P. Papa, A. X. Falcão, C. T. N. Suzuki, Supervised pattern classification based on optimum-path forest, International Journal of Imaging Systems and Technology 19 (2) (2009) 120–131.  doi:https://doi.org/10.1002/ima.20188.
  * [27] J. P. Papa, A. X. Falcão, V. H. C. Albuquerque, J. M. R. S. Tavares, Efficient supervised optimum-path forest classification for large datasets, Pattern Recognition 45 (1) (2012) 512–520.  doi:https://doi.org/10.1016/j.patcog.2011.07.013.
  * [28] J. P. Papa, S. E. N. Fernandes, A. X. Falcão, Optimum-Path Forest based on k-connectivity: Theory and Applications, Pattern Recognition Letters 87 (2017) 117–126.  doi:https://doi.org/10.1016/j.patrec.2016.07.026.
  * [29] L. M. Rocha, F. A. M. Cappabianco, A. X. Falcão, Data clustering as an optimum-path forest problem with applications in image analysis, International Journal of Imaging Systems and Technology 19 (2) (2009) 50–68.  doi:https://doi.org/10.1002/ima.20191.
  * [30] R. R. Guimarães, L. A. Passos, R. Holanda Filho, V. H. C. de Albuquerque, J. J. Rodrigues, M. M. Komarov, J. P. Papa, Intelligent Network Security Monitoring Based on Optimum-Path Forest Clustering, IEEE Network 33 (2) (2018) 126–131.  doi:10.1109/MNET.2018.1800151.
  * [31] R. W. R. Souza, J. V. C. Oliveira, L. A. Passos, W. Ding, J. P. Papa, V. H. Albuquerque, A Novel Approach for Optimum-Path Forest Classification Using Fuzzy Logic, IEEE Transactions on Fuzzy Systems 28 (12) (2020) 3076–3086.  doi:10.1109/TFUZZ.2019.2949771.
  * [32] G. H. Rosa, K. A. Costa, L. A. Passos, J. P. Papa, A. X. Falcão, J. M. R. Tavares, On the training of artificial neural networks with radial basis function using optimum-path forest clustering, in: 2014 22nd International Conference on Pattern Recognition, IEEE, 2014, pp. 1472–1477.  doi:10.1109/ICPR.2014.262.
  * [33] L. C. S. Afonso, L. A. Passos, J. P. Papa, Enhancing Brain Storm Optimization Through Optimum-Path Forest, in: 2018 IEEE 12th International Symposium on Applied Computational Intelligence and Informatics (SACI), IEEE, 2018, pp. 000183–000188.  doi:10.1109/SACI.2018.8440918.
  * [34] L. A. Passos, D. S. Jodas, L. C. F. Ribeiro, T. Pinheiro, J. P. Papa, $\text{O}^{2}$PF: Oversampling via Optimum-Path Forest for Breast Cancer Detection, in: 2020 IEEE 33th International Symposium on Computer-Based Medical Systems, IEEE, 2020, pp. 498–503.  doi:10.1109/CBMS49503.2020.00100.
  * [35] S. E. N. Fernandes, J. P. Papa, Improving optimum-path forest learning using bag-of-classifiers and confidence measures, Pattern Analysis and Applications 22 (2) (2019) 703–716.  doi:https://doi.org/10.1007/s10044-017-0677-9.
  * [36] D. Dua, C. Graff, UCI machine learning repository (2017).
URL http://archive.ics.uci.edu/ml

  * [37] M. Duval, A. DePabla, Interpretation of gas-in-oil analysis using new IEC publication 60599 and IEC TC 10 databases, IEEE Electrical Insulation Magazine 17 (2) (2001) 31–41.  doi:10.1109/57.917529.
  * [38] G. Lupi Filho, Comparação entre os critérios de diagnósticos por análise cromatográfica de gases dissolvidos em óleo isolante de transformador de potência, Ph.D. thesis, Universidade de São Paulo (2012).
  * [39] S. Ghoneim, S. A. Ward, Dissolved Gas Analysis as a Diagnostic Tools for Early Detection of Transformer Faults, Advances in Electrical Engineering Systems 1 (3) (2012) 152–156.
  * [40] R. Soni, K. Chaudhari, An approach to diagnose incipient faults of power transformer using dissolved gas analysis of mineral oil by ratio methods using fuzzy logic, in: 2016 International Conference on Signal Processing, Communication, Power and Embedded System (SCOPES), IEEE, 2016, pp. 1894–1899.  doi:10.1109/SCOPES.2016.7955775.
  * [41] M. D. Equbal, S. A. Khan, T. Islam, Transformer incipient fault diagnosis on the basis of energy-weighted DGA using an artificial neural network, Turkish Journal of Electrical Engineering & Computer Sciences 26 (1) (2018) 77–88.  doi:10.3906/elk-1704-229.
  * [42] F. Wilcoxon, Individual comparisons by ranking methods, Biometrics Bulletin 1 (6) (1945) 80–83.  doi:https://doi.org/10.2307/3001968.
  * [43] G. H. de Rosa, J. P. Papa, A. X. Falcão, OPFython: A Python-Inspired Optimum-Path Forest Classifier (2020).  arXiv:2001.10420.
  * [44] G. H. de Rosa, J. P. Papa, OPFython: A Python implementation for Optimum-Path Forest, Software Impacts 9 (2021) 100113.  doi:https://doi.org/10.1016/j.simpa.2021.100113.
  * [45] L. v. d. Maaten, G. Hinton, Visualizing data using t-SNE, Journal of Machine Learning Research 9 (86) (2008) 2579–2605.