Empirical Comparison of Multi-Label Classification Algorithms

Clifford A. Tawiah, Victor S. ShengAAAI 2013 · DOI

Abstract

Multi-label classification (MLC) presents a significant challenge in machine learning due to exponential label combinations and inherent label correlations. This study provides a comprehensive benchmark of six prominent MLC algorithms—categorized into algorithm adaptation and problem transformation approaches—across eight diverse datasets. Empirical results demonstrate that the Multi-label K-Nearest Neighbor (MLKNN) algorithm consistently outperforms other methods, achieving superior accuracy and ranking metrics.

Introduction

In traditional classification, an instance is assigned to exactly one category. However, real-world data often requires multiple labels; for example, a news article may simultaneously belong to "Politics," "Economics," and "Europe." This is the core of Multi-Label Classification (MLC). The primary challenges in MLC involve managing the exponential growth of label combinations and effectively modeling label correlations, such as the high probability that a "Biology" document is also related to "Genetics." This paper evaluates different algorithmic strategies to determine which approaches best handle these complexities across various domains.

Methodology

The researchers evaluated six algorithms, divided into two primary categories:

Algorithm Adaptation

These methods modify existing single-label algorithms to handle multi-label data natively:

  • MLKNN (Multi-label K-Nearest Neighbor): A lazy learning approach utilizing K-nearest neighbors and Bayesian inference.
  • Adaboost.MH: An extension of the boosting algorithm specifically for multi-label text categorization.

Problem Transformation

These methods convert the multi-label problem into one or more single-label tasks:

  • Binary Relevance (BR): Trains an independent classifier for each label, ignoring correlations.
  • Classifier Chain (CC): Trains classifiers in a sequence, using previous predictions as features for subsequent ones.
  • Random k-Label Set (RAkEL): Breaks labels into small random subsets and trains multi-class classifiers on each.
  • Pruned Problem Transformation (PPT): Treats unique label combinations as single classes, pruning infrequent ones.

For transformation methods, J48 (a C4.5 decision tree implementation) served as the base learner. The study utilized eight benchmark datasets from the MULAN library, covering text (Enron, Medical, Bibtex), multimedia (Emotions, Scene, Mediamill), and biology (Genbase, Yeast).

Results and Analysis

The algorithms were evaluated across five key metrics: Hamming Loss (HL), Average Precision (AP), One-Error (OE), Coverage (CV), and Ranking Loss (RL).

Average rankings of the six multi-label classification algorithms across five performance metrics.

As shown in the ranking table above, MLKNN emerged as the clear champion with an average rank of 1.8, consistently outperforming both transformation and other adaptation methods. RAkEL followed as the runner-up with an average rank of 2.375, validating the effectiveness of ensemble-based label grouping.

Detailed performance metrics for the evaluated algorithms across different datasets.

The raw performance data further highlights MLKNN's dominance, particularly in metrics like Hamming Loss and Average Precision. Conversely, Adaboost.MH (rank 5.025) and Pruned Problem Transformation (rank 4.25) struggled significantly, suggesting that their specific approaches to label handling may be sensitive to noise or data sparsity.

Discussion

The success of MLKNN suggests that local similarity—identifying "neighbors" with similar label sets—is a highly effective heuristic for MLC, often more robust than global correlation modeling. While Binary Relevance (BR) performed adequately, its inferiority to methods like RAkEL and CC confirms that ignoring label dependencies is a flawed assumption in real-world contexts. Interestingly, the poor performance of Adaboost.MH indicates that not all adaptation strategies are equally effective across diverse datasets.

Conclusion

This empirical study establishes a clear performance hierarchy among popular MLC algorithms. MLKNN stands out as a robust and high-performing choice for multi-label tasks. Future research should focus on developing more sophisticated methods to exploit label dependencies and improving the scalability of ensemble methods like RAkEL on larger datasets.

Summary updated

BibTeX
@inproceedings{tawiah2013empirical,
  author = {Clifford A. Tawiah and Victor S. Sheng},
  title = {{Empirical Comparison of Multi-Label Classification Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8521},
}
Figure