How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Linearity <s> We studied a number of measures that characterize the difficulty of a classification problem, focusing on the geometrical complexity of the class boundary. We compared a set of real-world problems to random labelings of points and found that real problems contain structures in this measurement space that are significantly different from the random sets. Distributions of problems in this space show that there exist at least two independent factors affecting a problem's difficulty. We suggest using this space to describe a classifier's domain of competence. This can guide static and dynamic selection of classifiers for specific problems as well as subproblems formed by confinement, projection, and transformations of the feature vectors. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Linearity <s> In this paper, we introduce a new model of solving pattern recognition tasks called PRISM (Pattern Recognition using Information Slicing Method). The main concept behind PRISM is the slicing of information through multiple planes across different feature axes to generate a number of cells. The number of cells created and their volume depends upon the number partitions per axes. In this context we define resolution as the number of partitions per axes. In this paper, we make the following contributions. First, we provide a brief survey of the class separability measures and feature partitioning schemes used for pattern recognition. Secondly, we define the PRISM framework and the algorithm for data assignment to cells. Thirdly, we detail four important concepts in PRISM: purity, neighbourhood separability, collective entropy, and data compactness. The first two measures define the data complexity, the next measure relates to uncertainty, and the last measure defines the alternative to statistical data variance in the PRISM framework. Fourthly, we investigate the variability in the estimates of these measures depending on the placement of partitions on each feature axis. Finally, we give an overview of experimental successes achieved with PRISM in the areas of classification complexity estimation and feature selection. <s> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Linearity <s> There are several aspects that might influence the performance achieved by existing learning systems. It has been reported that one of these aspects is related to class imbalance in which examples in training data belonging to one class heavily outnumber the examples in the other class. In this situation, which is found in real world data describing an infrequent but important event, the learning system may have difficulties to learn the concept related to the minority class. In this work we perform a broad experimental evaluation involving ten methods, three of them proposed by the authors, to deal with the class imbalance problem in thirteen UCI data sets. Our experiments provide evidence that class imbalance does not systematically hinder the performance of learning systems. In fact, the problem seems to be related to learning with too few minority class examples in the presence of other complicating factors, such as class overlapping. Two of our proposed methods deal with these conditions directly, allying a known over-sampling method with data cleaning methods in order to produce better-defined class clusters. Our comparative experiments show that, in general, over-sampling methods provide more accurate results than under-sampling methods considering the area under the ROC curve (AUC). This result seems to contradict results previously published in the literature. Two of our proposed methods, Smote + Tomek and Smote + ENN, presented very good results for data sets with a small number of positive examples. Moreover, Random over-sampling, a very simple over-sampling method, is very competitive to more complex over-sampling methods. Since the over-sampling methods provided very good performance results, we also measured the syntactic complexity of the decision trees induced from over-sampled data. Our results show that these trees are usually more complex then the ones induced from original data. Random over-sampling usually produced the smallest increase in the mean number of induced rules and Smote + ENN the smallest increase in the mean number of conditions per rule, when compared among the investigated over-sampling methods. <s> BIB003
Sum of the error distance by linear programming Error rate of linear classifier interpretation of their values is not easy. Each measurement has an associated limitation (for example, the feature separability measures cannot cope with situations where an attribute has different ranges of values for the same class; see Figure 3 (a)) and must then be considered only as an estimate of the problem complexity, which may have associated errors. Since the measures are made on a dataset T , they also give only an apparent measurement of the problem complexity BIB001 . This reinforces the need to analyze the measures together to provide more robustness to the reached conclusions. There are also cases where some caution must be taken, such as in the case of F2, whose final values depend on the number of predictive attributes in the dataset. This particular issue is pointed out by BIB002 , which states that the complexity measures ideally should be conceptually uncorrelated to the number of features, classes, or number of data points a dataset has, making the complexity measure values for different datasets more comparable. This requirement is clearly not fulfilled by F2. Nonetheless, for the dimensionality-and balance-based measures, Singh (2003a)'s assertion does not apply, since they are indeed concerned with the relationship of the numbers of dimensions and data points a dataset has. For instance, a linearly separable problem with an oblique hyperplane will have high F1, indicating that it is complex, and also a low L1, denoting that it is simple. LSC, however, will assume a low value for a very imbalanced two-class dataset in which one of the classes contains one unique example and the other class is far and densely distributed. This would be an indicative of a simple classification problem according to LSC interpretation, but data imbalance should be considered, too. In the particular case of class imbalance measures, BIB003 show that the harmful effects due to class imbalance are more pronounced when there is also a large overlap between the classes. Therefore, these measures should be analyzed together with measures able to capture class overlap (ex. C2 with N1). Regarding network-based measures, the ϵ parameter in the ϵ − N N algorithm in ECol is fixed at 0.15, although we can expect that different values may be more appropriate for distinct datasets. With the free distribution of the ECol package, interested users are able to modify this value and also other parameters (such as the distance metric employed in various measures) and test their influence in the reported results. Finally, while some measures are based on classification models derived from the data, others use only statistics directly derived from the data. Those that use classification models, i.e., a linear classifier or an NN classifier, are: F1v, L1, L2, L3, N3, N4. This makes these measures dependent on the classifier decisions they are based on, which in turn depends on some choices in building the classifiers, such as the algorithm to derive a linear classifier, or the distance used in nearestneighbor classification . Other measures are based on characteristics extracted from the data only, although the N1 and the network indexes involve pre-computing a distance-based graph from the dataset. Moreover, it should be noticed that all measures requiring the computation of covariances or (pseudo-)inverses are time-consuming, such as F1v, T3, and T4. highlight another notice-worthy issue that some measures are unable to provide an instance-level hardness estimate. Understanding which instances are hard to classify may be valuable information, since more efforts can be devoted to them. However, many of the complexity measures originally proposed for a dataset-level analysis can be easily adapted to give instance-level hardness estimates. This is the case of N2, which averages the intra-and inter-class distances from each example to their nearest neighbors.