How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <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> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> In discriminating between objects from different classes, the more separable these classes are the less computationally expensive and complex a classifier can be used. One thus seeks a measure that can quickly capture this separability concept between classes whilst having an intuitive interpretation on what it is quantifying. A previously proposed separability measure, the separability index (SI) has been shown to intuitively capture the class separability property very well. This short note highlights the limitations of this measure and proposes a slight variation to it by combining it with another form of separability measure that captures a quantity not covered by the Separability Index. <s> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> The algorithm selection problem [Rice 1976] seeks to answer the question: Which algorithm is likely to perform best for my problemq Recognizing the problem as a learning task in the early 1990's, the machine learning community has developed the field of meta-learning, focused on learning about learning algorithm performance on classification problems. But there has been only limited generalization of these ideas beyond classification, and many related attempts have been made in other disciplines (such as AI and operations research) to tackle the algorithm selection problem in different ways, introducing different terminology, and overlooking the similarities of approaches. In this sense, there is much to be gained from a greater awareness of developments in meta-learning, and how these ideas can be generalized to learn about the behaviors of other (nonlearning) algorithms. In this article we present a unified framework for considering the algorithm selection problem as a learning problem, and use this framework to tie together the crossdisciplinary developments in tackling the algorithm selection problem. We discuss the generalization of meta-learning concepts to algorithms focused on tasks including sorting, forecasting, constraint satisfaction, and optimization, and the extension of these ideas to bioinformatics, cryptography, and other fields. <s> BIB003 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> In this paper, analysis of class separability measures is performed in attempt to relate their descriptive abilities to geometrical properties of classification problems in presence of irrelevant features. The study is performed on synthetic and benchmark data with known irrelevant features and other characteristics of interest, such as class boundaries, shapes, margins between classes, and density. The results have shown that some measures are individually informative, while others are less reliable and only can provide complimentary information. Classification problem complexity measurements on selected data sets are made to gain additional insights on the obtained results. <s> BIB004 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> We study the relationship between linear separability and the level of complexity of classification data sets. Linearly separable classification problems are generally easier to solve than non linearly separable ones. This suggests a strong correlation between linear separability and classification complexity. We propose a novel and simple method for quantifying the complexity of the classification problem. The method, which is shown below, reduces any two class classification problem to a sequence of linearly separable steps. The number of such reduction steps could be viewed as measuring the degree of non-separability and hence the complexity of the problem. This quantification in turn can be used as a measure for the complexity of classification data sets. Results obtained using several benchmarks are provided. <s> BIB005 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> Systems for assessing the classification complexity of a dataset have received increasing attention in research activities on pattern recognition. These systems typically aim at quantifying the overall complexity of a domain, with the goal of comparing different datasets. In this work, we propose a method for partitioning a dataset into regions of different classification complexity, so to highlight sources of complexity inside the dataset. Experiments have been carried out on relevant datasets, proving the effectiveness of the proposed method. <s> BIB006 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> Performance measures are used in various stages of the process aimed at solving a classification problem. Unfortunately, most of these measures are in fact biased, meaning that they strictly depend on the class ratio - i.e. on the imbalance between negative and positive samples. After pointing to the source of bias for the best known measures, novel unbiased measures are defined which are able to capture the concepts of discriminant and characteristic capability. The combined use of these measures can give important information to researchers involved in machine learning or pattern recognition tasks, in particular for classifier performance assessment and feature selection. <s> BIB007 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Other Measures <s> Multiple classifier systems focus on the combination of classifiers to obtain better performance than a single robust one. These systems unfold three major phases: pool generation, selection and integration. One of the most promising MCS approaches is Dynamic Selection (DS), which relies on finding the most competent classifier or ensemble of classifiers to predict each test sample. The majority of the DS techniques are based on the K-Nearest Neighbors (K-NN) definition, and the quality of the neighborhood has a huge impact on the performance of DS methods. In this paper, we perform an analysis comparing the classification results of DS techniques and the K-NN classifier under different conditions. Experiments are performed on 18 state-of-the-art DS techniques over 30 classification datasets and results show that DS methods present a significant boost in classification accuracy even though they use the same neighborhood as the K-NN. The reasons behind the outperformance of DS techniques over the K-NN classifier reside in the fact that DS techniques can deal with samples with a high degree of instance hardness (samples that are located close to the decision border) as opposed to the K-NN. In this paper, not only we explain why DS techniques achieve higher classification performance than the K-NN but also when DS should be used. <s> BIB008
This section gives an overview of some other measures that can be used to characterize the complexity of classification problems found in the related literature. Part of these measures was not described previously, because they capture similar aspects already measured by the described measures. Other measures were excluded, because they have a high computational cost. Walt and Barnard (2007) present some variations of the T1 measure. One of them is quite similar to the LSC measure, with a difference on the normalization used by LSC. Another variation first generates an MST connecting the hypersphere centers given by T1 and then counts the number of vertexes that connect examples from different classes. There is also a measure that computes the density of the hyperspheres. We believe that the LSC measure complements T1 at a lower computational cost. present some density measures. The first one, named D1, gives the average number of examples per unit of volume in the dataset. The volume of local neighborhood (D2) measure gives the average volume occupied by the k nearest neighbors of each example. Finally, the class density in overlap region (D3) determines the density of each class in the overlap regions. It counts, for each class, the number of points lying in the same region of a different class. Although these measures give an overview of data density, we believe that they do not allow to extract complementary views of the problem complexity already captured by the original neighborhood-based measures. Furthermore, they may have a higher computational cost and present an additional parameter (e.g., the k in k nearest neighbors) to be tuned. Some of the measures found in the literature propose to analyze the dataset using a divisive approach or in multiple resolutions. Usually they show a high computational cost that can be prohibitive for datasets with a moderate number of features.  reports some of such measures. Their partitioning algorithm generates hypercuboids in the space at different resolutions (with increasing numbers of intervals per feature from 0 to 31). At each resolution, the data points are assigned into cells. Purity measures whether the cells contain examples from a same class or from mixed classes. The nearest neighbor separability measure counts, for each example of a cell, the proportion of its nearest neighbors that share its class. The cell measurements are linearly weighted to obtain a single estimate and the overall measurement across all cells at a given resolution is exponentially weighted. Afterwards, the area under the curve defined by one separability measure versus the resolution defines the overall data separability. In BIB001 , two more measures based on the space partitioning algorithm are defined: collective entropy, which is the level of uncertainty accumulated at different resolutions; and data compactness, related to the proportion of non-empty cells at different resolutions. In BIB006 , a method named Multi-resolution Complexity Analysis (MRCA) is used to partition a dataset. Like in T1, hyperspheres of different amplitudes are drawn around the examples and the imbalance regarding how many examples of different classes they contain is measured. A new dataset of profile patterns is obtained, which is clustered. Afterwards, each cluster is evaluated and ranked according to a complexity metric called Multiresolution Index (MRI). BIB007 presents how to obtain a class signature that can be used to identify, for instance, the discriminative capability of the input features. This could be regarded as a feature-based complexity measure, although more developments are necessary, since the initial studies considered binary-valued features only. BIB002 present a Separability Index SI, which takes into account the average number of examples in a dataset that have a nearest neighbor with the same label. This is quite similar to what is captured by N3, except for using more neighbors in NN classification. Another measure named Hypothesis margin (HM) takes the distance between the nearest neighbor of an object of the same class and a nearest enemy of another class. This largely resembles the N2 computation. Similarly to D3, and introduce a complexity measure that also focuses on local information for each example by employing the nearest neighbor algorithm. If the majority of the k nearest neighbors of an example share its label, this point can be regarded as easy to classify. Otherwise, it is a difficult point. An overall complexity measure is given by the proportion of data points classified as difficult. define some measures based on the concept of Local Sets previously described, which employ neighborhood information. Besides LSC, also propose to cluster the data in the local sets and then count the number of obtained clusters. This measure is related to T1. The third measure is named number of invasive points (Ipoints), which uses the local sets to identify borderline instances and is related to N1, N2, and N3. propose a set of measures devoted to understand why some data points are harder to classify than others. They are called instance hardness measures. One advantage of such an approach is to reveal the difficulty of a problem at the instance level, rather than at the aggregate level with the entire dataset. Nonetheless, the measures can be averaged to give an estimate at the dataset level. As shown in some recent work on dynamic classifier selection BIB008 , the concept of instance hardness is very useful for pointing out classifiers able to perform well in confusing or overlapping areas of the dataset, giving indicatives of a local level of competence. Most of the complexity measures previously presented, although formulated for obtaining a complexity estimate per dataset, can be adapted to assess the contribution of each example to the overall problem difficulty. Nonetheless, this is beyond the scope of this article. One very effective instance hardness measure from is the k-Disagreeing Neighbors (kDN), which gives the percentage of the k nearest neighbors that do not share the label of an example. This same concept was already explored in the works of , BIB002 BIB002 . The Disjunct Size (DS) corresponds to the size of a disjunct that covers an example divided by the largest disjunct produced, in which disjuncts are obtained using the C4.5 learning algorithm. A related measure is the Disjunct Class Percentage (DCP), which is the number of data points in a disjunct that belong to a same class divided by the total number of examples in the disjunct. The Tree Depth (TD) returns the depth of the leaf node that classifies an instance in a decision tree. The previous measures give estimates from the perspective of a decision tree classifier. In addition, the Minority Value (MV) index is the ratio of examples sharing the same label of an example to the number of examples in the majority class. The Class Balance (CB) index presents an alternative to measuring the class skew. The C1 and C2 measures previously described are simple alternatives already able to capture the class imbalance aspect. BIB005 focus their study on the relationship between linear separability and the level of complexity of classification datasets. Their method uses Recursive Deterministic Perceptron (RDP) models and counts the number of hyperplanes needed to transform the original problem, which may not be linearly separable, into a linearly separable problem. In BIB004 , various class separability measures are presented, focusing on feature selection. Some parametric measures are the Mahalanobis and the Bhattacharyya distances between the classes and the Normal Information Radius. These measures are computationally intensive due to the need to compute covariance matrices and their inverse. An information theoretic measure is the Kullback-Leibler distance. It quantifies the discrepancy between two probability distributions. Based on discriminant analysis, a number of class separability measures can also be defined. This family of techniques is closely related to measures F1v and N2, discussed in this survey. Cummins (2013) also defines some alternative complexity measures. The first, named N5, consists of multiplying N1 by N2. According to , the multiplication of N1 and N2 emphasizes extreme behavior concerning class separability. Another measure (named Case Base Complexity Profile) retrieves the k nearest neighbors of an example x for increasing values of k, from 1 up to a limit K. At each round, the proportion of neighbors that have the same label as x is counted. The obtained values are then averaged. Although interesting, this measure can be considered quite costly to compute. More recently,  presented a complexity curve based on the Hellinger distance of probability distributions, assuming that the input features are independent. It takes subsets of different sizes from a dataset and verifies if their information content is similar to that of the original dataset. The computed values are plotted, and the area under the obtained curve is used as an estimate of data complexity. The proposed measure is also applied in data pruning. The measure values computed turned out to be quite correlated to T2. In the recent literature, there are also studies on generalizations of the complexity measures for other types of problems. In  , these measures are adapted to quantify the difficulty of regression problems.  present a complexity score for multi-label classification problems. BIB003 surveys some strategies for measuring the difficulty of optimization problems.