How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Measures of Linearity <s> Abstract—A common nonparametric method for designing linear discriminant functions for pattern classification is the iterative, or "adaptive," weight adjustment procedure, which designs the discriminant function to do well on a set of typical patterns. This paper presents a linear programming formulation of discriminant function design which minimizes the same objective function as the "fixed-increment" adaptive method. With this formulation, as with the adaptive methods, weights which tend to minimize the number of classification errors are computed for both separable and nonseparable pattern sets, and not just for separable pattern sets as has been the emphasis in previous linear programming formulations. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Measures of Linearity <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
These measures try to quantify to what extent the classes are linearly separable; that is, if it is possible to separate the classes by a hyperplane. They are motivated by the assumption that a linearly separable problem can be considered simpler than a problem requiring a non-linear decision boundary. To obtain the linear classifier, Ho and BIB002 suggest to solve an optimization problem proposed by BIB001  Subject to: where C is the trade-off between the margin maximization, achieved by minimizing the norm of w, and the minimization of the training errors, modeled by ε. The hyperplane is given by w · x + b = 0, where w is a weight vector and b is an offset value. SVMs are originally proposed to solve binary classification problems with numerical features. Therefore, symbolic features must be converted into numerical values and multiclass problems must first be decomposed. (L1) . This measure assesses if the data are linearly separable by computing, for a dataset, the sum of the distances of incorrectly classified examples to a linear boundary used in their classification. If the value of L1 is zero, then the problem is linearly separable and can be considered simpler than a problem for which a non-linear boundary is required.