How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> CONCLUSION <s> Instance-based learning techniques typically handle continuous and linear input values well, but often do not handle nominal input attributes appropriately. The Value Difference Metric (VDM) was designed to find reasonable distance values between nominal attribute values, but it largely ignores continuous attributes, requiring discretization to map continuous values into nominal values. This paper proposes three new heterogeneous distance functions, called the Heterogeneous Value Difference Metric (HVDM), the Interpolated Value Difference Metric (IVDM), and the Windowed Value Difference Metric (WVDM). These new distance functions are designed to handle applications with nominal attributes, continuous attributes, or both. In experiments on 48 applications the new distance metrics achieve higher classification accuracy on average than three previous distance functions on those datasets that have both nominal and continuous attributes. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> CONCLUSION <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> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> CONCLUSION <s> Thank you very much for downloading perceptrons an introduction to computational geometry. As you may know, people have search numerous times for their chosen books like this perceptrons an introduction to computational geometry, but end up in malicious downloads. Rather than reading a good book with a cup of coffee in the afternoon, instead they are facing with some harmful virus inside their laptop. <s> BIB003
This article reviewed the main data complexity measures from the literature. These indices allow to characterize the difficulty of a classification problem from the perspectives of data geometry and distribution within or across the classes. They were first proposed and analyzed in Ho and BIB002 and have since been extensively used in the analysis and development of classification and pre-processing techniques. The original complexity measures and other measures found in related literature were briefly presented. Despite the presence of many methods for measuring the complexity of classification problems, they often share similar concepts. There has not been a study comparing them to reveal which ones can extract more distinct aspects regarding data complexity. Besides the characteristics of each individual measure highlighted alongside their definitions, we present next some general discussions about each category of complexity measures. In the case of the feature-based complexity measures, there is an expectation that each feature has a certain contribution to the discrimination task, and that the axis representing the feature can be interpreted as it is. This is more likely to be true for problems where the features are meaningful explanatory variables each contributing somewhat independently to the classification. It is particularly less likely to be true in classification problems where sensory signals are directly ACM Computing Surveys, Vol. 52, No. 5, Article 107. Publication date: September 2019. taken as input, such as pixel values in images, where a natural unit of discriminatory information tends to involve a larger group of features (such as a patch of colors displayed over multiple pixels). For those cases, transformation of the raw feature values, such as by a directional vector projection, becomes essential. The second issue is that as we examine the overlap of the feature value ranges, there is an expectation that the unseen values in an interval that spans the seen values contribute to the discrimination task in a similar way as the seen values, i.e., there is continuity in the class definition w.r.t. that feature. This tends to be true for features in a continuous numerical scale, and is less likely for other cases. For categorical features, the notion of value ranges degenerates into specific values, and several measures in this family have difficulties. The measures in the linearity family focus on the perspective of linear separability, which has a long history of being used as a characterization of classification difficulty. It was involved in the early debates of the limits of a certain classifier's capabilities (e.g., the debate on the perceptron in BIB003 ). One issue of concern is that linear separability is often characteristic of sparse data sets-consider the extreme case where only one training point is available from each class in an arbitrary classification problem, and in that case linear separability of the training data does not give much information about the nature of the underlying task. Sparse datasets in high-dimensional space are also likely to be linearly separable (see, for example, Costa et al. (2009)), which motivates techniques like SVMs that use a feature transformation to map the data to a highdimensional space where simple linear classifiers suffice. The interactive effects of this type of measure with data size, data density, and dimensionality are illustrative of the challenges involved in data complexity discussions. Therefore, the complexity evaluations need to be anchored first on fixed datasets and followed by discussions of changes in responses to the other influences. Measures in this neighborhood-based family characterize the datasets in ways different from those of the feature-based family and the linearity-based family. They use a distance function to summarize the relationship between points. This is best fitted for datasets where the features are on a comparable scale (e.g., per-pixel intensity values) such that a natural metric exists. For datasets that involve features of heterogeneous types and scales, a scale-normalization step or a suitable weighting scheme is needed for a summarizing metric to be properly defined. The usefulness of the measures depends critically on whether such a metric can be obtained. The Gower distance metric employed in ECol is a simple alternative for dealing with features of different types and scales, but more sophisticated distance functions could be used instead BIB001 . In addition, since these measures are influenced by within-class data distributions as well as by the data distributions near the class boundaries, the information they convey may include more than what is relevant to the discrimination task, which may cause drown-out of the critical signal about classification complexity. The network-based measures regard on the structure of the data in the input space. They may complement the previous measures presented, although they also consider the neighborhood of examples for obtaining the graph representation. It should be noticed that a number of other complex network measures can be extracted from the graph built, as well as other strategies can be used to obtain the graph representation. The strategy chosen to build the graph from a learning dataset considers both the proximity of the examples (ϵ-NN) and the data label information (pruning step). Herewith, we expect to get an overview of both intra-and inter-class relationships. All measures from the dimensionality group rely only on the numbers of examples and features in a dataset, disregarding the label information. Therefore, they do not give any indicative of boundary complexity, but rather give a very simplified and naïve overview on data sparsity. As discussed in the article introduction, data sparsity is one of the factors that may affect the complexity of a classification problem. Indeed, datasets with a high dimensionality and a low number of examples tend to be distributed sparsely. In many cases, this can make the classification problem look simpler than it really is, so simple classification models may not generalize well to new data points that occupy regions formerly underrepresented in the training dataset. The measures of the class imbalance category regard on the number of examples per class. As in the case of the dimensionality measures, they do not allow to directly estimate the complexity of the classification boundary. Rather, they regard on another aspect that may influence the performance of many ML classification techniques, which is the underrepresentation of one or more classes in relation to others. This work also provides an R package with an implementation of a set of 22 complexity measures from the previous categories. The package is expected to give interested researchers a quick start into the field. An immediate line of follow-up work is to evaluate these measures empirically and try to: (i) identify those measures with most distinct concepts, since many of them have similar computation; and (ii) compare their ability in revealing the complexity of a diverse set of classification problems. This type of investigation is expected to yield a reduced subset of core measures able to capture the most critical aspects of classification complexity. Last, the main use cases where the measures have been applied were presented. The most common use of the measures is to characterize datasets in meta-learning studies or the domain of competence of learning and pre-processing techniques. Nonetheless, more contributions remain possible in employing the conclusions of these studies to adapt and propose new learning and preprocessing techniques. For instance, relatively few works have been done in devising new learning schemes and pre-processing techniques based on the complexity measures. This points to the potential of these measures that remain poorly explored. We believe that a better understanding of the characteristics of a given problem shall be the key to support the design of techniques with better predictive results. Another direction that awaits to be better explored is how one can use the complexity measures to evaluate different formulations of a problem, in terms of how classes are defined or chosen, in domains where there is flexibility in such choices. An example is a text categorization task, where one may have some limited freedom to choose what is to be considered a category. Better choices can lead to lower error rates even if the classifier technology stays the same. Here the data complexity measures can serve as figures of merit to evaluate alternative class definitions.