# How Complex is your classification problem? A survey on measuring classification complexity

arXiv: https://arxiv.org/abs/1808.03591 · HTML: https://mlsanity.com/paper/1808.03591/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2018.

## Built on by (most cited first, 30 of 66)

- [Data-IQ: Characterizing subgroups with heterogeneous outcomes in tabular data](https://mlsanity.com/paper/2210.13043/) (2022)
- [Quantum Kernel Methods under Scrutiny: A Benchmarking Study](https://mlsanity.com/paper/2409.04406/) (2024)
- [Estimating informativeness of samples with Smooth Unique Information](https://mlsanity.com/paper/2101.06640/) (2021)
- [A Novel Intrinsic Measure of Data Separability](https://mlsanity.com/paper/2109.05180/) (2021)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Attribute-based Visual Reprogramming for Vision-Language Models](https://mlsanity.com/paper/2501.13982/) (2025)
- [Interaction-Grounded Learning with Action-inclusive Feedback](https://mlsanity.com/paper/2206.08364/) (2022)
- [Trace Encoding in Process Mining: a survey and benchmarking](https://mlsanity.com/paper/2301.02167/) (2023)
- [PMLBmini: A Tabular Classification Benchmark Suite for Data-Scarce Applications](https://mlsanity.com/paper/2409.01635/) (2024)
- [Selective Learning: Towards Robust Calibration with Dynamic Regularization](https://mlsanity.com/paper/2402.08384/) (2024)
- [A Critical Re-evaluation of Benchmark Datasets for (Deep) Learning-Based Matching Algorithms](https://mlsanity.com/paper/2307.01231/) (2023)
- [Learning Abstract Task Representations](https://mlsanity.com/paper/2101.07852/) (2021)
- [Reducing Data Complexity using Autoencoders with Class-informed Loss Functions](https://mlsanity.com/paper/2111.06142/) (2021)
- [What can we Learn by Predicting Accuracy?](https://mlsanity.com/paper/2208.01358/) (2022)
- [Improving Data Quality with Training Dynamics of Gradient Boosting Decision Trees](https://mlsanity.com/paper/2210.11327/) (2022)
- [Selecting the suitable resampling strategy for imbalanced data classification regarding dataset properties](https://mlsanity.com/paper/2201.07932/) (2021)
- [problexity -- an open-source Python library for binary classification problem complexity assessment](https://mlsanity.com/paper/2207.06709/) (2022)
- [Complexity of Representations in Deep Learning](https://mlsanity.com/paper/2209.00525/) (2022)
- [Several fitness functions and entanglement gates in quantum kernel generation](https://mlsanity.com/paper/2309.03307/) (2023)
- [Individual Packet Features are a Risk to Model Generalisation in ML-Based Intrusion Detection](https://mlsanity.com/paper/2406.07578/) (2024)
- [Application of Context-dependent Interpretation of Biosignals Recognition to Control a Bionic Multifunctional Hand Prosthesis](https://mlsanity.com/paper/2502.13301/) (2025)
- [Robust Support Vector Machines for Imbalanced and Noisy Data via Benders Decomposition](https://mlsanity.com/paper/2503.14873/) (2025)
- [TOC-UCO: a comprehensive repository of tabular ordinal classification datasets](https://mlsanity.com/paper/2507.17348/) (2025)
- [Adaptive Neighbourhoods for the Discovery of Adversarial Examples](https://mlsanity.com/paper/2101.09108/) (2021)
- [Empirical analysis of representation learning and exploration in neural kernel bandits](https://mlsanity.com/paper/2111.03543/) (2021)
- [A classification performance evaluation measure considering data separability](https://mlsanity.com/paper/2211.05433/) (2022)
- [Characterizing instance hardness in classification and regression problems](https://mlsanity.com/paper/2212.01897/) (2022)
- [Hidden Classification Layers: Enhancing linear separability between classes in neural networks layers](https://mlsanity.com/paper/2306.06146/) (2023)
- [IoTGeM: Generalizable Models for Behaviour-Based IoT Attack Detection](https://mlsanity.com/paper/2401.01343/) (2023)
- [Squeezing Lemons with Hammers: An Evaluation of AutoML and Tabular Deep Learning for Data-Scarce Classification Applications](https://mlsanity.com/paper/2405.07662/) (2024)

## Abstract (arXiv)

Characteristics extracted from the training datasets of classification problems have proven to be effective predictors in a number of meta-analyses. Among them, measures of classification complexity can be used to estimate the difficulty in separating the data points into their expected classes. Descriptors of the spatial distribution of the data and estimates of the shape and size of the decision boundary are among the known measures for this characterization. This information can support the formulation of new data-driven pre-processing and pattern recognition techniques, which can in turn be focused on challenges highlighted by such characteristics of the problems. This paper surveys and analyzes measures which can be extracted from the training datasets in order to characterize the complexity of the respective classification problems. Their use in recent literature is also reviewed and discussed, allowing to prospect opportunities for future work in the area. Finally, descriptions are given on an R package named Extended Complexity Library (ECoL) that implements a set of complexity measures and is made publicly available.