Manifold Distance-Based Over-Sampling Technique for Class Imbalance Learning

Lingkai Yang, Yi-Nan Guo, Jian ChengAAAI 2019 · DOI

Abstract

Class imbalance is a pervasive issue in machine learning where the minority class is often overlooked by standard optimization algorithms. Traditional over-sampling methods, such as SMOTE, rely on Euclidean distance to generate synthetic samples, which can introduce noise in datasets with complex topological structures or overlapping classes. This paper presents the Manifold Distance-Based Over-Sampling Technique (MDOTE), a novel approach that utilizes manifold learning to generate synthetic data points that respect the underlying geometric structure of the dataset. Experimental results on 23 benchmark datasets demonstrate that MDOTE significantly improves classification performance, particularly in terms of Area Under the ROC Curve (AUC), compared to state-of-the-art over-sampling methods.

Introduction

In many real-world applications, such as fraud detection or medical diagnosis, data is inherently imbalanced. Standard machine learning algorithms, optimized for overall accuracy, tend to ignore the minority class. To address this, over-sampling techniques are employed to balance the class distribution. However, the widely used SMOTE algorithm and its variants often struggle with "disjunct" clusters or overlapping regions because they utilize "as-the-crow-flies" Euclidean distance. This can lead to the generation of synthetic minority samples within majority-class territory, creating noise and reducing classifier performance.

Methodology

MDOTE addresses these limitations by shifting from flat geometric distance to manifold distance. The framework consists of four primary stages:

  1. Strategic Under-sampling: Redundant majority samples—those entirely surrounded by other majority samples—are removed to create a cleaner decision boundary.
  2. Manifold Mapping: The algorithm uses Locally Linear Embedding (LLE) to project high-dimensional data into a lower-dimensional manifold space that preserves local relationships.
  3. Neighbor Extraction: Neighbors for over-sampling are identified within the manifold space, ensuring they belong to the same structural cluster.
  4. Synthetic Generation: New samples are generated in the original feature space along the vectors connecting these manifold-verified neighbors.

By prioritizing topology over simple geometry, MDOTE avoids creating "bridges" of synthetic data across majority-class regions, a common failure mode for traditional methods.

Experimental Setup

The proposed method was evaluated using 23 diverse datasets from the UCI Machine Learning Repository, representing various domains including biology, physics, and engineering. These datasets were selected for their varying degrees of class imbalance and structural complexity.

Table 1: List of the 23 datasets used in the experimental evaluation.

Results

MDOTE's performance was compared against four established baselines: SMOTE (SMO), ADASYN (ADA), MWMOTE (MWM), and ACOSampling (ACO). The primary evaluation metric was the Area Under the ROC Curve (AUC).

Table 2: AUC performance comparison of MDOTE against baseline methods across 23 datasets.

As detailed in Table 2, MDOTE achieved the highest AUC scores on the majority of the tested datasets. Statistical significance was verified using the Wilcoxon paired signed-rank test. The R+ values (representing MDOTE wins) were consistently higher than the R- values across all baseline comparisons. For instance, MDOTE showed a clear advantage in complex datasets like "Abalone" and various "Yeast" configurations, where maintaining the structural integrity of the minority class is critical.

Discussion and Conclusion

The success of MDOTE lies in its ability to separate overlapping classes by extracting the underlying manifold structure. While the method demonstrates superior performance, it introduces additional complexity, particularly regarding hyperparameter sensitivity. Parameters such as the number of neighbors and the manifold dimensionality currently require grid search optimization. Future work will focus on automating these selections and enhancing the robustness of the manifold extraction process. Despite these challenges, MDOTE provides a significant advancement in handling class imbalance for structurally complex datasets.

Summary updated

BibTeX
@inproceedings{yang2019manifold,
  author = {Lingkai Yang and Yi-Nan Guo and Jian Cheng},
  title = {{Manifold Distance-Based Over-Sampling Technique for Class Imbalance Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.330110071},
}
Figure