How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Data Pre-proprocessing <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> Data Pre-proprocessing <s> We use several data complexity measures to explain the differences in classification accuracy using various sets of features selected from samples of magnetic resonance spectra for two-class discrimination. Results suggest that for this typical problem with sparse samples in a high-dimensional space, even robust classifiers like random decision forests can benefit from sophisticated feature selection procedures, and the improvement can be explained by the more favorable characteristics in the class geometry given by the resultant feature sets. <s> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Data Pre-proprocessing <s> With the continuous expansion of data availability in many large-scale, complex, and networked systems, such as surveillance, security, Internet, and finance, it becomes critical to advance the fundamental understanding of knowledge discovery and analysis from raw data to support decision-making processes. Although existing knowledge discovery and data engineering techniques have shown great success in many real-world applications, the problem of learning from imbalanced data (the imbalanced learning problem) is a relatively new challenge that has attracted growing attention from both academia and industry. The imbalanced learning problem is concerned with the performance of learning algorithms in the presence of underrepresented data and severe class distribution skews. Due to the inherent complex characteristics of imbalanced data sets, learning from such data requires new understandings, principles, algorithms, and tools to transform vast amounts of raw data efficiently into information and knowledge representation. In this paper, we provide a comprehensive review of the development of research in learning from imbalanced data. Our focus is to provide a critical review of the nature of the problem, the state-of-the-art technologies, and the current assessment metrics used to evaluate learning performance under the imbalanced learning scenario. Furthermore, in order to stimulate future research in this field, we also highlight the major opportunities and challenges, as well as potential important research directions for learning from imbalanced data. <s> BIB003 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Data Pre-proprocessing <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> Data Pre-proprocessing <s> We present what is, to the best of our knowledge, the first analysis that uses dataset complexity measures to evaluate case base editing algorithms. We select three different complexity measures and use them to evaluate eight case base editing algorithms. While we might expect the complexity of a case base to decrease, or stay the same, and the classification accuracy to increase, or stay the same, after maintenance, we find many counter-examples. In particular, we find that the RENN noise reduction algorithm may be over-simplifying class boundaries. <s> BIB005 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Data Pre-proprocessing <s> Classification is an important task in data mining. Class imbalance has been reported to hinder the performance of standard classification models. However, our study shows that class imbalance may not be the only cause to blame for poor performance. Rather, the underlying complexity of the problem may play a more fundamental role. In this paper, a decision tree method based on Kolmogorov-Smirnov statistic (K-S tree), is proposed to segment the training data so that a complex problem can be divided into several easier sub-problems where class imbalance becomes less challenging. K-S tree is also used to perform feature selection, which not only selects relevant variables but also removes redundant ones. After segmentation, a two-way re-sampling method is used at the segment level to empirically determine the optimal sampling percentage and the rebalanced data is used to fit logistic regression models, also at the segment level. The effectiveness of the proposed method is demonstrated through its application on property refinance prediction. <s> BIB006 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Data Pre-proprocessing <s> Label noise is an important issue in classification, with many potential negative consequences. For example, the accuracy of predictions may decrease, whereas the complexity of inferred models and the number of necessary training samples may increase. Many works in the literature have been devoted to the study of label noise and the development of techniques to deal with label noise. However, the field lacks a comprehensive survey on the different types of label noise, their consequences and the algorithms that consider label noise. This paper proposes to fill this gap. First, the definitions and sources of label noise are considered and a taxonomy of the types of label noise is proposed. Second, the potential consequences of label noise are discussed. Third, label noise-robust, label noise cleansing, and label noise-tolerant algorithms are reviewed. For each category of approaches, a short discussion is proposed to help the practitioner to choose the most suitable technique in its own particular field of application. Eventually, the design of experiments is also discussed, what may interest the researchers who would like to test their own algorithms. In this paper, label noise consists of mislabeled instances: no additional information is assumed to be available like e.g., confidences on labels. <s> BIB007
The data complexity measures have also been used to guide data pre-processing tasks, such as Feature Selection (FS)  , noise identification BIB007 , and dealing with data imbalance BIB003 ). In FS, the measures have been used to both guide the search for the best featues in a dataset BIB001 or to understand feature selection effects BIB002 BIB004 . For instance, propose to quantify whether FS effectively changes the complexity of the original classification problem. They found that FS was able to increase class separability in the reduced spaces, as measured by N1, N2, and T1. assert the power of some complexity measures in ranking the features contained in synthetic datasets for which the relevant features are known a priori. As expected, feature-based measures (mainly F1) are very effective in revealing the relevant features in a dataset, although some neighborhood measures (N1 and N2) also present highlighted results. Another interesting recent work on feature selection uses a combination of the feature-based complexity measures F1, F2, and F3 to support the choice of thresholds in the number of features to be selected by FS algorithms . Instance (or prototype) selection (IS) has also been the theme of various works involving the data complexity measures. In one of the first works in the area, tries to predict which instance selection algorithm should be applied to a new dataset. They report highlighted results of the F1 measure in identifying situations in which an IS technique is needed. Other works include: and BIB005 . , for instance, presents some complexity measures that are claimed to be specifically designed for characterizing IS problems. Among them is the LCS measure. perform a different analysis. They are interested in investigating whether the complexity measures can be calculated at reduced datasets while still preserving the characteristics found in the original datasets. Only separability-measures are considered, among them F1, F2, F3, and N2. The results were positive for all measures, except for F1. Under his partitioning framework, BIB001 discusses how potential outliers can be identified in a dataset. Other uses of the complexity measures in the noise identification context are: , . , for example, investigate how different label noise levels affect the values of the complexity measures. Neighborhood-based (N1, N2, and N3), feature-based (F1 and F3), and some network-based measures (density and hubs) were found to be effective in capturing the presence of label noise in classification datasets. Two of the measures most sensitive to noise imputation were then combined to develop a new noise filter, named GraphNN. BIB006 found that the data complexity of a classification problem is more determinant in model performance than class imbalance, and that class imbalance amplifies the effects of data complexity. adapted the back-propagation (BP) algorithm to take into account the class overlap and the imbalance ratio of a dataset using the F1 feature-based measure and the imbalance-ratio for binary problems. use the F1 measure to analyze the differences between pre-processing techniques and cost-sensitive learning for addressing imbalanced data classification. Other works in the analysis of imbalanced classification problems include , , , and . More discussions on the effectiveness of data complexity analysis related to the data imbalance theme can be found in .