The DOI matches its Crossref record; 67 of the 67 references it cites were found in a registry or an index.
How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity
Abstract
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 article surveys and analyzes measures that can be extracted from the training datasets 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An Introduction to Support Vector Machines and Other Kernel-based Learning Methods
Cristianini, N., & Shawe-Taylor, J. (2000) · doi:10.1017/cbo9780511801389 · Cited by 13,855
He, H., & Garcia, E. A. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.239 · Cited by 10,359
A General Coefficient of Similarity and Some of Its Properties
Gower, J. C. (1971) · Biometrics · doi:10.2307/2528823 · Cited by 5,303
A dendrite method for cluster analysis
Caliński, T., & Harabasz, J. (1974) · Communications in Statistics · doi:10.1080/03610927408827101 · Cited by 4,480
A study of the behavior of several methods for balancing machine learning training data
Batista, G. E. A. P. A., Prati, R. C., & Monard, M. C. (2004) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1007730.1007735 · Cited by 4,203
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,718
Classification in the Presence of Label Noise: A Survey
Frenay, B., & Verleysen, M. (2014) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2013.2292894 · Cited by 1,777
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0 · Cited by 1,775
The Lack of A Priori Distinctions Between Learning Algorithms
Wolpert, D. H. (1996) · Neural Computation · doi:10.1162/neco.1996.8.7.1341 · Cited by 1,647
Learning from Imbalanced Data Sets
Fernández, A., García, S., Galar, M., Prati, R. C., Krawczyk, B., & Herrera, F. (2018) · doi:10.1007/978-3-319-98074-4 · Cited by 1,349
Improved Heterogeneous Distance Functions
Wilson, D. R., & Martinez, T. R. (1997) · Journal of Artificial Intelligence Research · doi:10.1613/jair.346 · Cited by 1,344
A perspective view and survey of meta-learning
Vilalta, R., & Drissi, Y. (2002) · Artificial Intelligence Review · doi:10.1023/a:1019956318069 · Cited by 1,108
Complexity measures of supervised classification problems
Ho, T. K., & Basu, M. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.990132 · Cited by 734
Self-citationSemi-supervised learning with graphs
Zhu, X., Lafferty, J., & Rosenfeld, R. (2005) · Cited by 638
Gasarch, W. (1997) · ACM SIGACT News · doi:10.1145/262301.1040343 · Cited by 583
Proceedings of the 21st International Conference on Pattern Recognition, ICPR 2012
Wilkinson, M. H. F., & Jaap, O. (2012) · Cited by 580
Proceedings of the International Joint Conference on Neural Networks (IJCNN) 2005
(2005) · Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. · doi:10.1109/ijcnn.2005.1556327 · Cited by 553
Cross-disciplinary perspectives on meta-learning for algorithm selection
Smith-Miles, K. A. (2009) · ACM Computing Surveys · doi:10.1145/1456650.1456656 · Cited by 552
Dynamic classifier selection: Recent advances and perspectives
Cruz, R. M. O., Sabourin, R., & Cavalcanti, G. D. C. (2018) · Information Fusion · doi:10.1016/j.inffus.2017.09.010 · Cited by 440
An instance level analysis of data complexity
Smith, M. R., Martinez, T., & Giraud-Carrier, C. (2014) · Machine Learning · doi:10.1007/s10994-013-5422-z · Cited by 436
Santos, M. S., Soares, J. P., Abreu, P. H., Araujo, H., & Santos, J. (2018) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2018.2866730 · Cited by 402
On learning algorithm selection for classification
Ali, S., & Smith, K. A. (2006) · Applied Soft Computing · doi:10.1016/j.asoc.2004.12.002 · Cited by 374
Feature Selection: An Ever Evolving Frontier in Data Mining
Liu, H., Motoda, H., Setiono, R., & Zhao, Z. (2010) · Cited by 353
Support Vector Machine Solvers
Bottou, L., & Lin, C.-J. (2007) · Large-Scale Kernel Machines · doi:10.7551/mitpress/7496.003.0003 · Cited by 336
Dynamic selection of classifiers—A comprehensive review
Britto, A. S., Sabourin, R., & Oliveira, L. E. S. (2014) · Pattern Recognition · doi:10.1016/j.patcog.2014.05.003 · Cited by 331
López, V., Fernández, A., Moreno-Torres, J. G., & Herrera, F. (2012) · Expert Systems with Applications · doi:10.1016/j.eswa.2011.12.043 · Cited by 316
A review on the combination of binary classifiers in multiclass problems
Lorena, A. C., de Carvalho, A. C. P. L. F., & Gama, J. M. P. (2008) · Artificial Intelligence Review · doi:10.1007/s10462-009-9114-9 · Cited by 270
Self-citationSelecting Discrete and Continuous Features Based on Neighborhood Decision Error Minimization
Hu, Q., Pedrycz, W., Yu, D., & Lang, J. (2010) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2009.2024166 · Cited by 265
META-DES: A dynamic ensemble selection framework using meta-learning
Cruz, R. M. O., Sabourin, R., Cavalcanti, G. D. C., & Ing Ren, T. (2015) · Pattern Recognition · doi:10.1016/j.patcog.2014.12.003 · Cited by 250
A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors
Ho, T. K. (2002) · Pattern Analysis & Applications · doi:10.1007/s100440200009 · Cited by 205
Self-citationLearning from Imbalanced Data Sets
ndez, A. F., ́a, S. G., Galar, M., & Ronaldo, C. (2018) · Cited by 186
Proceedings 15th International Conference on Pattern Recognition. ICPR-2000
(2000) · doi:10.1109/icpr.2000 · Cited by 179
Instance spaces for machine learning classification
Muñoz, M. A., Villanova, L., Baatar, D., & Smith‐Miles, K. (2017) · Machine Learning · doi:10.1007/s10994-017-5629-5 · Cited by 151
Effect of label noise in the complexity of classification problems
Garcia, L. P. F., de Carvalho, A. C. P. L. F., & Lorena, A. C. (2015) · Neurocomputing · doi:10.1016/j.neucom.2014.10.085 · Cited by 148
Self-citationAhmad, N. B., & Shamsuddin, S. M. (2010) · Intelligent Systems Design and Applications · Cited by 145
Data Complexity in Pattern Recognition
Basu, M., & Ho, T. K. (2020) · CERN Document Server (European Organization for Nuclear Research) · doi:10.1007/978-1-84628-172-3 · Cited by 121
Self-citationOn developing an automatic threshold applied to feature selection ensembles
Seijo-Pardo, B., Bolón‐Canedo, V., & Alonso‐Betanzos, A. (2018) · Information Fusion · doi:10.1016/j.inffus.2018.02.007 · Cited by 102
Sáez, J. A., Luengo, J., & Herrera, F. (2012) · Pattern Recognition · doi:10.1016/j.patcog.2012.07.009 · Cited by 101
The effects of model and data complexity on predictions from species distributions models
García-Callejas, D., & Araújo, M. (2016) · Ecological Modelling · doi:10.1016/j.ecolmodel.2015.06.002 · Cited by 89
Complexity of Classification Problems and Comparative Advantages of Combined Classifiers
Ho, T. K. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45014-9_9 · Cited by 71
Self-citationAnalysis of complexity indices for classification problems: Cancer gene expression data
Lorena, A. C., Costa, I. G., Spolaôr, N., & de Souto, M. C. P. (2011) · Neurocomputing · doi:10.1016/j.neucom.2011.03.054 · Cited by 71
Self-citationMultiresolution estimates of classification complexity
Singh, S. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1251146 · Cited by 70
On the nonlinearity of pattern classifiers
Hoekstra, A., & Duin, R. P. W. (1996) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.1996.547429 · Cited by 69
Noise detection in the meta-learning level
Garcia, L. P. F., de Carvalho, A. C. P. L. F., & Lorena, A. C. (2015) · Neurocomputing · doi:10.1016/j.neucom.2014.12.100 · Cited by 67
Self-citationTowards UCI+: A mindful repository design
Macià, N., & Bernadó-Mansilla, E. (2013) · Information Sciences · doi:10.1016/j.ins.2013.08.059 · Cited by 66
Metalearning for choosing feature selection algorithms in data mining: Proposal of a new framework
Parmezan, A. R. S., Lee, H., & Wu, F. C. (2017) · Expert Systems with Applications · doi:10.1016/j.eswa.2017.01.013 · Cited by 66
Sun, M., Liu, K., Wu, Q., Hong, Q., Wang, B., & Zhang, H. (2019) · Pattern Recognition · doi:10.1016/j.patcog.2019.01.047 · Cited by 57
Macià, N., Bernadó-Mansilla, E., Orriols-Puig, A., & Ho, T. K. (2012) · Pattern Recognition · doi:10.1016/j.patcog.2012.09.022 · Cited by 46
Self-citationCan classification performance be predicted by complexity measures? A study using microarray data
Morán‐Fernández, L., Bolón‐Canedo, V., & Alonso‐Betanzos, A. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-016-1003-3 · Cited by 43
PRISM ? A novel framework for pattern recognition
Singh, S. (2003) · Pattern Analysis and Applications · doi:10.1007/s10044-002-0186-2 · Cited by 34
Measurement of data complexity for classification problems with unbalanced data
Anwar, N., Jones, G., & Ganesh, S. (2014) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11228 · Cited by 33
An instance-based learning recommendation algorithm of imbalance handling methods
Zhang, X., Li, R., Zhang, B., Yang, Y., Guo, J., & Ji, X. (2019) · Applied Mathematics and Computation · doi:10.1016/j.amc.2018.12.020 · Cited by 31
Linear separability and classification complexity
Elizondo, D. A., Birkenhead, R., Gámez, M., García, N., & Alfaro, E. (2012) · Expert Systems with Applications · doi:10.1016/j.eswa.2012.01.090 · Cited by 28
Gong, R., & Huang, S. H. (2011) · Expert Systems with Applications · doi:10.1016/j.eswa.2011.12.011 · Cited by 28
Data Complexity in Machine Learning and Novel Classification Algorithms
Li, L. (2006) · CaltechTHESIS (California Institute of Technology) · doi:10.7907/ew2g-9986 · Cited by 28
Tanwani, A. K., & Farooq, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17508-4_9 · Cited by 26
Garcia, L. P. F., de Carvalho, A. C. P. L. F., & Lorena, A. C. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40846-5_63 · Cited by 25
Self-citationA note on the separability indexPreprint
Mthembu, L., & Marwala, T. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0812.1107 · Cited by 25
Data complexity in machine learning
Li, L., & Abu‐Mostafa, Y. S. (2006) · CaltechAUTHORS (California Institute of Technology) · doi:10.7907/z9319sw2 · Cited by 23
A meta-learning framework for algorithm recommendation in software fault prediction
das Dôres, S. N., Alves, L., Ruiz, D. D., et al. (2016) · ACM Symposium on Applied Computing · doi:10.1145/2851613.2851788 · Cited by 18
de Souto, M. C. P., Lorena, A. C., Spolaôr, N., & Costa, I. G. (2010) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2010.5596305 · Cited by 17
Self-citationComplexity curve: a graphical measure of data complexity and classifier performance
Zubek, J., & Plewczyński, D. (2016) · PeerJ Computer Science · doi:10.7717/peerj-cs.76 · Cited by 15
Armano, G. (2015) · Information Sciences · doi:10.1016/j.ins.2015.07.028 · Cited by 11
Using Supervised Complexity Measures in the Analysis of Cancer Gene Expression Data Sets
Costa, I. G., Lorena, A. C., y Peres, L. R. M. P., & de Souto, M. C. P. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03223-3_5 · Cited by 10
Self-citationAn Easy to Use Repository for Comparing and Improving Machine Learning Algorithm UsagePreprint
Smith, M. R., White, A. D., Giraud-Carrier, C. G., et al. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.7292 · Cited by 10
Quantification of side-channel information leaks based on data complexity measures for web browsing
He, Z., Chan, P. P. K., Yeung, D., Witold Pedrycz, C., & Ng, W. W. Y. (2015) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-015-0348-3 · Cited by 6
Analyzing Data Complexity Using Metafeatures for Classification Algorithm Selection
Shah, R., Khemani, V., Azarian, M. H., et al. (2018) · Prognostics and System Health Management Conference · doi:10.1109/phm-chongqing.2018.00224 · Cited by 5
Cited by
Modelling species presence‐only data with random forests
Valavi, R., Elith, J., Lahoz‐Monfort, J. J., & Guillera‐Arroita, G. (2021) · Ecography · doi:10.1111/ecog.05615 · Cited by 307
Characterizing the Decision Boundary of Deep Neural Networks
Karimi, H., Derr, T., & Tang, J. (2019) · arXiv · doi:10.48550/arxiv.1912.11460 · Cited by 46
Metadata
- Authors
- Lorena, A. C., Garcia, L. P. F., Lehmann, J., Souto, M. C. P., & Ho, T. K.
- Venue
- ACM Computing Surveys
- Published
- 2019-09-13
- Volume
- 52
- Issue
- 5
- Pages
- 1-34
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2973136425
- Cited by
- 275
- References
- 67
- FWCI
- 12.55
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.