How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Volume of Overlapping <s> Machine Learning algorithms have been widely used for gene expression data classification, despite the fact that these data have often intrinsic limitations, such as high dimensionality and a small number of examples. Few studies try to characterize to which extent these aspects can influence the performance of the classification models induced. In this paper we compute different measures characterizing the complexity of gene expression data sets for cancer diagnosis. We then investigate how these measures relate to the classification performances achieved by support vector machines, a popular Machine Learning technique usually employed in the analysis of gene expression data. The results obtained indicate that some of the complexity indices utilized are indeed successful in explaining the difficulty involved in the classification of cancer gene expression data. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Volume of Overlapping <s> Feature selection plays an important role in pattern recognition and machine learning. Feature evaluation and classification complexity estimation arise as key issues in the construction of selection algorithms. To estimate classification complexity in different feature subspaces, a novel feature evaluation measure, called the neighborhood decision error rate (NDER), is proposed, which is applicable to both categorical and numerical features. We first introduce a neighborhood rough-set model to divide the sample set into decision positive regions and decision boundary regions. Then, the samples that fall within decision boundary regions are further grouped into recognizable and misclassified subsets based on class probabilities that occur in neighborhoods. The percentage of misclassified samples is viewed as the estimate of classification complexity of the corresponding feature subspaces. We present a forward greedy strategy for searching the feature subset, which minimizes the NDER and, correspondingly, minimizes the classification complexity of the selected feature subset. Both theoretical and experimental comparison with other feature selection algorithms shows that the proposed algorithm is effective for discrete and continuous features, as well as their mixture. <s> BIB002
where: The values max( f c j i ) and min( f c j i ) are the maximum and minimum values of each feature in a class c j ∈ {1, 2}, respectively. The numerator becomes zero when the per-class value ranges are disjoint for at least one feature. This equation uses a correction that was made in BIB001 and  to the original definition of F2, which may yield negative values for non-overlapping feature ranges. The asymptotic cost of this measure is O (m · n · n c ), considering a OVO decomposition in the case of multiclass problems. The higher the F2 value, the greater the amount of overlap between the problem classes. Therefore, the problem's complexity is also higher. Moreover, if there is at least one non-overlapping feature, the F2 value should be zero. Figure 2 illustrates the region that F2 tries to capture (as the shaded area), for a dataset with two features and two classes.  points to an issue with F2 for the cases illustrated in Figure 3 . In Figure 3 (a), the attribute is discriminative but the minimum and maximum values overlap in the different classes; and in Figure 3 (b), there is one noisy example that disrupts the measure values.  proposes to deal with these situations by counting the number of feature values in which there is an overlap, which is only suitable for discrete-valued features. Using this solution, continuous features must be discretized a priori, which imposes the difficulty of choosing a proper discretization technique and associated parameters, an open issue in data mining  . It should be noted that the situations shown in Figure 3 can also be harmful for the F1 measure. As noted by BIB002 , F2 does not capture the simplicity of a linear oblique border either, since it assumes again that the linear boundary is perpendicular to one of the features axes. Finally, the F2 value can become very small depending on the number of operands in Equation (9); that is, it is highly dependent on the number of features a dataset has. This worsens for problems with many features, so their F2 values may not be comparable to those of other problems with fewer features. BIB001 , , and, more recently, Seijo-Pardo et al. (2019) use a sum instead of the product in Equation (9), which partially solves the problems identified. Nonetheless, the result is not an overlapping volume and corresponds to the amount or size of the overlapping region. In addition, the measure remains influenced by the number of features the dataset has. 2. 1.4 Maximum Individual Feature Efficiency (F3) . This measure estimates the individual efficiency of each feature in separating the classes and considers the maximum value found among the m features. Here, we take the complement of this measure so higher values are obtained for more complex problems. For each feature, it checks whether there is overlap of values between examples of different classes. If there is overlap, the classes are considered to be ambiguous in this region. The problem can be considered simpler if there is at least one feature that shows low ambiguity between the classes, so F3 can be expressed as: where n o ( f i ) gives the number of examples that are in the overlapping region for feature f i and can be expressed by Equation (11). Low values of F3, computed by Equation (10), indicate simpler problems, where few examples overlap in at least one dimension. As with F2, the asymptotic cost of the F3 measure is O (m · n · n c ). In Equation (11), I is the indicator function, which returns 1 if its argument is true and 0 otherwise, while max min( f i ) and min max( f i ) are the same as defined for F2. Figure 4 depicts the computation of F3 for the same dataset from Figure 2 . While for feature f 1 the proportion of examples that are in the overlapping region is 14 30 (Figure 4(a) ), for f 2 this proportion is 25 30 (Figure 4(b) ), resulting in a F3 value of 14 30 . Since n o ( f i ) is calculated taking into account the minimum and maximum values of the feature f i in different classes, it entails the same problems identified for F2 with respect to: classes in which the feature has more than one valid interval (Figure 3(a) ), susceptibility to noise (Figure 3(b) ) and the fact that it is assumed that in linearly separable problems, the boundary is perpendicular to an input axis. (F4) . The F4 measure was proposed in to get an overview of how the features work together. It successively applies a procedure similar to that adopted for F3. First the most discriminative feature according to F3 is selected; that is, the feature that shows less overlap between different classes. All examples that can be separated by this feature are removed from the dataset and the previous procedure is repeated: the next most discriminative feature is selected, excluding the examples already discriminated. This procedure is applied until all the features have been considered and can also be stopped when no example remains. F4 considers the ratio of examples that have not been discriminated, as presented in Equation (12) . F4 is computed after l rounds are performed through the dataset, where l is in the range [1, m] . If one of the input features is already able to discriminate all the examples in T , l is 1, while it can get up to m in the case all features have to be considered. Its equation can be denoted by: