How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Learning Algorithms <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> Learning Algorithms <s> The constant appearance of algorithms and problems in data mining makes impossible to know in advance whether the model will perform well or poorly until it is applied, which can be costly. It would be useful to have a procedure that indicates, prior to the application of the learning algorithm and without needing a comparison with other methods, whether the outcome will be good or bad using the information available in the data. In this work, we present an automatic extraction method to determine the domains of competence of a classifier using a set of data complexity measures proposed for the task of classification. These domains codify the characteristics of the problems that are suitable or not for it, relating the concepts of data geometrical structures that may be difficult and the final accuracy obtained by any classifier. In order to do so, this proposal uses 12 metrics of data complexity acting over a large benchmark of datasets in order to analyze the behavior patterns of the method, obtaining intervals of data complexity measures with good or bad performance. As a representative for classifiers to analyze the proposal, three classical but different algorithms are used: C4.5, SVM and K-NN. From these intervals, two simple rules that describe the good or bad behaviors of the classifiers mentioned each are obtained, allowing the user to characterize the response quality of the methods from a dataset's complexity. These two rules have been validated using fresh problems, showing that they are general and accurate. Thus, it can be established when the classifier will perform well or poorly prior to its application. <s> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Learning Algorithms <s> Website fingerprinting attack can identify the visited websites by analyzing the side-channel information of the network traffic even though it is transferred through an encrypted tunnel. The security of web browsing can be evaluated by quantifying the side-channel information leaks. However, most of the current leak quantification measures focus on web applications and may be impractical in web browsing due to their time complexity. Although the revised models were proposed to simplify computations, their assumptions may not be suitable for web browsing. In this paper, the problem of website fingerprinting is analyzed from the viewpoint of pattern classification. The data complexity measures, which quantify the difficulty of separating classes in a classification problem, are applied to describe the leak quantification. The performance of these data complexity measures in representing information leaks is discussed and compared with the existing approaches. This comparative analysis is realized conceptually and through experiments by using two website fingerprinting countermeasures: traffic morphing and BuFLO. Moreover, the parameter selection model based on the leak quantification is proposed to estimate suitable parameters for the website fingerprinting countermeasure. The experimental results confirm that the countermeasures with parameters selected according to the data complexity measures are more secure than other leak quantification measures. <s> BIB003 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Learning Algorithms <s> It is noted that the rank of input data matrix has a critical impact on the performance of a trained classifier model. This paper presents a study on the rank of input data matrix based on a classification model of extreme learning machine which is a single hidden layer feed-forward neural network with non-iterative training. The changing tendency of model accuracy with the increase of input data matrix rank is experimentally investigated and the relationship between the input matrix rank and classification problem complexity is addressed. The analysis and experiments show some meaningful results. <s> BIB004
Data complexity measures can also be employed for analysis at the level of algorithms. These analyses can be for devising, tuning or understanding the behavior of different learning algorithms. For instance, BIB004 use the complexity measures to understand the data transformations performed by Extreme Learning Machines at each of their layers. They have noticed some small changes in the complexity as measured by F1, F3, and N2, which were regarded as non-significant. A very popular use of the data complexity measures is to outline the domains of competence of one or more ML algorithms BIB002 . This type of analysis allows to identify problem characteristics for which a given technique will probably succeed or fail. While improving the understanding of the capabilities and limitations of each technique, it also supports the choice of a particular technique for solving a new problem. It is possible to reformulate a learning procedure by taking into account the complexity measures, too, or to devise new ML and pre-processing techniques. In the analysis of the domains of competence of algorithms, one can cite: Ho (2000, 2002) for random decision forests; Bernadó-Mansilla and Ho (2005) for the XCS classifier; Ho and Bernadó-Mansilla (2006) for NN, Linear Classifier, Decision Tree, Subspace Decision Forest, and Subsample Decision Forest; for finding datasets that fit for a semi-naive Bayesian Network Classifier (BNC) and to recommend the best semi-naive BNC to use for a new dataset; for a Genetic Programming classifier; for incremental learning algorithms; ; Garcia-Piquer et al. (2012) for CBR; for the Dynamic Selection (DS) of classifiers. In BIB002 , a general automatic method for extracting the domains of competence of any ML classifier is proposed. This is done by monitoring the values of the data complexity measures and relating them to the difference in the training and testing accuracies of the classifiers. Rules are extracted from the measures to identify when the classifiers will achieve a good or bad accuracy performance. The knowledge advent from the problem complexity analysis can also be used for improving the design of existent ML techniques. For instance, propose a modification of the back-propagation algorithm for training Artificial Neural Networks (ANNs) that embed their concept of instance hardness. Therein, the error function of the BP algorithm places more emphasis on the hard instances. Other works along this line include: , also on NN, using the measures F1 and imbalance ratio; Campos et al. (2012) in DT ensembles, using the N1 and F4 measures. Recently, Brun et al. (2018) proposed a framework for dynamic classifier selection in ensembles. It uses a subset of the complexity measures for both: selecting subsets of instances to train the pool of classifiers that compose the ensemble; and to determine the predictions that will be used for a given subproblem, which will favor classifiers trained on subproblems of similar complexity to the query subproblem. They have selected one measure from each of the Ho and BIB001 's original categories, which showed low Pearson correlation with each other to be optimized by a GA suited for DS: F1, N2, and N4. However, some works have devised new approaches for data classification based on the information of the complexity measures. This is the case of  , in which the measures F1 and F2 are used as splitting criteria for decomposing multiclass problems. Quiterio and  also work on the decomposition of multiclass problems, using the complexity measures to place the binary classifiers in Directed Acyclic Graph structures. No specific complexity measure among those tested in the paper (namely, F1, F3, N1, N2, and T1) could be regarded as best suited for optimizing the DAG structures, although all of them were suitable choices for evaluating the binary classifiers. perform hierarchical partitions of the classes minimizing classification complexity, which are estimated according to the measures F1, F2, F3, N2, N3 and a new measure based on centroids introduced in their work. The best experimental results were obtained for the measures F1, F3, and centroid-based. Another task that can be supported by the estimates on problem complexity is to tune the parameters of the ML techniques for a given problem. In BIB003 , the data complexity measures are applied to describe the leak quantification problem. They employ one representative measure of each of the Ho and Basu (2002)'s categories: F2, N1, and T1. In addition, a parameter-tuning procedure that minimizes data complexity under some domain-specific constraints is proposed. Measures N1 and T1 achieved better results. use the complexity measures to specify the parameter values of fuzzy classifiers. Some decision rules for binary classification problems based on measures F4, L1, L2, N1, and T2 are reported. N4 is also mentioned as a key measure in the case of multiclass problems.