Iterative Nearest Neighborhood Oversampling in Semisupervised Learning from Imbalanced Data

Fengqi Li, Chuang Yu, Nanhai Yang, Feng Xia, Guangming Li, Fatemeh Kaveh-Yazdy

Abstract

Graph-based semi-supervised learning (GSSL) is a powerful paradigm for leveraging large amounts of unlabeled data. However, its performance is severely compromised when the initial labeled set is imbalanced, as label propagation tends to favor majority classes, skewing decision boundaries. This paper discusses the Iterative Nearest Neighborhood Oversampling (INNO) algorithm, which addresses this "majority rules" bias. INNO intelligently expands the minority labeled set by recruiting high-confidence unlabeled samples while employing a boundary-aware safety check. Evaluations on the IRIS, MNIST, and synthetic datasets show that INNO-enhanced GSSL maintains high accuracy even under extreme imbalance, outperforming existing state-of-the-art methods.

Introduction

In many real-world applications, such as fraud detection or rare disease identification, the data available for training is often highly imbalanced. While semi-supervised learning (SSL) aims to mitigate the scarcity of labeled data by utilizing unlabeled samples, standard graph-based SSL (GSSL) methods like Gaussian Fields and Harmonic Functions (GFHF) and Learning with Local and Global Consistency (LGC) are sensitive to class distribution. When labels are imbalanced, the propagation process naturally favors the majority class, pushing the decision boundary into the minority class's territory and leading to poor classification performance for the "underdog" class.

Existing oversampling techniques like SMOTE are designed for supervised learning and often rely on synthetic data generation. In contrast, SSL environments offer a wealth of real, unlabeled data. The INNO algorithm leverages this resource to balance the labeled set before the final classification phase.

The INNO Algorithm

The core of the Iterative Nearest Neighborhood Oversampling (INNO) approach is to iteratively "recruit" the most representative unlabeled samples into the minority class. Unlike simple oversampling, INNO incorporates a critical "Safety Check" to maintain the integrity of class boundaries.

The algorithm follows an iterative process:

  1. Minority Identification: The class with the fewest labeled samples is targeted for expansion.
  2. Neighborhood Search: For each labeled sample in the minority class, the algorithm identifies its $k$-nearest neighbors within the unlabeled pool.
  3. Boundary Safety Check: To prevent mislabeling near decision boundaries, any unlabeled sample that possesses an edge connecting it to a different class is excluded from recruitment.
  4. Recruitment: The unlabeled sample with the highest similarity to the existing minority labels is assigned the minority label and moved to the labeled set.
  5. Iteration: This process repeats until the dataset reaches a balanced state or a predefined stopping criterion is met.

By ensuring that only "safe" samples—those clearly within the minority manifold—are labeled, INNO provides a robust foundation for subsequent GSSL algorithms.

Experimental Evaluation

The effectiveness of INNO was tested across several benchmarks, including the IRIS dataset, the MNIST handwritten digit collection, and synthetic "two-moon" data.

Visualizing the Boundary Shift

The two-moon toy dataset provides a clear visualization of the problem and the INNO solution. In imbalanced scenarios, standard GSSL methods fail to identify the structural gap between the two classes, as the majority class labels dominate the propagation.

Visual comparison of classification results on the two-moon dataset.

As shown in the visualization, while standard GFHF, LGC, and even the more advanced GTAM struggle with boundary skew, the combination of INNO with these algorithms correctly identifies the underlying data structure by first balancing the labeled distribution.

Quantitative Results

On the IRIS dataset, the impact of INNO is even more pronounced as the imbalance ratio increases. Standard methods see a sharp decline in accuracy as the ratio of majority to minority labels grows.

Classification accuracy on the IRIS dataset across varying imbalance ratios.

While GFHF and LGC accuracy drops toward 70% at a 9:1 imbalance ratio, the INNO-enhanced versions maintain a stable accuracy of approximately 95%. Similar trends were observed in the MNIST 10-class experiments, where INNO+LGC consistently outperformed the state-of-the-art GTAM algorithm.

Discussion and Conclusion

The INNO algorithm represents a significant step forward in making graph-based SSL practical for real-world, imbalanced datasets. Its primary strength lies in its "boundary awareness"—by refusing to label samples near class intersections, it avoids the propagation of errors that typically plagues oversampling methods. Furthermore, by utilizing real unlabeled data rather than synthetic points, it preserves the natural manifold structure of the dataset.

Overall, INNO provides a computationally efficient and highly effective "safety net" for semi-supervised classification, ensuring that the structure of the data, rather than the distribution of labels, drives the learning process.

Summary updated

Abstract

Transductive graph-based semisupervised learning methods usually build an undirected graph utilizing both labeled and unlabeled samples as vertices. Those methods propagate label information of labeled samples to neighbors through their edges in order to get the predicted labels of unlabeled samples. Most popular semi-supervised learning approaches are sensitive to initial label distribution which happened in imbalanced labeled datasets. The class boundary will be severely skewed by the majority classes in an imbalanced classification. In this paper, we proposed a simple and effective approach to alleviate the unfavorable influence of imbalance problem by iteratively selecting a few unlabeled samples and adding them into the minority classes to form a balanced labeled dataset for the learning methods afterwards. The experiments on UCI datasets and MNIST handwritten digits dataset showed that the proposed approach outperforms other existing state-of-art methods.
BibTeX
@article{li2013iterative,
  author = {Fengqi Li and Chuang Yu and Nanhai Yang and Feng Xia and Guangming Li and Fatemeh Kaveh-Yazdy},
  title = {{Iterative Nearest Neighborhood Oversampling in Semisupervised Learning from Imbalanced Data}},
  journal = {The Scientific World JOURNAL},
  year = {2013},
  doi = {10.1155/2013/875450},
}
Figure