O2PF: Oversampling via Optimum-Path Forest for

Breast Cancer Detection

Leandro A. Passos∗ , Danilo S. Jodas∗ , Luiz C. F. Ribeiro∗ , Thierry Pinheiro, João P. Papa
Department of Computing
São Paulo State University
Bauru, Brazil
{[Link], [Link], [Link]}@[Link], {danilojodas, thierrypin}@[Link]
arXiv:2101.05775v1 [[Link]] 14 Jan 2021

Abstract—Breast cancer is among the most deadly diseases, dis- breast cancer diagnosis consists of a visual analysis performed
tressing mostly women worldwide. Although traditional methods by professionals aiming to identify possible abnormalities
for detection have presented themselves as valid for the task, they (e.g., nodules), which may indicate cancer risk signs. Once
still commonly present low accuracies and demand considerable
time and effort from professionals. Therefore, a computer-aided identified, it is possible to extract relevant measures from such
diagnosis (CAD) system capable of providing early detection nodules, assisting physicians to judge the presence or absence
becomes hugely desirable. In the last decade, machine learning- of cancerous tissue.
based techniques have been of paramount importance in this Many image processing-based algorithms have also been
context, since they are capable of extracting essential information proposed to help in such tasks [5]–[7], as well as machine
from data and reasoning about it. However, such approaches
still suffer from imbalanced data, specifically on medical issues, learning techniques, which have been commonly employed for
where the number of healthy people samples is, in general, both nodule segmentation and classification. Agarap [8], for
considerably higher than the number of patients. Therefore instance, studied the performance of several machine learning
this paper proposes the O2 PF, a data oversampling method techniques to label a nodule as benign or malignant. Further,
based on the unsupervised Optimum-Path Forest Algorithm. Passos et al. [9] developed a neural network to tell benign
Experiments conducted over the full oversampling scenario
state the robustness of the model, which is compared against from malignant nodules, and to label the latter according to
three well-established oversampling methods considering three the most likely cancer type.
breast cancer and three general-purpose tasks for medical issues Moreover, once the nodules can be seen as abnormalities,
datasets. their identification can also be tackled in an unsupervised
Index Terms—Data imbalance, Oversampling, Optimum-Path fashion. In such a direction, Ribeiro et al. [10] used the unsu-
Forest.
pervised Optimum-Path Forest (OPF) [11] algorithm to distinct
malignant nodes from benign, obtaining significant results.
I. I NTRODUCTION
The unsupervised Optimum-Path Forest algorithm possesses
Computer-Aided Diagnosis (CAD) systems aim at helping properties commonly employed to improve other machine
physicians to quickly report better diagnosis to patients, thus learning techniques, such as the Brainstorm Optimization [12],
representing an essential step towards dangerous disease accu- as well as to create new techniques, such as the OPF-based
rate diagnosis. Besides, intelligent-based CAD systems have approach for anomaly detection [13] and the Fuzzy OPF
successfully employed machine learning techniques, a promis- classifier [14].
ing subfield of artificial intelligence, to tackle complicated Although the above-mentioned techniques obtained promis-
problems that demand knowledge and reasoning about the ing results in the context of breast cancer detection, most
subject. Regarding the latter, several works were developed of the classification algorithms usually suffer from imbal-
in the last few years to aid detecting atherosclerosis [1], anced dataset problems, which arises when the number of
Parkinson’s disease [2], and breast cancer [3], to name a few. samples among classes differs significantly. In this scenario,
Breast cancer is a dangerous illness, affecting millions of the trained classifier is more likely to label a new sample as
women, as well as few men, around the world. According to belonging to the most common (majority) class, degrading
the World Health Organization, such a disease was responsible its performance for the smallest (minority) class. Moreover,
for the death of approximately 627, 000 women in 2018 such a situation may degenerate when the dataset presents
worldwide [4]. Therefore, early diagnosis is crucial to effec- outliers. Numerous studies have also been proposed to cope
tively prevent its progress, consequently making it possible to with such a problem in medical datasets [15]–[17]. Therefore,
elaborate more efficient treatment plans. In general, standard the generation of synthetic samples for the minority class,
which is usually referred to as oversampling, is recognized as a
∗ Authorscontributed equally. prominent contribution to rebalancing the dataset for classifier
The authors would like to thank FAPESP grants #2013/07375-0,
#2014/12236-1, #2019/18287-0, and #2019/07665-4, as well as CNPq grants training purposes, consequently improving their robustness to
#427968/2018-6 and #307066/2017-7. label minority class samples correctly. In this context, several
powerful oversampling strategies have been proposed in the by minimizing the normalized graph cut function, as it takes
literature to tackle such a problem [18]–[20], most of them into account the dissimilarities between clusters as well as the
still presenting difficulties while enforcing diversity among similarity degree among samples of each cluster.
new synthetic samples, which denotes a problem that worth Concerning the second step, the algorithm must select the
to be addressed, since it can improve classifier generalization prototypes to form the root of each OPT (which will ultimately
properties. form clusters) to rule the competition process and conquer
To such an extent, this work proposes an approach to per- the remaining samples in the graph. The supervised OPF
form oversampling via the Optimum-Path Forest, hereinafter proposed by Papa et al. [21], [22] selects as prototypes the
named O2 PF. The method employs the unsupervised OPF nearest samples from different classes, found by computing
algorithm to capture features intrinsic to the minority class into the graph Minimum Spanning Tree (MST). However, in the
different clusters. Further, new training examples are generated unsupervised variant, since labels are usually unavailable,
by sampling from a Gaussian distribution parametrized by Rocha et al. [11] proposed to select the prototypes as the
the cluster characteristics. Therefore, the main contribution samples located in the center of each cluster. To such an extent,
of this paper are twofold: (i) extending the OPF algorithm all samples are assigned a density score ρ(xi ), ∀xi ∈ D,
capabilities by introducing a novel oversampling mechanism computed through a Gaussian probability density function
that enforces synthetic intra-class variability; and (ii) studying (pdf), defined as follows:
how O2 PF can benefit the development of CAD systems
by extensively evaluating it on five tumor-classification and 1 X 
−d(xi , xj )

one retinopathy identification tasks. Finally, the full-balanced ρ(xi ) = √ exp , (1)
k 2πσ 2
? 2σ 2
datasets are employed to train the OPF classifier, and results, ∀xj ∈Ak? (xi )
i.e., the accuracy, recall, and F1-measure, are compared against
where i 6= j, σ = dmax /3 and dmax stands for the maximum
the ones obtained by the standard training dataset without
arc-weight in G. This formulation considers all adjacent nodes
oversampling. Additionally, results are compared against three
for density computations, as the Gaussian distribution covers
baselines: SMOTE [18], the Borderline SMOTE [19], and
99.7% of the samples with distance d(xi , xj ) ∈ [0, 3σ].
ADASYN [20].
After evaluating Equation 1 for each node in the graph, the
In the remainder of this paper, Section II presents the theo-
density values are used to populate a priority queue in a way
retical background regarding the unsupervised and supervised
that the unsupervised OPF maximizes the cost of each sample,
OPF algorithm variants, whereas Section III introduces the
thus partitioning the graph into OPTs. Such a cost is defined in
proposed approach. Further, Section IV outlines the experi-
terms of paths on G, which is an acyclic sequence of adjacent
mental setup and Section V discusses experimental results.
samples in Ak? .
Finally, Section VI presents conclusions and future works.
Let πxi be a path with terminus at sample xi and starting
II. BACKGROUND from some root R(xj ), being the latter the set of all prototype
This section presents the theoretical background regarding samples. Further, let πxi = hxi i be a trivial path (i.e., a path
the unsupervised and supervised variants of the OPF algo- containing only one sample), whereas πxi · hxi , xj i denotes
rithm. the concatenation of a path πxi and the arc (xi , xj ) such that
i 6= j.
A. Unsupervised Optimum-Path Forest In the third step, the algorithm assigns to each path πxi
Let D = {x1 , x2 , . . . , xn } be a dataset such that xi ∈ Rm a value fmin (πxi ) given by a smooth connectivity function
represents the features extracted from the i-th sample. Further, fmin : D → R+ , which must satisfy some constraints to
let G = (D, Ak? ) be a graph where each node corresponds to a ensure the algorithm theoretic correctness [23], [24]. A path
different feature vector connected to its k ? -nearest neighbors, πxi is considered optimal if fmin (πxi ) ≥ fmin (τxi ) for any
as defined in the adjacency relationship set Ak? . other path τxi . Among the proposed path-cost functions in
The unsupervised OPF algorithm consists in partitioning the the literature, the unsupervised OPF relies on the following
graph through a competitive process, in which a few samples formulation:
are marked as “prototypes” and compete among themselves

to conquer the remaining nodes. Such a procedure partitions ρ(xi ) if xi ∈ R
the G into optimum-path trees (OPTs) rooted at a prototype, fmin (hxi i) = (2)
ρ(xi ) − δ otherwise.
each corresponding to a cluster, where a sample is more fmin (πxi · hxi , xj i) = min{fmin (πxi ), ρ(xj )},
similar to the elements of its tree than any other tree. Overall,
the process can be divided into three steps: (i) computing a where δ = min∀(xi ,xj )∈Ak? |ρ(t)6=ρ(s) |ρ(t) − ρ(s)| consists in
proper neighborhood size k ? and the adjacency relationship the smallest quantity to avoid plateaus and over-segmentation
Ak? , (ii) electing the prototype nodes, and (iii) performing in regions near prototypes (i.e., areas with the highest density).
the competition process to partition the dataset into OPTs. Among all possible paths πxi that originate in some local
Regarding the first step, different approaches may be con- maximum, i.e., some prototype, the OPF algorithm assigns to
sidered. Among others, Rocha et al. [11] proposed to find k ? each sample a final path whose minimum density value along
it is maximum. Such final path value is represented by a cost making the classifier biased towards a subset of characteristics
map C, as follows: present in that class. To tackle such issues, the O2 PF first
performs the clustering from minority class samples, which
C(xi ) = max {f (πxj · hxj , xi i)}. (3) turns possible the extraction of common patterns intrinsic to
∀πxj ∈D, i6=j
the class, i.e., the samples’ average position and variance.
The OPF algorithm maximizes C(xi ) ∀xi ∈ D by com- Further, the algorithm assumes that all features from a class
puting an optimum-path forest for each sample in descending follow a normal distribution. Thus, a new sample z ∈ Rm can
order of cost. Each forest is encoded as an acyclic predecessor be generated by sampling such a distribution from some of
map P which assigns to each sample xi ∈ / R its predecessor the q clusters found. Notice the number of synthetic samples
P(xi ) in the optimum path from R, or a marker nil when generated by each cluster is proportional to the number of
xi ∈ R. original samples compounding it, i.e., we are always doubling
It is important to remark that the unsupervised OPF algo- the number of samples from the minority class, although the
rithm determines the number of clusters (OPTs) automatically, user can set that percentage. The distribution is performed as
hence such information is not required beforehand, differently follows:
from other algorithms. Furthermore, the only hyperparameter
that must be set is the search interval upper bound kmax for z ∼ N (µq , Σq ), (6)
the proper neighborhood size k ? ∈ [1, kmax ].
where µq ∈ Rm stands for the distribution mean, defined
B. Supervised Optimum-Path Forest as the average feature vector from all samples within the q-
Differently from its unsupervised version, the supervised th cluster. Moreover, Σq ∈ Rm×m is the covariance matrix,
variant uses a fully-connected graph G 0 = (D, B) instead. computed as follows:
Moreover, the closest samples from different classes are 1
marked as prototypes, as aforementioned. Regarding the com- Σq = (Xq − µq )(Xq − µq )T , (7)
nq − 1
petition process, instead of using Equation 2, the following
smooth function is employed: given that Xq ∈ Rm×nq is a matrix formed by concatenating
all nq cluster feature vectors. Figure 1 illustrates the proposed

0 if xi ∈ R approach behavior.
fmax (hxi i) = (4)
∞ otherwise.
fmax (πxi · hxi , xj i) = max {fmax (πxi ), d(xi , xj )} . Benign
Malignant
O2PF
Further, the following cost map is used to partition the
graph:
2

S(xi ) = min {max {S(xi ), d(xi , xj )}} . (5)

xi ∈D

Such costs are used to initialize the algorithm before eval-

uating Equation 5, which is performed for every node in an
ascending order of costs. After partitioning the graph, each
prototype propagates its ground truth label to all samples in 1
its OPT. Afterwards, prediction is performed by solving the
same equation for new samples individually. Fig. 1: Oversampling using O2 PF. The image comprises
WBCD Diagnostic II dataset samples and synthetic points
III. P ROPOSED A PPROACH from the minority class generated using O2 PF. Data were
Although the unsupervised OPF was conceived for clus- projected onto a 2-dimensional space using the Principal
tering purposes, such clusters possess a set of features that Component Analysis algorithm for visualization purposes.
can also be employed to synthesize new samples, thus being
suitable for oversampling. This section describes the procedure
IV. M ETHODOLOGY
for a binary classification problem, which intends to oversam-
ple the class composed of the smallest number of features. This section describes the datasets used in the experiments.
Notwithstanding, the same approach can be easily applied to Further, the experimental setup is outlined.
multiclass problems by individually repeating the procedure
for each class to be oversampled. A. Datasets
The process of synthetic samples generation contemplates Experiments were conducted over two sets of three
two main steps: (i) creating plausible samples, i.e., synthetic databases each. The first set comprises three datasets for breast
elements with characteristics that are coherent with the se- cancer detection, i.e., the Wisconsin Breast Cancer Database,
lected class; and (ii) introducing sample variability, avoiding which is composed of the datasets Prognostic, Diagnostic I,
and Diagnostic II. The second set is composed of general- are compared through the Wilcoxon signed-rank test [30]
purpose datasets for medical issues. All of them are unbal- with 0.05 significance concerning recall values. Figure 2
anced, binary, and were obtained from the UCI repository [25]. depicts such a pipeline. Implementation-wise, we rely on
A brief description of each one follows below: the supervised and unsupervised implementations provided by
• Wisconsin Breast Cancer Database (WBCD) Prognos- Opfython [31]. Additionally, the source code was implemented
tic1 [26]: Regards predicting a sample as recurrent or using Python and is available on GitHub.6
non-recurrent type of cancer based on 32 features. There
are 198 samples, being 151 (76.3%) non-recurrent and Best
hyperparameters Supervised
47 (23.7%) recurrent; Train set
OPF
Test set

• WBCD Diagnostic I: Consists of classifying a tumor

as benignant or malignant based on 32 features as well. Candidate
Oversampling
Supervised
Validation set
hyperparameters OPF
There are 569 instances, from which 357 (63.7%) are
benign and 212 (37.3%) are malignant;
• WBCD Diagnostic II: Corresponds to labelling each Smallest class recall
of the 699 samples as benign or malignant tumor. Each Fig. 2: Experimental pipeline for each dataset partition.
sample comprises 9 features and each class contains 458
(65.5%) and 241 (34.5%) examples, respectively;
2
• Diabetic Retinopathy Debrecen (DRD) [27]: Regards
V. E XPERIMENTAL R ESULTS
predicting whether an image contains signs of diabetic
retinopathy or not based on 19 variables. The dataset This section is divided into four main steps: (i) datasets
contains 1, 151 samples, from which 611 (53.1%) are augmented using the O2 PF are compared against the standard
positive and 540 (46.9%) are negative; version, (ii) the proposed approach is compared against three
3
• Cervical Cancer (CC) [28]: For this task we predict baselines for oversampling considering three distinct versions
the binary biopsy variable based on 32 features for 858 of the Wisconsin Breast Cancer Database, i.e., Prognostic,
samples. Differently from other datasets, all variables in Diagnostic I, and Diagnostic II, for the task of breast cancer
this scenario are either integer or binary. Further, the detection. In step (iii), a similar experiment is conducted
dataset is significantly skewed, with 55 (6.4%) positive over three general-purpose medical issues datasets, and (iv)
and 803 (93.6%) negative samples; it provides a brief discussion concerning the optimization of
4
• Mammographic Mass (MM) [29]: Concerns predicting the proposed method hyperparameter, i.e., the kmax .
if a mammographic mass is benign or malignant based
on six features. The dataset contains 516 (53.7%) benign A. O2 PF Data Augmentation Versus Standard Datasets
and 445 (46.3%) malignant samples, comprising 961
examples. This section presents the results obtained by the Optimum-
Path Forest classifiers considering the datasets balanced
B. Experimental setup through O2 PF oversampling, i.e., minority classes are aug-
The experiments conducted in this paper considered pre- mented such that both classes present a similar number of
processing the data such that missing features were replaced samples, against the standard version of the datasets. Table I
by their corresponding mean in the training partition. All the presents the recall considering each dataset. Values in bold
features were normalized to have zero mean and unitary stan- denote the best results according to the Wilcoxon signed-rank
dard deviation. Further, the datasets were randomly divided test with 5% of significance.
into training, validation and testing sets, each containing 70%,
15%, and 15% of the data, respectively5 . TABLE I: Evaluation of the proposed O2 PF against the
The validation set was employed to fine-tune the oversam- standard datasets versions.
pling method hyperparameters, i.e., finding the kmax for the
unsupervised OPF and κ for the other methods that maximize Ds. Version Recall Prognostic Diagnostic I Diagnostic II DRD CC MM
Avg. 0.4945 0.9184 0.8903 0.4922 0.6320 0.6180
the minority class recall. Afterward, the augmented dataset ORIGINAL
Std. ±0.1872 ±0.0346 ±0.0550 ±0.2017 ±0.1002 ±0.0480
is used to train the OPF classifier for further computing the Avg. 0.5739 0.9311 0.9104 0.5834 0.6292 0.6086
O2 PF
results over the testing sets. Notice that such a procedure Std. ±0.1368 ±0.0331 ±0.0452 ±0.2308 ±0.0924 ±0.0434

is repeated 20 times for statistical analysis, and the results

1 All considered versions are available at [Link] In this context, one can observe O2 PF obtained the best
datasets/Breast+Cancer+Wisconsin+(Prognostic). results in five out of six datasets according to the Wilcoxon
2 Available at [Link]
Debrecen+Data+Set.
signed-rank test, obtaining the best results alone in three of
3 Available at [Link] them.
%28Risk+Factors%29.
4 Available at [Link] 6 The source code is available online at [Link]
5 Such percentages were obtained empirically. o2pf.
B. Results concerning the Breast Cancer datasets TABLE III: Results considering General Purpose Datasets.
Table II presents the average recall, accuracy, F1-measure Dataset Statistics O2 PF SMOTE Borderline SMOTE ADASYN
and best kmax considering O2 PF or κ considering the other Recall 0.6086 ± 0.0434 0.5831 ± 0.0476 0.5855 ± 0.0498 0.5716 ± 0.0487
Accuracy 0.5934 ± 0.0327 0.5983 ± 0.0353 0.5974 ± 0.0343 0.5957 ± 0.0354
techniques, as well as their standard deviation. The results DRD
F1 0.6092 ± 0.0302 0.5799 ± 0.0465 0.5803 ± 0.0460 0.5734 ± 0.0469
comprise a minority oversampling, thus providing balanced Best k 26.2500 ± 26.9664 6.8500 ± 1.6515 7.5000 ± 1.7748 5.0000 ± 0.0000

datasets. The proposed approach is compared against three Recall 0.5834 ± 0.2308 0.6287 ± 0.1505 0.5791 ± 0.1811 0.6237 ± 0.1560
Accuracy 0.9388 ± 0.0212 0.9403 ± 0.0157 0.9403 ± 0.0165 0.9415 ± 0.0138
baseline techniques, i.e., SMOTE, Borderline SMOTE, and CC
F1 0.5330 ± 0.1548 0.5673 ± 0.0900 0.5414 ± 0.1109 0.5675 ± 0.0905
ADASYN. Best k 13.2500 ± 10.8714 6.5500 ± 1.4654 6.5500 ± 1.7168 6.0000 ± 1.5166

Recall 0.6292 ± 0.0924 0.6757 ± 0.0739 0.6876 ± 0.0608 0.6614 ± 0.0706

TABLE II: Results considering WBCD Breast Cancer datasets. MM
Accuracy 0.6769 ± 0.0531 0.6738 ± 0.0503 0.6852 ± 0.0426 0.6876 ± 0.0396
F1 0.6439 ± 0.0639 0.6591 ± 0.0545 0.6710 ± 0.0479 0.6631 ± 0.0567
Best k 48.0000 ± 34.2199 7.1000 ± 1.4799 7.2500 ± 1.5772 6.1500 ± 1.5898
Dataset Statistics O2 PF SMOTE Borderline SMOTE ADASYN
Recall 0.5739 ± 0.1368 0.5803 ± 0.1253 0.5802 ± 0.1343 0.6311 ± 0.1283
Accuracy 0.6317 ± 0.0654 0.6183 ± 0.0532 0.6317 ± 0.0619 0.6300 ± 0.0547
Prognostic
F1 0.4143 ± 0.1310 0.4112 ± 0.1330 0.4175 ± 0.1266 0.4366 ± 0.1413
Best k 37.2500 ± 27.0867 6.4000 ± 1.5297 6.0500 ± 1.4654 6.1500 ± 1.4586
considering the average values. Regarding Mammographic
Recall 0.9311 ± 0.0331 0.9368 ± 0.0275 0.9347 ± 0.0322 0.9422 ± 0.0336
Accuracy 0.9471 ± 0.0170 0.9500 ± 0.0138 0.9424 ± 0.0178 0.9448 ± 0.0191
Mass datasets, all techniques performed in a very much alike
Diagnostic I
F1 0.9285 ± 0.0257 0.9330 ± 0.0198 0.9231 ± 0.0278 0.9264 ± 0.0285 fashion, obtaining similar results.
Best k 12.7500 ± 12.6960 5.4000 ± 0.8602 5.6500 ± 1.2359 6.0000 ± 1.6432
One can notice that all three datasets present a challenging
Recall 0.9104 ± 0.0452 0.9075 ± 0.0541 0.8947 ± 0.0586 0.9108 ± 0.0520

Diagnostic II
Accuracy 0.9490 ± 0.0176 0.9476 ± 0.0192 0.9419 ± 0.0217 0.9490 ± 0.0191 task since no technique reached a 0.7 recall. Unusual behavior
F1 0.9195 ± 0.0294 0.9170 ± 0.0331 0.9080 ± 0.0353 0.9196 ± 0.0315
is observed over the Cervical Cancer dataset, whose all tech-
Best k 23.5000 ± 29.6268 6.4500 ± 1.4992 5.4000 ± 0.8602 6.8500 ± 1.5580
niques obtained an approximate accuracy of 94%, despite the
recall below 0.63. Such behavior may suggest samples from
Results observed over WBCD Prognostic dataset show all the minority class are distributed among a subcluster from
techniques obtained similar statistical results considering the majority class, therefore providing high accuracy despite the
recall. Regarding the accuracy, one can observe the proposed low recall.
approach obtained the highest average value, together with the
borderline SMOTE. Such a result suggests samples generated D. O2 PF Hyperparameter Selection
by O2 PF fit better the class distribution, being less prone O2 PF requires a proper selection of a single hyperparameter,
to false negatives. A similar behavior is observed over the the kmax , which is employed in the clustering process. Such a
Diagnostic I dataset. Concerning the Diagnostic II dataset, hyperparameter, however, is way less sensitive when compared
the proposed approach obtained the best results, together with to a proper selection of the best k, performed by the other
ADASYN and SMOTE, outperforming Borderline SMOTE. techniques. Figure 3 depicts a grid search considering a proper
Considering the accuracy, O2 PF obtained the highest averages. selection of those hyperparameters for each technique. Notice
Despite the good performance achieved by the oversampling the central line describes the average value over the valida-
approach using O2 PF, the baseline algorithms have shown tion dataset, while the broader area describes the standard
statistical similarity in most of the cases. Sparse clusters with deviation. Notice even though O2 PF considers a very wider
low density may be responsible for introducing new samples interval, i.e., ranging from [5, 100], most of the time, the results
that are distant from the original distribution of the minority outperform the other techniques, which assume a shorter
class, a situation that would be likely to produce outliers in interval between [5, 10].
the new resample dataset. Such behavior may also influence
in a moderate recall, as observed in Tables II. VI. C ONCLUSION
This paper presented an oversampling approach based on
C. General Purpose Medical Datasets Results the unsupervised Optimum-Path Forest Algorithm. The pro-
Table III presents the results obtained over the three general posed O2 PF showed to be capable of handling the class
purpose medical datasets, i.e., Diabetic Retinopathy Debrecen, imbalance problem through a simple and effective procedure
Cervical Cancer and Mammographic Mass. that generates new synthetic samples based on the normal
Considering Diabetic Retinopathy Debrecen, the proposed distribution of the feature vectors inside each cluster. The
approach outperformed the average recall overall techniques, experiments performed in three datasets of breast cancer, apart
although SMOTE and Borderline SMOTE achieved similar from three complementary medical issue datasets, showed that
results. Similar behavior is observed over the F1 metric. On the O2 PF approach demonstrated similar or superior results
the other hand, O2 PF, SMOTE and ADASYN obtained the when compared to the baseline methods already proposed in
best results regarding the Cervical Cancer dataset. Since both the literature.
Borderline SMOTE and ADASYN are variants of SMOTE, Notwithstanding, the effectiveness of the proposed approach
they are expected to perform differently over different sce- may still suffer in synthesizing new samples based on low-
narios. However, as observed in most of the experiments, density clusters, a situation that may introduce noise samples
they generally are outperformed by SMOTE technique itself, in the training set and, consequently, affect creating of the
 5 6 7 8 9 10 5 6 7 8 9 10 [10] P. B. Ribeiro, L. A. Passos, L. A. da Silva, K. A. da Costa, J. P. Papa,
0.70
0.96 and R. A. Romero, “Unsupervised breast masses classification through
0.95 optimum-path forest,” in 2015 IEEE 28th International Symposium on
0.65
0.94
Computer-Based Medical Systems. IEEE, 2015, pp. 238–243.
Accuracy

Accuracy
0.60
0.93
0.55
0.92
[11] L. M. Rocha, F. A. M. Cappabianco, and A. X. Falcão, “Data clustering
0.50 O2PF as an optimum-path forest problem with applications in image analysis,”
SMOTE 0.91
0.45 BorderlineSMOTE 0.90 International Journal of Imaging Systems and Technology, vol. 19, no. 2,
ADASYN
0.40
20 40 60 80 100 20 40 60 80 100
pp. 50–68, 2009.
kmax kmax [12] L. C. S. Afonso, L. A. Passos, and J. P. Papa, “Enhancing brain
storm optimization through optimum-path forest,” in 2018 IEEE 12th
(a) (b) International Symposium on Applied Computational Intelligence and
5 6 7 8 9 10 Informatics (SACI). IEEE, 2018, pp. 000 183–000 188.
0.98 [13] R. R. Guimarães, L. A. Passos, R. Holanda Filho, V. H. C. de Albu-
0.97 querque, J. J. Rodrigues, M. M. Komarov, and J. P. Papa, “Intelligent
Accuracy

0.96 network security monitoring based on optimum-path forest clustering,”

0.95 IEEE Network, vol. 33, no. 2, pp. 126–131, 2018.
0.94
[14] R. W. R. Souza, J. V. C. Oliveira, L. A. Passos, W. Ding, J. P. Papa,
and V. H. Albuquerque, “A novel approach for optimum-path forest
0.93
20 40 60 80 100 classification using fuzzy logic,” IEEE Transactions on Fuzzy Systems,
kmax 2019.
(c) [15] M. Zhu, J. Xia, X. Jin, M. Yan, G. Cai, J. Yan, and G. Ning,
“Class weights random forest algorithm for processing class imbalanced
Fig. 3: Grid searching for a proper selection of the techniques’ medical data,” IEEE Access, vol. 6, pp. 4641–4652, 2018.
[16] T. Razzaghi, I. Safro, J. Ewing, E. Sadrfaridpour, and J. D. Scott,
hyperparameter over the validation for WBCD (a) Prognostic, “Predictive models for bariatric surgery risks with imbalanced medical
(b) Diagnostic I, and (c) Diagnostic II datasets. datasets,” Annals of Operations Research, vol. 280, no. 1-2, pp. 1–18,
2019.
[17] M. Rezaei, H. Yang, and C. Meinel, “Recurrent generative adversarial
network for learning imbalanced medical image semantic segmentation,”
prediction model. Future studies will be conducted to over- Multimedia Tools and Applications, pp. 1–20, 2019.
[18] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “Smote:
come the influence of sparse clusters with low density in the synthetic minority over-sampling technique,” Journal of Artificial Intel-
process of synthesizing new outliers. Moreover, experiments ligence Research, vol. 16, pp. 321–357, 2002.
with a multiclass problem will also be performed in subsequent [19] H. Han, W.-Y. Wang, and B.-H. Mao, “Borderline-smote: a new over-
sampling method in imbalanced data sets learning,” in International
investigations. conference on intelligent computing. Springer, 2005, pp. 878–887.
[20] H. He, Y. Bai, E. A. Garcia, and S. Li, “Adasyn: Adaptive synthetic
sampling approach for imbalanced learning,” in 2008 IEEE interna-
R EFERENCES tional joint conference on neural networks (IEEE world congress on
computational intelligence). IEEE, 2008, pp. 1322–1328.
[1] D. S. Jodas, A. S. Pereira, and J. M. R. Tavares, “A review of [21] J. P. Papa, A. X. Falcão, and C. T. N. Suzuki, “Supervised pattern
computational methods applied for identification and quantification of classification based on optimum-path forest,” International Journal of
atherosclerotic plaques in images,” Expert Systems with Applications, Imaging Systems and Technology, vol. 19, no. 2, pp. 120–131, 2009.
vol. 46, pp. 1–14, 2016. [22] J. P. Papa, A. X. Falcão, V. H. C. De Albuquerque, and J. M. R.
[2] L. C. Ribeiro, L. C. Afonso, and J. P. Papa, “Bag of samplings Tavares, “Efficient supervised optimum-path forest classification for
for computer-assisted parkinson’s disease diagnosis based on recurrent large datasets,” Pattern Recognition, vol. 45, no. 1, pp. 512–520, 2012.
neural networks,” Computers in biology and medicine, vol. 115, p. [23] A. X. Falcão, J. Stolfi, and R. A. Lotufo, “The image foresting transform:
103477, 2019. theory, algorithms, and applications,” IEEE Transactions on Pattern
[3] N. I. Yassin, S. Omran, E. M. E. Houby, and H. Allam, “Machine Analysis and Machine Intelligence, vol. 26, no. 1, pp. 19–29, 2004.
learning techniques for breast cancer computer aided diagnosis using [24] K. C. Ciesielski, A. X. Falcão, and P. A. V. Miranda, “Path-value
different image modalities: A systematic review,” Computer Methods functions for which dijkstra’s algorithm returns optimal mapping,”
and Programs in Biomedicine, vol. 156, pp. 25–45, 2018. Journal of Mathematical Imaging and Vision, vol. 60, no. 7, pp. 1025–
[4] W. H. Organization. Breast cancer. [Online]. Available: https: 1036, Sep 2018.
//[Link]/cancer/prevention/diagnosis-screening/breast-cancer/en/ [25] D. Dua and C. Graff, “UCI machine learning repository,” 2017.
[5] M. Xian, Y. Zhang, H. Cheng, F. Xu, B. Zhang, and J. Ding, “Automatic [Online]. Available: [Link]
breast ultrasound image segmentation: A survey,” Pattern Recognition, [26] O. L. Mangasarian and W. H. Wolberg, “Cancer diagnosis via linear pro-
vol. 79, pp. 340 – 355, 2018. gramming,” University of Wisconsin-Madison Department of Computer
[6] W. Wieclawek, M. Rudzki, A. Wijata, and M. Galinska, “Preliminary Sciences, Tech. Rep., 1990.
development of an automatic breast tumour segmentation algorithm [27] B. Antal and A. Hajdu, “An ensemble-based system for automatic
from ultrasound volumetric images,” in Information Technology in screening of diabetic retinopathy,” Knowledge-based systems, vol. 60,
Biomedicine, E. Pietka, P. Badura, J. Kawa, and W. Wieclawek, Eds. pp. 20–27, 2014.
Cham: Springer International Publishing, 2019, pp. 77–88. [28] K. Fernandes, J. S. Cardoso, and J. Fernandes, “Transfer learning with
[7] L. Liu, K. Li, W. Qin, T. Wen, L. Li, J. Wu, and J. Gu, “Automated breast partial observability applied to cervical cancer screening,” in Iberian
tumor detection and segmentation with a novel computational framework conference on pattern recognition and image analysis. Springer, 2017,
of whole ultrasound images,” Medical & Biological Engineering & pp. 243–250.
Computing, vol. 56, pp. 183–199, 2017. [29] M. Elter, R. Schulz-Wendtland, and T. Wittenberg, “The prediction of
[8] A. F. M. Agarap, “On breast cancer detection: an application of machine breast cancer biopsy outcomes using two cad approaches that both
learning algorithms on the wisconsin diagnostic dataset,” in Proceedings emphasize an intelligible decision process,” Medical physics, vol. 34,
of the 2nd International Conference on Machine Learning and Soft no. 11, pp. 4164–4172, 2007.
Computing, 2018, pp. 5–9. [30] F. Wilcoxon, “Individual comparisons by ranking methods,” Biometrics
[9] L. A. Passos, C. Santos, C. R. Pereira, L. C. S. Afonso, and J. P. Papa, “A Bulletin, vol. 1, no. 6, pp. 80–83, 1945.
hybrid approach for breast mass categorization,” in ECCOMAS Thematic [31] G. H. de Rosa, J. P. Papa, and A. X. Falcão, “Opfython: A python-
Conference on Computational Vision and Medical Image Processing. inspired optimum-path forest classifier,” 2020.
Springer, 2019, pp. 159–168.