How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Maximum Fisher's Discriminant <s> A method for identifying clusters of points in a multidimensional Euclidean space is described and its application to taxonomy considered. It reconciles, in a sense, two different approaches to the investigation of the spatial relationships between the points, viz., the agglomerative and the divisive methods. A graph, the shortest dendrite of Florek etal. (1951a), is constructed on a nearest neighbour basis and then divided into clusters by applying the criterion of minimum within cluster sum of squares. This procedure ensures an effective reduction of the number of possible splits. The method may be applied to a dichotomous division, but is perfectly suitable also for a global division into any number of clusters. An informal indicator of the "best number" of clusters is suggested. It is a"variance ratio criterion" giving some insight into the structure of the points. The method is illustrated by three examples, one of which is original. The results obtained by the dendrite method are compared with those... <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Maximum Fisher's Discriminant <s> This paper proposes further generalization of a multiclass Fisher's criterion. A formula describing the dependence between the generalized multiclass Fisher's criterion F/sub /spl Theta// and the variance criterion F/sub v//spl Theta/ has been obtained. Using this formula, it has been shown that the feature extraction methods based on the Karhunen-Loeve (K-L) expansions are special cases of the discriminant method. A full evaluation of heuristic methods for feature extraction based on the K-L expansion with regard to discriminant methods has been presented. A new algorithm for sequential feature extraction has been proposed and is illustrated with an example. <s> BIB002 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Maximum Fisher's Discriminant <s> Feature selection plays an important role in pattern recognition and machine learning. Feature evaluation and classification complexity estimation arise as key issues in the construction of selection algorithms. To estimate classification complexity in different feature subspaces, a novel feature evaluation measure, called the neighborhood decision error rate (NDER), is proposed, which is applicable to both categorical and numerical features. We first introduce a neighborhood rough-set model to divide the sample set into decision positive regions and decision boundary regions. Then, the samples that fall within decision boundary regions are further grouped into recognizable and misclassified subsets based on class probabilities that occur in neighborhoods. The percentage of misclassified samples is viewed as the estimate of classification complexity of the corresponding feature subspaces. We present a forward greedy strategy for searching the feature subset, which minimizes the NDER and, correspondingly, minimizes the classification complexity of the selected feature subset. Both theoretical and experimental comparison with other feature selection algorithms shows that the proposed algorithm is effective for discrete and continuous features, as well as their mixture. <s> BIB003
where r f i is a discriminant ratio for each feature f i . Originally, F1 takes the value of the largest discriminant ratio among all the available features. This is consistent with the definition that if at least one feature discriminates the classes, the dataset can be considered simpler than if no such attribute exists. In this article, we take the inverse of the original F1 formulation into account, as presented in Equation (1). Herewith, the F1 values become bounded in the (0, 1] interval and higher values indicate more complex problems, where no individual feature is able to discriminate the classes. present different equations for calculating r f i , depending on the number of classes or whether the features are continuous or ordinal  . One straightforward formulation is: where p c j is the proportion of examples in class c j , μ f i c j is the mean of feature f i across examples of class c j , and σ f i c j is the standard deviation of such values. An alternative for r f i computation that can be employed for both binary and multiclass classification problems is given in . Here, we adopt this formulation, which is similar to the clustering validation index from BIB001 : where n c j is the number of examples in class c j , μ f i c j is the same as defined for Equation (2), μ f i is the mean of the f i values across all the classes, and x j li denotes the individual value of the feature f i for an example from class c j . Taking, for instance, the dataset shown in Figure 1 , the most discriminative feature would be f 1 . F1 correctly indicates that the classes can be easily separable using this feature. Feature f 2 , however, is non-discriminative, since its values for the two classes overlap with the same mean and variance. ACM Computing Surveys, Vol. 52, No. 5, Article 107. Publication date: September 2019. The denominator in Equation (3) must go through all examples in the dataset. The numerator goes through the classes. Since the discriminant ratio must be computed for all features, the total asymptotic cost for the F1 computation is O (m · (n + n c )). As n ≥ n c (there is at least one example per class), O (m · (n + n c )) can be reduced to O (m · n). Roughly, the F1 measure computes the ratio of inter-class to the intra-class scatter for each feature. Using the formulation in Equation (1), low values of the F1 measure indicate that there is at least one feature whose values show little overlap among the different classes; that is, it indicates the existence of a feature for which a hyperplane perpendicular to its axis can separate the classes fairly. Nonetheless, if the required hyperplane is oblique to the feature axes, F1 may not be able to reflect the underlying simplicity. To deal with this issue, propose to use a F1 variant based on a Directional Vector, to be discussed next. Finally, BIB003 note that the F1 measure is most effective if the probability distributions of the classes are approximately normal, which is not always true. On the contrary, there can be highly separable classes, such as those distributed on the surfaces of two concentric hyperspheres, that would yield a very high value for F1. . This measure is used in as a complement to F1. It searches for a vector that can separate the two classes after the examples have been projected into it and considers a directional Fisher criterion defined in BIB002 as: