Complexity Measures of Supervised Classification Problems

By Tin Kam Ho, Mitra Basu. 2002

759 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Counterfactual Normalization: Proactively Addressing Dataset Shift and Improving Reliability Using Causal Mechanisms (2018, methodology): “To measure classiﬁer-independent geometric complexity we will use two types of metrics developed by Ho and Basu (2000, 2002): measures of overlap of individual features and measures of separability of classes.”
Meta-Learning: A Survey (2018, neutral): “(μc1−μc2)2 σ 2 c1−σ 2 c2 Separability classes c1, c2 [64] See [64]”
Towards A Rigorous Science of Interpretable Machine Learning (2017, methodology): “This approach is similar to eﬀorts to characterize classiﬁcation [Ho and Basu, 2002] and clustering problems [Garg and Kalai, 2016].”
How Complex Is Your Classification Problem? (2018, methodology): “Among them are the measures proposed in [Ho and Basu, 2002] to describe the complexity of the boundary needed to separate binary classiﬁcation problems, later extended to multiclass classiﬁcation problems in works like [Mollineda et al., 2005, Ho et al., 2006, Mollineda et al., 2006, Orriols-Puig…”
An instance level analysis of data complexity (2014, methodology): “We first compare our measures to those used by Ho and Basu (2002). The matrix of Spearman correlation coefficients comparing the hardness measures against those measures”
The linear separability problem: some testing methods (2006, background): “A study presenting several measures to characterize the difficulty of a classification problem is presented in [ 28 ].”
Evolutionary Undersampling for Classification with Imbalanced Datasets: Proposals and Taxonomy (2009, background): “• The analysis of evolutionary undersampling in terms of data complexity (Ho and Basu, 2002; Bernadó-Mansilla and Ho, 2005) for a better understanding of the behavior of our approach over dataset depending on the data complexity measure values.”
A review of microarray datasets and applied feature selection methods (2014, background): “Data complexity Data complexity measures are a recent proposal to represent characteristics of the data which are considered difficult in classification tasks, such as the overlapping among classes, their separability or the linearity of the decision boundaries [99,59].”
Efficient image dataset classification difficulty estimation for predicting deep-learning accuracy (2018, background): “In [22], the authors proposemeasures that characterize the difficulty of a classification problem, focusing on the geometrical complexity of the class boundary.”
SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary (2018, background): “The widest use metric to compute the degree of overlap for a given dataset is known as maximum Fisher’s discriminant ratio, or simply F1 (Ho & Basu, 2002) (it must not be confused with the F1-score performance metric).”
A systematic review on overfitting control in shallow and deep neural networks (2021, background): “In Ho and Basu (2002), Ho et al. (2006) for data complexity computation, three main measures have been considered, including the overlap of individual features, separability of classes, and geometry of the manifold.”
Mining data with random forests: A survey and results of new tests (2011, methodology): “The measures N1, N2, and N3 express mixture identifiability and are attributed to the class of measures reflecting separability of classes [37].”