The use of nonparametric error estimates may lead to biased results if the kernel covariances are estimated from the same data as are used to form the error estimate. If additional design samples are available, one may eliminate this bias by estimating the class covariances using an independent set of data. If, however, additional samples are not available, one may resort to leave-one-out type estimates of the kernel (for Parzen estimates) or metric (for nearest-neighbor estimates) for every sample being tested. The authors present an efficient algorithm for computation of these leave-one-out type estimates that requires little additional computational burden over procedures currently in use. The presentation is applicable to both Parzen and k-nearest neighbor (k-NN) type estimates. Experimental results demonstrating the efficiency of the algorithm are provided.>

The Parzen density estimate is known to be an effective tool for estimating the Bayes error, given a set of training samples from the class distributions. An algorithm is developed to select a given number of representative samples whose Parzen density estimate closely matches that of the entire sample set. Using this reduced representative set, a piecewise quadratic classifier which provides nearly optimal performance is designed.>

The effect of finite sample-size on parameter estimates and their subsequent use in a family of functions are discussed. General and parameter-specific expressions for the expected bias and variance of the functions are derived. These expressions are then applied to the Bhattacharyya distance and the analysis of the linear and quadratic classifiers, providing insight into the relationship between the number of features and the number of training samples. Because of the functional form of the expressions, an empirical approach is presented to enable asymptotic performance to be accurately estimated using a very small number of samples. Results were experimentally verified using artificial data in controlled cases and using real, high-dimensional data.>

An expression for expected classifier performance previously derived by the authors (ibid., vol.11, no.8, p.873-855, Aug. 1989) is applied to a variety of error estimation methods and a unified and comprehensive approach to the analysis of classifier performance is presented. After the error expression is introduced, it is applied to three cases: (1) a given classifier and a finite test set; (2) given test distributions a finite design set; and (3) finite and independent design and test sets. For all cases, the expected values and variances of the classifier errors are presented. Although the study of Case 1 does not produce any new results, it is important to confirm that the proposed approach produces the known results, and also to show how these results are modified when the design set becomes finite, as in Cases 2 and 3. The error expression is used to compute the bias between the leave-one-out and resubstitution errors for quadratic classifiers. The effect of outliers in design samples on the classification error is discussed. Finally, the theoretical analysis of the bootstrap method is presented for quadratic classifiers.>

The bias of the finite-sample nearest neighbor (NN) error from its asymptotic value is examined. Expressions are obtained which relate the bias of the NN and 2-NN errors to sample size, dimensionality, metric, and distributions. These expressions isolate the effect of sample size from that of the distributions, giving an explicit relation showing how the bias changes as the sample size is increased. Experimental results are given which suggest that the expressions accurately predict the bias. It is shown that when the dimensionality of the data is high, it may not be possible to estimate the asymptotic error simply by increasing the sample size. A new procedure is suggested to alleviate this problem. This procedure involves measuring the mean NN errors at several sample sizes and using our derived relationship between the bias and the sample size to extrapolate an estimate of the asymptotic NN error. The results are extended to the multiclass problem. The choice of an optimal metric to minimize the bias is also discussed.

The use of k nearest neighbor (k-NN) and Parzen density estimates to obtain estimates of the Bayes error is investigated under limited design set conditions. By drawing analogies between the k-NN and Parzen procedures, new procedures are suggested, and experimental results are given which indicate that these procedures yield a significant improvement over the conventional k-NN and Parzen procedures. We show that, by varying the decision threshold, many of the biases associated with the k-NN or Parzen density estimates may be compensated, and successful error estimation may be performed in spite of these biases. Experimental results are given which demonstrate the effect of kernel size and shape (Parzen), the size of k (k-NN), and the number of samples in the design set.

The properties of the ``magnifying glass'' method of clustering are discussed. These properties, which include unbiased and consistent estimation of the mean for Gaussian distributions and biased and inconsistent estimation of the mean for non-Gaussian distributions, lead to the development of a technique for testing data to determine whether or not it is Gaussian. An example of a non-Gaussian distribution is given to show the sensitivity of the proposed Gaussian test.

By proper design of a nearest-neighbor (NN) rule, it is possible to reduce effects of sample size in NN risk estimation. The 2-NN rule for the two-class problem eliminates the first-order effects of sample size. Since its asymptotic value is exactly half that of the 1-NN rule, it is possible to substitute the 2-NN rule for the 1-NN rule with a resultant increase in accuracy. For further stabilization of the risk estimate with respect to sample size, 2-NN polarization is suggested. Examples are included. The 2-NN approach is extended to M-class and 2k-NN.

A quadratic metric dAO (X, Y) =[(X - Y)T AO(X - Y)]¿ is proposed which minimizes the mean-squared error between the nearest neighbor asymptotic risk and the finite sample risk. Under linearity assumptions, a heuristic argument is given which indicates that this metric produces lower mean-squared error than the Euclidean metric. A nonparametric estimate of Ao is developed. If samples appear to come from a Gaussian mixture, an alternative, parametrically directed distance measure is suggested for nearness decisions within a limited region of space. Examples of some two-class Gaussian mixture distributions are included.

Classification error is analyzed for a situation where the number of possible classes may be on the order of a hundred or more. The error associated with classifying to a single class is shown to depend mainly on average nearest-neighbor distance between class means, noise level, and effective dimensionality of the class mean distribution and not much on other aspects of the distribution, noise correlation, or number of classes. Since single class error is large, separation of classes into groups is also explored. Group classification error has the same properties as single class error but the size of the error is moderated by the Bayes overlap between groups. Standard curves are provided to predict single class and group error. Also discussed are the effect of pattern blurring on classification error and the nearest-neighbor distance statistics throughout a distribution.

A nonparametric data reduction technique is proposed. Its goal is to select samples that are ``representative'' of the entire data set. The technique is iterative and is based on the use of a criterion function and nearest neighbor density estimates. Experiments are presented to demonstrate the algorithm.

A number of properties of separable covariance matrices are summarized. Expressions for the divergence of the corresponding two-dimensional Gaussian random processes are given in terms of row and column covariance matrices, and in terms of linear prediction parameters and maximum likelihood spectral estimates. Such time and frequency domain expressions are not widely known, even for one-dimensional random processes.

Given a general n-dimensional bimodal Gaussian mixture, this paper shows how unknown parameters may be found by the method of moments. Three cases are considered-equal modal probabilities, known but not necessarily equal probabilities, and all parameters unknown. The solution involves sample moments no higher than fourth order. For Gaussian mixtures where the number of modes is unknown, fourth-order moments can be used to count them, provided all modes have the same covariance matrix, and their multiplicity is not greater than data dimensionality. Examples of mode-counting and the determination of bimodal parameters are included.

A nonparametric method of discriminant analysis is proposed. It is based on nonparametric extensions of commonly used scatter matrices. Two advantages result from the use of the proposed nonparametric scatter matrices. First, they are generally of full rank. This provides the ability to specify the number of extracted features desired. This is in contrast to parametric discriminant analysis, which for an L class problem typically can determine at most L 1 features. Second, the nonparametric nature of the scatter matrices allows the procedure to work well even for non-Gaussian data sets. Using the same basic framework, a procedure is proposed to test the structural similarity of two distributions. The procedure works in high-dimensional space. It specifies a linear decomposition of the original data space in which a relative indication of dissimilarity along each new basis vector is provided. The nonparametric scatter matrices are also used to derive a clustering procedure, which is recognized as a k-nearest neighbor version of the nonparametric valley seeking algorithm. The form which results provides a unified view of the parametric nearest mean reclassification algorithm and the nonparametric valley seeking algorithm.

A systematic feature extraction procedure is proposed. It is based on successive extractions of features. At each stage a dimensionality reduction is made and a new feature is extracted. A specific example is given using the Gaussian minus-log-likelihood ratio as a basis for the extracted features. This form has the advantage that if both classes are Gaussianly distributed, only a single feature, the sufficient statistic, is extracted. If the classes are not Gaussianly distributed, additional features are extracted in an effort to improve the classification performance. Two examples are presented to demonstrate the performance of the procedure.

A two-dimensional display whose coordinates are related to the distance to the kth-nearest neighbor of each class is presented. Applications of the display to minimum error, minimum cost, minimax, and Neyman-Pearson type classifier designs are given. The display is shown to present risk information in a manner that easily allows the specification of reject regions. Two methods of error estimation using the display, an error counting technique and a risk averaging method, are detailed. It is shown that the classifiers that result are generalizations of the standard k-NN majority vote classifier. As a result of the properties of the display, classifiers can be readily evaluated and modified. In addition, a condensing algorithm that preserves the nearest neighbor error count of any preclassified data set is described. The display is used to graphically illustrate the distance relationships that are central to the algorithm.

Feature extraction is considered as a mean-quare estimation of the Bayes risk vector. The problem is simplified by partitioning the distribution space into local subregions and performing a linear estimation in each subregion. A modified clustering algorithm is used to fimd the partitioning which minimizes the mean-square error.

The three-dimensional shape analysis problem is a very demanding test of shape analysis algorithms. Previous approaches to the problem have employed global features such as moments and Fourier descriptors. Global features lack the capacity for solving the partial shape recognition problem, in which only part of the unknown shape is available. Previous approaches to local shape analysis have employed structural (syntactic) methods, but these methods have so far failed to solve the three-dimensional problem. This paper describes a hybrid structural/statistical local shape analysis algorithm which is applied to the three-dimensional problem.

A local distance measure is shown to optimize the performance of the nearest neighbor two-class classifier for a finite number of samples. The difference between the finite sample error and the asymptotic error is used as the criterion of improvement. This new distance measure is compared to the well-known Euclidean distance. An algorithm for practical implementation is introduced. This algorithm is shown to be computationally competitive with the present nearest neighbor procedures and is illustrated experimentally. A closed form for the corresponding second-order moment of this criterion is found. Finally, the above results are extended to

Feature extraction criteria of the formf(D_{l}, \cdots ,D_{M},\Sigma_{1}, \cdots , \Sigma_{M})are considered whereD_{i}and\Sigma_{i}are the conditional means and covariances. The functionfis assumed to be invariant under nonsingular linear transformations and coordinate shifts. For the casef(D_{1},D_{2},\Sigma_{o}),fis shown to depend only upon the distance(D_{2}-D_{1})^{T} \Sigma_{o}^{-1}(D_{2}-D_{1})between classes. TheMclass case,f(D_{1}, \cdots ,D_{M}, \Sigma_{o}), is shown to depend upon the(M-1)M/2between-class distances(D_{j}-D_{k})^{T} \Sigma^{-1}_{O}(D_{j}-D_{k}). This criterion is also shown to be equivalent to the mean-square-error of the general Bayes risk estimate. The most generalfis reduced to a function ofMsets of between-class distances with metrics induced by the conditional covariances. WhenM=2this dependence is reduced to two parameters which may be regarded as different between-class distance measures. Finally, the linear mapping is reduced to a one-parameter problem as in the work of Peterson and Mattson.

The general procedure of conventional clustering is modified for various applications involving problem localization. This modification introduces the concept of clustering criteria which are used for partitioning a training set, and depend upon certain a priori information with regards to the training set. Also, the need of a structure or a mathematical form for the partition boundaries arises naturally from the need to process unknown samples. The general procedure is discussed in detail for applications of piecewise linear classifier design and piecewise linear density estimation. Experimental results are presented for both applications.

The optimal nonlinear features for a criterion function of the general formf(D_{l},\cdots,D_{M},K_{1},\cdots,K_{M})are studied, where theD_{j}and the are the conditional first- and second-order moments. The optimal solution is found to be a parametric function of the conditional densities. By imposing a further restriction on the functional dependence offon theK_{j}, the optimal mapping becomes an intuitively pleasing function of the posterior probabilities. Given a finite number of features\psi_{1}(X),\cdots ,\psi_{L}(X), the problem of finding the best linear mappings tomfeatures is next investigated. The resulting optimum mapping is a linear combination of the projections of the posterior probabilities onto the subspace spanned by the\psi_{j}(X). The problem of finding the best single feature and seqnential feature selection is discussed in this framework. Finally, several examples are discussed.

A feature subset selection algorithm based on branch and bound techniques is developed to select the best subset of m features from an n-feature set. Existing procedures for feature subset selection, such as sequential selection and dynamic programming, do not guarantee optimality of the selected feature subset. Exhaustive search, on the other hand, is generally computationally unfeasible. The present algorithm is very efficient and it selects the best subset without exhaustive search. Computational aspects of the algorithm are discussed. Results of several experiments demonstrate the very substantial computational savings realized. For example, the best 12-feature set from a 24-feature set was selected with the computational effort of evaluating only 6000 subsets. Exhaustive search would require the evaluation of 2 704 156 subsets.

The scatter criterion applied to nonlinear mappings is discussed. The trace of the between-class scatter matrix normalized by the mixture scatter matrix is chosen as the criterion to measure the degree of overlap among class distributions, and it is shown that the {\em a posteriori} probability functions maximize this criterion. When a set of nonlinear features is selected, the projections of the {\em a posteriori} probability functions into the selected feature space are found, and they approximate the {\em a posteriori} probability functions. The mean-square error of the approximation represents the difference between the criterion value in the feature space and its optimum value. The estimation of the optimum criterion value and the evaluation of an additional new feature are also discussed.

Nonparametric clustering algorithms, including mode-seeking, valley-seeking, and unimodal set algorithms, are capable of identifying generally shaped clusters of points in metric spaces. Most mode and valley-seeking algorithms, however, are iterative and the clusters obtained are dependent on the starting classification and the assumed number of clusters. In this paper, we present a noniterative, graph-theoretic approach to nonparametric cluster analysis. The resulting algorithm is governed by a single-scalar parameter, requires no starting classification, and is capable of determining the number of clusters. The resulting clusters are unimodal sets.

Computation of the k-nearest neighbors generally requires a large number of expensive distance computations. The method of branch and bound is implemented in the present algorithm to facilitate rapid calculation of the k-nearest neighbors, by eliminating the necesssity of calculating many distances. Experimental results demonstrate the efficiency of the algorithm. Typically, an average of only 61 distance computations were made to find the nearest neighbor of a test sample among 1000 design samples.

The problem of clustering N objects into M classes may be viewed as a combinatorial optimization algorithm. In the literature on clustering, iterative hill-climbing techniques are used to find a locally optimum classification. In this paper, we develop a clustering algorithm based on the branch and bound method of combinatorial optimization. This algorithm determines the globally optimum classification and is computationally efficient

Nonparametric density gradient estimation using a generalized kernel approach is investigated. Conditions on the kernel functions are derived to guarantee asymptotic unbiasedness, consistency, and uniform consistency of the estimates. The results are generalized to obtain a simple mcan-shift estimate that can be extended in ak-nearest-neighbor approach. Applications of gradient estimation to pattern recognition are presented using clustering and intrinsic dimensionality problems, with the ultimate goal of providing further understanding of these problems in terms of density gradients.

Nonparametric estimation of the Bayes riskR^\astusing ak-nearest-neighbor (k-NN) approach is investigated. Estimates of the conditional Bayes errorr(X)for use in an unclassified test sample approach to estimateR^\astare derived using maximum-likelihood estimation techniques. By using the volume information as well as the class representations of thek-NN's toX, the mean-squared error of the conditional Bayes error estimate is reduced significantly. Simulations are presented to indicate the performance of the estimates using unclassified testing samples.

This paper is concerned with the use of "intrinsic dimensionality" in the representation of multivariate data sets that lie on nonlinear surfaces. The term intrinsic refers to the small, local-region dimensionality ( mI) of the surface and is a measure of the number of parameters or factors that govern a data generating process. The number mI is usually much lower than the dimensionality that is given by the standard Karhunen-Loève expansion. Representation of the data is accomplished by transforming the data to a linear space of mI dimensions using a new noniterative mapping procedure. This mapping gives a significant reduction in dimensionality and preserves the geometric data structure to a large degree. Single-and two-surface data sets are considered. Numerical examples are presented to illustrate both techniques.

Nonparametric density estimation using thek-nearest-neighbor approach is discussed. By developing a relation between the volume and the coverage of a region, a functional form for the optimumkin terms of the sample size, the dimensionality of the observation space, and the underlying probability distribution is obtained. Within the class of density functions that can be made circularly symmetric by a linear transformation, the optimum matrix for use in a quadratic form metric is obtained. For Gaussian densities this becomes the inverse covariance matrix that is often used without proof of optimality. The close relationship of this approach to that of Parzen estimators is then investigated.

A new nonparametric method of estimating the Bayes risk using an unclassified test sample set as well as a classified design sample set is introduced. The classified design set is used to obtain nonparametric estimates of the conditional Bayes risk of classification at each point of the unclassified test set. The average of these risk estimates is the error estimate. For large numbers of design samples the new error estimate has less variance than does an error-count estimate for classified test samples using the optimum Bayes classifier. The first application of the nonparametric method usesk-nearest neighbor (k-NN) estimates of the posterior probabilities to form the risk estimate. A large-sample analysis is made of this estimate. The expected value of this estimate is shown to be a lower bound on the Bayes error. A simple modification provides unbiased estimates of thek-NN classification error, thus providing an upper bound on the Bayes error. The second application of the method uses Parzen approximation of the density functions to obtain estimates of the risk and subsequently the Bayes error. Results of experiments on simulated data illustrate the small-sample behavior.

Feature extraction has been recognized as a useful technique for pattern recognition. Feature extraction is accomplished by constructing a mapping from the measurement space to a feature space. Often, the mapping is chosen from an arbitrarily specified parametric family by optimizing the parameters with respect to a separability criterion.

The problem of clustering multivariate observations is viewed as the replacement of a set of vectors with a set of labels and representative vectors. A general criterion for clustering is derived as a measure of representation error. Some special cases are derived by simplifying the general criterion. A general algorithm for finding the optimum classification with respect to a given criterion is derived. For a particular case, the algorithm reduces to a repeated application of a straightforward decision rule which behaves as a valley-seeking technique. Asymptotic properties of the procedure are developed. Numerical examples are presented for the finite sample case.

A family of nonparametric clustering criteria has been previously proposed by the authors. One particular member of this family was subjected to analysis and experimentation. This criterion was shown by heuristic argument, experimentation, and approximate asymptotic analysis to exhibit ``valley-seeking'' behavior. In this paper, we consider a more general class of valley-seeking criteria. The results bear a close resemblance to Parzen's theory of probability density estimation. This similarity is exploited to develop sufficient conditions for a criterion to be valley seeking in the asymptotic sense.

In an optimum pattern-recognition system the error rate is determined by the reject function. This correspondence describes how this property may be exploited to provide quantitative tests of model validity using unclassified test samples. These tests are basically goodness-of-fit tests for a function of the observations. One of these tests is shown to provide an improved estimate of error in Monte Carlo studies of complex systems. Results are given for normal distributions when parameters are estimated. In this case error estimates obtained from the empirical reject rate underestimate the actual error and performance depends on the ratio of design samples to dimension.

This paper discusses methods of estimating the probability of error for the Bayes' classifier which must be designed and tested with a finite number of classified samples. The expected difference between estimates is discussed. A simplifled algorithm to compute the leaving-one-out method is proposed for multivariate normal distributions wtih unequal co-variance matrices. The discussion is extended to nonparametric classifiers by using the Parzen approximation for the density functions. Experimental results are shown for both parametric and nonparametric cases.

An algorithm for the analysis of multivariant data is presented along with some experimental results. The basic idea of the method is to examine the data in many small subregions, and from this determine the number of governing parameters, or intrinsic dimensionality. This intrinsic dimensionality is usually much lower than the dimensionality that is given by the standard Karhunen-Loève technique. An analysis that demonstrates the feasability of this approach is presented.

The properties of a two-dimensional display whose coordinates are the Euclidean distances from two points in a multivariate space are presented. When used in conjunction with three linear normalization procedures, this display is a useful tool in both supervised and unsupervised classification problems. In addition, some geometric structure is preserved by this mapping. Examples using well-known Iris data are presented to demonstrate the display characteristics.

In the statistical method proposed by Trunk [2], [3], he calculates the density function p(X|N) where X= [xl. .. xn,]Tis the observed random vector and N(= 1, 2,...) is the intrinsic number of parameters for the random vector. The most likely N for the observed vectors is determined by applying the multihypotheses test to these density functions. The number of random variables are reduced by using sufficient statistics such as the ratios of local distances and certain angles between local vectors, rather than the original x1,...,xn.

Signature analysis of small, complex, cyclic mechanisms is discussed. An envelope preprocessor for isolating signal events relating to mechanical impacts is developed. A recognition system based on second-order (normal) statistics is used and the use of statistical procedures for signature intepretation is presented. Experimental evidence is presented to support the validity of this approach to mechanical diagnostics signature analysis.

The Karhunen-Lo6ve expansion has been used previously to extract important features for representing samples taken from a given distribution. A method is developed herein to use the Karhunen-Loeve expansion to extract features relevant to classification of a sample taken from one of two pattern classes. Numerical examples are presented to illustrate the technique.

Many algorithms for grouping data without supervision depend on some criterion. We state two basic requirements such criteria should meet and we discuss several criteria in terms of these requirements. An attempt to satisfy both requirements simultaneously with a simple criterion leads us to introduce a linear transformation of the data. Although our principal result is for a two category problem, we present discussion and an example for the many category problem as well.

An algorithm is presented for calculating recognition error when applying pattern vectors to an optimum Bayes' classifier. The pattern vectors are assumed to come from two classes whose populations have Gaussian statistics with unequal covariance matrices and arbitrary a priori probabilities. The quadratic discriminant function associated with a Bayes' classifier is used as a one-dimensional random variable from which the probability of error is calculated, once the distribution of the discriminant function is obtained.

A new criterion for measuring separability of two pattern classes is given that is based on the determination of an averaged minimum distance from the mean feature vectors of two classes to an optimal separating hypersurface determined by Baye's postulate.