💻 computer science

Addressing Imbalance in Multi-Label Data via Label-Specific Distance-based Oversampling

This paper proposes Label-Specific Distance-based Multi-Label Oversampling (LSDMLO), a novel method that generates synthetic instances by utilizing label-specific weighted distances to identify label-consistent neighbors, thereby overcoming the limitations of existing Euclidean distance-based approaches in handling multi-label data imbalance and improving classifier performance.

Original authors: Bin Liu, Jun Wu, Haoyu Peng, Ao Zhou, Jin Wang, QiaoSong Chen, Grigorios Tsoumakas

Published 2026-06-05

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Bin Liu, Jun Wu, Haoyu Peng, Ao Zhou, Jin Wang, QiaoSong Chen, Grigorios Tsoumakas

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Unbalanced Party"

Imagine you are hosting a party where guests can belong to multiple groups at once (e.g., a guest can be a "Dog Lover," a "Music Fan," and a "Hiker" all at the same time). This is Multi-Label Classification.

However, your guest list is unbalanced.

The Majority: Most people are just "Regulars" (they have no special tags).
The Minority: Very few people are "Rare Hikers" or "Obscure Jazz Fans."

If you try to teach a new bouncer (the AI classifier) to recognize these rare guests, they will fail. Why? Because the bouncer sees thousands of "Regulars" and only a handful of "Rare Hikers." The bouncer gets lazy and just assumes everyone is a Regular. They never learn what a "Rare Hiker" actually looks like.

The Old Solution: The "Blindfolded Matchmaker"

To fix this, data scientists usually try to create synthetic guests (fake data) to fill in the gaps. They use a method called Oversampling.

The old way of doing this is like a blindfolded matchmaker.

The matchmaker looks at a "Rare Hiker" and asks, "Who is standing closest to them?"
They use a simple ruler (Euclidean distance) to measure physical proximity in the room.
The Flaw: The ruler doesn't care about interests. It might pair a "Rare Hiker" with a "Regular" who happens to be standing next to them, even though they have nothing in common.
The Result: The new synthetic guest created by this matchmaker is a confused mess—part hiker, part regular. This confuses the bouncer even more, leading to mistakes and "overfitting" (memorizing the wrong patterns).

The New Solution: LSDMLO (The "Specialized Guide")

The authors propose a new method called LSDMLO. Instead of a blindfolded matchmaker, they use a Specialized Guide who knows exactly what makes a "Rare Hiker" tick.

Here is how it works in three steps:

1. The "Specialized Ruler" (Label-Specific Distance)

The old ruler measured distance using all features (height, weight, shoe size, favorite color).
The Specialized Guide knows that for a "Hiker," shoe size and backpack weight matter, but "favorite color" doesn't. For a "Jazz Fan," the genre of music they listen to matters, but their shoe size doesn't.

How it works: The method calculates a unique "distance" for each label. It ignores irrelevant features and focuses only on the features that actually define that specific group.
The Analogy: If you are looking for a "Hiker," the guide ignores the "Jazz Fan" standing nearby because they don't share the right features, even if they are physically close. It finds the true neighbors who actually share the hiking spirit.

2. Picking the Best "Seed" Guests (Instance Weighting)

Not all "Rare Hikers" are equally important to copy.

The Safe Zone: Some hikers are deep in the middle of a group of other hikers. They are easy to recognize.
The Edge Zone: Some hikers are standing right on the border between "Hikers" and "Regulars." These are the tricky ones the bouncer struggles with the most.
The Strategy: LSDMLO specifically targets these Edge Zone guests. It also looks for guests who belong to multiple rare groups (e.g., a "Hiker" who is also a "Jazz Fan"). These guests carry the most valuable information about how these groups overlap.

3. Creating the "Perfect Copy" (Synthetic Generation)

Once the guide picks a "Seed" guest (an edge case) and a "Reference" guest (a similar neighbor), they create a new synthetic guest.

The Magic: When deciding what tags the new guest gets, the guide doesn't just vote. They use the Specialized Ruler again.
If the Seed is a Hiker and the Reference is a Regular, the guide checks: "Is the new guest physically closer to the Hiker when we only look at hiking features?"
If yes, the new guest gets the "Hiker" tag. This ensures the new fake guest is consistent and doesn't get confused tags.

The Results: A Better Bouncer

The authors tested this method on 13 different datasets (like music, images, and text) and compared it against 9 other top methods.

The Outcome: The "Specialized Guide" (LSDMLO) consistently helped the bouncer (the AI) perform better than any other method.
Why it won: It didn't just add more data; it added smart data. By focusing on the specific features that matter for each label, it avoided creating confused, inconsistent synthetic guests.
The Verdict: Whether the bouncer was a simple rule-follower or a complex deep-learning expert, the LSDMLO method made them all smarter at spotting the rare guests.

Summary

In short, the paper argues that when you have rare categories in your data, you can't just measure "closeness" with a generic ruler. You need a customized ruler for each category. By doing this, you can create high-quality fake examples that teach the AI exactly what those rare categories look like, without confusing the system.

Technical Summary: Addressing Imbalance in Multi-Label Data via Label-Specific Distance-based Oversampling

Problem Statement
Multi-label classification (MLC) faces a critical challenge due to the inherent imbalance in label distributions. This imbalance manifests in two ways: within-label imbalance (where relevant instances for a specific label are far fewer than irrelevant ones) and between-label imbalance (where label frequencies vary widely). Furthermore, local imbalance exists within the neighborhoods of data points, complicating the learning process. Most existing multi-label classifiers are biased toward majority classes and high-frequency labels. While oversampling is a flexible solution to balance training datasets, current methods rely heavily on Euclidean distance within the entire feature space to identify neighbors. This approach fails to account for the varying semantic relevance of features to different labels. Consequently, synthetic instances generated by these methods often suffer from label inconsistency among proximate neighbors, leading to label confusion, overfitting, and reduced diversity, particularly for rare label combinations.

Methodology: LSDMLO
The paper proposes Label-Specific Distance-based Multi-Label Oversampling (LSDMLO), a novel framework designed to generate more useful and well-labeled synthetic instances. The methodology proceeds in three main stages:

Learning Label-Specific Feature Weights:
Instead of using a global feature space, LSDMLO learns sparse feature weights for each label. This is achieved by optimizing a convex objective function that combines:
- Squared loss minimization between predictions and truth labels.
- $\ell_1$ norm regularization to enforce sparsity, ensuring only pertinent features contribute to each label's prediction.
- Graph regularization based on label correlations (derived from cosine similarity of label vectors) to mine complex relationships between features and labels.
  The optimization is solved using the Accelerated Proximal Gradient (APG) algorithm. The resulting weights are normalized to form a label-specific feature weight matrix ( $\Theta$ ).
Label-Specific Distance and Instance Weighting:
Using $\Theta$ , the method defines a label-specific distance metric. This distance measures the proximity between instances based only on the features most relevant to a specific label, rather than the entire feature set.
Based on this distance, LSDMLO calculates an instance weight for seed selection. The weight is a sum of two components:
- Local Imbalance Weight: Measures how close an instance is to a label boundary by assessing local label disagreement among its $k$ -nearest neighbors (retrieved via label-specific distance). Instances near boundaries of highly imbalanced labels receive higher weights.
- Label Correlation Weight: Evaluates the correlation information an instance carries by considering both global label dependencies and local neighborhood consistency. Instances located in overlapping boundary regions of correlated minority labels are prioritized.
Synthetic Instance Generation:
Synthetic instances are generated using a roulette wheel selection based on the calculated instance weights. For each new instance:
- A seed instance is selected.
- A minority label relevant to the seed is chosen.
- A reference neighbor is selected based on the label-specific distance for that specific label.
- Feature Generation: Numerical features are interpolated linearly; nominal features take the most common value among the seed and its neighbors.
- Label Assignment: A label-specific distance-induced strategy is employed. If the seed and reference agree on a label, that label is assigned. If they disagree, the label of the instance (seed or reference) that is closer to the synthetic instance in the label-specific feature subspace is assigned. This ensures label consistency in the pertinent feature space.

Key Contributions

Label-Specific Distance: The introduction of a distance metric that dynamically weights features based on their relevance to specific labels, overcoming the limitations of global Euclidean distance in multi-label contexts.
Semantic-Aware Seed Selection: A weighting mechanism that prioritizes instances near label boundaries and those carrying rich label correlation information, rather than relying on random or purely geometric proximity.
Consistent Label Assignment: A generation strategy that guarantees synthetic instances maintain label consistency within the discriminative feature subspace, reducing the risk of label confusion and overfitting.

Experimental Results
The authors evaluated LSDMLO on 13 multi-label datasets across various domains (text, image, music, biology) using four base classifiers (BR, MLkNN, RAkEL, CC), an imbalance-aware classifier (COCOA), and a deep learning model (C2AE).

Performance: LSDMLO achieved the best average ranks across all four evaluation metrics (Macro-F, Macro-AUC, Macro-AUPR, and Ranking Loss) compared to nine state-of-the-art sampling methods (including MLSMOTE, MLSOL, MLBOTE, AEMLO, and DR-SMOTE).
Statistical Significance: Wilcoxon signed-rank tests confirmed that LSDMLO significantly outperformed competitors in the majority of cases without suffering significant losses.
Local Imbalance Reduction: The study demonstrated that using label-specific distances significantly reduces the Local Label Imbalance (LImb) metric compared to Euclidean distance, particularly in datasets with complex local label distributions.
Base Classifier Synergy: The method showed superior effectiveness when paired with high-performing base learners like C2AE and COCOA.

Significance and Claims
The paper claims that the primary significance of LSDMLO lies in its ability to address the "label inconsistency" problem inherent in existing oversampling methods. By acknowledging that different labels rely on different subsets of features, LSDMLO generates synthetic data that is more realistic and informative. The authors assert that this approach effectively mitigates the bias toward majority classes and improves the learning of minority labels, especially in complex scenarios where local label distributions are difficult to learn. The method is presented as a flexible, classifier-agnostic solution that enhances the performance of diverse multi-label learning algorithms.

Future Work
The authors note that future research will focus on developing a more comprehensive label-specific distance learning framework. This includes incorporating global feature importance and instance correlations, as well as exploring nonlinear modeling to capture complex feature-label interactions beyond the current sparse linear formulation. Additionally, they plan to investigate advanced label dependency modeling strategies to capture higher-order relationships beyond pairwise correlations.