How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Fraction of Hyperspheres Covering Data (T1) <s> This article presents a pretopological approach for supervised learning, suited for the recognition of printed characters. This approach is an alternative to classic methods that use the "nearest neighbors rules" (NNR). We define a particular neighborhood which authorizes an optimal recovery of the training set in order to reduce the complexity of calculations during the recognition process. The number of neighborhoods does not depend on the size of training set but depend rather on the classes complexity. The degree of modelization wished is fixed by a parameter. For extreme values of this parameter, classes limits are near those deduced by the 1-NNR. This approach also allows to estimate the a priori substitution rate for each class and gives a good evaluation of the classes separability. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Fraction of Hyperspheres Covering Data (T1) <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
. This is regarded as a topological measure in Ho and BIB002 . It uses a process that builds hyperspheres centered at each one of the examples. The radius of each hypersphere is progressively increased until the hypersphere reaches an example of another class. Smaller hyperspheres contained in larger hyperspheres are eliminated. T1 is defined as the ratio between the number of the remaining hyperspheres and the total number of examples in the dataset: where Hyperspheres(T ) gives the number of hyperspheres that are needed to cover the dataset. The hyperspheres represent a form of adherence subsets as discussed in BIB001 . The idea is to obtain an adherence subset of maximum order for each example such that it includes only examples from the same class. Subsets that are completely included in other subsets are discarded. In principle, the adherence subsets can be of any form (e.g., hyperectangular), and hyperspheres are chosen in the definition of this measure, because it can be defined with relatively few parameters (i.e., only a center and a radius). Fewer hyperspheres are obtained for simpler datasets. This happens when data from the same class are densely distributed and close together. Herewith, this measure also captures the distribution of data within the classes and not only their distribution near the class boundary. In this article, we propose an alternative implementation of T1. It involves a modification of the definition to stop the growth of the hypersphere when the hyperspheres centered at two points of opposite classes just start to touch. With this modification, the radius of each hypersphere around an example can be directly determined based on distance matrix between all examples. The radius computation for an example x i is shown in Algorithm 1, in which the nearest enemy (ne) of an example corresponds to the nearest data point from an opposite class (ne (x i ) = N N (x i ) ∈ y j y i ). If two points are mutually nearest enemies of each other (line 3 in Algorithm 1), the radiuses of their hyperspheres correspond to half of the distance between them (lines 4 and 5; see also Figure 10 (a)). The radiuses of the hyperspheres around other examples can be determined recursively (lines 7 and 8), as illustrated in Figure 10  Once the radiuses of all hyperspheres are found, a post-processing step can be applied to verify which hyperspheres are absorbed: those lying inside larger hyperspheres. The hyperspheres obtained for our example dataset is shown in Figure 10 (c). The most demanding operation in T1 is to compute the distance matrix between all the examples in the dataset, which requires O (m · n 2 ) operations. , the Local-Set (LS) of an example x i in a dataset (T ) is defined as the set of points from T whose distance to x i is smaller than the distance from x i to x i 's nearest enemy (Equation (28)).