PaperlayerView exact revision on arXiv

Source-linked AI summary

Imbalanced Big Data Oversampling: Taxonomy, Algorithms, Software, Guidelines and Future Directions

William C. Sleeman IV, Bartosz Krawczyk

arXiv:2107.11508v1cs.LG

TL;DR

Imbalanced learning is difficult, and existing oversampling algorithms were not designed for distributed big-data environments. The paper presents a taxonomy and 14 Spark adaptations, then reports that local methods performed among the best while global methods such as Cluster SMOTE performed poorly. It also identifies oversampling components suited to distributed processing and notes efficiency limitations in some implementations.

  • Problem

    Oversampling methods are abundant for standard datasets but lack effective implementations for big-data environments such as Spark.

    Source: §1 · p. 2

  • Method

    The paper combines a taxonomy of oversampling methods with Spark adaptations of 14 algorithms and an experimental study on binary and multiclass data.

    Source: §1 · pp. 2–3

  • Results

    Global methods such as Cluster SMOTE performed highly unsatisfactorily, while local methods were consistently among the best-performing methods in the experiments.

    Source: §7.2 · p. 45

  • Takeaways & Limitations

    The study identifies oversampling components that translate well to high-performance distributed processing.

    Source: §8 · p. 46

    Some implementations have efficiency limitations, and the initial library contains 14 oversampling methods, with undersampling, hybrid methods, and ensembles left as possible extensions.

    Source: §5.5 · p. 29

Abstract

from arXiv · show

Learning from imbalanced data is among the most challenging areas in contemporary machine learning. This becomes even more difficult when considered the context of big data that calls for dedicated architectures capable of high-performance processing. Apache Spark is a highly efficient and popular architecture, but it poses specific challenges for algorithms to be implemented for it. While oversampling algorithms are an effective way for handling class imbalance, they have not been designed for distributed environments. In this paper, we propose a holistic look on oversampling algorithms for imbalanced big data. We discuss the taxonomy of oversampling algorithms and their mechanisms used to handle skewed class distributions. We introduce a Spark library with 14 state-of-the-art oversampling algorithms implemented and evaluate their efficacy via extensive experimental study. Using binary and multi-class massive data sets, we analyze the effectiveness of oversampling algorithms and their relationships with different types of classifiers. We evaluate the trade-off between accuracy and time complexity of oversampling algorithms, as well as their scalability when increasing the size of data. This allows us to gain insight into the usefulness of specific components of oversampling algorithms for big data, as well as formulate guidelines and recommendations for designing future resampling approaches for massive imbalanced data. Our library can be downloaded from https://github.com/fsleeman/spark-class-balancing.git.

1. Introduction

Class imbalance biases standard classifiers toward majority classes, and big datasets add distributed-computing demands that existing oversamplers were not designed to meet. The paper addresses this gap with a taxonomy, 14 Spark implementations, experiments, design guidance, and future research directions.

1. Introduction

  • Standard classifiers can favor majority classes, while big-data architectures require distributed implementations that oversampling methods often lack.The introduction also notes added challenges from overlapping distributions, noise, streaming, concept drift, and long-tailed recognition.Source: §1 · pp. 1–2
  • The paper combines a taxonomy, software, experiments, guidelines, and future directions into a holistic treatment of imbalanced big-data oversampling.It identifies the need for distributed-specific solutions and a unified taxonomy, noting that existing MapReduce packages offered no methods more advanced than SMOTE.Source: §1 · p. 2
  • The authors adapt 14 oversampling algorithms to Spark and propose a taxonomy based on instance-generation mechanisms and use of inner- and intra-class information.They also introduce a Scala package with optimized implementations, intended to support reproducibility and provide a baseline for future algorithm development.Source: §1 · p. 3
  • The experimental study covers 26 binary and multiclass imbalanced big-data benchmarks, assessing four performance metrics, classifier relationships, and accuracy–computational-complexity trade-offs.The paper also investigates relationships between oversampling techniques, data types, and base classifiers.Source: §1 · p. 3
  • The authors propose implementation-informed design guidelines for distributed oversampling and outline open challenges and future directions.The guidelines address considerations for novel methods and mechanisms that work favorably within MapReduce.Source: §1 · p. 3

2. Learning from imbalanced data

Imbalance handling includes data-level resampling and algorithm-level changes, but multiclass relationships and big-data scale complicate both. The section reviews these approaches and contrasts GPU and CPU-cluster settings, including their constraints for multiclass problems.

2.1. Binary imbalanced problems

  • Data-level methods rebalance training data through undersampling or oversampling, whereas algorithm-level methods modify learners but require choosing a specific classifier.SMOTE creates synthetic minority observations by interpolation; its homogeneity assumption can misplace samples when distributions are disjoint or contain noise or outliers, motivating variants such as Borderline SMOTE and ADASYN.Source: §2.1 · pp. 3–4

2.2. Multi-class imbalanced problems

  • Multiclass relationships are more complex than majority–minority labels capture, and overlapping classes, noise, or outliers can affect several class boundaries.The section notes that a class can be a majority relative to some classes and a minority relative to others.Source: §2.2 · p. 4
  • Binarization can discard class relationships, and one-vs-one decomposition can become costly as class and observation counts grow; native ad-hoc methods address multiclass problems directly.Binarization uses one-vs-one or one-vs-all subproblems, while ad-hoc methods include multiclass SMOTE extensions, feature selection, and algorithm-level adaptations.Source: §2.2 · pp. 4–5

2.3. Big imbalanced data

  • Big-data imbalance requires scalable computing architectures because conventional oversampling algorithms were designed for smaller datasets.The section contrasts GPU parallelism and control with CPU clusters’ elasticity, reliability, and scalability.Source: §2.3 · p. 5
  • GPU implementations can preserve neighborhood structure for SMOTE but require specialized programming and cannot currently handle terabyte-level datasets.CPU-cluster partitioning can corrupt spatial relationships for SMOTE, while random oversampling and undersampling perform significantly better in the cited study.Source: §2.3 · pp. 5–6
  • The section reports no dedicated large-scale multiclass imbalance algorithms for GPUs or CPU clusters, apart from the authors’ preliminary Spark-based ensembles.Source: §2.3 · p. 6

3. MapReduce architecture with Spark

MapReduce divides distributed processing into map, shuffle, and reduce phases. Spark builds on this model with in-memory intermediate results, DAG optimization, and a cluster architecture that distributes tasks across workers.

3. MapReduce architecture with Spark

  • MapReduce maps data by keys, shuffles grouped intermediate results to the appropriate reducers, and reduces them into a final result.Large tasks chain these three operations.Source: §3 · p. 6
  • Spark keeps intermediate results in main memory, whereas Hadoop saves them to disk between stages and reloads them for the next stage.Spark’s reduced disk access can provide superior runtime performance, though it can be memory intensive.Source: §3 · pp. 6–7
  • Spark uses directed acyclic graphs to optimize operation sequences by removing duplicates, reordering subtasks, and lazily executing work outside the critical path..Source: §3 · p. 7
  • A Spark job’s driver requests resources from a cluster manager, executors run tasks on worker nodes, and the driver prepares final results from returned data.Executors can use one or more CPU threads and share partial results.Source: §3 · p. 7
  • Spark’s Resilient Distributed Datasets partition data for parallel operations, allowing the same code to run across different data sizes and worker counts.DataFrames and Datasets also support map, filter, and reduce operations with a SQL-like interface.Source: §3 · p. 7
  • Spark extensions have explored GPU and FPGA support, including heterogeneous executors; limited GPU support was included in Apache Spark starting with version 3.0.Experiments with local and remote GPUs reported significant speed improvements.Source: §3 · pp. 7–8

4. Oversampling algorithms for imbalanced big data

This section surveys oversampling algorithms for imbalanced big data, classifying how they use data information and relationships to generate or select minority-class examples. It describes approaches adapted for big-data processing, including distribution-aware sampling, difficult-example weighting, noise filtering, and local interpolation to address challenges such as local difficulty, boundary uncertainty, noise, and multimodal minority classes.

4.1. Taxonomy of oversampling algorithms for big data

  • Guided oversampling uses local or global class information to preserve minority structure, adapt sampling to neighborhoods or modalities, and account for class-specific properties.Methods may combine global modality detection with local instance-difficulty analysis, or use clustering, density, noise, and outlier information to guide generation.Source: §4.1 · pp. 8–9
  • Oversampling methods also differ in whether they consider only minority-class structure or other classes, and whether sampling ratios are fixed or adapt to modalities, classes, or changing data.Considering other classes can limit increased overlap; in extreme imbalance, combining oversampling with majority-class undersampling may work better than oversampling alone.Source: §4.1 · p. 10

4.2. Details of oversampling algorithms

  • The algorithms were adapted for MapReduce, and multi-class support uses one-vs-all oversampling; ADASYN allocates synthetic examples by local imbalance, while ANS filters noisy minority seeds.ADASYN replicates an example with no minority neighbors and otherwise interpolates toward a minority neighbor; ANS weights generation using majority-neighbor counts among retained examples.Source: §4.2 · pp. 10, 12
  • Borderline SMOTE generates examples from minority instances with many majority neighbors, while CCR relocates majority examples to clear safe regions for targeted oversampling.Borderline SMOTE selects instances with between m/2 and m-1 majority neighbors among m neighbors; CCR expands radii under an energy budget and generates more examples in smaller-radius regions.Source: §4.2 · pp. 13–14
  • Cluster SMOTE clusters the minority class, then generates examples between a selected instance and a neighbor within its cluster to avoid interpolating across modalities.It applies k-means to form clusters and performs nearest-neighbor search separately within each cluster.Source: §4.2 · p. 16
  • Gaussian SMOTE samples between minority examples with a Gaussian to spread synthetic points; k-Means SMOTE weights qualifying clusters by minority density before applying SMOTE.k-Means SMOTE retains clusters with more minority than majority examples and allocates sampling in proportion to their minority-density weights.Source: §4.2 · p. 16
  • MWMOTE identifies difficult minority examples via 1-NN, weights their importance, and generates synthetic points to form more uniform minority regions.It retains minority examples with at least one minority neighbor in its first phase.Source: §4.2 · p. 19
  • NRAS removes minority examples with low linear-regression membership probabilities before SMOTE-style oversampling, targeting noisy data but potentially detecting noise even when none is present.Source: §4.2 · p. 20
  • Random oversampling duplicates minority examples to balance classes, while RBO translates selected examples using a phi criterion and adapts local sampling to difficult regions without nearest-neighbor search.Source: §4.2 · pp. 20–21
  • Safe Level SMOTE scales interpolation using local minority-neighbor ratios; SMOTE interpolates minority neighbors, whereas SMOTE-D allocates samples deterministically by neighbor spread.Avoiding difficult instances may reduce test performance when they are core minority concepts.Source: §4.2 · p. 23

5. Software package

The Scala library implements 14 oversampling algorithms for Spark, with multi-class support for methods originally designed for binary classification. The section describes its dependencies and use, while noting implementation limitations and possible extensions.

5. Software package

  • The Scala library implements 14 oversampling algorithms, adding multi-class support by processing each minority class separately and using one-vs-rest for methods that account for the majority class.The methods follow Spark MLlib's fit/transform pattern.Source: §5 · p. 28

5.5. Limitations and Future Extensions

  • Spark implementations stayed close to the original serial algorithms without major performance or accuracy improvements; kNN tree generation can fail with unbalanced child nodes, avoidable by forcing metric trees.For small datasets or classes with few examples, the library falls back to brute-force kNN.Source: §5 · p. 28, §5.5 · p. 29

5.1. Dependencies

  • The library was developed with Spark 3.0.1 and Scala 2.12.1 and depends on Spark core, SQL, and MLlib, Breeze, and a Spark 3-compatible spark-knn fork.Source: §5.1 · p. 28

5.2. spark-knn

  • The implementation uses spark-knn for nearest-neighbor search; its fork adds distance-radius search required by ANS and CCR.Source: §5.2 · p. 28

5.3. Using the spark-class-balancing library

  • The library is built as a jar with sbt, and the resulting jar can run Spark jobs locally or in cluster mode.The spark-knn fork must also be built as a jar and included as a dependency.Source: §5.3 · p. 28

5.4. Invoking sampling methods

  • For SMOTE, users fit an estimator, set parameters such as k=5, and transform the training DataFrame to produce oversampled data.Source: §5.4 · p. 29

5.5. Limitations and Future Extensions

  • Some implementations have efficiency limitations; the algorithms can be updated using the paper's design guidelines, and the library can add undersampling, hybrid methods, and ensembles.Source: §5.5 · p. 29
  • The library's future development includes tighter integration with its custom spark-knn fork and updates for newer Spark versions.Source: §5.5 · p. 29

6. Experimental study

The experiments compare oversampling performance, computational cost, accuracy–time trade-offs, and scalability across binary and multi-class data, feature types, and classifiers. The study uses 26 datasets, three classifiers, and five-fold cross-validation, but excludes three slow methods from the full experiments.

6.1. Setup

  • The study selected 26 datasets, each reduced to 100,000 examples, and used stratified 5-fold cross-validation; ANS, MWMOTE, and RBO were excluded from full experiments because runtime was excessive.Section 7 discusses properties of those algorithms that limit scalability.Source: §6.1 · pp. 30–31

6.2. Experiment 1: Oversampling algorithms for binary big imbalanced data

  • Across binary datasets, local-information methods often performed best, while random oversampling could outperform clustering- and Gaussian-based SMOTE variants.The authors attribute this pattern to Spark partitioning affecting spatial relationships among instances.Source: §6.2 · pp. 34–36
  • Borderline SMOTE, Safe-level SMOTE, ADASYN, and CCR were the strongest informed binary methods, with relative performance depending on overlap, imbalance, rare instances, and outliers.Borderline SMOTE suited overlap near decision boundaries; Safe-level SMOTE reinforced homogeneous minority regions, while ADASYN and CCR addressed rare instances and outliers.Source: §6.2 · p. 35

6.3. Experiment 2: Oversampling algorithms for multi-class big imbalanced data

  • In multi-class experiments, informed methods outperformed other solutions; Borderline SMOTE, ADASYN, and CCR remained strongest, while Cluster SMOTE improved over its binary performance.The authors associate Cluster SMOTE’s improvement with more pronounced class modalities and pairwise oversampling areas under one-vs-all adaptation.Source: §6.3 · p. 36
  • Random Forest and SVM behaved differently from Naive Bayes in multi-class settings, which the authors relate to their ensemble properties under one-vs-all training.The authors describe Random Forest as an explicit ensemble and SVM as an implicit ensemble in this setting.Source: §6.3 · p. 37

6.4. Experiment 3: Investigating oversampling trade-off between accuracy and time complexity

  • No oversampling method was the overall accuracy–time winner; the best trade-off depended on dataset properties and classifier, with Random Oversampling favoring Random Forest on two-class data.Random Oversampling often performed poorly with SVM and Naive Bayes; Borderline SMOTE, Cluster SMOTE, Gaussian SMOTE, and NRAS had strong trade-offs in some combinations.Source: §6.4 · p. 37

6.5. Experiment 4: Scalability of oversampling algorithms

  • At 100,000 examples, ANS, MWMOTE, and RBO sampling times were approximately 15x, 40x, and 400x standard SMOTE, respectively.These projected times made ANS and MWMOTE impractical for the study’s 130 experiments per method.Source: §6.5 · p. 38, Table 8 · p. 43

7. Guidelines for designing oversampling algorithms for imbalanced big data

The guidelines favor low-complexity analysis of local instance properties, while warning that some common algorithmic components limit distributed scalability. They also recommend exploring hybrid oversampling and undersampling, and reducing the burden of hyperparameter tuning.

7.1. Insight into commonly used algorithmic components

  • Distributed k-NN is practical for large datasets, but multiple models add runtime; k-Means can run efficiently, though tuning clusters and iterations may be costly.The k-NN implementation uses a hybrid spill tree; k-Means is provided by Spark MLlib.Source: §7.1 · p. 44
  • Dependent loops force serial execution, leave processors idle, and can create unpredictable bottlenecks, so the authors recommend avoiding them.Source: §7.1 · p. 44
  • Probability-based sampling requires collecting results to the driver for scoring, sorting, and selection, introducing a serial step in MapReduce.Source: §7.1 · p. 44
  • Table 9 lists each method’s high-level components in approximate fastest-to-slowest runtime order.Source: §7.1 · p. 44, Table 9 · p. 45
  • Radius searches can burden runtime and memory, while O(n^2) components lack scalability for big data; linear regression also adds execution time.A hard neighbor limit can mitigate radius-search costs; the authors advise avoiding O(n^2) or worse components.Source: §7.1 · pp. 44–45

7.2. Design choices and future directions for big data oversampling algorithms.

  • Local methods performed among the best, while global methods were highly unsatisfactory; the authors recommend low-complexity local analysis for scalable oversampling.More detailed instance-level analysis may improve generation but can be computationally expensive.Source: §7.2 · pp. 45–46
  • Undersampling alone may underperform, but local undersampling or data cleaning could enhance oversampling, including for uncertainty regions.The authors report that oversampling generally outperformed undersampling on Spark, particularly noting instance loss in multiclass problems.Source: §7.2 · p. 46
  • Massive-data oversampling should use as few hyperparameters as possible, ideally none, or include self-tuning to avoid costly user-guided tuning.Tuning can consume significant resources on Spark, and many parameters add a deployment bottleneck.Source: §7.2 · p. 46

8. Conclusion

The paper adapts 14 oversampling algorithms to Spark and identifies components that affect predictive performance and runtime. It also offers design guidelines and a library to support future work and reproducibility.

8. Conclusion

  • Fourteen popular oversampling algorithms were adapted to Spark, although some methods remain too complex to scale with dataset size.Source: §8 · p. 46
  • The study identifies oversampling components that affect classification performance and time complexity and translate to distributed architectures.Source: §8 · pp. 46–47
  • The authors provide design guidelines and a Spark library of the discussed methods to support future research and reproducibility.Source: §8 · p. 47
Loading 2107.11508v1…