How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Local Set Average Cardinality (LSC). According to <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> Local Set Average Cardinality (LSC). According to <s> In the past decade, the study of networks has increased dramatically. Researchers from across the sciencesincluding biology and bioinformatics, computer science, economics, engineering, mathematics, physics, sociology, and statisticsare more and more involved with the collection and statistical analysis of network-indexed data. As a result, statistical methods and models are being developed in this area at a furious pace, with contributions coming from a wide spectrum of disciplines. This book provides an up-to-date treatment of the foundations common to the statistical analysis of network data across the disciplines. The material is organized according to a statistical taxonomy, although the presentation entails a conscious balance of concepts versus mathematics. In addition, the examplesincluding extended cases studiesare drawn widely from the literature. This book should be of substantial interest both to statisticians and to anyone else working in the area of network science. The coverage of topics in this book is broad, but unfolds in a systematic manner, moving from descriptive (or exploratory) methods, to sampling, to modeling and inference. Specific topics include network mapping, characterization of network structure, network sampling, and the modeling, inference, and prediction of networks, network processes, and network flows. This book is the first such resource to present material on all of these core topics in one place. <s> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Local Set Average Cardinality (LSC). According to <s> This paper investigates the adoption of measures used to evaluate complex networks properties in the characterization of the complexity of data sets in machine learning applications. These measures are obtained from a graph based representation of a data set. A graph representation has several interesting properties as it can encode local neighborhood relations, as well as global characteristics of the data. These measures are evaluated in a meta-learning framework, where the objective is to predict which classifier will have better performance in a given task, in a pair wise basis comparison, based on the complexity measures. Results were compared to traditional data set complexity characterization metrics, and shown the competitiveness of the proposed measures derived from the graph representation when compared to traditional complexity characterization metrics. <s> BIB003
where ne (x i ) is the nearest enemy from example x i . Figure 11 illustrates the local set of a particular example (x, in gray) in a dataset. The cardinality of the LS of an example indicates its proximity to the decision boundary and also the narrowness of the gap between the classes. Therefore, the LS cardinality will be lower for examples separated from the other class with a narrow margin. According to , a high number of low-cardinality local sets in a dataset suggests that the space between classes Require: A distance matrix D nxn , a label vector y, a data index i; 1: is narrow and irregular; that is, the boundary is more complex. The local set average cardinality measure (LSC) is calculated here as: where |LS (x i )| is the cardinality of the local set for example x i . This measure can complement N1 and L1 by also revealing the narrowness of the between-class margin. Higher values are expected for more complex datasets, in which each example is nearest to an enemy than to other examples from the same class. In that case, each example will have a local set of cardinality 1, resulting in a LSC of 1 − 1 n . The asymptotic cost of LSC is dominated by the computation of pairwise distances between all examples, resulting in O (m · n 2 ) operations. BIB003 and model the dataset as a graph and extract measures for the statistical characterization of complex networks BIB002 ) from this representation. In low correlation values were observed between the basic complexity measures of Ho and BIB001 and the graph-based measures, which supports the relevance of exploring this alternative representation of the data structure. In this article, we highlight the best measures for the data complexity induced by label noise imputation ), with an emphasis on those with low correlation between each other.