mlsanityData to 7 Oct 2026

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

arXiv 1808.03591 ↗First posted 10 Aug 2018cs.LG stat.MLcited by 66

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 14; 2023: 10; 2024: 11; 2025: 14; 2026: 7.

66 papers.

Sort:

By area:

  1. 2022Data-IQ: Characterizing subgroups with heterogeneous outcomes in tabular datacited by 22
  2. 2024Quantum Kernel Methods under Scrutiny: A Benchmarking Studycited by 22
  3. 2021Estimating informativeness of samples with Smooth Unique Informationcited by 15
  4. 2021A Novel Intrinsic Measure of Data Separabilitycited by 9
  5. 2023It Is All About Data: A Survey on the Effects of Data on Adversarial Robustnesscited by 9
  6. 2022Interaction-Grounded Learning with Action-inclusive Feedbackcited by 7
  7. 2025Attribute-based Visual Reprogramming for Vision-Language Modelscited by 7
  8. 2023Trace Encoding in Process Mining: a survey and benchmarkingcited by 6
  9. 2024Selective Learning: Towards Robust Calibration with Dynamic Regularizationcited by 5
  10. 2024PMLBmini: A Tabular Classification Benchmark Suite for Data-Scarce Applicationscited by 5
  11. 2023A Critical Re-evaluation of Benchmark Datasets for (Deep) Learning-Based Matching Algorithmscited by 4
  12. 2021Learning Abstract Task Representationscited by 3
38 more
  1. 2021Reducing Data Complexity using Autoencoders with Class-informed Loss Functionscited by 3
  2. 2022What can we Learn by Predicting Accuracy?cited by 3
  3. 2022Improving Data Quality with Training Dynamics of Gradient Boosting Decision Treescited by 3
  4. 2021Selecting the suitable resampling strategy for imbalanced data classification regarding dataset propertiescited by 2
  5. 2022problexity -- an open-source Python library for binary classification problem complexity assessmentcited by 2
  6. 2022Complexity of Representations in Deep Learningcited by 2
  7. 2023Several fitness functions and entanglement gates in quantum kernel generationcited by 2
  8. 2024Individual Packet Features are a Risk to Model Generalisation in ML-Based Intrusion Detectioncited by 2
  9. 2025Application of Context-dependent Interpretation of Biosignals Recognition to Control a Bionic Multifunctional Hand Prosthesiscited by 2
  10. 2025Robust Support Vector Machines for Imbalanced and Noisy Data via Benders Decompositioncited by 2
  11. 2025TOC-UCO: a comprehensive repository of tabular ordinal classification datasetscited by 2
  12. 2021Adaptive Neighbourhoods for the Discovery of Adversarial Examplescited by 1
  13. 2021Empirical analysis of representation learning and exploration in neural kernel banditscited by 1
  14. 2022A classification performance evaluation measure considering data separabilitycited by 1
  15. 2022Characterizing instance hardness in classification and regression problemscited by 1
  16. 2023IoTGeM: Generalizable Models for Behaviour-Based IoT Attack Detectioncited by 1
  17. 2024Squeezing Lemons with Hammers: An Evaluation of AutoML and Tabular Deep Learning for Data-Scarce Classification Applicationscited by 1
  18. 2024iCost: A Novel Instance-Complexity-Based Cost-Sensitive Learning Frameworkcited by 1
  19. 2024Problem-oriented AutoML in Clusteringcited by 1
  20. 2025Your Model is Overconfident, and Other Lies We Tell Ourselvescited by 1
  21. 2025A Survey on Small Sample Imbalance Problem: Metrics, Feature Analysis, and Solutionscited by 1
  22. 2025Imbalanced Regression Pipeline Recommendationcited by 1
  23. 2025When Data Quality Issues Collide: A Large-Scale Empirical Study of Co-Occurring Data Quality Issues in Software Defect Predictioncited by 1
  24. 2026Dataset Complexity Shapes Finite-Distance Loss Geometry in Neural Networkscited by 1
  25. 2021Experimental Investigation and Evaluation of Model-based Hyperparameter Optimizationcited by 0
  26. 2021Man versus Machine: AutoML and Human Experts' Role in Phishing Detectioncited by 0
  27. 2021Holistic Deep Learningcited by 0
  28. 2022Local overlap reduction procedure for dynamic ensemble selectioncited by 0
  29. 2022On Taking Advantage of Opportunistic Meta-knowledge to Reduce Configuration Spaces for Automated Machine Learningcited by 0
  30. 2022Dataset Complexity Assessment Based on Cumulative Maximum Scaled Area Under Laplacian Spectrumcited by 0
  31. 2022Fine-tune your Classifier: Finding Correlations With Temperaturecited by 0
  32. 2022Eigen Memory Treescited by 0
  33. 2022A Critical Analysis of Classifier Selection in Learned Bloom Filterscited by 0
  34. 2023Why is the prediction wrong? Towards underfitting case explanation via meta-classificationcited by 0
  35. 2023Clustering Indices based Automatic Classification Model Selectioncited by 0
  36. 2023Hidden Classification Layers: Enhancing linear separability between classes in neural networks layerscited by 0
  37. 2023Poison is Not Traceless: Fully-Agnostic Detection of Poisoning Attackscited by 0
  38. 2023Towards Unsupervised Representation Learning: Learning, Evaluating and Transferring Visual Representationscited by 0

50 most cited of 66 All 66 (JSON)