Source-linked AI summary
How Complex is your classification problem? A survey on measuring classification complexity
Ana C. Lorena, Luís P. F. Garcia, Jens Lehmann, Marcilio C. P. Souto, Tin K. Ho
TL;DR
Classification-complexity measures address how difficult it is to separate labeled data, a question relevant to understanding and comparing learning problems. The paper surveys, standardizes, and reviews these measures, implements 22 of them in ECoL, and identifies opportunities for empirical evaluation and better technique design. The review finds that the measures are mainly used to characterize datasets and the competence domains of learning and preprocessing methods, while their individual contributions are often not clearly evaluated.
Problem
The paper addresses how to characterize the difficulty of separating data points into their expected classes using descriptors extracted from training datasets.
Method
The paper surveys and standardizes data complexity measures, reviews their applications, and implements 22 measures in the publicly available ECoL R package.
Results
The measures are mainly used to characterize datasets and the domains of competence of learning and preprocessing techniques in meta-learning studies.
Takeaways & Limitations
The review identifies opportunities to use complexity measures to adapt or develop learning and preprocessing techniques, an area it describes as poorly explored.
Takeaways & Limitations
Most reviewed studies do not clearly evaluate each measure's contribution and often select measures ad hoc, such as one representative per category.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper motivates classification-complexity analysis as a way to understand why learning techniques succeed or fail across problems and to guide data-driven method development. It surveys existing measures, reviews their use, and provides a standardized implementation in ECoL.
- Classification-complexity analysis helps identify scenarios in which particular machine-learning techniques succeed or fail.
- Complexity analysis can guide data-driven preprocessing and pattern-recognition techniques tailored to problem characteristics.
- Classification complexity combines class ambiguity, data sparsity and dimensionality, and the complexity of the separating boundary.
- The survey extends earlier work with additional measures, standardized formulations, literature applications, and reported strengths and weaknesses.
- The surveyed measures are implemented in the publicly available ECoL R package, which includes standardized DCoL measures and novel additions.
2 Complexity Measures
The paper organizes complexity measures around different aspects of feature informativeness, separability, local structure, graph structure, and dimensionality. Their definitions assume a labeled learning dataset, often numerical features, and in some cases binary classes.
- Complexity measures include feature-based, linearity, neighborhood, network, and dimensionality categories.
- Feature-based measures characterize feature informativeness for separating classes, whereas linearity measures assess linear separability.
- Neighborhood measures describe local densities and class relationships, while network measures model structural information as a graph.
- Dimensionality measures indicate data sparsity, reflecting the potential difficulty of modeling low-density regions.
- Measures are estimated from labeled datasets with n examples, m predictive features, and n_c classes; most require numerical features, and some are binary-only.
2.1 Feature-based Measures
Feature-based measures characterize classification complexity by evaluating how informative individual features are and how much feature-value overlap separates classes. The section presents F1 and its directional variant, then discusses F2–F4 and their assumptions and limitations.
- Feature-based measures: Feature-based measures assess whether available features discriminate classes, with a highly discriminative feature indicating a simpler problem.Most measures require numerical features, and many are restricted to binary classification problems.
- Maximum Fisher’s Discriminant Ratio (F1): F1 measures feature-value overlap through the maximum Fisher’s discriminant ratio; under the inverse formulation, higher values indicate more complex problems.The formulation is bounded in (0, 1], and low values indicate that at least one feature can fairly separate classes with a perpendicular hyperplane.
- Directional-vector Maximum Fisher’s Discriminant Ratio (F1v): F1v complements F1 by projecting examples onto a direction chosen to maximize class separation, allowing an appropriately oriented linear hyperplane to separate the data.Its binary asymptotic cost is O(m · n + m^3), and multiclass problems are decomposed using one-versus-one subproblems.
- Volume of Overlapping Region (F2): F2 computes normalized overlap across feature-value ranges, where higher values indicate greater class overlap.The measure costs O(m·n·nc) with one-versus-one decomposition, but can become feature-count dependent and cannot capture simple oblique linear boundaries.
- Volume of Overlapping Region (F2): F2 is vulnerable to discriminative features with overlapping extrema and to noisy examples, while a proposed workaround applies only to discrete features and requires prior discretization for continuous ones.F3 inherits related problems because it also uses per-feature minimum and maximum values across classes.
2.2 Measures of Linearity
Linearity measures quantify whether classes can be separated by a hyperplane, using a linear SVM formulation that balances margin maximization against training errors. L1, L2, and L3 characterize different aspects of linear separability, while their interpretations and computational costs impose distinct limitations.
- Linearity measures assess whether classes can be separated by a hyperplane, under the assumption that linear separability indicates a simpler classification problem.
- The adopted linear SVM finds a maximum-margin hyperplane while minimizing training errors; symbolic features require numerical conversion and multiclass problems require decomposition.
- L1: Error Distance of Linear Classifier: L1 sums distances of incorrectly classified examples to a linear boundary, with zero indicating linear separability and lower values indicating simpler problems.
- L1: Error Distance of Linear Classifier: L1 cannot distinguish narrow-margin linear separation from large-margin separation, and its worst-case cost is O(n^2).
- L2: Error Rate of Linear Classifier: L2 measures the linear SVM error rate, where higher values indicate more errors and greater complexity of non-linear separation.
- L2: Error Rate of Linear Classifier: L2 shares L1’s inability to distinguish barely separable data from classes separated by a large margin, while its asymptotic cost is O(n^2).
- L3: Non-Linearity of a Linear Classifier: L3 interpolates same-class training pairs, then evaluates a classifier trained on the original data at the generated points; higher values indicate greater complexity.
2.3 Neighborhood Measures
Neighborhood measures characterize classification complexity through local class relationships, boundary structure, and within-class distribution. They include distance-, nearest-neighbor-, hypersphere-, and local-set-based descriptors.
- Fraction of Borderline Points (N1): N1 builds a Minimum Spanning Tree and measures the percentage of vertices incident to edges linking opposite-class examples.Higher N1 indicates more complex decision boundaries and/or greater class overlap.
- Fraction of Borderline Points (N1): N1 is sensitive to mislabeled examples and can be large even for linearly separable problems when borderline cross-class distances are unusually small.Multiple valid MSTs can also produce different N1 values, motivating averaged estimates over differently ordered constructions.
- Ratio of Intra/Extra Class Nearest Neighbor Distance (N2): N2 compares summed nearest same-class distances with summed nearest opposite-class distances to characterize class separation and internal distribution.Low N2 indicates simpler problems, whereas N2 can be high for sparse, elongated class structures and is sensitive to labeling noise.
- Error Rate of the Nearest Neighbor Classifier (N3): N3 is the leave-one-out error rate of a 1NN classifier, with higher values indicating many examples near examples from other classes.Its computation requires O(m · n^2) operations.
- Non-Linearity of the Nearest Neighbor Classifier (N4): N4 uses a nearest-neighbor classifier on interpolated points and applies directly to multiclass problems without binary decomposition.Higher N4 indicates greater complexity, and its asymptotic cost is O(m · n · l), where l is the number of interpolated points.
- Fraction of Hyperspheres Covering Data (T1): T1 estimates topological complexity as the proportion of retained hyperspheres covering the dataset, with hyperspheres grown until reaching opposite-class examples.The proposed implementation determines radii from nearest-enemy relationships and removes hyperspheres contained within larger ones.
2.4 Network Measures
Network measures represent classification datasets as distance-weighted graphs and extract structural properties from their connectivity. These properties describe density, neighborhood grouping, and node influence in ways that complement basic complexity measures.
- Motivation: Graph-based measures showed low correlation with Ho and Basu’s basic complexity measures, supporting their use as an alternative representation of data structure.This finding was reported by Garcia et al. [2015].
- Graph Construction: Network measures construct graphs whose vertices are examples and whose distance-weighted edges preserve relationships among data points.The graph-based measures require a distance matrix, whose computation dominates their asymptotic cost at O(m · n^2).
- Edge Density: The edge-density measure normalizes the number of retained graph edges by the maximum possible number of edges.Lower values correspond to dense same-class regions or low-density data with nearby opposite-class examples, which are associated with different complexity levels.
- Clustering Coefficient: The clustering coefficient measures how closely each vertex’s neighbors form cliques and is smaller for simpler datasets with dense same-class connections.It aggregates the ratio of existing neighbor-to-neighbor edges to the maximum possible number.
- Hub Score: The hub score measures node influence through connections to highly connected neighbors, using the principal eigenvector of A^T A.The paper averages hub scores across vertices; complex overlapping datasets are expected to have smaller values than simple datasets.
2.5 Dimensionality Measures
Dimensionality measures characterize sparsity by relating the number of examples and informative dimensions to the difficulty of modeling the data. They use original or reduced dimensionality to capture different aspects of the input space.
- Overview: Dimensionality measures indicate data sparsity, which may hinder model extraction because low-density regions can be classified arbitrarily.They can be based on either the original or a reduced dataset dimensionality.
- T2: T2 uses the inverse of the examples-to-dimensionality ratio so higher values correspond to more complex, sparser datasets.Lower T2 indicates less sparsity and simpler problems; computation costs O(m + n).
- T3: T3 assesses sparsity using the number of PCA components required to represent 95% of data variability rather than raw feature dimensionality.Smaller T3 values indicate simpler, less sparse datasets, while PCA computation costs O(m^2 · n + m^3).
- T4: T4 estimates the proportion of relevant dimensions according to PCA-based data variability.Larger T4 values mean more original features are needed to describe variability, indicating a more complex relationship among input variables.
2.6 Class Imbalance Measures
Class imbalance measures quantify differences in class proportions because severe imbalance can make classification more complex. The presented indices assign lower complexity to balanced class distributions.
- Overview: Class imbalance is a large difference in the number of examples per class, which can make classifiers favor the majority class and impair generalization.Problems with highly unequal class proportions are considered more complex than balanced problems.
- C1: C1 captures class imbalance from the proportions of examples in each class and reaches its minimum when all proportions are equal.Its computation requires O(n) operations to obtain class proportions.
- C2: C2 is a multiclass-compatible class-balance index whose larger values indicate more imbalance.Its minimum occurs when every class has the same number of instances, and the class counts require O(n) operations to compute.
2.7 Other Measures
This section surveys alternative complexity measures that characterize classification problems through instance hardness, separability, density, resolution, feature signatures, and related generalizations.
- Separability and density: Density measures quantify global density, local-neighborhood volume, and class density within overlap regions.D1 counts examples per unit volume, D2 averages the volume occupied by nearest neighbors, and D3 counts points from each class in regions shared with another class.
- Resolution-based measures: Multi-resolution approaches partition datasets at different spatial scales or evaluate hyperspheres and resulting profile clusters.MRCA measures class imbalance within hyperspheres, clusters profile patterns, and ranks clusters using the Multiresolution Index.
- Other approaches: Other proposals include class signatures for feature discrimination, local-set measures for borderline points, and complexity curves based on Hellinger distance.The Hellinger-based curve uses subsets of different sizes and its area as a data-complexity estimate, assuming independent input features.
- Instance-level measures: Instance hardness measures estimate difficulty for individual data points and can be averaged to obtain dataset-level complexity.kDN measures the percentage of nearest neighbors with different labels; local-neighborhood approaches classify points as easy or difficult based on neighbor-label agreement.
- Separability and density: Class separability measures include distances such as Mahalanobis, Bhattacharyya, Normal Information Radius, and Kullback-Leibler distance.Some are computationally intensive because they require covariance matrices and their inverses.
- Other approaches: The literature also extends complexity measures to regression, multi-label classification, and optimization problems.These extensions adapt the measurement goal to different problem types.
3 The ECol Package
ECoL packages 22 standardized and extended complexity measures, while the survey emphasizes that their values are estimates requiring joint interpretation because each measure has limitations and scope dependencies.
- Package contents: ECoL assembles 22 complexity measures into a publicly available R package, with bounded intervals and larger values indicating greater measured complexity.The package documents categories, acronyms, value limits, and worst-case asymptotic computation costs.
- Package contents: The package includes measures from DCoL, standardized and reimplemented in R, plus novel measures and corrections from related literature.The implementation is publicly available through CRAN and GitHub.
- Interpretation and limitations: Complexity values are apparent measurements based on dataset T, and robust conclusions require analyzing multiple measures together.Feature-separability measures and F2 illustrate limitations related to attribute ranges and the number of predictive attributes.
- Interpretation and limitations: Individual measures can yield conflicting interpretations because they capture different characteristics of complexity.A linearly separable problem with an oblique hyperplane can have high F1 but low L1.
- Interpretation and limitations: Class-imbalance measures should be interpreted alongside class-overlap measures, while network-based results depend on the chosen ϵ parameter and other settings.ECoL fixes ϵ at 0.15 but allows users to modify it and other parameters.
- Interpretation and limitations: Measures based on linear or nearest-neighbor classifiers depend on the decisions and construction choices of those underlying models.The affected measures include F1v, L1, L2, L3, N3, and N4.
4 Application Areas
The reviewed literature applies data-complexity measures to dataset analysis, preprocessing, algorithm analysis, and meta-learning. Applications commonly use them to characterize when learning or preprocessing techniques perform well or poorly, while measure selection and contribution remain open issues.
- Data analysis: Data-complexity measures help analyze how dataset characteristics affect achievable classification performance in domains such as cancer gene-expression data.In microarray studies, highlighted measures included F1 and F3, N1 and N2 for kNN, and L1 for linear classifiers.
- Data analysis: The measures support controlled artificial-dataset generation for evaluating classifiers under systematically varied challenging conditions.Multi-objective genetic algorithms have been used to select instances according to target characteristics.
- Data preprocessing: Applications in preprocessing include feature selection, noise identification, instance selection, and handling class imbalance.Feature selection studies used complexity measures to guide searches and assess changes in the original problem.
- Data preprocessing: Data complexity can be more determinant of model performance than class imbalance, while imbalance can amplify complexity effects.Complexity measures have also been used to compare preprocessing and cost-sensitive learning for imbalanced classification.
- Learning algorithms: At the algorithm level, complexity measures are used to understand transformations, design classifiers, and identify domains where particular techniques may succeed or fail.They can support selecting a technique for a new problem and designing methods based on complexity information.
- Meta-learning and synthesis: Across reviewed applications, measures mainly characterize learning and preprocessing competence domains and serve as meta-features in meta-learning.However, many studies select measures ad hoc, and the contribution of individual values is often not clearly evaluated.
5 Conclusion
The survey consolidates data complexity measures for characterizing classification difficulty, while highlighting interpretive limits and opportunities to use them in designing techniques and problem formulations.
- Data complexity measures characterize classification difficulty through data geometry and distributions within or across classes.The survey traces these indices to Ho and Basu and their use in classification and preprocessing research.
- The measures span feature-based, linearity-based, neighborhood-based, network-based, dimensionality, and class-imbalance perspectives.These families capture different aspects, but several measures share similar concepts and computation.
- Feature-based measures are less reliable when features are sensory signals rather than meaningful, independently interpretable explanatory variables.Categorical features also create difficulties for measures relying on value ranges.
- Linearity measures can overstate simplicity for sparse or high-dimensional datasets, so complexity evaluations should first be anchored on fixed datasets.Linear separability may reflect data size, density, and dimensionality rather than the underlying task alone.
- Neighborhood-based measures require an appropriate distance metric and may mix discrimination-relevant boundary information with broader within-class distributional information.Scale normalization or weighting may be needed for heterogeneous feature types and scales.
- The ECoL package implements 22 measures, while future work should identify a smaller core subset and use complexity measures to guide techniques and alternative class definitions.The survey notes that applications based on complexity-informed learning methods and class formulations remain relatively underexplored.